Рекурсивная функция для добавления суммы последовательности чисел и их сумм - PullRequest
0 голосов
/ 21 августа 2009

Это был вопрос интервью:

Учитывая последовательность из n чисел (n может быть любым числом, предположим, что n <= 100 для этого вопроса), скажем, например, для. 11, 23, 9, 17, 20, 8, 5, 6. <strong>Проблема состоит в том, чтобы написать рекурсивную функцию в C , чтобы добавить каждое число в последовательности, чтобы получить сумму. Если эта сумма содержит более одной цифры, то суммируйте цифры снова и снова, если сумма составляет более одной цифры, затем суммируйте цифры снова. Следуйте этому процессу, пока сумма не уменьшится до одной цифры нет. Теперь добавьте все суммы, полученные в процессе, для вывода окончательной суммы.

Для иллюстрации возьмите приведенную выше последовательность: 11, 23, 9, 17, 20, 8, 5, 6

SUM(11, 23, 9, 17, 20, 8, 5, 6) = 99 => SUM(9, 9) = 18 => SUM(1, 8) = 9

Теперь добавьте все полученные суммы, то есть SUM(99, 18, 9) = 126 <== должно быть выводом. </p>

Обратите внимание, что эта функция должна быть рекурсивной функцией в C .

Ответы [ 7 ]

1 голос
/ 21 августа 2009

Не уверен насчет C, но алгоритм будет выглядеть примерно так:

СУММА (1, 2, ... n) = 1 + СУММА (2, ... n) и т. Д., Чтобы получить общую сумму, а затем повторите, как только будет найдено, что окончательное число больше чем одна цифра.

0 голосов
/ 11 июля 2013
#include <iostream>
using namespace std;

class RecursiveSum {
public:
    int nDigits(int a) {
        int d = 0;
        while (a > 0) {
            d++;
            a /= 10;
        }
        return d;
    }

    long sum(int *arr, int b, int e, int s) {
        if (!arr)
            return 0;
        if (b < e) {
            s += arr[b++];
            return sum(arr, b, e, s);
        } else { // b >= e
            if (s < 10)
                return s;

            int nd = nDigits(s);
            int* narr = new int[nd];
            long n = s, itr = 0;
            while (n > 0) {
                narr[itr++] = n % 10;
                n /= 10;
            }

            s += sum(narr, 0, nd, 0);
            delete[] narr;

            return s;
        }
    }

};
0 голосов
/ 17 декабря 2010

Я просто хочу добавить это к ответу 77v , чтобы сделать все хардкорное рекурсивным, насколько это возможно. Я знаю, что это уже год назад, и его решение на C ++ уже работает довольно хорошо. Но мне действительно было неинтересно, что я решил сделать последнюю функцию sumDigits в рекурсии. Итак, чтобы избавиться от скуки, вот оно:

long sumDigits(long x, long d = 0)
{
    if (x != 0)
    {
        d = x % 10;
        return d + sumDigits(x / 10, d);
    }
    else
        return 0;
}

Это то же самое, 7 строк и принимает один аргумент. Обратите внимание, что второй по умолчанию равен 0. Он используется как память для самой рекурсии. Пользователь может полностью игнорировать этот второй аргумент. Функция также используется так же, как и реализация 77v. Вы можете фактически заменить его функцию на эту. Отсюда все функции в его решении основаны на рекурсии. Что делает и без того потрясающую работу еще более крутой! Лол! : D

0 голосов
/ 22 августа 2009

Как говорили другие: суть в том, чтобы понять рекурсию.

Есть 3 места, где мы можем использовать рекурсию:

  • сумма всех цифр в интегральном числе:

    sum_digital :: (Integral a) => a -> a
    sum_digital d
       | d < 10     = d
       | otherwise  = d `mod` 10 + sum_digital (d `div` 10)
    
  • объединяет все суммы из начального значения и правил

    chain :: (Integral a) => a -> [a]
    chain a 
        | a < 10 = [a]
        | otherwise = a : chain (sum_digital a)
    
  • последний. сумма списка

    mySum :: (Integral a) => [a]-> a
    mySum [] = 0
    mySum (x:xs) = x + mySum xs 
    

Соберите все это вместе:

*Main> mySum $ chain $ mySum [11, 23, 9, 17, 20, 8, 5, 6]    
126

C-версия оставлена ​​для вас в качестве упражнения:)

0 голосов
/ 21 августа 2009

Вот реализация Scala:

def sum(lst: List[Int]): Int = {
    val sum1 = lst.reduceLeft(_+_)
    println(sum1)
    sum1 match {
       case nb if nb < 10 => sum1
       case _ => {
            val lst2 = sum1.toString.toList.map(_.toString).map(Integer.parseInt(_))
            sum1 + sum(lst2)
       }
    }

}

val lst = List(11, 23, 9, 17, 20, 8, 5, 6)
val totalSum = sum(lst)
println(totalSum)

Результат:

99
18
9
126

Я действительно начинаю любить, насколько лаконична Скала.

0 голосов
/ 21 августа 2009
#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

const int n = 8;

int sumDigits(int x)
{
    int d = 0;

    while (x != 0)
    {
        d += x % 10;
        x /= 10;
    }

    return d;
}

int sumArr(int* a, int start)
{
    return (start == n)? 0: a[start] + sumArr(a, start + 1);
}

int sum(int x)
{
    return (x < 10)? x: x + sum(sumDigits(x));
}

int main(int argc, _TCHAR* argv[])
{
    int* a = new int[n];
    a[0] = 11; a[1] = 23; a[2] = 9; a[3] = 17; a[4] = 20; a[5] = 8; a[6] = 5; a[7] = 6;
    //for (int i = 0; i < n; i++) a[i] = rand() % 100;
    //for (int i = 0; i < n; i++) printf("a[%d] = %d\n", i, a[i]);

    printf("sum = %d\n", sum(sumArr(a, 0)));

    return 0;
}

Это выводит: сумма = 126

0 голосов
/ 21 августа 2009

Вот реализация Erlang, которую вы можете использовать в качестве руководства

-module('summation').  
-export([start/1]).  

sumlist(List)->
  lists:foldl(fun(X, Sum) -> X + Sum end, 0, List). << Inherently recursive

num_to_list(Value) ->
  Str = integer_to_list(Value),
  lists:map(fun(X) -> X - 48 end, Str).  << Inherently recursive

accumulate([_H], List) ->
  io:fwrite("~w~n", [List]),
  List;
accumulate(Value, List) ->
  Tmp = sumlist(Value),
  accumulate(num_to_list(Tmp), [Tmp|List]).  % << Recurse here

start(List)->
  Value = accumulate(List, []),
  sumlist(Value).

тестирование

25> c(summation).
{ok,summation}
26> summation:start([11, 23, 9, 17, 20, 8, 5, 6]).
[9,18,99]
126
27>
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...