如何正确计算所有生成的排列，包括递归?

Question

我目前正在做一个小程序，它应该能找到所有的组合。

填补用1到9的数字跟随占位符。每个数字只出现一次，构成方程的总和是100。

_/_ * _ + _ * * _/_ + _ * _ = 100

#include <bits/stdc++.h>
#include <cmath>
using namespace std;
void print(int arr[], int n){
for (int i = 0; i < n; i++){
cout << arr[i] << " ";
}
cout << endl;
}
void findCombos(int arr[], int n){
std::sort(arr, arr + n);
do{
if((arr[0] / arr[1] * arr[2] + arr[3] * arr[4] * arr[5] / arr[6] + arr[7] * arr[8]) == 100){
print(arr, n);
}
}while(next_permutation(arr, arr + n));
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int size = sizeof(arr) / sizeof(arr[0]);
findCombos(arr, size);
return 0;
} 

我用这段代码生成了900个解。有些排列是正确的，但有些组合不能精确计算到100。我的if语句正确地匹配了操作，但是为什么显示了不正确的排列?作为扩展，我如何使这个程序递归运行?

Answer 1

您正在除整数，这会截断结果。如果你把9除以2作为整数，结果是4而不是4.5。这意味着您的程序计算的值将不正确。

Answer 2

正如PiedPiper已经提到的整数除法问题，您可以简单地将arr[]声明为double，它就解决了这个问题。

作为扩展，您还可以使用递归方法计算排列。请检查函数findCombosRecursive()，它具有与findCombos()相似的功能，但进行递归组合。

递归算法将arr划分为两部分:已经排列的元素和未改变的元素。参数curr表示这两个部分之间的枢轴。每次我们在主元素和剩余不变的元素之间进行交换时都会把主元素的位置向前推进1。一旦我们到达数组的末尾，我们得到数组的一个新的排列，并检查这个排列是否满足我们的必要条件。不要忘记在递归调用后恢复位置。这将确保枢轴位置与单个排列结构中的其他剩余元素交换。

这里我分享了一个递归构造解决方案的示例实现:

#include <bits/stdc++.h>
#include <cmath>
using namespace std;
void print(double arr[], int n, int sid) {
cout << "Solution " << sid << ":";
for (int i = 0; i < n; i++){
cout << " " << arr[i];
}
cout << endl;
}
void findCombosRecursive(double arr[], int size, int curr, int& sid) {
if (curr == size) {     // base-case of the recursion
// check whether the current combination satisfy the following condition:
// "_ / _ * _ + _ * _ * _ / _ + _ * _ = 100"
if((arr[0] / arr[1] * arr[2] + arr[3] * arr[4] * arr[5] / arr[6] + arr[7] * arr[8]) == 100){
print(arr, size, sid);
sid += 1;
}
} else {
for (int i = curr; i < size; i+=1) {
swap(arr[i], arr[curr]);
findCombosRecursive(arr, size, curr + 1, sid); // placing next position
swap(arr[i], arr[curr]);  // restoring
}
}
}
void findCombos(double arr[], int n){
std::sort(arr, arr + n);
int i = 0;
do{
if((arr[0] / arr[1] * arr[2] + arr[3] * arr[4] * arr[5] / arr[6] + arr[7] * arr[8]) == 100){
print(arr, n, i);
i += 1;
}
} while(next_permutation(arr, arr + n));
}
int main(){
double arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int size = sizeof(arr) / sizeof(arr[0]);
int sid = 0;
findCombosRecursive(arr, size, 0, sid);
// findCombos(arr, size);
return 0;
}