Page 26 - Bilgisayar Bilimi Kur 1| I. Bölüm

Doğru cevap 17’dir. Sorunun çözümünde satır ve sütunların kesişim noktalarından yararlanılmıştır.
Şekilde görüldüğü gibi 1. satır 1. sütundan başlanarak satır satır işlem yapılır ve her kesişim noktasında
soldaki ve üstteki değerler toplanır. Kesişim noktasının üstünde ya da solunda değer yoksa aynı sayı
tekrar yazılır. Örneğin 1. satır 1. sütundaki değer 1’dir. 1. satır 2. sütuna geçildiğinde sadece sol tarafta
1 değeri olduğu için 1 yazılır. 2. satır 2. sütunda ise kesişim noktasının solunda ve üstünde 1 değeri
vardır. Bu nedenle bu kesişim noktasının değeri 1+1=2 olur. En son 5. sütun 4. satıra gelindiğinde ise
9+8=17 olur.
1 2 3 4 5

A
1 1 1 1 1 1

2 1 2 3 4 5

3 1 2 4 9

4 1 2 3 8 17 B

Bu problemden neler öğrendik?

Yol hesaplama, çok iyi bilinen dinamik programlama uygulamalarından biridir.

2.1.5.5. Hanoi Kulesi

A B C

Yukarıdaki şekilde çeşitli renklerle gösterilen tahta parçaları, A çivisinden C çivisine aşağıdaki kural-
lara göre geçirilmek istenmektedir.
• Küçük tahtaların üstüne büyük tahtalar yerleştirilemez.

• Aynı anda sadece bir disk oynatılabilir.
Buna göre tahta parçalarını A’dan C’ye taşıyınız.
Bu soruda 5 tahta parçasının C çivisine taşınması gerekmektedir. Sorunun çözümü aşağıdaki gibidir.

A B C A B C

a. 2 hamle b. 1 hamle

40