[exercice] algo sur les tableaux

Version imprimable

bonjour,

Je voudrais de l'aide concernant un éxo à résoudre sur les algo partie tableau et je galère pour ça :( , voici l'exercice:

un vecteur ville contient le nom de plusieurs villes et une matrice distance contient les distances entre les villes.
Voici le principe: les indices de ligne et de colonne de la matrice distance représente les indices des villes dans le vecteur ville.
Attention, la matrice distance est "triangulaire" c'est à dire qu'elle n'est remplie qu'à moitié (ce qui est logique car la distance antibes-nice est la même que nice-antibes).

voici à quoi ressemble distance:
    1    2    3    4    5
   ----------------------
1 | 0   23   12    5   46
2 | -    0    2   40   10
3 | -    -    0   51   20
4 | -    -    -    0   11
5 | -    -    -    -    0
si antibes est la ville n°3 et nice la ville n°5 dans le vecteur ville, alors la distance entre antibes est nice est de 20km,

Ecrire la séquence algorithmique qui permet de saisir 2 noms de villes et d'afficher la distance entre ces 2 villes. si l'un des noms de villes n'est pas présent dans le tableau des villes, il faudra alors juste afficher un message d'erreur

voici donc ce que jai realisé:
Code:

1 2 3 4 5 6 7 8 9 10 Programme Ville ville[1..100]: chaine nbvilles: entier // contient le nombre de cases effectivement remplies dans ville distance [1..100,1..100]: entier // contient les distances entre les villes Debut Afficher "entrer ville1:" saisir ville1 afficher "entrer ville2:" saisir ville2
Voila je vous remercie d'avance ;)

16/05/2011, 20h10
Franck Dernoncourt

Sauf mauvaise lecture de me part, il n'y a vraiment aucune difficulté, sauf à la rigueur le fait que la matrice distance est triangulaire...

Qu'as-tu essayé de faire mis à part recueillir les entrées de l'utilisateur ?
16/05/2011, 20h18
omzoway

bonsoir, justement c'est la matrice qui me fait bugger un peu avec les autres exos classique sur les structures des tableaux je m'en sortais mieux, mais je me disais si par la suite de sil faut faire une boucle si ville 1 et ville 2 existe alors afficher distance entre les 2 villes sinon afficher error, oubien je me trompe :? car le truc de la matrice triangulaire là, je ne vois pas trop ^^', merci :)

Pourquoi une boucle ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
Programme Ville
  ville[1..100]: chaine
  nbvilles: entier // contient le nombre de cases effectivement remplies dans 
   ville 
   distance [1..100,1..100]: entier // contient les distances entre les villes
Debut
     Afficher "entrer ville1:"
     saisir ville1
       afficher "entrer ville2:"
       saisir ville2
      Si ville1 ou ville2 n'est pas dans tableau_des_distances, alors erreur
      return tableau_des_distances[min(index_ville1, index_ville2)][max(index_ville1, index_ville2)]

16/05/2011, 20h32
omzoway

ooh mince je voulais dire condition si plutot, jai tendance à dire toujours boucle :aie: , voilà cest ce que je voulais dire en gros sauf que moi je pensais plutot comme ça:
si distance.ville1 et distance.ville2 existent alors on les affiche
sinon on affiche un message d'erreur et on retourne piocher au tableau, par contre je ne comprends pas le pourquoi des min et max, oui je sais je suis un neuneu en math, pourriez vou s'il vous plait être plus explicite, merci encore d'avantage :ccool:
16/05/2011, 20h36
Franck Dernoncourt

min et max car la matrice est triangulaire, donc on doit faire attention d'appeler des cellules de la matrice qui existe.

Citation:

Envoyé par Franck Dernoncourt

Pourquoi une boucle ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
Programme Ville
  ville[1..100]: chaine
  nbvilles: entier // contient le nombre de cases effectivement remplies dans 
   ville 
   distance [1..100,1..100]: entier // contient les distances entre les villes
Debut
     Afficher "entrer ville1:"
     saisir ville1
       afficher "entrer ville2:"
       saisir ville2
      Si ville1 ou ville2 n'est pas dans tableau_des_distances, alors erreur
      return tableau_des_distances[min(ville1, ville2)][max(ville1, ville2)]

Ne faudrait-il pas rechercher l'index de ville1 et ville2 (qui sont des chaines de caractère) dans le tableau villes ?

16/05/2011, 20h38
Franck Dernoncourt

Oui désolé, je pensais aux index, je viens de le corriger.
16/05/2011, 20h39
prgasp77

C'est plus au PO qu'à toi que je faisais la remarque. On va pas tout faire non plus ;)
Alors omzoway, que proposes-tu ?
16/05/2011, 20h49
omzoway

lool honneur aux dames, alors je vais essayer , comme notre objectif est d'afficher la distance entre antibes et nice si je mettais:
si la ville 1 et ville 2 existe dans nbvilles
pour ville1 de 1 à 100 afficher ville 1 puis saisie de ville 1 ,
ensuite pour ville2 de 1 à 100 aussi affichage et saisie de ville 2
puis saisie " de la distance entre" ville1 "et" ville2 "= 20 km"
sinon
affichez "erreur ville non existante"
???
Ps: l'algorithme cest vraiment chiant, il ne devrait y avoir que des trucs cool genre VB, Vbnet, my sql, mcd merise...^^
16/05/2011, 21h08
prgasp77
Plutot que d'essayer de pondre l'algo directement, je te propose de m'expliquer comment tu ferais pour faire le travail que tu va demander à ton programme. Imaginons le cas suivant :

Matrice de distance :
```
    1    2    3    4  
   -------------------
1 | 0   23   12    5  
2 | -    0    2   40  
3 | -    -    0   51  
4 | -    -    -    0  
```
Liste de villes :
```
1       2        3         4
Paris   Nantes   Bordeaux  Marseille
```
Disons qu'aux deux premières questions que tu va me poser, je te réponde «Marseille » puis « Nantes ». Alors, raconte nous tout !
16/05/2011, 21h18
omzoway
Citation:
Envoyé par prgasp77

Plutot que d'essayer de pondre l'algo directement, je te propose de m'expliquer comment tu ferais pour faire le travail que tu va demander à ton programme. Imaginons le cas suivant :

Matrice de distance :

1 2 3 4 ------------------- 1 | 0 23 12 5 2 | - 0 2 40 3 | - - 0 51 4 | - - - 0
Liste de villes :

1 2 3 4 Paris Nantes Bordeaux Marseille

Disons qu'aux deux premières questions que tu va me poser, je te réponde «Marseille » puis « Nantes ». Alors, raconte nous tout !
intéréssant alors en principe on devrait chercher si marseille et nantes existe vraiment dans la matrice triangulaire et si tel est le cas alors ça nous affiche la distance entre les 2 par ex ici si marseille est en colonne on devrait avoir 40 pour la distance entre ces 2 villses sinon à linverse si marseille est en ligne cest le message derreur qui safficherait puisque la distance ne serait pas saisie?
16/05/2011, 21h33
prgasp77

Non, je ne te demande pas ce qu'il se passerait, mais comment tu ferais pour répondre *toi* au problème. Comment sais-tu que c'est la colonne 4 qu'il faut consulter ? Et présente moi ça comme une liste d'action.

Exemple pour expliquer comment mettre le JT d'arte :
1/ je prends la télécommande
2/ je cherche le bouton "on" sur la télécommande
3/ si je le trouve, j'appuie dessus
4/ je cherche le bouton "5" sur la télécommande
5/ si je le trouve, j'appuie dessus
6/ fini \o/

On traitera les cas critiques (ex: erreurs) plus tard.
16/05/2011, 21h42
Golgotha

Désoler de venir foutre le bordel :aie:

Pourquoi la matrice est "triangulaire", je dirais pluôt "symétrique", les cases marqué "-" ont bien une réalité.. la distance "Brest - Paris" est la même que "Paris - Brest", pourquoi occulter une des distances ?

--- 1 2 3 4
1 | 0 23 12 5
2 | 23 0 2 40
3 | 12 2 0 51
4 | 5 40 51 0

Ce tableau me semble tout à fait valide..
16/05/2011, 21h46
prgasp77

C'est un simple exercice ;) Ça corse la difficulté, je pense.
16/05/2011, 22h04
omzoway

[HS] lool on croirait entendre mon prof elle dit que jai lesprit trop synthetique parfosi avec les algo et qu'on est pas en mathématiques [Fin HS]
alors alors hummm ok
disons que je decide de rajouter k en declaration en tant que variable:
(pour k de 1 à 100
afficher "entrer la ville1 n°", K, "="
saisir ville1[k]
afficher "entrer la ville2 n°", k, "="
saisir ville2[k]
si ville1[k]=nbvilles[k] et ville2[k]=nbvilles[k] alors
afficher "la distance entre ces 2 villes est:"
saisir distance
sinon
return distance):cry:
16/05/2011, 22h09
omzoway

Citation:

Envoyé par Golgotha

Désoler de venir foutre le bordel :aie:

Pourquoi la matrice est "triangulaire", je dirais pluôt "symétrique", les cases marqué "-" ont bien une réalité.. la distance "Brest - Paris" est la même que "Paris - Brest", pourquoi occulter une des distances ?

--- 1 2 3 4
1 | 0 23 12 5
2 | 23 0 2 40
3 | 12 2 0 51
4 | 5 40 51 0

Ce tableau me semble tout à fait valide..

oulààà je comprends pas mais ce que tu dis m'interesse explique plus en detail sil te plait ^^
16/05/2011, 22h09
Golgotha

Citation:

Envoyé par omzoway

oulààà je comprends pas mais ce que tu dis m'interesse explique plus en detail sil te plait ^^

heuuu, oublie ce que j'ai dit :aie: ça va encore plus t’embrouiller..

je peux donner la réponse moi :D
16/05/2011, 22h15
omzoway

je suis fatigué cest le seul exo qui me reste jai fait tout ce qui est sql trace et mcd :cry:, mais dabord le tableau que tu as crée tu veux dire quil vaut pareil que la matrice initiale et pourquoi? oubien tu las sorti juste comme ça, sinon sil vous plait veuillez abreger mes souffrances, pikachu na meme pas encore mangé XD par contre jaimerais bien des explications détaillées aussi
16/05/2011, 22h16
prgasp77

Trop compliqué encore. Ais l'obligeance d'oublier tout ce que tu as appris en cours d'algorithmie pour quelques instants. Réponds moi comme si j'étais un imbécile fini (vas-y franchement, je ne t'en voudrait pas).

Étant donné les deux éléments (Matrice de distance et liste de ville) donnés dans mon message #11, comment en déduits-tu que la distance entre Marseille et Nantes est de 40 km ?
16/05/2011, 22h21
Golgotha

Citation:

Envoyé par prgasp77

Plutot que d'essayer de pondre l'algo directement, je te propose de m'expliquer comment tu ferais pour faire le travail que tu va demander à ton programme. Imaginons le cas suivant :

Matrice de distance :
1 2 3 4 ------------------- 1 | 0 23 12 5 2 | - 0 2 40 3 | - - 0 51 4 | - - - 0
Liste de villes :
1 2 3 4 Paris Nantes Bordeaux Marseille

Disons qu'aux deux premières questions que tu va me poser, je te réponde «Marseille » puis « Nantes ». Alors, raconte nous tout !

1 - Je note la position de Marseille dans mon petit bloc note : 4
2 - je fait pareille avec Nantes : 2
3 - Je regarde à la position 4:2 de la matrice si je voie un nombre
4 - OUI : c'est 40 ce nombre !
5 - j'envoie 40 au maître contrôle principale ;)
16/05/2011, 22h23
omzoway

Citation:

Envoyé par prgasp77

Trop compliqué encore. Ais l'obligeance d'oublier tout ce que tu as appris en cours d'algorithmie pour quelques instants. Réponds moi comme si j'étais un imbécile fini (vas-y franchement, je ne t'en voudrait pas).

Étant donné les deux éléments (Matrice de distance et liste de ville) donnés dans mon message #11, comment en déduits-tu que la distance entre Marseille et Nantes est de 40 km ?

Mdrrrrrr baah je me suis dit si ville1 à savoir marseille existe et ville 2 nantes existe dans la liste des villes et que le coefficient de la colonne 4 et ligne 2 existe dans la matrice distance alors on saisit ce coefficient ^^
16/05/2011, 22h25
omzoway

Citation:

Envoyé par Golgotha

1 - Je note la position de Marseille dans mon petit bloc note : 4
2 - je fait pareille avec Nantes : 2
3 - Je regarde à la position 4:2 de la matrice si je voie un nombre
4 - OUI : c'est 40 ce nombre !
5 - j'envoie 40 au maître contrôle principale ;)

bah voilà sauf qu'on est pas en maths ^^
16/05/2011, 23h12
prgasp77
Golgotha 1 − omzoway 0
On continue.

Maintenant que tu as un algorithme de haut niveau (celui qu'a donné Golgotha), transforme chacune des étapes en une suite d'instructions algorithmiquement parlant.
Par exemple, l'étape 3 donnera :
Code:

1 2 3 Si matrice_distances[4][2] est un nombre Alors < insérer les étapes 4 et 5 ici> Sinon <faire autre chose, oui mais quoi ?>
_______________

Citation:

Envoyé par omzoway

Mdrrrrrr baah je me suis dit si ville1 à savoir marseille existe et ville 2 nantes existe dans la liste des villes et que le coefficient de la colonne 4 et ligne 2 existe dans la matrice distance alors on saisit ce coefficient ^^

Ici, tu ne m'expliques pas comment tu fais la relation entre « Nantes » et le nombre 2. Je t'avais demandé de tout m'expliquer, comme si j'étais un demeuré ...
17/05/2011, 05h12
omzoway
Citation:
Envoyé par prgasp77

Golgotha 1 − omzoway 0
On continue.

Maintenant que tu as un algorithme de haut niveau (celui qu'a donné Golgotha), transforme chacune des étapes en une suite d'instructions algorithmiquement parlant.
Par exemple, l'étape 3 donnera :

Code:

1 2 3 Si matrice_distances[4][2] est un nombre Alors < insérer les étapes 4 et 5 ici> Sinon <faire autre chose, oui mais quoi ?>

_______________

Ici, tu ne m'expliques pas comment tu fais la relation entre « Nantes » et le nombre 2. Je t'avais demandé de tout m'expliquer, comme si j'étais un demeuré ...
lol je suis malmené là, désolé je m'etais endormi ^^
je propose à l'étape 3 si distance[4][2]>0 alors
afficher "distance entre cest 2 villes est" distance[4][2]
saisie de distance[4].[2]
sinon
afficher "erreur"
repeter saisir distance
jusqu'à que distance[1..100][1..100]>0
fi
17/05/2011, 12h17
Golgotha

Citation:

Envoyé par omzoway

lol je suis malmené là, désolé je m'etais endormi ^^
je propose à l'étape 3 si distance[4][2]>0 alors
afficher "distance entre cest 2 villes est" distance[4][2]
saisie de distance[4].[2]
sinon
afficher "erreur"
repeter saisir distance
jusqu'à que distance[1..100][1..100]>0
fi

Je crois que tu te complique le bourichon pour rien.. d'ou sort tu ton itération de 100 ?

Tu as :

Input :
- Une matrice des distances entre des villes
- Un tableau de ville.
- 2 villes choisi par l'utilisateur.

Output:
- La distance entre deux villes

Ton algorithme est très simple.

Après que l'utilisateur est tapé deux nom de ville :

- SI les deux villes sont dans le tableau des villes ALORS :
- PLACER dans A l'indexe de la ville 1
- PLACER dans B l'indexe de la ville 2
- PLACER dans C la valeur qui se trouve en [A,B] de la matrice des villes.
- SI C n'est pas égale à '-' ALORS
---- AFFICHER "La distance est " + C
- SINON
---- PLACER dans C la valeur qui se trouve en [B,A] de la matrice des villes.
---- AFFICHER "La distance est " + C

Il n'y à rien de plus.. ;)
17/05/2011, 12h48
omzoway

Citation:

Envoyé par Golgotha

Je crois que tu te complique le bourichon pour rien.. d'ou sort tu ton itération de 100 ?

Tu as :

Input :
- Une matrice des distances entre des villes
- Un tableau de ville.
- 2 villes choisi par l'utilisateur.

Output:
- La distance entre deux villes

Ton algorithme est très simple.

Après que l'utilisateur est tapé deux nom de ville :

- SI les deux villes sont dans le tableau des villes ALORS :
- PLACER dans A l'indexe de la ville 1
- PLACER dans B l'indexe de la ville 2
- PLACER dans C la valeur qui se trouve en [A,B] de la matrice des villes.
- SI C n'est pas égale à '-' ALORS
---- AFFICHER "La distance est " + C
- SINON
---- PLACER dans C la valeur qui se trouve en [B,A] de la matrice des villes.
---- AFFICHER "La distance est " + C

Il n'y à rien de plus.. ;)

javoue je ne pige pas le sinon car pour moi cest pareil que la condition si puisque la distance [A]*[B] est egale à [B]*[A], je croyais quau sinon on affiche juste un message derreur puis return dans tableau ville: Donc en gros lalgo cest:
si ville="Antibes" et ville="Nice" alors
ville[3]=Antibes et
ville[5]=Nice
distance=distance.ville[3][5]
finsi
si distance.ville[3][5] <> '-' // cest à dire positif puisque le coefficient ne doit
pas etre egale à - ni 0 puis que ce serait que mesurer la distance entre 2 villes identiques
alors Afficher distance.ville[3][5] "=" 40
sinon Afficher "error"
distance= distance.ville[5][3]
afficher distance.ville[5][3]
Fin ????

Ps: promis des que je finis mon projet de creation de site php dans 2 semaines je fais une remise à jour totale sur les algos et fichiers et je refais tous les exos dunet ainsi que du cours, et biensur je vous remercie pour tout laide et surtout la patience car je sais que je vous torture lol
17/05/2011, 15h52
edfed

input ville1 = A
input ville2 = B

si A dans liste ville alors A=indexA
sinon erreur

si B dans liste ville alors B=indexB
sinon erreur

si A < B ;parce que le tableau est triangulaire
echanger A et B

C = element tableau [A][B] ;tableau [colonne][ligne]

retourner la distance C
17/05/2011, 16h12
prgasp77

Je ne comprends pas pourquoi vous vous évertuez à faire ses devoirs, alors que le PO ne fait manifestement aucun effort pour y parvenir par lui-même.
Comprenez que je ne vous en veut pas le moins du monde, mais que je reproche à omzoway son manque de concentration qui ne lui sera, au final, que néfaste ...
17/05/2011, 16h32
omzoway

Citation:

Envoyé par prgasp77

Je ne comprends pas pourquoi vous vous évertuez à faire ses devoirs, alors que le PO ne fait manifestement aucun effort pour y parvenir par lui-même.
Comprenez que je ne vous en veut pas le moins du monde, mais que je reproche à omzoway son manque de concentration qui ne lui sera, au final, que néfaste ...

Aïe aïe :cry: pourtant je fais des efforts tu sais..jai passé toute la soirée hier dessus, c'est juste que j'ai pas trop trop d'affinités avec les algo disons, soit je reflechis toujours de façon complexe soite même si je saisis l'objectif du probléme, ma démarche de résolution nest pas trop bonne, mais d'un coté aussi javoue tas pas tort cest que je dois my mettre encore plus et je lacherai pas ^^
Ps: Po ça signifie quoi? ^^
17/05/2011, 16h36
omzoway

Citation:

Envoyé par edfed

input ville1 = A
input ville2 = B

si A dans liste ville alors A=indexA
sinon erreur

si B dans liste ville alors B=indexB
sinon erreur

si A < B ;parce que le tableau est triangulaire
echanger A et B

C = element tableau [A][B] ;tableau [colonne][ligne]

retourner la distance C

merci c'est plus lumineux encore :ccool:

?????

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
 
Programme Distance Villes
 
  Ville[1..100]: chaîne
  nbvilles: entier                                 // contient le nombre de cases effectivement remplies dans ville
  distance[1..100,1..100]: entier       //  contient les distances entre les villes
 
Debut
 
   Afficher "entrer ville1"
   Saisir ville1
   Afficher "entrer ville2"
   Saisir ville2 
 
 // intialisation des villes
  Ville1= Antibes
  Ville2=Nice 
  Si Ville1.Ville= Antibes alors          // cest à dire si antibes est dans la liste des villes
   Antibes= ville[3]                        // indexation de la ville1
   sinon Afficher "error"
  fsi
 Si Ville2.ville= Nice alors                // cad si Nice est dans la liste des villes 
             Nice=Ville[5]
   sinon afficher "error" 
 fsi 
     Si ville[5]< ville[3]    alors                // car la matrice  est triangulaire 
     Antibes=ville[5] et Nice=ville[3]       // je dois echanger la ville1 à la ville 2
   Afficher " la distance entre les 2 villes est:" ville[3][5];    // element tableau ville1*ville2, (tableau colonne, ligne)
   retourner distance"= "40
   fsi
Fin

Fuseau horaire GMT +2. Il est actuellement 22h23.