Döşeme Dikdörtgenleri
İki bulmacanız var. 1xn boyutlarında bir dikdörtgeni, 1x1 kareler ve 1x2 dikdörtgenlerin karışımıyla kaç farklı şekilde doldurabilirsiniz? 2xn boyutlarında bir dikdörtgeni, 1x2 dikdörtgenlerle kaç farklı şekilde doldurabilirsiniz?
CHALLENGE
Bu iki bulmaca neden aynı cevabı veriyor? Doldurulacak dikdörtgenlerin uzunluğu 10 olduğunda cevaplar nelerdir? Peki ya uzunlukları 20 olduğunda?
KEŞİF
Bu iki problem birbirine ve önceki bulmacalara nasıl benziyor? 1x1 ve 1x3 parçaları kullanırsak 1xn bulmacasında neler değişir? 1x1, 1x2 ve 1x3 parçaları kullanırsak 1xn bulmacasında neler değişir?
notlar
CHALLENGE
Önceki sonuçların yeni bir bulmacanın bir kısmına veya tamamına nasıl uygulanacağını görmek güçlü bir beceridir.
Bu iki bulmaca doğası gereği tamamen aynıdır. 2 x n dikdörtgenindeki dikey parçalar, 1 x n dikdörtgenindeki 1 x 1 parçalara karşılık gelir ve 2 x n dikdörtgenindeki yatay parçalar, 1 x n dikdörtgenindeki 1 x 2 parçalara karşılık gelir. Dolayısıyla, iki bulmaca arasında gerçekte hiçbir fark yoktur.
Ayrıca, 1 x n dikdörtgen bulmacası, “Fibonacci – 2”deki adım bulmacasıyla tamamen aynıdır. Birer adım atmak, 1 x 1 kare yerleştirmek gibidir ve ikişer adım atmak, 1 x 2 dikdörtgen yerleştirmek gibidir. İki bulmaca aynı olduğundan, analiz ve sonuçlar da aynıdır.
KEŞİF
1x1 ve 1x3 dikdörtgenler kullanırsak, birçok şey değişir. İlk birkaç değere bakalım ve bunların nasıl hesaplandığını düşünelim. İlk birkaç değer için 1, 1, 2, 3, 4, 6 ve 9 elde ederiz. Genel olarak, bir sonraki değer, mevcut değer ile ondan iki adım önceki değerin toplamıdır. Hesaplaması oldukça basittir, ancak artık Fibonacci dizisi değildir.
1'i 1, 1'i 2 ve 1'i 3 ile çarparsak, durum çok daha çarpıcı bir şekilde değişir. Şimdi ilk birkaç değer 1, 2, 4, 7, 13 ve 24 ile verilir. Dizideki bir sonraki değer, önceki üç değerin toplamıdır.
Bir önceki terimleri içeren bir formülle sonraki terimlerini tanımlayan bu tür dizilere özyinelemeli diziler denir. Fibonacci sayıları tek özyinelemeli dizi değildir, ancak muhtemelen en ünlüsüdür.