Bu savol javobi koʻpchilik uchun qiziq boʻlsa kerak.
Bizga bitta usul kerak.
Qadamlari aniq bo`lishi kerak. Ehtimollik bilan topish bizga yarashmaydi.
Demak, bitta yoqgichni olamiz. Uni yuqoriga qaratamiz. Keyingisiga o`tamiz.
1. Agar pastga tushgan boʻlsa, sanoqqa 1 qoʻshib davom etamiz.
2. Agar yuqoriga qaragan boʻlsa, sanoqni yozib qoʻyib. Buni pastga tushiramiz.
Yoʻnalishimizni (orqaga) almashtiramiz. Orqaga qaytishni boshlaymiz.
Yoʻlda yuqoriga qaragan yoqgich chiqadi. Chunki oradagilarni hammasini pastga tushirganmiz (oʻchirganmiz). Qancha yurganimizni yozib qoʻyamiz.
Yo`nalishimizni almashtirib, boshqattan boshlaymiz.
Endi savol qachon toʻxtashda.
Qogʻozda oxirgi marta yozgan (maksimal) sonimizcha yuramiz. Agar orada yuqoriga qaragan yoqgich chiqmasa, demak shu yozganimiz yoqgichlar soni boʻladi.
Masalan, faraz qilamiz, 100 ta yoqgich bor va 1 tasi tepaga qaragan. 20 qadam yurib ilk tepaga qaraganni topdik. Shu biz uchun hatboshi boʻladi. Oldingga qarab sanab ketamiz. 100 tadan oʻtgandan keyin yana shunga kelib qolgan boʻlamiz. 100 ni yozib, pastga tushirib, orqaga ketamiz. 100 qadamdan keyin hali ham hammasi pastga qaragan. Bilamizki 100 ta ekan.
Bu N=1.
Endi faraz qilamiz 2 tasi yuqoriga qaratilgan. Birinchi yuqoriga qaragandan boshladik. 40 qadam yurib, yana yuqoriga qaraganni topdik. Buni pastga tushiramiz va orqaga qaytamiz. 40 tadan keyin yuqoriga qaraganga keldik. Demak hatboshidamiz. Endi boshqattan boshlaymiz. 100 ta yoqgichdan o`tganda yuqoriga qaraganga kelamiz. Buni o`chiramiz va orqaga 100 ta yuramiz. Shunda hammasi o`chiq bo`ladi. Demak maksimal 100 ta.
Bu N=2.
Qolgan ixtiyoriy N uchun ham shu shaklda amalga ochiriladi.
Izohlar va javoblar uchun katta rahmat!
Pattern orqali ham ko`p izohlar bo`ldi, lekin aniqlik kerakligi uchun uni tasdiqlamadim.
https://t.me/DrAlgorithm/399