0

Имеется код программы, который находит сумму делителей числа. Правда он не мой и написан лично для меня не понятно. Пыталась расписать код (закомментирован), но ничего не вышло. Вычисляет только для нечетных чисел и то не всегда правильно. Подскажите где я ошиблась.

#include <iostream>

using namespace std;

//int sd(int n, int d=1)
//{     
//  if (d <= n)
//  {
//      if(n % d == 0)
//          return d + sd(n, d + 1);
//      else
//          return sd(n, d + 1);
//  }
//}

int sd(int n, int d=1)
{
    return d <= n ? (n % d == 0? d + sd(n, d + 1) : sd(n, d + 1)) : 0;
}

int main() 
{ 
    setlocale(LC_ALL, "rus");
    int n; 
    cout<<"Дано натуральное число найти сумму его делителей через рекурсию \n"<<endl;
    cout << "Введите натуральлное число, n = "; cin >> n;
    cout <<"Сумма делителей натурального числа = "<<sd(n)<<endl; 
    system ("pause");
    return 0; 
}
0

2 ответа 2

3
int sd(int n, int d=1)
{
    return d <= n ? (n % d == 0? d + sd(n, d + 1) : sd(n, d + 1)) : 0;
}

==>

int sd(int n, int d=1)
{
    if(d <= n)  //Если делитель меньше нужного числа, то идем дальше
    {
        if( n % d == 0) //если число n делится на d без остатка
        {
            return d + sd(n, d+1); //возвращаем сумму этого делителя + все суммы остальных делителей, которые делятся без остатка.
        }
        else 
        {
           return sd(n, d+1); //возвращаем суммы остальных делителей, которые делятся без остатка
        }
    } 
    else 
    {
        return 0; //на этой итерации нет делителей для числа
    }
}
3
  • ps. интересно, если топик стартеры не будут прикидываться девушками, то им совсем никто не ответит?
    – Deadkenny
    23 июн 2014 в 9:48
  • @Deadkenny: Угу. Хоть бы фото прикладывали в профиль.
    – VladD
    23 июн 2014 в 9:54
  • Спасибо большое. Теперь вижу свою ошибку 23 июн 2014 в 9:56
2

О, а хороший код. Написан человеком, который слыхал о рекурсии (правда, не о хвостовой).

Смотрите. Функция sd у вас в двух экземплярах. Они равнозначны, просто первый вариант попроще расписан. Давайте его и рассмотрим.

Итак, как у нас определяется сумма делителей? Определим функцию sd(n, d): сумма делителей числа n, которые больше или равны d. Почему так? Потому что эту функцию легко определить рекурсивно, и она даёт нам искомый результат, если положить d = 1.

Рекуррентное соотношение такое:

  1. Если n делится на d, то d — один из делителей, и sd(n, d) есть d плюс остальные делители (то есть, для больших d). Итак, для этого случая sd(n, d) = d + sd(n, d + 1).
  2. Если не делится, то очевидно sd(n, d) = sd(n, d + 1)
  3. Если d > n, sd(n, d) = 0, и дальше можно не считать.

Соответственно этому код:

int sd(int n, int d=1)
{     
    if (d <= n) // случай 3?
    {
        // нет. тогда может случай 1?
        if(n % d == 0)
            return d + sd(n, d + 1); // да!
        else
            return sd(n, d + 1); // нет, случай 2.
    }
    // тут потеряно else return 0; для полного разбора случая 3
    // в незакомментированной функции этот случай есть
}

С вас что-то вкусное для того, кто написал код.


Да, и код правильный.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.