Discussion :

[pAnTiNhO]

Bonjour à tous !
Je dois réaliser une fonction tribonacci (fibonacci mais la la somme se fait sur 3 termes au lieu de 2). J'ai réussi la fonction mais je dois maintenant faire la même chose sans boucle et sans récurssivité ! Si quelqu'un pouvez m'aider !
Voici le code de la fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
public static int fonctiontribo(int n){
		int nombre1=0,nombre2=1,nombre3=1,resultat=0;
		for(int i=0;i<n;i++){
			resultat = nombre1 + nombre2 +nombre3;
			nombre1 = nombre2;
			nombre2 = nombre3;
			nombre3 = resultat;
		}
		return resultat;
}

Merci d'avance
pAnTiNhO

[dinobogan]

Sans boucle et sans récursivité ? Cela reviendrait à vouloir rouler en voiture, mais sans le moteur ni les roues

[Tux++]

Bonsoir,


je suppose que sans boucle, tu veux dire, récursivement.

Même si c'est un très mauvais exemple pour du récursif mais qui est souvent utilisé en cours.

Il te faut un cas de base (quand arrêtes-tu la récursion?)
et la récursion proprement dite.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
public int Fibo(int n){
        if (n<=1){
               return n;
        }else{
               return Fibo(n-1)+Fibo(n-2);
        }
}

à toi de l'adapter à ton "tri"bo

[pAnTiNhO]

C'est bien ça le soucis c'est sans boucle et sans récursivité je trouves ça bizarre et surtout infaisable...
Si le prof nous l'a demandé ça doit être possible ^^ va falloir se creuser les méninges !

[titourock]

Bonjour,

Cela doit être possible, vu que c'est nöel je n'ai pas le temps de tout détailler mais voilà l'idée en gros :

J'appellerai f_0, f_1 et f_2 les trois premiers termes de la suite.

Il faut ici que tu démontres par récurrence que que le n-ieme terme, à savoir f_n, s'écrit a_n*f_0 + b_n*f_1 + c_n*f_2 où a_n, b_n et c_n sont des coefficients dépendants de n...

Ainsi ça n'est plus qu'une "bête" application numérique et on fait "disparaître" boucles et récursivité...

Je pense que c'est l'idée, je regarderai plus en détail pour trouver les coefficients mais ça ne doit pas être bien sorcier. Il faut y aller pas-à-pas, regarder les premiers termes, poser une hypothèse de récurrence etc...

A bientôt

[EDIT] Autre info, on peut calculer les termes de la suite de Fibonacci, en écrivant sous forme matricielle de la forme Y = AX. Puis en diagonalisant A, on peut calculer facilement les puissances n-iemes de A et donc le n-ieme terme de la suite de Fibonacci. Donc, c'est aussi une piste à explorer...

[droggo]

Hai,

En cherchant avec Google, on trouve rapidement des références.

Il existe des formules explicites démontrées donnant la valeur de Tribonacci(n), dont, par exemple

http://mathworld.wolfram.com/TribonacciNumber.html

J'ai testé la formule en C, avec des doubles, les résultats sont ok jusqu'à n = 54, contrôlé avec une version récursive, puis ça diverge, divergence due à l'approximation venant des calculs avec des doubles.

Mais je ne pense pas que votre prof vous demande de démontrer ça, même si c'est en fait assez simple (?).

[tchize_]

c'est formules utilisent des racines carrées. Or, en informatique, la résolution d'une racine carrée se fait .... récursivement. T'as donc une boucle / récursivité cachée! Bon c'est vrai, ta complexité ne dépend plus de ton nombre n, mais ta complexité devient méchant à estimer.... Car la fonction Math.sqrt ne donne pas se complexité

Pour ce qui est de la précision des doubles, en java tu as les BifDecimal, qui te font des calculs précis mais qui sont vachement plus compliqués à utiliser....

[droggo]

Jia,

c'est formules utilisent des racines carrées. Or, en informatique, la résolution d'une racine carrée se fait .... récursivement. T'as donc une boucle / récursivité cachée!

N'exagérons pas tout de même. Je ne connais aucun programmeur qui dira qu'un calcul est récursif parce qu''il utilise des racines carrées.

Bon c'est vrai, ta complexité ne dépend plus de ton nombre n, mais ta complexité devient méchant à estimer.... Car la fonction Math.sqrt ne donne pas se complexité

Dans la formule en question, les racines carrées n'interviennent que comme des constantes. Il suffit de les pré-calculer (ce que j'ai fait, même pour mon petit test ), et la complexité ne pose plus de problème, et devient celle de la fonction pow(x,y), qui ne va pas bien loin.

Pour ce qui est de la précision des doubles, en java tu as les BifDecimal, qui te font des calculs précis mais qui sont vachement plus compliqués à utiliser....

Je le sais bien, mais :

1) j'ai fait le test en C (c'est précisé dans mon message), et certes il existe des biibliothèqyes multi-précision en C, mais :

2) Je n'avais pas l'intention de calculer des valeurs exactes jusqu'à n = 10000 ou plus, c'était juste pour voir si ça allait

3) L'utilisation des BigDecimal n'est pas plus compliquée qu'autre chose, il suffit de regarder les docs.