• 
  • A la une du site
  • 100 dernièrs ajouts de fichiers ..
• 
  • Demolist
  • Download
  • Interviews
  • Articles et Dossiers
  • Cheats
  • Gallerie/Musée graphiques
  • Productions CPC+
• 
  • Articles
  • Tests / Gameslist
  • Pokes et Solutions
  • Auteurs
  • Compagnies d'édition
  • Gallerie/Musée graphiques
  • Download
  • Référencement de livres et magazines AMSTRAD CPC
  • Peoples
• 
  • Articles et Chroniques
  • Infos Techniques
  • Crossdev
  • Sources
• 
  • Dépannage
  • Les CPC
  • Les matériel et périphériques
  • Doc's et schémas ...
  • Les montages
  • Service manual
  • Peoples
• 
  • Référencement d'applications AMSTRAD CPC
  • Référencement de livres et magazines AMSTRAD CPC
  • Peoples
• 
  • Download
  • Tools
  • Crossdev
• 

VARIABLES LOCALES ET RECURSIVITE

VARIABLES LOCALES ET RECURSIVITE - PARTIE 2

CPC INFO n°30 Cet article fait suite à celui paru dans CPC Infos de Janvier. Il propose deux exemples d'utilisation de variables locales et de récursivité, programmes à l'appui. Avant de commencer, et en toute généralité, si ia récursion peut être gourmande en mémoire, et si elle n'est pas plus rapide que d'autres méthodes, toutefois elle permet d'écrire des algorithmes relativement compacts et de compréhension aisée. Que ceux qui n'en sont pas convaincus réécrivent les programmes présentés sans. Bon courage ! QUICKSORT En conclusion de l'article précédent était évoqué le tri rapide "Quicksort". C'est un procédé de tri dû à un monsieur C.A.R. Hoare et inventé en 1962. On se demande pourquoi il a fallu attendre tout ce temps pour un truc simple comme bonjour (quoique parfois...), enfin ce doit être le premier Homme à en avoir donné l'algorithme à des fins Informatiques. C'est vraiment très simple : — supposons que le critère de tri soit du genre "Inférieur" ou "supérieur ou égal". On s'y ramène toujours de toutes manières. 1) On met devant soi le tas d'éléments à trier. 2) On pioche un élément. 3) On met à gauche les éléments inférieurs et à droite les éléments supérieurs. 4) On applique ce procédé à chacun des tas ainsi constitués en s'arrêtant naturellement pour un tas lorsqu'il ne contient plus qu'un seul élément ou zéro (mais si, mais si !). Programmé, voici ce que cela donne (une possibilité parmi tant d'autres) : — On indique les bornes de gauche et droite dans le tableau à trier. — On choisit comme élément de partage celui du milieu, que l'on échange avec l'élément de gauche (point 2). — On examine la partie du tableau à trier de droite à gauche. Si un élément est supérieur ou égal à celui de partage, on le laisse en place, sinon on le place sur la gauche du tas à trier, en l'échangeant avec l'élément à l'extrême gauche de ce tas. Il y a là un index utilisé pour connaître l'avancement du tas d'"inférieurs". Dans ce cas on poursuit l'examen à partir de l'élément échangé. — Le tri fini, on rééchange l'élément frontière entre les deux tas de gauche) avec l'élément de partage, qu'on avait placé à gauche (point 3). — On trie le tas de gauche et le tas de droite de la même manière (point 4). Plus un tas est déjà trié, plus on risque d'atteindre vite la limite de la pile BASIC (80 niveaux environ). Pour éviter cela, il suffit de mettre du désordre dans le tableau à trier (qui l'eût cru ?). Par exemple avec une boucle du genre : FOR i=1 to n STEP 2 j=1+INT(RND*n) ùGIVE,5,àa(i),5,àa(j):ùGET,5,àa(i),5,àa(i) NEXT Deux programmes sont proposés, qui sont très semblables. L'un trie des nombres (QUICK-R) et l'autre des chaînes (QUICK-S). Les explications précédentes et les commentaires inclus dans les listings doivent permettre leur compréhension sans tTop de problèmes. A noter l'usage du couple ùGIVE, ÙGET pour l'échange de variables. Pour échanger deux variables, c'est plus élégant qu'économique (en temps), mais au-delà on gagne très vite beaucoup de temps. Ainsi est réalisé dans QUICK-R un rapide transfert de valeurs d'un tableau quelconque au tableau spécifique de la routine de tri. TRI BINAIRE Encore un procédé de tri. Mais autant ne pas voir deux fois la même chose- Revenons sur le Quicksort. ou "rapide tri" en anglais. On l'applique à un ensemble d'éléments, dont on dispose déjà avant de commencer à trier. Seulement bien souvent on a un paquet d'éléments à insérer dans un tas préexistant. Il faut donc faire de l'insertion au coup par coup. Structurer les éléments en un "arbre binaire" est une manière très pratique de réaliser ceci. L'arbre binaire : "Dessine-moi un arbre binaire". "C'est très simple, petit Prince. Prends un crayon et une feuille de papier. Dessine en haut un point, puis deux branches en partant. Et fais de même pour chaque point". Voilà le principe d'un arbre binaire, de manière Imagée. Plus concrètement, les points sont appelés "noeuds". Les 2 noeuds reliés à un même noeud sont appelés noeuds "fils". On parle de noeud fils gauche ou droite selon leur classement (voir plus loi). Un noeud peut n'avoir qu'un fils ou aucun. Un noeud est privilégié par rapport aux autres : c'est le premier, celui par lequel on "entre" dans l'arbre. On l'appelle "racine". Un noeud est une entité complexe. A tout élément trié correspond un noeud. Un noeud est ainsi constitué ; — pointeur sur l'élément ; — compteur d'occurrences de l'élément ; — pointeur sur le fils gauche ; — pointeur sur le fils droit. Qu'est-ce qu'un pointeur ? C'est tout bêtement une adresse. Cela indique à quel endroit chercher ou mettre de l'Information. Ici par exemple le "pointeur de l'élément" est le numéro de l'élément dans le tableau des éléments ("mottab" ou "xtab" dans les programmes). Les pointeurs sur les fils sont simplement les numéros des noeuds fils dans le tableau des noeuds. Comment ciasse-t-on dans un arbre (si vous ne l'avez déjà deviné) ? Enfantin ! On se ramène avec l'élément à insérer à la racine. De là c'est toujours le même processus ; 1 ) Si le noeud est vide, c'est-à-dire ne pointe sur aucun élément, alors on lui attribue le nouvel élément et on met le compteur d'occurrences à 1. C'est fini ici. 2) Si l'élément est égal à celui du noeud, alors on incrémente le compteur d'occurrences et c'est fini ici. 3) Si l'élément est Inférieur à celui du noeud, alors on se déplace au fils de gauche et on reprend en 1 ). 4) Sinon c'est qu'il est supérieur et alors on se déplace au fils droit. On reprend en 1). L'insertion se fait donc très simplement. On obtient en fin de compte un arbre avec l'élément le plus petit le plus à gauche (on prend toujours à gauche mais là on ne tourne pas en rond) et le plus grand le plus à droite. Mais comment débrouiller le méli-mélo entre les deux ? L'enfance de l'art, grâce encore une fois à la récursi-vité. On considère la procédure "afficher noeud". Voilà comment elle se décompose ; 1) Si noeud vide, alors retour de procédure. 2) 'afficher fils de gauche". 3) Faire apparaître à l'écran ce qui nous intéresse sur le noeud. Souvent II s'agit de l'élément pointé et de son nombre d'occurrences. 4) "afficher fils de droite". 5) Retour de procédure. Cela semble magique, mais pour parodier une célèbre citation : "et pourtant ça marche". On voit défiler à l'écran en un temps record tous les éléments triés. Comme pour Quicksort, des éléments arrivant déjà ordonnés conduisent à un déséquilibre de l'arbre et on a vite fait d'arriver à une saturation de la pile BASIC. Pour des éléments venant au hasard par contre, on a beaucoup plus de chances d'aboutir d'abord à un manque de place pour les tableaux de données. Encore une fois les deux programmes proposés sont très proches : l'un trie des réels (SHELL-R) et l'autre des chaînes numériques (SHELL-S). Dans ce dernier cas un fichier ASCII préexistant est lu. Comme souvent il s'agit d'un fichier de texte, on lit des lignes entières à chaque "INPUT". Aussi chaque "ligne" est-elle retravaillée pour supprimer les espaces superflus et en extraire ensuite aisément le contenu. On peut plus facilement taper une série de mots lus par un INPUT, que l'on envole à chaque fois pour insertion dans l'arbre (c'est toute l'utilité de la chose ! Et cela va très vite, c'est du temps réel). En sauvegardant en même temps les mots d'un fichier, on peut faire ultérieurement l'économie d'une nouvelle entrée de données. Si on veut épater la galerie, on peut même en rajouter soi-même, soit par programme, soit carrément "à Iq main", en mGI-Vant* la racine et en appelant la procédure d'Insertion. Au possesseur de 464 : la fonction DEC$ est buggée sur le 464, mais on peut l'utiliser en ouvrant 2 parenthèses et en n'en fermant qu'une : "DEC$((...)". Elle est utilisée dans l'affichage de l'arbre. CONCLUSION Maintenant il n'y a plus qu'à espérer que quelque lecteur soit Inspiré et nous offre bientôt dans ces colonnes un programme dans ce bon vieux BASIC du CPC (gonflé des RSX que vous savez), qu'on n'aurait pas pu écrire sans la récurslon (ou pas sans ENORMES difficultés). Je souhaite y avoir donné goût (je trouve très agréable le côté naturel des algorithmes et les deux exemples traités doivent le mettre en valeur, sinon tant pis... y'a plus rien à faire). NOTE : Pour utiliser les programmes ci-dessous, il faut bien sûr avoir initialisé les RSX auparavant. Reportez-vous au numéro 28 de CPC Infos pour cela. CPCINFOS n°28/n°30

CPCrulez[Content Management System] v8.7-desktop Page créée en 049 millisecondes et consultée 2879 fois L'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent  du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko.