Summe echter Teiler

  • VB.NET

Es gibt 13 Antworten in diesem Thema. Der letzte Beitrag () ist von Mangafreak1995.

    Summe echter Teiler

    Hi

    folgendes Problem (wahrscheinlich eher mathematisch)

    Nehmen wir 30
    echte Teiler sind 1 2 3 5 6 10 15

    Ich möchte jetzt testen ob es möglich ist aus den Teilern (müssen nicht alle verwendet werden) durch summieren die Ausgangszahl wieder zu bilden.
    in dem Fall funktioniert es ( z.B 5+10+15 = 30) kann aber auch natürlich bei anderen Zahlen nicht Möglich sein.

    Muss ich jetzt wirklich so schreiben, dass jede mögliche Kombination durchgerechnet wird?
    Oder gibts dahinter irgend eine Regel? Ne Funktion die mir das vereinfacht?

    Danke im Vorraus

    Pulsar
    Echte Teiler kannst du mit Modulo bestimmen. Die Regel ist, dass nur Zahlen kleiner oder gleich der Differenz Ziel zu jetztigen Wert nutzbar sind. Ansonsten musst du jede Kombi machen.

    Pulsar schrieb:

    Muss ich jetzt wirklich so schreiben, dass jede mögliche Kombination durchgerechnet wird?

    Nein, aber eine mathematische Formel sehe ich hierfür auch nicht. Woher hast Du die Aufgabe ?

    Vermutlich gilt hier auch noch die Regel, dass jeder Teiler höchstens 1x in der Summe vorkommen darf - oder ?

    Ansatz wäre auf jeden Fall rekursiv:
    - für Zahl N die Menge aller echten Teiler T bilden
    - wähle ersten Teiler t1 -> neue menge T1 = T \ t1
    - Rekursion: suche Summe für die Zahl N-t1 aus der Menge T1
    Echte Teiler kannst du mit Modulo bestimmen.
    Das ist kein Problem ^^
    Spoiler anzeigen

    Quellcode

    1. Public Function alleTeiler(ByVal z As Integer) As List(Of Integer)
    2. Dim liste As New List(Of Integer)
    3. For i As Integer = 1 To z - 1
    4. If z Mod i = 0 Then
    5. liste.Add(i)
    6. End If
    7. Next
    8. Return liste
    9. End Function


    Die Regel ist, dass nur Zahlen kleiner oder gleich der Differenz Ziel zu jetztigen Wert nutzbar sind. Ansonsten musst du jede Kombi machen.
    Joa das hab ich mir schon gedacht :(


    Nein, aber eine mathematische Formel sehe ich hierfür auch nicht. Woher hast Du die Aufgabe ?
    Von ner Seite auf ders paar Übungsaufgaben zum programmieren gibt, mags grad nich posten weils nich so gern gesehen wird wenn man nachfragt, wobei meine Frage hier nur ein kleiner Teil ist, der zur kompletten Lösung erforderlich ist. ^^
    Also ist es schon möglich dass es keine Formel gibt.

    Mhm ja jeder Teiler kommt nur einmal vor.

    - wähle ersten Teiler t1 -> neue menge T1 = T \ t1
    - Rekursion: suche Summe für die Zahl N-t1 und der Menge T1
    Den Teil hab ich leider nicht ganz verstanden. ?(
    Also t1 ist ein Teiler aus der Menge in meinem oben genannten Beispiel also z.B 3?
    T die Menge der Ausgangsteiler? Oder ...?
    Sry kapiers nicht. ^^

    Aber danke schonmal für eure Antworten! :)
    Wenn du nicht jede mögliche Kombination brauchst und gilt, dass du jede Zahl nur einmal verwenden darfst kannst du wie folgt vorgehen:

    Sortiere die Teiler nach Größe (größter zuerst).
    TS ist jetzt die Summer der Teiler (am Anfang 0), die schon akzeptiert wurden und T der jetztige Teiler.
    Du gehst diese Liste von Teilern durch( und weißt sie T zu).
    Wenn die Differenz von TS und der zu untersuchenden Zahl größer ist als T, dann rechnest du T auf TS drauf.

    Log dir am besten mal jeden Schritt mit den Werten und dann verstehst du die Vorgehensweise auch ein bisschen besser (falls du es jetzt noch nicht hast).
    In die Richtung hab ich auch erst gedacht aber dann vermutet dass es passieren kann, dass eine von den "höheren " Zahlen verhindert dass das richtige Ergebnis noch mit den kleineren Zustande kommen kann.

    Bisschen doof geschrieben.

    Naja aber ich hab verstanden was du meinst und werds jetzt erstmal versuchen.

    Danke. Ich meld mich wieder wenns geklappt hat. ;)
    Wenn die Zahl durch eine Zahl nicht teilbar ist, brauchst du die vielfachen dieser Zahl gleich gar nicht zu prüfen...
    Heißt durch 2 nicht teilbar->4,6,8,10,12,... sind ebenfalls ausgeschlossen...
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---
    @Mangafreak1995

    VB.NET-Quellcode

    1. For j = 0 To lstTeiler.Count - 1
    2. If pruefSum + lstTeiler(j) <= number Then
    3. pruefSum += lstTeiler(j)
    4. End If
    5. Next


    lstTeiler ist die Teiler Liste beginnend mit dem Größten.
    pruefSum ist zum Anfang 0
    number ist die ausgangszahl

    Am Ende bleibt pruefSum übrig, ob die = number ist prüf ich später erst.

    Dummerweise stimmt das endgültige Ergebnis immernoch nicht.

    Da alles andere richtig scheint muss der Fehler immernoch hier liegen.
    Ich müsste wissen ob die jetzige Variante auch bei hohen Zahlen fehlerfrei arbeitet, ich glaub das kommt noch nich hin :(
    Manuell prüfen geht auch schlecht da wie gesagt recht hohe Zahlen auftreten.

    MfG

    Pulsar schrieb:

    Dummerweise stimmt das endgültige Ergebnis immernoch nicht.

    Wird allgemein so auch nie stimmen , da Deine und Mangafreaks Vorgehensweise nicht korrekt ist. Das ist nun mal eine typische Aufgabe für Rekursion, die durch Schleifen so kaum zu lösen ist.

    Deshalb hatte ich Dich gefragt , wo Du die Aufgabe her hattest. Damit implizit ob Du mit dem Begriff der Rekursion auch nur das geringste anfangen kannst ...

    Ob Du nun mit dem grössten / kleinsten / irgendeinem zufälligen Teiler beginnst, ist prinzipiell nicht wichtig. Höchstens für eine optimierte Abbruchsbedingung ...

    @jvbsl zwar richtig, aber hier wohl (noch) das kleinste Problem ;)
    Wird allgemein so auch nie stimmen , da Deine und Mangafreaks Vorgehensweise nicht korrekt ist. Das ist nun mal eine typische Aufgabe für Rekursion, die durch Schleifen so kaum zu lösen ist.


    Tjoa hab ich mir vorher schon gedacht ^^

    Mit Rekursion kann ich nix anfangen.
    Hab zwar eben bissel gegoogelt/ nachgelesen, aber naja mit dem was ich gefunden hab, können wohl eher Mathematik bzw Informatik Studenten was anfangen xD

    Edit: naja gut das Grundprinzip von Rekusion hab ich verstanden, aber ichs in dem Fall hier umsetzen kann ... ma schauen :D

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Pulsar“ ()

    Lies mal den Abschnitt über pseudovollkommene Zahlen: de.wikipedia.org/wiki/Vollkommene_Zahl
    Wenn du dich damit begnügst, nur eine Teilmenge der pseudovollkommenen Zahlen zu finden, kannst du die Primfaktoren für ein gegebenes n auf Quadratfreiheit testen. Ist das der Fall, hast du eine primär pseudovollkommene Zahl gefunden. Da es bisher keine effiziente Methode für die Primfaktorzerlegung gibt, bleibt dir nichts anderes übrig, als diese für jedes zu testende n erneut zu berechnen.
    Gruß
    hal2000
    @Kangaroo
    wo ist das Problem wenn ich 30 habe => 15, 10, 6, 5, 2, 1 als Teiler
    Ist 0 + 15 kleiner-gleich 30 (ja)
    Wert ist nun 15
    Ist 15 + 10 kleiner-gleich 30 (ja)
    Wert ist nun 25
    Ist 25+6 kleiner-gleich 30 (nope)
    Wert bleibt 25
    Ist 25+5 kleiner-gleich 30 (ja)
    Wert ist nun 30 (ab hier kann abgebrochen werden)

    Und mit meinen gegebenen Bedingungen ist das vollkommen legitim.