#include <iostream>

using namespace std;

int n;

//recursiv, varianta foarte ineficienta
int Al_N_lea_termen_Fibonacci(int n)
{
    if(n==1 || n==2)
        return 1;
    return Al_N_lea_termen_Fibonacci(n-1) + Al_N_lea_termen_Fibonacci(n-2);
}

//cu vector, complexitate O(n)
int Fib(int n)
{
    int a[n+1];
    a[1] = 1;
    a[2] = 1;
    for(int i=3;i<=n;++i)
        a[i] = a[i-1] + a[i-2];
    return a[n];
}

//fara vector, complexitate O(n)
int Fib2(int n)
{
    int a, a1, a2;
    a1 = 1;
    a2 = 1;
    for(int i=3;i<=n;++i)
    {
        a = a1 + a2;
        a2 = a1;
        a1 = a;
    }
    return a;
}

//sa se spuna daca x este seu nu un termen al sirului Fibonacci
int Fib3(int x)
{
    int f, f1, f2, i;
    f1 = 1;
    f2 = 1;
    f = 2;
    for(i=3; f<x;)
    {
        f = f1 + f2;
        f2 = f1;
        f1 = f;
        i++;
    }
    //x=3
    //1 1 2 3 5 8
    //1 2 3 4 5 6
    if(f==x)
        return i-1;///de reparat aici. de ce e i-1?
    return -1;//inseamna ca x nu apartine sirului Fibonacci
}

int Combinari(int n, int k)
{
    int minim, maxim;
    maxim = k;
    minim = n-k;
    if(minim > maxim)
    {
        maxim = n-k;
        minim = k;
    }

    int numarator, numitor,i;
    numarator=1;
    for(i=maxim+1;i<=n;++i)
        numarator*=i;


    numitor=1;
    for(i=1;i<=minim;++i)
        numitor*=i;


    return numarator/numitor;
}

void Succesor(int c[], int k,int n)
{
    ///elementele sunt numerotate de la 1 la k
    if(c[k]<n)
    {
        c[k]++;
        return;
    }
    Succesor(c, k-1, n-1);
    c[k] = c[k-1] + 1;
}

int main()
{
    /*int n;
    cin>>n;
    cout<<Al_N_lea_termen_Fibonacci(n)<<"\n";
    cout<<Fib(n)<<"\n";
    cout<<Fib2(n)<<"\n";

    cout<<Fib3(34)<<"\n";

    cout<<"C(10, 4) = "<<Combinari(10, 4)<<"\n";*/

    int n, k;
    n = 8;
    k = 6;

    ///c maxim(care nu mai are succesor) : 3 4 5 6 7 8

    int c[] = {0, 1, 2, 3, 6, 7, 8};
    ///succesorul este 1 2 4 5 6 7
    Succesor(c, k, n);
    cout<<"succesorul lui c este:\n";
    for(int i=1;i<=k;++i)
        cout<<c[i]<<" ";
    cout<<"\n";
    return 0;
}