递归地汇总数字C ++ [英] summing numbers recursively C++

问题描述

我正在尝试制作一个递归程序，它对数组或数字列表求和。使用visual studio 2013，c ++控制台应用程序。



我的第一个问题是：

现在我知道我有多少号码，我知道我的数组的大小。我如何以不提前知道数字的方式对其进行编程，例如在计算数字时仍有新数字加起来，空间使用最少？



我的第二个问题是：

我如何改进仍然可以递归工作的程序，并且它的时间和空间使用是最佳的？



这是我的代码：

I'm trying to make a recursive program that sums an array or a list of numbers. Using visual studio 2013, c++ console application.

My 1st question is that:
Now I know how many numbers i have and i know the size of my array. How can i program it the way that don't know the numbers in advance, like while it's calculating the numbers there are still new numbers adding up, with the least space usage?

My 2nd question is that:
How can I improve the program that still works recursively and its time and space usage be optimal?

Here is my code:

    // summing a list of number.cpp
#include "stdafx.h"
#include "iostream"
int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int sum = 0, i = 0;
int sumarray(int i){
    if (i < 9){
        sum += array[i];
        i++;
        sumarray(i);
    }
    else
        return sum;
}
int main(){
    std::cout << "sum is ::: " << sumarray(i);
    getchar();
}

谢谢，

thanks,

推荐答案

你可以制作使用划分和征服算法 [ ^ ]。



Eg通过计算左边half加上数组右半部分之和来计算总和。

You may make the example a bit more challenging by employing Divide and conquer algorithms[^].

E.g. calculate the sum by calculating the sum of the left "half" plus the sum of the right "half" of your array.

int sum(int a[], int size)
{
  int result = 0;
  if (size == 1)
  {
    result = a[0];
  }
  else if (size > 1)
  {
    int midpoint = size/2;
    int left = sum(a, midpoint);
    int right = sum(a+midpoint, size-midpoint);
    result = left + right;
  }
  return result;
}

为了本练习的目的，添加一些参数来跟踪算法，例如：

For the purpose of this exercise, add some more arguments to trace the algorithm, e.g.

int sum(int a[], int from, int size, const string& context, int depth)
{
  string indent(depth, '|');
  cout << indent << context << "(a, " << from << ", " << size << ")" << endl;
  int result = 0;
  if (size == 1)
  {
    result = a[from];
  }
  else if (size > 1)
  {
    int midpoint = size/2;
    int left = sum(a, from, midpoint, "left", depth+1);
    int right = sum(a, from+midpoint, size-midpoint, "right", depth+1);
    result = left + right;
    cout << indent << "=" << left << "+" << right << endl;
  }
  cout << indent << "=" << result << endl;
  return result;
}
...
int a[] = { 1,2,3,4,5,6,7,8,9, 10};
cout << "sum = " << sum(a, 0, 10, "sum", 0) << endl;

这导致

sum(a, 0, 10)
|left(a, 0, 5)
||left(a, 0, 2)
|||left(a, 0, 1)
|||=1
|||right(a, 1, 1)
|||=2
||=1+2
||=3
||right(a, 2, 3)
|||left(a, 2, 1)
|||=3
|||right(a, 3, 2)
||||left(a, 3, 1)
||||=4
||||right(a, 4, 1)
||||=5
|||=4+5
|||=9
||=3+9
||=12
|=3+12
|=15
|right(a, 5, 5)
||left(a, 5, 2)
|||left(a, 5, 1)
|||=6
|||right(a, 6, 1)
|||=7
||=6+7
||=13
||right(a, 7, 3)
|||left(a, 7, 1)
|||=8
|||right(a, 8, 2)
||||left(a, 8, 1)
||||=9
||||right(a, 9, 1)
||||=10
|||=9+10
|||=19
||=8+19
||=27
|=13+27
|=40
=15+40
=55
sum = 55

这是一个更现实的情况（不是针对数组，而是针对某些问题）。递归深度也减少了。你不必计算左半部分和右半部分。例如。如果你想利用并发计算一些值，你可以分成多个部分并征服;-)



干杯

Andi

This is a more realistic situation(not for an array, but for some kind of problems). And the recursion depth is reduced too. You are not bound to calculate the left half and the right half. E.g. if you want to take benefit of concurrent calculation of some values, you may divide into multiple parts and conquer ;-)

Cheers
Andi

要停止递归，您要么传递数组 size ，要么使用数组中的特殊值（比如'sentinel'）来表示结束 - 数组条件（你知道， C 字符串以这种方式工作）。

请注意第二个选项只有才可行你事先知道数组项是可用的 int 值的一个子集（例如，如果你的程序只能加上正整数，那么，例如，一个负值可能是'哨兵'）。



正如谢尔盖所​​正确指出的那样，忘记'空间和时间的优化'：递归在这里只是作为一个练习来证明编码器（但是，根据 Wirth ，这种'递归练习'只会导致递归本身的坏名声。）

To stop recursion you either pass the array size or use a special value in the array (say 'the sentinel') to signal end-of-the-array condition (you know, C strings work this way).
Please note the second option is viable only if you know in advance the the array items are a subset of the available int values (e.g. if your program is supposed to add up only positive integers then, for instance, a negative value could be 'the sentinel').

As correctly pointed out by Sergey, forget about 'space and time optimization': recursion is justified here only as an exercise for the coder (but, according to Wirth, such kind of 'recursion exercises' just contribute to the bad reputation of the recursion itself).

请看我的评论：在这里使用递归是一件坏事。所以，首先，忘记它的时间和空间使用是最佳的。解决问题后，您可以讨论此类设计的性能问题。



从代码中删除9和10 立即常量开始。您的代码应该适用于任何合理长度的所有数组，但您需要对其进行硬编码。这是无法接受的。在测试中（仅在测试中），引入单个长度常量并在任何地方使用它，特别是作为参数传递给你的函数（见下文）。 />


完成后，请查看 main 。在 somearray（i）中， i 未定义（顺便说一下，永远不要使用这么短的名字）。如果有人调用，你可以设计计算总和的算法，比如说， sumArray（array，arrayLength，0）（0就是你开始递归的地方;你需要这个参数用于递归）。你真的需要另一个参数来传递数组，因为你不应该假设数组是在代码之上声明的，具有这个确切的名字;和另一个传递数组长度的参数;在C或C ++中，你不知道它指针的数组长度。



我希望这足以让你独立继续。解决我解释的问题并继续。任何运行时问题都可以使用调试器，这一点很重要。

-SA

Please see my comment: using recursion here is a bad thing. So, first of all, forget "its time and space usage be optimal". After you solve the problem, you can discuss the performance problems of such design.

Start with removing 9 and 10 immediate constants from code. Your code should work with all arrays, of any reasonable length, but you are hard-coding it. This is unacceptable. In the test (only in the test), introduce the single length constant and use it everywhere, in particular, pass as a parameter to your function (see below).

When this is done, look at main. In somearray(i), i is undefined (by the way, never use so short names). Your could design the algorithm calculating the sum if one calls, say, sumArray(array, arrayLength, 0) (0 would be where you start your recursion with; you need this parameter for recursion). You really need another parameter to pass the array, because you should not assume that the array is declared on top of code, with this exact name; and another parameter to pass the array length; in C or C++, you don't know the array length from it's pointer.

I hope this is enough for you to continue independently. Fix the problems I explained and proceed. It's important to use the debugger in case of any runtime problems, any at all.

—SA

这篇关于递归地汇总数字C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！