Форум программистов, компьютерный форум CyberForum.ru

Рекурсия, совершенные числа - C++

Восстановить пароль Регистрация
 
Neys
-1 / 0 / 0
Регистрация: 27.10.2009
Сообщений: 14
11.04.2012, 16:12     Рекурсия, совершенные числа #1
Добрый вечер. Столкнулся с проблемой написания рекурсивной функции для определения, совершенное число или нет.
Попробовал сделать так, для первых четырех чисел проверенно работает, но принцип работы -"не есть хорошо".
Для того же числа 28 что выходит: ищу делители от 28/2 = 14 до 1, как только нахожу (а 14 и есть один из таковых), считаю уже от половины делителя до той же двойки. Понятно, что при нахождении делителя 7 и делении его пополам будем считать по убыванию от (int)3.5. Как находится четверка - для меня секрет. Возможно, она кроется в "невидимых" для меня и ненужных по сути шагах рекурсии. Таковых в этом коде много, насколько я понимаю.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
using namespace std;
 
bool is_perfect(int num, int lim)
{
    int sum = 0;
    for(int i = lim; i >= 1; i--)
        if(num % i == 0)
        {
            sum += i; 
            is_perfect(num, lim / 2);
        }
    return sum == num;   
}
 
void main()
{
    setlocale(0, "");
    int number;
    cout << "Введите число: ";
    cin >> number;
    if(is_perfect(number, number / 2))
        cout << "Число совершенное." << endl;
    else
        cout << "Число совершенным не является." << endl;
}
ВОПРОС: Как можно красиво решить данную задачу? Придумать бы хотя бы алгоритм.

Добавлено через 19 часов 40 минут
P.S. Тупанул с названием темы. Естественно, совершенные числа, а не случайные.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.04.2012, 16:12     Рекурсия, совершенные числа
Посмотрите здесь:

C++ совершенные числа
C++ Совершенные числа.
C++ Совершенные числа.
Совершенные числа C++
C++ Совершенные числа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TwiX
59 / 59 / 1
Регистрация: 27.10.2011
Сообщений: 189
11.04.2012, 18:44     Рекурсия, совершенные числа #2
Зачем ты вызываешь ещё раз is_perfect(num, lim / 2); внутри? Это ничего не меняет
C++
1
2
3
4
5
6
7
8
bool is_perfect(int num)
{
    int s=0;
    for(int i = 1; i <= num/2; i++)
        if(num % i == 0)
            s+=i;
    return num==s;
}
Neys
-1 / 0 / 0
Регистрация: 27.10.2009
Сообщений: 14
11.04.2012, 21:36  [ТС]     Рекурсия, совершенные числа #3
C++
1
2
3
4
5
6
7
8
9
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
43
44
45
46
47
48
49
#include <iostream>
#include <iomanip>
 
using namespace std;
 
int lim, sum = 0, count = 0;
int mas[100];
 
bool is_perfect(int num)
{
    for(int i = lim; i >= 1; i--)
    {
        bool fl = true;
        for(int j = 0; j < count; j++)
            if(mas[j] == i)
                fl = false;
 
        if((num % i == 0) && (lim >= 1) && fl)
        {
            count++;
            sum += i;
            cout << left << setw(13) << lim << setw(17) << i << sum << endl;
            mas[count] = i;
            lim = i - 1;
            
            is_perfect(num);
            break;
        }
    }
    return sum == num;   
}
 
void main()
{
    setlocale(0, "");
 
    int number;
    cout << "Введите число: ";
    cin >> number;
 
    lim = number / 2;
 
    cout << "Считаем от |" <<  " Нашли делитель |" << " Сумма делителей"  << endl;
 
    if(is_perfect(number))
        cout << endl << "Число совершенное." << endl;
    else
        cout << endl << "Число совершенным не является." << endl;
}
Добавлено через 13 минут
Не успел подправить в нормальный вид, отвлекся.
Как итог: проходим меньшее кол-во чисел в поисках делителей + желанная рекурсия.
Для чисел 6, 28, 496, 8128, 33550336 работает как надо.

Добавлено через 7 минут
Лучше не читайте этот бред. Я понял, что сделал просто дохрена лишнего и нафиг так надо.

Добавлено через 46 минут
Разобрался, что было лишнее, сделал по схеме:
глобальная переменная lim, в мэйне задаем lim = num/2, вызываем функцию
ищем по убыванию от lim до 1
нашли делитель: lim = делитель - 1; sum += делитель; цикл break;
если lim > 1 вызываем рекурсивно функцию,
иначе возвращаем sum == num.

т.е. рекурсия получилась искусственная, если убрать её одновременно с break, будет то же самое
т.к. будут в цикле искаться и другие делители, причем так же от уменьшенного lim.

есть у кого идеи получше/попроще?
instagib
11.04.2012, 21:40
  #4

Не по теме:

Neys, неформатированный код крайне неудобно читать

Neys
-1 / 0 / 0
Регистрация: 27.10.2009
Сообщений: 14
12.04.2012, 05:30  [ТС]     Рекурсия, совершенные числа #5
Понимаю, так получилось. Вот в нормальном виде. Интересно было бы услышать другие идеи.

C++
1
2
3
4
5
6
7
8
9
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
#include <iostream>
 
using namespace std;
 
int lim, sum = 0;
 
bool is_perfect(int num)
{
    for(int i = lim; i >= 1; i--)
        if(num % i == 0)
        {
            sum += i;
            lim = i - 1;
            break;
        }
 
    if(lim >= 1) is_perfect(num);
 
    return sum == num;   
}
 
void main()
{
    setlocale(0, "");
 
    int number;
    cout << "Введите число: ";
    cin >> number;
    lim = number / 2;
 
    if(is_perfect(number))
        cout << "Число совершенное." << endl;
    else
        cout << "Число совершенным не является." << endl;
}
Yandex
Объявления
12.04.2012, 05:30     Рекурсия, совершенные числа
Ответ Создать тему
Опции темы

Текущее время: 19:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru