Проблема толи лыжи не едут.. то ли..
Nag_X
Новичок
5/29/2006, 10:25:04 PM
Господа программисты, такая проблема... пишу контрольную по С++
Задача звучит так: Найти сумму всех чётных делителей натурального числа. Ну вроде как разобрался составил функцию:
Написал консольку на C++ Bilder 5...
И тут началось кино и немцы в хате...
Ну ладно думаю масдайность глюкавая мне мозг парит... нет на другом компе таже лажа, я раньше дела с С++ не имел, прошу помочь...
Вот две функции как бы для одного и того же конечного результата, где я не прав или укажите как надо:
int sumdel(int n)
№1
{ int s,i=2 ;
while(i>n)
{if(n%i==0) s+=i;
++i;
}
return s;
}
№2
int sumdel(int n)
{ int s=n,i ;
for( i=2; i>n;) i+=2;
if(n%i==0) s+=i;
return s;
}
Задача звучит так: Найти сумму всех чётных делителей натурального числа. Ну вроде как разобрался составил функцию:
Написал консольку на C++ Bilder 5...
И тут началось кино и немцы в хате...
Ну ладно думаю масдайность глюкавая мне мозг парит... нет на другом компе таже лажа, я раньше дела с С++ не имел, прошу помочь...
Вот две функции как бы для одного и того же конечного результата, где я не прав или укажите как надо:
int sumdel(int n)
№1
{ int s,i=2 ;
while(i>n)
{if(n%i==0) s+=i;
++i;
}
return s;
}
№2
int sumdel(int n)
{ int s=n,i ;
for( i=2; i>n;) i+=2;
if(n%i==0) s+=i;
return s;
}
DELETED
Акула пера
5/29/2006, 10:57:56 PM
Вот тебе корректные варианты:
CODE
int sumdel(int n)
{
int s = 0, i = 2;
while(n >= i)
{
if(!(n % i))
s += i;
i += 2;
}
return s;
}
int sumdel1(int n)
{
int s = n, i;
for(i = 2; n > i; i += 2)
{
if(!(n % i))
s += i;
}
return s;
}
Багов было просто немерено. Начиная от неверного сравнения и т.д.
А вот этот вариант мне больше всего нравится:
CODE
int sumdel2(int n)
{
int sum = n;
for(int i = 2; n > i; i += 2)
sum += n % i ? 0 : i;
return sum;
}
CODE
int sumdel(int n)
{
int s = 0, i = 2;
while(n >= i)
{
if(!(n % i))
s += i;
i += 2;
}
return s;
}
int sumdel1(int n)
{
int s = n, i;
for(i = 2; n > i; i += 2)
{
if(!(n % i))
s += i;
}
return s;
}
Багов было просто немерено. Начиная от неверного сравнения и т.д.
А вот этот вариант мне больше всего нравится:
CODE
int sumdel2(int n)
{
int sum = n;
for(int i = 2; n > i; i += 2)
sum += n % i ? 0 : i;
return sum;
}
tetro
Специалист
5/29/2006, 11:07:55 PM
За что люблю коллегу, так за лаконичнисть формулировок: немногое, но много...
А что будет если n нечетно?
А что будет если n нечетно?
DELETED
Акула пера
5/30/2006, 12:01:48 AM
(tetro @ 29.05.2006 - время: 19:07)А что будет если n нечетно?
Точно :) в последних двух вариантах есть глюк, который я не исправил.
Правильно будет так:
CODE
int sumdel1(int n)
{
int s = 0, i;
for(i = 2; n >= i; i += 2)
{
if(!(n % i))
s += i;
}
return s;
}
int sumdel2(int n)
{
int sum = 0;
for(int i = 2; n >= i; i += 2)
sum += n % i ? 0 : i;
return sum;
}
Специально нечетный варианты никак не обрабатываются, мой принцип: никогда не оптимизируй заранее.
Точно :) в последних двух вариантах есть глюк, который я не исправил.
Правильно будет так:
CODE
int sumdel1(int n)
{
int s = 0, i;
for(i = 2; n >= i; i += 2)
{
if(!(n % i))
s += i;
}
return s;
}
int sumdel2(int n)
{
int sum = 0;
for(int i = 2; n >= i; i += 2)
sum += n % i ? 0 : i;
return sum;
}
Специально нечетный варианты никак не обрабатываются, мой принцип: никогда не оптимизируй заранее.
Nag_X
Новичок
5/30/2006, 4:36:23 AM
Спасибо большое. Как я понял, двигался в правильном направлении..))) Ток заплутал в трёх соснах... Ещё раз спасибо....
tetro
Специалист
5/30/2006, 3:33:27 PM
Глюк увидел, поэтому и спросил... просто не было времени чинить, позвали на заседание ...
GrAnd
Профессионал
5/30/2006, 9:35:11 PM
Ну перво-наперво бросается в глаза, что i пробегает значения от 2 до n, т.е. задача имеет временную сложность порядка O(n). Сразу возникает желание (если n четно), заставить i пробегать значения до n/2, а n прибавить потом. Но это на порядок сложности не повлияет никак, разве что уменьшит время работы в 2 раза.
Вопрос такой: А нельзя ли создать алгоритм с временной сложностью порядка O(ln(n)) или O(sqrt(n))?
Кажется, что-то такое возможно.
Ведь самый большой делитель должен быть n. учтя это мы можем откинуть сразу половину из возможных кандидатов и проверить, является ли число n/2 целым. Оно является, если n четно. Прибавив n/2 к n можно отбросить все i свыше n/3 и проверить, является ли n/3 целым (делится ли n на 3) и т.д. Таким образом отбрасываем сразу значительную часть от кандидатов на делители. Правда, с каждым последующим шагом, отбрасываемая часть уменьшается и станет меньше 1. Но и это не очень страшно, т.к. можно затормозиться, когда количество кандидатов станет равно корню из n. остальные можно получить делением n на уже найденные. Только, если число n является квадратом и найден делитель i, являющийся корнем квадратным, то прибавлять n/i не надо - оно рано i.
Кстати, из постановки задачи не совсем ясно, делители ли должны быть четными, или их номера. Вроде бы первое ...
Очень мешает то, что нужно находить только четные делители. Поэтому, если найден некий четный делитель i, то нужно не только найти делитель n/i, но и проверить на четность оба делителя (i и n/i) и прибавить только четные.
Избавиться от этого поможет тот факт, что сумма четных делителей числа равна удвоенной сумме ВСЕХ делителей половины этого числа. Тогда можно будет идти не сверху, а снизу, проверяя делители, начиная с 1, до корня из половины n).
Таким образом, алгоритм примерно такой:
1. Если n<=0 или нечетно, то возврат 0.
2. Получаем целые числа n2=n/2; nr=целая часть(корень_квадратный(n-1))+1; s=0.
3. Для i от 1 до nr-1 делать проверку: если n2 делится на i, то s=s+i+n/i.
4. Если n=nr*nr (n - квадрат) , то s=s+nr.
5. Вернуть s+s.
Прошу прощения за псевдокод. Последний раз на C я писал лет так 10 назад или чуть поменьше. Поэтому специально избегал синтаксиса C, ибо мог и ошибиться.
Маленькая тонкость. Т.к. при извлечении корня квадратного возможны ошибки, в результате которого целая часть окажется меньше на 1, то мною применен следующий алгоритм вычисления nr, основанный на том, что сумма первых нечетный чисел равна квадрату:
1. n1=0; nr=0;
2. Пока n1 < n2 делай
2.1. n1=n1+nr+nr+1;
2.2. nr=nr+1;
Как ни странно, это работает ...
Временная сложность данного алгоритма O(sqrt(n)). Алгоритм с временной сложностью O(ln(n)) придумать не удалось. Может быть кто-то сумеет.
Вопрос такой: А нельзя ли создать алгоритм с временной сложностью порядка O(ln(n)) или O(sqrt(n))?
Кажется, что-то такое возможно.
Ведь самый большой делитель должен быть n. учтя это мы можем откинуть сразу половину из возможных кандидатов и проверить, является ли число n/2 целым. Оно является, если n четно. Прибавив n/2 к n можно отбросить все i свыше n/3 и проверить, является ли n/3 целым (делится ли n на 3) и т.д. Таким образом отбрасываем сразу значительную часть от кандидатов на делители. Правда, с каждым последующим шагом, отбрасываемая часть уменьшается и станет меньше 1. Но и это не очень страшно, т.к. можно затормозиться, когда количество кандидатов станет равно корню из n. остальные можно получить делением n на уже найденные. Только, если число n является квадратом и найден делитель i, являющийся корнем квадратным, то прибавлять n/i не надо - оно рано i.
Кстати, из постановки задачи не совсем ясно, делители ли должны быть четными, или их номера. Вроде бы первое ...
Очень мешает то, что нужно находить только четные делители. Поэтому, если найден некий четный делитель i, то нужно не только найти делитель n/i, но и проверить на четность оба делителя (i и n/i) и прибавить только четные.
Избавиться от этого поможет тот факт, что сумма четных делителей числа равна удвоенной сумме ВСЕХ делителей половины этого числа. Тогда можно будет идти не сверху, а снизу, проверяя делители, начиная с 1, до корня из половины n).
Таким образом, алгоритм примерно такой:
1. Если n<=0 или нечетно, то возврат 0.
2. Получаем целые числа n2=n/2; nr=целая часть(корень_квадратный(n-1))+1; s=0.
3. Для i от 1 до nr-1 делать проверку: если n2 делится на i, то s=s+i+n/i.
4. Если n=nr*nr (n - квадрат) , то s=s+nr.
5. Вернуть s+s.
Прошу прощения за псевдокод. Последний раз на C я писал лет так 10 назад или чуть поменьше. Поэтому специально избегал синтаксиса C, ибо мог и ошибиться.
Маленькая тонкость. Т.к. при извлечении корня квадратного возможны ошибки, в результате которого целая часть окажется меньше на 1, то мною применен следующий алгоритм вычисления nr, основанный на том, что сумма первых нечетный чисел равна квадрату:
1. n1=0; nr=0;
2. Пока n1 < n2 делай
2.1. n1=n1+nr+nr+1;
2.2. nr=nr+1;
Как ни странно, это работает ...
Временная сложность данного алгоритма O(sqrt(n)). Алгоритм с временной сложностью O(ln(n)) придумать не удалось. Может быть кто-то сумеет.
DELETED
Акула пера
5/30/2006, 10:19:24 PM
А не напоминает ли вам это все факторизацию, у которой текущая стоимость sqrt(a)/2? Если тут кто напишет на ln(a) - чур я его импрессарио.. :)
tetro
Специалист
5/30/2006, 11:31:51 PM
Естественно, можно конечно через решето Эрастофена... т.е. разложить на делители и посмотреть потом собрав:
Т.е. двигаемся в двух направлениях: строим послед. простых чисел и параллельно пытаемся на них поделить, как с двух сторон сойдемся так нам и будет счастье
Не помню какова сложность решета (тут точно, что не более sqrt(a)/2), но насчет лога, не уверен...
Т.е. двигаемся в двух направлениях: строим послед. простых чисел и параллельно пытаемся на них поделить, как с двух сторон сойдемся так нам и будет счастье
Не помню какова сложность решета (тут точно, что не более sqrt(a)/2), но насчет лога, не уверен...
Nag_X
Новичок
5/31/2006, 2:45:35 AM
И тут я понял...как мало я знаю... 
DELETED
Акула пера
5/31/2006, 3:02:18 AM
(GrAnd @ 30.05.2006 - время: 17:35) Временная сложность данного алгоритма O(sqrt(n)). Алгоритм с временной сложностью O(ln(n)) придумать не удалось. Может быть кто-то сумеет.
+1
Но! Основная заповедь разработчика: "Keep It Simple, Stupid".
+1
Но! Основная заповедь разработчика: "Keep It Simple, Stupid".
DELETED
Акула пера
5/31/2006, 3:59:04 AM
(простите за assa )
(tetro @ 30.05.2006 - время: 19:31)Естественно, можно конечно через решето Эрастофена...
А есть трехлетней давности полиномиальный алгоритм факторизации со стоимостью (уж простите, я по старинке) O(ln^(6+e)n). Ну куда нам тут с титанами бороться.
(GregZ @ 30.05.2006 - время: 23:02)Но! Основная заповедь разработчика: "Keep It Simple, Stupid".
Вы просто неправильно понимаете эту фразу. :)
)(tetro @ 30.05.2006 - время: 19:31)Естественно, можно конечно через решето Эрастофена...
А есть трехлетней давности полиномиальный алгоритм факторизации со стоимостью (уж простите, я по старинке) O(ln^(6+e)n). Ну куда нам тут с титанами бороться.
(GregZ @ 30.05.2006 - время: 23:02)Но! Основная заповедь разработчика: "Keep It Simple, Stupid".
Вы просто неправильно понимаете эту фразу. :)
GrAnd
Профессионал
5/31/2006, 1:42:32 PM
(Nag_X @ 30.05.2006 - время: 23:45) И тут я понял...как мало я знаю...
Да ладно, какие проблемы ...
Лет так 20-25 назад, когда я еще понятия не имел об анализе производительности алгоритмов, я искренне считал пузырьковую сортировку эффективным алгоритмом.
Если тебя заинтересуют эффективные алгоритмы и методы их исследований, то попытайся найти книгу
"Н.Вирт (Да-да, тот самый дедушка Вирт). Алгоритмы и структуры данных. М.: Мир, 1989 г."
Или хотя бы
"Н.Вирт. Алгоритмы + структуры данных = программы. М.: Мир, 1985 г."
Там все на пальцАх расписывается - различные маленькие хитрости, способные значительно улучшить производительность программ. А так же азы расчета производительности. Только примеры приведены на языках Modula-2 и Pascal (что почти одно и то же).
Для более глубокого изучения
"Д.Кнут. Искусство программирования. 1-3 т.т. М.: Вильямс, 2000 г."
Но это уже для профи. БГ говорил, что того, кто осилит этот трехтомник, он сразу берет к себе на работу.
(GregZ)Но! Основная заповедь разработчика: "Keep It Simple, Stupid".
Впервые про KISS-принцип я прочитал в книге
"Ван Тассел. Стиль, разработка, эффективность, отладка и испытание программ. Д.: Мир, 1985 г."
Но там же был приведен и другой принцип:
"Оптимизацию любой программы можно проводить бесконечно" :) ...
IMHO, "просто" - это то, что работает как часы, песочные ... Кондово ...
Иногда встречаются простейшие расчеты (особенно с применением рекурсивных вычислений), которые на самых крутых компах могут выполняться очень заметное время (до нескольких минут). Покумекаешь немного, помиркуешь, справочники полистаешь, если сам не сможешь, придумаешь или найдешь алгоритм с меньшей временной сложностью - и вот уже прога порхает как бабочка. Ну, может быть бабочка и жестяная, но уже не кирпич ...
(JeyLo)А есть трехлетней давности полиномиальный алгоритм факторизации со стоимостью (уж простите, я по старинке) O(ln^(6+e)n). Ну куда нам тут с титанами бороться.
Извини, не понял в обозначениях. Это что за крышечка? Показатель степени? Т.е. (ln(n))^(6+e). Или наоборот - основание логарифма?
Да ладно, какие проблемы ...
Лет так 20-25 назад, когда я еще понятия не имел об анализе производительности алгоритмов, я искренне считал пузырьковую сортировку эффективным алгоритмом.
Если тебя заинтересуют эффективные алгоритмы и методы их исследований, то попытайся найти книгу
"Н.Вирт (Да-да, тот самый дедушка Вирт). Алгоритмы и структуры данных. М.: Мир, 1989 г."
Или хотя бы
"Н.Вирт. Алгоритмы + структуры данных = программы. М.: Мир, 1985 г."
Там все на пальцАх расписывается - различные маленькие хитрости, способные значительно улучшить производительность программ. А так же азы расчета производительности. Только примеры приведены на языках Modula-2 и Pascal (что почти одно и то же).
Для более глубокого изучения
"Д.Кнут. Искусство программирования. 1-3 т.т. М.: Вильямс, 2000 г."
Но это уже для профи. БГ говорил, что того, кто осилит этот трехтомник, он сразу берет к себе на работу.
(GregZ)Но! Основная заповедь разработчика: "Keep It Simple, Stupid".
Впервые про KISS-принцип я прочитал в книге
"Ван Тассел. Стиль, разработка, эффективность, отладка и испытание программ. Д.: Мир, 1985 г."
Но там же был приведен и другой принцип:
"Оптимизацию любой программы можно проводить бесконечно" :) ...
IMHO, "просто" - это то, что работает как часы, песочные ... Кондово ...
Иногда встречаются простейшие расчеты (особенно с применением рекурсивных вычислений), которые на самых крутых компах могут выполняться очень заметное время (до нескольких минут). Покумекаешь немного, помиркуешь, справочники полистаешь, если сам не сможешь, придумаешь или найдешь алгоритм с меньшей временной сложностью - и вот уже прога порхает как бабочка. Ну, может быть бабочка и жестяная, но уже не кирпич ...
(JeyLo)А есть трехлетней давности полиномиальный алгоритм факторизации со стоимостью (уж простите, я по старинке) O(ln^(6+e)n). Ну куда нам тут с титанами бороться.
Извини, не понял в обозначениях. Это что за крышечка? Показатель степени? Т.е. (ln(n))^(6+e). Или наоборот - основание логарифма?
tetro
Специалист
5/31/2006, 2:09:52 PM
Да показатель степени ...
поскольку я далек от этой области (но могу поинтерсоваться ), то не в курсе последних достижений... Судя по форме, это, как мне кажется, метод остнованный на известном рандомальном-теоретико-груповом тесте на простые числа (он восходит то ли к Карпу, то ли к Рабину, то ли к обоим вместе), который по умному раскрутили на факторизацию...
Это к стати примерно идея (на детальную имплементацию с места в карьер не уверен что рискну), которая крутилась у меня в голове по дороге домой.
Сложность решета где-то О(sqrt(x)*ln(x)), а возраст примерно как сумма возрастов народу в этой ветке с весьма толстым фактором...
По поводу книг, то на сегодня лучшим считается в этой области (как одна книга):
Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (с первого издания есть русский перевод).
Не все в ней совремменно, выбор тем для примеров иногда странен, например черно-красные деревья вместо АВЛей и нет рандомальных скип-листов (из того что я помню), но еще раз если одна книга, то скорее она.
поскольку я далек от этой области (но могу поинтерсоваться ), то не в курсе последних достижений... Судя по форме, это, как мне кажется, метод остнованный на известном рандомальном-теоретико-груповом тесте на простые числа (он восходит то ли к Карпу, то ли к Рабину, то ли к обоим вместе), который по умному раскрутили на факторизацию...
Это к стати примерно идея (на детальную имплементацию с места в карьер не уверен что рискну), которая крутилась у меня в голове по дороге домой.
Сложность решета где-то О(sqrt(x)*ln(x)), а возраст примерно как сумма возрастов народу в этой ветке с весьма толстым фактором...
По поводу книг, то на сегодня лучшим считается в этой области (как одна книга):
Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (с первого издания есть русский перевод).
Не все в ней совремменно, выбор тем для примеров иногда странен, например черно-красные деревья вместо АВЛей и нет рандомальных скип-листов (из того что я помню), но еще раз если одна книга, то скорее она.