/*

Fichier regroupant les fonctions ayant attrait au calcul des termes de la suite de Fibonacci.

*/


void suiteFiboIt()
{
    int int_terme1; //définition des variables
    int int_terme2;
    int int_termeN;
    int int_termeNsuivant1;
    int int_termeNsuivant2;
    int int_rang;
    int int_compteur;
    int_terme1=1; //premier termes de la suite
    int_terme2=1;
    printf("les deux premiers termes sont %d et %d. \n", int_terme1, int_terme2);
    printf("Jusq'a ou voulez-vous aller? \n");
    scanf("%d", &int_rang);
    int_compteur=1; //initialisation du compteur
    int_termeNsuivant2 =int_terme1; //intiialisation des termes de la boucle
    int_termeNsuivant1 = int_terme2;
    for(int_compteur=3; int_compteur<= int_rang; int_compteur++)
    {
        int_termeN = int_termeNsuivant1 + int_termeNsuivant2; //calcul du terme suivant
        int_termeNsuivant2 = int_termeNsuivant1;
        int_termeNsuivant1 = int_termeN;
        printf("Le terme de rang %d vaut %d \n", int_compteur, int_termeN);

    }
}

int suiteFiboRecNaif(int n) //algorithme vu en amphi qui permet de calculer les termes de manière récursive
{
    int res;
    if(n<=1) //cas de sortie
    {
        return n;
    }
    else //cas de récursion
    {
        res = suiteFiboRecNaif(n-1) + suiteFiboRecNaif(n-2); //la suite telle qu'elle est définie en maths. La fonction s'appelle elle-même
        return res;
    }
}

int suiteFiboRecPower(int n)
{
    /*

    Il s'agit d'un algorithme récursif qui utilise les propriétés surpuissantes de la suite de Fibonacci (cf. ci-dessous).
    Cette partie du programme est en travaux pour le moment, désolé!

    LES PROPRIETES SURPUISSANTES DE LA SUITE DE FIBONNACCI:

    On peut démontrer assez facilement par récurrence sur n les propriétés suivantes:

    - (1) pour n=2k, U(2k) = (2*U(k-1) + U(k))*U(k)

    - (2) pour n= 2k+1, U(2k+1)= U(k+1)^2 + U(k)^2

    */
    int res; //variable de sortie
    if (n<0) //cas de sortie de la partie récursive
    {
        return n;
    }
    else
    {
        if (n%2==0) //cas ou n est pair
        {
            res = (2*suiteFiboRecPower((n/2) -1) + suiteFiboRecPower(n/2))*suiteFiboRecPower(n/2); //calcul grâce à la formule (1)

            /*

            Le problème vient d'ici: pour une raison que j'ignore l'appel récursif fait que l'on rentre dans une boucle infinie
            (enfin je crois) et c'est pas cool. Si quelqu'un trouve une manière de le faire marcher ce serait cool :)

            */
            return res;
        }
        if (n%2==1) //cas ou n est impair
        {
            res= suiteFiboRecPower(n/2 +1)*suiteFiboRecPower(n/2 +1) + suiteFiboRecPower(n/2)*suiteFiboRecPower(n/2); //calcul grâce à la formule (2)

            /*

            Même problème ici.

            */
            return res;
        }
    }
}


void suiteFibo()//Il s'agit du sous-menu correspondant au choix de la suite de Fibonacci dans le menu principal.
{
    int n; //terme à calculer
    int int_choixFibo; //choix de la version
    int res; //valeur du terme de rang n dans les cas récursifs
    do
                { printf("SUITE DE FIBONNACCI \nVersion iterative (1)\nrecursive (2)\nrecursive mode super sayen (non fonctionnelle, Sangoku s'entraine)(3)\nretour au menu principal (4)? \n");
                scanf("%d", &int_choixFibo); //affichage du menu et lecture du choix
                switch (int_choixFibo)
                    {
                case 1: //cas 1: lancement de la fonction itérative
                    printf("Version iterative over naive:\n\n");
                    suiteFiboIt();
                    printf("\n");
                    break;
                case 2: //cas 2: lancement de la version récursive naïve
                    printf("Version recursive naive:\n\n");
                    printf("Quel terme? \n");
                    scanf("%d", &n);
                    res = suiteFiboRecNaif(n);
                    printf("Le terme de rang %d est %d \n", n, res);
                    break;
                case 3: //cas 3: lancement de la version récursive super-sayen le jour ou elle marchera
                    printf("Version recursive super sayen:\n\n");
                    printf("Quel terme?\n");
                    scanf("%d", &n);
                    res = suiteFiboRecPower(n);
                    printf("Le terme de rand %d est %d \n", n, res);
                    break;
                case 4: //cas 4: retour au menu principal
                    break;
                default: //cas pour ceux qui ne savent pas choisir entre 1, 2, 3 et 4
                    printf("Choix impossible, recommencez. \n");
                }

                }
                while(int_choixFibo != 4); //fin de boucle si l'utilisateur demande la sortie
}