Wie programmiert man dieses Puzzle rekursiv?

Question

Also habe ich einen Denkfehler in meinem Kopf gelöst, aber es fällt mir schwer, es in eine rekursive Definition zu übersetzen. Der Denkfehler ist das gebrochene Gewichtsproblem (https://mathlesstraveled.com/2010/05/01/the-broken-weight-problem/):

Ein Kaufmann hatte ein vierzig Pfund messendes Gewicht, das als Ergebnis eines Sturzes in vier Stücke zerbrach. Als die Stücke anschließend gewogen wurden, wurde gefunden, dass das Gewicht jedes Stücks eine ganze Anzahl von Pfund betrug und dass die vier Stücke verwendet werden konnten, um jedes integrale Gewicht zwischen 1 und 40 Pfund zu wiegen. Wie groß waren die Gewichte der Teile?

die Antwort ist also (1,3,9,27), die als das Doppelte der Summe der bisherigen Bedingungen verallgemeinert werden kann + 1.

Ich versuche, eine Python-Funktion zu schreiben, die rekursiv zurückkehren nter Begriff der Sequenz und ich habe eine schwere Zeit davon, weil ich noch nicht so gut in der Rekursion bin. Ich dachte Art heraus, dass ich auch die laufende Summe zurück ....

Dies ist unvollständig Code meines Denkprozesses so weit:

def x(n): 
    if n == 1: 
    sum = term = 1 
     return (sum, term) 
    else: 
    term = (sum*2)+1 
    sum = sum+term 
    return (sum,term) 

Dieser Code ist gebrochen und hebt eine " lokale Variable 'sum', auf die vor der Zuweisung verwiesen wird "error. Wie kann ich am besten darüber nachdenken?

Answer 1

Ich glaube, dies ist der Code Sie suchen:

def _x(n): 
    if n <= 1: 
     return (1,1) 
    else: 
     oldsum, oldterm = _x(n-1) 
     newterm = 2*oldsum + 1 
     newsum = oldsum+newterm 
     return (newsum, newterm) 

def x(n): 
    return _x(n)[1] 

Beispiel:

>>> x(1) 
(1, 1) 
>>> x(2) 
(4, 3) 
>>> x(3) 
(13, 9) 
>>> x(4) 
(40, 27) 
>>> x(5) 
(121, 81) 

Die Verwirrung vs neue Summen/terms alt gewesen sein mag.