Vaqt murakkabligi
O(2^n - 1)
Xanoy minoralari — bu klassik rekursiv boshqotirma. Barcha disklarni boshlang'ich ustundan maqsadli ustunga bittadan ko'chirish kerak. Bunda hech qachon katta diskni kichik diskning ustiga qo'yish mumkin emas.
Qanday ishlaydi (Rekursiya):
1. Yuqoridagi n-1 ta diskni boshlang'ich ustundan yordamchi ustunga ko'chirish
2. Eng katta diskni boshlang'ich ustundan maqsadli ustunga ko'chirish
3. n-1 ta diskni yordamchi ustundan maqsadli ustunga ko'chirish
Vaqt murakkabligi: O(2^n - 1) — jami 2^n - 1 ta ko'chirish
Xotira murakkabligi: O(n) — rekursiv chaqiruvlar steki
Xususiyatlari:
- Minimal ko'chirishlar soni: 2^n - 1
- "Bo'lib tashla va hukmronlik qil" usulining klassik namunasi
- Rekursiyaning imkoniyatlarini namoyish etadi
Ushbu boshqotirma matematik Édouard Lucas tomonidan 1883-yilda ixtiro qilingan. Rivoyatlarga ko'ra, ibodatxonadagi rohiblar 64 ta oltin diskni ko'chirishmoqda — boshqotirma yakunlanganda dunyoning oxiri keladi (buning uchun 18 446 744 073 709 551 615 ta ko'chirish talab etiladi).
O'xshash algoritmlar
Ko'p beriladigan savollar
- Xanoy minoralari nima?
- Xanoy minoralari — bu klassik rekursiv boshqotirma. Barcha disklarni boshlang'ich ustundan maqsadli ustunga bittadan ko'chirish kerak. Bunda hech qachon katta diskni kichik diskning ustiga qo'yish mumkin emas.
- Xanoy minoralari murakkabligi qanday?
- Vaqt (o'rtacha): O(2^n - 1) · Xotira: O(n)
- Ushbu Xanoy minoralari vizualizatori kimlar uchun?
- Xanoy minoralari vizualizatsiyasi "Bo‘lib tashla va hukmronlik qil" kategoriyasida o'rta darajadagi o'rganuvchilar uchun mo'ljallangan. Talabalar, texnik suhbatlarga tayyorgarlik va amaliy takrorlash uchun foydali.
- Xanoy minoralari ga o'xshash qanday algoritmlar bor?
- Shu kategoriyada (Bo‘lib tashla va hukmronlik qil) quyidagilarni ko'rishingiz mumkin: Binary Exponentiation. Har biri interaktiv vizualizatsiyaga ega.