flash_back
@flash_back

Упражнение из книги Страуструпа. Программа угадай число. Можно ли написать лучше?

Всем привет.
Сделал упражнение к книге Бьерна Страуструпа "Программирование. Принципы и практика
использования С++".
Текст упражнения такой:
Напишите программу, угадывающую число. Пользователь должен задумать
число от 1 до 100, а программа должна задавать вопросы, чтобы выяснить, какое
число он задумал (например, “Задуманное число меньше 50”). Ваша программа
должна уметь идентифицировать число после не более семи попыток. Подсказ-
ка: используйте операторы < и <=, а также конструкцию if-else.

Мое решение такое:
#include <iostream>

using namespace std;

int main()
{
	setlocale(LC_ALL, "Russian");
	double curr =50;
	double shift =50;
	char answer = ' ';
	bool equal_check = false;
	for(int i=0;i<8;i++){
		cout << "Число равно" << static_cast<int>(curr + 0.5) <<"?(y,n)";
		cin >> answer;
		if (answer=='y') { equal_check = true; break; }
		cout << "Число меньше " <<  static_cast<int>(curr + 0.5) << "?(y,n)";
		cin >> answer;
		cout << "shift" << shift << endl;
		cout << "curr" << curr << endl;
		if (answer=='y') { shift=shift/2; curr -= shift; } 
		else if(answer=='n') { shift=shift/2; curr += shift; } 
	}
	if (!equal_check)
	{
		cout << "wrong input" << endl;
	}
	system("pause");
	return 0;
}

Вроде работает, но есть подозрение, что я не до конца понял суть упражнения и что еще можно написать как-то проще и эффективней. Подскажите, пожалуйста, можно ли написать лучше? И правильно ли я понял задачу?

upd.Короче сам похоже нашел решение, которое подходит условиям упражнения:
#include <iostream>

using namespace std;

int main()
{
	setlocale(LC_ALL, "Russian");
	double curr =50, shift =50;
	char answer = ' ';
	cout << "Загадайте число от 1 до 100." << endl;
	system("pause");
	for(int i=0;i<8;i++){
		cout << "Число меньше " <<  static_cast<int>(curr + 0.5) << "?(y,n)";
		cin >> answer;
		if (answer=='y'){ 
			shift=shift/2; 
			curr -= shift; 
		} 
		else if(answer=='n'){ 
			shift=shift/2; 
			curr += shift; 
		}
		if ( (curr <= 1.0) || (curr >= 99.5) ){ 
			cout <<"Ваше число " <<  static_cast<int>(curr + 0.5) << endl; 
			break;
		};
		if ( shift <= 0.5){ 
			cout <<"Ваше число  " <<  static_cast<int>(curr) << endl; 
			break;
		}
	}
	system("pause");
	return 0;
}


upd.Еще раз перепроверил.
Оказалось тоже есть недочет. На 99 не работает. В первый раз проглядел.
Поправил перестала работать как решение снизу от teugen во втором варианте (при выборе 100, до 100 не доходит ).
В итоге получается, что с исходным вопросом “Задуманное число меньше X”, если его не менять и включить 100 в возможный выбор числа, а не брать от 1 до 99 , работать в семь итерации при варианте 100 не будет никак, а только в восемь. Поэтому склоняюсь к тому, что в тексте вопроса неправильный перевод на русский и предполагалось, что интервал будет от 1 до 99. Либо второй вариант такой, что вопрос (“Задуманное число меньше X”) можно видоизменять и тогда вариант такой как у teugen получился в третий раз (финальный). Я лично считаю, что все таки ошибка переводчика или Бьерн неточно написал и ожидалась, что интервал будет от 1 до 99.
Вот думаю какая реализация имелась ввиду (решение от teugen во втором варианте, чуть исправленное мной):
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	setlocale(LC_ALL, "Russian");

	int min = 1, max = 100;
	cout << "Загадайте число от " << min << " до " << (max - 1) << ".\n";  //микрофикс

	int guess = (max + min) / 2, count = 7;//микрофикс (C++98)
	for (int i = 0; i < count; ++i)
	{
		cout << "Загаданное число меньше " << guess << "? (y/n)\n";

		char ans;
		cin >> ans;
		if (ans == 'y')
		{
			max = guess;
		}
		else
		{
			min = guess;
		}
		guess = (min + max) / 2;

		if (max - min < 2)
		{
			cout << "Вы загадали число \"" << guess << "\".\n";
			system("PAUSE");
			return 0;
		}
	}

	cout << "Жулик!\n";
	system("PAUSE");
	return 0;
}

Думаю вопрос закрыт.
  • Вопрос задан
  • 4571 просмотр
Решения вопроса 1
@teugen
Призрак алкоголизма.
Поняли правильно, это обыкновенный двоичный поиск. Обычно он реализуется рекурсивно, можете посмотреть исполнение, например, в Википедии.
Написать лучше тоже можно - с переносами строк и пробелами выглядеть будет гораздо приятнее.

P.s. У вас 8 проходов цикла.

upd. Если предположить, что каждый вопрос (неважно какой) - это попытка, то можно ограничиться только семью вопросами. Например, так:
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    setlocale(LC_ALL, "Russian");

    int min = 1, max = 100;
    cout << "Загадайте число от " << min << " до " << max << ".\n";

    int guess = (min + max) / 2, count = (int) ceil(std::log2(max - min));
    for (int i = 0; i < count; ++i)
    {
        cout << "Загаданное число меньше или равно " << guess << "? (y/n)\n";   // fixed

        char ans;
        cin >> ans;
        if (ans == 'y')
        {
            max = guess;
        }
        else
        {
            min = guess + 1;    // fixed
        }
        guess = (min + max) / 2;

        if (max == min)    // fixed
        {
            cout << "Вы загадали число \"" << guess << "\".\n";
            system("PAUSE");
            return 0;
        }
    }

    cout << "Жулик!\n";
    system("PAUSE");
    return 0;
}
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
maaGames
@maaGames
Погроммирую программы
Скорее всего подразумевается, что пользователь должен ввести число, а программа потом его "ищет" не взаимодействуя с пользователем.
В вашем решении сравнение на меньше заменено общением с пользователем.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы