J'ai un algorithme à résoudre sur lequel j'ai vraiment du mal, tout d'abord c'est un problème qu'il faut résoudre par la récursivité, et c'est bien là tout le problème. En ce moment j'ai du mal avec la récursivité, j'ai fais quelque exercice récursive assez simple pour comprendre le principe, j'ai résolu des problèmes simples comme la factorielle d'un nombre, la puissance d'un nombre, multipliez deux nombres en récursives, trouver le reste d'une division, calculer la profondeur d'un arbre. Mais là je bloque sur un exercice, la somme des puissances ou "power sum", je suis actuellement inscris sur un site "HackerRank" où il y a plein d'exos d'algorithmique et je suis tombé sur cette exercice.
Voici le principe, en entrée il faut donné deux nombre X et n, X représente un entier compris entre 1 et 1000 et n la puissance compris entre 2 et 10. Je préfère donner un exemple car j'ai du mal à expliquer clairement en français le principe.
Exemple:
En entrée je donne
X=10 et n=2
En sortie :
resultat : 1
Il y a une manière de représenter le nombre 10 comme la somme des carrés : 1^2 + 3^2 = 10
Autre exemple :
En entrée je donne
X=100 et n=2
En sortie :
resultat : 3
Il y a 3 manières de représenter le nombre 100 comme la somme des carrés :
100 = (10^2)
100 = (6^2)+(8^2)
100= (1^2)+(3^2)+(4^2)+(5^2)+(7^2)
Je voudrais si possible des pistes sur lesquelles me diriger et pas la solution s'il vous plaît
Je sais qu'une récursivité n'est pas necessaire, seulement je veux m'entraîner sur la récursivité car j'ai encore du mal avec cette notion, en itératif je sais que je peux le faire sans problème. Merci de ton aide
Tu cherche ici le nombre de possibilité différentes qui résout ton problème, pour pouvoir le trouver tu dois tester chaque possibilité et transmettre l'info lorsque la possibilité explorée est solution de ton problème. Il va falloir que tu explore les possibilités dans l'ordre pour avoir tout tester lorsque tu rencontre ta condition d'arrêt.
Le fait de jouer avec des carré ne change pas grand chose, tu peux faire la réflexion sur de simple nombre entre 1 et 10, l'exercice sera semblable. Commence par bien définir ta condition d'arrêt, à quelle moment est-il inutile de poursuivre ? Ensuite quelle information va tu transmettre pour que chaque fonction puisse tenir compte du nombres de possibilités précédente plus éventuellement sa possibilité testée ?
Si besoin je peux répondre à ces deux question qui définiront la structure, il restera le code mais si je comprend bien, c'est le raisonnement et la mise en place que tu souhaite travailler.
J'ai vu le sujet, le premier truc auquel j'ai pensé c'est de la mémoïsation. Tu crées un tableau T de taille X + 1, T[i] contiendra.le nombre de décomposition de i en.somme de puissances de n. Tu sais déjà remélirglis deux premières cases, et tu remplis les cases de proche en proche. En effet, le nombre de solutions pour un entier i c'est la somme pour k allant de 1 à i/2 des produits des solutions pour k et pour i - k (pas exactement, mais on comprend l'idée). On ajoute à cette somme 1 si i est lui même une puissance de n (pour le vérifier rapidement, on peut avoir un compteur j qui vaut 1 au départ et qu'on incrémente dès que j^n vaut i).
PS : quelle difficulté d'érire sur téléphone !
PS 2 : À noter que la mémoïsation peut être améliorée.
EDIT : après avoir relu les exemples donnés, ça ne répond pas exactement à ce problème.
yo@n97one pas de soucis merci quand même :) Imguofrie oui c'est bien ça je veux vraiment travailler le raisonnement, la manière de penser quand on code récursivement :), merci pour ton aide je vais y réfléchir à ces questions
Je pensais que j’avais fait un EDIT, mais non. Voici une manière de résoudre le problème.
On calcule T le tableau des puissances de n inférieure à X
resultat = 0
Pour i allant de 0 à len(T) - 1 Faire
resultat = resultat + nombre_solutions(X - T[i], T[i + 1, len(T) - 1])
Fin Pour
Avec nombre_solutions(x, T) qui calcule le nombre de moyens d’obtenir x avec les éléments du tableau T (elle s’écrit très bien de manière récursive).
En gros, on essaie d’abord de faire X avec tous les éléments du tableau, puis avec les n - 1 derniers éléments, puis avec les n - 2, etc.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique