L'algorithmique une forme d'art

Bonjour amis artistes.

Alors comme ça ici ça partage des photos, des tableaux, des textes ? Mais je viens en tapant du pied au sol et en vous présentant l'Algorithmique

Kezako ? Algorithmique ça rime avec arithmétique. En revanche ça rime plus avec logique.

Alors l'algorithmique c'est de la logique pure. Par exemple si je fais ça dans un tel endroit après avoir fait ça autrefois il risque que m'arriver cela.

L'algorithmique c'est la représentation du cheminement de pensé que tout le monde a au quotidien et qui régit les lois de notre monde et de la nature.

C'est le cerveau qui parle grosso modo !

DesCartes a inventé une méthode révolutionnaire pour la résolution de problème qui préconise en premier lieu de se calmer, de comprendre la question et de la diviser en plusieurs sous questions qui ont un rapport entre elles ou pas forcément au premier abord.

De cette façon on peut naturellement constater que DesCartes avait une longueur d'avance car il avait pleinement conscience du schéma de pensé, des relations entre les idées, à une époque où on brûlait encore des pauvres personnes sur la place publique.

Il a littéralement inspiré les programmeurs à un point qu'ils connaissent tous la méthode.

Maintenant quelle rapport entre :




ET



Aucun justement et elle est là la beauté. derrière cette ligne de code comme derrière ce tableau il y a une personne qui a philosophé, qui a muri, qui a échoué, une personne qui avait les idées qui partaient dans tous les sens et qui a fini par les canalyser.

Et toi tu vois cet oeuvre de ta manière. J'aime bien la métaphore du ballon et du bonhomme articulé qui marche sur les sentiers. Le ballon gonfle et emporte avec lui toutes les idées mais il ne fait pas attention aux détails comme la forme et la structure. Il englobe c'est tout. En revanche le bonhomme marche, il marche, il marche, il sent le sol chaud sous ses pieds, il se perd sur le chemin, il ne voit que l'horizon et d'où il est venu.

Voilà j'espère que ça vous a plu

Moi ça m'a bien plus ça ma rappelé :
Un bouquin où les gens écrivaient le vent avec des ponctuations
Un film PI ou le mec cherche la solution de la Torah dans les maths
Les figures géométriques de Penrose et les trucs à la sauce Pythagore
Et mon amour des soliloques....

Je ne voyais pas les lignes de code comme de potentielles oeuvres d'art, mais, pourquoi pas ? Ton intervention est ma "petite découverte du jour" (je me balade plutôt au hasard sur ce forum, un peu comme quand on se promène sans but en vacances, prêt-e à découvrir quelque chose au détour du chemin).

J'imaginais les programmeurs comme des gens à lunettes et avec un grand couteau, prêts à découper chaque action en de multiples sous-actions. Rien de poétique, selon moi. Ca me change de point de vue d'un coup.

Au fait, "canalyser", c'est un mélange de "canaliser" et d'"analyser" ? Un truc de geek ?

C'est à peu près ce que font les développeurs tous les jours, et on peut dire que ce ne sont pas tous des artistes du codage
Pour ma part, je ne parlerais pas d'art pour qualifier les algo, mais plutôt d'élégance, tout comme la pensée, car j'associe l'art à l'esthétique. Et s'il y a un art de penser, et qu'on peut considérer qu'il y a un art de coder, la sensibilité dans le codage n'a que peu de place je crois. Il s'agit essentiellement d'efficacité, et d'autres notions relatives aux environnements dans lesquels ce code est produit.
Donc je résumerais par "intelligence" et "élégance", mais pas d'esthétique pour autant. (bien que l'indentation compte beaucoup pour la lisibilité !)

Il y a une certaine beauté dans un alogithme, qui coïncide souvent avec efficacité, mas pas toujours.
Par exemple, l'indentation n'apporte aucun gain d'efficacité au niveau de l'execution du progamme, mais je trouve ça beau, esthétiquement parlant (surtout quand il y a de nombreux niveaux d'indentation, qui font une sorte d'effet de vague sur la gauche du document), et pratique (compréhension du code facilitée).

L'efficacité a parfois quelque chose de beau, dans la formule, parfois non (un code indéchiffrable mais efficace n'est pas beau, juste performant).
Exemple de 'beauté' algorithmique:
Supposons qu'on doive programmer une fonction retournant la somme des nombres de 1 à X.
On peut faire une bête boucle, avec une variable pour stocker le résultat du calcul, qui est augmentée à chaque itération: 1 ->3 > 6 -> 10 -> 15...
Ou on peut faire: (x+1)*(x/2), formule bien plus astucieuse et élégante, qui donne le résultat en effectuant beaucoup moins d'opérations.
Ici c'est trivial, mais dans de grosses applications, ça fait la différence entre des programmes qui nécessitent un PC haut de gamme récent pour fonctionner sans lag, et d'autres, de complexité similaire, qui tourneraient sans problème sur des PC des années 90.

Malheureusement, il existe un tas de codeurs 'dégueulasses', qui font des programmes qui fonctionnent vite fait, mais pas du tout efficaces, et super bordéliques à comprendre (et quand on t'embauche pour faire évoluer le code de ces gens là, ça peut parfois aller plus vite de recommencer à zéro).

J'ai deux petits exemples d'algorithmes que je trouve très simples et élégants, il s'agit d'employer la récursivité (possibilité qu'a une fonction de s’appeler elle-même).

1/ Supposons qu'on doive programmer une fonction retournant la somme des nombres de 1 à X.

Solution récursive :
sum (n) = n + sum(n-1)
sum(1) = 1

Et roulez jeunesse !

2/ Supposons qu'on veuille retourner la liste inversée de la liste fournie en argument.

Solution récursive :
renverse (l) = renverse(sous-liste(l)) plus premier_element(l)
premier_element(vide) = vide

Et roulez jeunesse !!

oui en effet ce qui se conçoit bien s'énonce etc

bien coder suppose bien comprendre ce qui doit être fait et ensuite réduire la complexité le plus possible dans des codes simples

puis documenter pour le suivant ou pour soi même dix ans plus tard

indenter aussi

le parallèle avec la peinture est intéressant, par petites touches pointillistes ou par grandes couches définissant les grandes lignes de ce que l'on veut produire, ou les détails sur lesquels onv eut polariser dans les règles de l'art

l’algorithmique a donc son rythme comme en musique, appel dans un appel et le tout appelé dans un autre , bloc dans bloc, lignes dans blocs et même blocs de lignes dans bloc etc

pas de limite aux appels sauf l'efficacité première , si on imbrique trop on perd en lisibilité et en vitesse, si on imbrique trop peu on a de long spaghettis infames

puis parfois le bloc est écris par un autre, laid sale comme une grosse tache de peinture sur sa belle toile à soi

berg

programmer comme on code une séquence de son

l'algo est beau s'il sonne bien en somme

si ré donc fa et si fa dont sol alors mi sauf si bémol alors ré do

on peut donner un nom au bloc

harmoniser le code sonorement

le bloc impression c'est ré do , le bloc affichage c'est la mi

do ré la mi, imprime moi l'écran

etc

mi ré la sol

l'impression est stockée

etc

je suppose que chaque artiste a sa palette de couleurs, y compris celle qu'il invente avec de la coquille d'oeuf par exemple ou autre ingrédients

chaque programmeur a ses manies, ses algorythmes favoris ou appris, ses fonctions et bibliothèques empruntées au monde; conçues de zéros ou juste modifiées

optimiser je suppose, un art subtil qui implique que l'on comprenne le comment bien avant le pourquoi

je me demande si je n'ai pas entendu un jour un listing de programmation transformé en sons








c'est beau et compliqué et simple et .. beau

et puis y a tant de brols

https://fr.wikipedia.org/wiki/Algorithmique

https://fr.wikipedia.org/wiki/Algorithme_de_Bellman-Ford

"Un algorithme énonce une solution à un problème sous la forme d’un enchaînement d’opérations à effectuer. "

étapes donc capacité de réduire la complexité en des blocs maitrisables qui se suivent, quand un problème semble insoluble commencer par le diviser en deux ou autant de morceaux nécessaires

conçois moi le logiciel pour la navette spatiale.. on commence par le code pour monter et descendre les roues...

puis on apprend


", le calcul de l’efficacité d’un algorithme (sa complexité algorithmique) consiste en la recherche de deux quantités importantes.

La première quantité est l’évolution du nombre d’instructions de base en fonction de la quantité de données à traiter (par exemple, pour un algorithme de tri, il s'agit du nombre de données à trier), que l’on privilégiera sur le temps d'exécution mesuré en secondes (car ce dernier dépend de la machine sur laquelle l'algorithme s'exécute).

La seconde quantité estimée est la quantité de mémoire nécessaire pour effectuer les calculs"

https://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_(informatique_th%C3%A9orique)

et ça ça me fascine

https://fr.wikipedia.org/wiki/Algorithme_g%C3%A9n%C3%A9tique

en ia j'ai vu il ya quelques années un robot dont on avait retiré une des pattes et qui avait la capacité de réécrire en partie son code de marche je pense à l'université de manchester une anglaise en tout cas et le robot a force d'essais et d'erreurs avait réécris tout seul ses alogrythme correctifs de son handicap de marche dont des inédits

cette manière de coder par la pratique est à la fois inquiétante sur les ia et terriblement fascinante

ah.. je lis aussi

"ces algorithmes ont été utilisés par la NASA pour la mission d'exploration de Mars, dans la gestion des déplacements du robot Pathfinder. "

ben voilà même technique

ah et ici aussi

"La société Sony les a aussi utilisés dans son robot Aibo. En effet, ce robot a « appris » à marcher dans un dispositif expérimental où son système de commande a été soumis à une évolution artificielle. Différents modes de commandes ont été testés, les plus performants ont été croisés et le résultat a été très positif. De génération en génération, le robot s'est redressé, puis a commencé à marcher en chutant souvent et a fini par marcher d'un pas assuré. "

trop cool

en gros on réinjecte dans la boucle le résultat de la boucle précédente comme nicolas_72 l'évoque

ZebMckay11, j'adoooore ta première vidéo, c'est fascinant et amusant à la fois. On voit comment le développeur procède pour trier une liste. On ne connait pas les contraintes de base, mais on voit la diversité de raisonnements. Un régal.

Petite énigme qu'on donne aux informaticiens débutants.

Vous avez deux variables entières X et Y.
Chacune a sa valeur initialisée.
Exemple état initial : X=5 et Y=12

A l'aide de l'affectation et des opérations arithmétiques classiques, comment pouvez-vous échanger leur contenu (quel qu'il soit initialement) ? Combien d'instructions sont nécessaires ?
Etat final souhaité : X=12 et Y=5

Rem : on se passera donc d'une troisième variable intermédiaire Z.

Trois exemples d'instruction :
X := 7 (signifie qu'on affecte 7 à X ou que X reçoit 7)
Y := Y * 3 - X
X := X - 2*Y

Bon je me lance, au prix de ne pas être à la hauteur d'un informaticien débutant (pourquoi t'écris ça franchement ??)

shame on me:

C'est réellement une énigme que l'on pose à des débutants. J'y ai eu droit à mon époque. OK avec ta réponse.

Nicolas_72 a écrit:Petite énigme qu'on donne aux informaticiens débutants.

Vous avez deux variables entières X et Y.
Chacune a sa valeur initialisée.
Exemple état initial : X=5 et Y=12

A l'aide de l'affectation et des opérations arithmétiques classiques, comment pouvez-vous échanger leur contenu (quel qu'il soit initialement) ? Combien d'instructions sont nécessaires ?
Etat final souhaité : X=12 et Y=5

Rem : on se passera donc d'une troisième variable intermédiaire Z.

Je ne l'ai jamais eu celle là, mais j'ai eu sa variante en tant que débutant: comment inverser X et Y.
Le piège étant de faire X=Y, Y=X (ça ne marche pas), et l'astuce étant de recourrir à une variable Z (dont la création n'était pas mentionnée dans l'énoncé) pour faire Z=X, X=Y, Y=Z.

Pour ta version, je dirais:

Spoiler:

J'aurais l'occasion de parler de la programmation, parce que cela a eu une grande importance pour moi, d'un point de vue d'une éthique rationnelle mais aussi d'une éthique esthétique (d'une éthique morale moins, mais qui sait ?), c'est-à-dire que cela a nourri ma réflexion philosophique.

Mais, auparavant, je voudrais faire un commentaire concernant le problème posé par Nicolas.

Ma solution:

Elle est légèrement différente de celle de Xav et d'Aperzebre, tout en étant de même complexité algorithmique. Alors se pose la question : laquelle est la plus élégante ? Et c'est là que cela devient intéressant. C'est un cas particulier que j'aurais pu étudier dans ma thèse de logique si j'en étais venu à bout.

Alors, je demande aux intervenants de trancher entre les deux solutions, et d'indiquer pourquoi. Selon moi, ma solution était plus symétrique. Et pourtant, en étudiant le problème à trois variables (où il s'agit d'effectuer une permutation circulaire entre les valeurs de X, Y et Z : X devient Y, Y devient Z et Z devient X), j'en suis venu à penser que c'était la leur qui était la plus élégante. Mais il faudrait généraliser à n variables.

Bon, pourrez-vous indiquer votre solution à 3, 4 ou n variables et trancher la question ? Pour ma part, j'ai trouvé une solution en 4 étapes pour le cas à 3 variables. Pourrez-vous la trouvez ? Et y en a-t-il plusieurs, certaines plus élégantes que d'autres ?

J'ai l'impression que la solution de Xav et d'Asperzèbre (à laquelle j'ai pensé aussi en premier), se généralise à N variables de façon assez automatique, dans le cas d'une permutation circulaire (auquel on peut toujours se ramener en réarrangeant les assignations, quitte à obtenir plusieurs permutations circulaires):

Spoiler:

Edit : je proposais un autre exercice marrant, mais je me suis embrouillé et ai dit n'importe quoi. Je vais essayer de retrouver ce à quoi je pensais ^^

Oui, c'est ce que je conjecturais aussi. Bravo ! Maintenant, indépendamment du fait d'en fournir une démonstration, il s'agirait de justifier de l'élégance de la méthode. Une notion qui s'impose, c'est celle de sa généralisation. Y en a-t-il d'autres ?

Pieyre, j'ai remarqué que lorsqu'il s'agit de logique, tu as toujours des raisonnements qui me sont contre-intuitifs, mais tout aussi valables.

Vu la simplicité du problème, je n'irais pas chercher une solution meilleure qu'une autre, ce n'est pas assez complexe pour moi pour qu'elles se démarquent. Cela dit, avant d'écrire ma réponse, je m'étais posé la question de démarrer par une addition ou par une soustraction.
Dans mon esprit, il est plus confortable de penser que lors de la première assignation, on a toujours les 2 variables entières (x + y).
Ton raisonnement est plus abstrait, ta première assignation est une soustraction, la valeur de X ne "contient" plus, ni X, ni Y, mais une 3ème valeur en quelque sorte. Il est à noter que tu es très habile avec les mathématiques, tu as certainement un baguage plus important que le mien dans ce domaine, et il est possible qu'avec d'avantage de connaissances, j'aurais procédé comme toi.

Ma solution avec plusieurs variables reste dans le même esprit :
a=a+b+c+d+e
b=a-b-c-d-e
c=a-b-c-d-e
d=a-b-c-d-e
e=a-b-c-d-e
a=a-b-c-d-e

Avec plus de 2 variables par contre, je préfère largement ma solution, ne serait-ce que pour la simplicité d'écriture, il n'y a même pas à réfléchir.

Dans certains cas j'ai peut-être une démarche différente, plus abstraite sans doute, ou du moins qui vise à généraliser un problème plutôt que d'en fournir une solution rapide de façon efficace, et aussi que la solution doive respecter certains principes de symétrie, plus généralement d'harmonie, notamment dans la façon de l'écrire. Aussi j'ai été très gêné quand il m'a fallu passer du langage Pascal (le premier véritable langage de programmation que j'ai appris) au langage C (de même que de devoir apprendre l'anglais après avoir appris le français). De même, si j'ai bien aimé l'analyse élémentaire au lycée, par la suite en faculté j'ai eu un peu de mal avec les statistiques et l'analyse numérique et j'ai préféré l'algèbre, la topologie et la logique.

C'est en partie ma formation de logicien qui veut ça, et le fait que tout ce qui est technique me barbe (même si la logique c'est souvent très technique); mais c'est aussi qu'auparavant je n'ai pas tellement eu de réactivité intellectuelle supérieure aux autres (sinon celle qui est développée par le travail), enfin ce coup d'œil qui fait qu'on entrevoit le bon chemin directement (alors que sur le plan physique j'ai davantage cette réactivité), comme le fait inverse que je n'étais pas très travailleur. Déjà à l'école primaire, même si je devais être en général le premier à répondre, je ne me sentais pas à l'aise avec le calcul mental; et par la suite, au lycée et en faculté, il me fallait toujours un certain temps avant d'entrer dans une épreuve sur table (alors qu'à la fin, la concentration ayant pris, et un certain plaisir qui va avec, je serais bien resté davantage de temps).

Mais là, je ne sais pas si cela qui a joué. Dans l'expression X - Y, il y a exactement la même information partielle sur les valeurs de X et Y que dans l'expression X + Y. Non, même si je ne suis pas vraiment dit ça, je pense que ce qui a joué, c'est le fait que la différence est plus fréquente que la somme dans de nombreuses constructions mathématiques (ainsi le calcul de la distance entre deux points ou le taux de variation d'une fonction), même si en informatique il y a beaucoup de sommations, en relation avec des processus cumulatifs, itératifs. Et puis, il était évident qu'il allait falloir utiliser la différence pour éliminer des valeurs. Aussi j'ai été très satisfait de trouver une solution parfaitement symétrique avec une différence aux deux bouts. Simplement, en généralisant, eh bien ça n'allait plus (ou tout au moins je n'ai pas pu m'orienter vers une telle solution symétrique). Alors autant privilégier la forme générale qui se dessinait, d'autant plus qu'elle permet de justifier plus facilement de la méthode.

Mais je ne crois pas que le fait que les deux solutions soient élémentaires doive nous empêcher de nous poser déjà et la question de la complexité (un bien grand mot dans ce cas, certes) et celle de l'élégance.

Ainsi, il y a quelques années, avec le développement des logiciels de démonstration mathématique, un logiciel avait trouvé une démonstration minimale, – sinon inédite comme cela avait été annoncé, au moins qui n'était pas présentée dans l'enseignement –, au sujet d'un problème pourtant d'une grande simplicité. Il s'agissait de démontrer que si un triangle avait deux côtés égaux – autrement dit qu'il était isocèle, disons en A – alors l'angle en B était égal à l'angle en C. La démonstration classique est simple, bien sûr, mais là elle était minimale : si l'on permute B et C, le problème est inchangé; donc on a le résultat; c'est tout. C'est bien ce qu'on voit de façon intuitive, mais moi j'aurais cherché à appliquer des règles apprises, parce que voir ce n'est pas suffisant pour que cela nous conduise à adopter une méthode...

Juste pour le fun, algorithme récursif pour additionner deux entiers :

somme(x, y) = somme (x+1, y-1)
somme (z, 0) = z

A ne pas utiliser bien sûr !

De la même manière, comment coder le produit de deux entiers ?

Avant de proposer une réponse, il me paraît intéressant de rappeler que cet algorithme de la somme, s'il n'est pas efficace dans le cadre de la représentation courante des entiers, est pourtant le plus immédiat et le plus simple à formaliser dans la théorie arithmétique élémentaire, celle de Peano.

Il s'agit juste de considérer les entiers comme des suites de bâtons que l'on place dans une boîte, comme cela a été considéré historiquement pour compter les objets (même si l'on ne mentionnait pas la boîte, notamment parce qu'on ne se représentait pas le zéro, mais il pouvait s'agir de la paroi d'un rocher ou d'un morceau de peau d'animal). Soit la boîte est vide, soit il y a un bâton (|), deux bâtons (||), trois bâtons (|||), etc. (en relation avec la forme des doigts). Simplement, les mots un, deux, trois, etc. correspondent pour le moment à des conventions langagières. Initialement, il y a juste la boîte et son contenu, et le fait qu'on puisse parcourir séquentiellement ce contenu. Alors, les mots qui désignent ces configurations suffisent pour compter les objets. Mais, dès lors que l'on veut trouver le mot qui correspond au compte de la réunion de deux ensembles d'objets, on est obligé d'en revenir à la représentation primaire, qui calque le réel : |, ||, |||, etc. de mettre bout à bout les symboles | et de recompter. Sauf qu'on peut commencer le compte à partir d'un compte déjà connu et ajouter un à un les bâtons de la deuxième quantité, c'est-à-dire sans pouvoir utiliser le fait qu'on a déjà compté cette deuxième quantité : ||| + || = |||| + | = |||||.

Conclusion : on n'utilise de fait qu'un symbole : | et une opération : ajouter | à la première quantité en le retranchant de la deuxième. D'où chez Peano le fait d'introduire uniquement deux symboles : 0 (plutôt que 1) et S, la fonction successeur, de sorte que 0 désigne le contenu vide, S(0) désigne |, S(S(0)) désigne ||, etc.

D'où la définition de la somme n + m par récurrence :

n + 0 = n
n + S (p) = S (n + p)

D'un point de vue mathématique, c'est assez clair, mais cela masque un élément : le fait de déterminer, quand m = S (p), ce que vaut p. Pour cela, on aurait besoin de la fonction prédécesseur P (si m = S (p), alors c'est que p = P (m)). Mais en fait ce n'est pas une opération mathématique complexe comme l'est la somme que l'on tente de définir : de même que S correspond juste à ajouter un bâton, pour faire P il s'agit d'en enlever un.

Aussi on peut transformer l'expression pour en faire un algorithme de la façon suivante :

si m = 0
  n + m = n
sinon
  n + m = S (S (n), P (m))

Ce serait un algorithme acceptable si dans la mémoire d'un ordinateur les entiers étaient représentés par des séries de bits 1 et non par des séries de bits 0 et 1 selon la numération de position.

Aussi, quand Nicolas propose la forme somme (x, y) = somme (x+1, y-1), c'est comme si l'on calculait la somme de façon primaire alors qu'on la connait déjà (ainsi que la différence) de façon plus efficace.

Bon, j'ai été un peu long : c'est fou comme ce qui est élémentaire prend du temps !

Alors, pour en revenir au problème posé par Nicolas, je propose :

n × 0 = 0
n × S (p) = n × p + n

Ou, de façon algorithmique :

si m = 0
  produit (n, m) = 0
sinon
  produit (n, m) = somme (produit (n, m-1), n)

Il faut remarquer tout de même qu'il y a une différence avec le cas de la somme. Déjà, le produit utilise la somme; je ne vois pas comment il pourrait en être autrement. Cela correspond à une dissymétrie qu'on ne peut pas s'empêcher de tenter de justifier. Pour cela, on peut se ramener une fois de plus à l'origine du comptage. On additionne des quantités d'objets de même nature, enfin de même type (cela peut être des choux et des carottes, peu importe : il s'agit toujours de légumes). Mais, quand on multiplie, il s'agit cette fois d'une quantité d'objets que l'on considère un certain nombre de fois. C'est-à-dire que les deux opérandes ne sont pas a priori de même nature. Dans le langage courant, cela se manifeste dans le fait qu'on dise : « a fois b » de façon équivalente à : « b multiplié par a », et non le contraire. C'est typique d'une loi de composition externe, ce qui peut faire penser à un espace vectoriel plutôt qu'à un anneau ou un corps. Et pourtant la structure d'anneau convient a priori. C'est-à-dire que la question pratique, c'est à la fois : « si j'achète trois cagettes de douze tomates, combien j'ai de tomates ? » et : « si j'ai un terrain qui fait 100 m sur 200 m, combien j'ai de m² ? » Dans le second cas, les deux opérandes sont de même type (mon terrain, c'est aussi 200 m sur 100 m, ce qui me conduit à considérer la notion de m²) mais pas dans le premier (je n'achète pas douze cagettes de trois tomates). Maintenant, en pratique, le second cas se ramène au premier : je peux considérer que j'ai 200 fois une bande de terrain de 100 fois 1 m². C'est donc le premier cas qui est le plus général et le plus intéressant.

Alors, est-ce qu'on peut relier l'algorithme du produit (celui que j'ai indiqué, qui ne fait que reprendre celui de Peano) à une façon primitive de considérer le produit ? Considérons la multiplication 2 × 4. Il s'agit de quatre fois deux, qu'on peut ramener au fait de placer à la suite des séries d'objets : || || || ||, que l'on doit additionner. Comment s'y prend-t-on si l'on n'a aucune notion mathématique ? Eh bien, à mon avis, on fait comme ça : ((|| + ||) + ||) + ||, autrement dit : somme partielle – ou produit partiel – + reste à additionner. C'est en somme (sic) l'algorithme de Peano.

Bien joué Pieyre. C'est vrai que c'est un peu long mais tu es le plus rigoureux de nous tous !

OK pour le produit.

Et si on passait à la solution récursive du problème des tours de Hanoï ??

Vous pouvez déjà vous familiariser aux tours en lisant la fin du fil suivant : https://www.zebrascrossing.net/t28020-l-aphantasie

Solution récursive:
Pour un étage: déplacer le disque de la pile 1 à la pile 3.

Pour n étages (n >=2): Reproduire la solution de n-1 étages, mais en mettant cette fois le ou les disques sur la pile 2, mettre le n eme disque sur la pile 3, et reproduire à nouveau la solution de n-1 étages pour mettre les disques de la pile 2 sur la pile 3.

Nombre de déplacements pour n étages: 2k+1, k étant le nombre de déplacements pour n-1 étages (ce qui fait 2^n -1 déplacements).

Ma "solution" récursive aux tours de Hanoï :

Hanoï(n, P1, P2, P3) est le lancement de la fonction et signifie "Empiler correctement n disques de P1 à P3 en s'aidant de P2".
Rem : on prend n disques en partant du plus petit (le plus haut placé donc).

Récurrence :
Hanoï(n, P1, P2, P3) = Hanoï(n-1, P1, P3, P2), Hanoï(1, P1, P2, P3), Hanoï(n-1, P2, P1, P3)

Terminaison :
Hanoï(1, Pi, Pj, Pk) = "Déplacer le disque de Pi à Pk"

Souvent dans les processeurs il y a une fonction "swap" qui permet l'échange entre deux registres. Pas de variable intermédiaire, c'est en dur dans le circuit, et peut-être même simultané.

J'aime beaucoup la notion de "pile" : j'empile des données et je les dépile.

Mais un des gros problèmes en programmation, c'est le scope, la visibilité des variables dans un programme, et comment je les passe aux sous-programmes, avec quelle efficacité ?
Et quel embrouillage de code...

La programmation "virtuelle" je trouve ça trop décalé par rapport aux réalités du terrain, et ne pas prendre en compte la machine c'est s'exposer à de GROS problèmes IRL.

Bonjour !
Je vois ce sujet et cela me rappelle des moments où, pour préparer un concours de programmation, je voyais de la beauté , de l'astuce et des legos s'empiler pour faire un programme fantastique...
Bon, je dois m'y remettre en ce moment et cela ne me déplias pas...

Je viens de voir une chose, avec la fonction somme, définie par récurrence :

def somme(x, y):
  si y = 0:
     donner x
  sinon:
     donner somme(x+1, y-1)

Je me penchais, il y a peu de temps, sur la théorie ZF (qui est, en résumé, une manière d'expliqué TOUTES les mathématique ou presque...) et, entre autre, sur l'addition entre entiers. Et bien, en fait, il définissent la somme pareil ! Alors que c'est un système très formel et que cette définition est accessible à toute personne bien expliquée !

Détails:

Vous connaissez les échecs ?

Le cavalier peut se déplace en décrivant des "L". En gros, quand il est en (x,y), il peut aller en (x+2,y+1),(x+1,y+2),(x-2,y+1), etc...

Etant donné la position de départ (sx,sy) et la position d'arrivée (ex,ey), comment tester si un déplacement du cavalier est valide ?
Comment tester si le cavalier pouvait se déplacer en utilisant au maximum un seul test ?

abs(sx-ex) + abs(sy-ey) = 3

Une version plus compliquée (et intéressante) serait: à partir d'une position P de l'échiquier, comment déterminer si un mouvement du cavalier est valide?
Voilà les règles supplémentaires:
-Il ne doit pas aller sur une case avec une pièce de sa propre couleur.
-Il ne peut pas se déplacer si il met son propre roi en échec (si il est l'unique pièce intercallée entre une tour adverse et son roi par exemple).
-Il ne peut pas se déplacer si son roi est en situation d'échec, sauf si le déplacement en question annule cette situation d'échec (capture de la pièce menaçant le roi, ou positionnement entre cette pièce et le roi).

J'avais fait un petit échiquier complet en java il y a quelques années (j'avais fait la validité des déplacements pour toutes les pièces, le roque, la prise en passant, la promotion du pion, les vérifications de situation de mat, pat...il manquait juste une IA, on ne pouvait jouer qu'à 2 joueurs humains).
Le cavalier est la pièce la plus simple à gérer (pas besoin de vérifier si il y a des obstacles entre la position de départ et celle d'arrivée).