Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
4 beğenilme 0 beğenilmeme
1.9k kez görüntülendi

"Tower of Hanoi" isimli bulmacada yapmamiz gereken $n$ uzunlugundaki kuleyi katlarin azalan yuksekligini bozmadan $A$ noktasindan $C$ noktasina tasimak...


image


Eger $4$ birimlik bir kulemiz var ise asagidaki gif'teki gibi $15=2^4-1$ halede bunu basarabiliyoruz. Daha az hamlede basarmak mumkun mu? Daha genel olarak en az $2^n-1$ hamle ile bunu gerceklestirebilecegimizi gosteriniz.

image



Soruya isinmak icin bu internet sitesinden bu bulmacayi disk sayisini $3$ ile $8$ arasinda secip oynayabilirsiniz ya da cozumunu (Solve! butonuna) tiklayarak gorebilirsiniz.

Orta Öğretim Matematik kategorisinde (25.5k puan) tarafından 
tarafından düzenlendi | 1.9k kez görüntülendi

sercan hocam özelden yazamıyorum malesef :).varmış oyle bır uygulama :D

tam soruyu yazıcaktım benden önce davranmış sercan hocam:)

Bir de algoritmasini sormustum, ona da bakabilirsin, cevabi yok henuz.

1 cevap

1 beğenilme 0 beğenilmeme
En İyi Cevap

$n$ diski $A$'dan $C$'ye aktarmayı hedefleyen oyuna $(n)_{AC}$ ve bu oyunu kazanmak için gereken minimum hamle sayısına $s(n)_{AC}$ diyelim. $s(1)_{AC}=2^1-1=1$ ve $s(1)_{AC}=2^2-1=3$ olduğu aşikar. Şimdiyse $s(n)_{AC}=2^n-1$ ve $s(n+1)_{AC}=2^{n+1}-1$ için de sağlandığını ispatlayalım. Diyelim ki elimizde $(n+1)_{AC}$ oyunu var. İlk olarak $s(n)_{AB}$ hamle yaparak bir $(n)_{AB}$ oyunu oynamalıyız ki $(n+1)$. diski $C$'ye aktarabilelim. $(n)_{AB}$ oyununu oynadıktan sonra $(n+1)$. diski $C$'ye aktararak $1$ hamle daha yaparız. Ardından bu sefer de $s(n)_{BC}$ hamle yaparak bir $(n)_{BC}$ oyunu oynarsak $(n+1)_{AC}$ oyununu tamamlamış oluruz. $s(n)_{AC}=s(n)_{AB}=s(n)_{BC}=2^n-1$ olduğundan $s(n+1)_{AC}=1+s(n)_{AB}+s(n)_{BC}=1+2^n-1+2^n-1=2^{n+1}-1$ olmalıdır. Böylece sorudaki önermeyi tümevarımla ispatlamış olduk.

(2.9k puan) tarafından 
tarafından seçilmiş
20,275 soru
21,807 cevap
73,489 yorum
2,444,072 kullanıcı