Un petit problème intéressant concernant les nombres est la décomposition du carré d'un nombre en une somme de carrés de nombres différents tous plus petits que le premier.
exemple :
soit le nombre 11. 112=121. Il faut décomposer le nombre 121 en une
somme de carrés de nombres distincts plus petits que 11. Plusieurs solutions se
présentent à chaque fois, et plus le nombre initial est grand, plus il y a de
solutions. Voici deux décompositions pour le carré de 11 (une autre solution
vous sera donnée par l'algorithme) :
121=100+16+4+1=102+42+22+12
121=81+36+4=92+62+22
Nous allons d'abord étudier sur le cas concret présenté ci-dessus l'approche à effectuer.
Notre nombre est 11. On doit donc prendre un par un tous les nombres inférieurs à 11, soustraire leur carré de 121, extraire la racine carrée (éventuellement majorée si le résultat n'est pas entier) du résultat et recommencer.
exemple:
On doit trouver 121 avec la somme des carrés
de nombres plus petits que 11.
Les nombres
plus petits que 11 sont 10,9,8,7,6,5,4,3,2,1. On doit tous les essayer, donc
une boucle s'impose.
a0) On prend
10 et on l'élève au carré : 10*10=100.
b0) On
soustrait : 121-100=21.
c0) On
extrait la racine carrée de 21 et on obtient 4,6; on majore le résultat par
5.
appel
récursif :
On doit maintenant trouver le résultat du
b0) avec la somme des carrés de nombres plus petits que 5.
a1) On prend
4 et on l'élève au carré: 4*4=16.
b1) On
soustrait : 21-16=5.
c1) On
extrait la racine carrée de 5 et on obtient 2,2; on majore le résultat pour
obtenir 3.
appel
récursif :
On doit maintenant trouver le résultat du
b1) avec la somme des carrés de nombres plus petits que 3.
a2) On prend
2 et on l'élève au carré: 2*2=4.
b2) On
soustrait : 5-4=1.
c2) On
extrait la racine carrée de 1 et on obtient 1; on ne majore pas le résultat car
il est entier.
appel
récursif :
On doit maintenant trouver le résultat du
b2) avec la somme des carrés de nombres plus petits ou égaux à 1.
Ici on a
"ou égaux à" car il n'y a pas eu de majoration.
a3) On prend
1 et on l'élève au carré: 1*1=1
b3) On
soustrait: 1-1=0
Et c'est
fini, donc on affiche la solution, et on remonte dans la récursion au niveau 2.
a2) On prend
1 et on l'élève au carré: 1*1=1.
b2) On
soustrait: 5-1=4.
c2) On
extrait la racine carrée de 4 et on obtient 2; on ne majore pas le résultat car
il est entier.
Mais on voit
que le nombre 2 obtenu est plus grand que le nombre 1 du a2). Donc on s'arrête.
a1) On prend
3 et on l'élève au carré: 3*3=9.
b1) On
soustrait 21-9=12.
c1) On
extrait la racine carrée de 12 et on obtient 3,5; on majore le résultat pour
obtenir 4.
appel
récursif :
On doit maintenant trouver le résultat du
b1) avec la somme des carrés de nombres plus petits que 4.
a2) On prend
3 et on l'élève au carré: 3*3=9.
b2) On
soustrait : 12-9=3.
c2) On
extrait la racine carrée de 3 et on obtient 1,7; on majore le résultat par 2.
appel
récursif :
On doit maintenant trouver le résultat du b)
avec la somme des carrés de nombres plus petits ou égaux à 1.
... et ainsi
de suite.
Nous devons donc créer une fonction qui extrait la racine carrée d'un nombre et qui la majore lorsque le résultat n'est pas entier.
function racine_majoree(carre: integer): integer;
var a: integer;
begin
a := round(sqrt(carre)); if a * a < carre then inc(a); racine_majoree := a;end;
Nous devons utiliser ensuite un tableau d'entiers dans lequel nous allons accumuler les valeurs décroissantes dont la somme des carrés donne le nombre cherché. Nous allons ensuite les concaténer tous dans une chaîne, de façon à pouvoir les afficher.
t: array[0..50] of integer;
s: string;
On a enfin la procédure "cherche", qui a plusieurs paramètres, comme nous l'avons vu dans l'exemple commenté ci-dessus :
- a_trouver : le nombre à trouver qui est au début un carré, ensuite une différence de carrés. Ce nombre diminue au fur et à mesure qu'on descend dans la récursion.
- nb : le nombre à partir duquel on va chercher les carrés. Ainsi, si le nombre initial est 11, ce paramètre de la procédure sera 10. Il est calculé dans cette procédure avant chaque appel récursif.
- niveau : une variable qui sert d'indice pour le tableau dans lequel on accumule les nombres qui constitueront la solution finale
- exacte : une variable booléenne qui indique si la précédente racine carrée extraite était entière ou si elle avait été majorée. Si elle avait été majorée, alors on doit décrémenter nb.
Pendant la recherche et l'accumulation des nombres dans le tableau, on doit aussi vérifier que chaque nombre ajouté est plus petit que son prédécesseur, sinon on obtient n'importe quel nombre comme une somme de nombres 1 (qui est lui-même le carré de 1, donc le résultat est bien une somme de carrés !).
L'algorithme est le suivant :
procedure cherche(a_trouver, nb, niveau: integer; exacte: boolean);
var bool: boolean;
rac, diff, carre, i, j: integer;begin
if not exacte then dec(nb);for i := nb downto 1 do
begin carre := i * i;diff := a_trouver - carre;
if (diff = 0) and (i < t[niveau - 1]) then
begins := '';
for j := 1 to niveau - 1 do s := s + inttostr(t[j] * t[j]) + '+';
s := s + inttostr(carre) + '=' + inttostr(nb1 * nb1);
memo1.lines.add(s); end else begin rac := racine_majoree(diff);t[niveau] := i;
bool := (rac * rac = diff);
if (i < t[niveau - 1]) then //--- on s'assure que les nombres sont distincts
cherche(diff, rac, niveau + 1, bool);
end;
end;end;
Télécharger le code source Delphi