我需要一些幫助來將迭代演算法轉換為遞回演算法。
我需要生成總和為 11 的所有 4 個數字，其中第一個數字始終為 1，其他 3 個數字至少為 2。
for(int i = 1 ; i < 7; i ){
for(int j = 2; j < 7; j ){
for(int k = 2; k < 7; k ){
for(int p = 2; p < 7; p ){
if(i j k p == 11 && i == 1){
printf(" %d %d %d %d \n", i, k, j, p);
}
}
}
}
}
一些輸出示例：
1 2 2 6
1 3 2 5
1 4 2 4
1 5 2 3
這會起作用，但它的設計很糟糕，我需要用遞回來做。
uj5u.com熱心網友回復：
第一個數字總是 1，你不需要回圈。對于其余部分，您可以創建一個函式，將所有可能性求和為特定數字。這是一個 Java 語法的程式，但不使用類，因此很容易翻譯成 C：
public void printPossibilities(int rest, int[] buffer, int len, int total) {
if (len 1 == total) {
buffer[len] = rest;
System.out.println(Arrays.toString(buffer));
} else {
// check if it is possible that the rest of the numbers are >= 2
for (int i = 2; rest >= i (total - len - 1) * 2; i ) {
buffer[len] = i;
printPossibilities(rest - i, buffer, len 1, total);
}
}
}
// call with
int[] buffer = new int[4];
buffer[0] = 1;
printPossibilities(10, buffer, 1, 4);
uj5u.com熱心網友回復：
首先，這里有點數學：假設有 4 個數字，num1，num2，num3 和 num4，它們需要相加為 11。所以，
num1 num2 num3 num4=11
num1=1 and num2>=2, num3>=2, num4>=2
num2 num3 num4=11-num1=10
(num2-2) (num3-2) (num4-2)=10-(2 2 2)=4
var2 var3 var4=4, where var2, var3 and var4>=0
歸結為以遞回方式找到3個非負數，使它們總和為4。這是一個通用的解決方案，然后可以進行相應的修改：這是一個可以做到這一點的代碼，在 C 中：
#include <iostream>
#include <vector>
void get_target_sum(std::vector<std::vector<int>>& total_ans, std::vector<int>& curr_ans, int num_remaining, int targetnum){
// total_ans denotes all the tuples, curr_ans denotes the current
// computation, num_remaining denotes the numbers remaining which
// should sum up to targetnum.
// each time we find a valid number which can be a part of our answer, we
// add it to curr_ans, decrement num_remaining since the numbers remaining
// has decreased by 1, and decrease the target number to be found by the
// value of the number
if(num_remaining<1){return;}
if(num_remaining==1){
curr_ans.push_back(targetnum);
total_ans.push_back(curr_ans);
curr_ans.pop_back();
}
for(int curr_num=0;curr_num<targetnum;curr_num ){
curr_ans.push_back(curr_num);
get_target_sum(total_ans,curr_ans,num_remaining-1,targetnum-curr_num);
curr_ans.pop_back();
}
}
int main()
{
std::vector<std::vector<int>>final_ans;
std::vector<int> curr_ans;
get_target_sum(final_ans,curr_ans,3,4);
for(int i=0;i<final_ans.size();i ){
std::cout<<1<<" ";
// The first variable
for(auto num:final_ans[i]){
std::cout<<num 2<<" ";
// the other 3 variables, incremented by 2.
}
std::cout<<"\n";
}
return 0;
}
輸出：https ://onlinegdb.com/gdQdLgni8
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/417560.html
標籤：