- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 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
int NOD(int a,int b)
{
if(a==0)
{
return b;
}
if(b==0)
{
return a;
}
if(a==b)
{
return a;
}
if((a%2==0)&&(b%2==0))
{
return 2*NOD(a/2,b/2);
}
else if((a%2==0)&&(b%2!=0))
{
return NOD(a/2,b);
}
else if((a%2!=0)&&(b%2==0))
{
return NOD(a,b/2);
}
else if((a%2!=0)&&(b%2!=0))
{
return NOD(b,abs(a-b));
}
else return 1;
/*
1. НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
2. НОД(1, n) = 1; НОД(m, 1) = 1;
3. Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
4. Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
5. Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
6. Если m, n нечётные, то НОД(m, n) = НОД(n, |m - n|).
*/
}
Follow us!
И да, давайте не будем показывать автору решето Эратосфена!
Все эти подпрыгивания с четностью и деленьями на 2 - попытки "т.н.оптимизации" решетом, из которого взята только двойка. Почему остатки от деления на 3 не проверяются?
Хотя никакого решета не нужно. Если уж работать с делением, то можно сделать так.
Так что в топку решето. Последний пример заруливает решето в минуса между вторым и третьим раундами.
>Алгоритм Евклида - прошлый век!
У вас есть алгоритм нашего века?
Как раз таки эта 30-строчная конструкция, имхо, отличный пример говнокода, в то время как алгоритм Евклида пишется в 5-6 строк))
">Алгоритм Евклида - прошлый век!" - сарказм, если что
Естественно, что приведённая как "говнокод" версия плоха, она использует рекурсию и не сдвигает чётную разность перед следующим вызовом.
(j/k)
Вы еще скажите, что считать числа Фибоначчи рекурсией неэффективно. Но описаны они именно реккурентным соотношением.
Поэтому в посте не говнокод - а отличный школьный пример реализации алгоритма Евклида.
fil teh pawer.
>считать числа Фибоначчи рекурсией неэффективно
Да. Вообще считать рекурсией не эффективно, потому что каждый раз память забивается ненужной числовой информацией, а иногда очень большими числами, хотя хранить их в памяти не нужно.
Например, в общем случае: вычисление длины кратчайшего пути выхода из лабиринта. Рекурсией неэффективно по времени, но требует гораздо меньше ресурсов по памяти. Нерекурсивным волновым методом получится быстрее, но памяти потребует - не горюй. Потому что рекурсия одновременно "помнит" один путь, а волновой метод - одновременно все возможные.
Такшта, каждому овощу - свой шесток. ;) А язык - дело наживное.
Другое дело, когда действительно нужно запомнить.
А в рядах, обычно, ничего запоминать не нужно, потому это и есть банальное забивание памяти.
А алгоритм Евклида, между прочим, ищет НОД последовательным делением с остатком, а не вычитанием.
Правда, существуют два поверья:
1. компиляторы сами оптимизируют деление в сдвиг.
2. компиляторы сами оптимизируют остаток от деления в конъюнкцию
Лично я до сих пор пользуюсь двоичными операторами по привычке.
Нужно к каждому отдельному компилятору читать документацию, а ещё лучше разбираться в сгенерированном машинном коде. Ещё лучше именно для того приложения, которое должно работать, а не приём отдельно.
Вообще, я только за ту оптимизацию, которую глазом вижу, а не миллисекундами. Доли секунд вообще могут сожраться системой. (кстати тоже весело: Макконелл писал, что можно получать существенную оптимизацию, если писать код выровненными кусками; я ничего не понял, но впечатляет заморочка; связано с загрузкой кода в рабочую память процессора)
Вот если я сдвиг написал и у меня программа работает стабильно сорок минут вместо часа -- значит верно воткнуто =]