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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.88
morphling
 Аватар для morphling
-9 / 19 / 1
Регистрация: 26.06.2010
Сообщений: 181
24.08.2011, 20:58     НОК для N чисел #1
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%
Использовать файлы для ввода/вывода

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

Добавлено через 11 минут
Цитата Сообщение от iama Посмотреть сообщение
morphling, речь, я понимаю, об этой задаче? У меня решение есть, но выкладывать пока не буду, там только 34 из 540 решили. Ваш код не читал, но подскажу - ответ может быть больше 64-битного беззнакового целого, нужна длинка, кроме того нужно факторизовать каждое число последовательности, и суммировать коэфициенты, тогда получим разложение на простые искомого числа. После этого просто реализуем умножение длинного числа на простое, и выводим результат
насчет разложения я знаю.... я вот попытался без него сделать.... тока вот во времени не уложился не 3%(((
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 21:38     НОК для N чисел #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
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 21:48     НОК для N чисел #6
Olga_, я имел в виду ваше решение, исходящее из основной теоремы арифметики, но неясно изъяснился а задача и с длинной арифметикой решается красиво

Не по теме:

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

Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 21:51     НОК для N чисел #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
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
24.08.2011, 21:57     НОК для N чисел #8
Прямо над "Быстрым ответом" есть строка "Редактор формул", которую можно раскрыть пиктограммкой справа. Там можно с помощью предпросмотра сгенерировать код нужной формулы, набирая вручную или с помощью шаблонов. Я долго не замечал эту строчку, пока носом не ткнули
iama
24.08.2011, 22:02
  #9

Не по теме:

Olga_, спасибо

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

Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 22:03     НОК для N чисел #10
Цитата Сообщение от grizlik78 Посмотреть сообщение
Прямо над "Быстрым ответом" есть строка "Редактор формул"...
Как в ворде сделано, не как в обычном WinEdt
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.08.2011, 14:13     НОК для N чисел
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.08.2011, 14:13     НОК для N чисел #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. Засчитано

Yandex
Объявления
26.08.2011, 14:13     НОК для N чисел
Ответ Создать тему
Опции темы

Текущее время: 19:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru