Iterative algorithm becomes recursive algorithm
I need some help converting an iterative algorithm to a recursive one.
I need to generate all 4 numbers that sum to 11, where the first number is always 1, The other 3 numbers are at least 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);
}
}
}
}
}
Some output examples:
1 2 2 6
1 3 2 5
1 4 2 4
1 5 2 3
This will work, but it's badly designed and I need to do it with recursion.
uj5u.com enthusiastic netizens replied:
The first number is always 1, you don't need to loop around.For the rest, you can create a function that sums all possibilities to a specific number.This is a program in Java syntax, but does not use classes, so it is easy to translate to 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 enthusiastic netizens replied:
First, a bit of math here: Say there are 4 numbers, num1, num2, num3 and num4, they Need to add up to 11.So,
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
It boils down to finding 3 non-negative numbers recursively so that they sum to 4.This is a general solution, which can then be modified accordingly: here is a code that does it, in 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 decreased 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;
}
Output:https://onlinegdb.com/gdQdLgni8
0 Comments