Wednesday 2 September 2015

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;
}











No comments:

Post a Comment

Uploading and Running Lambda function in AWS

Main.go package main import ( "fmt" "encoding/json" "log" "github.com/aws/aws-lambda-g...