Alperen ERTEN
Forum Bağımlısı
- Kayıt
- 15 Eylül 2010
- Mesaj
- 845
- Tepki
- 255
- Şehir
- Fethiye
- Bisiklet
- Geotech
Şimdi k sayısındaki merdiveni çıkılabilecek yol sayısına O(k) diyelim.. Yani O(25)'i bulmamız lazım.
k'nin 4'ten büyük olduğu her durum için ilk adım olarak 3 olasılık var; 1, 2 veya 3 merdiven.
Eğer 1 merdiven çıkarsan geri kalan merdivenler için çıkabileceğin yol sayısı O(k-1) kalır.
Eğer 2 merdiven çıkarsan geri kalan merdivenler için çıkabileceğin yol sayısı O(k-2) kalır.
Eğer 3 merdiven çıkarsan geri kalan merdivenler için çıkabileceğin yol sayısı O(k-3) kalır.
Yani
O(k) = O(k-1) + O(k-2) + O(k-3) olur. (Her olasılık bu denklemin içinde olacaktır)
O(1), O(2) ve O(3)'ü bulmak kolay zaten,
O(1) (Yani 1 merdiven çıkmak için kaç farklı yol izleyebileceğin) = 1
O(2) (1er 1er veya doğrudan 2 basamak) = 2
O(3) (1er 1er, 1+2, 2+1 veya doğrudan 3 basamak) = 4
Bundan sonrası zaten matematik hesap
O(4) = O(4-1) + O(4-2) + O(4-3) = O(3) + O(2) + O(1)= 1 + 2 + 4 =7
O(5) = O(4) + O(3) + O(2) = 7 + 4 + 2 = 13
O(6) = O(5) + O(4) + O(3) = 13 + 7 + 4 = 24
O(7) = O(6) + O(5) + O(4) = 24 + 13 + 7 =44
O(8) = O(7) + O(6) + O(5) = 44 + 24 + 13 = 81
.
.
.
.
.
O(25) = O(24) + O(23) + O(22) = 1.389.537 + 755.476 + 410.744 = 2.555.757
arkadaşlar çözüm bu şekilde gerçekleşti.
Ayrıca başka çözümler de var Edip ve Ali abilerime çok teşekkür ediyorum...
Onları da paylaşacak olursak,
Ali abinin alternatifi:
3 tane çıkış şeklimiz olduğu için ilk üç basamağı bulursak 4. basamak bundan önce gelen 3'ünün toplamı olur. Yani:
1 basamağı, sadece 1 adım atarak çıkarız buradan 1 farklı yol gelir. f(1)=1 olur.
2 basamağı, 1+1 veya 2 adım atarak 2 farklı şekilde çıkabiliriz buradan f(2)=2 olur.
3 basamağı, 1+1+1, 1+2, 2+1 ya da 3 adım atarak 4 farklı şekilde çıkabiliriz. Buradan da f(3)=4 olur.
Genel kural şöyledir:
f(n)=f(n-1)+f(n-2)+f(n-3). Yani f(5)=f(4)+f(2)+f(1)=7 olur. Koyu yazdığım yer çıkış sayısını temsil ediyor 3 tane olduğu için basamak sayılarını çıkarıyorsun.
Dediğim mantığı 25'e kadar yapıyorsun. Sonraki elemanları bulurken sonucu veren bir bağıntı ulaşabilirisin. Mesela f(13)=2.f(4)+3 gibi, bunu kafadan salladım. Kolay gelsin.
Bu da Edip abimin çözümleri:
Eğer sadece 1 veya 2 basamak çıkabiliyor olsaydın doğrudan Fibonacci dizisinin 25. basamağına bakabilirdin.
Ama 3. basamağı da çıkabildiğin için Tribonacci dizisinin 25. basamağına bakman gerekiyor..
Eğer 4 basamak da çıkabiliyor olsaydın Tetranacci dizisinin 25. basamağına bakman gerekirdi =)
benim tribonacci ve tetranacci ile alakam olmadığı için bunları hiç anlamadım :=)
Ali abinin çözümü ile ilk çözüm aynı
k'nin 4'ten büyük olduğu her durum için ilk adım olarak 3 olasılık var; 1, 2 veya 3 merdiven.
Eğer 1 merdiven çıkarsan geri kalan merdivenler için çıkabileceğin yol sayısı O(k-1) kalır.
Eğer 2 merdiven çıkarsan geri kalan merdivenler için çıkabileceğin yol sayısı O(k-2) kalır.
Eğer 3 merdiven çıkarsan geri kalan merdivenler için çıkabileceğin yol sayısı O(k-3) kalır.
Yani
O(k) = O(k-1) + O(k-2) + O(k-3) olur. (Her olasılık bu denklemin içinde olacaktır)
O(1), O(2) ve O(3)'ü bulmak kolay zaten,
O(1) (Yani 1 merdiven çıkmak için kaç farklı yol izleyebileceğin) = 1
O(2) (1er 1er veya doğrudan 2 basamak) = 2
O(3) (1er 1er, 1+2, 2+1 veya doğrudan 3 basamak) = 4
Bundan sonrası zaten matematik hesap
O(4) = O(4-1) + O(4-2) + O(4-3) = O(3) + O(2) + O(1)= 1 + 2 + 4 =7
O(5) = O(4) + O(3) + O(2) = 7 + 4 + 2 = 13
O(6) = O(5) + O(4) + O(3) = 13 + 7 + 4 = 24
O(7) = O(6) + O(5) + O(4) = 24 + 13 + 7 =44
O(8) = O(7) + O(6) + O(5) = 44 + 24 + 13 = 81
.
.
.
.
.
O(25) = O(24) + O(23) + O(22) = 1.389.537 + 755.476 + 410.744 = 2.555.757
arkadaşlar çözüm bu şekilde gerçekleşti.
Ayrıca başka çözümler de var Edip ve Ali abilerime çok teşekkür ediyorum...
Onları da paylaşacak olursak,
Ali abinin alternatifi:
3 tane çıkış şeklimiz olduğu için ilk üç basamağı bulursak 4. basamak bundan önce gelen 3'ünün toplamı olur. Yani:
1 basamağı, sadece 1 adım atarak çıkarız buradan 1 farklı yol gelir. f(1)=1 olur.
2 basamağı, 1+1 veya 2 adım atarak 2 farklı şekilde çıkabiliriz buradan f(2)=2 olur.
3 basamağı, 1+1+1, 1+2, 2+1 ya da 3 adım atarak 4 farklı şekilde çıkabiliriz. Buradan da f(3)=4 olur.
Genel kural şöyledir:
f(n)=f(n-1)+f(n-2)+f(n-3). Yani f(5)=f(4)+f(2)+f(1)=7 olur. Koyu yazdığım yer çıkış sayısını temsil ediyor 3 tane olduğu için basamak sayılarını çıkarıyorsun.
Dediğim mantığı 25'e kadar yapıyorsun. Sonraki elemanları bulurken sonucu veren bir bağıntı ulaşabilirisin. Mesela f(13)=2.f(4)+3 gibi, bunu kafadan salladım. Kolay gelsin.
Bu da Edip abimin çözümleri:
Eğer sadece 1 veya 2 basamak çıkabiliyor olsaydın doğrudan Fibonacci dizisinin 25. basamağına bakabilirdin.
Ama 3. basamağı da çıkabildiğin için Tribonacci dizisinin 25. basamağına bakman gerekiyor..
Eğer 4 basamak da çıkabiliyor olsaydın Tetranacci dizisinin 25. basamağına bakman gerekirdi =)
benim tribonacci ve tetranacci ile alakam olmadığı için bunları hiç anlamadım :=)
Ali abinin çözümü ile ilk çözüm aynı