Correction.
1 - La complexité en O(log2(n)) qui est indiquée nous aiguille vers une dichotomie. En effet, en supposant que l’on a k ≥ log2(n)], on obtient le résultat sur les étages de i à j en jetant un étudiant depuis le nème étage, où n = j −i/2, puis en itérant le procédé sur les étages de i à n−1 si la chute à été fatale, et sur les étages de n à j dans le cas contraire. La méthode dichotomique nous garantit alors que l’on obtient le bon résultat (lorsqu’il ne reste plus qu’un seul étage, c’est-à-dire lorsque l’on calcule pour les étages de i = j), et ce avec une complexité logarithmique dans le pire des cas.
Cet algorithme utilise une approche de recherche dichotomique pour trouver l'étage fatal. On commence par diviser l'intervalle d'étages en deux et on teste l'étage médian. En fonction du résultat, on restreint l'intervalle de recherche en conséquence jusqu'à ce qu'on trouve l'étage fatal.
int trouverEtageFatal(int n, int k) {
int i = 1, j = n;
while (i < j) {
int milieu = (i + j) / 2;
// Simuler la chute de l'étudiant depuis l'étage
if (chuteFatale(milieu)) {
j = milieu;
} else {
i = milieu + 1;
}
}
return i; // i est le premier étage fatal
}
Complexité : O(log2(n)). À chaque itération, l'intervalle d'étages est réduit de moitié.
2-Puisqu’icionnedisposequede k <[log2(n)] étudiants,on ne peut pas appliquerdirectement la méthode dichotomique proposée précédemment. Cependant, on va remédier au problème de manière simple en appliquant une recherche dichotomique avec k −1 étudiants, de manière à délimiterunintervalled’étagesdanslequelsetrouvel’étagerecherché.Onsesertalorsdudernier étudiant restant pour parcourir l’intervalle de façon linéaire, donc en le jetant de chaque étage en partant du plus bas de l’intervalle, jusqu’au plus haut. Après avoir jeté les k −1 premiers étudiants, si l’on n’a pas encore trouvé le bon étage, il reste exactement n/2k−1 étages dans l’intervalle de recherche, d’où une complexité dans le pire des cas en O(k +n/(2(k−1)) sauts.
Cet algorithme utilise d'abord une recherche dichotomique avec k-1 étudiants pour délimiter un intervalle d'étages potentiels. Ensuite, il effectue une recherche linéaire à l'intérieur de cet intervalle pour trouver l'étage fatal.
int trouverEtageFatal(int n, int k) {
int i = 1, j = n;
for (int etudiant = 1; etudiant < k; ++etudiant) {
int milieu = (i + j) / 2;
// Simuler la chute de l'étudiant depuis l'étage
if (chuteFatale(milieu)) {
j = milieu;
} else {
i = milieu + 1;
}
}
for (int etage = i; etage <= j; ++etage) {
// Simuler la chute de l'étudiant depuis l'étage
if (chuteFatale(etage)) {
return etage;
}
}
return n + 1; // Aucun étage fatal trouvé
}
Complexité : O(k + n/(2^(k-1))). La recherche dichotomique réduit l'intervalle d'étages de manière logarithmique, puis la recherche linéaire à l'intérieur de cet intervalle a une complexité linéaire.
3 - Dans le cas particulier où l’on a k = 2, on ne veut pas avoir à tester chaque étage de façon linéaire, c’est pourquoi on va reprendre à notre compte les idées précédentes, et notamment celle qui consiste à délimiter un intervalle de recherche. Nous découpons donc l’ensemble des étages en “tranches” de √n étages, avant de jeter le premier étudiant de chacun des étages de début de tranche. Lorsque l’étudiant y laisse sa peau, on se ramène au dernier étage n testé qui ne soit pas fatal, et on n’a plus qu’à parcourir de manière linéaire l’intervalle allant de l’étage n+1 à l’étage fatal trouvé précédemment. On a ainsi deux séries d’essais en O(√n), et donc une complexité finale dans le pire des cas également en O(√n) sauts.
Cet algorithme découpe les étages en "tranches" de taille √n et teste le premier étudiant de chaque tranche. Lorsqu'un étudiant échoue, l'algorithme effectue une recherche linéaire à l'intérieur de cette tranche pour trouver l'étage fatal.
int trouverEtageFatal(int n) {
int pas = (int)sqrt(n);
int debut = 1;
while (!chuteFatale(debut)) {
debut += pas;
}
for (int etage = debut - pas + 1; etage <= debut; ++etage) {
if (chuteFatale(etage)) {
return etage;
}
}
return n + 1; // Aucun étage fatal trouvé
}
Complexité : O(√n). L'algorithme teste le premier étudiant de chaque tranche, et si un échec est rencontré, il effectue une recherche linéaire à l'intérieur de la tranche, ce qui donne une complexité globale en racine carrée.