Перебор:
k = a; // или k = b;
while ( a % k != 0 ||
b % k != 0 )
k --;
printf ("НОД(%d,%d)=%d", a, b, k);
много операций для больших чисел
ИЛИ
НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)
НОД (1998, 2) = НОД (1996, 2) = … = 2
Пример:
много шагов при большой разнице чисел:
= НОД (7, 7) = 7
НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7
Пример:
Еще один вариант:
НОД(2·a,2·b)= 2·НОД(a, b)
НОД(2·a,b)= НОД(a, b) // при нечетном b
int NOD ( int a, int b )
{
while ( a != b )
if ( a > b ) a -= b;
else b -= a;
return a;
}
int NOD ( int a, int b )
{
if ( a*b == 0 ) return a + b;
if ( a < b )
return NOD ( a, b%a );
else return NOD ( a%b, b );
}
int NOD ( int a, int b )
{
while ( a*b != 0 )
if ( a > b ) a = a % b;
else b = b % a;
return a + b;
}
for ( i = 1; i <= N; i++ ) {
isPrime = 1;
for ( k = 2; k < i ; k++ )
if ( i % k == 0 ) {
isPrime = 0;
break;
}
if ( isPrime )
printf("%d\n", i);
}
k*k <= i
k*k <= i
O(N2)
растет не быстрее N2
Алгоритм:
начать с k = 2;
«выколоть» все числа через k, начиная с 2·k;
перейти к следующему «невыколотому» k;
если k·k <= N, то перейти к шагу 2;
напечатать все числа, оставшиеся «невыколотыми».
высокая скорость, количество операций
нужно хранить в памяти все числа от 1 до N
O((N·log N)·log log N )
2
3
Массив A[N+1], где
A[i]=1, если число i не «выколото»,
A[i]=0, если число i «выколото».
100! < 100100
201 цифра
201/6 ≈ 34 ячейки
Хранить число по группам из 6 цифр – это значит представить его в системе счисления с основанием
d = 1000000.
{A} = 1;
for ( k = 2; k <= 100; k ++ )
{ A} = {A} * k;
... // вывести { A}
Алгоритм:
{A} – длинное число, хранящееся как массив
умножение длинного числа на «короткое»
c0
перенос, r1
568901·3 + 2 = 1 706705
c1
r2
1234·3 + 1 = 3703
c2
c0 = ( a0·k + 0) % d
r1 = ( a0·k + 0) / d
c1 = ( a1·k + r1) % d
r2 = ( a1·k + r1) / d
c2 = ( a2·k + r2) % d
r3 = ( a2·k + r2) / d
...
пока не кончились цифры числа {A} или есть перенос
for ( i = len-1; i >= 0; i -- )
if ( i == len-1 ) printf ( "%ld", A[i] );
else printf ( "%.6d", A[i] );
printf ("%d", A.empty() ? 0 : a.back()); for (int i=(int)A.size()-2; i>=0; --i) printf ("%06d", a[i]);
здесь небольшой тонкий момент: нужно не забыть записать приведение типа (int), поскольку в противном случае число будут беззнаковым, и если , то при вычитании произойдёт переполнение
при малом количестве вариантов можно решить простым перебором
при большом количестве вариантов на решение перебором может потребоваться огромное время (для ряда задач другие алгоритмы неизвестны)
Точные методы:
простой перебор;
метод ветвей и границ;
метод Литтла;
…
Приближенные методы:
метод случайных перестановок (Matlab);
генетические алгоритмы;
метод муравьиных колоний;
…
большое время счета для больших N
O(N!)
не гарантируется оптимальное решение
Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:
Email: Нажмите что бы посмотреть