If you're seeing this message, it means we're having trouble loading external resources on our website.

Ако си зад уеб филтър, моля, увери се, че домейните *. kastatic.org и *. kasandbox.org са разрешени.

Основно съдържание

Игра на отгатване

Да поиграем на една игра, за да добиеш представа как различните алгоритми за решаването на един и същи проблем могат драстично да се различават по своята ефективност. Компютърът ще избере наслуки цяло число между 1 и 16. Ти ще отгатваш числа, докато откриеш числото на компютъра, а компютърът ще те насочва всеки път дали предположението ти е по-голямо или по-малко от числото:
Когато откриеш числото, помисли върху това каква техника използва, когато трябваше да решиш кое е следващото число, с което ще опиташ.
Може би ти нацелва с 1, 2, 3, 4 и т. н. докато не позна вярното число. Наричаме този подход линейно търсене, защото отгатваме всички числа все едно те са подредени в редица. Той ще работи. Но какъв е най-големия брой предположения, които трябва да направиш? Ако компютърът избере 30, ти ще трябва да направиш 30 предположения. Разбира се, може да изкараш голям късмет и компютърът да избере 1 – тогава ще познаеш числото от първия опит. Но какво става със средния брой опити? Ако компютърът може да избере всяко число от 1 до 30 с еднаква вероятност, то средно ще ти трябват 15 опита, за да познаеш числото му.
Но ти можеш да направиш нещо по-ефикасно от просто налучкване с 1, 2, 3, 4, …, нали? Тъй като компютърът ти казва дали предположението ти е по-малко, по-голямо или точното число, можеш да започнеш налучкването с 15. Ако числото, което компютърът е избрал, е по-малко от 15, можеш да елиминираш всички числа между 15 и 30, защото знаеш, че 15 е твърде голямо. Обратно, ако числото, избрано от компютъра, е по-голямо от 15 можеш да елиминираш всички числа от 1 до 15. И в двата случая можеш да елиминираш около половината от числата. На следващото предположение елиминираш половината от оставащите числа. Продължавай по същия начин, винаги премахвайки половината от оставащите числа. Наричаме този подход двоично търсене и независимо от избраното от компютъра число трябва да можеш да го откриеш с не повече от 5 предположения.
Например опитай с числата от 1 до 300. Трябва да успееш да познаеш вярното число с не повече от 9 предположения.
Колко предположения ти бяха нужни, за да намериш числото? Защо никога не ти трябват повече от 9? (Можеш ли да измислиш математическо обяснение?)?
Ще се върнем отново на двоично търсене и ще видим как ти можеш да го използваш ефективно, за да търсиш елемент от JavaScript масив. Но първо нека разгледаме алгоритъм за един по-сложен проблем.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.

Искаш ли да се присъединиш към разговора?

Все още няма публикации.
Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.