Niveau algorithmique

Problème d'empilement élaboration d'algorithme

Posté par
Nectalis 30-07-10 à 20:56

Bonjour à tous,

Je requiers votre aide pour un problème à l'apparence simple, mais dont l'algorithme que j'ai élaboré n'est pas venu à bout. De plus, mon raisonnement n'est pas très rigoureux et je n'ai quasiment rien démontré. Je vais essayer d'exposer clairement.

La question est textuellement (tirée du hors-série La recherche/Tangente) "On range des oranges en pyramide. Le nombre d'oranges est égal à 100 fois le nombre d'étages de la pyramide. Combien y a-t-il d'étages ?"

La difficulté est surtout de savoir de combien d'oranges chaque étage est constitué : s'il est facile de connaître le nombre d'oranges "sur le bord", il est beaucoup plus difficile de savoir combien il y en a au centre.

Je vais indiquer toutes les étapes de mon raisonnement qui ont aboutis à la réalisation de l'algorithme :

J'ai considéré une pyramide réalisée : sur le dessus, il y a une orange. L'étage du dessous a donc trois oranges. Je considère qu'à chaque étage, un triangle est fait : à l'étage supérieur, d'une orange de côté, l'étage inférieur, deux oranges de côté, et l'étage encore inférieur trois oranges de côté et ainsi de suite.

Ainsi, en appelant l'orange du dessus "Etage 1", on peut généraliser en disant que l'étage C contient un "triangle" de C oranges de côté.

Ainsi, les "bords" des triangles, c'est à dire les côtés (sans compter le "remplissage") sont constitués de Z = C + (C-1) + (C-2) oranges donc de (3C-3) oranges.

Or j'ai remarqué (mais je ne peux le démontrer) qu'un triangle suffisamment grand (en fait supérieur ou égal à 3) contient au centre le triangle deux étages au-dessus.

Exemple : le triangle de l'étage 3 contient (au centre de celui-ci) le triangle de l'étage 1, c'est à dire 1 orange, en plus de ces bords.
De même, le triangle de l'étage 4 contient, en plus de ses bords, le triangle de l'étage 2, c'est à dire 3 oranges.

Là où ça devient intéressant, c'est qu'en itérant l'opération, on peut connaître le nombre d'oranges d'un triangle en connaissant simplement le nombre d'oranges de ces bords et le nombre d'orange des triangles précédent. On a donc contourné la difficulté.

On peut et même on doit, réitérer l'opération si on peut "caser" un autre triangle : par exemple dans le triangle de l'étage 5, on case les bords du triangle de l'étage 3 (facilement calculable : 3C-3) mais il reste une place pour le triangle de l'étage 1. Autrement dit, si C est le nombre d'étages, on retranche 2 à C jusqu'à arriver à 0 ou en dessous en 0, pour savoir combien de triangle il faut caser.

L'idée générale est donc de partir du haut et de construire la pyramide de haut en bas, jusqu'à trouver une pyramide qui corresponde à l'énoncé.

Soit N, le nombre d'oranges
Et E, le nombre d'étages

Je rappelle que N = 100E (énoncé)

J'ai commencé l'algorithme à l'étage 3, en ayant déjà comptabilisé les étages 1 et 2 (d'où N=4 au départ et E=3)

Algorithme

Initialiser N à 4
Initialiser E à 3

Tant que N différent de 100E
Initialiser Q à 0
                   Tant que E-2Q > 0
                   N+3(E-2Q)-3 ==> N
                   Q+1 ==> Q
                   Fin de la boucle
E+1 ==> E
Fin de la boucle

E-1 ==> E
Afficher E

Le problème est que le programme tourne depuis très longtemps sur ma calculatrice : est-ce parce que le temps de calcul est très long ou mon algorithme est-il en boucle infinie ? Déjà, est-il approprié pour résoudre le problème ?

Je vous remercie de votre attention et de votre patience à la lecture

Cordialement

Posté par re : Problème d'empilement élaboration d'algorithme 30-07-10 à 23:08

Bonjour Nectalis,

Le problème étant rédigé comme tu le rapportes, il faut bien voir que la forme de la base fait partie des résultats à donner, en supposant quand même que les bases possibles sont des polygones réguliers (triangle équilatéral, carré, hexagone régulier). Et si l'on s'en tient aux deux possibilités a priori les plus évidentes (triangle et carré), on constate en effet (ça se calcule sans grande difficulté, et sans algorithme) que seule l'une des deux aboutit à une solution ... Faut-il aller plus loin ?

Posté par re : Problème d'empilement élaboration d'algorithme 31-07-10 à 16:03

Oui, pardonnez-moi, je n'ai pas fait attention car un dessin accompagnait l'énoncé : il s'agit bien d'une pyramide à base triangulaire.

Du coup, je devine que le cas impossible est celui d'une pyramide à base carrée. Mais comment le savez-vous ? Je crois que le nombre d'oranges (corrigez moi si je me trompe) d'une pyramide à base carrée de E étages est
N = S(k=1 jusqu'à E) k² : est-ce bien ça ?

Et mon algorithme peut-il répondre au problème, est-il correct ?

Je suis désolé, la réponse est peut-être évidente, mais soyez indulgents, je n'ai que le niveau bac et c'est le premier problème de ce type que je traite ^^.

Je vous remercie de l'attention portée à ma question et de votre réponse.

Posté par re : Problème d'empilement élaboration d'algorithme 01-08-10 à 17:30

Bonjour Nectalis,

Oui, le nombre d'oranges pour une pyramide à base carrée de n étages est bien $N\ =\ \bigsum_{k=1}^n\,k^2\ =\ \frac{n(n+1)(2n+1)}6$ (somme des n premiers carrés, résultat connu) ; et en effet, l'équation $N=100n$ n'a pas d'autre solution entière que $n=0$ .

Mais la base est triangulaire (équilatérale) ; alors le kème étage est un triangle constitué de k rangées ayant 1, puis 2, puis 3, ... et enfin k oranges : le nombre d'oranges du kème étage est donc $\bigsum_{i=1}^k\ i\ =\ \frac{k(k+1)}2$ (somme des k premiers entiers, résultat connu) ; et le nombre d'oranges dans les n premiers étages est : $N\ =\ \bigsum_{k=1}^n\,\frac{k(k+1)}2\ =\ \frac12\,\big[\bigsum_{k=1}^n\,k^2 \,+\, \bigsum_{k=1}^n\,k\big]\ =\ \frac12\,\big[\frac{n(n+1)(2n+1)}6\,+\,\frac{n(n+1)}2\big]\ =\ ...$
Je te laisse continuer : on trouve là que l'équation N=100n a bien une solution entière positive.

Quant à l'algorithme, ce n'est pas vraiment ma tasse de thé, surtout quand il y a une solution algébrique simple.