Notes Annuelles & Recours

Priere de verifier vos notes. Elles sont consultables

 ⇓

ICI

Puis, en cas d'erreur, priere de bien vouloir remplir la fiche de recours

 ⇓

ICI

Notes STM Gr B1

La consultation des copies est prévue pour dimanche à 9:30.

Notes de PSD de B1

TP 12, codes sources

• Programme 1: Création

#include <stdio.h>
#include <stdlib.h>
typedef struct {int jour,mois,annee;} tDate;
typedef struct {char nom[20],prenom[20],poste[20]; tDate date; } tEmploye;
typedef struct {char poste[20]; float salaire; } tPoste;
int getFichEmploye(char *);
int main(){
    getFichEmploye("listEmploye.txt");
    return 0;
}
int getFichEmploye(char *nomFichier){
   FILE *ptFichier;
   tEmploye employe;
   int  comp,nbrEmploye;

   printf("Donner le nbr d'employes : ");
   scanf("%d",&nbrEmploye);
   ptFichier=fopen(nomFichier,"wt");
   if(!ptFichier){printf("\n La creation de fichier a echouee!");return 1;}
   for(comp=0;comp<nbrEmploye;comp++){
      printf("Entrez le nom de la personne N%d: ",comp+1);
      scanf("%s", employe.nom); // sans espaces
      fprintf(ptFichier, "%s\t", employe.nom);
      printf("Entrez le prenom de %s : ",employe.nom);
      scanf("%s", employe.prenom);
      fprintf(ptFichier, "%s\t",employe.prenom);
      printf("Donner le poste de %s %s:",employe.nom,employe.prenom);
      scanf("%s",employe.poste);
      fprintf(ptFichier, "%s\t",employe.poste);
      printf("Donner la date de recrut de %s %s (jj/mm/yyyy):",employe.nom,employe.prenom);
      scanf("%d/%d/%d",&(employe.date.jour),&(employe.date.mois),&(employe.date.annee));
      fprintf(ptFichier, "%d/%d/%d\n",employe.date.jour,employe.date.mois,employe.date.annee);
    }
    fclose(ptFichier);
    return 0;
}

• Programme 2: Lecture

#include <stdio.h>
#include <stdlib.h>
typedef struct {int jour,mois,annee;} tDate;
typedef struct {char nom[20],prenom[20],poste[20];tDate date;} tEmploye;
int affichListEmploye(char *);
int main(){
    affichListEmploye("listEmploye.txt");//ajouter le chemin    
    return 0;
}
int affichListEmploye(char *fichEmploye)
{
    FILE *ptFichEmploye;
    tEmploye employe={"","","",{0,0,0}};int i=1;

    ptFichEmploye = fopen(fichEmploye,"rt");
    if(!ptFichEmploye){
        printf("Impossible d'ouvrir le ficher %s, arret d'execution",fichEmploye);
        return 1;
    }
    while(!feof(ptFichEmploye)){ //on suppose le fichier non vide
        fscanf(ptFichEmploye,"%s\t",employe.nom);
        fscanf(ptFichEmploye,"%s\t",employe.prenom);
        fscanf(ptFichEmploye,"%s\t",employe.poste);
        fscanf(ptFichEmploye,"%d/%d/%d\n",&(employe.date.jour),&(employe.date.mois),&(employe.date.annee));
        printf("\nNom%3d:%s\tPrenom:%s\tPoste:%s",i++, employe.nom,employe.prenom,employe.poste);
        printf("\tdate recrut:%d/%d/%d",employe.date.jour,employe.date.mois,employe.date.annee);
    }
    fclose(ptFichEmploye);
    return 0;
}

• Remarks/Further reading

1. Ajouter le chemin du fichier listEmploye.txt en lecture:

• Sous linux: affichListEmploye("/votre/chemin/listEmploye.txt");

• Sous Windows : dans le chemin, ne pas oublier de doubler les \

2. Resolution du pb de fichier existant mais vide: On remplace les lignes 20 à 27 par:
while(1){
        fscanf(ptFichEmploye,"%s\t",employe.nom);
        if(feof(ptFichEmploye)){printf("\n fichier vide, arret d'execution"); fclose(ptFichEmploye);return 1;}
        fscanf(ptFichEmploye,"%s\t",employe.prenom);
        fscanf(ptFichEmploye,"%s\t",employe.poste);
        fscanf(ptFichEmploye,"%d/%d/%d\n",&(employe.date.jour),&(employe.date.mois), &(employe.date.annee));
        printf("\nNom%3d:%s\tPrenom:%s\tPoste:%s",i++, employe.nom,employe.prenom,employe.poste);
        printf("\tdate recrut:%d/%d/%d",employe.date.jour,employe.date.mois,employe.date.annee);
    }
3. EOF bien expliqué:
https://latedev.wordpress.com/2012/12/04/all-about-eof/
4. Gestion de repertoires en C (hors programme MI)
http://www.thegeekstuff.com/2012/06/c-directory/

TP11 codes sources

Programme 1:
#include <stdio.h>
#include <stdlib.h>

typedef struct {int x;int y;}tPoint;

tPoint p1,p2={0,300},p3;

int main(){
  p1.x=150;
  p1.y=103;
  printf("Les coordonnees du point p1 sont (%d,%d)\n",p1.x,p1.y);
  printf("Les coordonnees du point p2 sont (%d,%d)\n",p2.x,p2.y);
  printf("Saisir les coordonnees du point p3\n");
  scanf("%d %d",&(p3.x),&(p3.y));
  printf("Les coordonnees du point p3 sont donc (%d,%d)\n",p3.x,p3.y);
  return 0;
}
Programme 2:
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int jour;
    int mois;
    int annee;
    }tDate;
typedef struct {
    int id;
    char nom[21];
    tDate ddn;
    float note[3];
    float moy;
    }tEtudiant;
tEtudiant student;

void getInfoEtudiant(tEtudiant *etudiant);
void affichInfoEtudiant(tEtudiant etudiant);

int main(){
  getInfoEtudiant(&student);
  affichInfoEtudiant(student);
  //getListEtudiant()
  //affichListEtudiant()
  //getInfoEtudFromList()
  //bestStudent()
  return 0;
}
void getInfoEtudiant(tEtudiant *etudiant){
   int i;
   printf("\nIdentifiant:");
   scanf("%d",&(*etudiant).id);
   printf("Nom:");
   scanf("%s",(*etudiant).nom);
   printf("jour de naissance:");
   scanf("%d",&(*etudiant).ddn.jour);
   printf("mois de naissance:");
   scanf("%d",&(*etudiant).ddn.mois);
   printf("annee de naissance:");
   scanf("%d",&(*etudiant).ddn.annee);
   (*etudiant).moy=0;
   for(i=0;i<3;i++){
      printf("Note%d:",i+1);
      scanf("%f",&((*etudiant).note[i]));
      (*etudiant).moy+=(*etudiant).note[i]/3;
   }
}
void affichInfoEtudiant(tEtudiant etudiant){
   int i;
   printf("\nIdentifiant:%d",etudiant.id);
   printf("\nNom:%s",etudiant.nom);
   printf("\njour de naissance:%d",etudiant.ddn.jour);
   printf("\nmois de naissance:%d",etudiant.ddn.mois);
   printf("\nannee de naissance:%d",etudiant.ddn.annee);
   for(i=0;i<3;i++){
      printf("\nNote%d:%.2f",i+1,(etudiant.note[i]));
   }
   printf("\nMoyenne:%.2f",etudiant.moy);
}
Programme 3:
#include <stdio.h>
#include <stdlib.h>
/*variante1:declaration de structure seulement (ajouter / au debut pour de-commenter)
struct tPoint{int x;int y;}; //
//puis instanciation
struct tPoint p1,p2={0,300},p3; //Enlever struct genere une erreur en C
//*/
/*variante2:declaration de structure et en meme temps instanciation de p1 et p2 (idem)
struct tPoint{int x;int y;} p1,p2={0,300};
//puis instanciation de p3
struct tPoint p3;
//*/
/*variante3:declaration de structure anonyme et en meme temps instanciation des point (idem)
struct {int x;int y;} p1,p2={0,300},p3;
//*/
/*variante4:declaration en associant un nom de type a une structure non anonyme (idem)
typedef struct stPoint{int x;int y;}tPoint;
//puis instanciation avec 2 possibilites
tPoint p1,p2={0,300}; //on n'a pas besoin de struct car tpoint est un alias de struct stPoint
struct stPoint p3;    //ici on en a
//*/
//Je vous conseille de maitriser au moin cette derniere version
//*variante5:declaration en associant un nom de type a une structure anonyme (enlever / au debut pour commenter)
typedef struct {int x;int y;}tPoint;
//puis instanciation
tPoint p1,p2={0,300},p3;
//*/
int main(){
  p1.x=150;p1.y=103;
  printf("Les coordonnees du point p1 sont (%d,%d)\n",p1.x,p1.y);
  printf("Les coordonnees du point p2 sont (%d,%d)\n",p2.x,p2.y);
  printf("Saisir les coordonnees du point p3\n");
  scanf("%d %d",&(p3.x),&(p3.y));
  printf("Les coordonnees du point p3 sont donc (%d,%d)\n",p3.x,p3.y);
  return 0;
}
Programme 4:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct {
       char titre_livre[16];
       char auteur[16];
       char editeur[16];
       int annee;
       int nbr_page;
       } tRef;

tRef listRef[50];

void remplir(int n,tRef listRef[50]),
    affiche(int n,tRef listRef[50]),
    triRef(int n,tRef listRef[n],int  choix);

int main(){
        int n,choix;
        printf("Donnez le nombre de references biblio <50");
        scanf("%d",&n);
        remplir(n,listRef);
        affiche(n,listRef);
        do{
           printf("\nEntrer : \n 1 pour le tri par titre"
                  "\n 2 pour le tri par auteur"
                  "\n 3 pour le tri par editeur"
                  "\n 4 pour le tri par annee"
                  "\n 5 pour le tri par nbr de page "
                  "\n 6 quitter "
                  "\n votre choix --------------------------->");
           scanf("%d",&choix);
           if(choix!=6){
                triRef(n,listRef,choix);
                affiche(n,listRef);
           }
        }while(choix!=6);

        return 0;
}

void remplir(int n,tRef listRef[50]){
          int i;
          printf("\n Introduire des chaines de caracteres <15 et sans espace \n");
          for(i=0;i<n;i++){
          printf("Donnez le titre N°%d:",i+1);
          scanf("%s",listRef[i].titre_livre);
          printf("donnez le nom de l'auteur ");
          scanf("%s",listRef[i].auteur);
          printf("donnez le nom de l'editeur ");
          scanf("%s",listRef[i].editeur);
          printf("donnez l'annee de publication ");
          scanf("%d",&(listRef[i].annee));
          printf("donnez le nbr de page ");
          scanf("%d",&(listRef[i].nbr_page));
          }
}

void affiche(int n, tRef listRef[50]){
        int i;
        printf("\n____________________________________________________________________");
        printf("\n|Titre          |Auteur         |Editeur        |Annee  |Nbr pages |");
        printf("\n--------------------------------------------------------------------");
        for(i=0;i<n;i++){
          printf("\n|%15s|",listRef[i].titre_livre);
          printf("%15s|",listRef[i].auteur);
          printf("%15s|",listRef[i].editeur);
          printf("%5d  |",listRef[i].annee);
          printf("%6d    |",listRef[i].nbr_page);
        }
         printf("\n--------------------------------------------------------------------");
}

void triRef(int n,tRef listRef[50],int choix){
    int i,j;
    tRef tmp;

        switch (choix){
            case 1:
                for(i=0;i<n-1;i++){
                    for(j=i+1;j<n;j++){
                        if(strcmp(listRef[i].titre_livre,listRef[j].titre_livre)>0){
                                tmp=listRef[i];listRef[i]=listRef[j];listRef[j]=tmp;
                        }
                    }
                }
            break;
            case 2:
                for(i=0;i<n-1;i++){
                    for(j=i+1;j<n;j++){
                        if(strcmp(listRef[i].auteur,listRef[j].auteur)>0){
                            tmp=listRef[i];listRef[i]=listRef[j];listRef[j]=tmp;
                        }
                    }
                }
            break;
            case 3:
                for(i=0;i<n-1;i++){
                    for(j=i+1;j<n;j++){
                        if(strcmp(listRef[i].editeur,listRef[j].editeur)>0){
                            tmp=listRef[i];listRef[i]=listRef[j];listRef[j]=tmp;
                        }
                    }
                }
            break;
            case 4:
                for(i=0;i<n-1;i++){
                    for(j=i+1;j<n;j++){
                        if (listRef[i].annee>listRef[j].annee){
                            tmp=listRef[i];listRef[i]=listRef[j];listRef[j]=tmp;
                        }
                    }
                }
          break;
          case 5:
            for(i=0;i<n-1;i++){
                    for(j=i+1;j<n;j++){
                        if(listRef[i].nbr_page>listRef[j].nbr_page){
                            tmp=listRef[i];listRef[i]=listRef[j];listRef[j]=tmp;
                        }
                    }
                }
          break;
          default:printf("le choix n'est pas valide");
        }
}


Une autre version de triRef a verifier.

void permutRef(tRef *ref1,tRef *ref2){
  tRef tmpRef;
  tmpRef=*ref1;*ref1=*ref2;*ref2=tmpRef;
}
void triRefV2(int n,tRef listRef[50],int choix){
    int i,j;
    if((choix>5)||(choix<1)){printf("le choix n'est pas valide");}
    else{
    for(i=0;i<n-1;i++){
        for(j=i+1;j<n;j++){
            switch (choix){
               case 1:
                  if(strcmp(listRef[i].titre_livre,listRef[j].titre_livre)>0){permutRef(&listRef[i],&listRef[j]);}

               break;
               case 2:
                  if(strcmp(listRef[i].auteur,listRef[j].auteur)>0){permutRef(&listRef[i],&listRef[j]);}
               break;
               case 3:
                 if(strcmp(listRef[i].editeur,listRef[j].editeur)>0){permutRef(&listRef[i],&listRef[j]);}
               break;
               case 4:
                 if (listRef[i].annee>listRef[j].annee){permutRef(&listRef[i],&listRef[j]);}
               break;
               case 5:
                 if(listRef[i].nbr_page>listRef[j].nbr_page){permutRef(&listRef[i],&listRef[j]);}
           }
        }
    }
    }
}

L'exercice de l'ecart entre deux dates

// *********************************************//
// La reutilisation de ce code est autorisée         //
// pour des fins pédagogiques non lucratives     //
// a condition de citer la ref :                                //
// (c) BouMen-Université de Boumerdes           //
// http://algocri18.blogspot.com                        //
// *********************************************//
#include <stdio.h>
#include <stdlib.h>
typedef struct {int jour,mois,annee;} tDate;

tDate nextDate(tDate);
void permutDate(tDate *date1, tDate *date2);
void affichDate(tDate date);
int date1AvtDate2(tDate date1,tDate date2);
int isBissextile(int annee);
int isDateValide(tDate date);

tDate date1,date2;

int main(){
    tDate tmpDate;int ecart=0;
    printf("Donner deux dates valides jj/mm/aaaa!\n");
    do{
       printf("Premiere date:");
    }while((scanf("%d/%d/%d",&date1.jour,&date1.mois,&date1.annee)!=3)||!isDateValide(date1));
    printf("  Ok\n");
    do{
       printf("\nDeuxieme date:");
    }while((scanf("%d/%d/%d",&date2.jour,&date2.mois,&date2.annee)!=3)||!isDateValide(date2));

    if(date1AvtDate2(date2,date1))permutDate(&date1,&date2);
    //methode efficace (chirurgicale)
    int vNbrJourMois[12]={31,28,31,30,31,30,31,31,30,31,30,31};
    int mois,annee;
    ecart+=vNbrJourMois[date1.mois-1]-date1.jour;
    for(mois=date1.mois+1;mois<=12;mois++)ecart+=vNbrJourMois[mois-1];
    ecart+=365*(date2.annee-date1.annee-1);
    for(mois=1;mois<date2.mois;mois++)ecart+=vNbrJourMois[mois-1];
    ecart+=date2.jour;
    for(annee=date1.annee+1;annee<date2.annee;annee++)if(isBissextile(annee))ecart++;

    printf("\nEcart 1:%d",ecart);

    //une autre méthode
    //int hejir=0; //en plus pour calculer l'age avec calend hejirien
    for(ecart=0,tmpDate=date1;date1AvtDate2(tmpDate,date2);ecart++,tmpDate=nextDate(tmpDate)){
       /*if(ecart%355==0){
         affichDate(tmpDate);
         printf("\t Hejir:%d",++hejir);
       }//sulp ne*/
    }


    printf("\nEcart 2:%d",ecart);
    return 0;
}

int isDateValide(tDate date)
{
    if((date.jour>31)||(date.jour<1)||(date.mois>12)||(date.mois<1)||(date.annee<1)) return 0;
    switch(date.mois)
    {
        case 4 :
        case 6 :
        case 9 :
        case 11 :if(date.jour>30) return 0; break;
        case 2 : if(date.jour>29)return 0;
                 if(!isBissextile(date.annee)&&(date.jour==29)) return 0;

    }
    return 1;
}

int isBissextile(int annee){
   return (((annee%4==0)&&(annee%100!=0))||(annee%400==0))?1:0;
}

tDate nextDate(tDate date){
  tDate dateSuiv=date;

  if((date.mois==2) && (date.jour==28)){
     if (isBissextile(date.annee)){dateSuiv.jour=29;dateSuiv.mois=2;}
     else {dateSuiv.jour=1;dateSuiv.mois=3;}
  }else if(((date.jour==30)&&((date.mois==4)||
                         (date.mois==6)||
                         (date.mois==9)||
                         (date.mois==11)))
        ||((date.jour==31)&&((date.mois==1)||
                         (date.mois==3)||
                         (date.mois==5)||
                         (date.mois==7)||
                         (date.mois==8)||
                         (date.mois==10)||
                         (date.mois==12)))||
        ((date.jour==29)&&(date.mois==2))){
        dateSuiv.jour=1;
        dateSuiv.mois++;
        if(date.mois==12){dateSuiv.annee++;dateSuiv.mois=1;}
     }else{
        dateSuiv.jour++;
  }
  return dateSuiv;
}
void permutDate(tDate *date1, tDate *date2){
   tDate tmpDate=*date1;*date1=*date2;*date2=tmpDate;
}
void affichDate(tDate date){
  printf("\ndate:%d/%d/%d",date.jour,date.mois,date.annee);
}
int date1AvtDate2(tDate date1,tDate date2){
   if(
        (date1.annee<date2.annee)||
        ((date1.annee==date2.annee)&&(date1.mois<date2.mois))||
        ((date1.annee==date2.annee)&&(date1.mois==date2.mois)&&(date1.jour<date2.jour))
    )return 1;
    else return 0;
}

Questions:
1. La méthode 1 marche t elle si les deux dates sont issues de la meme annee? Pourquoi?
2. Un peu de complexite (hors programme, mais essayer de reflechir quand meme): Quelle est la méthode la plus efficace (rapide)?
3. Si pour deux dates données, les deux ecarts sont différents faites le moi savoir please.

Enregistrement et act param, l'exemple du cours promis

fonction quotient ... a definir (exercice)
fonction modulo ... a definir (exercice)
 
fonction nbSec(E/ time : tHms) : entier ;
Debut    
   retourner (time.heure* 3600) + (time.minute * 60) + time.seconde ; 
Fin ;
 
fonction converthms(E/ nbSec :entier) : tHms ;
Var time : tHms ; reste:entier ;
Debut
    time.heure  ← quotient(nbSec,3600) ; // car slash division ent et div non def
    reste  ←  modulo(nbSec,3600) ;            // car mod non def
    time.minute  ← quotient(reste,60) ;
    time.seconde  ← modulo(nbSec,60) ;
    retourner time ;
Fin ;

Algorithme exCours ;
Type
    tHms=enregistrement heure,minute,seconde : entier ; Fin ;
Var
    dureeSec : entier ;
    dureeH : tHms ;
    mySwitch :bool;
Debut
    lire(mySwitch) ;
    si mySwitch alors  
        lire(dureeSec) ;
        dureeH  ←  converthms(dureeSec) ;
        ecrire(dureeH.heure,dureeH.minute,dureeH.seconde) ; //oui ; avant sinon
    sinon                                                                                                 //car fsi délimite
        lire(dureeH.heure,dureeH.minute,dureeH.seconde) ;     //si always
        ecrire(nbSec(dureeH)) ;
    fsi ;
Fin.

TP10, codes sources

Prg1:
#include <stdio.h>
#include <stdlib.h>

int multIter(int x,int y)
{
   int prod=0;
   for(;y>0;y--)prod+=x;
   return prod;
}
int multRec(int x,int y)
{
   if(y==0) return 0;       //critere d'arret
   return x+multRec(x,y-1); //sinon recursion
}
int main()
{
    int a=11,b=3; //par exemple
    char tmp;
    printf("\nCode Iteratif: %d x %d = %d",a,b,multIter(a,b));
    printf("\nTapez Entree SVP");scanf("%c",&tmp);
    printf("\nCode Recursif: %d x %d = %d\n",a,b,multRec(a,b));
    return 0;
}

Prg2: 
#include <stdio.h>
#include <stdlib.h>
unsigned int nbrDisq;
void Hanoi(unsigned n, char x, char y,char z,unsigned matSocles[][3]),
     deplacer (char x,char y, unsigned matSocles[][3]),
     initMatSocles(unsigned matSocles[][3],unsigned nbrDisq),
     modifMatSocles(char x,char y,unsigned matSocles[][3],unsigned nbrDisq),
     affichMat(unsigned mat[][3],unsigned,unsigned);
int main()
{
    printf("NbrDisques :");
    scanf("%u",&nbrDisq);
    unsigned matSocles[nbrDisq][3];
    initMatSocles(matSocles,nbrDisq);
    Hanoi(nbrDisq,'A','B','C',matSocles);
    return 0;
}

void deplacer (char x, char y, unsigned matSocles[][3])
{
    static unsigned mouvNbr=1;
    printf("\n Mouvement %u : Deplacer un disque du socle %c vers le socle %c \n",mouvNbr++,x,y);
    modifMatSocles(x,y,matSocles,nbrDisq);
    affichMat(matSocles,nbrDisq,3);
}
void Hanoi(unsigned n,char x,char y,char z,unsigned matSocles[][3])
{
    if (n>0){
        Hanoi(n-1,x,z,y,matSocles);
        deplacer(x,y,matSocles);
        Hanoi(n-1,z,y,x,matSocles);
    }
}
void initMatSocles(unsigned matSocles[][3],unsigned nbrDisq)
{
   unsigned i;
   for(i=0;i<nbrDisq;i++)matSocles[i][0]=i+1;
   for(i=0;i<nbrDisq;i++){matSocles[i][1]=0;matSocles[i][2]=0;}
   affichMat(matSocles,nbrDisq,3);
}

void modifMatSocles(char x,char y,unsigned matSocles[][3],unsigned nbrDisq)
{
   unsigned i1,i2;


   for(i1=0;(i1<nbrDisq)&&(matSocles[i1][x-65]==0);i1++){} //recherche du sommet du socle de depart

   for(i2=0;(i2<nbrDisq)&&(matSocles[i2][y-65]==0);i2++){} //recherche du sommet d'arrivee


   //transfert du disque
   matSocles[i2-1][y-65]=matSocles[i1][x-65];//ajout dans l'arrivee
   matSocles[i1][x-65]=0;//suppression dans le depart
}
 void affichMat(unsigned mat[][3],unsigned n,unsigned m)
 {
    unsigned i,j;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++)printf("%4d",mat[i][j]);
        printf("\n");
    }
 }

Récursivité : Analyse recursive

Pour résoudre un problème de manière récursive, on réalise une anlyse recursive.

Etape 1, Recherche d'un cas trivial : celui qui peut être résolu sans appel récursif (le critère d’arrêt) ; 

Étape 2, Paramétrage du problème : déterminer les paramètres en particulier la taille qui doit décroître a chaque appel récursif (converger vers le cas trivial);

Étape 3, Décomposition du cas général : ramener la résolution du problème a la résolution d'un ou de plusieurs problèmes de même nature et de taille plus petite (la partie récursive);

 

Exemple : Tour de Hanoї [Lucas 1883]:

Problème : 64 disques étant posés les uns sur les autres par ordre de taille décroissant sur un socle A, les transférer sur un socle B en utilisant un socle C en ne prenant qu'un disque a la fois pour le déposer sur un disque plus grand.

Réponse :

1. Analyse recursive

Étape 1 : avoir un seul disque (i.e. n=1) est un cas trivial car il suffit de le déplacer directement depuis le socle de départ vers le socle d’arrivée. D’où le critère d’arrêt :

si n=1 alors déplacer un disque du socle A vers le socle B

Étape 2 : n est le nombre de disques, socle de départ, socle d’arrivée et socle intermédiaire sont les paramètres. D’où : Action Hanoi(E/ n : entier ; E/ depart,arrivee,intermed : socle ) ;

Étapes 3 : Un socle contenant un disque plus grand que tous les autres est assimilable pour le transfert de ceux ci a une position vide. D’où la décomposition :

n disques peuvent être transférés de A vers B en :

• transférant n-1 disques de A vers C en utilisant B comme intermédiaire;
• déplacer le disque restant de A vers B ;
• transférant les n-1 disques de C vers B en utilisant A comme intermédiaire.

2. Algorithme

Action deplacer (E/x,y:caractere);

debut 

       ecrire('Deplacer un disque du socle',x,'vers le socle',y);

fin ;

Action Hanoi(E/ n:entier ; E/ x,y,z : caractere) ;

debut

    si n=1 alors

        deplacer(x,y) ;

    sinon

        Hanoi(n-1,x,z,y) ;

        deplacer(x,y) ;

        Hanoi(n-1,z,y,x) ;

    fsi ;

fin ;

Algorithme TourHanoi ;

debut

    Hanoi(64,'A','B','C') ;

fin.

3. En résumé [fom Wikipedia]:

« The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. »  Niklaus Wirth, Algorithms + Data Structures = Programs.

«  La puissance de la récursivité réside évidemment dans la possibilité de définir des ensembles infinis d'objets par une affirmation finie. De façon similaire, un nombre infini d'étapes de calcul peut être décrit par un programme récursif fini, même si ce programme ne contient aucune répétition explicite. »

Bibliography and/or further reading:

1. Meyer B. et Baudoin C., Méthodes de programmation. Eyrolles 1984.

2. http://en.wikipedia.org/wiki/Tower_of_Hanoi

3. http://www.fil.univ-lille1.fr/~sedoglav/C/main019.html

Récursivité : Principe général

1. Squelette d'une action paramétrée récursive

 2. Mécanisme

Une vidéo décrivant le principe réalisée par un étudiant (que je remercie vivement) :

Construction d'une unité centrale simple

L'organisation matérielle des ordinateurs usuels suit l'architecture dite de Von Neumann (de Zuse ? Non pas de politique). Dans celle-ci :

• La RAM sert a stocker les données et les programmes ;
• Une unité de commande donne les ordres et synchronise l’exécution des opérations dans l’unité de traitement du processeur central.

Exemple :

Bibliography and/or further reading

1. Introduction a l'informatique. Tellier I. (http ://www.grappa.univ-lille3.fr/∼tellier/enseignement.html)

2. https://fr.wikipedia.org/wiki/Architecture_Harvard

3. http://fr.wikipedia.org/wiki/Discussion:Konrad_Zuse

4. http://en.wikipedia.org/wiki/Konrad_Zuse

Notes algo Gr B1

Les notes rectifiées : 

matricule	c_continue	examen
X150638	18.5	18.5
161631052224	0	abs
171731046847	0	abs
171731035983	9.5	0.5
171731058380	9.75	3.75
X150230	14.5	6.5
171731030205	5	0.25
161631096115	8.5	3.5
171731034317	9	3
171731028261	11.5	2.5
171731041918	0	abs
161631063017	17.5	15
161631064097	0	abs
171731106639	16.5	14.5
161631032758	5.75	5
161631035274	0	abs
171731099737	11.25	4.5
171731058479	6.5	0.5
171731053109	3.5	abs
171731036892	1.25	0.5
161631058906	0	abs
171731037280	5.5	0.5
X150565	12	6.5
171731068866	6.25	0.5
171731037856	7.5	0.5
161631114806	16.25	3.5
161631062749	13.25	11.5
161631038289	0	abs
171731033535	9.25	3.5
011731053210	13	11
161631110065	15	9
171731057429	8.5	7
171731058199	10.75	10
171731041374	18.75	15