Wie finden Sie die Anzahl der Möglichkeiten, die die ganzen Zahlen 1,2,3 summieren können?

Question

Geben Sie für einen Satz von Ganzzahlen 1,2 und 3 die Anzahl der Möglichkeiten an, die diese zu n addieren können. (Die Reihenfolge ist wichtig, dh n ist 5. 1 + 2 + 1 + 1 und 2 + 1 + 1 + 1 sind zwei verschiedene Lösungen)

Meine Lösung beinhaltet die Aufteilung von n in eine Liste von 1en, wenn n = 5 , A = [1,1,1,1,1]. Und ich werde mehr Unterlisten rekursiv aus jeder Liste erzeugen, indem ich benachbarte Zahlen hinzufüge. A wird also 4 weitere Listen erzeugen: [2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2] und jede diese Listen werden weiter Sublisten erzeugen, bis es einen abschließenden Fall wie [3,2] oder [2,3]

(in Python) Hier bin meine vorgeschlagene Lösung

ways = [] 
def check_terminating(A,n): 
    # check for terminating case 
    for i in range(len(A)-1): 
     if A[i] + A[i+1] <= 3: 
      return False # means still can compute 
    return True 

def count_ways(n,A=[]): 
    if A in ways: 
     # check if alr computed if yes then don't compute 
     return True 
    if A not in ways: # check for duplicates 
     ways.append(A) # global ways 
    if check_terminating(A,n): 
     return True # end of the tree 
    for i in range(len(A)-1): 
     # for each index i, 
     # combine with the next element and form a new list 
     total = A[i] + A[i+1] 
     print(total) 
     if total <= 3: 
      # form new list and compute 
      newA = A[:i] + [total] + A[i+2:] 
      count_ways(A,newA) 
      # recursive call 

# main    
n = 5 
A = [1 for _ in range(n)] 

count_ways(5,A) 
print("No. of ways for n = {} is {}".format(n,len(ways))) 

Darf ich wissen, ob ich erreicht bin auf dem richtigen Weg, und wenn ja, gibt es eine Möglichkeit, diesen Code effizienter zu machen?

Bitte beachten Sie, dass dies kein Münzwechsel Problem ist. Beim Münzwechsel ist die Reihenfolge des Auftretens nicht wichtig. In meinem Problem unterscheidet sich 1 + 2 + 1 + 1 von 1 + 1 + 1 + 2, aber beim Münzwechsel sind beide gleich. Bitte geben Sie für diese Antwort keine Lösungen zum Münzwechsel an.

Edit: Mein Code funktioniert, aber ich würde gerne wissen, ob es bessere Lösungen gibt. Vielen Dank für Ihre Hilfe :)

Answer 1

die Rezidiv rel ation ist F (n + 3) = F (n + 2) + F (n + 1) + F (n) mit F (0) = 1, F (-1) = F (-2) = 0.Dies sind die tribonacci Zahlen (eine Variante der Fibonacci-Zahlen):

Es ist möglich, eine einfache O schreiben (n) Lösung:

def count_ways(n): 
    a, b, c = 1, 0, 0 
    for _ in xrange(n): 
     a, b, c = a+b+c, a, b 
    return a 

Es ist schwieriger, aber möglich, das Ergebnis in relativ wenige Arithmetik zu berechnen Operationen:

def count_ways(n): 
    A = 3**(n+3) 
    P = A**3-A**2-A-1 
    return pow(A, n+3, P) % A 

for i in xrange(20): 
    print i, count_ways(i) 

Answer 2

Die Idee, die Sie beschreiben, klingt richtig. Es ist einfach, eine rekursive Funktion zu schreiben, die die richtige Antwort ... langsam erzeugt.

Sie können es dann schneller machen, indem Sie die Antwort memoisieren. Behalte einfach ein Wörterbuch mit Antworten, die du bereits berechnet hast. Prüfen Sie in Ihrer rekursiven Funktion, ob Sie eine vorberechnete Antwort haben. Wenn ja, gib es zurück. Wenn nicht, berechnen Sie es, speichern Sie diese Antwort im Wörterbuch und geben Sie die Antwort zurück.

Diese Version sollte schnell ausgeführt werden.

Answer 3

Ein O (n) Verfahren möglich:

def countways(n): 
    A=[1,1,2] 
    while len(A)<=n: 
     A.append(A[-1]+A[-2]+A[-3]) 
    return A[n] 

Die Idee ist, dass wir arbeiten können, wie viele Möglichkeiten, eine Sequenz mit n zu machen, indem jede Wahl unter Berücksichtigung (1,2,3) für die letzte Partitionsgröße

z.B. zu zählen Entscheidungen für (1,1,1,1) berücksichtigen:

1. Entscheidungen für (1,1,1) durch eine 1
2. Entscheidungen für (1,1) durch ein 2
gefolgt gefolgt
3. Entscheidungen für (1), gefolgt von einem 3

Wenn Sie die Ergebnisse (statt nur die Zählung) benötigen, können Sie diesen Ansatz anpassen, wie folgt:

cache = {} 
def countwaysb(n): 
    if n < 0: 
     return [] 
    if n == 0: 
     return [[]] 
    if n in cache: 
     return cache[n] 
    A = [] 
    for last in range(1,4): 
     for B in countwaysb(n-last): 
      A.append(B+[last]) 
    cache[n] = A 
    return A