Написать программу, которая за меньшее число ходов отгадывает загаданное число - Помощь студентам - Страница 2

Скарам · 30.10.2009, 19:33

По-моему золотое сечение быстрее сходиться,чем дихотомия.Алгоритмы золотого сечения тоже лежат в интернете,если надо,могу своими словами объяснить,но принцип почти тот же,что и при дихотомии)Вот ссылочка на объяснения))

LeBron · 30.10.2009, 19:44

Золотое сечение - это очень хорошо, но для новичка... Если надо не конкретно автору темы, а его преподавателю/учителю - просто не поверят. И не примут

LeBron · 30.10.2009, 19:53

Да и используют золотое сечение обычно в более сложных задачах с немного другими целями. Сдесь можно доказать, что разбиение на близкие к равным интервалы - оптимально.

Lemo · 30.10.2009, 20:03

http://www.youtube.com/watch?v=dKr28WtDX9E

NSvirus · 30.10.2009, 20:56

Код:

writeln('загадайте число:');
readln(s);
writeln('Это число ', s,'???');
writeln('какой я молодец!!!')

Так пойдет?

LeBron · 30.10.2009, 21:05

Кстати, подумал - а ведь даже не чистая дихотомия оптимальна, а деление "2интервала+1". Дихотомия рулит при 2 теоретически равных деревьях ситуаций. Если бы было 2 ответа - "больше" и "не больше" - тогда все ок, а у нас 3 ответа. Поиск с делением на 3 не прокатит, так как у ответов разные последствия. А оптимальным будет деление, при котором спрашиваем, разбивая на равные верхний и нижний интервал. Отсюда вывод - мы все, и я в том числе, сильно протупили. Задача решима в 9 вопросов. Когда мы выбираем, к примеру, из 8 чисел, то дихотомично спрашиваем относительно 4го. А ведь это неверно. Вверху получается 4 числа (5-8), а внизу только 3 (ведь число 4 не входит в "меньше 4"). Надо же сводить все к числу 9 и спрашивать относительно 5го. Тогда вверху и внизу по 4, что значит невозможность дальнейшей оптимизации.
Вывод - 10ый вопрос должен рассматривать интервал из 3 чисел. 9ый - из 3*2+1=7 чисел. 8ой - из 7*2+1=15 чисел. И так далее. Тогда в 10 вопросов можно угадать число в пределах 2047, а наше (в пределах 1023) угадывается за 9 вопросов.

LeBron · 08.11.2009, 12:57

Чисто случайно наткнулся - эта задача была на NetOI-2000, 5ая задача первого тура

30.10.2009, 19:33	#11
Скарам Дружите с Linq ;) Форумчанин Регистрация: 15.10.2008 Сообщений: 823	По-моему золотое сечение быстрее сходиться,чем дихотомия.Алгоритмы золотого сечения тоже лежат в интернете,если надо,могу своими словами объяснить,но принцип почти тот же,что и при дихотомии)Вот ссылочка на объяснения)) Не давай организму поблажки, каждый день тренируй его в шашки.. Последний раз редактировалось Скарам; 30.10.2009 в 19:39.

30.10.2009, 20:56	#15
NSvirus пропагандирую жизЪ Форумчанин Регистрация: 19.03.2007 Сообщений: 950	Код: `writeln('загадайте число:'); readln(s); writeln('Это число ', s,'???'); writeln('какой я молодец!!!')` Так пойдет? Посторонним В.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Помогите написать программу игры угадай число!!!	Oleg Olegovi4	Паскаль, Turbo Pascal, PascalABC.NET	6	21.05.2009 21:54
Программа, которая отгадывает заданное число	vakich	Помощь студентам	7	24.02.2009 19:13
Ввести число N и определить делится ли оно без остатка на число M (VBA)	Ivanich	Microsoft Office Excel	7	24.04.2008 19:43
Паскаль.программа, которая определяет каким является введенное число...	Integer	Помощь студентам	4	18.11.2007 22:17
нужна функция WinApi, которая переводит десятичное число в шестнадцатиричное???	Morskoivolk	Win Api	3	02.04.2007 18:14

30.10.2009, 19:44	#12
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Золотое сечение - это очень хорошо, но для новичка... Если надо не конкретно автору темы, а его преподавателю/учителю - просто не поверят. И не примут

30.10.2009, 19:53	#13
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Да и используют золотое сечение обычно в более сложных задачах с немного другими целями. Сдесь можно доказать, что разбиение на близкие к равным интервалы - оптимально.

30.10.2009, 20:03	#14
Lemo Форумчанин Регистрация: 13.10.2008 Сообщений: 714	http://www.youtube.com/watch?v=dKr28WtDX9E

30.10.2009, 21:05	#16
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Кстати, подумал - а ведь даже не чистая дихотомия оптимальна, а деление "2интервала+1". Дихотомия рулит при 2 теоретически равных деревьях ситуаций. Если бы было 2 ответа - "больше" и "не больше" - тогда все ок, а у нас 3 ответа. Поиск с делением на 3 не прокатит, так как у ответов разные последствия. А оптимальным будет деление, при котором спрашиваем, разбивая на равные верхний и нижний интервал. Отсюда вывод - мы все, и я в том числе, сильно протупили. Задача решима в 9 вопросов. Когда мы выбираем, к примеру, из 8 чисел, то дихотомично спрашиваем относительно 4го. А ведь это неверно. Вверху получается 4 числа (5-8), а внизу только 3 (ведь число 4 не входит в "меньше 4"). Надо же сводить все к числу 9 и спрашивать относительно 5го. Тогда вверху и внизу по 4, что значит невозможность дальнейшей оптимизации. Вывод - 10ый вопрос должен рассматривать интервал из 3 чисел. 9ый - из 32+1=7 чисел. 8ой - из 72+1=15 чисел. И так далее. Тогда в 10 вопросов можно угадать число в пределах 2047, а наше (в пределах 1023) угадывается за 9 вопросов.

08.11.2009, 12:57	#17
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Чисто случайно наткнулся - эта задача была на NetOI-2000, 5ая задача первого тура