Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.88
morphling
-9 / 19 / 1
Регистрация: 26.06.2010
Сообщений: 181
#1

НОК для N чисел - C++

24.08.2011, 20:58. Просмотров 3156. Ответов 10
Метки нет (Все метки)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//---------------------------------------------------------------------------
 
#include <stdio.h>
#include <stdlib.h>
 
 
//---------------------------------------------------------------------------
int Nok(int *mass, short N, int m)
    {
      short kol = N;
      short f = 0;
 
 
        while(1)
                {
                 N = kol;
                    while(N)
                          {
                              N--;
                            if (m%mass[N]==0)
                               {
                                 f++;
                               }
                               else break;
                          }
 
                    if (f == kol)
                       {
                         return m;
                       }
                       else f = 0;
                    m++;
                }
      return m;
    }
 
int main()
{
    short N, c;
    int *mas;
    int max = - 145;
    FILE *f;
    f = fopen("input.txt","r");
    fscanf(f, "%d", &N);
    mas = (int*)malloc(N*sizeof(int));
       c = N;
    while(c)
       {
        c--;
        fscanf(f,"%d",&mas[c]);
 
        if (max < mas[c])
           {
             max = mas[c];
           }
       }
    fclose(f);
    f = fopen("output.txt","w");
    fprintf(f, "%d\n", Nok(mas, N, max));
    fclose(f);
 
    free(mas);
    return 0;
}
//---------------------------------------------------------------------------
вот код для нахождения НОК для N чисел... считывается N потом N количество чисел.... как мне ее оптимизировать что бы менее чем за секунду выполнялась?

Добавлено через 2 минуты

Не по теме:


Результат по тестам:
1. Засчитано
2. Засчитано
3. Засчитано
4. Засчитано
5. Засчитано
6. Исчерпан лимит времени
7. Засчитано
8. Исчерпан лимит времени
9. Засчитано
10. Засчитано
11. Исчерпан лимит времени
Дата отправки: 24 Августа 2011 19:51:01
Задача: 135. НОК
Автор решения: kubachi
Компилятор: Gnu C++
Среднее время выполнения: 0.292 секунды
Максимальное время выполнения: 1.031 секунды из 1 секунда, 103.1%
Лимит памяти: 856 KB из 65536 KB, 1.3%
Использовать файлы для ввода/вывода

Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.08.2011, 20:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос НОК для N чисел (C++):

Как найти НОК и НОД нескольких чисел или n чисел ? - C++
Собственно вопрос в теме . Как найти двух чисел нод ,нок я могу .А как это найти НОД,НОК n чисел ? Помогите пожалуйста !

Нахождение НОД и НОК двух чисел - C++
Вот код программы на Паскале нужно переделать на С++ { Рекурсивные алгоритмы: нахождения НОД и НОК двух чисел } var a,b:longint; ...

Вычисление нок и нод переменных натуральных чисел - C++
Здравствуйте. Искал подобную тему по форуму, но там все либо на 2 числа либо на несколько, но с фиксированным числом после компиляции....

Как при использовании цикла while найти НОК 3х чисел? - C++
Объясните плс как цикл такой сделать?

Найти наименьшее общее кратное (НОК) натуральных чисел С++ - C++
Вот мой исходник : #include &lt;iostream.h&gt; int NSD (int a, int b) { while (a!=0 &amp;&amp; b!=0) { if (a&gt;b) { ...

Посчитайте НОК чисел второй последовательности. doesnt work - C++
#include &lt;iostream&gt; #include &lt;vector&gt; int GCD(int a, int b) { if (b == 0) return a; else return GCD(b, a%b); ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
24.08.2011, 21:10 #2
Можно ссылку на задачу? (которая находится на e-olimp )? Т.к. нужны ограничения.
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 21:20 #3
morphling, речь, я понимаю, об этой задаче? У меня решение есть, но выкладывать пока не буду, там только 34 из 540 решили. Ваш код не читал, но подскажу - ответ может быть больше 64-битного беззнакового целого, нужна длинка, кроме того нужно факторизовать каждое число последовательности, и суммировать коэфициенты, тогда получим разложение на простые искомого числа. После этого просто реализуем умножение длинного числа на простое, и выводим результат
morphling
-9 / 19 / 1
Регистрация: 26.06.2010
Сообщений: 181
24.08.2011, 21:33  [ТС] #4
Можно..... Вот

Добавлено через 11 минут
Цитата Сообщение от iama Посмотреть сообщение
morphling, речь, я понимаю, об этой задаче? У меня решение есть, но выкладывать пока не буду, там только 34 из 540 решили. Ваш код не читал, но подскажу - ответ может быть больше 64-битного беззнакового целого, нужна длинка, кроме того нужно факторизовать каждое число последовательности, и суммировать коэфициенты, тогда получим разложение на простые искомого числа. После этого просто реализуем умножение длинного числа на простое, и выводим результат
насчет разложения я знаю.... я вот попытался без него сделать.... тока вот во времени не уложился не 3%(((
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 21:38 #5
Цитата Сообщение от iama Посмотреть сообщение
кроме того нужно факторизовать каждое число последовательности, и суммировать коэффициенты, тогда получим разложение на простые искомого числа.
Не понятно какие коэффициенты, но вот формула для НОК. Пусть натуральные числа http://www.cyberforum.ru/cgi-bin/latex.cgi?a_1, a_2,...,a_m представимы в следующем виде:
http://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
a_1=p_1^{\alpha_{1}}p_2^{\alpha_{2}}...p_n^{\alpha_{n}},~<br />
a_2=p_1^{\beta_{1}}p_2^{\beta_{2}}...p_n^{\beta_{n}},<br />
...<br />
a_m=p_1^{\gamma_{1}}p_2^{\gamma_{2}}...p_n^{\gamma_{n}},<br />
Тогда
http://www.cyberforum.ru/cgi-bin/latex.cgi?NOK(a_1,a_2,...,a_m)= p_1^{max\{\alpha_1,\beta_1,...,\gamma_1\}}p_2^{max\{\alpha_2,\beta_2,...,\gamma_2\}}...p_n^{max\{\alpha_n,\beta_n,...,\gamma_n\}}.

Если бы не длинная арифметика, то задачу можно очень красиво решить.
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 21:48 #6
Olga_, я имел в виду ваше решение, исходящее из основной теоремы арифметики, но неясно изъяснился а задача и с длинной арифметикой решается красиво

Не по теме:

Не подскажете, как LaTEX'ом пользоваться? уже больше года на форуме, а до сих пор не знаю

Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 21:51 #7
Цитата Сообщение от iama Посмотреть сообщение

Не по теме:

Не подскажете, как LaTEX'ом пользоваться? уже больше года на форуме, а до сих пор не знаю

В кодах BB (между latex и /latex) набираете формулы. Например, http://www.cyberforum.ru/cgi-bin/latex.cgi?a^n это a^n, http://www.cyberforum.ru/cgi-bin/latex.cgi?a_n это a_n и т.д. А какие формулы конкретно вам надо? Да, задача красиво решается, только в самом конце длинная арифметика нужна, а так достаточно одного массива, где будет вся информация последовательного вычисления НОК и свойство NOK(a1,a2,...,an) = NOK(NOK(...NOK(a1,a2),...an))
grizlik78
Эксперт С++
1908 / 1440 / 111
Регистрация: 29.05.2011
Сообщений: 2,996
24.08.2011, 21:57 #8
Прямо над "Быстрым ответом" есть строка "Редактор формул", которую можно раскрыть пиктограммкой справа. Там можно с помощью предпросмотра сгенерировать код нужной формулы, набирая вручную или с помощью шаблонов. Я долго не замечал эту строчку, пока носом не ткнули
iama
24.08.2011, 22:02
  #9

Не по теме:

Olga_, спасибо

grizlik78, 2 минуты искал, где ж оно еще раз спасибо

Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 22:03 #10
Цитата Сообщение от grizlik78 Посмотреть сообщение
Прямо над "Быстрым ответом" есть строка "Редактор формул"...
Как в ворде сделано, не как в обычном WinEdt
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.08.2011, 14:13 #11
morphling, если задача из e-olimp, то без длинной арифметики не обойтись. Могу предложить свой вариант (проходит все тесты). Только код не оптимизирован (это можете вы проделать).

Вот

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#define Q 10000  // система счисления
#define N 100000
 
typedef int DIGIT;
int count[101];
DIGIT a[N], b[N];
int alen, blen;
 
// вывод конечного результата
void Print(DIGIT *a, int n)
{
   int i;
   for (i = n - 1; i >=0 ; i--)
      printf("%d", a[i]);
   printf("\n");
}
 
// нахождение максимальных степеней простых чисел
void Count(unsigned int n)
{
  unsigned int i;
  int a[101] = {0};
  i = 2;
  while (n != 1)
  {
      if (n % i == 0)
      {
          a[i]++;
          n /= i;
      }
      else
          if (i*i > n)
             i = n;
          else i++;
  }
  for (i = 1; i < 101; i++)
     if (a[i] > count[i])
        count[i] = a[i];
}
 
// сумма (длинная арифметика, числа перевернуты)
void Sum(DIGIT *a, int *alen, DIGIT *b, int *blen)
{
   DIGIT ost, buf;
   int i;
   i = ost = 0;
   while (i < *alen && i < *blen)
   {
       buf = (a[i] + b[i] + ost) / Q;
       a[i] = (a[i] + b[i] + ost) % Q;
       ost = buf;
       i++;
   }
   while (i < *alen)
   {
      buf = (a[i] + ost) / Q;
      a[i] = (a[i] + ost) % Q;
      ost = buf;
      i++;
   }
   while (i < *blen)
   {
      buf = (b[i] + ost) / Q;
      a[i] = (b[i] + ost) % Q;
      ost = buf;
      i++;
   }
   if (ost)
      a[i++] = ost;
   *alen = i;
}
 
// произведение (длинная арифметика, числа перевернуты)
void Product(DIGIT *a, int *alen, DIGIT *b, int blen)
{
   int i, j, buflen, prodlen = 0;
   DIGIT prod[N] = {0}, buf[N], ost;
   for (i = 0; i < blen; i++)
   {
      for (j = 0; j < i; j++)
         buf[j] = 0;
      ost = 0;
      for (j = 0; j < *alen; j++)
      {
         buf[i + j] = (a[j] * b[i] + ost) % Q;
         ost = (a[j] * b[i] + ost) / Q;
      }
      buflen = i + j;
      if (ost)
         buf[buflen++] = ost;
      Sum(prod, &prodlen, buf, &buflen);
   }
   for (i = 0; i < prodlen; i++)
      a[i] = prod[i];
   *alen = prodlen;
}
 
// перевод числа в массив в перевенутом виде
void ToArray(long x, DIGIT *a, int *n)
{
   int i = 0;
   do
   {
       a[i++] = x % Q;
       x /= Q;
   }
   while (x);
   *n = i;
}
 
 
int main()
{
  unsigned int n, i, j;
  unsigned int A[21];
 
  scanf("%u", &n);
  for (i = 0; i < n; i++)
  {
     scanf("%u", &A[i]);
     Count(A[i]);
  }
  ToArray(1, a, &alen);
  for (i = 1; i < 101; i++)
  {
     ToArray(i, b, &blen);
     for(j = 0; j < count[i]; j++)
        Product(a, &alen, b, blen);
  }
 
  Print(a, alen);
  return 0;
}


Добавлено через 43 минуты

Не по теме:


Среднее время выполнения: 0.016 секунды
Максимальное время выполнения: 0.031 секунды из 1 секунда, 3.1%
Лимит памяти: 1456 KB из 65536 KB, 2.2%
Результат по тестам:
1. Засчитано 2. Засчитано 3. Засчитано 4. Засчитано 5. Засчитано 6. Засчитано 7. Засчитано 8. Засчитано 9. Засчитано 10. Засчитано 11. Засчитано

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.08.2011, 14:13
Привет! Вот еще темы с ответами:

Найти наименьшее общее кратное (НОК) n натуральных чисел - C++
Есть задача: НОК Найти наименьшее общее кратное (НОК) n натуральных чисел. Технические условия Вход В первой...

Разработать функцию, которая находит НОК двух целых чисел. - C++
Разработать функцию, которая находит НОК двух целых чисел.

Вычислить НОК (наименьшее общее кратное) двух натуральных чисел A и B - C++
Задача 7. Вычислить НОК (наименьшее общее кратное) двух натуральных чисел A и B.

Найти НОК (наименьшее общее кратное) массива натуральных чисел - C++
Найти НОК (наименьшее общее кратное) массива натуральных чисел. Спасибо за помощь :)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.08.2011, 14:13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru