在递归中使用一维数组

最近我一直在处理分区问题。我已经完成了一项研究，并且发现它可以在Wiki页面上使用算法解决。下面是一个伪算法：在递归中使用一维数组

INPUT: A list of integers S 
    OUTPUT: True if S can be partitioned into two subsets that have equal sum 
1 function find_partition(S): 
2  N ← sum(S) 
3  P ← empty boolean table of size (\lfloor N/2 \rfloor + 1) by (n + 1) 
4  initialize top row (P(0,x)) of P to True 
5  initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False 
6  for i from 1 to \lfloor N/2 \rfloor 
7   for j from 1 to n 
8   P(i, j) ← P(i, j-1) or P(i-S[j-1], j-1) 
9  return P(\lfloor N/2 \rfloor , n)

使用递归，就可以计算出它是否能达到它返回true，如果在整数数组一定金额即可到达。我从sumOfTheIntegers/2开始，然后回到0，直到找到解决方案。当我发现整数的最大可能总和低于或等于平均值时，我计算出(average-lowestSumLowerorEqualtoAverage)*2这两组整数之间的差值。

但是，然后我面对的问题如何包括一维数组在递归？

下面是代码，它应该可能工作，但我还没有测试过，因为这个问题。所以也许代码包含小错误。但这不是问题，我稍后会解决它。

#include <iostream> 
#include <cmath> 
using namespace std; 
bool matrix (int a, int b) 
{ 
    if(b == -1) return true; 
    else if (a == -1) return false; 
    else if(matrix(a-1, b) == true) return true; 
    else if(matrix(a-1,b-numbers[a-1]) == true) return true; 
    else return false; 
} 
int main() 
{ 
    int number, sum = 0; 
    cin >> number; 
    int numbers[number]; 
    for(int i = 0; i<number; i++) 
    { 
     cin >> numbers[i]; 
     sum += numbers[i]; 
    } 
    double average = sum/2.0; 
    for(int i = floor(sum/2); i!= 0; i--) 
    { 
     if(matrix(number+1, i) == true) 
     { 
      cout << abs(average-i)*2; 
      break; 
     } 
    } 
    return 0; 
}

来源

2013-03-08 Stefan4024

这似乎是复杂的方式。难道你不能用O（2N）解法来解决这个问题：将所有数字相加，除以2以确定它是否均匀（如果不是，则无法用整数等分），然后从一个数中减去一个数字直到两个子数组相等，或者你发现它们不能成为循环的结尾？ – Tawnos 2013-03-08 22:48:16

最简单的（但肯定不是最好的）方法是引入一个全局变量：

#include <vector> 
std::vector<int> numbers; 

/* ... */ 

int main(){ 
    int number; 
    cin >> number; 
    numbers.resize(number); 
    /* ... */ 
}

另一种可能性是使用附加参数：

bool matrix (int a, int b, const std::vector<int>& numbers) 
{ 
    if(b == -1) return true; 
    else if (a == -1) return false; 
    else if(matrix(a-1, b,numbers) == true) return true; 
    else if(matrix(a-1,b-numbers[a-1],numbers) == true) return true; 
    else return false; 
}

请注意，int numbers[number]实际上使用的是编译器特定的扩展（VLA），不是C++标准的一部分（请参阅Does C++ support Variable Length Arrays?和Why aren't variable-length arrays part of the C++ standard?）。

来源

2013-03-08 22:49:57 Zeta

把它作为参数传递给函数

bool matrix (int a, int b, int num_arr[]) 
{ 
    ... 
    matrix(a-1,b,num_arr); 
    ... 
}

来源

2013-03-08 22:47:49 AxelOmega

在递归中使用一维数组

回答

相关问题