Поиск идеального числа с помощью функций переполнения стека
У меня проблемы с приближением к конкретной проблеме в моей программе.
Во-первых, мне нужно было определить, является ли число идеальным. Используя функцию с именем: bool isPerfect (int n), которую я сделал здесь:
bool isPerfect(int n) {
sum = 0;
for (int i = 1; i < n; i++) {
if (n % i == 0)
sum += i;
}
if (sum == n) {
return true;
}
else {
return false;
}
}
Проблема, с которой я сталкиваюсь, — это второй шаг. Это мне нужно создать код, который генерирует много целых чисел для тестирования. Затем проверяйте эти целые числа, пока я не найду и не напечатаю пять из них, которые идеально подходят. Код спагетти, который я написал, занял слишком много времени, чтобы вычислить 5-е идеальное число. Какие шаги я могу предпринять, чтобы сократить количество времени, необходимое для тестирования такого большого числа? Как правило, которое я мог бы ввести, чтобы пропустить числа, чтобы проверить, что я знаю, что мне не нужно? Любая помощь очень ценится.
Решение
Евклид доказал, что 2р-1(2п — 1) это даже идеальное число всякий раз, когда 2p − 1 прост. Увидеть: Википедия — Даже идеальные числа Это обеспечивает основу для генерации всех кандидатов на совершенные числа в почти тривиально небольшом наборе вычислений. Здесь цель — найти первые пять совершенных чисел. К счастью, первые пять легко поместятся в 4-байтовом unsigned Тип данных и может быть вычислен за меньшее время, чем требуется для ввода [Ctrl + C].
Чтобы подойти к проблеме, вы сначала вычисляете кандидата на идеальное число по формуле выше. Вы можете использовать pow функция предоставлена math.h даже если он был разработан для использования с плавающей запятой, или вы можете просто создать свой собственный, который перебирает значение для кандидата p количество времени, необходимое для умножения p сам по себе для массива в конечном результате, например, что-то вроде следующего:
unsigned upow (unsigned v, unsigned n) /* unsigned pow() */
{
unsigned tmp = 1;
if (n == 0)
return 1;
while (n--)
tmp *= v;
return tmp;
}
(нота: Для защиты от переполнения без знака следует добавить проверки переполнения, которые могут возникать при использовании unsigned 4-байтовый тип для идеальных чисел за пределами 5го)
Остальная часть алгоритма довольно проста, вы просто зацикливаете числа в кандидате от 1 к candidate / 2 (включительно), чтобы гарантировать, что все факторы найдены, суммированы и сохранены в массиве, содержащем отдельные делители для последующего отображения.
Краткий пример подхода дает:
unsigned sum = 0, i, j, p, pn, pncount = 0; /* variable declarations */
for (p = 2; p < 32; p++) { /* generate candidate from */
unsigned divisors[NELEM] = {0}, n = 0; /* divisors array and ndx */
pn = upow (2, p - 1) * (upow (2, p) - 1); /* 2^(n - 1) * (2^n - 1) */
for (i = 1; i <= pn / 2; i++) { /* find divisors & sum */
if (pn % i == 0) {
sum += i;
divisors[n++] = i; /* store divisor to array */
}
if (n == NELEM) { /* protect array bound */
fprintf (stderr, "error: f full.\n");
return 1;
}
}
if (sum == pn) { /* test whether candidate is Perfect Number */
printf ("Perfect number: %10u :", pn);
for (j = 0; j < n; j++) /* output divisors */
printf (j ? ", %u" : " %u", divisors[j]);
putchar ('\n');
if (++pncount == MAXPN) /* check against limit */
break;
}
sum = 0; /* reset sum for next iterations */
}
Осталось только добавить stdio.h заголовок, объявляя пару констант для нашего максимального числа идеальных чисел для генерации и для нашего массива делителей. В целом, вы можете сделать что-то похожее на следующее:
#include <stdio.h>
#define MAXPN 5 /* const - max perfect numbers to find */
#define NELEM 4096 /* const - elements in divisors array */
unsigned upow (unsigned v, unsigned n) /* unsigned pow() */
{
unsigned tmp = 1;
if (n == 0)
return 1;
while (n--)
tmp *= v;
return tmp;
}
int main (void) {
unsigned sum = 0, i, j, p, pn, pncount = 0; /* variable declarations */
for (p = 2; p < 32; p++) { /* generate candidate from */
unsigned divisors[NELEM] = {0}, n = 0; /* divisors array and ndx */
pn = upow (2, p - 1) * (upow (2, p) - 1); /* 2^(n - 1) * (2^n - 1) */
for (i = 1; i <= pn / 2; i++) { /* find divisors & sum */
if (pn % i == 0) {
sum += i;
divisors[n++] = i; /* store divisor to array */
}
if (n == NELEM) { /* protect array bound */
fprintf (stderr, "error: f full.\n");
return 1;
}
}
if (sum == pn) { /* test whether candidate is Perfect Number */
printf ("Perfect number: %10u :", pn);
for (j = 0; j < n; j++) /* output divisors */
printf (j ? ", %u" : " %u", divisors[j]);
putchar ('\n');
if (++pncount == MAXPN) /* check against limit */
break;
}
sum = 0; /* reset sum for next iterations */
}
}
Производительность является ключевым. Как вы выяснили, поскольку метод грубой силы потребует триллионов вычислений, повторяющихся при любой возможной комбинации и возможном совершенном числе, что даже на быстрой машине у вас, скорее всего, будет время для короткого отпуска, прежде чем это будет сделано с помощью 5.го дело.
Проверка выходных данных показывает, что алгоритм устойчив для первых пяти совершенных чисел, например,
* Пример использования / Вывод **
$ ./bin/perfnumber
Perfect number: 6 : 1, 2, 3
Perfect number: 28 : 1, 2, 4, 7, 14
Perfect number: 496 : 1, 2, 4, 8, 16, 31, 62, 124, 248
Perfect number: 8128 : 1, 2, 4, 8, 16, 32, 64, 127, 254, 508,
1016, 2032, 4064
Perfect number: 33550336 : 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,
1024, 2048, 4096, 8191, 16382, 32764, 65528,
131056, 262112, 524224, 1048448, 2096896,
4193792, 8387584, 16775168
(нота: выход независимых делителей, которые составляют sum были аккуратно обернуты, чтобы избежать прокрутки для SO, как правило, они просто приведены в последовательности за идеальным числом).
Что касается времени кода, просто простой вызов time было все, что использовалось для сравнительного сравнения требуемого времени вычислений, например,
Приблизительное время выполнения
$ time ./bin/perfnumber
<snip output>
real 0m0.146s
user 0m0.139s
sys 0m0.008s
Все первые пять совершенных чисел вычисляются менее чем за две десятых секунды, занимая всего 8 тысячных секунды.
Алгоритм имеет все значение в мире.
Другие решения
Других решений пока нет …