M1102-TD3 Exercice5 Corrigé

[Algo]
fonction SaisirEntierSupX  (Invite : in string, MsgErr : in string, X : in entier_naturel) renvoie entier_naturel
debut
	declarer N : entier_naturel;
	boucle
		afficher (Invite);
		saisir(N);
		si (N > X) sortie;
		afficher (MsgErr);
		ligne_suivante;
	fboucle
	renvoie N;
fin

fonction find (Val : in entier, TabInt : in tableau_de entier) renvoie entier_naturel
debut
	allonger (TabInt, 1);
	TabInt [taille (TabInt) - 1] <- Val;

	declarer Pos : entier_naturel;
	Pos <- 0;
	tant_que (TabInt[Pos] ne_vaut_pas Val)
	faire
		Pos <- Pos + 1;
	ffaire
	renvoie Pos;
fin

procedure AfficheTabInt (TabInt : in tableau_de entier, Sep : in caractere, NbParLigne : in entier_naturel)
debut

	//cpt designe le nombre d'affichage déjà effectué
	declarer cpt :entier_naturel;
	cpt <- 0;

	pour (i variant_de 0 a taille(TabInt) - 1)
	faire

		afficher (TabInt [i]);
		cpt <- cpt + 1;
		si (modulo (cpt, NbParLigne) vaut 0)
			ligne_suivante;
		sinon
			afficher (Sep);
		fsi
	ffaire
fin

// une première version pas du tout efficiente qui utilise find ()
//procedure GenereTabInt (TabInt : in_out tableau_de entier, M : in entier)
//debut
//	declarer Val : entier;
//	pour (Nb variant_de 0 a taille (TabInt) - 1)
//	faire
//		boucle
//			Val <- Rand (1, M);
//			declarer Pos : entier_naturel;
//			Pos <- find (Val, TabInt);
//			si (Pos vaut taille (TabInt)) sortie;
//		fboucle
//		TabInt [Nb] <- Val;
//	ffaire
//fin

// une seconde version qui utilise la technique des sentinelles
//procedure GenereTabInt (TabInt : in_out tableau_de entier, M : in entier)
//debut
//	pour (Nb variant_de 0 a taille (TabInt) - 1)
//	faire
//		boucle
//			TabInt [Nb] <- Rand (1, M);
//			declarer Pos : entier_naturel;
//			Pos <- 0;
//			tant_que ((Pos ne_vaut_pas Nb) ET_ALORS (TabInt[Pos] ne_vaut_pas TabInt[Nb]))
//			faire
//				Pos <- Pos +1;
//			ffaire
//			si (Pos vaut Nb) sortie;
//		fboucle
//	ffaire
//fin

//une troisième qui fait moins de tests que la précédente
procedure GenereTabInt (TabInt : in_out tableau_de entier, M : in entier)
debut
	//pas besoin de test pour la première case tu tableau, l'élément généré est forcément unique
	TabInt [0] <- Rand (1, M);

	//du coup, on change la borne inf
	pour (Nb variant_de 1 a taille (TabInt) - 1)
	faire
		boucle
			TabInt [Nb] <- Rand (1, M);
			declarer Pos : entier_naturel;
			Pos <- 0;
			//un test de moins ici, on s'arrête a 
                        // la sentinelle
			jusqua (TabInt[Pos] vaut TabInt[Nb])
			faire
				Pos <- Pos +1;
			ffaire
			//du coup le test de sortie change 
                        //puisqu'on ne peut atteindre la sentinelle
			si (Pos vaut Nb) sortie;
		fboucle
	ffaire
fin

algorithme TestDeGenereTabInt
debut
	declarer N : entier_naturel;
	afficher ("entrer la taille du tableau : ");
	saisir (N);

	declarer TabInts : tableau_de N entier;

	declarer M : entier_naturel;
	afficher ("entrer la valeur maximale du tableau : ");
	M <- SaisirEntierSupX ("entrer la valeur maximale du tableau : ", "Plus grand que la taille du tableau svp ...", N);

	GenereTabInt (TabInts, M);

	AfficheTabInt (TabInts, '\t', 10);
	ligne_suivante;
fin[/Algo]

M1102-TD3 Exercice6

On souhaite écrire le sous-programme GenereTabInt (). Celui-ci doit générer un tableau de N entiers aléatoires distincts dans [1..M] (M > N). Dans cet exercice, à chaque itération, on va générer un nombre aléatoire, que l’on va ranger ou non dans le tableau. L’algorithme de haut niveau est le suivant :
[Algo]

tant_que (Nb < N)
faire
GenererEntierAleatoire;
si (LEntierAleatoireNAppartientPasAuTableau)
StockerLEntierAleatoireDansTabInt;
fsi
ffaire

[/Algo]

Ecrire l’algorithme qui teste GenereTabInt ().

M1102-TD3 Exercice6 Corrigé

[Algo]
fonction SaisirEntierSupX (Invite : in string, MsgErr : in string, X : in entier_naturel) renvoie entier_naturel
debut
declarer N : entier_naturel;
boucle
afficher (Invite);
saisir(N);
si (N > X) sortie;
afficher (MsgErr);
ligne_suivante;
fboucle
renvoie N;
fin

fonction find (Val : in entier, TabInt : in tableau_de entier) renvoie entier_naturel
debut
allonger (TabInt, 1);
TabInt [taille (TabInt) – 1] <- Val;

declarer Pos : entier_naturel;
Pos <- 0;
tant_que (TabInt[Pos] ne_vaut_pas Val)
faire
Pos <- Pos + 1;
ffaire
renvoie Pos;
fin

procedure AfficheTabInt (TabInt : in tableau_de entier, Sep : in caractere, NbParLigne : in entier_naturel)
debut

//cpt designe le nombre d’affichage déjà effectué
declarer cpt :entier_naturel;
cpt <- 0;

pour (i variant_de 0 a taille(TabInt) – 1)
faire

afficher (TabInt [i]);
cpt <- cpt + 1;
si (modulo (cpt, NbParLigne) vaut 0)
ligne_suivante;
sinon
afficher (Sep);
fsi
ffaire
fin

procedure GenereTabInt (TabInt : in_out tableau_de entier, M : in entier)
debut
declarer Nb : entier_naturel;
Nb <- 0;
tant_que (Nb < taille (TabInt))
faire
declarer Alea : entier_naturel;
Alea <- Rand (1, M);
declarer Pos : entier_naturel;
Pos <- 0;
tant_que (Pos < Nb ET_ALORS TabInt[Pos] ne_vaut_pas Alea)
faire
Pos <- Pos + 1;
ffaire
si (Pos vaut Nb)
TabInt [Nb] <- Alea;
Nb <- Nb + 1;
fsi
ffaire
fin

algorithme TestDeGenereTabInt
debut
declarer N : entier_naturel;
afficher ("entrer la taille du tableau : ");
saisir (N);

declarer TabInts : tableau_de N entier;

declarer M : entier_naturel;
M <- SaisirEntierSupX ("entrer la valeur maximale du tableau : ", "Plus grand que la taille du tableau svp …", N);

GenereTabInt (TabInts, M);

AfficheTabInt (TabInts, ‘\t’, 10);
ligne_suivante;
fin[/Algo]

M1102-TD3 EXERCICE 7

On souhaite écrire le sous-programme GenereTabInt (). Celui-ci doit générer un tableau de N entiers aléatoires distincts dans [1..M] (M vaut N).