Je suis tombé sur un puzzle intéressant: en effet, le nombre a et l'entier positif n sont donnés. Calculez la nième racine d'un nombre sans utiliser de bibliothèques.
Données d'entrée: le nombre a est réel, non négatif, ne dépasse pas 1000, est spécifié avec une précision de 6 décimales. Le nombre n est naturel, ne dépasse pas 10.
Sortie: Le programme doit sortir un seul numéro: la réponse au problème avec une précision d'au moins 5 décimales.
Naturellement, il était intéressant de le résoudre dans un brouillon avec un crayon, puis de le dessiner dans l'éditeur et d'essayer de le compiler. Sans googler, astuces et encore plus en utilisant des bibliothèques. Si vous décidez ceci pour la première fois, essayez d'abord d'écrire un programme pour trouver la racine carrée habituelle. Si vous trouvez la tâche difficile, résolvez presque la même chose, mais plus simple. Ensuite, votre peur disparaîtra et une sorte de compréhension grossière surgira.
Donc, pour commencer, je vais donner un exemple de la façon de calculer la racine carrée sans utiliser de fonction de bibliothèque. Algorithme d'itération séquentielle. Il converge assez rapidement même pour de grands nombres.
#include <stdio.h> int main(void) { double num = 570.15; double root = num / 2; double eps = 0.01; int iter = 0; while( root - num / root > eps ){ iter++; root = 0.5 * (root + num / root); printf("Iteration: %d : root = %f\n", iter, root); } printf("root = %f", root); return 0; }
Vous pouvez exécuter le code ici:
CLIQUEZLa complexité logarithmique de l'algorithme? Ou un autre? :)
Vous pouvez maintenant passer à la version compliquée de la tâche. Dans ce cas, la solution est plus généralisée.
#include <stdio.h> double mabs(double x){ return (x < 0)? -x : x; } int main(void) { double num = 8; int rootDegree = 3; printf(", = %f\n", num); printf(" n = %d\n", rootDegree); double eps = 0.00001; // double root = num / rootDegree; // double rn = num; // int countiter = 0; // while(mabs(root - rn) >= eps){ rn = num; for(int i = 1; i < rootDegree; i++){ rn = rn / root; } root = 0.5 * ( rn + root); countiter++; } printf("root = %f\n", root); printf(" = %i\n", countiter); return 0; }
Vous pouvez exécuter le code ici:
CLIQUEZDans cette solution, j'utilise l'idée d'une approximation initiale relativement bonne. La division séquentielle est alors la deuxième approximation de la racine du nième degré. Ensuite, une nouvelle approximation est considérée en faisant la moyenne des deux actuelles. De manière cohérente, l'algorithme converge vers la racine souhaitée avec une erreur prédéterminée. C'est un peu comme une méthode d'itération simple.
Il s'agit du premier algorithme de travail écrit sur le genou. Nous devons encore réfléchir à la complexité et aux possibilités d'accélération. Soit dit en passant, quelles fonctionnalités d'accélération de cet algorithme peuvent être implémentées à votre avis?
Je pense qu'il y aura une question: "Pourquoi faire cela si tout a été implémenté dans les bibliothèques il y a cent ans?!"
Réponse: Personnellement, j'ai toujours aimé penser aux algorithmes déjà implémentés dans les bibliothèques standard. Essayez de les développer vous-même (enfin, ou de développer une sorte de parodie lente et d'échouer). Il entraîne très bien le cerveau. Par conséquent, à mon avis, «réinventer la roue» est très utile. Et il est catégoriquement dangereux de toujours utiliser tout prêt, sans aucune idée de la structure interne.