Compte_supprime_69952 Posted August 12, 2005 Share Posted August 12, 2005 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 PS:je mets les exos les uns à la suite des autres pour que ça ne soit pas illisible et pour que vous puissiez voir les exos ou vous pouvez m'aider Merci d'avance 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)[/b] Link to comment Share on other sites More sharing options...
Compte_supprime_69952 Posted August 13, 2005 Author Share Posted August 13, 2005 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 Link to comment Share on other sites More sharing options...
Compte_supprime_69952 Posted August 13, 2005 Author Share Posted August 13, 2005 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 Link to comment Share on other sites More sharing options...
Chimayscripteur Posted August 15, 2005 Share Posted August 15, 2005 Juste une question, tu as un compilateur C chez toi? Si oui, tu peux aller récupérer le code des fonctions strcomp,strcat, ... Je crois que ça pourrait t'aider! Je vais essayer de te filer un coup de main plus productif mais je ne promets rien, suis un peu pressé par le temps! Link to comment Share on other sites More sharing options...
Compte_supprime_69952 Posted August 16, 2005 Author Share Posted August 16, 2005 Juste une question, tu as un compilateur C chez toi?Si oui, tu peux aller récupérer le code des fonctions strcomp,strcat, ... Je crois que ça pourrait t'aider! Je vais essayer de te filer un coup de main plus productif mais je ne promets rien, suis un peu pressé par le temps! Non,je n'ai pas de compilateur C chez moi. Link to comment Share on other sites More sharing options...
Chimayscripteur Posted August 16, 2005 Share Posted August 16, 2005 Ca c'est un rien foireux car c'est bien pratique pour tester tes exercices! Compilateur C gratuit Voilà qui devrait bien t'aider! Link to comment Share on other sites More sharing options...
Compte_supprime_69952 Posted August 16, 2005 Author Share Posted August 16, 2005 Ca c'est un rien foireux car c'est bien pratique pour tester tes exercices!Compilateur C gratuit Voilà qui devrait bien t'aider! Salut, tu parlais de recuperer le code de strcmp,strcat,... mais comment faire pour récupérer la fonction détaillée car je ne connais que la fonction man "nom de la fonction" qui donne le prototype de la fonction... Link to comment Share on other sites More sharing options...
Chimayscripteur Posted August 16, 2005 Share Posted August 16, 2005 J'suis plus certain mais en ouvrant sous vi la bibliothèque contenant la fonction (ex: stdio.h contient printf, scanf, ...), tu devrais avoir son prototype. Link to comment Share on other sites More sharing options...
Recommended Posts
Archived
This topic is now archived and is closed to further replies.