Как с 8 опита можем със 100% сигурност да познаем число

NoThanks · Гост

Като гледам, че напоследък пускате доста задачи тук, се присетих за една, по която правихме програмка в 10ти клас Very Happy

Да се намери алгоритъм, чрез който с 8 опита можем със 100% сигурност да познаем число в интервала [1;1000], ако след всеки от опитите ни се казва дали търсеното число е по-малко или по-голямо от това, което сме казали.

Реклама

dgs · Пуснато на: Fri Nov 21, 2008 7:25 pm Заглавие:

Тоя алгоритъм щеше да пасне перфектно на задачата за зайците (Задача 14 на седмицата - още не е решена), стига там да можехме да правим 8 последователни опита (а не само един).
// Трябват ни (само) 5 последователни опита и ще нахраним (поне) 936 човека. Може и повече, стига да са ни останали живи зайци след 5-тия опит

Fed · Пуснато на: Fri Nov 21, 2008 8:20 pm Заглавие:

Двоично търсене по някакъв начин...

dgs · Пуснато на: Fri Nov 21, 2008 8:32 pm Заглавие:

И аз в предишния пост си мислех за двоично търсене.
Ама сега на второ четене, мисля, че 8 на брой опита не стигат за 100% сигурност при 1000 числа
С 8 опита и двоично търсене, ще стесним интервала до четири последователни числа. И едно от тези четири е търсеното
При 1000 числа, трябват 10 опита за двоичното търсене

Fed

Прав си...

NoThanks · Гост

martosss · Пуснато на: Sat Nov 22, 2008 4:07 pm Заглавие:

е ми трябва винаги да казваме числото, което е най-близко да средата на интервала... ама наистина с 8 опита не става Confused

с 9-10 опита е по-вероятно Smile

Methuselah · Пуснато на: Sat Nov 22, 2008 5:09 pm Заглавие:

С log₂|b - a| за [a;b] Mr. Green

dgs · Пуснато на: Sat Nov 22, 2008 5:27 pm Заглавие:

JusTok · Пуснато на: Sun Nov 23, 2008 10:07 pm Заглавие:

Това май не е възможно с по малко от 10 опита Confused

voknid

Деля 1000 на 2, резултата пак на 2 и т.н. докато получа число по-малко от 1. Ето какво се получава:
оп
ит 1000
1 = 500
2 = 250
3 = 125
4 = 62.5
5 = 31.25
6 = 15.625
7 = 7.8125
8 = 3.90625
9 = 1.953125
10 = 0.9765625
Извод: за гарантирано познаване на цяло число от 1 до 1000 са достатъчни 10 опита, ако след всеки опит знаем посоката (+ или -) към верния отговор. Не трябва ли автора на тази тема да и коригира заглавието - вместо 8, 10? Между другото - нещо подобно се използува в т.н. алгоритъм за сортиране на числа чрез "клатене". Ако бъркам нещо, поправете ме.

Пример: Игра "Познай теглото на предмета"
Стратегия:
1. След всеки грешен опит корегирам долната или горната граница на диапазона, в който търся.
2. За следващия опит избирам средата на новия диапазон.
3. Повтарям т.1 и т.2 докато диапазона се стесни достатъчно близо до верния отговор.

Начално положение: долна граница = 0 кг., горна = 1000 кг. Предмета тежи 300 кг. Аз не знам това, но трябва да го позная с минимален брой опити чрез налучкване или смятане.
опит 1 - посочвам 500 (средата), отговарят ми: "не улучи, надолу" (=> нова горна граница = 500)
опит 2 - посочвам 250 =(0 + 500)/2, отговарят ми: "не улучи, нагоре" (=> нова долна граница = 250)
опит 3 - посочвам 375 =(250+500)/2, отговарят ми: "не улучи, надолу" (=> нова горна граница = 375) и т.н. доближавайки се с всеки следващ опит все по-близо до верния отговор.
Трябва да помня последните долна и горна граница и да ги събирам и деля на 2 наум. Това е номера Laughing

charlie_eppes · Пуснато на: Fri Dec 12, 2008 5:59 am Заглавие:

Дайте пример!!! Ако да речем че числото е 71? Как ще стане работата???

savage309 · Пуснато на: Fri Dec 12, 2008 6:59 pm Заглавие:

charlie_eppes · Пуснато на: Fri Dec 12, 2008 7:19 pm Заглавие:

voknid · Пуснато на: Fri Dec 12, 2008 8:09 pm Заглавие:

charlie_eppes · Пуснато на: Fri Dec 12, 2008 8:40 pm Заглавие:

voknid · Пуснато на: Sat Dec 13, 2008 11:18 am Заглавие:

charlie_eppes · Пуснато на: Sat Dec 13, 2008 8:26 pm Заглавие: