| Автор | Математикам) |
|---|
А, читать не умею. там по 3 ответа... значит 4 варианта ответа, а значит:
ceiling(log4(1000)) = 10 |
Опять бредятину написал:)
То есть все верно, кроме = 10. Так то 5 ответ.
Ну а алгоритм не сложный:
1) угадываем число от 1 до 1024 (хоть варианты 1001 - 1024 невозможны, но для удобство будем думать что и они есть).
2) Каждый раз диапазон вероятного ответа в 4 раза уменьшаем. Если подозреваемый отрезок был [a,b], то спрашиваем
1: х<= 1/4*(b-a) + a?
2: х<= 2/4*(b-a) + a?
3: х<= 3/4*(b-a) + a?
Ну а там уже если 0 ответов "да", то в последней четверти, если 1 - в третьей четверти, если 2 - во второй, 3 - в первой. Как то так:) |
для Мария Мутола:
Ну компьютер, ты балдеешь (ералаш, серия в которой проверяли результат сложением)
Даже интересно стало |
| Эта задача из разряда бинарного поиска? Похожа во всяком случае... |
1) больше 500? да 501-1000 средн. 750,5
2) больше 750? нет 501-750 средн. 625,5
3) больше 625? да 626-750 средн. 688
4) больше 688? нет 626-688 средн. 657
5) больше 657? да 658-688 средн. 673
6) больше 673? нет 658-673 средн. 665,5
7) больше 665? да 666-673 средн. 669,5
8) больше 669? нет 666-669 средн. 667,5
9) больше 667? да 668-669
10) 668 ли? Нет. Значит, 669. |
для __DestroyeR__:
да бинарный поиск, только я причитался в задание а там говорится что ответ напрямую не знаешь, только сколько "да" или "нет" в серий из трех вопросов
к примеру если число 669
1. 1. <=500?
1. 2. <=250?
1. 3. <=125?
итого 0 "да" (т.е. 3 "нет"), значит ищем в диапазоне 501-1000
2. 1. <=750?
2. 2. <=625?
2. 3. <=563?
итого 1 "да", значит ищем в 625-750
3. 1. <=688?
3. 2. <=656?
3. 3. <=640?
1 "да", 656-688
4. 1. <=672?
4. 2. <=664?
4. 3. <=660?
1 "да", 664-672
5. 1. <=668?
5. 2. <=664?
5. 3. <=662?
0 "да", 669-672
6. 1. <=670?
6. 2. <=669?
6. 3.
число найдено после 6 серий 3 вопросов (наверно в округление одним числом обломался)
выходит в зависимости в какой половине начинать поиск в лучшем случае (число 1) угадывания число найдется в ceiling(ceiling(log2(1000)) / 4) = 3 серий (по 4 диапазона сокращен поиск тремя угадываниями за серию)
в худшем случае (число 1000), постоянно получать ответ что 0 "да" в серии вопросов, нужны будут ceiling(ceiling(log2(1000)) / 1) = 10 (по 1 диапазону сокращем поиск тремя неугадываниями за серию)
поправьте меня кто с пар по курса алгоритмов не прогуливал) |
Почему не задать 3 серии вопросов:
1) В числе есть цифра 1
2) В числе есть цифра 2
3) В числе есть цифра 3
1) В числе есть цифра 4
и т.д.
таким образом получив ответы на эти вопросы, вся выборка сократится до 3! (факториал 3-х) = 6
дальше дело техники.
я бы сказал, что минимальное количество ответов будет 3! + 3 |
для JoshuaGraham:
Ты первое действие слабое делаешь. Нужно не (125, 250, 500), а (256, 512, 768) проверять. Тогда в любом случае не больше 256 останется подозрительных. И за 5 суммарно справишься. |
а не проще выполнить 3 действия?
1. взять утюг
2. взять паяльник
3. раздеть ТС
по моему он скажет нам тогда любое число... которое он задумал... или задумает в будущем ) |
1. взять утюг
2. взять паяльник
3. раздеть ТС
Оно проще, ессно. Но, задача того не стоит. |
для Мария Мутола:
да все так, твой метод лучше в среднем |
| Ноль, если это 42. |
| Картина маслом. Куча челиков пытаются трактовать бинарный поиск ращными словами, говоря, что придумали новое решение. С: |
| Бинарный поиск не пойдёт. На 3 вопроса нам дают только сумму положительных ответов. За 3 вопроса можно найти четверть от суммы, так как на выходе мы получаем 4 варианта - от 0 до 3. Вопросы - принадлежит ли число первой четверти, первой и второй четверти, первой или второй или третьей четверти. Итого 6 вопросов потребуется, хотя последний - выбор из 2 значений. |
Сколько минимум моих ответов потребуется, чтобы точно узнать число при любых раскладах (какое бы я число не загадал).
Я так понимаю ТС начал проходить программирование в школе? |
| - Число чётное? Число простое? Числ делится на 3, 5?.. и тд. Каждый раз вычёркиваем неподходящие. |
