Ziffernpotenzsumme

[keta063]

Hallo,

ich brauche bitte eure Unterstützung zur folgenden Aufgaben: Alle positiven Ganzzahlen, die die Querschnittsumme (Ziffernpotenzsumme) ==5 (bsp2+2+1) haben, sollen ausgegeben werden.
Hab das mal so probiert: - Statt der Summe der Funktion quersum, sollten die Querschnittsummen nach der Reihe überprüft werden. Es müsste mit Index funktionieren, habs aber nicht zusammengebracht. Könnts ihr bitte einen Tipp geben, wie ich das machen kann.
def calculate_solution():
k = []
i = 0
sum=0
for s in range(0,100,1):
k.append(s)
i = list(map(str,k))
for f in range(len(i)-1,-1,-1):
sum = sum + int(i[f])
return i
def quersum():
sum = 0
for s in range(len(calculate_solution())-1,-1,-1):
for l in calculate_solution()[s]:
if len(calculate_solution()[s]) == 2:
sum = sum + int(calculate_solution()[s])
if sum == 50:
print("true")
return sum

Danke im Voraus.
Keita

[__blackjack__]

@keta063: Das ist alles ziemlich umständlich und verworren. Man definiert nicht auf ”Vorrat” am Anfang einer Funktion Namen die erst später benötigt werden. In `calculate_solution()` wird die 0 die dem `i` zugewiesen wird niemals irgendwo benutzt und später wird dem Namen `i` eine Liste zugewiesen. Ein Name sollte nicht im gleichen Gültigkeitsbereich an so unterschiedliche Werte gebunden werden. Diese ganzen einbuchstabigen Namen sind auch keine guten Namen. Namen sollen dem Leser die Bedeutung des Wertes dahinter vermitteln. `i` und `j` für Indexwerte ist noch vertretbar, aber wenn Listen an `i` und `k` gebunden werden, dann sind die Namen einfach nur nichtssagend.

`sum` wird auch nicht wirklich verwendet. Da wird zwar ein Wert für berechnet, aber der wird nirgends verwendet:

Code: Alles auswählen

def calculate_solution():
    k = []
    for s in range(0, 100, 1):
        k.append(s)
    i = list(map(str, k))
    return i

Bei Range sind der Startwert 0 und der Schritt 1 die Defaultwerte und statt in einer Schleife die Elemente vom `range`-Objekt einzeln an eine Liste zu hängen, könnte man einfach `list()` verwenden:

Code: Alles auswählen

def calculate_solution():
    k = list(range(100))
    i = list(map(str, k))
    return i

Aber man kann statt `k` auch gleich das `range`-Objekt verwenden und auch den Rückgabewert braucht man nicht sinnlos an einen Namen binden:

Code: Alles auswählen

def calculate_solution():
    return list(map(str, range(100)))

Bei `quersum()` muss man sich dann mal kurz an den Kopf fassen wie oft Da `calculate_solution()` aufgerufen wird was immer wieder Listen mit gleichem Inhalt erzeugt. Ich weiss das Rechner heute verdammt schnell sind, aber das ich echt ziemlich daneben! Also erst einmal diese Berechnung heraus ziehen:

Code: Alles auswählen

def quersum():
    solutions = calculate_solution()
    sum = 0
    for s in range(len(solutions) - 1, -1, -1):
        for l in solutions[s]:
            if len(solutions[s]) == 2:
                sum = sum + int(solutions[s])
                if sum == 50:
                    print("true")
    return sum

Dann ist das was Du da mit `range()` veranstaltest schlecht lesbar. Dafür gibt es die `reversed()`-Funktion.

Code: Alles auswählen

def quersum():
    solutions = calculate_solution()
    sum = 0
    for s in reversed(range(len(solutions))):
        for l in solutions[s]:
            if len(solutions[s]) == 2:
                sum = sum + int(solutions[s])
                if sum == 50:
                    print("true")
    return sum

Dann ist das iterieren über ganze Zahlen, nur um die als Index in eine Sequenz zu benutzen ein „anti-pattern“ in Python. Man kann in Python direkt über die Elemente von Sequenzen iterieren, ohne den Umweg über einen Index:

Code: Alles auswählen

def quersum():
    sum = 0
    for solution in reversed(calculate_solution()):
        for l in solution:
            if len(solution) == 2:
                sum += int(solution)
                if sum == 50:
                    print("true")
    return sum

`l` wird überhaupt nicht verwendet. Die Länge von `solution` hängt nicht von der Schleife ab, es wäre also effizienter die Schleife überhaupt erst zu betreten wenn die Länge zwei entspricht. `sum` ist der Name einer eingebauten Funktion, den sollte man nicht an etwas anderes binden. Wenn man jetzt noch die `calculate_solution()`-Funktion von oben einsetzt, bleibt das hier:

Code: Alles auswählen

def quersum():
    result = 0
    for solution in reversed(list(map(str, range(100)))):
        if len(solution) == 2:
            solution_value = int(solution)
            for _ in solution:
                result += solution_value
                if result == 50:
                    print("true")
    return result

Jetzt weiss ich aber ehrlich gesagt nicht was das mit dem im Text beschriebenen Problem zu hat und was das machen soll.

[__blackjack__]

Eine Mögliche Lösung wäre das hier:

Code: Alles auswählen

print(
"""\
5
14
23
32
41
50
104
113
122
131
140
203
212
221
230
302
311
320
401
410
500
1004
1013
1022
1031
1040
1103
1112
1121
1130
1202
1211
1220
1301
1310
1400
2003
2012
2021
2030
2102
2111
2120
2201
2210
2300
3002
3011
3020
3101
3110
3200
4001
4010
4100
5000
10004
10013
10022
10031
10040
10103
10112
10121
10130
10202
10211
10220
10301
10310
10400
11003
11012
11021
11030
11102
11111"""
)

Der Ansatz mit dem ich die Zahlen ermittelt habe ist einfach alle Zahlen aufgezählt die in Frage kommen und geprüft ob die Quersumme 5 ist. Ist der einfachste Ansatz. Der geht bei 5 ganz gut, aber skaliert nicht besonders weil immer wenn man den Zielwert um 1 erhöht, auch die Anzahl der Ziffern der grössten Möglichkeit um 1 steigt, der Suchraum also jedes mal um den Faktor 10 grösser wird.

Für grössere Zielwerte wäre es also sinnvoller zum Beispiel die Quersummen gezielt rekursiv zu generieren.

[keta063]

Hallo,

danke für die ausführliche Antwort. Ich hätte statt Listen eine Funktion verwenden sollen. Aber durch deine Erklärung versteh ich Listen ein wenig mehr.
So habs mal so probiert:

def quersum(zahl):
result=0
while zahl:
result = result + zahl%10
zahl = zahl //10
return result
def total():
zahl=0
totalzahl =0
while zahl < 11112:
zahl+=1
if quersum(zahl)==5:
totalzahl= totalzahl+zahl
return totalzahl
Macht genau das was es machen soll, ich bedanke mich für die sehr gute Erklärung.
Eins noch wie kann ich die 0 weglassen, sprich wenn 104, sollte hier die Quersumme nicht berechnet werden.
wenn ich sage if zahl %10 ==0 sollte die Funtkion abgebrochen werden, sprich so:

def quersum(zahl):
result=0
while zahl:
if zahl%10==0:
break
result = result + zahl%10
zahl = zahl //10
return result
def total():
zahl=1
totalzahl =0
while zahl < 11112:
zahl+=1
if quersum(zahl)==5:
print(zahl)
totalzahl= totalzahl+zahl
return totalzahl

Aber hier wird bsp 104 auch mitberechnet, kannst du mir grad noch einen Tipp geben
Weil ich noch Anfänger bin, hätt ich mir gdacht, dass Listen einfacher wären als Funktionen.

Danke Keita

[__blackjack__]

@keta063: Bei Python ist die Einrückung wichtig, darum sollte man Quelltext hier im Forum in Code-Tags setzten, damit man die Einrückung auch sehen kann. Im vollständigen Editor gibt es dafür die Schaltfläche die mit </> beschriftet ist, wenn man die nicht selbst tippen möchte.

Du bist mit der Leerzeichensetzung ziemlich inkonsequent. Die Konvention ist um das Gleichheitszeichen bei Zuweisungen ausserhalb von Argumentlisten und um binäre Operatoren werden Leerzeichen gesetzt.

`quersum()` ist ein komischer Name. Das sollte entweder `quersumme` oder `cross_sum` heissen, oder noch besser `berechne_quersumme()`/`calculate_cross_sum()`. Abkürzungen sollte man vermeiden, und man sollte sich für eine Sprache entscheiden für die Namen. Also kein Denglisch. `total`/`totalzahl` ist auch nicht so toll. Hier sieht man auch das Problem wenn man Funktionen nicht wie üblich nach der Tätigkeit benennt die sie ausführt — denn das `totalzahl` steht da ja nur weil die Funktion schon `total` heisst.

Die ``while``-Schleife in `total()` sollte eine ``for``-Schleife sein.

In `quersum()` wird zweimal der Rest der Division durch 10 ermittelt. Das würde ich nur einmal machen. Und die `divmod()`-Funktion ist hier praktisch.

Zwichenstand:

Code: Alles auswählen

def berechne_quersumme(zahl):
    ergebnis = 0
    while zahl:
        zahl, rest = divmod(zahl, 10)
        if rest == 0:
            break
        ergebnis += rest
    return ergebnis


def berechne_summe():
    summe = 0
    for zahl in range(2, 11112):
        if berechne_quersumme(zahl) == 5:
            summe += zahl
    return summe

Das Problem bei Zahlen wie 105 ist, dass Du beim erkennen von einer 0 als Ziffer in Zahl nicht das bisherige Ergebnis zurückgeben darfst, sondern eines zurückgeben musst das beim Aufrufer in dem Fall nicht dazu führen kann, das der Vergleich mit 5 zutrifft. `None` wäre ein geeigneter Rückgabewert für diesen Fall.

Beide Funktionen sollte man dokumentieren, beispielsweise über einen Docstring. Die Funktion zur Quersumme ginge auch ohne Dokumentation wenn sie passend benannt wäre, aber diese Sonderbedingung mit einer 0-Ziffer würde man von einer normalen Quersummenfunktion nicht erwarten.

Die zweite Funktion liesse sich mit der `sum()`-Funktion und einem Generatorausdrück übrigens deutlich kompakter formulieren:

Code: Alles auswählen

def berechne_summe():
    return sum(
        zahl for zahl in range(2, 11112) if berechne_quersumme(zahl) == 5
    )

Was mir persönlich daran noch nicht so gut gefällt sind die festen Zahlen bei `range()`, denn zumindest die zweite hängt von der 5 ab. Das könnte man dokumentieren was man sich bei 11112 gedacht hat, oder noch besser man schreibt diese Zahl nicht fest in den Code sondern berechnet sie aus der 5. Dann könnte man die 5 auch zu einem Argument der Funktion machen und die Summe damit auch für andere Ausgangszahlen als 5 berechnen lassen.

Die Zahlen aus meinem letzten Beitrag sind übrigens mit folgendem Hy-Programm entstanden:

Code: Alles auswählen

#!/usr/bin/env hy3

(defn cross-sum [n]
  (->> (str n) (map integer) (sum)))

(defmain [&rest args]
  (setv target 5
        search-space (range target (-> (* "1" target) (integer) (inc)))
        cross-sum-equals-target? (fn [n] (= (cross-sum n) target)))
  (for [n (filter cross-sum-equals-target? search-space)]
    (print n)))

Hy ist ein Lisp-Dialekt der in Python geschrieben ist, nach Python-Bytecode übersetzt wird und damit die Python-Laufzeitumgebung nutzt, also Funktionen und Module die für Python installiert sind, lassen sich von Hy aus benutzen. Bei der Quersummenfunktion bin ich über die Zeichenkettendarstellung gegangen um die Ziffern zu bekommen. Ebenso bei der Berechnung der Obergrenze des Zahlenbereichs der durchsucht werden soll.

Das man Zahlen mit 0-Ziffern besonders berücksichtigen muss fiel mir gestern auch schon auf, weil es sonst ja unendlich viele Zahlen mit der Quersumme 5 gibt.

Die Gegenüberstellung Listen vs. Funktionen verstehe ich nicht so ganz. Das ist doch kein entweder oder, und Du hast zwar was mit Listen gemacht, aber dafür ja auch Funktionen verwendet.

[Sirius3]

Ein anderer Lösungsweg:
Wenn die Ziffer 0 ausgeschlossen ist, ist die Menge der Ziffern, die zusammen 5 ergeben ja sehr begrenzt. Man könnte also zuerst alle Ziffernmengen bestimmen und dann jeweils alle Kombinationen aus diesen Ziffern bilden. Dann muß man nicht alle Zahlen durchprobieren, sondern bekommt direkt nur solche, die der Quersumme entsprechen: [5], [4,1], [3,2], [3,1,1], [2,2,1],[2,1,1,1] und [1,1,1,1,1]
Diese Listen lassen sich am einfachsten Rekursiv bestimmen.

[/me]

Die Quersumme lässt sich auch anders ermitteln.

Code: Alles auswählen

def berechne_quersumme(zahl):
    return sum(map(int, str(zahl)))

Für die Ermittlung der Summe wird die Zahl zunächst in einen String konvertiert. Dann wird anschließend der in einen Integer konvertierte Wert jedes einzelnen Zeichens addiert. Das ist ein sehr simpler und (zumindest für mich) offensichtlicher Ansatz. Wie sich das von der Performance her verhält müsste man testen.

[__deets__]

Das es geht steht ausser Frage. Trotzdem rollen sich mir die Fussnaegel, so den Typ zu wandeln. Ich wuerde Rekursion bevorzugen:

Code: Alles auswählen

def quersumme(n):
    return 0 if n == 0 else quersumme(n // 10) + (n % 10)

[__blackjack__]

@/me: Das mit den Zeichenketten habe ich ja in dem Hy-Programm gemacht.

Statt nur die Mengen rekursiv zu bestimmen, würde ich gleich alle passenden Quersummen rekursiv bestimmen.

@__deets__: Rekursion in Python, ohne tatsächlichen Grund finde ich ja fast schlimmer als über die Zeichenkettendarstellung zu gehen. Und es ist halt schwerer die zusätzliche Bedingung mit der 0 da rein zu bringen.

@__all__: Hier noch mal der Ansatz alle Zahlen aufzuzählen und die passenden raus zu filtern in C:

Code: Alles auswählen

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

#define TARGET  5


int main(void)
{
    uint16_t i, j;
    uint16_t upper_limit;
    uint16_t total;
    uint8_t cross_sum;
    div_t qr;
    
    for (i = upper_limit = 0; i < TARGET; ++i) {
        upper_limit = upper_limit * 10 + 1;
    }
    
    for (i = total = 0; i <= upper_limit; ++i) {
        cross_sum = 0;
        j = i;
        while (j != 0 && cross_sum <= TARGET) { /* EDIT */
            qr = div(j, 10);
            if (qr.rem == 0) {
                cross_sum = 0;
                break;
            }
            cross_sum += qr.rem;
            j = qr.quot;
        }
        
        if (cross_sum == TARGET) {
            printf("%"PRIu16"\n", i);
            total += i;
        }
    }
    
    printf("total: %"PRIu16"\n", total);
    
    return 0;
}

Da mit der 5 als Ziel kein Wert der benötigt wird die 16-Bit-Grenze sprengt, habe ich das mal auf dem C64 laufen lassen. Da dauert es eine halbe Minute bis zum Ergebnis und gibt folgende Summanden aus:
5
14
23
32
41
113
122
131
212
221
311
1112
1121
1211
2111
11111

Die zeitliche Lücke zwischen den letzten beiden Summanden fällt besonders deutlich auf. Da stellt sich dann die Frage ob nicht hier schon ein rekursives generieren der passenden Quersummen schneller sein könnte, oder ob der Zeitgewinn durch die rekursiven Aufrufe wieder aufgefressen würde.

Edit: Du eine kleine zusätzliche Bedingung beim berechnen der Quersumme, nämlich dem Abbruch wenn die grösser als der Zielwert ist, liess sich die Laufzeit auf dem C64 um die Hälfte auf 15 Sekunden drücken.

[ThomasL]

Alle positiven Ganzzahlen, die die Querschnittsumme (Ziffernpotenzsumme) ==5 (bsp2+2+1) haben, sollen ausgegeben werden.

Also Google findet weder etwas erklärendes zu Querschnittsumme noch Ziffernpotenzsumme.
Ich unterstelle mal, dass die Quersumme https://de.wikipedia.org/wiki/Quersumme gemeint ist. Zumindest sieht das Beispiel so aus.
Ich hoffe dem Aufgabensteller ist klar, dass die Menge aller positiven Ganzzahlen die eine bestimmte Quersumme haben, unendlich groß ist.
Wie wollt ihr die also alle ausgeben?

[__blackjack__]

@ThomasL: Deswegen gibt es ja wohl die Einschränkung das in den Zahlen die Ziffer 0 nicht vorkommen darf.

[ThomasL]

Habe ich diese Einschränkung in diesem Thread überlesen oder war das jetzt deine intuitive Annahme, dass der OP diese Einschränkung nur nicht erwähnt hat?

[__blackjack__]

@ThomasL: Die Einschränkung hat keta063 ins Spiel gebracht, also ging ich davon aus die ist Teil der Aufgabe. Sonst wäre die Aufgabe bei unendlich vielen Zahlen auf die die Bedingung mit der Quersumme zutrifft, ja auch nicht lösbar. Man könnte natürlich auch andere Einschränkungen festlegen. Nur die ersten n Zahlen untersuchen, oder nur die ersten n Zahlen bei der die Quersumme gleich 5 ist, oder solange bis die Summe der Zahlen einen bestimmten Wert erreicht/überschritten hat, oder …

[ThomasL]

Eins noch wie kann ich die 0 weglassen, sprich wenn 104, sollte hier die Quersumme nicht berechnet werden.

Manchmal sieht man den Wald vor lauter Bäumen nicht.

[keta063]

Hallo noch einmal,

nochmals danke für die Antworten, hat mir sehr geholfen, auch andere Lösungsansätze wie dieser hier: def berechne_quersumme(zahl):return sum(map(int, str(zahl))) ist genial .

Ich habs nun folgendermaßen gelöst, vor allem auch die divmod - Funktion find ich hier sehr hilfreich.

Code: Alles auswählen

def quersum(zahl):
    result=0
    while zahl:
        zahl, res = divmod(zahl,10)
        if res == 0:
            return None
            break
        result = result + res
    return result
def calculate_solution():
    zahl=1
    result=0
    while zahl < 11112:
        zahl+=1
        if quersum(zahl)==5:
            print(zahl)
            result= result+zahl
    return result

Ich hab gesehen, dass ich für Verwirrung gesorgt haben , weil die Quersumme eigentlich ohne die 0 gerechnet werden soll (ist auch Teil des Problems). Weil ich Schritt für Schritt das Problem lösen wollte, habe ich zuerst die Quersumme berechnen wollen und erst später das mit der 0. Ich schau aber darauf, dass ich in Zukunft konkretere Aufgabenstellungen stelle.

Danke noch einmal und bis zur nächsten Aufgabe

Keita

[Sirius3]

Du kennst `zahl += 1` schreibst aber `result =result + res`?
Das break nach `return None` macht keinen Sinn. Die while-Schleife in calculate_solution sollte eine for-Schleife sein. 11112 sollte nicht hart codiert im Code stehen sondern berechnet werden. Dann ist die Funktion auch trivial auf beliebige Quersummen verallgemeinerbar.

[Jankie]

Hab auch noch zwei Möglichkeiten(Auch wenn sich da bestimmt wieder Fußnägel rollen):

Code: Alles auswählen

def ist_quersumme_gleich(soll_quersumme, zahl):
    if sum([int(x) for x in str(zahl)]) == soll_quersumme:
        return True


print([x for x in range(0,10000) if ist_quersumme_gleich(5, x)])

Code: Alles auswählen

def berechne_quersumme(zahl):
    return sum([int(x) for x in str(zahl)])


print([x for x in range(0, 10000) if berechne_quersumme(x) == 5])

[__blackjack__]

@Jankie: Bei der ersten Variante rollen in der Tat Fussnägel. Die `ist_quersumme_gleich()`-Funktion gibt zwei mögliche Werte zurück: `True` oder `None`. Das ist falsch und sollte `True` oder `False` sein. Und dafür braucht man dann kein ``if``, denn der Vergleich in der ``if``-Bedingung hat ja bereits das gewünschte Ergebnis. Statt einer „list comprehension“ wäre hier auch ein Generatorausdruck sinnvoller:

Code: Alles auswählen

def ist_quersumme_gleich(soll_quersumme, zahl):
    return sum(int(x) for x in str(zahl)) == soll_quersumme

Und den Generatorausdruck kann man auch durch `map()` ersetzen, wie das Vorgänger bereits gezeigt haben: ``sum(map(int, str(zahl)))``.

[Sirius3]

Hier noch die direkte Erzeugung der Zahlen:

Code: Alles auswählen

def generate_cross_sum_numbers(cross_sum, digits=()):
    missing = cross_sum - sum(digits)
    if missing < 10:
        result = digits + (missing,)
        yield sum(d*10**p for p,d in enumerate(result))
    for d in range(1, min(10, missing)):
        yield from generate_cross_sum_numbers(cross_sum, digits + (d,))

print(generate_cross_sum_numbers(5))

[nezzcarth]

@__all__: Hier noch mal der Ansatz alle Zahlen aufzuzählen und die passenden raus zu filtern in C:

Ließt sich als bc-Script ein bisschen ähnlich :

Code: Alles auswählen

#!/usr/bin/env -S bc -q 
scale = 0
define digitsum(x) {
    sum = 0
    while (x > 0) {
        remainder = x % 10
        if (remainder == 0) {
            return -1
        }
        sum += remainder
        x /= 10  
    }
    return sum
}

n = read()
limit = ((10^n)-1) / 9
total = 0
for (i = 0; i <= limit; i++) {
    if (digitsum(i) == n) {
        print i, "\n"
        total += last
    }
}
print "Total: ", total, "\n"

quit