Wie kann man das mit dynamsichen Programieren in polynomieller zeit lösen?
Ein Arithmetischer Ausdruck besteht aus 1,x,+,(,).
Das Gewicht eines arithmetischen Ausdruckes ist die Anzahl an Einsen in ihm.
Gewicht von (1+1) x (1+1+1) = 5
Der Algorithmus soll folgendes lösen :
Input natürliche Zahl n , minimales Gewicht das ein Arithmetischer Ausdruck braucht um n dazustellen.
Wie kann ein Algorithmus vorgehen?
3 Antworten
Für n≥2 hat der Ausdruck Tₙ entweder die Form Tₖ+Tₗ oder Tₖ×Tₗ, und das Gewicht dieser Terme ist minimal ⇔ das Gewicht jedes Teilterms ist minimal.
Berechne also nacheinander das minimale Gewicht G(m) für m=1, 2, 3 … n via:
G(m) = min {G(k)+G(m–k) : 1≤k≤m/2} ∪ {G(k)+G(m/k) : 1≤k≤√m ∧ k|m}
Das sind m/2+√m≤m Kandidaten für min(), und jeder davon kann in 𝓞(m) Zeit berechnet werden.
Hoppla, Denkfehler! "default=..." greift nur, wenn gt2 leer ist.
Statt:
gt = min( gt2, default=min(gt1) )
schreibe:
gt = min( chain(gt2, gt1) )
und ganz oben:
from itertools import chain
Poste doch bitte nächstes mal einfach die gesamte Aufgabe und gib ein vollständiges Beispiel an.
Ausdruck = (1+1) * (1+1+1)
Wert Ausdruck = n = 6
Gewicht Ausdruck = 5
Würde dazu einfach n in seine Primfaktoren zerlegen, so wie mit 6 in deinem Beispiel geschehen und jeden Primfaktor dann durch die Summe von i=1 bis p mit "1" definieren, wodurch dein minimales Gewicht der Summe aller Primfaktoren entspricht.
Da ich dafür aber keine dynamische Programmierung brauche hab ich dein Problem vielleicht nicht richtig verstanden. Was soll "(,)" bedeuten?
(,) sollen einfach klammern sein. deine Methode funktioniert aber nicht Bsp zahl 7.
7 ist schon eine Primzahl also wäre es ja nach der Methode ein minimales gewicht von 7 aber 7 = (1+1+1) * (1+1) +1 also ein gewicht von 6.
Da hast du natürlich Recht. Ich habe es jetzt nicht komplett durchdacht und ausprobiert, aber vielleicht reicht es ja schon das Gewicht mit dem einer weiteren Berechnung zu vergleichen. Ist n prim, dann ziehst du 1 ab, die du später zum Gewicht dazurechnest, und zerlegst dann diese Zahl in ihre Primfaktoren. Dadurch kommst du für 7 auf das Ergebnis und erhältst für alle anderen Primzahlen eine faktorisierbare Zahl, da sie mindestens durch 2 teilbar ist, da sie danach gerade ist.
schon , aber nicht die verklausulierte Form von Uhr-Aufheberrecht , die einen Mehrwert andeutete.
Und wer so das Recht haben ? Ein Buchautor ?
Die Aufgabe (aber anscheinend ohne Lösung) kann man leicht im Internet finden, wenn man nach der Aufgabenstellung sucht
Die Aufgabe (aber anscheinend ohne Lösung) kann man leicht im Internet finden, wenn man nach der Aufgabenstellung sucht
Input natürliche Zahl n , minimales Gewicht das ein Arithmetischer Ausdruck braucht um n dazustellen.
Du meinst vermutlich:
Input: natürliche Zahl n
Output: minimales Gewicht das ein Arithmetischer Ausdruck braucht um n dazustellen.
?
------------------------------------------------------------------------------------------
6 = (1+1) x (1+1+1) ................... Gewicht 5
also das minimale Gewicht von 6 ist 5
denn andere Darstellungen von 6 haben ein größeres Gewicht, wie z.B.:
6 = 1+1+1+1+1+1 ................... Gewicht 6
6 = 1x1x1x1+1x1x1x1+1x1x1+(1+1)x1+1 ................Gewicht 15
_____________________________
Dynamische Programmierung:
z.B.:
Teile das Problem in Teilprobleme, und speicher die Lösungen der Teilprobleme ab, anstatt diese Lösungen immer wieder zu berechnen - macht also Sinn, wenn das Problem aus überlappenden Teilproblemen besteht
Hier eine einfache Implementierung in Python:
Die Laufzeit ist bei mir etwa n²·1 ms (≈10 s für n=10000). Wenn man den nicht erforderlichen Code für die Beispielterme weglässt, wird's fast doppelt so schnell.