Se connecter avec
S'enregistrer | Connectez-vous

Exercices d'algorithmiques

Dernière réponse : dans Programmation

Salut,
je suis en train de réviser l'algo1 et l'algo2 (ce qui correspond aux 2 semestres de licence info) pour les rattrappages de septembre.
Voici les exercices d'algo1 et d'algo2 que je n'arrive pas à faire
l'énoncé sera mis en noir et les questions en bleu

Algo1:
Tri de suffixe
On considère une table de caractères,y,de dimension n.Le but de cet exercice est de calculer la table Pos de dimension n pour laquelle

y[Pos[0]..n-1]<y[Pos[1]..n-1]<....<y[Pos[n-1]..n-1]

ou y[i...n-1] = yy[i+1]...y[n-1] désigne le suffixe de y qui est à la position i.
La table fournit ainsi les suffixes non vides de y en ordre croissant (pour l'ordre lexicographique).

1)Ecrire en C le code de la fonction strcmp de prototype
int strcmp(const char *s, const char *t);

2)Ecrire en C une fonction d'en-tete
int Partage(int d, int f, int p) qui appliquée aux suffixes dont les positions sont Pos[d], Pos[d+1], ..., Pos[f] et au pivot y[Pos[p]...n-1] = z (d<=p<=f), effectue le "partage" des suffixes considérés selon le pivot (en modifiant Pos) et produit le plus petit indice k (d<=k<=f) pour lequel y[Pos[k]...n-1] = z

3)Ecrire un algorithme de classement des suffixes de y qui produit la table Pos en utilisant la fonction de partage du 2. Quelle table Pos obtient-on avec y = "abracadabra"?

4)Donnez une majoration asymptotique des temps d'execution de
Partage(d,f,p) et de l'algorithme de classement. Quel peut etre son temps moyen d'éxécution en supposant que le temps moyen pour comparer 2 suffixes est O(logn)





Arbres feuillus
Les arbres considérés dans cet exercice sont des arbres binaires feuillus (complets) dont les noeuds sont des entiers . À un tel arbre A on associe le mot
Str(A) = {1 si A est réduit à une feuille,
{0Str(G)Str(D) si A = (r,G,D),

ou r est la racine de A, G son sous-srbre gauche et D son sous-abre droit.

1)Calculer Str((1,(2,(3),(4)),(5))) et Str((1,(2),(3,(4),(5))))
Dessinez les arbres qui correspondent aux mots 0001111 et 0101011

2)Soit x = Str(A) et y = Str(B) pour 2 arbres A et B
Montrez que x = y si et seulement si A et B sont égaux à la numérotaion près de leurs noeuds (autrement dit, s'il existe une bijection entre les noeuds qui respecte la structure de l'arbre)

3)Indiquer comment mémoriser dans un fichier le code obtenu par la méthode de Huffman, en adaptant la fonction Str à appliquer à l'arbre de Huffman de codage

4)Ecrire une fonction C qui produit sur la sortie standart x = Str(A) pour un arbre A

5)Ecrire une fonction C qui, à partir d'un mot binaire Str(A) sur l'entée standart ,reconstruit l'arbre A




Algo2:

Sous-mots

Soient 2 mots x et y supposés déclarés en C par:

char x[100]; char y[100];

1)Écrire en C une fonction qui teste si x est un sous-mot de y

2)Ecrire en C une fonction qui calcule lsc(x,y),la longueur maximale des sous-mots communs à x et y

3)Calculer la table Tx,y relative aux mots x = agctga et y = cagatcagag et définie par:

Tx,y[i,j] = lsc(x[0]x[1]...x[i-1],y[0]y[1]...y[j-1])

ou i = 0,1...|x| et j= 0,1...|y|.(Pour i = 0 on convient x[0]x[1]...x[i-1] est le sous mot vide; meme convention avec y[0]y[1]...y[j-1] quand j = 0)

4)Quels sont les plus longs sous-mots communs à agctga et cagatcagag?.
Indiquer comment calculer un sous mot commun à x et y et de longeur lsc(x,y) à partir de la table Tx,y[/b]

Autres pages sur : exercices algorithmiques

Lassé par la pub ? Créez un compte
Expert Programmation

Je te propose de t'aider à t'aider.

Alors, on commence par le début.
  1. int strcmp(const char *s, const char *t);
La 1ère chose à faire, c'est aller lire la doc de la fonction. Ensuite, on essaie de faire pareil. A toi de nous trouver la définition ( $man strcmp ), puis de proposer un bout d'algo. On verra ensuite comment en faire du C.

Citation :
Je te propose de t'aider à t'aider.

Alors, on commence par le début.
  1. int strcmp(const char *s, const char *t);
La 1ère chose à faire, c'est aller lire la doc de la fonction. Ensuite, on essaie de faire pareil. A toi de nous trouver la définition ( $man strcmp ), puis de proposer un bout d'algo. On verra ensuite comment en faire du C.

Le man de cette fonction indique que la fonction renvoie une valeur positive si la chaine s précède la chaine t suivant l'ordre lexicographique,la valeur 0 si les 2 chaines sont égales et une valeur négative sinon
Expert Programmation

Ben voilà, alors on va faire ça. On regarde le premier caractère de chaque chaine. Si les deux sont nuls, elles sont vides, et on sort avec 0 comme résultat. Si l'un est plus grand que l'autre, je te propose de renvoyer 1 et de sortir. Sinon, on continue pour le caractère suivant. A toi d'écrire ça en C maintenant.

nberraoui a dit :
Le man de cette fonction indique que la fonction renvoie une valeur positive si la chaine s précède la chaine t suivant l'ordre lexicographique,la valeur 0 si les 2 chaines sont égales et une valeur négative sinon


repompe les sources de la glibc par exemple

Citation :
Ben voilà, alors on va faire ça. On regarde le premier caractère de chaque chaine. Si les deux sont nuls, elles sont vides, et on sort avec 0 comme résultat. Si l'un est plus grand que l'autre, je te propose de renvoyer 1 et de sortir. Sinon, on continue pour le caractère suivant. A toi d'écrire ça en C maintenant.


hé !!!
ptet on peut faire en récursivité ?

nberraoui a dit :
Voila ce que je propose

int strcmp(const char *s,const char *t){
int l1 = strlen(s);
int l2 = strlen(t);
for(i=0; i<l1; i++)
for(j=0; i<l2; j++)
if(s < t[j]) retun 1;
if(s > t[j]) retun 1;
else return 0;
}


bon, un ptit coup de pouce (et en récursif pour faire plaisir au neuneu) :

  1. (define (strcmp str1 str2)
    

  2. 	(charlstcmp (string->list str1) (string->list str2))
    

  3. )
    

  4. (define (charlstcmp lst1 lst2)
    

  5. 	(cond 
    

  6. 		(
    

  7. 			(null? lst1)
    

  8. 			(if (null? lst2) 0 1)
    

  9. 		)
    

  10. 		(
    

  11. 			(null? lst2)
    

  12. 			-1
    

  13. 		)
    

  14. 		(
    

  15. 			(eq? (car lst1) (car lst2))
    

  16. 			(charlstcmp (cdr lst1) (cdr lst2))
    

  17. 		)
    

  18. 		(
    

  19. 			(char>? (car lst2) (car lst1))
    

  20. 			-1
    

  21. 		)
    

  22. 		(
    

  23. 			#t
    

  24. 			1
    

  25. 		)
    

  26. 	)
    

  27. )


utilisation :

  1. (strcmp "aef" "ae")
Expert Programmation

Parce que le return 0, c'est quand les lettres sont identiques, alors si les deux premières sont identiques, on ne s'arrête pas, on attend de voir si les secondes le sont aussi, etc........

nexo59 a dit :
bon, un ptit coup de pouce (et en récursif pour faire plaisir au neuneu) :

  1. (define (strcmp str1 str2)
    

  2. 	(charlstcmp (string->list str1) (string->list str2))
    

  3. )
    

  4. (define (charlstcmp lst1 lst2)
    

  5. 	(cond 
    

  6. 		(
    

  7. 			(null? lst1)
    

  8. 			(if (null? lst2) 0 1)
    

  9. 		)
    

  10. 		(
    

  11. 			(null? lst2)
    

  12. 			-1
    

  13. 		)
    

  14. 		(
    

  15. 			(eq? (car lst1) (car lst2))
    

  16. 			(charlstcmp (cdr lst1) (cdr lst2))
    

  17. 		)
    

  18. 		(
    

  19. 			(char>? (car lst2) (car lst1))
    

  20. 			-1
    

  21. 		)
    

  22. 		(
    

  23. 			#t
    

  24. 			1
    

  25. 		)
    

  26. 	)
    

  27. )


utilisation :

  1. (strcmp "aef" "ae")



Ton code m'a lair bizarre il n'y a pas quelqu'un qui a plus simple ou plus compréhensible pour moi?

Voila du code vite fait, j'ai pas essaye ed compiler alors vive les erreurs :D 
  1. strcmp(char *str1,char* str2)
    

  2. {
    

  3. int l_mini=(strlen(str1)<strlen(str2)?strlen(str1):strlen(str2));
    

  4. bool fini=false;
    

  5. short res=0;
    

  6. int i=0;
    

  7. while(i<l_mini && !fini)
    

  8. {
    

  9. 	if(str1[i]<str2[i])
    

  10. 	{
    

  11. 		res=-1;
    

  12. 		fini=true;
    

  13. 	}
    

  14. 	else if(str1[i]>str2[i])
    

  15. 	{
    

  16. 		res=1;
    

  17. 		fini=true;
    

  18. 	}
    

  19. 	else
    

  20. 		i++;
    

  21. }
    

  22. if(res==0 && strlen(str2)>l_mini)
    

  23. {
    

  24. 	res=-1;
    

  25. }
    

  26. else if(res==0 && strlen(str1)>l_mini)
    

  27. {
    

  28. 	res=1;
    

  29. }
    

  30.  
  31. return res;
    

  32. }

m <- minimum(longueur(chaine1),longueur(chaine2))
pour i allant de 0 a m
faire
si chaine1[i] > chaine2[i]
retour 1
si chaine1[i] < chaine2[i]
retour -1
fin pour
si longueur(chaine 1) > longueur(chaine2)
retour 1
si longueur(chaine 1) < longueur(chaine2)
retour -1
retour 0

Expert Programmation 

  1. int strcmp ( const char * s, const char * t )
    

  2. {
    

  3. 	int i = 0;
    

  4. 	while ( s [ i ] && t [ i ] )
    

  5. 	{
    

  6. 		if ( s [ i ] > t [ i ] ) return  1;
    

  7. 		if ( s [ i ] < t [ i ] ) return -1;
    

  8. 		i ++;
    

  9. 	}
    

  10. 	if ( s [ i ] > t [ i ] ) return  1;
    

  11. 	if ( s [ i ] < t [ i ] ) return -1;
    

  12. 	return 0;
    

  13. }
Bon, puisque personne ne laisse faire Morpheus75, voilà une solution en C.
Lassé par la pub ? Créez un compte

Créer un nouveau sujet