Sonlu 01 dizilerinin sıralanması

Question

Eğer sonlu uzunluktaki 01-dizisinde beliren her 00'dan sonra 1 geliyorsa ve beliren her 11'den sonra 0 geliyorsa o diziye "Purple Dizisi" diyelim. Örneğin 1100110 - 7 uzunluğunda purple dizisidir. Ama 0101100 purple dizisi değildir. Buna göre en fazla 7 uzunluğundaki purple dizilerinden oluşan kümenin eleman sayısı kaçtır ?

Tek tek yazmayı denedim ve uzun sürüyor ve tek tek kontrol etmek gerekiyor farklı bir çözüm metodu var mı acaba ? 

Comments

Merhaba purplelephant, Matkafasi'na hoş geldin. Sitede soru sorarken dikkat edilmesi gereken pek çok kural var. Bunlardan en önemlilerinden birisi, soru soran kişinin yazdığı soru hakkında kendi denemelerini ve düşündüklerini yazması kuralı. Bu kuralın pek çok nedeni var. Bu konuda lütfen şuradaki yorumu okuyunuz. Genel kurallar hakkında da lütfen şuraya bakınız.

Kısacası: Neler düşündüğünüzü ve neleri denediğinizi yazmanızı istiyoruz.

Önemli anımsatma: Genel olarak kurallara uygun sorulmuş sorular yanıt bulmakta

---

Bu soruyu kendiniz mi yazdiniz? Purple'lar cok benzer. 

Aslinda ...000... ve ...111... gozukmesin isteniyor. 

---

1,2,3,4 uzunluklu olanları saymayı denedin mi?

Bir düzen olabilir.

---

Böyle bir dizi verildiğinde ardarda iki tane aynı rakam olanlardan birini silerek, hiç tekrarsız diziler elde ederiz. Bunların sayısı çok az. Bu işlem de birebir değil

Şimdi tersini düşünelim. Uzunluğu 7 veya daha az olan, 0-1 lerden oluşan (ardarda terimleri farklı olan)  bir dizi alalım. Bunların bazı terimlerini seçip, onları "ikileyelim" ( o terimlerin yanına aynısını yazalım). 

Bu şekilde oluşacak dizileri saymayı deneyebilirsin.

---

Çok teşekkürler. Bir şeyler denedim..

---

Bir kitaptan uyarladım.)

Answer 1

1 Uzunluğunda -> 0 / 1 = 2 

2 Uzunluğunda -> 10 / 01 = 2 

3 Uzunluğunda -> 001/110/ 101/010 = 4

4 Uzunluğunda -> 1010/ 0101/1101/0010/0110/1001 = 6

5 Uzunluğunda -> 01001/10110/10101/10010/11001/01101/01010/00110/11010/00101 = 10

6 Uzunluğunda -> = 16

7 Uzunluğunda -> = 26

Şöyle bir şey düşündüm: 

1 uzunluğunu ve 2'yi oluşturdum. 3 oluşturmak için 1 ve 2'yi birleştiriyoruz. 1'i 2'nin soluna ekleyeceğiz örneğin tekrar etmediği için 2 şer taneden dört tane oluşuyor. 4 uzunluğuna geçtiğimizde 3 ile 1 uzunluğunu birleştiriyoruz. Burda 2 tane tekrarlı 2 tane tekrarsız var. Tekrarsızların başına 2 tane koyabileceğimiz için 2.2 = 4 etti. Diğerlerinin başınada 1 ini koyabileceğimiz için 1 er taneden 6 

5 için 1 ve 4 aynı şekilde 4.2 = 8 + 2 = 10  6 için 6.2 = 12 + 4 = 16 

6 yı yazmadım onun yerine de bir önceki uzunluktaki dizide bulunan tekrarsızlar kadar tekrarlı oluşacak 

yani 5 de 6 tekrarsız vardı demekki 6 uzunluğunda bunlar 6 tekrarlı oluşturcak 10 taneside tekrarsız

dolayısıyla 7 de de 10.2 + 6 = 26 eder. 

( Tekrarlı => başında 11 veya 00; Tekrarsız => başında 10 veya 01)

Comments

Fibonacci dizisindeki sayılarının 2 katları çıkıyor.

---

Evet siz söyleyince fark ettim. Acaba tamamen denk mi geldi yoksa ilişkili mi ?

---

Raslantı değil çünki Fibonacci dizisi $F_0=0,\ F_1=1$ ve $F_{n+2}=F_n+F_{n+1}$ olarak tanımlanıyor.