Summe =X, Kehrwert =1

CDW

0
Mitarbeiter
Also, die Summe einer Menge positiver, ganzer Zahlen soll X ergeben. Die Summe der Kehrwerte=1 (Kehrwert von Zahl Y ist 1/Y -> also z.B Kehrwert von 4 ist 1/4). Dabei ist es egal, wie viele Zahlen man nimmt oder ob sie sich wiederholen.
Bsp:
X=10:
[4,2,2]
4+4+2=10
1/4+1/4+1/2=1
X=20:
[6,6,6,2]
6+6+6+2=20
3/6+1/2=1/2+1/2=1

Schreibe ein Programm, welches die Lösung für für X berechnet.
Gib eine Lösung für X=200 an.
Optional: für X=2008 (kann etwas länger dauern ;) ).
 
Nur ganzzahlige Lösungen nehme ich an?
Dann müsste man also damit leben, dass es nicht für alle Zahlen eine Lösung gibt.

Mit Brüchen wärs glaub ich einfacher :evil:
 
Python
Code:
def suminverse(n, rs=set(), xs=[]):
    if sum(xs) == n and sum(map(lambda x: 1.0/x, xs)) == 1:
        rs.add("%i -> %s" % (n, sorted(xs)))
        return rs
    elif sum(xs) > n:
        return
    for i in range(2, n/2+1):
        if suminverse(n, rs, xs+[i]):
            return rs

for r in suminverse(9): print r
Vielleicht ist das ja ein Anreiz für einige Leute, den Code zu optimieren.
Einige Optimierungsmöglichkeiten kann man recht schnell erkennen, wenn man sich die Ergebnisse anschaut, die für kleinere Zahlen ausgegeben werden q0]

Gruß
Felix
 
Geht es darum nur eine Lösung zu finden? Oder die kürzesten? Oder alle?

Gibt es eine Lösung die nicht auf stupides brute-force setzt? (Also wo alle Lösungen für 200 in wenigen Minuten berechnet werden können.)
 
Original von lagalopex
Gibt es eine Lösung die nicht auf stupides brute-force setzt? (Also wo alle Lösungen für 200 in wenigen Minuten berechnet werden können.)

Ich habe die Aufgabe damals nur als 4 Zeilen PoC umgesetzt (BF Methode, um an ein paar gültige X Werte für die Aufgabenstellung zu kommen).

Aber afaik ja, es sollte eine bessere Lösung als BF geben (bitte auf das Datum achten, hab die Details nicht mehr so richtig im Kopf ;) ).

Sonst: ob Du nun alle oder nur die kürzesten ermittelst bleibt Dir überlassen. Die Aufgabenstellung gibt ja nur eine Schranke nach "unten" vor ;)
 
Effizient...

Möglich, dass der Code noch viel schöner geschrieben werden könnte, aber in Sachen Effizienz wohl kaum schöner möglich...
Das Ergebnis für 200 wird in einigen Millisekunden und jenes für 2008 innerhalb einer Sekunde berechnet. Die Tatsache, dass die Zahlen immer "recht" nahe um die Wurzel von X liegen und die Intervalle zwischen diesen Zahlen den grössten Teiler von X (wobei Teiler kleiner Wurzel X sein muss) betragen, lassen sich für jedes beliebige X möglichst effiziente Voreinstellungen treffen, die meist innert sehr kurzer Zeit zum Ergebnis führen. Bin gespannt auf andere Lösungsansätze... Würde mich sehr interessieren, wie man diese Aufgabe ohne Rekursion lösen könnte!?

Python Code:
Code:
import math
import time


def neueZiffer(ziel, start = 2, intervall = 1, anfangszeit = time.time(), liste = []):
    s = 0
    for zahl in liste:
        s += 1/float(zahl)

    for i in xrange(start , int(1.3 * math.sqrt(ziel)), intervall):
        if s + 1/float(i) < 0.9999999:
            neueZiffer(ziel, i, intervall, anfangszeit, liste + [i])
        elif s + 1/float(i) > 0.999999 and s + 1/float(i) < 1.0000001:
            kompl = liste + [i]
            summe = 0
            for z in kompl:
                summe += z
            if summe == ziel:
                print ziel
                print kompl
                print "Zeit seit Programmstart: %.2f Sekunden" % (time.time() - anfangszeit)

neueZiffer(200,10,5)
print
neueZiffer(2008, 32, 8)
print "Programmende"
 
Zurück
Oben