Comment écrire un algorithme binaire pour C/C++

Question

J'ai du mal à écrire l'algorithme binaire en C/C++.
Ma question est comme ça:

Appliquez l'algorithme binaire pour rechercher un nombre de 1 à 100 dans un jeu de devinettes.
L'utilisateur répondra «y» pour une estimation correcte, «h» si l'estimation est trop élevée ou «l» si l'estimation est trop faible.

Je n'ai aucune idée de l'appliquer. Est-ce que quelqu'un peut me donner un exemple du code?

Answer 1

Instructions détaillées here plus diverses implémentations.

int low = 1; 
int high = 100; 
while (low <= high) { 
    int mid = (low + high)/2; 
    char answer = evaluateGuess(mid); //return l, h or y; 
    if ('y'==answer) { 
     return mid; 
    } 
    if ('l' == answer) { 
     low = mid + 1; 
    } else { 
     high = mid - 1; 
    } 
} 
// If you get here the human player lied and the answer wasn't in [1..100] 

Answer 2

Je suppose que vous voulez dire recherche binaire. Wikipedia a loads of information. Vous n'avez pas non plus spécifié si vous pouvez utiliser le stl.

Le pseudo-code de base est

min := 1; 
    max := N; {array size: var A : array [1..N] of integer} 
    repeat 
    mid := (min + max) div 2; 
    if x > A[mid] then 
     min := mid + 1 
    else 
     max := mid - 1; 
    until (A[mid] = x) or (min > max); 

Donc, en vous cas, min 0, max est de 100, où pourrait modifier l'algorithme ci-dessus pour qu'il prend en charge l'entrée d'utilisateur. Tout ce qui doit arriver est plutôt que les contrôles de comparaison sur un tableau, il suffit de vérifier les entrées de l'utilisateur.

min := 1; 
    max := 100; 
    repeat 
    mid := (min + max) div 2; 
    print mid; 
    c := getChar(); 
    if c == 'h' then 
     min := mid + 1 
    else if c == 'l' 
     max := mid - 1; 
    else if c == 'y' 
     return mid 
    until (min > max); 

Toutefois, si vous souhaitez obtenir de l'aide, vous devez envoyer votre code jusqu'à présent.

Answer 3

getRandomNumber(lower, upper){ 
    return random number between lower and upper; 
} 

main(){ 
lower = 0; 
upper = 101; 
num = getRandomNumber(lower, upper); 
response = askUser(num); 
while(response != Y){ 
    if (response==H) 
    //if secret is higher than num 
    lower = num; 
    else 
    //if secret is lower than num 
    upper = num; 

    num = getRandomNumber (lower, upper); 
    response = askUser(num); 
} 
}