求和数字递归C++

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

我的第一个问题是：现在我知道我有多少个数字，我知道我的数组的大小。我怎样才能以事先不知道数字的方式对其进行编程，例如在计算数字时，仍然有新数字加起来，占用的空间最少？

我的第二个问题是：如何改进仍然以递归方式工作的程序，并且其时间和空间利用率是最佳的？

这是我的代码：

// 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();
}

我希望

你不要再编写依赖于全局变量的函数，因为它们可以很容易地只使用提供的输入来工作。

这是一个适合我的版本。

#include <iostream>
int sumarray(int array[], int i)
{
   if ( i <= 0 )
   {
      return 0;
   }
   return sumarray(array, i-1) + array[i-1];
}
int main()
{
   int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   std::cout << "sum is : " << sumarray(array, 0) << std::endl;
   std::cout << "sum is : " << sumarray(array, 5) << std::endl;
   std::cout << "sum is : " << sumarray(array, 10) << std::endl;
}

输出：

总和为 ： 0总和为 ： 15总和为 ： 55

如果i >= 9，你的函数会执行return sum;。
（这很好，很好）

如果i < 9 ???，函数将返回何处

if (i < 9){
    sum += array[i];
    i++;
    sumarray(i);  // I see no return statement here!!
}

基本上，如果你调用sumarray(3)，则没有返回语句被命中。

在您的程序中，有一个名为 i 的全局变量。该函数还有一个本地参数，也称为 i 。

局部变量隐藏全局变量，因此全局i没有明确的目的。

我会这样做：

int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Pass in the current index, and the size of the array
int sumarray(int i, int sz)
{
    if (sz == 0)
    {
        return 0;
    }
    return array[i] + sumarray(i+1, sz-1);
}
int main(){
    std::cout << "sum is ::: " << sumarray(0, 10);
    // Start at the beginning (index 0)
    // Run for 10 elements.
    getchar();
}

第一个递归调用将是 sumarray(1,9); 然后是 sumarray(2,8); ...当最终调用sumarray(10,0)时，它将return 0.

对数组元素求和的函数通常会接受数组作为参数。在这种情况下，作为一个实际问题，它还必须接受数组的大小。像这样：

int sumarray(int a[], size_t size) {

像这样的签名还可以让你访问更好的递归方法。特别是，您可以递归计算数组前半部分和后半部分的总和，并返回它们的总和：

        size_t midpoint = size / 2;
        return sumarray(a, midpoint) + summaray(a + midpoint, size - midpoint);

这不是一个完整的解决方案：您需要一个终止条件（当size小于 2 时）。把它放进去并完成这个功能留给你一个练习，因为如果你必须自己做一些工作，你会学得更好。

这种方法限制了递归深度，从而限制了堆栈大小（内存开销）与数组大小的对数成正比，尽管它仍然涉及函数调用的总数和与数组大小成比例的整数添加。我不认为你可以用递归算法实现更好的渐近空间或时间复杂度。（但是，此任务的非递归算法只需要固定数量的函数调用和固定数量的内存开销。

这是我写的Qt中的工作C++代码 - 祝你好运我添加了一些调试点输出以使其理解更清晰

#include <QCoreApplication>
#include <QDebug>
int sum=0;
int sumrec(int *array,int n)
{
    if (n>=0)
    {
       int element=*(array+n); // note *(array+n) -> moving the pointer
                               //      *array+n   -> this is adding n to the pointer data (wrong)
                               // what is array ?
       qDebug() << " element value " << *(array+n) << " at n=" << n << " array address = " << array;
       n--;
       sum=sum+element;
       qDebug() << "sum = " << sum;
       sumrec(array,n);
       return sum;
   }
   else
   {
       return 0;
   }
}

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    int A[10]={12,13,14,15,16,17,18,19,20,11};
    int b=sumrec(&A[0],9);
    qDebug() << "answer = " << b;
    //return a.exec();
}

这是终端的输出

element value  11  at n= 9  array address =  0x7fff5fbffb78 
sum =  11 
 element value  20  at n= 8  array address =  0x7fff5fbffb78 
sum =  31 
 element value  19  at n= 7  array address =  0x7fff5fbffb78 
sum =  50 
 element value  18  at n= 6  array address =  0x7fff5fbffb78 
sum =  68 
 element value  17  at n= 5  array address =  0x7fff5fbffb78 
sum =  85 
 element value  16  at n= 4  array address =  0x7fff5fbffb78 
sum =  101 
 element value  15  at n= 3  array address =  0x7fff5fbffb78 
sum =  116 
 element value  14  at n= 2  array address =  0x7fff5fbffb78 
sum =  130 
 element value  13  at n= 1  array address =  0x7fff5fbffb78 
sum =  143 
 element value  12  at n= 0  array address =  0x7fff5fbffb78 
sum =  155 
answer =  155

在C++中，您拥有所有工具，以非常简单，可读和安全的方式执行此操作。查看valarray容器：

#include <iostream>
#include <valarray>
int main () {
  std::valarray<int> array{1,2,3,4,5,6,7,8,9,10};
  std::cout << array.sum() << 'n';
  return 0;
}

相关内容

最新更新

热门标签：