NON Repeatitive ::: -- Print all increasing sequences of length k from first n natural numbers (Recursive)
http://www.geeksforgeeks.org/print-increasing-sequences-length-k-first-n-natural-numbers/
Geeksforgeeks.
Input: k = 2, n = 3 Output: 1 2 1 3 2 3 Input: k = 5, n = 5 Output: 1 2 3 4 5 Input: k = 3, n = 5 Output: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
This is a Branch and Bound type of Problem. In which you have to decide whether to "take a
number" or "not to take" a number. After that make a recursive call again.
#include<bits/stdc++.h> using namespace std; int fi(int dest,int steps,int cu) { if(cu==dest) return steps; if(abs(cu)>dest) return INT_MAX; return min(fi(dest,steps+1,steps+cu+1),fi(dest,steps+1,cu-steps-1)); } int main() { int dest,i,j; cin>>dest; cout<<fi(dest,0,0)<<endl; return 0; }
Comments
Post a Comment