Überprüfen ob vielfaches einer Zahl die gleichen Ziffern enthält

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Reversibuh
User
Beiträge: 8
Registriert: Freitag 5. Januar 2018, 14:31

Hallo!

Ich übe momentan auf einen Test in dem irgendein Algorithmus implementiert werden muss und gehe dazu alte Aufgaben durch.

Momentan überlege ich mir eine gute Lösung zu folgendem Problem:
Die Zahl 125874 enthält die gleichen Ziffern wie ihr 2-Faches 251748. Es soll die kleinste Zahl gefunden werden, bei der x*1 - x*6 die gleichen Ziffern beinhalten


Ich würde es so angehen, dass ich eine Schleife definiere, die bei n=1000 beginnt und solange eine Bedingung(z) nicht erfüllt ist, laufen lassen.
Bei jedem durchlauf soll n in Variable a und ihr doppeltes in Variable b gespeichert werden. Nun muss ich die einzelnen Ziffern rausbekommen.

Dafür brauch ich Liste 1 und Liste 2.
Ich füge diesen Listen immer das ergebnis von a bzw. b % 10 hinzu, solange a bzw. b >=1 ist (mehr als eine Stelle hat).

Diese sortiere ich (zB. mit Bubblesort) und vergleiche die einzelnen Stellen der Listen.
Wenn dies für alle Listen (natürlich dann eben in 6-Facher ausührung) zutrifft, Bedingung z auf True setzen und die Zahl n zurück geben.

Ich habe es mal laut meinen Vorstellungen wie unten nur für das Doppelte ausgeführt.

Code: Alles auswählen

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp
    return alist
        

def pal():
    print("klasdjf")                        
    a1 = []
    a2 = []
    pal = False
    n = 873491
    m = 2
    while pal != True:
        print(n)                            
        a = n
        b = n * m
        while a > 1 and b > 1:
            a1.append(a % 10)               
            a2.append(b % 10)
            a = int(a / 10)
            b = int(b / 10)
        a1 = bubbleSort(a1)
        a2 = bubbleSort(a2)
        if a1 == a2:
            pal = True
        else:
            a1 = []
            a2 = []
        n = n + 1
    return n
        
        
print(pal())   

Ein Weg, das ohne je ein Array für ein Vielfaches zu verwenden, wäre in einer Schleife Prüfen, ob die Bedingung a1 == a2 passt, dann b mit dem m-fachen von a überschreiben und wieder von vorne, bis es für das 6-fache passt. Bin ich da richtig?

Bin für jede Hilfe dankbar.

Edit: Bin auf einen kleinen Fehler gestoßen und hab den Code / meine Frage angepasst.
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@Reversibuh: Python kennt `sort` bzw. `sorted`, da braucht man keinen eigenen Sortieralgorithmus programmieren. Eine Funktion, die eine Zahl in ihre Ziffern umwandelt wäre gut, so dass man das für a und b nicht doppelt programmieren muß. Statt einer while-Schleife mit Flag wäre eine for-Schleife und break lesbarer. Statt Werte nach dem Gebrauch zu resetten solltest Du sie vor dem Gebrauch initialisieren. Also a1=[] und a2=[] sollte direkt vor der inneren while-Schleife stehen. Es gibt // für Ganzzahldivision. `pal != True` wäre besser `not pal`.
Reversibuh
User
Beiträge: 8
Registriert: Freitag 5. Januar 2018, 14:31

Danke!

Einiges wusste ich schon, aber wende es noch nicht intuitiv an :)

Wie mach ich das am elegantesten um zu überprüfen ob a*2 bis a*6 alle die gleichen Ziffern enthalten?

Hätte entweder, wenn a1 == a2 True ist, a2 mit a1 * 3 überschieben usw bis a1 = a1 * 6 ODER
ein eigenes array für jedes vielfache verwendet.

Mir fällt aber bei beiden Optionen nichts ein, das den Code nicht mit Bedingungen (if a1 = a2 = a3 ....) oder vielen Schleifen unnötig lang macht.

Hätte wer einen Vorschlag?
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@Reversibuh: erster Schritt wäre ja, den jetzigen Code zu verbessern. Den nächsten Schritt sieht man dann.
Reversibuh
User
Beiträge: 8
Registriert: Freitag 5. Januar 2018, 14:31

Ok, dann hab ich noch (ein paar) Fragen:
Sirius3 hat geschrieben:@Reversibuh: Python kennt `sort` bzw. `sorted`, da braucht man keinen eigenen Sortieralgorithmus programmieren. Eine Funktion, die eine Zahl in ihre Ziffern umwandelt wäre gut, so dass man das für a und b nicht doppelt programmieren muß. Statt einer while-Schleife mit Flag wäre eine for-Schleife und break lesbarer. Statt Werte nach dem Gebrauch zu resetten solltest Du sie vor dem Gebrauch initialisieren. Also a1=[] und a2=[] sollte direkt vor der inneren while-Schleife stehen. Es gibt // für Ganzzahldivision. `pal != True` wäre besser `not pal`.
Die erste ist mir, wenn sie beantwortet wurde, sicher peinlich, aber:
wie definiere ich eine endlose for-Schleife? for i in range(0, ???)

Code sieht momentan so aus:

Code: Alles auswählen

def ziffern(a):
    return (a % 10)
        

def pal():
    pal = False
    n = 100000
    m = 2
    for i in range(0, ???):
        print(n)                           
        a = n
        b = n * m
        a1 = []
        a2 = []
        while a >= 1 and b >= 1:
            a1.append(ziffern(a))               
            a2.append(ziffern(b))
            a = a // 10
            b = b // 10
        print(a1, a2)
        if sorted(a1) == sorted(a2):
            break
        n = n + 1
    return n - 1
        
        
print(pal()) 
wo liegt der unterschied, ob ich a1.append(ziffern(a)) für jede Zahl anwende, oder gleich a%10 appende? Gibt es eine Möglichkeit, dass ich in der Ziffern-Funktion 2 Parameter returne undn diese verwend?

also return(a % 10, a // 10). Somit könnte ich mir mehr sparen, aber wie kann ich das aufrufen, dass die richtigen Werte appended werden und a // 10 bzw. b // 10 in den jeweiligen variablen returned werden?
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@Reversibuh: für die Endlosschleife gibt es »itertools.count«; jetzt ist nur das »n« zu viel. »pal« ist auch noch von früher übrig geblieben. Es macht natürlich keinen Sinn, nur a%10 in eine Funktion auszulagern, eine sinnvolle Funktion wäre z.B. eine, die eine Zahl nimmt und gleich die ganze sortierte Liste zurückliefert.
Benutzeravatar
DeaD_EyE
User
Beiträge: 1011
Registriert: Sonntag 19. September 2010, 13:45
Wohnort: Hagen
Kontaktdaten:

Falls gleiche Ziffern auch doppelt vorkommen dürfen, könnte man zum Vergleich ein set nehmen.

Code: Alles auswählen

def equal(number, max):
    for i in range(2, max):
        if set(str(number * i)) == set(str(number)):
            return number, i
Falls Zahlen nicht doppelt vorkommen dürfen, könnte man den Counter nehmen:

Code: Alles auswählen

from collections import Counter


def equal(number, max):
    for i in range(2, max):
        if Counter(str(number * i)) == Counter(str(number)):
            return number, i

Falls der unendlich ohne Abbruchbedingungen nach einer Lösung suchen soll, nimmst du anstatt einer for-loop eine while-loop oder den vorgeschlagenen count von itertools.

Code: Alles auswählen

from itertools import count

for i in count(2):
    # code
Wen man einen nicht endlichen Generator programmiert, sollte man sich vorher Gedanken machen, ob es Mathematisch überhaupt so ist, dass es unendlich viele Lösungen gibt.Es ist sinnlos ein Programm bis zur Unendlichkeit rechnen zu lassen, wenn Mathematisch bewiesen ist, dass es nur endlich viele Lösungen gibt.

Mein erstes Beispiel könnte unendlich viele Lösungen finden, da dort Ziffern auch mehrfach vorkommen dürfen. Im zweiten Beispiel dürfen ausschließlich die gleichen Ziffern vorkommen, was die Anzahl der Lösungen auf keine bis endlich viele einschränkt. Ab einer gewissen Anzahl von Multiplikationen wird die Ziffernfolge länger.

Bei ersten Beispiel wäre es interessant zu wissen, ob es für jede Zahl unendlich viele Lösungen gibt. Naja, das ist Zahlentheorie. Wenn einem mal langweilig ist, kann er darüber ja nachdenken :-D
sourceserver.info - sourceserver.info/wiki/ - ausgestorbener Support für HL2-Server
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@DeaD_EyE: schön dass Du Lösungen zu Klausuraufgaben lieferst. Funktionen sollten immer einen Wert zurückliefern, nicht nur manchmal. `equal` ist auch ein ziemlich generischer Name für einen sehr speziellen Vergleich; bei solch einer Funktion würde ich als Ergebnis True/False erwarten.
Benutzeravatar
DeaD_EyE
User
Beiträge: 1011
Registriert: Sonntag 19. September 2010, 13:45
Wohnort: Hagen
Kontaktdaten:

Die Funktion liefert immer einen Wert zurück. Wenn er nichts findet, liefert er None zurück. Weitere Funktionen können das nutzen, um z.B. die Zahlen von 1 bis 10000 zu testen.

Code: Alles auswählen

def find_numbers(von, bis):
    for i in range(von, bis):
        result = equal(i)
        if result:
            yield result
Über den Namen hatte ich keine Lust nachzudenken. Das kann schließlich derjenige, der es anwendet.
Ob es sich hier um Hausaufgaben handelt oder nicht, kann ich nicht beurteile.
Falls ja, habe ich mit Absicht eine andere Lösung gesucht, die von der des OPs völlig abweicht.
sourceserver.info - sourceserver.info/wiki/ - ausgestorbener Support für HL2-Server
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@DeaD_EyE: entweder liefert eine Funktion immer explizit einen Wert zurück, oder nie. Wenn man das mischt, ist das nur verwirrend, `number` gibt man als Argument schon rein, warum kommt das als Rückgabe wieder zurück?
Benutzeravatar
DeaD_EyE
User
Beiträge: 1011
Registriert: Sonntag 19. September 2010, 13:45
Wohnort: Hagen
Kontaktdaten:

Damit man später weiß welche Nummer vorgegeben war und was der Multiplikator ist, um zum kleinsten Ergebnis zu kommen. Lässt sich auch von weiteren Funktionen verarbeiten.

Ich habe mir schon beim Schreiben der Funktion gedacht, dass es hier mindestens einen geben wird, der sich darüber beschweren wird, dass die Funktion mal eine Tupel und dann mal None zurück liefert. Ganz einfach, wenn ich bool von einer Tupel abfrage, bekomme ein True zurück, wenn die Tupel Elemente hat. Frage ich None ab, bekomme ich ein False zurück. Lässt sich wunderbar in einer IF-Abfrage verwenden.

Wenn dir das nicht passt, dann diskutiere nicht mir, antworte mit Code wie du es für richtig hältst. Letztendlich kann es anderen ja auch helfen das besser zu verstehen. Auf jeden Fall ist die Diskussion für Neulinge z.B. ziemlich verwirrend.

PS: Schau mal einfach in der Standardlib von Python nach. Dort sind auch einige Funktionen, die manchmal ein None zurück liefern (ich kann mich jetzt gerade nicht erinnern welche).
sourceserver.info - sourceserver.info/wiki/ - ausgestorbener Support für HL2-Server
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

@DeaD_EyE: es geht mir in erster Linie nicht darum es selbst zu machen (die Aufgabe hab ich schon komplett in einem Einzeiler gelöst), sondern Programmierneulingen guten Stil zu zeigen. Das ist nicht Geschmacksache, sondern hilft, Funktionen besser zu verstehen, Fehler zu vermeiden und macht einem das Leben als Programmierer insgesamt leichter. Es gibt Funktionen, die haben keinen Rückgabewert, dann wird implizit None zurückgegeben, und es gibt Funktionen, die haben einen Rückgabewert, dann muß der auch exlizit angegeben werden. Deine Funktion hat mal einen und mal keinen. Das ist verwirrend.

Deine Funktion, explizit geschrieben:

Code: Alles auswählen

def equal(number, max):
    for i in range(2, max):
        if set(str(number * i)) == set(str(number)):
            return i
    # no solution found
    return None

def find_numbers(von, bis):
    for i in range(von, bis):
        result = equal(i)
        if result is not None:
            yield i, result
schon wird klar, das None ein valider Rückgabewert ist, und es sich nicht um einen Programmierfehler handelt.
Antworten