TPINFO

7/21/2019 TPINFO

http://slidepdf.com/reader/full/tpinfo 1/63

MEA 3

TP/TD de Programmation C

2015-2016

7/21/2019 TPINFO


Sommaire

ENVIRONNEMENT DE PROGRAMMATION VISUAL STUDIO2

TP 1 : INITIATION AU LANGAGE C 7

TP 2 : STRUCTURES DE CONTRÔLE 11

TP 3 : TABLEAUX A UNE DIMENSION 12

TP : ALGORIT!ME DU PLUS COURT C!EMIN "LEE# 13

TP $ : VARIABLES ET %ONCTIONS 1$

TP & : STRUCTURES ET %IC!IERS 17

TP 7 : STRUCTURES DE DONNEES 1'

TP ( : RECURSION 2)

TP ' : LISTE C!AINEES 21

TP COMPLEMENTAIRES 22

EXERCICES COMPLEMENTAIRES 27

ANNEXE : INTRODUCTION AU S*STEME +INDO+S,MS-DOS &

7/21/2019 TPINFO


E./iro..eme.0 e roramma0io. Visual Studio

A) Création d’un projet

1. Ouvrir le logiciel Microsoft Visual Studio 200

Menu Démarrer / Tous les Programmes /MEA/Microsoft Visual Studio 2005

2. Création du projet

Menu Fichier / Noueau / Pro!et

Dans la fenêtre qui s’ouvre « Nouveau Projet », développer l’arborescence Visual C en cliquant sur la croi!" #électionner $in%&, puis dans la fenêtre de droite c'oisir « (pplication Console $in%& »")ntrer le no* de votre projet +par e!e*ple ici, Premier Pro!et " C'oisir é-ale*ent la localisation de l’enre-istre*ent devotre projet +nous vous conseillons de tout enre-istrer dans votre répertoire personnel, sur le disque réseau" Cliquer sur "# "

!. Con"guration du projet

C'oisir l’on-let Param$tres de l%a&&licatio' dans l’outil de confi-uration de l’application $in%&"C'oisir le para*.tre une application de t/pe (o'sole, et coc'er la case Pro!et Vide dans les options additionnelles" Cliquer ensuite sur Termi'e r "0e projet est *aintenant confi-urer pour pro-ra**er en C 1 cette procédure devra être ri-oureuse*ent reproduite pour toutnouveau projet"

#. Création $ Ajout de "c%ier&s) source&s)

Nous allons *aintenant rajouter un fic'ier source 2 notre projet"3aire un clic droit sur Sources, c'oisir A!outer , A!outer u' 'ouel éléme't "(ppu/er sur la croi! pour développer l’arborescence Visual C"

#électionner l’ic4ne Fichier ()) et donner un no* 2 votre fic'ier +par e!e*ple Premier Programme ainsi que lalocalisation de ce fic'ier sur le disque dur +par défaut, il indique le répertoire correspondant 2 votre projet, nous vousconseillons de conserver ce para*.tre" Pour ter*iner, cliquer sur A!outer "

. 'dition du progra((e

0e pro-ra**e ouvert est vide, et vous deve5 alors saisir dans la fenêtre d’édition votre pro-ra**e" 6ci par e!e*ple, nousallons faire un pro-ra**e qui réalise l’addition de deu! no*bres entiers"

Exercice : Recopiez pour commencer les quelques lignes de C qui suivent :

void main (void){

int a=2;int b=6int c=0;

c=a+b;}

Ca y est ! Vous avez écrit votre premier programme.

Pour ter*iner, sauve-arder votre travail 1

Menu Fichier , Sauegarder Premier Programme*c&&

%

7/21/2019 TPINFO


) Co(pilation et e*écution d’un progra((e

Pour être e!écuté par votre ordinateur, le pro-ra**e doit être traduit en lan-a-e *ac'ine 1 c’est le lan-a-e que co*prend le*icroprocesseur" C’est le co*pilateur qui est c'ar-é de cette t7c'e" #on r4le est tout d’abord de vérifier la bonne écriture devotre pro-ra**e +anal/se s/nta!ique puis de le traduire en lan-a-e *ac'ine"

+. Co(pilation du ,rogra((e

Menu +uild , puis lancer la co**ande (om&ile +ou Ctrl 38

#i votre pro-ra**e est écrit correcte*ent +c9est:2:dire, suivant les r.-les du lan-a-e C, le co*pilateur vous indique que lat7c'e de co*pilation n’a pas provoqué d’erreurs +fenêtre du bas"#i vous re*arque5 des erreurs, appu/e5 sur 3; et corri-e5 les"

-. 'dition des iens

Menu +uild , puis lancer la co**ande +uild Solutio' +ou 38

<ne fois que le pro-ra**e ne co*porte plus d’erreur, il est nécessaire d’effectuer ce qu’on appelle l’édition des liens" )neffet, les pro-ra**es en C utilisent -énérale*ent des bibliot'.ques de fonctions prédéfinies et préco*pilées +par e!e*ple, la

bibliot'.que stdio.h contient la fonction printf()" 0ors de la p'ase d’édition des liens, le co*pilateur va ajouter lecode objet correspondant 2 cette fonction printf() au code -énéré lors de la p'ase précédente" Cette p'ase peut é-ale*ent-énérer des erreurs si les correspondances entre les librairies et les fonctions utilisées sont incorrectes"

/. '*écution du progra((e

Menu De,ug , puis lancer la co**ande Start -ithout De,uggi'g +ou C=>03?

#i tout est écrit correcte*ent, le co*pilateur -én.re alors un fic'ier « e!écutable » +qui se ter*ine par "e!e et indique que la-énération s’est déroulée sans erreurs"

Vous pouve5 alors lancer l’e!écution du pro-ra**e, en vous rendant dans le *enu De,ug / E.écuter +*arqué par uneic4ne représentant un point d’e!cla*ation ou C=>03?"

Exercice : Qu’est-ce que vous remarquez à l’eécution du programme

"#in de visualiser le résultat o$tenu par notre programme% nous allons a&outer une #onction qui permet de visualiser sur

l’écran une c'a(ne de caract)res. *our cela a&outer la ligne suivante au $on endroit dans votre programme :

printf("a=%d, b=%d, a+b = %d\n",a,b,c);

+aire la compilation et l’édition des liens. ,i vous o$servez des erreurs% corrigez-les

ne #ois que le programme ne comporte plus d’erreurs et que l’édition des liens s’est déroulée correctement% eécuter votre

programme.

ne console s’ouvre et doit a##ic'er le résultat de votre calcul. /ans l’eemple proposé% on o$tient un a##ic'age tel qu’il est

représenté ci-dessus.

;

7/21/2019 TPINFO


C) Monsieur a (arc%e pas3 4

)t oui@ Vous re*arquere5 tr.s rapide*ent qu’un pro-ra**e *arc'e rare*ent du pre*ier coup" Ne vous inquiéte5 pas, celaarrive 2 tous les pro-ra**eurs, *ê*e au! plus e!péri*entés@ Pense5 aussi que vous êtes de futurs in-énieurs et que votrer4le sera entre autres de trouver des solutions 2 des probl.*es 1 pour cela il suffit d’un peu de patience et de *ét'ode"

Durant ces séances de =P, vous alle5 être confrontés 2 & t/pes de probl.*es 1A" 0e co*pilateur indique que le pro-ra**e contient des erreurs&" 0e pro-ra**e se co*pile correcte*ent, *ais 2 l’e!écution Ba plante ou vous n’obtene5 pas le bon résultat

Dans le pre*ier cas, il suffit de co*prendre les *essa-es du co*pilateur pour corri-er une 2 une c'aque erreur produite lorsde l’écriture du code"

Conseil :

"#in de ne pas vous retrouver avec des dizaines voire des centaines d’erreurs à la compilation% &e vous sugg)re vivement decompiler réguli)rement votre programme.

ne erreur 0vraie0 peut éventuellement déclenc'er plusieurs messages d1erreur. 2a correction de cette seule erreur enl)vera

donc tous les messages. /e m3me% par#ois le compilateur 0se perd0 et gén)re $eaucoup plus de messages que d1erreurs%

certains de ces messages étant erronés. 4l est donc conseillé de corriger la 5ere erreur 6attac'ée au 5 er message7% de

recompiler etc &usqu1à ce qu1il n1y ait plus d1erreurs.

Dans le deu!i.*e cas, il faut se *unir d’un autre outil qu’on appelle le « débo-ueur »"

5é6oguer un progra((e

Co**e nous l’avons vu dans le para-rap'e précédent, le co*pilateur per*et d’identifier des erreurs de lan-a-e" Par*i lesdifficultés que vous alle5 rencontrer, il se peut que votre pro-ra**e passe l’étape de co*pilation avec succ.s, *ais que votre pro-ra**e ne s’e!écute pas co**e prévu"

Exercice : Cet e!ercice consiste 2 créer un pro-ra**e qui per*et de faire le calcul suivant 1

somme= i

i=A

N

∑

2e résultat attendu avec 895 est ;;.

<apez le code suivant dans l’éditeur de tete de Visual ,tudio 6partez du pro&et eistant7 :

inc!d# $stdio.h

void main (void){

int i;int &='0;int somm#=0;

for(i=';i$=&; i++);{

somm#=somm#+i;}

printf("somm#=%d\n",somm#);}

Compilez et #a(tes l’édition des liens de ce programme 6touc'e +=7.

>écutez le programme 6Ctrl?+;7 : Quel est le résultat o$tenu

Dans un pro-ra**e relative*ent court, on peut rapide*ent identifié les erreurs, en insérant par e!e*ple des printf() quiaffic'ent les résultats des opérations effectuées" Mais d.s qu’un pro-ra**e -a-ne en co*ple!ité, il va devenir tr.s difficilede contr4ler les valeurs de toutes les variables" )n -énéral, on va donc attendre le résultat final, et s’il ne correspond pas aurésultat attendu, on va débo-uer le pro-ra**e"

?

7/21/2019 TPINFO


0’interface de Visual #tudio per*et un débo-a-e relative*ent aisé des pro-ra**es" 0a pre*i.re étape du débo-a-e consiste2 insérer des points d’arrêt 1

1. 7nsertion de ,oints d’arr8ts

Pour insérer un point d’arrêt, clique5 si*ple*ent dans la *ar-e 2 -auc'e de la fenêtre d’édition 2 l’endroit o vous voule5que le pro-ra**e s’arrête lors de l’e!écution" <n point rou-e apparat alors 2 l’endroit o vous ave5 cliqué"

/ans cet eemple% on va mettre un point d’arr3t au niveau de la $oucle #or% puis eécuter en mode pas à pas le programme.

2. ance(ent du (ode 5e6ug

Menu De,ug , puis lancer la co**ande Start De,uggi'g +ou 3?

0’e!écution du pro-ra**e co**ence, puis s’arrête au point spécifié 1 le *ode EDebu-’ per*et alors de contr4ler les valeursdes variables" Dans la fenêtre en bas 2 -auc'e, on observe les valeurs des variables dans le pro-ra**e au *o*ent de l’arrêtde l’e!écution 1

Varia$le Valeur < ype

i int

somme -@;@AABD int

!. '*écution en (ode pas 9 pas 4

Fn va *aintenant e!écuter en *ode pas 2 pas tout le pro-ra**e" Pour cela, aller dans le *enu Debu- et essa/e5 lesdifférentes possibilités 1

Step Into (F11)

Step Over (F10)

Step Out (SHIFT+F11)

Restart (CTRL+SHIFT+F5)

: 0e Ste& 'to per*et de rentrer 2 l’intérieur d’un « bloc d’instructions » pour en vérifier la bonne fonctionnalité" <n blocd’instructions sera soit un ense*ble d’instructions déli*ités par des accolades, soit des fonctions": Pour éviter de rentrer dans un bloc, vous pouve5 faire un Ste& "er 1 dans ce cas, les instructions d’un bloc sont e!écutéesen *ode nor*al jusqu’2 l’instruction suivant la fin du bloc"

: )nfin, si vous êtes entrés dans un bloc d’instruction ou une fonction pour une e!écution pas 2 pas, *ais que vous voule5 ensortir, vous pouve5 alors faire un Ste& "ut , qui vous per*et de venir 2 l’instruction suivant le bloc": Guand vous ave5 plusieurs points d’arrêt, vous pouve5 lancer l’e!écution en *ode Debu- plusieurs fois 1 l’e!écutions’arrêtera s/sté*atique*ent au proc'ain point d’arrêt"

Exercice : *our comprendre eactement ce qu’il se passe% démarrez le dé$ogage d)s la premi)re instruction 6insérer un point

d’arr3t en #ace de l’instruction int i E7 et eécutez en mode pas à pas avec la commande ,tep Fver 6touc'e +57.

Relevez sur un papier le résultat des opérations : repérez l’erreur% corrigez là% et relancez une eécution en mode pas à pas pour voir si l’erreur est corrigée.

Conseil :

tilisez de pré#érence le ,tep Fver 6touc'e +57 lorsque vous ne voulez pas rentrer dans le détail de l’eécution de #onctionstels que le print#67

H

7/21/2019 TPINFO


5) :accourcis utiles

)dition 1

Ctrl + a : Tout sélectionner Ctrl + c : Copier

Ctrl + : Couper Ctrl + p : Coller Ctrl + ! : "nnuler Ctrl + # : Re$aireCtrl + s : Sauver Ctrl + % + Ctrl F : "li&ne'ent auto'atiue

Co*pilation 1

Ctrl + F : Co'piler F : *uilCtrl + F5 : ,écuter

Debu-1

F5: -e.u&F11: Step IntoF10: Step Over S/i$t + F11: Step Out

(ide1

lacer le curseur sur un 'ot et $aire F1

') :e(ar;ue "nale

0a pro-ra**ation est un e!ercice qui peut paratre co*ple!e au début, et qui nécessite une -rande ri-ueur" Vous ave5 des

outils +co*pilateurs, aides de la librairie M#DN qui peuvent vous être d’une -rande utilité pour corri-er des erreurs et éviter de les co**ettre par la suite" Votre professeur est l2 é-ale*ent pour vous aider 1 n’'ésite5 pas 2 poser des questions IDans tous les cas, avant de foncer tête baissée dans l’écriture d’un pro-ra**e, réfléc'isse5 bien au! objectifs, et pose5 sur le papier l’or-ani-ra**e de votre pro-ra**e en déco*posant le probl.*e en sous probl.*es")nfin, faites attention au! no*s que vous donne5 2 vos variables, et abuse5 des co**entaires I 6ls peuvent vous aider 2co*prendre plus facile*ent et plus rapide*ent quelques li-nes de codes dont vous aurie5 oublié le r4le@

Rappel :

2es commentaires en C sont délimités par des $alises : GH pour commencer un commentaire

HG pour terminer un commentaire

Comme vous évoluez dans un environnement dédié au C??% vous avez également la possi$ilité de #aire des commentaires de

#in de ligne qui s’ouvrent simplement par un dou$le slas' : GG

8

7/21/2019 TPINFO


TP 1 : INITIATION AU LANGAGE C

PROBLEME 1

Créez un nouveau projet et copiez le fchier se trouvant dans le répertoirePublicEns\PublicMEA\MEA3\MEA3-Ino\P!\proble"e#$cpp$ Corri%er leserreurs de s&nta'e éventuelles et lancer le pro%ra""e avec le jeud(essais proposé$

A-t-il le co"porte"ent attendu ) *inon+ le "odifer en consé,uence$

inc!sion d# !a !ibrairi# math*mati# "math.h"

main (); proramm# d# ca!c! d#s racin#s d# !-*ation a + b + c =0 on aci#rt !#s co#ffici#nts a,b,c !# proramm# it*r# sr p!si#rs /# d# va!#rs a,b,c i! s-arr#t# !ors# a = b = c = 0 f!oat a,b,c;printf("\ndonn#r !a va!#r d# a");scanf("%f\n",a);printf("\ndonn#r !a va!#r d# b");scanf("%f\n",b);printf("\ndonn#r !a va!#r d# c);scanf("%f\n",c);printf("\n")hi!#((1(a==0) 1(b==0) 1(c==0))

{ ca!c! d discriminantd#!ta = b b 3 4 a cif d#!ta = 0 printf ("racin# dob!# %f \n)

#!s#if d#!ta 0

{s = srt (d#!ta);' = 3b + s 2 a ;2 = 3b 3 s 2 a ;printf ("pr#mi5r# racin# r*#!!# %f\n", ');printf ("d#i5m# racin# r*#!!# %f\n", 2)}

#!s#sd = srt (3d#!ta);

' = 3b 2 a;2 = sd 2 a ;printf("pr#mi5r# racin# comp!## %f +i %f",',2);printf("d#i5m# racin# comp!## %f 3i %f",',2);

printf("\ndonn#r !a va!#r d# a");scanf("%f\n",a);printf("\ndonn#r !a va!#r d# b");scanf("%f\n",b);printf("\ndonn#r !a va!#r d# c);scanf("%f\n",c);printf("\n");}

}

Fn prendra comme &eu d1essais :

J

a b c' '0 '' 32 '0 ' '2 ' '

7/21/2019 TPINFO


K

7/21/2019 TPINFO


Vous remarquerez que la #onction scan#67 qui permet de saisir une valeur au clavier et de la stocIer en mémoire

est indiquée comme étant J désapprouvée K. >n e##et% vous pourrez vous-m3me #aire l’epérience de certains

inconvénients de cette #onction plus tard.

>n attendant% vous avez L possi$ilités pour supprimer les avertissements o$tenus :

,oit vous remplacez simplement la #onction scan#67 par scan#Ms67 qui est la version sécurisée de scan#67 et

approuvée par le compilateur

,oit vous allez dans les propriétés du pro&et pour indiquer au compilateur que vous n’3tes pas concernés par ces avertissements : pour cela% clic droit sur le nom du pro&et% *ropriétés% *ropriétés de Con#iguration% CGC??%

*réprocesseur et a&outer à J *réprocesseur dé#initions K la valeur _CRT_SECURE_NO_DEPRECATE

PROBLEME 2 : P4ramie

Créer un pro%ra""e per"ettant d(aicher un trian%le isoc.le or"éd(étoiles de / li%nes 0/ étant ourni au clavier12

Nombre de lignes : 8

* *o* *ooo* *ooooo* *ooooooo* *ooooooooo* *ooooooooooo* ***************

PROBLEME 3 : D50e60io. e 589e.6eCréer un nouveau projet et écrire un pro%ra""e ,ui lit des caract.resentrés au clavier 0données d(entrée1+ et cela jus,u( ce ,ue les troiscaract.res ((+ (i( et (n( - "inuscules - ou (4(+ (I( et (/( - "ajuscules -aient été saisis successive"ent$ 5n n(acceptera pas les "élan%es delettres "inuscules et "ajuscules$ 0Il n(& a pas de données de sortie1$

Indication 2 "é"oriser en per"anence les trois derniers caract.res lus$

AL

7/21/2019 TPINFO


TP 2 : STRUCTURES DE CONTRÔLE

5n veut aire aicher un da"ier de n par n cases$ 6es cases noires 0resp$blanches1 sont représentées par p 7 p un caract.re C1 0resp$ C21$ Pare'e"ple pour n89+ p 8 3+ C18:+ C28;+ le pro%ra""e doit aicher 2

:::;;;:::;;;:::;;;:::;;;:::;;;:::;;;;;;:::;;;:::;;;:::;;;:::;;;:::;;;::::::;;;:::;;;:::;;;:::;;;:::;;;:::;;;;;;:::;;;:::

;;;:::;;;:::;;;:::;;;:::

6es no"bres n et p+ les caract.res C1 et C2 sont choisis par l(utilisateur0n et p sont supposés <tre inérieurs ou é%au' =1$

Question 1 : Fn écrira ce pro%ra""e de telle a>on ,ue 2- l(entrée des données soit ?sécurisée? en ce sens ,u(en cas de aute derappe lors de l(ac,uisition des no"bres n et p+ le pro%ra""e ne s(arr<tepas "ais ,u(au contraire il de"ande nouveau les valeurs n ou p 0pare'e"ple on rappe sur la touche ?@? au lieu de la touche ??1$ Be a>onsi"ilaire+ on s(assurera ,ue le no"bre n est pair et ,ue les caract.res C1et C2 sont diérents$- apr.s cha,ue aicha%e+ le pro%ra""e ?reco""ence?$ Il s(arr<teralors,ue la valeur donnée n est nulle$

Question 2 : Ecrire trois versions de la partie aicha%e du da"ier propre"ent ditn(utilisant ,ue des structures itératives 0?pour?+ ?tant ,ue?+ ?jus,u( ce,ue?1$ 6(e'écution de ces trois versions sera contrlée par un "enuinteracti$ Par e'e"ple sur l(écran s(aichera le teste suivant 2

o!#73vos affich#r !# dami#r 83 #n ti!isant !a strctr# por (r*pons# a o 9)3 #n ti!isant !a strctr# tant # (r*pons# b o :)3 #n ti!isant !a strctr# por (r*pons# c o )3 ac*rir d# nov#!!#s va!#rs por n, p, ' #t 2 (r*pons# d o <)

*i la réponse est a+ b ou c le da"ier sera aiché puis le "enuréapparaDtra$ *i la réponse est d on rede"andera les para".tres duprobl."e puis le "enu réapparaDtra$ *i la réponse est autre+ le "enuréapparaDtra$

Indications 2 l(i"pression se ait caract.re par caract.re$ Pour ce aire onpeut utiliser soit la onction printf() soit la onction ptchar()$ Pare'e"ple pour i"pri"er la lettre (a(+ on peut écrire 2

AA

7/21/2019 TPINFO


- *oit ptchar (-a-);

- *oit printf("%c",-a-);

A&

7/21/2019 TPINFO


TP 3 : TABLEAUX A UNE DIMENSION

Exercice 1 :a$ *aisir une chaDne de caract.res$

b$ Apr.s la saisie+ calculer 0sans utiliser de onction1 et aicher lalon%ueur de la chaDne de caract.res$

Exercice 2 :

a$ *aisir+ caract.re par caract.re+ une chaine co"posée e'clusive"ent dechires et aicher la chaine saisie$ 6e pro%ra""e vérifera ,ue cha,uecaract.re entré au clavier est bien un chire co"pris entre (( et (=($

b$ Convertir le tableau de caract.res en un tableau de no"bres entiers et

aicher ce tableau$c$ Convertir le no"bre entré sous or"e de chaDne de caract.res enno"bre entier et lFaicher$

Exercice 3 :

a$ *aisir un no"bre entier positi co"posé de G chires "a'i"u"$

b$ Convertir ce no"bre en une chaDne de caract.res$

c$ Aicher la chaDne convertie$

Exercice 4 :

a$ *aisir deu' chaDnes de caract.res

b$ Co"parer+ caract.re par caract.re+ ces deu' chaDnes et déter"iner sielles sont identi,ues ou leur ordre le'ico%raphi,ue$

Exercice 5 :

@n palindro"e est un "ot ,ui reste le "<"e ,u(on le lise de %auche droite ou de droite %auche 0par e'e"ple+ PIEHHE n(est pas un

palindro"e+ alors ,ue 55 est un palindro"e1$

a$ Ecrire un pro%ra""e ,ui vérife si une chaDne si"ple 0sans espace1introduite au clavier est un palindro"e$b$ 4aire la "<"e chose+ "ais cette ois avec une phrase co"pl.te 0avecespaces etou ponctuation1$

Exercice 6 :

Heaire les e'ercices précédents avec les onctions de la biblioth.,ueJ stdlib$h K et J strin%$h K$

A%

7/21/2019 TPINFO


A;

7/21/2019 TPINFO


TP : ALGORIT!ME DU PLUS COURT C!EMIN "LEE#

Bans un lab&rinthe+ on recherche un che"in+ le plus court possible+ allant

d(une case de départ 0Ld+d1 une case d(arrivée 0La+a1+ données$ 1. Représentation

5n représente le lab&rinthe par un tableau rectan%ulaire NMON/Od(entiers 0M8Q et /8Q+ tous les deu' plus petits pendant la "ise aupoint1$ 5n e"ploiera le coda%e suivant 2

NLONO *i%nifcation-! ?case blo,uée par un obstacle? ?case libre non encore traversée?rR ?case libre traversée au pas ?r?-# ?case du se%"ent de che"in déj tracée$

Conditions de che"ine"ent 2 5n re%arde le tableau co""e une carte %éo%raphi,ue$ B(une case 0i+j1on peut passer seule"ent ses ,uatre voisines /ord+ *ud+ Est et 5uest+si elles e'istent 0attention au voisina%e des bords1 et si elles sont libresd(obstacle$

2. Algorithme

2.1 Phase d'expansion

5n "ar,ue ?!? la case de départ$ 5n f'e lp8! 0lon%ueur parcourue1$

En bala&ant tout le tableau dans un ordre ,uelcon,ue+ on "ar,ue ?lp;!?toutes les cases libres d(obstacle+ non déj traversées et adjacentes par le/ord+ le *ud+ l(Est ou l(5uest une case nu"érotée ?lp?$ Puis onincré"ente lp$

Cette opération est répétée jus,u( ce ,ue la case d(arrivée soitatteinte 0cas oS le che"in e'iste1 ou bien jus,u( ce ,ue l(e'écution d(unbala&a%e du tableau s(ach.ve sans ,u(aucune case supplé"entaire n(aitété "ar,uée 0cas oS le che"in n(e'iste pas 2 les cases de départ etd(arrivée sont séparées par des obstacles incontournables1$

2.2 Phase de remontée ou de tracé

Tuand un che"in e'iste+ on le trace en re"ontant de la case d(arrivée la case de départ$

5n "é"orise la lon%ueur du che"in trouvé 2 lp 8 NLaONaO$ C(est ladistance entre 0Ld+d1 et 0La+a1 pour les conditions de che"ine"entadoptées$ Puis on "ar,ue co""e appartenant au che"in 0?-#?1 la cased(arrivée+ ,ui est donc la case initiale de la re"ontée$

Alors+ tant ,ue la derni.re case "ar,uée n(est pas la case de départ+ onen recherche une voisine ,ui soit "ar,uée ?lp-!? 0on sait ,u(il en e'isteune+ car autre"ent la précédente ne serait pas "ar,uée lp1+ on la "ar,ue?appartenant au che"in? et on décré"ente lp$

A?

7/21/2019 TPINFO


3. Présentation des résultats

Pour visualiser l(écran le lab&rinthe et le che"in+ on convertit cha,ue valeur enti.re du tableau en un seul caract.re i"pri"able selon laconvention 2

(( 8 5bstacle(7( 8 Case du che"in($( 8 Case libre hors che"in

He"ar,ues 2

Pour si*plifier le traite*ent des cases se trouvant sur le bord du lab/rint'e, on pourraentourer celui:ci d9obstacles" (insi toute case utile du lab/rint'e poss.de ; voisins"

Fn pensera au cas o il n9e!isterait pas de c'e*in"

4 – Modifcation de la phase d’expansion !acultati"#

Afn dFa"éliorer la phase dFe'pansion on utilisera une fle$ Au lieu debala&er lFense"ble du tableau pour retrouver les cases "ar,uées ?lp?+ lescases nouvelle"ent "ar,uées sont alors stocUées dans une fle$Initiale"ent la fle contient la case départ$ Ecrire le pro%ra""ecorrespondant en utilisant 2

: @ne onction ,ui ajoute un élé"ent la fle+: @ne onction ,ui retire un élé"ent+: @ne onction ,ui teste si la fle est vide

$omplément % $omment générer des nom&res aléatoires '

6e pro%ra""e suivant per"et de %énérer un no"bre entier co"prisentre a et b de "ani.re réelle"ent aléatoire 2

inc!d# $std!ib.hinc!d# $stdio.hinc!d# $tim#.h

int and( int a, int b){

int nand ;

nand= a + (int) ( (f!oat)rand() (b3a+') (9&<>?9@3')) ;

r#trn nand;

}

void main(){

int i;srand((nsin#d)tim#(0));

for (i=0; i$'0; i++){

printf("nandA%dB=%d\n",i,and(3'00,'00));}

}

estez ce pro%ra""e et utilisez cette onction pour %énérer les obstaclesde "ani.re aléatoire dans le pro%ra""e précédent$

AH

7/21/2019 TPINFO


A8

7/21/2019 TPINFO


TP $ : VARIABLES ET %ONCTIONS

Rappels :

- 6(instruction du pré-processeur d#fin# @ C per"et de défnir l(élé"entL ,ui sera substitué par dans le reste du pro%ra""e$ Par e'e"ple 2

d#fin# pi D.'4'EF

G

Hrfac#= pi ; *iva!#nt G D.'4'EF

- 6ors du déroule"ent d(un pro%ra""e+ dans la onction main()+ ou dans

une autre onction+ un branche"ent peut <tre ait vers une autreonction$ Apr.s l(e'écution de la onction appelée+ un nouveaubranche"ent se ait+ en sens inverse+ pour revenir l(endroit oS le courss(était interro"pu$ Pour eectuer le traite"ent+ la onction appelée utilisedes valeurs 0no"bres+ caract.res+ $$$1 ,ui sont+ soit co""unes l(ense"ble des onctions 0variables globales1+ soit trans"ises par la listedes para".tres déli"itée par des parenth.ses et attachée au no" de laonction+ soit défnies au sein "<"e de la onction 0variables locales1$

- 6es para".tres d(une onction sont un ense"ble de valeurs ,ui+ au"o"ent de l(appel+ sont recopiées sur une pile "é"oire 0allocationd&na"i,ue1$ Vu de l(intérieur de la onction+ les para".tres sont des variables locales ,ui disparaissent auto"ati,ue"ent apr.s l(e'écution+tout co""e les autres variables défnies dans le corps de la onction$ Parconsé,uent+ apr.s la fn d(e'écution d(une onction+ les variables passéesen ar%u"ent conservent les valeurs ,u(elles avaient avant l(appel laonction$...

int Ionction'(int /)

/ pr#nd !a va!#r d# !a variab!# a mom#nt d# !-app#! c3a3d i='

{

/ = /2 / d#vi#nt *a! J 2 if (condition) ! = / ;

#!s# ! = 0 ;

r#trn ! ;

}

...

void main()

{

...

int i=' ; i #st initia!is# G '

int K ;

K = Ionction'(i) ;

i vat to/ors '

...

}

AJ

7/21/2019 TPINFO


- 5n peut et on doit renvo&er une valeur d(une onction ,ui n(est pasdéclarée void$ 6(instruction de retour 0return1 précise une valeur deretour 0voir e'e"ple ci-dessus1$ *i la onction ne doit pas retourner de valeur+ elle est déclarée void$

void Procedure1 (int i, ...) { /* ne contient pas d'instruction return */ }

- Il est parois utile de conserver les "odifcations apportées la valeurd(un ar%u"ent apr.s la fn d(e'écution d(une onction$ Puis,ue cela n(estpas prévu ori%inelle"ent par le lan%a%e+ il aut non pas utiliserdirecte"ent les variables traiter "ais plutt leur adresse$

void Procedure2(int val, int *ad)

/* val prend la valeur de i, ad prend la valeur de &j */

{

val++ ;

(*ad)++ ;}

void ain()

{

!.

int i"1;

int j"1 ;

Procedure2(i,&j) /* attention on utilise &j et non directeent j */

/* i vaut toujours 1, j vaut 2*/

}

Tuand on appelle Lroc#dr#2()+ va!++ incré"ente une copie locale du

pre"ier ar%u"ent réel i+ alors ,ue (ad)++ incré"ente le deu'i."ear%u"ent réel / 0i est passée par valeur+ / est passée par réérence1$

- @ne variable stati,ue 0static int i ;1 reste locale la onction dansla,uelle elle est déclarée "ais conserve sa valeur d(un appel l(autre dela onction$

Exercices :

Copier le fchier VarEt4onc$c se trouvant dans le répertoire 2PublicMEA\MEA!-Ino\

! Corri%er les erreurs de co"pilation et d(e'écution

# Ecrire une onction 9pparti#nt() ,ui per"ettra de vérifer si un entierappartient ou pas un ense"ble$ Elle sera appelée partir deMnt#rs#ctiont't2() et de Nniont't2() et per"ettra d(éviter la duplicationdu code de vérifcation d(appartenance dans ces deu' onctions$

3 Proposer trois nouvelles versions possibles de 9cisition()

per"ettant de co"pter et d(aicher le no"bre d(appels cette onction$6a pre"i.re version utilisera une variable %lobale 0l(aicha%e du no"bre

d(appels étant e'terne 9cisition()1+ la deu'i."e version utilisera une variable locale 9cisition() 0l(aicha%e du no"bre de passa%es étant

AK

7/21/2019 TPINFO


interne la onction1+ la troisi."e version utilisera le passa%e parar%u"ent 0l(aicha%e du no"bre de passa%es étant e'terne ou interne la onction1$

Le compte rendu de TP doit contenir le listing de VarEtFonct.c après

correction, les listings des 3 nouvelles versions de #c$uisition() o l!one"pli#uera #uelles sont les modi$cations correspondantes % apporter auprogramme principal pour utiliser ces nouvelles &onctions.

&L

7/21/2019 TPINFO


TP & : STRUCTURES ET %IC!IERS

But

6Fobjecti de ce P est de développer un pro%ra""e per"ettant de trieret co"pter les "ots ,ui sont contenus dans un fchier te'te$

otions utilisées 7 6es chaDnes de caract.res 7 6es fchiers 7 6es structures

!ahier des char"es

Il s(a%it de lire un fchier contenant du te'te+ de trier les "ots par ordrele'ico%raphi,ue croissant+ puis d(aicher la liste triée des "ots du te'teen indi,uant pour chacun d(entre eu' leur no"bre d(occurrences$ Plusprécisé"ent+ le pro%ra""e doit per"ettre 2

- lFouverture en lecture d'un $c(ier contenant un te"te+ fchier dont leno" est indi,ué sur la li%ne de co""ande$ Bans le cas oS l(utilisateuro"ettrait de donner un no" de fchier d(entrée sur la li%ne de co""ande+le pro%ra""e de"ande l(utilisateur d(indi,uer le te'te directe"ent parle clavier W il audra alors ter"iner la saisie avec une indication de ?fn defchier?$

- le tri des mots et le nombre d!occurrences de c(a#ue mot W le tri utilisela dichoto"ie pour chercher la place d(un "ot avant de l(insérer dans letableau trié s(il n(e'istait pas encore+ ou bien d(incré"enter son no"bred(occurrences$ - lFa)ic(age % l'*cran de la liste tri*e des mots+ un "ot par li%ne+ avecpour cha,ue "ot+ son nombre d!occurrences$

#ndications

! E'e"ple de lecture dFun fchierinc!d# "stdio.h"

void main() {

IMOP fic;

char c;

ov#rtr# d fichi#r

fic=fop#n("t#t#.tt","r");

boc!# sr !#s caract5r#s !s

hi!#((c=f#tc(fic)) 1= PQI) {

dans c#tt# boc!#, c conti#nt scc#ssiv#m#nt cha# caract5r# !

printf("%c",c);

}

}

&A

7/21/2019 TPINFO


&&

7/21/2019 TPINFO


# 6a onction strtoK() déclarée dans strin.h per"et de découper unechaDne de caract.res en ?"orceau'? en se basant sur des séparateurs$Pour co""encer ce P+ vous pouvez partir du pro%ra""e ci-dessous ,uilit une li%ne envo&ée au clavier et la découpe avec la onction strtoK()$

inc!d# $strin.hinc!d# $stdio.hchar strinAB = "9 strin\tof ,,toK#ns\nand som# mor# toK#ns";char s#psAB = " ,\t\n";char toK#n;void main( void ){

printf( "%s\n\nRoK#ns8\n", strin ); Pstab!ish strin and #t th# first toK#n8 toK#n = strtoK( strin, s#ps );hi!#( toK#n 1= &NOO ){

Shi!# th#r# ar# toK#ns in "strin" printf( " %s\n", toK#n ); T#t n#t toK#n8 toK#n = strtoK( &NOO, s#ps ); }}

3 6a onction strcmp() protot&pée dans strin.h co"pare des chaDnes decaract.res selon l(ordre le'ico%raphi,ue$

9 6a onction str!#n() protot&pée dans strin.h per"et de connaDtre lalon%ueur d(une chaDne de caract.res$

!onsi"nes

Pour coder le "ot du te'te et le no"bre d(occurrences de ce "ot dans lete'te+ on utilisera la structure de données suivante 2

tUp#d#f strct ompt#?ot{ char motA20B; int nbQcc;}ompt#?ot;

5n utilisera un tableau stati,ue pour ompt#?ot$ 5n peut lire le te'te li%nepar li%ne avec la onction f#ts()$

E'e"ple d(e'écution

*upposons ,ue le pro%ra""e ait été lancé avec un seul ar%u"entindi,uant le no" d(un fchier contenant le te'te suivant 2

:on/or, comm#nt vas3t V Rr5s bi#n. Pt toi, comm#nt vas3t V

Alors+ nous obtiendrons co""e résultat 2

:on/or 8 ' foisPt 8 ' foisRr5s 8 ' foisbi#n 8 ' foiscomm#nt 8 2 foistoi 8 ' fois

t 8 2 foisvas 8 2 fois

&%

7/21/2019 TPINFO


TP 7 : S0r9609re e o..5e

5n veut créer un répertoire téléphoni,ue électroni,ue$ 6esinor"ations "é"orisées sont le nom de la personne et son num*ro de

t*l*p(one 0considéré co""e un entier dans le pro%ra""e1$ Pour ce aire+on utilisera une liste chainée stati,ue appelée Annuaire dans la,uellecha,ue élé"ent contient les inor"ations relatives une personne$ 6echaina%e sFeectuera en onction de lFordre alphabéti,ue$

Principe de la liste chainée stati,ue avec une structure J E'e"ple K+co"posée dFun cha"p /o" 0tableau de caract.res1+ et un cha"p *uivant0entier1$

struct E'e"ple Xchar /o"N#O W

int *uivantWY W

!on$ention :: @n élé"ent de la liste ,ui nFa pas de successeur aura son

cha"p *uivant J -! K$: 5n utilise deu' identifcateurs dFinde'+ Vide et Pleine+ ,ui

per"ettent de repérer lFinde' du pre"ier élé"ent de la listeJ Pleine K et de la liste J Vide K

: *Fil nF& a aucun élé"ent dans la liste+ J Pleine K est J -! K: *i la liste est co"pl.te+ J Vide K est J -! K

Exemple :

5n défnit dans le pro%ra""e principal une liste E'e"ple de taille G 2

struct E'e"ple 6isteNGO Wint Vide8 Wint Pleine8-! W

6a liste vide est initialisée de la "ani.re suivante 2

om %ui$ant

&iste()

!

&iste1)

#

&iste2)

3

&iste3)

9

&iste4)

-!

&;

7/21/2019 TPINFO


&?

7/21/2019 TPINFO


5n ajoute un élé"ent dont le no" est J Alain K+ la liste devient 2

om %ui$ant

&iste

()

*lai

n

+1

&iste1)

#

&iste2)

3

&iste3)

9

&iste4)

-!

Vide8!Pleine85n ajoute un nouvel élé"ent dont le no" est J Zizou K+ la liste devient 2

om %ui$ant

&iste()

Alain !

&iste1)

,i-ou

+1

&iste

2)

3

&iste3)

9

&iste4)

-!

Vide8#Pleine8

5n ajoute un nouvel élé"ent dont le no" est J [ernard K+ la liste

devient 2

om %ui$ant

&iste()

Alain 2

&iste1)

Zizou -!

&iste2)

Bernard

1

&iste3)

9

&iste -!

&H

7/21/2019 TPINFO


4)

Vide83Pleine8

5n suppri"e lFélé"ent 0J Alain K1 de la liste+ la liste devient 2

om %ui$ant

&iste()

3

&iste1)

Zizou -!

&iste2)

[ernard

!

&iste3) 9

&iste4)

-!

Vide8Pleine8#

Etc$

! Béfnir un t&pe de données L#rsonn# per"ettant de "é"oriser les

inor"ations relatives une personne telles ,ue son no" et son nu"érode téléphone$

# Béfnir un tableau de personnes+ de taille f'e+ no""é 9nnair#$

3 Ecrire une onction 9cisition() ,ui per"et l(ac,uisition au clavierdu no" de la personne et de son nu"éro de téléphone$5n vérifera dans cette onction ,ue 2

: le no" de la personne ne dépasse pas 3 caract.res: le nu"éro de téléphone est un no"bre positi

*i ces conditions sont vérifées+ la valeur de retour de la onction vaut !+et le no" et le nu"éro de la personne sont renvo&és au pro%ra""eappelant$ Bans le cas contraire+ un "essa%e d(erreur est envo&é l(opérateur et la valeur de retour de la onction vaut $

9 Ecrire une onction 9/ot#() ,ui ajoute 9nnair# un no" et unnu"éro de téléphone associé$ *i le no" de la personne ne f%urait pasdans Annuaire+ un nouvel élé"ent est ajouté la liste+ sFil f%urait déj+ lenu"éro de téléphone e'istant est re"placé par le nouveau nu"éro detéléphone$ Cette onction doit é%ale"ent per"ettre de "ettre jour lechaina%e des élé"ents en onction de lFordre alphabéti,ue$

&8

7/21/2019 TPINFO


G Ecrire une onction 9ffich#() ,ui aiche le contenu de l(annuaire danslFordre alphabéti,ue$

Ecrire une onction #ch#rch#() ,ui+ pour un no" de personne donné+aiche 2

- son nu"éro de téléphone si le no" f%ure dans l(annuaire- le "essa%e ?pas de personne ce no"? si le no" ne f%ure pas

dans l(annuaire$

Ecrire une onction Pffac#() ,ui+ pour un no" de personne donnésuppri"e lFélé"ent de la liste$ *i la personne n(e'iste pas le "essa%e ?pasde personne ce no"? est aiché$

= Ecrire un pro%ra""e principal constitué d(un "enu per"ettant 2- d(ajouter une personne l(annuaire- d(aicher le contenu de l(annuaire dans l(ordre alphabéti,ue- de suppri"er une personne de l(annuaire- de consulter le nu"éro de téléphone d(une personne- de sortir du pro%ra""e

+ - n supposera #u!il n!/ a pas d!(omon/mes et #ue c(a#ue personnen!a #u!un num*ro de t*l*p(one.

&J

7/21/2019 TPINFO


TP ( : RECURSION

Eer6i6e 1 : VO*AGEUR DE COMMERCE

6e probl."e du vo&a%eur de co""erce 2 *oit n villes reliées par desroutes de lon%ueur di+j 0cha,ue ville est supposée reliée par une route cha,ue autre ville$ 6e probl."e consiste trouver un che"in passant partoutes les villes une ois et une seule revenant au point de départ+ et dontla lon%ueur totale soit "ini"ale$

Pour résoudre ce probl."e on utilisera une "éthode ?brutale? consistant %énérer tous les che"ins+ calculer la lon%ueur de cha,ue che"in etenfn choisir le plus court$

*tructures de données6es distances entre les / villes seront "é"orisées dans une "atriceBistN/ON/O$ Ces données sont stocUées initiale"ent dans un fchier dont lapre"i.re li%ne donne la di"ension /$ Cha,ue li%ne suivante du fchiercorrespond une li%ne de la "atrice$

@n che"in entre les villes sera représenté par un tableau Che"in de /cases+ cha,ue case contenant le nu"éro d(une ville$

Par e'e"ple! 9 3 # 2 représente le che"in !-R9-R3-R#-R!

Pour / 8 9+ on devra %énérer tous les che"ins+ soit 2! # 3 9! # 9 3! 3 # 9! 3 9 #! 9 # 3! 9 3 #He"ar,ue 2 Pour / villes+ il & a 0/-!1] che"ins$ Bonc+ pour "ettre au

point votre pro%ra""e vous co""encerez avec des petites valeurs de /$

Cha,ue ois ,u(un che"in est %énéré+ on calcule sa lon%ueur$ *i salon%ueur est plus courte ,ue celle du "eilleur che"in déj trouvé+ ceche"in devient le "eilleur che"in$

&K

7/21/2019 TPINFO


Eer6i6e 2 : TRIANGLE DE PASCAL

Ecrire un pro%ra""e ,ui construit le trian%le de PA*CA6 de de%ré / etle "é"orise dans une "atrice carrée P de di"ension /;!$

Exemple: <riangle de *ascal de degré D: n=0

'

n=' ' '

n=2 ' 2 '

n=D ' D D '

n=4 ' 4 6 4 '

n=E ' E '0 '0 E '

n=6 ' 6 'E 20 'E 6 '

Eer6i6e 6om;5me.0aire : D<TERMINANT D=UNE MATRICE

5n veut calculer le déter"inant d(une "atrice M$ Pour ce aire+ on utilisela or"ule suivante 2

det+A++ A,

A

Aii

n

i

i

N m N /e t ∑=+−=

dans la,uelle Mi est la "atrice M privée de la li%ne ! et de la colonne i etmi,1 et lFélé"ent de la li%ne i et de la colonne ! de la "atrice M$

Bans un pre"ier te"ps+ saisir les valeurs au clavier lors de lFe'écution dupro%ra""e+ et aicher la valeur du déter"inant lFécran$

Bans un deu'i."e te"ps+ vous pourrez écrire un fchier te'te contenantla "atrice M + puis créer un deu'i."e fchier et écrire la "atrice M ainsi

,ue son déter"inant dans ce nouveau fchier$ 6es fchiers ! et # serontchoisis par l(utilisateur des # a>ons suivantes$

- soit les no"s des fchiers sont donnés sur la li%ne de co""ande$Par e'e"ple 2

pm fichi#r' fichi#r2

- soit les no"s des fchiers ne f%urent pas sur la li%ne deco""ande+ et le pro%ra""e de"ande l(utilisateur le no" des fchiers$

+ - pour acc*der au" mots donn*s sur la ligne de commande, utiliserarc et arv

%L

7/21/2019 TPINFO


/éthode:Calculer et aicher seule"ent les valeurs jus,u( la dia%onale principale0incluse1$ 6i"iter le de%ré entrer par l(utilisateur !3$Construire le trian%le li%ne par li%ne2- Initialiser le pre"ier élé"ent et l(élé"ent de la dia%onale !$

- Calculer les valeurs entre les élé"ents initialisés de %auche droite enutilisant la relation2Pi+j 8 Pi-!+j ; Pi-!+j-!

- Héaliser le "<"e e'ercice+ "ais cette ois en aisant le calcul de"ani.re récursive$

%A

7/21/2019 TPINFO


TP ' : LISTES C!AINEES

5n souhaite créer une application per"ettant de saisir une liste

dFétudiant sans en connaDtre le no"bre au départ$ Cette liste est crée le jour de la rentrée$5n opte pour une structure de liste chaDnée dont cha,ue enre%istre"entposs.de 2

: 6e no" de lFétudiant: 6e nu"éro de la carte étudiant: 6a "o&enne au' e'a"ens: @n pointeur *@IV pointant vers lFadresse de lFenre%istre"ent

suivant

! Créer la liste chaDnée correspondante$ Pour cela on utilisera une onction9/ot() per"ettant dFajouter un élé"ent la liste$

# *uite la rentrée certains étudiants+ ne sont pasprésents$ Il est donc nécessaire de les suppri"er de la liste$ Pour cela onutilisera une onction Hpprim#r() per"ettant de suppri"er un élé"entde la liste$

3 Il est "aintenant nécessaire de trier cette listepar ordre alphabéti,ue 2 utiliser un al%orith"e si"ple de tri 0tri bullepar e'e"ple1 pour trier la liste$ 0on utilisera une onction Rri()1$ @ne ois

la liste triée par ordre alphabéti,ue+ créer une onction Mnv#rs#Oist#()+per"ettant dFinverser la liste$

9 @ne ois ,ue la liste est triée+ il est possible ,uFunétudiant supplé"entaire arrive en cours dFannée 2 "odifer alors laonction 9/ot() afn de lFinsérer directe"ent au bon e"place"ent dansla liste$

G En fn dFannée+ une ois les "o&ennes calculées+on désire conserver la liste uni,ue"ent avec les étudiants ,ui ont une"o&enne supérieure ou é%ale !##$ 5n utilisera une onctionLromoIina!#() pour aire les "odifcations nécessaires la liste$ 6a listechaDnée résultante sera donc la liste fnale des étudiants ad"is endeu'i."e année$

Q 5n désire "aintenant usionner # listes 2 pare'e"ple une liste de la pro"otion actuelle entrant 0obtenu partir depro"o^fnal1 en #."e année et une liste des recrute"ents e'térieursentrant directe"ent en #."e année$ 5n utilisera pour cela une onctionIsion()$

%&

7/21/2019 TPINFO


%%

7/21/2019 TPINFO


TD,TP COMPLEMENTAIRES

Vous trouvere0 cioint une liste d'e"ercice a$n de pr*parer au mieu" lesT4TP et *ventuellement les e"amens d'in&ormati#ue. 5ttention la listen'est pas &orc*ment class*e par ordre de di)icult*

E'ercice !-

Bonner la structure dFun pro%ra""e per"ettant de donner tous lesno"bres paraits inérieur p donné$ Aide 2 un no"bre est parait si et seule"ent si il est é%ale la so""e deses diviseurs 0hor"is lui "<"e1

E'e"ple 2 diviseurs de Q 8 !+ #+ 3+ Q 8R !;#;3 8 Q$ Q no"bre parait$

E'ercice #- 6a "ultiplication ? la russe?

6a techni,ue de "ultiplication dite ? la russe? consiste diviser par # le"ultiplicateur 0et ensuite les ,uotients obtenus1+ jus,uF un ,uotient nul+ noter les restes+ et "ultiplier parall.le"ent le "ultiplicande par #$ 5nadditionne alors les "ultiples obtenus du "ultiplicande correspondantau' restes non nuls$

E'e"ple 2 Q _ !#3 08 3Q91

"ultiplicandeM _ #

"ultiplicateur" ` #

reste" "od #

so""e partielle

!#3 Q 0 _ !#31 ; #9Q 39 0 _ #9Q1 ; 9=# ! ! 0! _ 9=#1 ; =9 0 _ =91 ; 9=#

!=Q 9 0 _ !=Q1 ;9=#3=3Q # 0 _ 3=3Q1 ;

9=## ! ! 0! _ #1 ;

9=#Q _ !#3 8 3Q9

Effectuer les "ultiplications suivantes selon cette techni,ue$Q9 _ =Q 08 Q!9919G _ #3= 08 !GG1

Bonner l(or%ani%ra""e d(un pr%" eectuant cette "ultiplication

%;

7/21/2019 TPINFO


E'ercice 3- Calcul du PCB "éthode !

5n utilisera les propriétés suivantes pour calculer le PCB de # no"bres A et [ 2

PCB 0A+A1 8A PCB 0A+[1 8 PCB 0A-[+[1 si A R [PCB 0A+[1 8 PCB 0[+A1

E'e"ple 2PCB 03Q+#!1 8 PCB03Q-#!+#!18PCB0!G+#!18PCB0Q+!G18PCB0Q+=18PCB 0Q+31 8PCB03+31 83

Bonner l(or%ani%ra""e de ce pro%ra""e

E'ercice 9- Calcul du PCB par la "éthode d(Euclide

5n consid.re ,ue p%cd0a+1 8 a et ,ue pour b p%cd0a+b1 8 p%cd0b+ a"od b1$ 5n pro%resse dans l(al%orith"e en di"inuant cha,ue étape lesno"bres considérés par calcul du "odulo$

Par e'e"ple+ le PCB de !! et de !#= l(aide de l(al%orith"ed(Euclide 2

!! 8 !#= _ ! ; 9#!#= 8 9# _ #9 ; #!

9# 8 #! _ # ;

Il aut prendre le dernier reste avant le zéro+ donc PCB0!! W !#=1 8#!

Bonner l(or%ani%ra""e de ce pro%ra""e

E'ercice G- Anal&se d(un te'te$

5n lit un te'te dans un fchier lettres par lettre$ 5n suppose ,ue l(onutilise une onction ,ui lit un caract.re et renvoie la valuer du caract.re

lu$ Elle renvoie la fn du fchier$

Bonne l(or%ani%ra""e d(un p%" ,ui calcule le no"bre de caract.res etde "ots du te'te$

E'ercice Q-

Donner l’or-ani-ra**e d’un pro-ra**e per*ettant de calculer le no*bre lu 2 rebours d9unno*bre positif entré au clavier")!e*ple: )ntrée1 A&%; (ffic'a-e1 ;%&A

E'ercice -

%?

7/21/2019 TPINFO


Donner l’or-ani-ra**e d’un pro-ra**e qui per*et de calculer la so**e, le produit et la*o/enne d9une suite de c'iffres non nuls entrés au clavier, sac'ant que la suite est ter*inée

par 5éro">etene5 seule*ent les c'iffres +L, A """ K lors de l9entrée des données"

E'ercice -Bonner l(or%ani%ra""e et le pro%ra""e ,ui déter"ine si une année estbisse'tile$ 6(utilisateur doit entrer l(année$Happel 2 une année est bisse'tile si elle est divisible par 9$ E'2 #!# étaitbisse'tileE'ception ! 2 si elle est divisible par ! elle n(est pas bisse'tile$ E' 2!= n(était pas bisse'tileE'ception # 2 si elle est divisible par 9 elle est bisse'tile$ # étaitbisse'tileE'ception 3 2 si elle est divisible par !+ elle n(est pas bisse'tile$! ne sera pas bisse'tile$

Bonner l(or%ani%ra""e d(un p%" ,ui calcule le no"bre de jours écoulésentre un edate donnée et le !er janvier de cette année$

Bonner l(or%ani%ra""e d(un pro%ra""e ,ui calcule le no"bre de joursséparant # dates$

E'ercice =-Bonner l(or%ani%ra""e d(un p%" ,ui donne la valeur "a'i"ale et la valeur "ini"ale d(une suite de no"bres donnés positis entrés au clavier$

6(ac,uisition s(arr<te lors,ue on donne un no"bre né%ati

E'ercice !-

Donner l'organigramme et écrire le code C d'un pgm qui calcule le produit de deux nombres

suivant la méthode suivante :

a*b = a *( b-1) +a si b est impair

a*b = (2 *a ) * (b /2) si b est pair est positif

Exemple ;3*7 = 36 * 6 + 36

= 72 *3 + 36

= 72 * 2 + 108

= 144 *1 + 108

= 144 *0 + 252

= 252

E'ercice !!-

%H

7/21/2019 TPINFO


Ecrire un pro%ra""e per"ettant de saisir une chaDne de caract.resco"posée uni,ue"ent de caract.res (( et de caract.res (!($ Cette chaDnede caract.res représente le coda%e binaire d(un entier$

6e pro%ra""e aichera ensuite 2

! une chaDne de caract.res représentant le co"plé"ent # de l(entier# la valeur de l(entier sous or"e déci"ale

E'e"ple 2

chaWn# saisi# 8 ''0'0comp!*m#nt J 2 8 00''0

va!#r d# !-#nti#r 8 36

He"ar,ue 2 on supposera ,ue l(entier est codé sur 3# caract.res au

"a'i"u"Prére,uis 2 notion de tableau

E'ercice !#-5n désire écrire un pro%ra""e ,ui trie et aiche un ense"ble de vecteurs du plan+ par ordre croissant+ selon la valeur de leur nor"eeuclidienne$ Pour cela+ on utilise la onction 0sort+ déclarée dans le fchierstdli.h+ ,ui réalise un tri rapide 0?0uicU sort?1+ et ,ui a l(en-t<te suivant 2

void qsort(void *tab,size_t nb_elem,size_t taille, int (*compare)(constvoid *,const void *))

6emar#ues -6a onction 0sort est ?double"ent %énéri,ue? 2 d(une part+ elle peut trierdes élé"ents de t&pe ,uelcon,ue W d(autre part+ elle peut trier desélé"ents 0de "<"e t&pe1 selon n(i"porte ,uel crit.re de co"paraison$6e "ot-clé const si%nife ,ue les deu' objets pointés par les deu'para".tres de t&pe $oid ne peuvent pas <tre "odifés l(intérieur de laonction pointée par compare$ Cela vise éviter tout ?eet de bord?$

6a onction 0sort réalise le tri 0croissant1 du tableau d(adresse ta+co"portant nelem élé"ents de taille octets$ Pour cela+ 0sort vaeectuer diérentes co"paraisons entre les élé"ents du tableau+ enappelant une onction de co"paraison donnée par l'utilisateur $ Cetteonction de co"paraison devra retourner 2@ne valeur né%ative si l(élé"ent pointé par son pre"ier para".tre estinérieur l(élé"ent pointé par son second para".tre 0au sens d(uncertain ordre1$@ne valeur nulle si les deu' élé"ents sont é%au'$@ne valeur positive si le pre"ier élé"ent est supérieur au second$ Apr.s avoir défni le t&pe $ecteur par 2

tUp#d#f strct v#ct{

%8

7/21/2019 TPINFO


dob!# ;dob!# U;} v#ct#r;

Héaliser les tches suivantes 2

! Ecrire la onction norme+ ,ui retourne la valeur de la nor"eeuclidienne d(un vecteur dont l(adresse est passée en para".tre+ d(en-t<te 2dob!# norm#(const v#ct#r v)

# Ecrire la onction comparenorme+ d(en-t<te 2int compar#>norm#(const void v',const void v2)

,ui co"pare les nor"es euclidiennes des deu' vecteurs pointés par $1 et $2$

3 Ecrire un pro%ra""e per"ettant de lire les coordonnées tapées auclavier d(au plus 1(( vecteurs+ puis de les aicher l(écran+ une oistriés$

Prére,uis 2 onctions+ pointeurs

E'ercice !3-Ecrire un pro%ra""e ,ui per"et de trouver les boucles dans une listechaDnés de pointeurs de t&pe ool nd&oop#nstance ip$ 6epro%ra""e renvoie ! si il a trouvé une boucle sinon $ Pour tester lepro%ra""e+ créer une structure de t&pe 2

tUp#d#f strct >Mnstanc#{ instanc# n#t ;} Mnstanc#

puis aire un pro%ra""e ,ui %én.re une liste dFInstances avec et sansboucle de t&pe 2

Mnstanc# chain!ist(int si7#Oist, boo! doOoop)

6e pro%ra""e fnal sera du t&pe 2int main (void){

Mnstanc# ip ;boo! !oop ;int si7# ;boo! doOoop ;

printf("#ntr# !a tai!!# d# !a !ist#\n ") ;scanf("%d ", Xsi7#) ;

printf("fair# n# !ist# av#c bo!c# 0oi, 'non ") ;sacanf("%d ", XdoOoop) ;

%J

7/21/2019 TPINFO


ip = chain!ist(si7#, doOoop)!oop = findOoop(ip) ;

Mf (!oop == doOoop){

printf("mon proramm# march#, /# sis !# m#i!!#r\n ") ;

}#!s#{

printf("i! fat contin#r a travai!!#r m#s RL\n ") ;}

}

4aire un test avec si-e7 do&oop 8 57 9RE et si-e7 do&oop 8 57;*&%E.

E'ercice !9-Ecrire un pro%ra""e contenant une <onction récursi$e Calcul78 ,ui 2

- lit un no"bre entier positi entré au clavier- eectue la so""e de ce no"bre avec les no"bres saisis

précéde""ent 0on utilisera une variable de t&pe entier ,ue l(onappellera somme pour "é"oriser le résultat courant1

6e calcul se ter"ine lors,ue le no"bre saisi est é%al $6e résultat fnal est aiché l(écran$

/ote 2 5n pourra utiliser le passa%e d(ar%u"ent par adresse pour la variable somme$

E'ercice !G-Ecrire une onction récursi$e 0et le pro%ra""e principal associé1per"ettant de traduire un no"bre ro"ain en un no"bre sous la or"edéci"ale$ 6a onction ne vérifera pas la validité du no"bre ro"ain$

6appels 2M 8 ! B 8 G C 8 ! 6 8 G L 8 ! V 8 G I 8 !

E"emple 2 I II III IV V VI VII VIII IL L LI LII LL LLL L6 66L ! # 3 9 G Q = ! !! !# # 3 9G Q

6LL 6LLL LC C B M = ! G !

Principe 2*i un chire ro"ain est suivi d(un chire ro"ain de valeur supérieure+ la valeur de ce chire se soustrait+ sinon la valeur de ce chire s(additionne$

%K

7/21/2019 TPINFO


E"emple 2 VIII 8 G ; 3 8 $ LL 8 ! ; ! 8 #$ 6LVII 8 G ; ! ; G ; #8 Q$ IV 8 G - ! 8 9$ L6 8 G - ! 8 9$

Ce s&st."e n(est pas e"plo&é pour les "illiers 0M1$

E'ercice !Q- Bia%onale de Cantor

Fn nu*érote c'aque point du plan de coordonnées +x y +o x et y sont des entiers naturels par le procédé su--éré sur la fi-ure ci:dessous 1

Ocrire une fonction nu*ero+!,/, définie de faBon récursive, qui retourne le nu*éro du point de

coordonnées +x y"

E'ercice !- Anal&se dFun fchier

A l(aide du pro%ra""e ?[loc-notes? créer un fchier ?te'te$t't? contenantun te'te ,uelcon,ue co"posé de lettres+ caract.res de ponctuation+chires etc 0vous pouvez copier un te'te trouvé sur Internet+ depréérence en an%lais1$

Ecrire un p%" ?anal&se? ,ui 2

- lit le fchier ?te'te$t't?- co"pte le no"bre /! de lettres contenues dans ce fchier- co"pte le no"bre /# de blancs+ tabulations+ retours chariot$- co"pte le no"bre /3 de "ots ?4I/? ou ?fn?- ,ui aiche le te'te d(ori%ine en re"pla>ant les lettres par des

"ajuscules$- ,ui aiche la so""e des caract.res chires contenus dans le te'te

5n se servira du %abarit suivant pour lire les caract.res dans le fchier$

inc!d# "stdio.h"

void main() {

;L

7/21/2019 TPINFO


IMOP fic;

char c;

ov#rtr# d fichi#r

fic=fop#n("t#t#.tt","r");

boc!# sr !#s carct5r#s !s

hi!#((c=f#tc(fic)) 1= PQI) {

dans c#tt# boc!#, c conti#nt scc#ssiv#m#nt cha# caract5r# !

printf("%c",c);

comp!*t#r !# proramm# ici GGGGGGG.

}

#t ici GG.

}

E'ercice !- tableau' une di"ension

@n tableau est un ense"ble d(élé"ents de "<"e t&pe et a toujours unedi"ension fnie$ Bans ce P+ on se propose de "anipuler successive"entdes tableau' d(entiers et des tableau' de caract.res$ 5n era au "oins lestrois pre"iers e'ercices$

1 - A partir de données de t&pe entier entrées au clavier+ écrire unpro%ra""e P! ,ui re"plit un tableau A[! de t&pe taleau d'entierspositi<s ou nuls+ de telle sorte ,ue les données dans le tableau soientran%ées dans l'ordre croissant = tout instant. Au préalable+ on aurainitialisé toutes les cases du tableau la valeur -!+ la valeur -! dans unecase d(un tableau si%nifant par convention ,ue la case est ?vide?$ 5n

f'era la di"ension du tableau M!8G$ 6(ac,uisition des no"bress(arr<te soit lors,ue le tableau est plein soit lors,u(on donne un no"brené%ati$ He"ar,ue 2 si le tableau n(est pas co"pl.te"ent re"pli+ les cases?vides? seront "ar,uées par la valeur -!$

E'e"ple 2 si les valeurs données sont successive"ent 3+ !+ G+-9

3' 3' 3' 3' 3' 3'

D 3' 3' 3' 3' 3'

' D 3' 3' 3' 3' ' D E 3' 3' 3'

0

He"ar,ue 2 il ne s(a%it pas de trier le tableau une ois celui-ci re"pli+"ais de rajouter cha,ue valeur sa bonne place dans le tableau en?décalant? si nécessaire les autres valeurs$

2 : En utilisant le pro%ra""e P!+ et donc un tableau A[! dans le,uel /

élé"ents sont ran%és dans l(ordre croissant+ écrire un pro%ra""e P# ,ui

lit les données de A[! et ran%e uni,ue"ent les p entiers pairs dansun tableau A[# de telle sorte ,ue ces élé"ents se retrouvent dans unordre décroissant. 5n f'era la di"ension du tableau A[# M#83 et

;A

7/21/2019 TPINFO


on vérifera la condition /p M# c$--d$ ,ue si /p R M# on ne copiera,ue les M# plus %randes valeurs paires$ Bans le cas contraire+ A[# seraco"plété par des valeurs !$

3 : A partir de deu' tableau' A[! et A[# dans les,uels les élé"ents de

t&pe entier sont ran%és dans l(ordre croissant 0on se servira dupro%ra""e P! pour construire A[! et A[#1+ écrire un pro%ra""e P3,ui ran%e toutes les données de A[! et A[# dans un troisi."e tableauA[3+ de telle sorte ,ue les données dans le tableau A[3 soient ran%éesdans l(ordre croissant$ He"ar,ue 2 le no"bre de valeurs ran%ées dansA[! et A[# peut <tre diérent$ 5n ne era pas de tri sur A[3$

4 : A partir d(un tableau d(entiers A[I dans le,uel sont ran%ées des

données non triées+ écrire un pro%ra""e PG ,ui prend les données deA[I et les ran%e dans l(ordre croissant dans un deu'i."e tableau A[4$6e tableau initial A[I pourra contenir plusieurs ois les "<"es valeurs$

E'ercice !=- ri par dichoto"ie

Il e'iste diérentes "éthodes de tri$ 5n se propose ici de "ettre enuvre un tri par J dichoto"ie K$

Pour cela+ on consid.re la pre"i.re valeur du tableau A appelée pivot$ 5nplace le pivot la place 9 de telle a>on ,ue 2

- pour tout iU+ ANiO8ANUO8pivot- pour tout iRU+ ANiORANUO8pivot

5n reco""ence la "<"e opération sur les deu' sous-tableau' AN!O+$$+ANU-!O et ANU;!O+$$$$+ANnO$ Puis+ pour chacun d(eu' sur # sous-tableau'+etc$$$

5n arr<te de traiter un sous-tableau lors,u(il ne contient ,u(un seulélé"ent ou lors,ue tous ses élé"ents sont é%au'$ Pour %érer lesintervalles successis du tableau sur les,uels on appli,ue ladichoto"ie on utilisera une i"plantation récursive$

E'ercice #-a Bonner l(or%ani%ra""e et un pro%ra""e+ utilisant une boucle >hile+,ui aiche une table de conversion des de%rés 4arenheit en de%résCelsius+ de la or"e suivante 2

4arenh$ Celsius

!# Q

9 9Q !G$

;&

7/21/2019 TPINFO


$$3 !9

6es bornes 0 et 3 dans le cas ci-dessus1 sont données par l(utilisateur$

5n vérifera ,ue la borne inérieure est réelle"ent inérieure la bornesupérieure$ Bans le cas contraire+ un "essa%e d(erreur sera aiché$

Remar0ue :• 6a conversion 4arenheit 0;1 - Celsius 0!1 est assurée par la or"ule

suivante 2!85?;+32

Bans le tableau précédent+ les valeurs nu"éri,ues aichées sonttoutes enti.res

b Heprendre l(e'ercice précédent en re"pla>ant la boucle >hile par uneboucle <or $

E'ercice #!-Ecrire un pro%ra""e ,ui de"ande la hauteur d(une p&ra"ide et ,uiaiche celle-ci en utilisant la onction aicheCar01$

E'e"ple 2 une p&ra"ide de hauteur 9

E'ercice ##-Bonner l(or%ani%ra""e et le pro%ra""e per"ettant d(aicher le losan%esuivant or"é d(étoiles et dFespaces de / li%nes 0/ est ourni au clavier12

/o"bre de li%nes 2

*

E'ercice #3-Ecrire un pro%ra""e ,ui per"ette d(ac,uérir des no"bres positis auclavier$ 6(ac,uisition s(arr<te lors,ue on donne un no"bre né%ati$ 6ep%" aiche alors les valeurs "a'i"ales et "ini"ales données"

E'ercice #9-

;%

7/21/2019 TPINFO


Ecrire un pro%ra""e per"ettant de trouver tous les gpF pre"iersno"bres pre"iers oS p est donné par lFutilisateur$

5ide - un no"bre est pre"ier si et seule"ent si il nFe'iste pas de diviseurinérieur ou é%ale la partie enti.re de sa racine$

E'ercice #G- Calcul de π 2 "éthode stochasti,ue

6e principe de cette "éthode consiste tirer aléatoire"ent un %randno"bre de points l(intérieur du carré C déli"ité par les points 0+1 et0!+!1$ 6a proportion des points intérieurs au ,uart de dis,ue B de ra&on !et de centre 0+1 tend vers le rapport des suraces de B sur C+ c(est--dire π9$ 6e pro%ra""e eectue donc une boucle ,ui tire un point auhasard et incré"ente un co"pteur si le point se trouve <tre intérieur B$

II-! Ecrire la onction tirage78 ,ui eectue le tira%e aléatoire dFun point+et vérife sFil appartient ou pas au ,uart de dis,ue B$ Cette onctionrenverra ! si le point appartient B+ et dans le cas contraire$II-# Ecrire le pro%ra""e principal pour ,uFil e'écute !$ tira%es+ et,uFil aiche la valeur esti"ée de π cha,ue itération$

II-3 Bans le cas oS une précision donnée sur π est recherchée+ ,uepourrait <tre le crit.re dFarr<t du pro%ra""e)

Happels 2

- @n point est intérieur B si et seule"ent si A&&≤+ y $

- 6a onction rand78 renvoie un entier co"pris entre et la constanteprédéfnie MALÎ/

E'ercice #Q-

5n se propose de calculer l(inté%rale d(une onction entre deu' bornes a

et b+ tel ,ue 2

∫ =

=

=%

A

$

a

d 4

5n utilisera la "éthode de calcul dite des rectan%les 0voir f%ure !1$ 5ndéfnit un pas suisa""ent petit appelé pas correspondant la ! ."e partie de l(intervalle considéré et on eectue la so""e discr.te desaires des rectan%les inscrits entre la courbe et l(a'e des abscisses$

Ecrire le pro%ra""e du calcul de l(inté%rale en utilisant la "éthode citéeprécéde""ent$

;;

7/21/2019 TPINFO


/ote 2 le pro%ra""e principal doit se présenter sous la or"e d(unesi"ple boucle d(itération %rce la,uelle on calcule+ par cu"ul+ une variable somme correspondant la so""e des aires élé"entairesdéfnies par le découpa%e de l(intervalle en ! élé"ents de lar%euré%ale pas$ A titre d(e'e"ple la pre"i.re valeur calculée sera l(aire du

rectan%le au point a+ INO80a1 7 0a-b1!$

E'ercice #-Ecrire une <onction /# et une <onction /*@ ,ui déter"inent le"ini"u" et le "a'i"u" de deu' no"bres réels selon les protot&pessuivant 2a oat MI/ 0oat+ oat1 oat MAL 0oat+oat1b void MI/ 0oat+ oat+ 7oat1 void MI/ 0oat+ oat+ 7oat1Ecrire un pro%ra""e principal se servant des onctions MI/ et MAL pour

déter"iner le "ini"u" et le "a'i"u" de ,uatre no"bres réels entrés auclavier et ce pour les versions de protot&pe$

E'ercice #-Ecrire un p%" ,ui calcule le produit de deu' entiers en utilisant leprincipe suivant 2a 7 b 8 a 7 0b-!1 ; a si b est i"paira 7 b 8 0# 7 a1 7 0b #1 si b est pair et diérent de Ainsi on se ra".ne ne aire ,ue des "ultiplications et divisions par # enplus des additions$E'e"ple 2

3Q 7 8 3Q 7 Q ;3Q8 # 73 ;3Q8 # 7# ; !8 !99 7 ; #G#8 #G#

E'ercice #=-Ecrire un p%" se co"portant co""e une calculatrice+ cd e'écutant uneboucle sur 2

!$ lecture d(une li%ne supposée contenir un entier+ un opérateur etune entier 0e' 2 !;#1$ 6es opérateurs sont ;+ -+ 7+ +

#$ calcul de la valeur de l(e'pression

;?

3 !

6QLRas

! !a b

7/21/2019 TPINFO


3$ aicha%e du résultat l(écran5n aura intér<t utiliser la onction sscan pour e'traire les opérandes etl(opérateur de la li%ne lue$

E'ercice 3-

Bonner l(or%ani%ra""e et le pro%ra""e ,ui lit la di"ension / d(untableau du t&pe int 0di"ension "a'i"ale2 G co"posantes1+ re"plit letableau par des valeurs entrées au clavier et aiche le tableau$Copiez ensuite toutes les co"posantes stricte"ent positives dans undeu'i."e tableau P5* et toutes les valeurs stricte"ent né%atives dansun troisi."e tableau /E$ Aicher les tableau' P5* et /E$

E'ercice 3!-Ecrire un pro%ra""e ,ui construit le trian%le de PA*CA6 de de%ré / etle "é"orise dans une "atrice carrée P de di"ension /;!$

Exemple: <riangle de *ascal de degré D:

n=0 '

n=' ' '

n=2 ' 2 '

n=D ' D D '

n=4 ' 4 6 4 '

n=E ' E '0 '0 E '

n=6 ' 6 'E 20 'E 6 '

/éthode:Calculer et aicher seule"ent les valeurs jus,u( la dia%onale principale0incluse1$ 6i"iter le de%ré entrer par l(utilisateur !3$Construire le trian%le li%ne par li%ne2

- Initialiser le pre"ier élé"ent et l(élé"ent de la dia%onale !$- Calculer les valeurs entre les élé"ents initialisés de %auche droite enutilisant la relation2Pi+j 8 Pi-!+j ; Pi-!+j-!

E'ercice 3#-

Ecrire un pro%ra""e per"ettant de saisir un tableau de ! no"bresentiers puis ,ui ait appel une onction renvo&ant la so""e de tous lesélé"ents du tableau$

E'ercice 33-

;H

7/21/2019 TPINFO


Ecrire un pro%ra""e ,ui eectue la transposition tA d(une "atrice A dedi"ension / et M en une "atrice M et /$

a1 6a "atrice transposée sera "é"orisée dans une deu'i."e "atrice[ ,ui sera ensuite aichée$

b1 6a "atrice A sera transposée par per"utation des élé"ents

c1 Pour les ,uestions a et b+ donner la co"ple'ité du pro%ra""e "isen uvre$

Rappel :

t( S t a b c d S a e ii f - ' b f ji j T l c - T

d ' l

E'ercice 39-

*oit la sé,uence 2int tab[10];int *p,i;for (i=0;i<10;i++) tab[i]=0;i=5;p=tab; /* Equivalent à p=!tab[0]; */p=tab+i; /* Equivalent à p=!tab[i]; */

A l(aide d(une représentation %raphi,ue+ indi,uer les "odifcationsapportées au tableau ta par la sé,uence d(instructions suivante+ et ceapr.s cha,ue instruction 2

&<p)==>&p==)>&<p)==>&<&p=2))==>&<&ta6=2))==>

E'ercice 3G-

5n consid.re un tableau de personnes 0no"+ préno"+ nu"éro dans larue+ rue+ code postal+ ville+ nu"éro de téléphone1+

a1 Créer la structure correspondante+b1 aire un pro%ra""e de recherche auto"ati,ue de toutes les

inor"ations sur les personnes répondant une valeur d(unerubri,ue donnée 0tous les PAHIC par e'e"ple1$ 5n suppose,ue le tableau est déj initialisé$

E'ercice 3Q-

;8

7/21/2019 TPINFO


5n veut écrire un pro%ra""e ,ui calcule la so""e suivante 2

∑=

+=$

ai

ii$a, sin+,+

6e calcul de *0a+b1 doit se aire en utilisant une onction &ct78$ 6epro%ra""e principal se char%e de de"ander lFutilisateur de saisir auclavier deu' entiers a et b+ puis appelle la onction en lui passant a et bco""e para".tres$ 6e résultat est stocUée dans une variable c$

I-! Tuel doit <tre le t&pe de la valeur retournée par la onction ) Ecrivezla onction+ ainsi ,ue le pro%ra""e principal en co""entant votresolution$

I-# Est-il possible de "odifer les variables locales main78 a ou b partir

de la onction ) Pour,uoi )I-3 Béfnissez une variable compteur locale main78, et "odifez laonction &ct78 0utilisation de pointeur1 pour ,ue compteur stocUe leno"bre total dFadditions eectuées depuis le lance"ent du pro%ra""e$

E'ercice 3-

4aire la so""e consécutive de # entiers contenus dans un tableau t! etretourner le résultat de la so""e dans deu'i."e tableau t#$ 5nsupposera dans un pre"ier te"ps ,ue le tableau t! est de lon%ueur paire$

E'ercice 3-

M<"e e'ercice ,ue précéde""ent "ais on sort du pro%ra""e lors,uFunter"e du tableau t! est é%al zéro$

E'ercice 3=-

Bonner lFor%ani%ra""e dFun pro%ra""e per"ettant de co"pter leno"bre de li%nes+ le no"bre de caract.res et le no"bre de "ots lus dansun fchier

E'ercice 9-

Ecrire un pro%ra""e ,ui 2a$ lit au clavier des inor"ations dans un tableau de structures de t&pe

point défni co""e suit 2"tru#t point $

int nu% ;

&oat ' ;&oat ;

;J

7/21/2019 TPINFO


6e no"bre dFélé"ents du tableau sera f'é par une instruction kdefne0,ui per"et de défnir un constante avant le "ain011$b$ Aiche lFécran lFense"ble des inor"ations précédentes$

Héaliser la "<"e chose ,ue dans lFe'ercice précédent+ "ais enprévo&ant+ cette ois une onction pour la lecture des inor"ations et uneonction pour lFaicha%e$

E'ercice 9!-

Ecrire un pro%ra""e ,ui se contente dFenre%istrer sé,uentielle"entdans un fchier une suite de no"bre entier ,uFon lui ournit au clavier$

E'ercice 9#-

Ecrire un pro%ra""e ,ui lit une chaDne de caract.res C et ,ui convertittoutes les "ajuscules dans des "inuscules et vice-versa$6e résultat sera "é"orisé dans la "<"e variable C et aiché apr.s laconversion$

E'ercice 93-

Ecrire un pro%ra""e ,ui suppri"e la pre"i.re occurrence d(une chaDnede caract.res 5[m dans une chaDne de caract.res *@m$

Exemples: LYQ& 9OLYQ&HP 9OHP PM LMPP LMPP R RQR9OP?P&R QR9OP?P&R

YPOOQ YPOOQ

E'ercice 99-

Ecrire un pro%ra""e ,ui lit ! phrases d(une lon%ueur "a'i"ale de #caract.res au clavier et ,ui les "é"orise dans un tableau de pointeurssur char en réservant d&na"i,ue"ent l(e"place"ent en "é"oire pourles chaDnes$ Ensuite+ l(ordre des phrases est inversé en "odifant lespointeurs et le tableau résultant est aiché$

E'ercice 9G-

Ecrire un pro%ra""e ,ui lit ! "ots au clavier 0lon%ueur "a'i"ale2 Gcaract.res1 et attribue leurs adresses un tableau de pointeurs M5$Eacer les ! "ots un un+ en suivant l(ordre le'ico%raphi,ue et en

;K

7/21/2019 TPINFO


libérant leur espace en "é"oire$ Aicher cha,ue ois les "ots restantsen attendant la confr"ation de l(utilisateur 0par (Enter(1$

E'ercice 9Q-

5n veut coder un al%orith"e de cr&pta%e tr.s si"ple 2 on choisit undécala%e 0par e'e"ple G1+ et un a sera re"placé par un + un b par un %+un c par un h+ etc$ 5n ne cr&ptera ,ue les lettres "ajuscules et"inuscules sans toucher ni la ponctuation ni la "ise en pa%e$ 5nproc.de co""e suit 2

i$ Ecrire une procédure void cr&pt0 char 7p 1 de cr&pta%ed(un caract.re$

ii$ Ecrire le "ain ,ui appellera la onction cr&pt surl(ense"ble du "essa%e et i"pri"era le résultat$

E'ercice 9-

5n veut savoir si une lettre est présente dans une chaDne de caract.res etle no"bre de ois ,ue cette lettre apparaDt dans la chaDne$

iii$ Ecrire une onction void "in#"aj0 char 7p 1 ,uitransor"e une chaDne de caract.res ,uelcon,ue en unechaDne identi,ue "ais dont tous les caract.res sont des"ajuscules$

iv$ Ecrire une onction int parcours0 char 7p + char c 1renvo&ant le no"bre de ois ,ue la lettre se trouve dansla chaDne de caract.res$

v$ Ecrire le pro%ra""e principal "ain01$

E'ercice 9-

@n palindro"e est un "ot ,ui reste le "<"e ,u(on le lise de %auche droite ou de droite %auche 0par e'e"ple+ PIEHHE n(est pas unpalindro"e+ alors ,ue 55 est un palindro"e1$ Ecrire de deu' a>ons

diérentes+ un pro%ra""e ,ui vérife si une chaDne C introduite auclavier est un palindro"e$

vi$ En utilisant uni,ue"ent le or"alis"e tableau$

vii$ En utilisant des pointeurs au lieu des indicesnu"éri,ues$

E'ercice 9=-

ri bulle 0bubblesort1 2 il consiste aire %lisser la plus petite valeur audébut du tableau$ *i deu' valeurs adjacentes ANiO et ANi;!O sont telles

,ue ANiO R ANi;!O on les échan%e$ Ainsi apr.s un pre"ier passa%e la valeur la plus ?lé%.re? "onte au début du tableau$ 5n reco""ence en

?L

7/21/2019 TPINFO


ne considérant plus ,ue AN#O+AN3O+$$$+ANnO$

E'ercice G-

*oit le pro%ra""e tp3ê'9$c ,ue vous trouverez dans le répertoire

2PublicMEA\MEA!-Ino\PourP3$ Bans un pre"ier te"ps+ lire ete'écuter le pro%ra""e$ Ensuite+ écrire la partie # du pro%ra""e 0ladescription de cette partie se trouve dans le fchier tp3ê'9$c1 en utilisantuni,ue"ent les adresses des tableau' s et t pour les parcourir ou"odifer leur contenu$

E'ercice G!-

(n pro&l)me de planning

En début dFannée+ dans une université+ chacun des M étudiants sFinscrit

U cours par"i /$5n se propose dFétablir la chronolo%ie de lFense"ble des cours sousor"e de sessions$ @ne session est un ense"ble de cours pouvant sedérouler si"ultané"ent$ Beu' cours peuvent se dérouler si"ultané"entlors,ue aucun étudiant nFest inscrit ces deu' cours$ Bans le cascontraire+ les cours sont dits en conit$

- Cha,ue cours est réérencé par un entier co"pris entre ! et /$- Cha,ue étudiant est réérencé par un entier co"pris entre ! et M$- 5n supposera M et / inérieurs respective"ent ! et !$

5n suppose donné les ense"bles I/*CHIPI5/ des cours suivis sousor"e dFun tableau de M par / oS I/*CHIPI5/NiONjO 8 ! si l(étudiant iest inscrit au cours j+ dans le cas contraire$*oit !A;&#9 un tableau # di"ensions pour le,uel !A;&#9c) estlFense"ble des cours en conit avec le cours c$ 5n utilisera pourC5/46I la "<"e convention ,ue celle utilisée pour I/*CHIPI5/ 2C5/46INc!ONc#O8 ! si c! et c# sont en conit+ C5/46INc!ONc#O8 sinon soit %E%%#As) lFense"ble des cours se déroulant la session s$

5n veut déter"iner les ense"bles *E**I5/ sans chercher "ini"iser leno"bre de sessions connaissant les ense"bles I/*CHIPI5/$Pour se aire+ on utilise lFal%orith"e suivant dans le,uel RE%9E dési%nelFense"ble des cours non encore placés dans une session+ ses la sessionen cours de construction et !A;&#9% lFense"ble des cours en conitavec lFun des cours placés dans cette session ses$

a3 initia!isations 8

3 Lor cha# cors c, *tab!ir Q&IOMRAcB

3 s#s = 0

3 PHRP = !Z#ns#mb!# d#s cors

b3 Rant # PHRP [ fair# 8

3 s#s = s#s +'

?A

7/21/2019 TPINFO


constrction d# !a s#ssion s#s

3 choisir n cors c0 appart#nant J PHRP

3 r#tir#r c0 d# PHRP

3 p!ac#r !# cors c0 dans !a s#ssion s#s

3 Q&IOMR>H = Q&IOMRAc0B ∪ {c0}

3 Lor tot cors c dans PHRP #t i nZ#st pas #n conf!it av#c !a s#ssion

s#s, fair# 8

3 ra/ot#r c J !a s#ssion s#s

3 Q&IOMR>H = Q&IOMR>H ∪ Q&IOMRAcB ∪ {c}

3 r#tir#r c d# PHRP

*uestions -5n suppose dans la suite ,ue / et M connus au "o"ent de laco"pilation

- Ecrire les déclarations de constantes+ t&pes et variables nécessaires

l(i"plantation de lFal%orith"e$- Ecrire le pro%ra""e pour 2

: He"plir le tableau I/*CHIPI5/ W

: Ecrire lFal%orith"e per"ettant de donner le no"bre / decours eective"ent choisis et M le no"bre d(étudiants W

: I"planter lFal%orith"e ci dessus W

Aicher lFécran le no"bre de sessions et pour cha,ue session

lFense"ble des cours la co"posant$

E'ercice G#-<n fic'ier contient une séquence +de lon-ueur inconnue d9é-alités entre les so**es desno*bres entiers positifs +un par li-ne" ( titre d9e!e*ple, considérons le fic'ier suivant 1&%A&JSK&%;SK&&S%;?AL%?AS;;;

Note5 que les é-alités peuvent être soit correctes +les trois pre*i.res soit fausses +la dernier")crire une fonction C qui prend en para*.tre le no* du fic'ier et renvoie la fraction desé-alités correctes" Dans cet e!e*ple, la fonction doit retourner L,8?"#u--estion 1 vous pouve5 utiliser des fonctions telles que atoi, strtoK,f#ts

E'ercice G3-Ecrire une onction ,ui per"et de transor"er un vecteur d(entiers enune chaine de caract.res$ 6a onction re>oit le pointeur de début du vecteur+ sa di"ension et le pointeur de début de la chaine de caract.resdestination 2 void ecrirevecteur 0int vNO+ int di"+ car sNO1W6a chaine s devra contenir les no"bres présents dans le vecteur séparéspar des vir%ules

E'e"ple 2 V 8*8 ?!#+ + + 9G+ #+ =+ ?

?&

!# 9G # =

7/21/2019 TPINFO


Version ! 2 on utilisera la onction sprint& ,ui per"et d(écrire dans unechaine de caract.res et dont le onctionne"ent est identi,ue celui de laonction print$

*on %abarit est int sprint< char c(aine7 const char &ormat N7 argumentO $$$ oS

7chaine est l(adresse de la chaine destination$

Version # 2 on n(utilisera pas la onction sprint$ Il est conseillé décrireune onction ,ui transor"e un no"bre entier en une chaine decaract.res$

E'ercice G9-

Ecrire un pro%ra""e capable de trouver un "ot l(intérieur d(une"atrice de caract.res$ 6e pro%ra""e devra tout d(abord de"ander l(utilisateur la "atrice de caract.res de di"ension /'/ 0/ sera de"andé l(utilisateur1$ Il de"andera ensuite le "ot rechercher+ la lon%ueur Mdu "ot devra <tre inérieure /$ 6e pro%ra""e devra rechercher laprésence du "ot l(intérieur de la "atrice+ horizontale"ent de %auche droite et de droite %auche et verticale"ent de haut en bas et de bas enhaut$*i le "otest trouvé+ le pro%ra""e aichera les coordonnées du caract.rede début de la chaine et sa direction$ *i le "ot n(est pas trouvé+ un"essa%e sera aiché$

E'e"ple de "atrice et de "ots trouvés2

E'ercice GG-Ocrire un pro-ra**e pour affic'er une c'ane de caract.res +reBu 2 partir du clavier sur

plusieurs li-nes de lon-ueur U +U c'oisi aussi par l’utilisateur de faBon justifiée"0a c'ane doit être co*posée de *a!i*u* %LLL caract.res et le no*bre de caract.res parli-ne doit être entre &L et JL")!e*ple" C'aine introduite 1

L'avantage d'être intelligent, c'est qu'on peut toujours faire

l'imbécile, alors que l'inverse est totalement impossible

K=25

>ésultat 1L'avantage d'être

intelligent, c'est qu'on

?%

7/21/2019 TPINFO


peut toujours faire

l'imbécile, alors que

l'inverse est totalement

impossible

E'ercice GQ-Ocrire une fonction ,upprime/ou$lons qui prend une liste de valeurs enti.res +déj2 triées dansl9ordre croissant et qui suppri*e tous les nuds qui contiennent les *ê*es valeurs"6déale*ent, la liste ne doit être parcourue qu9une seule fois" 6l faut bien suppri*er de la*é*oire les nuds effacés"Par e!e*ple, si vous ave5 la liste suivante 10, ', ', D, 4, 4, E, 6, 6, 6, ], F

le pro-ra**e *odifiera la liste de faBon 2 avoir 10, ', D, 4, E, 6, ], F

Ocrire aussi la fonction *ain qui appellera la fonction Remplir +vois ci dessous, puis qui

affic'e le contenu de la liste, puis la fonction ,upprime/ou$lons, et 2 nouveau on affic'era lecontenu de la liste"Winclude Xstdio"'YWinclude Xstdlib"'YWinclude Xti*e"'Y

struct liste Zint nstruct liste ne!t

[

void re*plir +struct liste tete

Z int i, vSLstruct liste t

srand +ti*e+N<00teteS+struct liste*alloc+si5eof+struct listetStetefor +iSL iX?L i Z

t:YnSvt:Yne!tS+struct liste*alloc+si5eof+struct listetSt:Yne!tvS++intrand+\?

[

t:YnSvt:Yne!tSN<00[

E'ercice G-)crire un pro-ra**e en C qui reBoit en entrée une séquence d’entiers positifs non nuls +le Lest considéré co**e ter*inateur de la séquence" Montrer 2 l’écran l’ense*ble de valeursdistinctes reBues, c'acune acco*pa-née par sa fréquence d9apparition dans la séquenced9entrée"Par e!e*ple, si vous receve5 la séquence suivante 1'2

'0^'0

?;

7/21/2019 TPINFO


'0'2D0

le pro-ra**e affic'e 1

'28 2^,6%'08 42,^%^8 '4,D%D8 '4,D%

<tiliser une liste pour *é*oriser les élé*ents de la séquence" C'aque nud de la listecontient % élé*ents 1 le no*bre faisant partie de la séquence, sa fréquence, et le pointeur aunud suivant" Pour c'aque valeur reBue, le pro-ra**e va c'erc'er dans la liste si la valeur est déj2 présente" Dans ce cas, le pro-ra**e va incré*enter la fréquence correspondante" #ila valeur n’est pas dans la liste, on rajoutera +en tête de la liste la nouvelle valeur"

E'ercice G- Passa%e d(une onction co""e para".tre d(une autre

onctionIl est possible de défnir des variables a&ant le t&pe ?pointeur deonction?$ 6a valeur d(une telle variable est l(adresse en "é"oire dudébut du code e'écutable d(une onction+ et sa déclaration s(écrit selonl(une des deu' s&nta'es suivantes 2

type_fonction (*nom_variable)(paramètres_de_la_fonction); type_fonction (*nom_variable)(types_paramètres_de_la_fonction);

Pour lire de telles déclarations sans ris,ue de conusion+ on a intér<t procéder en plusieurs étapes$E'e"ple 2

int (*p_f)(float r); o int (*p_f)(float);

Pour co"prendre cette déclaration+ on pourra procéder de la "ani.resuivante 2p?f le no" de la variable déclarée est p?f <p?f 2 la variable p?f est un pointeur"&<p?f)&) 1 l(objet pointé est une onction$ int &<p?f)&@oat r), ou int &<p?f)&@oat) 1 l(objet pointé est une onctionretournant un entier+ a&ant un seul para".tre de t&pe ottant$ Attention 2Il ne aut surtout pas oublier les parenth.ses autour de <p?f , sans ,uoi leco"pilateur co"prendrait ,ue p?f est une onction retournant un pointeursur un entier+ a&ant un seul para".tre de t&pe ottant ]&'intért essentiel de telles variables est de pouvoir passer des<onctions en paramCtres = une <onction$ Bans un cas de ce %enre+ lepara".tre or"el doit <tre de t&pe ?pointeur de onction?$Exemple 26e pro%ra""e ci-apr.s per"et de calculer la valeur approchée de ladérivée d(une onction tri%ono"étri,ue 0cos+ sin ou tan1+ en un point choisipar l(utilisateur$ 5n utilise pour cela l(identité suivante+ per"ettant lecalcul approché de la dérivée d(une onction < au point x pour EP%#&A suisa""ent petit 2<'x 88 <xDEP%#&A+<x+EP%#&A2EP%#&A

inc!d# $stdio.h

??

7/21/2019 TPINFO


inc!d# $std!ib.hinc!d# $math.hd#fin# PLHMOQ& 0.00'

dob!# d#riv##(dob!# (p>f)(dob!#),dob!# ) a!c! d# !a d*riv*# d-n# fonction par n# #pr#ssion approch*#. {

r#trn(((p>f)(+PLHMOQ&)3(p>f)(3PLHMOQ&))(2PLHMOQ&));}

int main(void){

char r#pons#=-\n-;dob!# ;do{

printf("<*riv*#s d#s fonctions trionom*tri#s 8\n");printf("\tAcBosins\n");printf("\tAsBins\n");printf("\tAtBan#nt#\n");printf("\tABitt#r\n");printf("\totr# choi (c,s,t o ) 8 ");

ff!sh(stdot);if (r#pons#1=-\n-)

hi!# (#tchar()1=-\n-) ;scanf("%c",Xr#pons#);if ((r#pons#==-c-)(r#pons#==-s-)(r#pons#==-t-)){

printf("Pn #! point vo!#73vos ca!c!#r !a d*riv*# 8 ");

ff!sh(stdot);

scanf("%!f",X);}printf("\n");

sitch (r#pons#){

cas# -c- 8 printf("*s!tat 8 %f\n\n",d#riv##(Xcos,)); br#aK;

cas# -s- 8 printf("*s!tat 8 %f\n\n",d#riv##(Xsin,)); br#aK;

cas# -t- 8 printf("*s!tat 8 %f\n\n",d#riv##(Xtan,)); br#aK;

cas# -- 8 br#aK;d#fa!t 8 printf("Rap#7 c, s, t o 1\n\n");

}} hi!# (r#pons#1=--);#it(0);

}

6emar#ue -

[ien ,ue cela puisse paraDtre surprenant+ il n(& a aucune diérence+ tant la co"pilation ,u( l(e'écution+ entre les deu' s&nta'es d(appelsuivantes 2

d#riv##(Xcos,)d#riv##(cos,)

E'ercice G=-

CRYPTOGRAPHIE - CRYPTANALYE(Lisez entièrement l’énoncé avant de commencer !

?H

7/21/2019 TPINFO


2es deu parties suivantes peuvent 3tre traitées de mani)re indépendante 6seule la derni)re question de la partie

L s’appuie sur une #onction de la partie 57. 4l est conseillé de #aire deu pro&ets séparés a#in d’améliorer la

lisi$ilité des programmes.

PARTIE ! : CRYPTOGRAPHIE

0a >otation César est un al-orit'*e de cr/pta-e si*pliste utilisé pour censurer des propos c'oquants sur lesserveurs de Ne]s sur 6nternet +<senet" 0e principe de ce cr/pta-e consiste 2 e!ercer une rotation de l9alp'abetde A% positions vers l9avant" Cette transfor*ation ne concerne que les *ajuscules et *inuscules non accentuées"Les lett"es a##e$tuées% les $&m'"es et t&us les aut"es si($es )emeu"e$t i$#a$(és" 0e tableau suivant illustrela transfor*ation pour les lettres *inuscules1’a’ est transfor*é en ’n’, ’b’ en ’o’, etc"

<ne transfor*ation si*ilaire s9applique au! *ajuscules1 9(9 est transfor*é en 9N9, 9^9 en 9F9, etc"

1- )crire une fonction void PncrUptOin#'(char R) effectuant la rotation de César" )tablisse5 déj2sur papier la for*ule *at'é*atique per*ettant d9effectuer la transfor*ation +aussi bien sur des lettres*inuscules, que des *ajuscules" Co**e il s9a-it d9effectuer un c/cle sur &H lettres pense5 2 la fonction*odulo +\" #i vous n’/ arrive5 pas par le biais de cette for*ule, re*arque5 plus si*ple*ent que vous

pouve5 traiter l9alp'abet en deu! *oitiés +2 la pre*i.re *oitié on ajoute A%, 2 la deu!i.*e on enl.ve A%" N9oublie5 pas non plus que les caract.res en C +variables de t/pe char sont considérés co**e des no*bres

et qu9on peut donc leur appliquer des opérations arit'*étiques, ainsichar c = ’e’+2;

est une instructionvalable +et c vaut -.

&: Proposer une *ét'ode +ou une fonction pour décr/pter une c'aine de caract.res cr/ptée par la *ét'odede César"

%: )crire une nouvelle fonction de c'iffre*ent par rotation, c9est:2:dire acceptant tout t/pe de décala-e devaleur dec 1 void PncrUptOin#2(char R, int d#c) +il faut utiliser l’opérateur *odulo \

;: Propose5 une fonction pour décr/pter une c'aine de caract.re cr/ptée par la fonctionPncrUptOin#2()"

?: 0es *ét'odes de c'iffre*ent par transposition sont facile*ent « cassables » +cf" e!ercice suivant" Pour

renforcer la robustesse de notre pro-ra**e de cr/pto-rap'ie, on propose de réaliser une fonction desubstitution utilisant une clé secr.te sous la for*e d’un *ot, _)P`6> dans le tableau suivant" )crire unefonctionA char ONR(char c!#) qui -én.re sous for*e de 0ooT:<p:=able +0<= la table decorrespondance, c’est:2:dire qu’2 un caract.re donné correspond un autre caract.re" )crire é-ale*ent lafonction void 9ffich#ONR( char !) qui affic'e la 0<= -énérée"

Lettre

normale( ^ C D ) 3 ` 6 U 0 M N F P G > # = < V $ _

Lettre

cryptée+ E P H I R ( ^ C D 3 U 0 M N F G # = < V $

A <tilise5 une double allocation d/na*ique sur un pointeur c'ar , et renvo/er ce pointeur"?8

7/21/2019 TPINFO


H: )crire une nouvelle fonction de c'iffre*ent s’appu/ant sur le tableau de correspondance -énéré par lafonction ONR()1 void PncrUptOin#D(char R, char c!#)

8: )crire une fonction void PncrUptIi!#(IMOP in, IMOP ot, int m#thod#)qui per*et par l’appel de la fonction PncrUptOin#() de cr/pter un fic'ier te!te par la *ét'ode c'oisie par l’utilisateur .

0e no* du fic'ier 2 cr/pter ainsi que la *ét'ode de cr/pta-e +César, décala-e ou substitution avec clé dec'iffre*ent seront de*andés 2 l’utilisateur dans la fonction main()" 0e fic'ier cr/pté correspondant seraécrit dans un fic'ier te!te de sortie et é-ale*ent affic'é dans la console"

J: )crire une fonction void <#crUptIi!#(IMOP in, IMOP ot, int m#thod#)qui per*et dedécr/pter un fic'ier te!te par la *ét'ode c'oisie. 0e no* du fic'ier 2 cr/pter et le nu*éro de la *ét'odeseront de*andés 2 l’utilisateur dans la fonction main()" 0e fic'ier cr/pté correspondant sera écrit dans unfic'ier te!te de sortie et é-ale*ent affic'é dans la console"

K: 3aire le pro-ra**e principal et un *enu per*ettant 2 l’utilisateur de cr/pter ou de décr/pter un fic'ier par la *ét'ode de son c'oi!"

PARTIE , : CRYPTANALYE

0es al-orit'*es t/pe « rotation de César », ou plus -énérale*ent les al-orit'*es de c'iffre*ent par substitution,sont des al-orit'*es de cr/pta-e asse5 si*ples 2 « casser »" ( partir d9une anal/se statistique des s/*boles du*essa-e c'iffré, il est possible d’identifier des lettres et de re*onter, avec un peu de *ét'ode, jusqu’au *essa-ed’ori-ine" <ne pre*i.re approc'e pour casser ces al-orit'*es peut consister 2 rec'erc'er le s/*bole le plusfréquent dans le *essa-e c'iffré et le re*placer par le s/*bole le plus fréquent dans le lan-a-e du te!te clair"Par e!e*ple le e est le s/*bole le plus utilisé dans les te!tes franBais et an-lais"

Nous allons tenter de *ettre en place cette anal/se statistique sur un te!te c'iffré par substitution"

A: Définisse5 dans un pre*ier te*ps une structure de donnée HUmbo!# per*ettant de stocTer un caract.re etson no*bre d’occurrences +utilise5 le t/pedef struct@

&: 3aire une fonction HUmbo!# Ii!#Htat(IMOP fich ,int nbHUmbo!#) qui per*et deconstruire 2 partir de fich la liste des s/*boles" 0a variable nbHUmbo!# est un pointeur per*ettant derécupérer dans le pro-ra**e principal le no*bre total de s/*boles présents dans le te!te" Pour ran-er letableau de s/*boles, vous utilisere5 l’allocation d/na*ique de *é*oire" 3aire le pro-ra**e per*ettant delire et de stocTer les s/*boles en *é*oire" 0es s/*boles autres que des lettres ne seront pas *é*orisés etles lettres *inuscules et *ajuscules seront considérées équivalentes" Pour c'aque s/*bole ajouté, initialiser son no*bre d’occurrence 2 A, si le s/*bole e!iste déj2, incré*enter son no*bre d’occurrences"

Dans le pro-ra**e principal, pro-ra**e5 l’affic'a-e de l’ense*ble des s/*boles présents dans le te!te,leur occurrence et leur probabilité d’apparition +qui est un no*bre réel é-al 2 A sur le no*bred’occurrences"

HUmbo!# 08 i &b Qccr#nc#8 F'F0 Lroba8 0.'26]

HUmbo!# '8 &b Qccr#nc#8 ]0D6 Lroba8 0.0F]0HUmbo!# 28 # &b Qccr#nc#8 E]0F Lroba8 0.0]̂ ]HUmbo!# D8 s &b Qccr#nc#8 E62F Lroba8 0.0]]6

- 3aire une fonction de tri void Rri(HUmbo!# t, int nbHUmbo!#) qui prendra en entrée un pointeur sur #/*bole +ou sur un tableau de s/*boles et le no*bre total de #/*boles" Cette fonction per*ettra de classer dans l’ordre des fréquences décroissantes l’ense*ble des s/*boles" Vous pouve5utiliser l’al-orit'*e de tri de votre c'oi!"

?: (ffic'e5 dans le pro-ra**e principal le résultat du tri des s/*boles par fréquence décroissante"

H: (fin de voir s’il peut s’a-ir d’un c'iffre*ent par décala-e et 2 partir du résultat du tri précédent, on calcule pour les ; s/*boles les plus fréquents le décala-e correspondant avec les s/*boles les plus fréquents enfranBais et en an-lais +e, s, a, n en franBais, et e, t, o, a en an-lais voir les tableau! ci:dessous"

?J

7/21/2019 TPINFO


Statistiues Lettres Fran2aises

3 A 8.11 % 4 N 7.68 %

* 0341 O 5360

C 7374 6386

- 9364 0347

1 E 17.69 % R ;397

F 1317 2 S 8.87 %

< 1318 T 399

H 039 = 5367

I 369 > 1364

? 0314 @ 030;

% 0306 A 0357

L 5388 B 036;

6368 D 0316

Statistiues Lettres "n&laises

4 A 7.81 % E 364

* 1364 3 O 8.21 %

C 6387 6315

- 9311 0319

1 E 13.05 % R ;3;9

F 6344 S ;39;

< 1378 2 T 9.02 %

H 5345 = 63

I ;3 > 1300

? 0367 @ 1398

% 0396 A 0370

L 73;0 B 1351

63;6 D 0308

Pn francais 8HUmbo!# 08 i Lroba8 0.'26] <#ca!a# av#c #8 4HUmbo!# '8 Lroba8 0.0F]0 <#ca!a# av#c s8 EHUmbo!# 28 # Lroba8 0.0]^] <#ca!a# av#c a8 4HUmbo!# D8 s Lroba8 0.0]]6 <#ca!a# av#c n8 E

Pn an!ais 8HUmbo!# 08 i Lroba8 0.'26] <#ca!a# av#c #8 4HUmbo!# '8 Lroba8 0.0F]0 <#ca!a# av#c t8 4HUmbo!# 28 # Lroba8 0.0]^] <#ca!a# av#c o8 '6HUmbo!# D8 s Lroba8 0.0]]6 <#ca!a# av#c a8 '^

8: )nsuite, applique5 un décala-e +vous pouve5 réutiliser les fonctions de la partie A sur les lettres *inusculeset les lettres *ajuscules correspondant au! valeurs trouvées +;, ?, AH,AJ" (ffic'e5 le résultat dans la console

et dans un fic'ier te!te pour voir si le fic'ier est lisible"

Rappels:

Qv#rtr# d-n fichi#r #n !#ctr#IMOP fichi#r'=fop#n("!pp.tt", "r");

:oc!# por r*cp*r#r !#s !in#s d# "fichi#r'" #t d# !#s stocK#r dans chain#Oa boc!# s-arr_t# !ors# !# point#r d# !#ctr# att#int !a fin d fichi#rhi!#(1f#of(fichi#r')){

char chain#A'00B;f#ts(chain#,'00,fichi#r');

}fc!os#(fichi#r');

Qv#rtr# d-n fichi#r #n *critr#IMOP fichi#r2=fop#n("c!air.tt", "");Pcritr# d# !a chain# d# caract#r# ` 7#phir dans !# fichi#r2char chain#A'0B= "7#phir";fprintf(fichi#r2,"%s",chain#);fc!os#(fichi#r2);

?K

7/21/2019 TPINFO


ANNEXE : INTRODUCTION AU S*STEME +INDO+S,MS-DOS

1> S40?me e e0io. e @i6ier

a# 9=e0 6e 89=9. @i6ier Un fichier est une suite d’octets2 (de 0 à plus de 2 Go) stock ée sur un disque. Les disques

ont pour nom a: , c: , p:, etc... Aucune structure n’est imposée à un fichier par le système, et

aucune signification n’est attachée à son contenu – la signification des octets dépend

uniquement des programmes qui manipulent le fichier. Windows reconna î t deux grandes

catégories de fichiers.

Les fichiers ordinaires ou réguliers sont des fichiers sur disque dont le contenu est non

structuré et correspond donc à une suite de caractères caractérisée par sa longueur (qui permet

en particulier de détecter la fin de fichier).

Les répertoires voient leur contenu interprété par un certain nombre de fonctions dusystème : ils permettent de structurer l’ensemble des fichiers en arborescence et définissent un

mécanisme de désignation des fichiers indépendant de leur localisation dans les tables du

système et sur le disque.

Un répertoire n’est rien d’autre qu’un fichier contenant une liste de cha î nes de caractères

ou noms de fichier. L’organisation qui s’ensuit est donc arborescente et suppose, pour être

opérationnelle, l’existence d’une origine. symbolique. Cette origine est le nom du disque.

# [email protected] ao;9e o9 re;a0i/e

La figure ci-contre fournit un exemple d’arborescence de fichiers. Pour tout fichier, il

existe au moins un chemin menant de la racine jusqu’à lui. La liste des liens physiques qu’il

faut utiliser pour arriver à ce fichier l’identifie sans ambiguïté : elle constitue un chemin

d’accès long ( full-pathname) ou réf érence absolue du fichier. Si les liens rencontrés sur un

chemin de la racine vers un fichier sont successivement U, paul, travail et toto.c, la réf érence

absolue du fichier s’écrit symboliquement P:U\paul\travail\toto.c . Une réf érence absolue

commence toujours par le nom du disque.

Afin de faciliter les repérages, à tout processus (activité dans le système) est associé un

répertoire de travail. La désignation d’un fichier par rapport au répertoire de travail est

appelée réf érence relative (short pathname) et s’écrit sous la forme d’une suite de liens

séparés par le caractère \ : elle correspond à un chemin allant du répertoire de travail à un

fichier. La réf érence absolue d’un fichier se d

éduit d’une r

éf érence relative en lui ajoutant en

préfixe la réf érence absolue du répertoire de travail. Ainsi, dans l’exemple précédent, si le

répertoire de travail est P: \U\paul, le fichier dont nous avons donné la réf érence absolue aura

comme réf érence relative travail\toto.c.

Ce type de repérage est encore facilité par un mécanisme permettant de remonter dans

l’arborescence. Le lien « .. » contenu dans un répertoire est toujours associé au répertoire

unique dont il est le descendant. De plus, le lien « . » est utilisé par le répertoire pour se

désigner lui même. Ainsi, ..\claude\C est une réf érence relative parfaitement valide si le

répertoire de travail est, par ex. P: \U\denise. De même, et bien qu’elles soient inutilement

compliquées, les réf érences ..\.\denise\..\..\soft ou jeux\..\travail\toto.c sont valides…

& O#tet 1 une quantité d’infor*ation de J bits" Pour nous, un octet est équivalent 2 uncaract.re"

HL

7/21/2019 TPINFO


2> Comma.e e ae MS-DOS,+INDO+S-NT

Les commandes de base sont celles qui permettent d’obtenir des informations générales ou

de manipuler l’environnement immédiat de l’utilisateur : répertoire courant, fichiers, tâches.

Elles sont utilisées dans les fenêtres MS-DOS

#) répertoire

c'an-e le répertoire de travail")i" O #ic'ierP

Pour c'aque #ic'ier qui est un répertoire, )i" donne la liste des no*s de fic'iers qu’il contient" Pour c'aque #ic'ier ordinaire, )i" rép.te son no*" Dans les deu! cas, les options per*ettent de de*ander des infor*ationssupplé*entaires sur les fic'iers" Par défaut, la sortie est triée par ordre alp'abétique" #i aucun #ic'ier n’estdonné en ar-u*ent, c’est le répertoire courant +" qui est traité" Par défaut encore, les références i*plicites defic'iers +c’est:2:dire dans les répertoires e!plorés co**enBant par le caract.re " ne sont pas traitées

type O #ic'ier P

copie le contenu des fic'iers donnés en para*.tre sur la sortie standard +l9écran" 09arrêt du défile*ent estobtenu en appu/ant si*ultané*ent sur les touc'es ctrl et s" Pour continuer 2 affic'er le contenu du fic'ier,faire 2 nouveau ctrl s"

copy ficSource ficCible (voir également la commande xcopy)copy ficSource1 [ ficSource2… ] repCible

Copie de fic'iers" Dans la pre*i.re for*e présentée, ni #ic,ource, ni #icCi$le ne sont des répertoires ni necorrespondent au *ê*e no* 1 #p copiera le contenu de #ic,ource dans #icCi$le" #i #icCi$le e!iste, #&py

écrasera son contenu0a deu!i.*e for*e per*et de copier plusieurs fic'iers dans le répertoire repCi$le" 0es no*s des fic'iers sontconservés dans le nouveau répertoire" C’est une erreur que l’un des #ic,ource soit un répertoire ou querepCi$le n’en soit pas un ou n’e!iste pas"

rename source cible

"e$ame déplace le fic'ier no**é source vers ci$le" 6l s’a-it d’un c'an-e*ent de no* du fic'ier" ,ource et ci$le

doivent être des no*s différents" #i ci$le e!iste déj2, son contenu précédent est détruit

del fichier : destruction d'un fichier.

mkdir r é pertoire : création d'un répertoire

"m)i" répertoire 1 suppression d9un répertoire et de toute l9arborescence de fic'iers qu9il contient"

print fichier : impression de fichier. Attention le fichier ne doit contenir que des caractères

imprimables.

help : aide sur toutes les commandes. Donne la liste des commandes;

help nom de commande : aide sur une commande particulière

Remarques :

- toutes ces commandes admettent de nombreuses options. Pour avoir le détail de ces

options utiliser la commande help

- En dehors des fenêtres MS-DOS, l'équivalent de la plupart de ces commandes peut

être effectué par l'explorateur Windows.

Liste complète des commandes MS-DOS/WINDOWS-NT :9;O;Q&6 ;onv#rtit !#s !ist#s d# contr!# d-acc5s (9;O) d# O9&?9& H#rv#"r QH2.9R L!anifi# !-#*c"tion d# command#s o" proramm#s s"r "n ordinat#"r.9RR=M: ;han# o" affich# !#s attrib"ts d-"n fichi#r.:=P9 9ctiv# o" d*sactiv# !# contr!# d# ;R=O+;.;9OO 9pp#!!# "n fichi#r d# command#s d#p"is "n a"tr# fichi#r d# command#s.

;< ;han# d# r*p#rtoir# o" affich# !# r*p#rtoir# #n co"rs.;Y;L ;han# !a pa# d# cod# activ# o" affich# son n"m*ro.;Y<M= ;han# d# r*p#rtoir# o" affich# !# nom d" r*p#rtoir# #n co"rs.;Y<H 6*rifi# "n dis"# #t affich# "n r#!#v* d-*tat.;OH Pffac# !-*cran.

HA

7/21/2019 TPINFO


;?< Oanc# "n# no"v#!!# instanc# d# !-int#rpr*t#"r d# command#s d# Sindo0s &R.;Q?L ;ompar# !#s cont#n"s d# d#" fichi#rs o" ro"p#s d# fichi#rs.;Q&6P=R ;onv#rtit d#s vo!"m#s I9R o" YLIH #n vo!"m#s &RIH. 6o"s n# po"v#7 pas conv#rtir !# !#ct#"r co"rant.;QLC ;opi# "n o" p!"si#"rs fichi#rs.<9RP 9ffich# o" modifi# !a dat#.<PO H"pprim# "n o" p!"si#"rs fichi#rs.<M= 9ffich# !a !ist# d#s fichi#rs d-"n r*p#rtoir#.<MH;Q?L ;ompar# !#s cont#n"s d# d#" dis"#tt#s.<MH;QLC ;opi# !# cont#n" d-"n# dis"#tt# s"r "n# a"tr#.

<QHPC =app#!!# d#s command#s #ntr*#s, p#rm#t d# !#s modifi#r #t d# cr*#r d#s macros.P;YQ 9ffich# d#s m#ssa#s J !-*cran o" activ#d*sactiv# !-afficha# d#s command#s.P&<OQ;9O Htopp# !a !oca!isation d#s modifications d# !-#nvironn#m#nt dans "n fichi#r d# command#s.P=9HP H"pprim# "n o" p!"si#"rs fichi#rs.P@MR "itt# !-int#rpr*t#"r d# command#s (;?<.P@P).I; ;ompar# d#" fichi#rs o" ro"p#s d# fichi#rs, #t affich# !a diff*r#nc#.IM&< ;h#rch# "n# chaWn# d# caract5r#s dans "n o" p!"si#"rs fichi#rs.IM&<HR= ;h#rch# d#s chaWn#s d# caract5r#s dans "n o" p!"si#"rs fichi#rs.IQ= P*c"t# "n# command# s"r cha"# fichi#r d-"n ro"p# d# fichi#rs.IQ=?9R Iormat# "n dis"# po"r "ti!isation av#c Sindo0s &R.TQRQ Lo"rs"it !-#*c"tion d-"n fichi#r d# command#s G "n# !in# id#ntifi*# par "n# *ti"#tt#.T=9IR9:O L#rm#t J Sindo0s &R d-affich#r "n /#" d# caract5r#s #n mod# raphi"#.YPOL 9ffich# d#s informations s"r !#s command#s d# Sindo0s &R.MI P*c"t# "n# command# si "n# condition #st v*rifi*#.PC: ;onfi"r# "n c!avi#r po"r "n !ana# sp*cifi"#.O9:PO ;r*#, modifi# o" s"pprim# !# nom d# vo!"m# d-"n dis"#.#t !-#*c"t#.?< ;r*# "n r*p#rtoir#.?<M= ;r*# "n r*p#rtoir#.

?Q<P ;onfi"r# !#s p*riph*ri"#s.?Q=P 9ffich# !a sorti# ecran par ecran.?Q6P <*p!ac# "n o" p!"si#"rs fichi#rs d-"n r*p#rtoir# J "n a"tr# s"r !# m_m# !#ct#"r.L9RY 9ffich# o" definit !# ch#min d# r#ch#rch# d#s fichi#rs #*c"tab!#s.L9NHP Mnt#rrompt !-#*c"tion d-"n fichi#r d# command#s #t affich# "n m#ssa#.LQL< =#sta"r# !a va!#"r pr*c*d#nt# d" r*p#rtoir# co"rant #nr#istr* par LNHY<.L=M&R Mmprim# "n fichi#r t#t#.L=Q?LR ;han# !-invit# d# Sindo0s &R.LNHY< Pnr#istr# !# r*p#rtoir# co"rant p"is !# chan#.=< H"pprim# "n r*p#rtoir#.=P;Q6P= =*c"p5r# !-information !isib!# d-"n dis"# d*f#ct"#".=P? Mns5r# "n comm#ntair# dans "n fichi#r d# command#s o" ;Q&IMT.HCH.=P& =#nomm# "n o" p!"si#"rs fichi#r(s).=P&9?P =#nomm# "n o" p!"si#"rs fichi#r(s).=PLO9;P =#mp!ac# d#s fichi#rs.=PHRQ=P =#sta"r# d#s fichi#rs sa"v#ard*s av#c !a command# :9;NL.=?<M= H"pprim# "n r*p#rtoir#.HPR 9ffich#, definit o" s"pprim# "n# variab!# d-#nvironn#m#nt Sindo0s &R.

HPROQ;9O ;omm#nc# !a !oca!isation d#s chan#m#nts d# !-#nvironn#m#nt dans "n fichi#r d# command#s.HYMIR ;han# !a position d#s param5tr#s r#mp!aab!#s dans "n fichi#r d# command#s.HQ=R Rri# son #ntr*#.HN:HR 9ff#ct# "n# !#ttr# d# !#ct#"r G "n ch#min.HR9=R Oanc# "n# f#n_tr# po"r !-#*c"tion d" proramm# o" d# !a command#.RM?P 9ffich# o" definit !-h#"r# d# !-hor!o# int#rn# d" sUst5m#.RMROP Ii# !# titr# d# !a f#n_tr# po"r "n# s#ssion ;?<[email protected]=PP =#pr*s#nt# raphi"#m#nt !-arbor#sc#nc# d-"n !#ct#"r o" d-"n ch#min.RCLP 9ffich# !# cont#n" d-"n fichi#r t#t#.6P= 9ffich# !# n"m*ro d# v#rsion d# Sindo0s &R.6P=MIC 9ctiv#d*sactiv# !a v*rification d# !-*crit"r# s"r dis"#.6QO 9ffich# !# nom #t !# n"m*ro d# s*ri# d" vo!"m#.@;QLC ;opi# d#s fichi#rs #t d#s r*p#rtoir#s.

/iii> III Reire60io. e e.0r5e-or0ie

L'entrée standard est le clavier, la sortie standard l'écran. Tous deux sont en fait considérés

comme des fichiers.

On peut substituer à ces fichiers d'autres fichiers texte. Ainsi on peut conserver la trace de

l'exécution d'un programme dans un fichier ou remplacer son entrée par une suite de

caractères stock és dans un fichier.

La redirection de la sortie se fait à l'aide du caractère ">". Par exemple :

mon-prog.exe affiche ces résultats sur l'écran

mon-prog.exe > resultat.txt stocke ces résultat dans le fichier resultat.txt.

La redirection de l'entrée se fait à l'aide du caractère "<".

H&

7/21/2019 TPINFO


Par exemple, mon-prog.exe < entree.txt prend les caractères contenus dans le fichier

entree.txt au lieu du clavier.

Documents

TPINFO