Différentes questions algorithmiques

Version imprimable

21/12/2005, 20h11
Premium

Différentes questions algorithmiques

Bonjour,

j'ai différentes questions d'ordres algorithmiques alors si quelqu'un pouvait m'aider ce serait sympa.

1)Soient 2 mots x et y de meme taille
-Comment faire pour savoir si un mot x est un sous-mot de y
-Donner la longueur maximale des sous mots communs à x et y

2)comment reconnaitre un graphe biparti

3)m'expliquer comment fonctionne l'algo de Ford-Fulkerson car je ne le comprend pas du meme que la recherche de la coupure maximale

Merci de voir aide

Bonjour,
1)
-Comment faire pour savoir si un mot x est un sous-mot de y

Code:

1
2
3
 
 
if (strstr(y, x) != NULL) { printf("%s est une sous-chaîne de %s\n", x, y); }

-Donner la longueur maximale des sous mots communs à x et y

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int i, tmp, max, len;
 
len  = strlen(x);
tmp = max = 0;
 
for (i = 0; i < len; i++) {
  if (x[i] == y[i]) {
    tmp++;
  } else {
    if (tmp > max) {
      max = tmp;
    }
    tmp = 0;
  }
}
printf("longueur max : %i\n", max);

21/12/2005, 22h24
Premium

Merci sympho pour ta réponse:

Je remets les questions qui me posent problème et ou j'ai besoin d'aide

Merci de votre aide

1)comment reconnaitre un graphe biparti

2)m'expliquer comment fonctionne l'algo de Ford-Fulkerson car je ne le comprend pas du meme que la recherche de la coupure maximale

3)On considère une liste de n chaines de caractères mémorisée dans une table T.
La longueur maximale des chaines T[0],T[1],...,T[n-1] est notée M.
On note <= l'ordre lexicographique et on suppose que :
T[0]<=T[1]<=...<=T[n-1]

On considère un chaine x de longueur m (|x| = m)
Ecrire un algo qui fait la recherche dichotomique de x dans T en utilisant la comparaison de caractère

Attention je crois que le deuxième algo de sympho est faux :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int i, tmp, max, len; len = strlen(x); tmp = max = 0; for (i = 0; i < len; i++) { if (x[i] == y[i]) { // ici on ne prend que les sous-mots qui débutent au même index dans les deux chaînes tmp++; } else { if (tmp > max) { max = tmp; } tmp = 0; } } printf("longueur max : %i\n", max);
Pour cet algo, je pense que tu dois prendre le problème à l'envers, à savoir, si len est la longueur de str1, tu recherches les sous mots de longeur len dans str2, puis les sous mots de longeur len-1, puis len-2 etc, etc, tu t'arrêtes évidemment lorsque tu en as trouvé un !!

Je suis d'accord avec Trap D, l'algorithme de sympho est faux dans le sens que les mots ne sont pas forèment au même endroit...

En m'inspirant de son algorithme, voici une proposition: Il faudrait rajouter une boucle pour gérer le décalage:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
 
int i, j, tmp, max, lenx,leny;
 
lenx  = strlen(x);
leny = strlen(y);
 
max = 0;
 
for (i = 0; i < leny; i++) 
{
    tmp = 0;
   //On fait une passe avec un décalage différent grâce à i
   for(j = 0; (j<lenx) && ((i+j) < leny); j++) 
   {
    if (x[j] == y[i+j]) 
         tmp++;
    else 
     {
     if (tmp > max) 
        max = tmp;
 
      tmp = 0;
      }
   }
  //On vérifie si on a un nouveau maximum
  if(tmp > max)  
     max = tmp;
}
 
printf("longueur max : %i\n", max);

moi je verraisplutôt un algo de ce style :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fontion lenmaxsousmot(str1, str2) retour entier
  paramètres
    str1 chaine de caractères
    str2 chaine de caractères
  variables
    len entier longueur de str1
    lenmax entier
 
  pour lenmax de len à 1 par pas de -1 faire
    pour tous les sous mots smot de longueur lenmax de str1
       si smot est un sous mot de str2 alors
         // ici on a gagne, on peut retourner la valeur
         retour lenmax
       fin si
    fin pour
  fin pour
  // si on arrive ici, il n' y a aucun sous mot
  retour 0
fin fonction

22/12/2005, 10h26
Premium

Merci à tous pour vos suggestions.

Une idée sur la manière d'écrire cet algo?

On considère une liste de n chaines de caractères mémorisée dans une table T.
La longueur maximale des chaines T[0],T[1],...,T[n-1] est notée M.
On note <= l'ordre lexicographique et on suppose que :
T[0]<=T[1]<=...<=T[n-1]

On considère un chaine x de longueur m (|x| = m)
Ecrire un algo qui fait la recherche dichotomique de x dans T en utilisant la comparaison de caractère