Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Опредилить числа

Автор: Saninho 4.2.2013, 00:52

Всем привет   Уважаемые пользователи помогите решить задачу (С + + или Visual C + +) если не трудно. Вот у меня произошла проблема в написать программы:
Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением самого себя. Данное натуральное число N. Используя тылькы елементарны арифметичны операцыъ (+, -, *, /) определить все совершенные числа меньше N.
  Буду очень благодарен.
  Кто может то посоветуйте учебник чтобы я самостоятельно научился писать программы такого типа.   Спасибо за внимание.

Автор: math64 11.2.2013, 10:19

Создать массив int[N+1]; (можно размерности N или N-1 если индексироваться от 1 или 2)
Решетом Эратосфена определить простые числа, а для составных - наименьший делитель.
А дальше перебирай числа, находи делители и проверяй на совершенность.

Автор: feodorv 11.2.2013, 19:25

Цитата(math64 @ 11.2.2013, 11:19

)

Решетом Эратосфена

Так довольно сложно. Потом придётся перебирать комбинации простых делителей... Из двух делителей, потом из трёх и т.д. Потом тут будет нужен массив, а есть сомнение, что они разрешены:

Цитата(Saninho @ 4.2.2013, 01:52

)

Используя тылькы елементарны арифметичны операцыъ (+, -, *, /)

Понятно, что тут чем проще, тем не оптимальнее. И самое простое, но совершенно не оптимальное решение smile

задачи, является ли число n совершенным, заключается в переборе всех чисел, меньших n. Если n делится на такое число без остатка, то его можно добавить в сумму делителей. А после перебора проверить, совпадает ли сумма с самим числом n. Если да, то n - число совершенное. Ну и поверх всего этого сделать цикл по числам n от 1 до N.

Автор: sQu1rr 11.2.2013, 19:43

Цитата(feodorv @ 11.2.2013, 19:25

)

заключается в переборе всех чисел, меньших n

всех чисел меньших или равным sqrt(n)

Автор: feodorv 11.2.2013, 21:52

Цитата(sQu1rr @ 11.2.2013, 20:43

)

всех чисел меньших или равным sqrt(n)

Нет, но можно <= n/2 для чётных чисел и <= n/3 для нечётных. Речь ведь идёт о любых делителях, не только простых.

Автор: Qu1nt 11.2.2013, 22:19

feodorv,
http://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D0%B1%D0%BE%D1%80_%D0%B4%D0%B5%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%B9#cite_note-1.

Автор: feodorv 12.2.2013, 03:16

Qu1nt,
http://ru.wikipedia.org/wiki/%D1%EE%E2%E5%F0%F8%E5%ED%ED%EE%E5_%F7%E8%F1%EB%EE smile

Добавлено через 3 минуты и 7 секунд
Я понимаю, о чём идёт речь, но

Цитата(Saninho @ 4.2.2013, 01:52

)

Используя тылькы елементарны арифметичны операцыъ (+, -, *, /)

Автор: math64 12.2.2013, 13:44

Можно проверять до квадратного корня, для этого извлечение квадратного корня не нужно:

Код


bool isPerfect(int N) {
 int S = 1; // 1 всегда делитель
 for(int d = 2; d * d <= N; ++d) {
   int q = N / d;
   int r = N % d; 
   // r = N - q * d; // если % запрещен
   if (r == 0) {
     S += d;
     if (q > N)
       S += q;
   }
   if (S > N)
     return false;
 }
 return N == S;
}

Автор: feodorv 12.2.2013, 15:29

Цитата(math64 @ 12.2.2013, 14:44

)

Можно проверять до квадратного корня, для этого извлечение квадратного корня не нужно:

Можно)))) Но тогда нужно быть осторожнее:

Цитата(math64 @ 12.2.2013, 14:44

)

for(int d = 2; d * d <= N; ++d) {

Здесь d*d опасная конструкция с точки зрения переполнения, хотя, конечно, по заданию вряд ли N дадут достаточно большим....

Цитата(math64 @ 12.2.2013, 14:44

)

if (q > N)
S += q;

Наверное, имелось в виду

Код


if( q != d ) S += q;

math64, хороший вариант оптимизации, однако до всякой оптимизации:

Цитата(Saninho @ 4.2.2013, 01:52

)

посоветуйте учебник чтобы я самостоятельно научился писать программы такого типа

...

Автор: math64 13.2.2013, 07:43

d * d >= N можно заменить на q >= d; переполнение d * d возможно когда N > 0x80000000 (при 32 битном int; при другой разрядности другое число нулей)
в связи с этим далее условие q > d эквивалентно q != d

Автор: feodorv 13.2.2013, 08:46

Цитата(math64 @ 13.2.2013, 08:43

)

в связи с этим далее условие q > d эквивалентно q != d

Я не спорю. Просто написано

Цитата(math64 @ 12.2.2013, 14:44

)

if (q > N)

вместо q > d...

Цитата(math64 @ 13.2.2013, 08:43

)

переполнение d * d возможно когда N > 0x80000000

Поскольку d и N - просто int, переполнение возникает уже при N = 0x7ffea811 (46340 * 46340 < 0x80000000u; 46341 * 46341 > 0x80000000u), хотя

Цитата(feodorv @ 12.2.2013, 16:29

)

по заданию вряд ли N дадут достаточно большим

Я имел в виду, что, на мой взгляд, лучше написать в таком стиле:

Код

for(int d = 2; d <= N/d; ++d)