[HaBo]

**CDW** · 07.05.09, 22:16

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 ;) ).

xblax · 07.05.09, 23:19

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

HaBo Ads

**CDW** · 07.05.09, 23:27

Zitat:

Nur ganzzahlige Lösungen nehme ich an?

Jep.

Zitat:

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

Das Leben ist hart und ungerecht

Ook! · 19.06.09, 16:13

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

lagalopex · 12.09.09, 00:36

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.)

**CDW** · 12.09.09, 01:44

Zitat:

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

raorao · 23.04.10, 15:00

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"

Empfehlung

07.05.09, 22:16	#1 (permalink)
CDW Moderator Registriert seit: 20.07.05 Likes: 156	Summe =X, Kehrwert =1 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 ;) ). __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

19.06.09, 16:13	#4 (permalink)
Ook! Registriert seit: 21.04.08 Likes: 0	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

23.04.10, 15:00	#7 (permalink)
raorao Registriert seit: 21.04.10 Likes: 0	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"

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

07.05.09, 23:19	#2 (permalink)
xblax Registriert seit: 23.03.05 Likes: 19	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

12.09.09, 00:36	#5 (permalink)
lagalopex Registriert seit: 01.11.03 Likes: 0	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.)


HaBo Ads HaBOT

[HaBo]

Summe =X, Kehrwert =1