Algorithmique & Codage et Representation de l'information 2016/2017: March 2017

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]);}
           }
        }
    }
    }
}

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