Algorithmie

[Spinoza]

J'ai réussi !

[LeJeu]

Voilà l'algorithme que je propose après de multiples essais ! Il a l'air de fonctionner

excusez moi par avance car je ne maitrise pas les balises codes ...

C'est pas mal, et ca doit marcher ! Bravo pour la persistance dans l'effort !

Tu peux faire un peu mieux utilisant un "else" en 17/18 ( ca évite de re tester la parité )

J'aime bien le nom de variable intermédiaire "untemps !"

[C.Ret]

Bonsoir,
Cependant mon algorithme ne me donne pas ce dont j'ai besoin soit : La chaine des entiers et la longueur de la chaine ... :hum:

Comme signalé par LeJeu, et comme cela est visible dans mon organigramme, le test de sortie de la "boucle" doit se faire sur la variable.
C'est à dire sur ce qui varie, pas sur une valeur qui reste constante.

L'instruction U_terme_de_la_suite PREND LA VALEUR Nombre_Choisi, ne signifie pas que ces deux variables sont égales dans tout l'algorithme, cela signifie uniquement que l'on copie la valeur de Nombre_Choisi dans la varaible U_Terme_de_la_suite au moment où l'on passe par cette instruction. Ce n'est pas une égalité ni une identité comme en mathématique ou en logique.

Ensuite, pour avoir les termes de la suite, il faut les AFFICHER quelque part dans la boucle. Regarde mon organigramme, tu verra une boite qui permet de faire cela dans la "boucle".
Ce qui te permettra aussi de réflèchir et répondre à la question suivante :

Pourquoi mon organigramme n'utilise-t-il que deux variables (n et c), là où le tien semble en avoir besion de trois ?
A quoi servent tes variables ? Que contiennent-elles à chaque instant de ton algorithme ??

[Spinoza]

Le problème n'est cependant pas terminé ...
Je dois maintenant écrire un algorithme qui calcule la longueur de toutes les chaînes partant de 2 à 100, restitue la longueur d'une chaîne plus longue que toutes les autres et l'entier de départ de cette chaîne
~ Préciser si l'algorithme proposé démontre l'unicité de la chaîne de longueur maximale
~ Si la réponse précédente est négative, peut-on y remédier ?
~ Compléter l'algorithme précédent pour qu'il restitue toute une chaîne de longueur maximale ... C'est reparti :)

J'avais pensé à l'utilisation de la condition "Pour N allant de 2 à 100" et reprendre une partie du premier algorithme cependant je sèche un peu ...

[Spinoza]

Comme signalé par LeJeu, et comme cela est visible dans mon organigramme, le test de sortie de la "boucle" doit se faire sur la variable.
C'est à dire sur ce qui varie, pas sur une valeur qui reste constante.

L'instruction U_terme_de_la_suite PREND LA VALEUR Nombre_Choisi, ne signifie pas que ces deux variables sont égales dans tout l'algorithme, cela signifie uniquement que l'on copie la valeur de Nombre_Choisi dans la varaible U_Terme_de_la_suite au moment où l'on passe par cette instruction. Ce n'est pas une égalité ni une identité comme en mathématique ou en logique.

Ensuite, pour avoir les termes de la suite, il faut les AFFICHER quelque part dans la boucle. Regarde mon organigramme, tu verra une boite qui permet de faire cela dans la "boucle".
Ce qui te permettra aussi de réflèchir et répondre à la question suivante :

Pourquoi mon organigramme n'utilise-t-il que deux variables (n et c), là où le tien semble en avoir besion de trois ?
A quoi servent tes variables ? Que contiennent-elles à chaque instant de ton algorithme ??

Je tenais à te remercier particulièrement C.Ret parce que, mon algorithme "final" dépend de ton organigramme que j'ai repris de façon beaucoup plus attentive et celà m'a permis de comprendre certaine de mes erreurs ..

[C.Ret]

Le problème n'est cependant pas terminé ...
Je dois maintenant écrire un algorithme qui calcule la longueur de toutes les chaînes partant de 2 à 100, restitue la longueur d'une chaîne plus longue que toutes les autres et l'entier de départ de cette chaîne
~ Préciser si l'algorithme proposé démontre l'unicité de la chaîne de longueur maximale
~ Si la réponse précédente est négative, peut-on y remédier ?
~ Compléter l'algorithme précédent pour qu'il restitue toute une chaîne de longueur maximale ... C'est reparti

J'avais pensé à l'utilisation de la condition "Pour N allant de 2 à 100" et reprendre une partie du premier algorithme cependant je sèche un peu ...

Chouette, la varaible Nombre_Choisi va donc être justifiée ! C'était donc une bonne idée.

Une boucle POUR n ALLANT DE 2 A 100 est une excellente idée, car ce type de boucle est bien pratique quand on connait à l'avance l'intervalle à parcourir.


Construire un algorithme qui indique quelle est la langueur de chaine maximale est une chose (assez facile - quoi que ...)
Par contre, modifier cet algorithme pour qu'il affiche toutes et uniquement toues les suites de longueur maximale est bien plus compliqué. La principale difficulté est de savoir, avant d'avoir parcouru toutes les possibilités, la longueur des suites les plus longues.

En effet, il n'y a pas unicité des longueurs.
Par exemple, si l'on considère les suites de longueur #11, il y a en a plusieurs :

Code: Tout sélectionner

1024 512 256 128  64  32  16   8   4   2   1
 170  85 256 128  64  32  16   8   4   2   1
 168  84  42  21  64  32  16   8   4   2   1
 160  80  40  20  10   5  16   8   4   2   1
  26  13  40  20  10   5  16   8   4   2   1
  24  12   6   3  10   5  16   8   4   2   1


C'est un excercice très interessant, mais aussi assez difficile, car ces suite sont comme des arbres:

Code: Tout sélectionner

Lvl#1  #2  #3  #4  #5  #6  #7  #8  #9 #10 #11
    1;););)2;););)4;););)8;);)16;);)32;);)64;)128;)256;)512;)1024;)...
                    ;)       ;)       ;)
                    ;)       ;)       ;););)85;);)170;)...
                    ;)       ;)
                    ;)       ;););)21;);)42;);)84;);)168;)...
                    ;)
                    ;);););)5;);)10;);)20;);)40;);)80;);)160;)...
                            ;)       ;)
                            ;)       ;););)13;););)26;)...
                            ;)
                            ;);););)3;););)6;);)12;););)24;)...


[Spinoza]

J'ai du mal à voir comment je vais créer les 2 algorithmes demandés... Mais bon, ne désespérons pas :)

[Dlzlogic]

Bon, il faut pas désespérer.
Ecrivez la suite des opérations en français sans vous préoccuper de syntaxe. quand je dis en français, ça veut dire avec des mots que vous utilisez habituellement. Un ordinogramme avec des rectangles, des losanges et des flèches, comme l'a montré C.Ret est assurément la meilleure méthode.
Une fois l'algorithme décrit, la traduction en Algobox sera facile.
Pour la question de présentation et de clarté, vous mettez des "indentations" c'est à dire des espaces pour décaler des lignes qui correspondent à un bloc, puis lorsque vous copiez votre algo, vous le sélectionnez, et vous cliquez sur l’icône '#' et ça marche.
[hs] pour une fois qu'on en trouve un qui cherche, profitez-en[/hs] :we:

[C.Ret]

Effectivement, il ne faut se décourager c'est en fait facile pour une machine de faire ce type de calculs.

Voici les plus longues suite que je trouve en fonction du nombre initial :

Code: Tout sélectionner

Intervalle:  Nombre (longueur suite)
 1 et  100:    97(119)
 1 et  200:   171(125)
 1 et  300:   231(128)  235(128)
 1 et  400:
 1 et  500:
 1 et  600:   327(144)
 1 et  700:   649(145)  654(145)  655(145)  667(145)
 1 et  800:   703(171)
 1 et  900:
 1 et 1000:   871(179)


Voici, pour aider, l'organigramme retraçant l'algorithme utilisé pour construire ce tableau de résultats:



Et un apperçu de ce que donne l'affichage avec cet algorithme (n variant de 2 à 30000) (le détail des suites n'est pas donné, uniquement le nombre initial et, entre parenthèse, la longueur de la suite:

Code: Tout sélectionner

    2(  2)    3(  8)    6(  9)    7( 17)
    9( 20)   18( 21)   19( 21)   25( 24)
   27(112)   54(113)   55(113)   73(116)
   97(119)  129(122)  171(125)  231(128)
  235(128)  313(131)  327(144)  649(145)
  654(145)  655(145)  667(145)  703(171)
  871(179) 1161(182) 2223(183) 2322(183)
 2323(183) 2463(209) 2919(217) 3711(238)
 6171(262)10971(268)13255(276)17647(279)
17673(279)23529(282)26623(308)


[Dlzlogic]

Bonjour C.Ret,
Cet outil d'ordinogramme me parait très largement préférable à AlgoBox. Est-il répandu, l'éducation nationale le connait-elle, ou est-ce un produit "maison"?

[Spinoza]

Je trouve que la méthode de l'organigramme est vraiment géniale ! Je comprends tout de suite mieux l'intérêt de l'algorithme et la démarche !

[Dlzlogic]

Comme quoi, les idées des vieux ont quelque-fois du bon. :we:

[C.Ret]

Pour répondre à la question de Dlzlogic, je ne sais pas si l'Education nationale connait cette façon de faire, mais en tout cas elle fait l'objet d'une norme (assez ancienne) qui est toujours en vigueur dans le monde industriel (en extinction).

Il existe diffèrentes variantes qui dépendane de la nature de l'organigramme (gestion documentaire, assemblage, certification et recette, traitements,, production, etc...). Les "boite" ont toujours les mêmes forme (ou presque), d'une norme à l'autre c'est surtout ce qu'il faut mettre dans les cartouches et le long des flèches qui varie.
Mais, c'est une norme (il faut que je retrouve , j'ai quelque part la réfèrence exacte) en même sens que les normes de réprésentation des schéma et autres iagramme comme ceux que l'on fait en Technologie (ex; EMT).

Par ailleurs, l'algorithme ci-dessus permet de répondre aux questions de l'excercice:
~ Préciser si l'algorithme proposé démontre l'unicité de la chaîne de longueur maximale

Nous avons vu ci-dessus que les suite forme une sorte d'arbre. Il peut donc très facilemetn y avoir des suite initiée par des nombre différent qui ont même longueur. (cf. mon exemple à 11 éléments).

L'algorithme tient compte de cela en mémorisant (record) dans la variable r la longueur maximale rencontré (cf. test avec le compteur c )

Cette longueur record mémorisée permet ensuite d'afficher tous les nombres initiaux qui produisent une suite de même longueur.

Par exemple: 649 654 655 et 667 qui produisent tous les trois une suite de longueur (145)


~ Si la réponse précédente est négative, peut-on y remédier ?


Cet algorithme résout déjà de façon simple et élégente le problème de l'unicité des longeur des suites. Le remède a été en quelque sorte d'utiliser une variable supplèmentaire (r) pour mémoriser la longeur de suite record.


~ Compléter l'algorithme précédent pour qu'il restitue toute une chaîne de longueur

Bonne idée, il suffit simplement d'ajouter l'opération au bon endroit et au lieu d'afficher simplement le nombre initiateur de la suite ont peut en donner tout le détail

On constatera alors qu'il y a dans l'organigramme deux endroit où l'on fait le même traitement (une première fois pour compter) et une seconde fois pour afficher.
J'imagine que cette question est là pour introduire la notione de sous-tache ou sous-procèdure.

Car c'est bien à cela que set l'algorithmie; identifier les opérations répétitive ou identique afin de les rassembler et donc faire un programme plus court en évitant les répétitions.
Mais, là on sort de la'algorithmié pour entrer petit à petit dans l'optimisation.

[Dlzlogic]

A l'époque où le dessin informatique n'en était qu'à ses débuts, on utilisait une plaque en plexiglas où les différentes formes étaient découpées en creux, ce qui permettait de dessiner des ordinogrammes à peu près proprement. [maintenant, j'en ai plus besoin, j'ai tout dans la tête :marteau: ].

[Spinoza]

Bonjour à vous tous !

Pour la suite du problème d'algorithmie, d'après ton organigramme C.Ret, j'ai tenté une implantation sous Algobox, cependant l'algorithme ne fonctionne pas et il y aurait une erreur ligne 23 d'après Algobox ... Que puis-je faire ?

CODE DE L'ALGORITHME :
1 VARIABLES
2 n EST_DU_TYPE NOMBRE
3 u EST_DU_TYPE NOMBRE
4 I EST_DU_TYPE NOMBRE
5 r EST_DU_TYPE NOMBRE

6 DEBUT_ALGORITHME
7 r PREND_LA_VALEUR 1

8 POUR I ALLANT_DE 2 A 100
9 DEBUT_POUR
10 I PREND_LA_VALEUR 0
11 u PREND_LA_VALEUR n

12 SI (u!=1) ALORS
13 DEBUT_SI
14 SI (u%2==1) ALORS
15 DEBUT_SI
16 u PREND_LA_VALEUR 1+3*(u)
17 FIN_SI

18 SINON
19 DEBUT_SINON
20 u PREND_LA_VALEUR u/2
21 FIN_SINON
22 FIN_SI

[Dlzlogic]

Bonjour,
Il ne faut pas tomber dans l'excès inverse qui consiste à donner aux variables des noms ultra courts, en particulier une minuscule qui parait bien petite à côté des mots-clé à rallonge, en majuscule, du code.
Pour l'erreur ligne 23, je dirais que 'i' n'est pas défini. Mais comme je ne connais pas la syntaxe, je peux pas en être sûr.

[C.Ret]

Pour un excercice court, utiliser des variable au nom très simple ne pose pas de problème.

Mais, en régle générale, il est préfèrable d'utiliser des noms assez courts (5 à 8 caractères), mais qui donnent du sens.

Par exemple, au lieu d'utiliser n, c ou r comme je l'ai fait, il est préférable d'utiliser Initial, Compteur et Record. Cela peut rapidement aider à la compréhension de l'algorithme.

Concernant l'erreur des Algo-BOX, c'est tout simplement lié au fait que i n'est pas défini, car Algo-Box fait la diffèrence ente capitales et minuscules.

Je trouve Algo-Box particulièrement mauvais; pour un environnemtn de programmation sensé être un support pédagogique, il pourrait y avoir un minium de cohérence.

En particulier, il y a trois choses qu'Algo-Box devrait indiquer clairement avant de tenter tout début d'éxecution :
- La variable i est utilisée dans le code sans être déclarée dans la première partie ?
- La variable n n'est pas initialisée. Quelle est sa valeur de départ ?
- La variable d'itération prédéfinie (POUR ... ALLANT DE ... A ...) I est modifiée (à la ligne 10) ce qui est interdit! Seuls les ordres de la boucle (POUR et SUIVANT) sont authorisés à manipuler le contenu de I


Donc, ça ne marche pas car :
- il y une confusion dans le rôle de n et I,
- il y une erreur majuscule/minuscule dans l'utilisation de I,


De plus, ça ne marchera pas en état car :
- il manque quelque part l'endroit où l'on compte ; je ne vois pas la ligne [I]Comptr record) ALORS
25 DEBUT_SI
26 record PREND_LA_VALEUR comptr
27 AFFICHER* " "
28 FIN_SI

// Afficher nombre inital et record de longueur

29 SI (comptr=record) ALORS
30 DEBUT_SI
31 AFFICHER initial
32 AFFICHER "("
33 AFFICHER comptr
34 AFIICHER ") "
35 FIN_SI

35 FIN_POUR // aller à initial suivant

36 FIN_ALGORITHME
==============
[/CODE]

J'ai corrigé:
- utilisation des noms plus explicites,
- oubli de l'opération d'augmentation du compteur de termes de la suite,
- confusion de la boucle à faire "tant que" le terme de la suite n'est pas 1.
- la mise en page concervée dans le post.

Les organigrammes, tels que je les dessine ont un gros inconvénient, ils n'ont pas de façon explicite pour les structures de boucle évoluées comme TANTQUE ou JUSQU'A, ni les POUR CHAQUE, etc.

Il faut décomposer ces structures en boite de test (losange) ou de traitemetn (rectangle) élémentaires, ce qui peut parfois rendre l'adaptation dans des languages de programmation comme Algo-Box difficile.

Inversement, il y a d'autres languages, comme les premiers BASIC (ou le FORTRAN), le RPN, qui se prêtaient bien à la retranscription directe des organigrammes car les flèches sont souvent des GOTO (surtout dans les tests) ou des passages à l'instruction suivante.

C'est pour cela que de mon temps, on dessinait l'organigramme, simulait l'exécution sur celui-ci, puis nous perforions nos cartes en numérotant les lignes du programme (une instruction par carte perforée) pour enfin les insérer dans l'ordinateur.

On pouvait alors voir tourner nos programme (et ce n'est pas une image, la lecteur de carte faisait réellement tourner les cartes perforées ou les bandes magnétiques).

[Dlzlogic]

Bonjour,
Il y a un bout de temps que je n'avais vu cette machine. Mais à première vue, il n'y a pas de dispositif de "programme". Pour taper des ligne de code, c'est sans intérêt, mais si elle est reliée à une table à digitaliser, ce pense que c'est indispensable.

[Spinoza]

Top ! Effectivement, on s'y retrouve plus facilement avec des variables plus précises !

[C.Ret]

Oui, l'unité centrale n'est pas visible sur la photo, c'est uniquement la perforatrice.

En FORTRAN et BASIC, les programmes pouvaient être saisie uniquement avec cette console.
On codait, le numéro de ligne du programme (perforation + feutre pour numéroter la carte), on codait l'instruction (en fait le Token de chaque instruction) et les arguments (sur cet IBM on allait jusqu'à "40 caractères d'arguments"

La programmation interactive clavier + écran n'est arrivé que bien après; A la rigueur, avec cet équipement on relisait son code en affichant chaque carte; le système décodé et imprimer la ligne de commande (n° de ligne, instruction et arguments ), avec éventuellement en face les code de validation ou d'erreur (erreur de syntaxe, manque terminateur de ligne, etc...).

Et pour l'exécussion, il fallait l'authorisation du chef de salle, on obtenait le résultat le lendemain sous forme d'un listing (ou d'une bande perforrée).

Après avoir appris sur ce truc (qui était déjà obsolette du temps de mes étude, programmer un Apple //c , un Thomson TO7 ou même un Commodore VIC-20 était un régal:
- utilisation systèmatique clavier-écran
- éditeur plein écran
- message d'erreur immédiats,
- lancement du programme directement sur le micro (plus besion d'attendre le lendemain !).