düzenlemelerin sayısı

oy
4

Elimizdeki varsayalım n elemanları, bir 1 , bir 2 , ..., bir n, bir daire içinde düzenlenmiş. Diğer bir deyişle, bir 2 arasındadır bir 1 ve bir 3 , bir 3 arasında bir 2 ve bir 4 , bir n arasında bir n -1 ve bir 1 ve benzerini.

Orada mukabil eğer 0 veya 1 iki düzenlemeler de farklı her bir elemanı değerini alabilir bir I 'in, değerleri farklıdır. Örneğin, zaman için , n = 3, (1, 0, 0) ve (0, 1, 0) bu dönüş açısı veya yansıtma altında izomorfik olsa bile, farklı düzenlemeler bulunmaktadır.

Olduğundan n adet iki değer alabilir her biri elemanları, düzenlemelerin sayısı 2 , n .

İşte soru:

Kaç düzenlemeler hiçbir iki komşu elemanlar hem eşittir 1 olacak şekilde, mümkün olan? Eğer yardımı olacaksa, sadece vakaları dikkate n > 3.

Ben çeşitli nedenlerle buraya soruyorum:

  1. Bir programlama problem çözme iken bu ortaya çıktı
  2. Bu Boole mantığı / bit aritmetik yararlanabilir sorun var gibi görünüyor
  3. Belki hiçbir kapalı bir çözüm yoktur.
Oluştur 10/12/2008 saat 00:41
kaynak kullanıcı
Diğer dillerde...                            


4 cevaplar

oy
10

İlk soruyu soralım "kaç n uzunluğundaki 0-1 dizileri hiçbir iki ardışık 1'ler ile vardır?" Cevap A (n) olsun. A (0) = 1 (boş sekansı), bir (1) = 2 ( "0" ve "1"), ve A (2) = 3 ( "00", "01" ve "10" sahiptir, ancak değil "11").

Daha kolay bir nüks yazma hale getirmek için, iki sayının toplamı olarak bir (n) değerinin hesaplanması gerekir:
(n) B, 0 ile sona bu dizilerin sayısını ve
bu C, (n), sayı a 1 ile son dizileri.

Daha sonra B (n) A (n-1) (uzunluk, n-1 böyle bir dizisini alır ve bir 0 ekleme) =
((n-1) B ve C, (n) = çünkü pozisyonu n'de bir 1 varsa , olması gerekir, bir 0, n-1). en
Bu A (n) = B (n) + C, (n) A (n-1) + B (n-1) = = veren bir (n-1) + A (n-2). Artık tanıdık :-) olmalıdır

A (n) basit Fibonacci sayı F n + 2 Fibonacci dizisi ile tanımlanır
F 0 = 0, F, 1 = 1 ve F n + 2 = F , n + 1 + K , n , n ≥ 0.

Şimdi soru için. Biz ile yaptığı düzenlemelerin sayısını sayarız 1 = 0 ve bir 1 ayrı = 1. Eski, bir 2 ... bir N (birbirini izleyen 1s) hiç bir sekans olabilir, bu nedenle numarası A (n-1) = F , n + 1 . İkincisi için bir olması gerekir 2 ardından = 0 ve 3 ... bir n birbirini izleyen 1s dizisidir.CONTROL 0 ile sona erer , yani B (n-2) (n-3) = K = N- 1 .

Yani cevap F n + 1 + F n-1 .

Aslında bunu cevap daha da ileri gidebilir. Not siz cevap çağrı durumunda
G (n) = E n + 1 + K , n-1 , ardından
G (n + 1) = F , n + 2 + K , n , ve
G (n + 2) = F , n + 3 + K n + 1 , bu da G (n) Fibonacci dizisi ile aynı nüks tatmin! [Aslında, Fibonacci benzeri sekansların herhangi bir doğrusal kombinasyonunun aynı nüks tatmin edecek, bu nedenle bütün bu şaşırtıcı değildir.] Bu nedenle cevaplar hesaplamak için başka bir yol ile olabilir
G (2) = 3
G (3) = 4
(G n≥4 n) = G (n-1) + G (n-2).

Şimdi de, aynı zamanda kullanabilir kapalı form F , n = (α nn ) / (α-β) (α ve β: (1 ± √5) / 2 x kökleri 2 -x-1 = 0), elde etmek için
G (n) = ((1 + √5) / 2) n + ((1-√5) / 2) n .
[Bu aslında G (n) 'de, büyük n, 0 çok yakın olduğu için ikinci terimi ihmal edilebilir ((1 + √5) / 2) en yakın tam sayı , n , tüm n≥2 için.]

Cevap 10/12/2008 saat 01:00
kaynak kullanıcı

oy
1

Ben de denemek için küçük bir komut dosyası doğramaya karar:

#!/usr/bin/python
import sys

# thx google 
bstr_pos = lambda n: n>0 and bstr_pos(n>>1)+str(n&1) or ""

def arrangements(n):
    count = 0
    for v in range(0, pow(2,n)-1):
        bin = bstr_pos(v).rjust(n, '0')
        if not ( bin.find("11")!=-1 or ( bin[0]=='1' and bin[-1]=='1' ) ):
            count += 1
            print bin
    print "Total = " + str(count)

arrangements(int(sys.argv[1]))

5 için bu Koşu, 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100 ile bana 11 olasılıkların toplam verdi.

PS - Pardon değil () Yukarıdaki kodda.

Cevap 10/12/2008 saat 01:14
kaynak kullanıcı

oy
0

Bu sorun çok benzer Zeckendorf temsiller . Ben nedeniyle dairesellik kısıtlamadan dolayı, Zeckendorf Teoremi uygulamak için bariz bir yol bulamıyorum ama Fibonacci sayıları belli ki bu problemde çok yaygındır.

Cevap 10/12/2008 saat 01:38
kaynak kullanıcı

oy
0

Abonenin naif senaryoyu Fırlatma. Kısmi sonuçları önbelleğe için fırsat bol ama benim rahatsız etmedi küçük n yeterince hızlı koştu.

def arcCombinations(n, lastDigitMustBeZero):
    """Takes the length of the remaining arc of the circle, and computes
       the number of legal combinations.
       The last digit may be restricted to 0 (because the first digit is a 1)"""

    if n == 1: 
        if lastDigitMustBeZero:
            return 1 # only legal answer is 0
        else:
            return 2 # could be 1 or 0.
    elif n == 2:
        if lastDigitMustBeZero:
            return 2 # could be 00 or 10
        else:
            return 3 # could be 10, 01 or 00
    else:
        # Could be a 1, in which case next item is a zero.
        return (
            arcCombinations(n-2, lastDigitMustBeZero) # If it starts 10
            + arcCombinations(n-1, lastDigitMustBeZero) # If it starts 0
            )

def circleCombinations(n):
    """Computes the number of legal combinations for a given circle size."""

    # Handle case where it starts with 0 or with 1.
    total = (
            arcCombinations(n-1,True) # Number of combinations where first digit is a 1.
            +
            arcCombinations(n-1,False) # Number of combinations where first digit is a 0.
        )
    return total


print circleCombinations(13)
Cevap 10/12/2008 saat 01:16
kaynak kullanıcı

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more