Une fraction continue est une série de divisions de ce genre:algorithme optimal pour calculer le résultat d'une fraction continue
depth 1 1+1/s
depth 2 1+1/(1+1/s)
depth 3 1+1/(1+1/(1+1/s))
. . .
. . .
. . .
La profondeur est un nombre entier, mais s est un nombre à virgule flottante.
Quel serait un algorithme optimal (performance-sage) pour calculer le résultat pour une telle fraction avec une grande profondeur?
Astuce: déroulez chacune de ces formules à l'aide de l'algèbre de base. Vous verrez un modèle apparaître.
, je vous montrerai les premiers pas il devient évident:
f(2,s) = 1+1/s = (s+1)/s
f(3,s) = 1+1/f(2,s) = 1+(s/(s+1)) = (1*(s+1) + s)/(s+1) = (2*s + 1)/(s + 1)
/* You multiply the first "1" by denominator */
f(4,s) = 1+1/f(3,s) = 1+(s+1)/(2s+1) = (1*(2*s+1) + (s+1))/(2*s+1) = (3*s + 2)/(2*s + 1)
f(5,s) = 1+1/f(4,s) = 1+(2s+1)/(3s+2) = (1*(3*s+2) + (2s+1))/(3*s+2) = (5*s + 3)/(3*s + 2)
...
Hint2: si vous ne voyez pas la tendance évidente nouvelle forme ce qui précède, la plus optimale L'algorithme impliquerait de calculer des nombres de Fibonacci (ainsi vous devriez google pour le générateur optimal de Fibonacci #).
NOTE: n'ayant pas appris l'algèbre basique en anglais, j'espère que je n'ai pas mélangé "dénominateur" et "nominateur" dans le commentaire ci-dessus - j'espère que les formules sont assez évidentes même si j'ai mélangé la terminologie. – DVK
Non, je crois que vous avez raison. Le numérateur est le numéro en haut de la division et le dénominateur en bas. IE, 2/3 -> Numérateur = 2; Dénominateur = 3 – Daenyth
@Daenyth - Thx! – DVK
Odeur semblable à la récursivité de la queue (récursivité (récursivité (...))).
(En d'autres termes - en boucle)
Généralement, C ne supporte pas la récursion de la queue. –
Mais tout noir @ James algorithme récursif peut être :-) déroulèrent Il ne change pas la complexité d'exécution. (Je ne prétends pas pour que cela soit une bonne réponse pour l'algorithme « optimale ».) –
@James Black: Comme le mentionne @pst, je préconise de transformer le problème récursif de la queue (au niveau conceptuel) en une boucle (au niveau du code) qui est un processus plutôt trivial. C'est là que mon commentaire "en boucle" entre, bien que je suppose que cela aurait pu être plus clair. –
Je commencerais par le calcul 1/s, que nous appellerons a.
Ensuite, utilisez une boucle for, car, si vous utilisez la récursivité, en C, vous pouvez rencontrer un débordement de pile. Puisque ceci est un devoir, je ne donnerai pas beaucoup de code, mais, si vous commencez avec une simple boucle, de 1, alors continuez à l'augmenter, jusqu'à ce que vous obteniez 4, alors vous pouvez juste aller à n fois.
Puisque vous allez toujours diviser 1/s et que la division est chère, le fait de le faire une seule fois vous aidera avec les performances.
Je m'attends à ce que vous trouviez un motif qui vous aidera à optimiser davantage.
Vous pouvez trouver un article comme celui-ci: http://www.b-list.org/weblog/2006/nov/05/programming-tips-learn-optimization-strategies/, pour être utile.
Je suppose qu'en termes de performances, vous voulez dire que vous voulez que ce soit rapide, quelle que soit la mémoire utilisée, btw.
Vous pouvez trouver que si vous mettez en cache les valeurs que vous avez calculées, à chaque étape, que vous pouvez les réutiliser, plutôt que de refaire un calcul coûteux.
Personnellement, je ferais 4-5 étapes à la main, en écrivant les équations et les résultats de chaque étape, et voir si un motif émerge.
Mise à jour:
GCC a ajouté récursion queue, et je ne remarqué, depuis que j'essaie de limiter fortement récursivité en C, par habitude. Mais cette réponse a une bonne explication rapide des différentes optimisations gcc basées sur le niveau d'optimisation.
http://answers.yahoo.com/question/index?qid=20100511111152AAVHx6s
vos algorithmes ne sont décidément PAS les plus optimaux, bien que ce soit l'implémentation la plus optimale de cet algorithme particulier. – DVK
@DVK - Je n'essaie pas de donner l'algorithme le plus optimal, comme il était indiqué comme devoir, mais de trouver un moyen de trouver un meilleur algorithme, c'est pourquoi j'ai suggéré de faire plusieurs pas à la main pour trouver un motif , afin qu'une solution meilleure que ce que j'ai suggéré puisse être trouvée. –
Je voudrais élaborer un peu sur DVK's excellent answer. Je vais coller avec sa notation f(d,s) pour indiquer la valeur recherchée pour la profondeur d.
Si vous calculez la valeur f(d,s) pour les grandes d, vous remarquerez que les valeurs convergent comme d augmente.
Soit φ = f (∞, s). C'est φ est la limite que d approches infini, et est la fraction continue entièrement expansé. Notez que φ contient une copie de lui-même, de sorte que nous pouvons écrire φ = 1 + 1/φ. En multipliant les deux côtés par φ et en réarrangeant, on obtient l'équation quadratique
φ - φ - 1 = 0
qui peut être résolue pour obtenir
φ = (1 + √ 5)/2.
Ceci est le famous golden ratio.
Vous constaterez que f(d,s) est très proche de φ à mesure que sa taille augmente.
Mais attendez. Il y a plus!
Comme DVK a fait remarquer, la formule de f(d,s) implique termes de la suite de Fibonacci. En particulier, il implique des rapports de termes successifs de la séquence de Fibonacci. Il y a un closed form expression for the nth term of the sequence, à savoir
(φ n - (1- φ) n)/√ 5.
Depuis 1- φ est inférieur à un, (1- φ) n devient petit comme n devient grand, donc une bonne approximation pour le nième terme Fibonacci est φ n/√ 5. Et pour revenir à la formule de DVK, le rapport des termes successifs dans la séquence de Fibonacci tendra à φ n + 1/φ n = φ.
C'est donc une deuxième façon d'obtenir au fait que la fraction continue dans cette question est évaluée à φ.
ce n'est pas des devoirs parce que mon école est fermée en juillet dernier, maintenant je suis assis dans ma maison et j'essaie juste de résoudre un problème –
Puisque vous voudrez probablement résoudre ceci vous-même, pour le meilleur effet d'apprentissage, je pense il est bon de traiter cette question comme s'il s'agissait de devoirs. – Svante