Αριθμός ρυθμίσεων

ψήφοι
4

Ας υποθέσουμε ότι έχουμε n στοιχεία, ένα 1 , α 2 , ..., α n , τοποθετημένα σε ένα κύκλο. Δηλαδή, μια 2 είναι μεταξύ ενός 1 και ένα 3 , ένας 3 είναι μεταξύ ενός 2 και ένα 4 , ένας n είναι μεταξύ ενός n -1 και ένα 1 , και ούτω καθεξής.

Κάθε στοιχείο μπορεί να λάβει τη αξία είτε 1 ή 0. Δύο ρυθμίσεις είναι διαφορετικά αν οι αντίστοιχοι εκεί μια θ «s των οποίων οι τιμές διαφέρουν. Για παράδειγμα, όταν το η = 3, (1, 0, 0) και (0, 1, 0) είναι διαφορετικές ρυθμίσεις, ακόμη και αν μπορεί να είναι ισομορφική υπό περιστροφή ή αντανάκλαση.

Επειδή υπάρχουν n στοιχεία, καθένα από τα οποία μπορεί να πάρει δύο τιμές, ο συνολικός αριθμός των ρυθμίσεων είναι 2 n .

Εδώ είναι το ερώτημα:

Πόσες ρυθμίσεις είναι δυνατόν, έτσι ώστε δεν υπάρχουν δύο γειτονικά στοιχεία και οι δύο έχουν την τιμή 1; Αν βοηθάει, σκεφτείτε μόνο τις περιπτώσεις όπου n > 3.

Ζητώ εδώ για πολλούς λόγους:

  1. Αυτό προέκυψε, ενώ ήμουν επίλυση ενός προβλήματος προγραμματισμού
  2. Ακούγεται σαν το πρόβλημα μπορεί να επωφεληθεί από Boolean λογική / αριθμητική bit
  3. Ίσως δεν υπάρχει κλειστό λύση.
Δημοσιεύθηκε 10/12/2008 στις 00:41
πηγή χρήστη
Σε άλλες γλώσσες...                            


4 απαντήσεις

ψήφοι
10

Ας πρώτα να θέσουμε το ερώτημα «πόσα 0-1 ακολουθίες μήκους n είναι χωρίς δύο συνεχόμενες 1s εκεί;» Έστω η απάντηση είναι Α (n). Έχουμε Α (0) = 1 (ο κενός αλληλουχία), Α (1) = 2 ( "0" και "1"), και Α (2) = 3 ( "00", "01" και "10", αλλά δεν "11").

Για να καταστεί ευκολότερη να γράψει ένα υποτροπή, θα υπολογίσουμε ένα (ν) ως το άθροισμα των δύο αριθμών:
Β (n), τον αριθμό αυτών των αλληλουχιών που τελειώνουν με 0, και
C (n), ο αριθμός αυτών των αλληλουχίες που τελειώνουν με ένα 1.

Στη συνέχεια, Β (n) = Α (n-1) (λαμβάνει κάθε τέτοια αλληλουχία μήκους n-1, και να προσαρτάται 0)
και C (n) = Β (n-1) (επειδή εάν έχετε ένα 1 στην θέση Ν , θα πρέπει να έχετε 0 σε η-1.)
Αυτό δίνει α (n) = Β (n) + C (n) = α (n-1) + Β (n-1) = α (n-1) + Α (n-2). Μέχρι τώρα θα πρέπει να είναι εξοικειωμένοι :-)

Α (n) είναι απλά ο αριθμός Fibonacci F n + 2 , όπου η ακολουθία Fibonacci ορίζεται από
F 0 = 0, F 1 = 1, και F n + 2 = F n + 1 + F n για n ≥ 0.

Τώρα για την ερώτησή σας. Θα μετρήσει τον αριθμό των ρυθμίσεων με 1 = 0 και 1 = 1 ξεχωριστά. Για την πρώτη, ένα 2 ... α n μπορεί να είναι οποιαδήποτε αλληλουχία καθόλου (χωρίς διαδοχικές 1s), έτσι ώστε ο αριθμός είναι Α (n-1) = F n + 1 . Για την τελευταία, πρέπει να έχουμε μια 2 = 0, και στη συνέχεια ένα 3 ... α n είναι η οποιαδήποτε αλληλουχία που δεν διαδοχικές 1s που τελειώνει με μια 0 , δηλαδή Β (n-2) = Α (n-3) = F n- 1 .

Έτσι η απάντηση είναι F n + 1 + F n-1 .

Στην πραγματικότητα, μπορούμε να προχωρήσουμε ακόμη περισσότερο από ό, τι αυτή την απάντηση. Σημειώστε ότι εάν καλέσετε την απάντηση ως
G (n) = F n + 1 + F n-1 , τότε
το G (n + 1) = F n + 2 + F n , και
το G (n + 2) = F n + 3 + F n + 1 , έτσι ώστε ακόμη και G (n) ικανοποιεί την ίδια επανάληψη όπως η ακολουθία Fibonacci! [Στην πραγματικότητα, οποιοσδήποτε γραμμικός συνδυασμός Fibonacci-ειδείς αλληλουχίες θα ικανοποιήσει την ίδια επανάληψη, έτσι δεν είναι όλα αυτά που εκπλήσσει.] Έτσι ένας άλλος τρόπος για να υπολογίσει τις απαντήσεις θα ήταν με τη χρήση:
G (2) = 3
G (3) = 4
G ( n) = G (n-1) + G (n-2) για n≥4.

Και τώρα μπορείτε επίσης να χρησιμοποιήσετε την κλειστή μορφή F n = (α nn ) / (α-β) (όπου α και β είναι (1 ± √5) / 2, οι ρίζες του x 2 -χ-1 = 0), για να πάρετε
G (n) = ((1 + √5) / 2) n + ((1-√5) / 2) n .
[Μπορείτε να αγνοήσει το δεύτερο όρο επειδή είναι πολύ κοντά στο 0 για μεγάλα n, στην πραγματικότητα G (n) είναι το πλησιέστερο ακέραιο έως ((1 + √5) / 2) n για όλα n≥2.]

Απαντήθηκε 10/12/2008 στις 01:00
πηγή χρήστη

ψήφοι
1

Αποφάσισα να χαράξει ένα μικρό script για να το δοκιμάσετε:

#!/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, μου έδωσε συνολικά 11 δυνατότητες με 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10010, 10100.

PS - συγχωρήστε το όχι () στο παραπάνω κώδικα.

Απαντήθηκε 10/12/2008 στις 01:14
πηγή χρήστη

ψήφοι
0

Το πρόβλημα αυτό είναι πολύ παρόμοιο με Zeckendorf παραστάσεις . Δεν μπορώ να βρω μια προφανής τρόπος για να εφαρμοστεί το θεώρημα Zeckendorf, λόγω του περιορισμού της κυκλικότητας, αλλά οι αριθμοί Fibonacci είναι προφανώς πολύ διαδεδομένη σε αυτό το πρόβλημα.

Απαντήθηκε 10/12/2008 στις 01:38
πηγή χρήστη

ψήφοι
0

Ρίχνουν αφελές σενάριο μου στο μίγμα. Πολλές ευκαιρίες για την προσωρινή αποθήκευση μέρους αποτελέσματα, αλλά έτρεξε αρκετά γρήγορα για μικρά n που δεν έκαναν τον κόπο.

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)
Απαντήθηκε 10/12/2008 στις 01:16
πηγή χρήστη

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