თამაში გამოცნობაზე

მოდით, ვითამაშოთ პატარა თამაში, რათა წარმოდგენა შეგექმნათ, თუ როგორ შეიძლება განსხვავებულ ალგორითმებს, რომლებსაც ერთისა და იმავე ამოცანის გადასაჭრელად ვიყენებთ, ჰქონდეთ განსხვავებული ეფექტურობა. კომპიუტერი შემთხვევით აარჩევს მთელ რიცხვს 1-დან 15-მდე. თქვენ კი მანამ უნდა განაგრძოთ რიცხვების გამოცნობა, სანამ კომპიუტერის მიერ არჩეულ რიცხვს არ იპოვით, კომპიუტერი კი ყოველი არჩევანის შემდეგ გეტყვით, ეს რიცხვი მის რიცხვზე მეტია თუ ნაკლები:

როდესაც რიცხვს იპოვით, დაფიქრდით, რა მეთოდის იყენებდით ყოველ ჯერზე ახალი რიცხვის არჩევისას.

შეიძლება თავიდან აირჩიეთ 1, შემდეგ 2, შემდეგ 3, 4 და ა.შ. მანამ, სანამ სასურველ რიცხვს არ მიადექით. ამ მიდგომას ჩვენ ვუწოდებთ წრფივ ძებნას, რადგან რიცხვების გამოცნობას ვცდილობთ ისე, როგორც მიმდევრობაში. ეს მიდგომა მუშაობს. თუმცა, რამდენი რიცხვის მოსინჯვა შეიძლება დაგჭირდეთ პასუხამდე მისასვლელად? კომპიუტერს რომ აერჩია 15, მაშინ დაგჭირდებოდათ 15 ცდა. ან შეიძლებოდა, ძალიან იღბლიანი გამომდგარიყავით და კომპიუტერს აერჩია 1, ამ შემთხვევაში პირველივე ცდაზე გამოიცნობდით მის რიცხვს. და საშუალოდ რამდენი ცდა გამოდის? თუ კომპიუტერი თანაბარი ალბათობით ირჩევს 1-დან 15-მდე ნებისმიერ რიცხვს, მაშინ საშუალოდ 8 ცდა დაგჭირდებათ.

თუმცა, ხომ შეგიძლიათ, უფრო ეფექტური გზა აირჩიოთ, ვიდრე ცალ-ცალკე 1-ის, 2-ის, 3-ის და ა.შ. მოსინჯვაა, არა? ვინაიდან კომპიუტერი გეუბნებათ, არჩეული რიცხვი დაბალია, მაღალია თუ სწორი, შეგიძლიათ, პირდაპირ შუიდან დაიწყოთ და აირჩიოთ 8, შემდეგ, რადგან იცით, რომ 8 მაღალია, შეგიძლიათ გამორიცხოთ ყოველი რიცხვი 8-დან 15-მდე. თუ კომპიუტერის მიერ არჩეული რიცხვი მეტია 8-ზე, მაშინ შეგიძლიათ გამორიცხოთ ყოველი რიცხვი 1-დან 8-მდე. ნებისმიერ შემთხვევაში, შეგიძლიათ რიცხვების ნახევარი მოიცილოთ. შემდეგ ცდაზე შეგიძლიათ გამორიცხოთ დარჩენილი რიცხვების ნახევარი. ასე განაგრძეთ და ყოველ ჯერზე დარჩენილი რიცხვების ნახევარს გაცხრილავთ.

ჩვენ ამ განახევრების მეთოდს ორობით ძებნას ვუწოდებთ და მნიშვნელობა არ აქვს, კომპიუტერი 1-დან 15-მდე რომელ რიცხვს აარჩევს, თქვენ ამ მეთოდით სასურველი რიცხვის საპოვნელად არასდროს დაგჭირდებათ 4 ცდაზე მეტი.

მიდით, სცადეთ 1-დან 300-მდე რიცხვისთვის. 9 ცდაზე მეტი არ დაგჭირდებათ.

ამჯერად რამდენი ცდა დაგჭირდათ რიცხვის გამოსაცნობად? რატომ არასდროს არ გჭირდებათ 9 ცდაზე მეტი? (შეგიძლიათ მათემატიკური ახსნა მოიფიქროთ)?

ჩვენ დავუბრუნდებით ორობით ძებნას და ვნახავთ, რამდენად ეფექტურად გამოიყენებთ მას JavaScript-ის მასივში საგნის მოსაძებნად. თუმცა, ჯერ უფრო ეშმაკური ამოცანის გადასაჭრელი ალგორითმი განვიხილოთ.

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.