Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Neys
-1 / 0 / 0
Регистрация: 27.10.2009
Сообщений: 14
#1

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

11.04.2012, 16:12. Просмотров 1198. Ответов 4
Метки нет (Все метки)

Добрый вечер. Столкнулся с проблемой написания рекурсивной функции для определения, совершенное число или нет.
Попробовал сделать так, для первых четырех чисел проверенно работает, но принцип работы -"не есть хорошо".
Для того же числа 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. Тупанул с названием темы. Естественно, совершенные числа, а не случайные.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.04.2012, 16:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия, совершенные числа (C++):

Для заданного натурального числа N вывести в столбик все совершенные числа меньшие N c++ - C++
Для заданного натурального числа N вывести в столбик все совершенные числа меньшие N. Совершенное число – натуральное число, которое равно...

Совершенные числа - C++
В интервале от a до b напечатать совершенные числа. Совершенное число, равно сумме всех своих делителей, например 28=1+2+4+7+14

совершенные числа - C++
Здрасте,помогите организовать программу на Си,которая определяет является ли введённое с клавиатуры число совершенным. и надо расписать...

Совершенные числа - C++
Вводится число n, требуется вывести совершенные числа до n. #include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; void...

Совершенные числа - C++
Здравствуйте. Пытаюсь решить следующую задачку: реализовать метод, который получает число n и возвращает все совершенные числа в диапазоне...

Совершенные числа - C++
Натуральное число называется совершенным, если оно равно сумме всех своих делителей, кроме себя самого. Число 6 является совершенным, так...

4
TwiX
60 / 60 / 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;
}
0
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.

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

Не по теме:

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

0
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;
}
0
12.04.2012, 05:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2012, 05:30
Привет! Вот еще темы с ответами:

Совершенные числа - C++
Как из этого кода сделать алгоритм, который находит совершенные числа. #include &lt;iostream&gt; using namespace std; int main() { ...

Совершенные числа. - C++
подскажите как переделать под С , а не С++ буду признателен #include &lt;iostream.h&gt; #include&lt;conio.h&gt; #include &lt;vcl.h&gt; ...

Совершенные числа. - C++
По введеному натуральному числу N визначити, чи є воно досконалим. Досконале число дорівнює сумі усіх своїх дільників, включаючи одиницю і...

Совершенные числа(косяк) - C++
Добрый день! Возникла проблема с вывод совершенных чисел в интервале от m до n. Почему-то вообще не выводит, хотя проверял похожий...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru