Algorithme itératif avec des trains.

[MrBrightside]

Bonjour,

Voici l'énoncé:

n, k désignent deux entiers naturels non nuls, c désigne un entier naturel, p désigne un tableau d'entiers à n cases numérotées de 0 à n-1.

n personnes veulent relier par train deux villes A et B le même jour.

Les k trains qui relient A et B ce jour là sont numérotés de 0 à k-1 et partent dans l'ordre de leur numéro.

Les n personnes sont numérotées de 0 à n-1 et pour tout i appartenant à |[0,n-1]|, la personne i souhaite prendre le train p[i].

Chaque train peut contenir au plus c personnes.

1- Écrire en pseudo-langage, un algorithme qui teste si tout le monde peut prendre le train de son choix.

2- On suppose maintenant que pour tout i appartenant à |[0,n-1]|, si le train p[i] est plein alors que la personne i veut le prendre, elle est prête à prendre le train suivant (lorsqu'il existe et n'est pas plein!).
Écrire un algorithme qui répartit les gens dans les trains lorsque cela est possible.

3- On suppose maintenant que pour tout i appartenant à |[0,n-1]|, si le train p[i] est plein alors que la personne i veut le prendre, elle souhaite prendre le train suivant le plus tôt possible après le train p[i].
Écrire un algorithme qui répartit les gens dans les trains lorsque cela est possible.

4- Apporter quelques critiques positives ou négatives au modèle de réservation de la question 3.


Voici ce que j'ai fait pour la 1:

k <- k
n <- n
Pour i allant de 0 à n-1 faire
n <- n-1
k <- k-1
fin pour
si n<k afficher "ok"
sinon afficher "impossible"
fin si

La 2 me pose déjà problème, j'ai fait quelque chose mais je doute que ce soit juste:

k <- k
n <- n
c <- c
Pour i allant de 0 à n-1
a <- nombre de personnes dans le train p[i]
si a<c alors n <- n-1
k <- k-1
sinon k <- k-1
fin si
fin pour


J'aurais donc voulu savoir si ce que j'ai fait pour le moment est juste ou non...
Je vois mal la différence entre la 2ème et la 3ème question.

J'espère que vous pourrez m'aider.

Merci de m'avoir lu!

[ampholyte]

Bonjour,

Je pense que pour la première question ton algorithme ne convient pas.
Dans ton algorithme, tu essayes simplement de voir si le nombre de personne est inférieur au nombre de train si c'est le cas alors OK sinon impossible.

Prenons un exemple :
k = 3
n = 2
Pour i = 0:
n = 2 - 1 = 1
k = 3 - 1 = 2
Pour i = 1:
n = 1 - 1 = 0
k = 2 - 1 = 1

Si (0 Vrai on affiche alors "ok".

Ne crois-tu pas que cela revient à faire l'algorithme suivant ? :
k c) : // On teste si dans le train k, on a plus de c personnes
Afficher("Train k complet")
res = Faux
Quit() // On sort de la boucle de la boucle
Fin pour

Si (res = Vrai)
Afficher(" Tout le monde est placé")
Sinon
Afficher("Tout le monde ne peux pas prendre le train")

[/CODE]

As-tu compris ce qui ne va pas dans ton algo pour le 1?

Pour la question 2), on te demande si lors qu'une personne i veut prendre le train j = p[i] mais que celui-ci est plein, on lui fasse prendre le train j+1 si celui-ci n'est pas plein, sinon impossible. Ici on ne cherche que le train suivant et non le train j+x.

Pour la question 3), on te demande si lors qu'une personne i veut prendre le train k = p[i] mais que celui-ci est plein, on lui fasse prendre le train k+1 si celui-ci n'est pas plein, sinon il prend le train k+2 si celui-ci n'est pas plein, sinon ... Impossible si tous les trains suivant sont pleins !