AUFGABE: Jeden tag eine Änderung des Bankcodes...

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.
sebastian0202
User
Beiträge: 168
Registriert: Montag 9. Mai 2016, 09:14
Wohnort: Berlin

Dann weiß ich immer noch nicht wann es sich lohnt ein Objekt zu erstellen.
Vielleicht lese ich die falschen Bücher.

Bei Klassennamen sollte der Anfangsbuchstabe jedes Wortes Groß und aneinander gereiht sein, richtig?
Bei Methoden und Funktionen sollten die Wörter dann kleingeschrieben und mit Unterstrich verbunden sein, richtig?
https://www.python.org/dev/peps/pep-000 ... tion-names :lol:

Bei der Formatierung hätte ich ja "%4d" verwenden können, aber was ist, wenn ich anstelle von 4 auf 6 Zahlen auffüllen möchte?
Abhängig von der Anzahl der Stellen des Codes eben. Es wird ja kein %ANZAHL_STELLENd geben.
Deshalb ('0'*anzahl_stellen+str(zahl))[anzahl_stellen*-1:], aber das liest sich ja katastrophal.

Sorted() konnte ich nicht nehmen, da er die Zahlen als Strings sortiert. Und so kommt 57 vor 571 etc.
Habe die Zahlen vor zum string konvertiert um sie als dict Key zu nutzen :oops:

Es sieht schon wirr aus was ich da geschrieben habe :lol:
Da bekomme ich glatt Angst, wenn ich darüber nachdenke wie ich auf Arbeit programmiere.
Dabei habe ich mehrfach über den Code geschaut.

Ich habe mir any und all angeschaut. Keine Ahnung wie ich die Funktionen nutzen soll,
um über mehrere Listen zu iterieren um darin ein Element an beliebiger Stelle zu suchen. Zumal ich dann ja den Index der Gruppe brauche.

@Sirius3
Wie meinst du das mit den Sets?
Wie kann ich denn 99% Rechenzeit sparen?



Ich habe mich eben an einem zweiten Versuch gewagt :?

Code: Alles auswählen


class Code(object):
    def __init__(self, laenge, zahl = -1):
        self._generation = 0
        self.laenge = laenge
        if zahl >= 0: 
            self.ziffern = list(map(int, str(zahl)))
        else:
            self.ziffern = [random.randint(0,9) for x in laenge]
        self.codes = [self.get_code()]

    def next_code(self, generations = 1):
        while generations > 0:
            zahl = sum(self.ziffern) % 10        
            self.ziffern.append(zahl)
            self.ziffern = self.ziffern[self.laenge*-1:]
            self._generation += 1
            self.codes.append(self.get_code())
            generations -= 1
        return self.get_code()

    def get_code(self):
        return int(''.join(map(str, self.ziffern)))
    
    def get_codes(self):
        return self.codes

    def get_generation(self):
        return self._generation

    def show_generations(self, von=0, bis=None):
        text = ''
        if not bis: bis = self._generation
        for generation in range(von, bis + 1):
            text += "Gen: %s - %i\n" % (generation, self.codes[generation])
        return text
    
    def __str__(self):
        return "Code: %4d - Generation: %i" % (self.get_code(), self._generation)

class CodeGruppe(object):
    def __init__(self):
        self.gruppen = []
        self._codes = []

    def add_group(self, codes):
        if not self.number_exists(codes[0]):
            self.gruppen.append(codes)
            self._codes.extend(codes)
    
    def number_exists(self, code):
        if code in self._codes:
            return True
        return False
    
    def get_group(self, number):
        return self.gruppen[number]

    def get_group_number(self, code):
        if not code in self._codes:
            return False
        for nr in self.get_group_numbers():
            if code in self.gruppen[nr]:
                return nr
    
    def get_group_numbers(self):
        return [nr for nr, liste in enumerate(self.gruppen)]

    def get_group_info(self, *arg):
        text = ''
        if not arg:
            arg = self.get_group_numbers()
        for nr in arg:
            text += "Gruppe: %i laenge: %i\n" % (nr, len(self.gruppen[nr]))

        return text

def main():
    codegruppe = CodeGruppe()

    for i in range(0, 1000):
        if not codegruppe.number_exists(i):
            code = Code(4, i)
            anfang = code.get_code()

            while code.get_generation() < 4800:
                if anfang == code.next_code():
                    break
            codegruppe.add_group(code.get_codes())
    
    
    print(codegruppe.get_group_info())
    number = codegruppe.get_group_number(1986)
    print(codegruppe.get_group_info(number))
    print(codegruppe.get_group(number))

if __name__ == '__main__':
    main()
BlackJack

@sebastian0202: Es gibt kein '%0ANZAHL_STELLENd' aber '%0*d'. Und bei `format()` kann man Platzhalter auch verschachteln. Notfalls gäbe es auf Zeichenketten auch noch die `zfill()`-Methode.

Code: Alles auswählen

In [13]: '%0*d' % (4, 42)
Out[13]: '0042'

In [14]: '{0:0{1}d}'.format(42, 4)
Out[14]: '0042'

In [15]: str(42).zfill(4)
Out[15]: '0042'
`sorted()` kannst Du natürlich trotzdem nehmen wenn Du es auf die umgewandelten Daten anwendest, also einfach statt der „list comprehension“ die `sorted()`-Funktion mit einem Generatorausdruck als Argument:
sorted_numbers = sorted(int(s) for s in strings)

Bezüglich `any()`/`all()`: Aus diesem hier:

Code: Alles auswählen

    def add_group(self, zahl, liste):
        gefunden = False
        for group in self.groups:
            if zahl in group:
                gefunden = True
                break
 
        if not gefunden:
            self.groups.append(liste)
wird das hier (ungetestet):

Code: Alles auswählen

    def add_group(self, zahl, liste):
        if all(zahl not in group for group in self.groups):
            self.groups.append(liste)
`Code` macht IMHO schon wieder zu viel. Das `codes`-Attribut hat da nichts zu suchen. `_generation` eigentlich auch nicht, denn ich würde erwarten das `Code` ein Wertobjekt ist und der Wert nur aus dem Zahlwert und der Länge eines Codes besteht. Du packst da gleich noch alle Codes die aus dem Code folgen mit hinein, wobei das aber abhängig davon ist ob und wie viele man davon hat generieren lassen.

`next_code()` würde ich `advance_code()` nennen, weil man nicht nur den nächsten Code bekommen kann, sondern auch beliebig weite Sprünge machen kann. Das und auch das mit dem Zufallswert in der `__init__()` scheint mir hier überflüssig zu sein‽

Wenn `Code` kein Werttyp ist, dann würde ich da einen Iterator draus machen statt eine `next_code()`-Methode zur Verfügung zu stellen. `CodeIterator` wäre dann auch ein passenderer Name IMHO. Denn es ist ja kein Code sondern enthält einen (aktuellen) Code (und eventuell alle seine Vorgänger).

``while generations > 0:`` sollte eine ``for``-Schleife sein.

`get_codes()` und `get_generation()` sind trivialer Getter → weg damit. Aus `get_code()` könnte man ein `property()` machen.

`show_generations()` wäre in Haskell vielleicht der passende Namen, aber in Python eher nicht. Da würde man bei `show_irgendwas()` erwarten das etwas ausgegeben oder angezeigt wird. Die Methode ist vom Inhalt her auch mehr was für die Benutzerinteraktion und nicht für die Programmlogik.

”Magische” Methoden wie `__str__()` erwartet man eigentlich am Anfang der Klasse vor Properties und normalen Methoden und nicht versteckt als letzte Methode.

``self.ziffern[self.laenge*-1:]`` würde ich als ``self.ziffern[-self.laenge:]`` schreiben. Eine `collections.deque` statt einer Liste würde die Sache vereinfachen und eventuell auch effizienter machen.

`CodeGruppe` enthält mehr als eine Gruppe, sollte also `CodeGruppen` heissen. Das `_group` kann aus allen Methodennamen verschwinden, denn es doppelt nur noch mal die Typinformation.

Wenn ``if``/``else`` in den zweigen nur `True` oder `False` zurück gibt, dann ist das Konstrukt unnötig, denn die Bedingung vom ``if`` ist ja schon der Wert den man haben möchte, oder seine Negation, die man mit ``not`` bekommt. Also wird `number_exists()` zu einem Einzeiler: ``return code in self._codes``.

Eine Funktion sollte immer nur einen (Duck)Typ als Ergebnis liefern, also beispielsweise nicht mal `False` und mal eine Zahl. Das lässt sich in diesem Fall auch nur über einen Typtest prüfen, denn `False` ist eine Zahl und hat den gleichen Wert wie 0 beim Vergleichen und allen anderen Operationen die auf `int` definiert sind:

Code: Alles auswählen

In [21]: isinstance(False, int)
Out[21]: True

In [22]: False == 0
Out[22]: True

In [23]: False + 42
Out[23]: 42

In [24]: False * 42
Out[24]: 0
Statt spezielle Fehlercodes zurück zu geben, verwendet man in Python Ausnahmen. `get_group_number()` sollte eine Auslösen wenn der `code` nicht enthalten ist. `KeyError` würde sich anbieten.

`get_group_numbers()` nutzt `enumerate()` wo ein `range()` ausreichen würde. In Python 3 mit einem `list()` um da tatsächlich eine Liste draus zu machen. Sofern das benötigt wird tatsächlich eine Liste vorliegen zu haben.

Die API von `get_group_info()` ist mir zu magisch. Warum nicht einfach eine Liste mit Nummern statt ein *-Parameter? Was ist der Anwendungsfall für einen Aufruf mit mehr als einer Nummer bei der beim Aufruf *kein* Sternchen gebraucht wird? Der zudem einen besseren Namen als `*arg` haben könnte. Der Leser will nicht wissen das da irgendwelche Argumente übergeben werden können, sondern was sie bedeuten.

Eventuell würde es die API von `CodeGruppen` schöner machen, wenn man da die ”magischen” Methoden für einen Containertyp implementiert. Wohl eine Abbildung in diesem Fall.

Im Hauptprogramm sind 1000, 4, und 4800 Zahlen die zusammenhängen. Wobei 4800 IMHO einer Erklärung bedarf. Warum ist diese Zahl sicher? Wie berechnet die sich aus der Stellenanzahl? Ist der Code robust gegen den Fall das eine Kombination niemals wieder erreicht würde? Was wäre da das Gegenargument?

Zur Frage wann es sich lohnt ein Objekt zu erstellen: Implementiere das doch mal nur mit Funktionen. Dann sieht man in der Regel leichter welche Daten und welche Funktionen man zusammenfassen kann/sollte. Wie gesagt Funktionen sind nicht böse und Klassen sind kein Selbstzweck. Wenn man sie nicht benötigt, sollte man sie auch nicht schreiben und man sollte auch nicht versuchen krampfhaft jede ``def``\inition in eine Klasse stecken zu wollen.

Edit: Man braucht die Fähigkeit Code sinnvoll auf Funktionen aufzuteilen auch bei OOP, denn dort muss man ihn sinnvoll auf Klassen und Methoden aufteilen. Wenn man also schon bei der Aufteilung auf Funktionen Probleme hat, dann wird das bei OOP nur noch schwieriger. Ich erwähne das weil Dein Versuch weiter oben im Thema die ursprüngliche Aufgabe auf Funktionen zu verteilen auch schon nicht gut war. Auch ein Grund erst einmal Funktionen zu üben.
BlackJack

@sebastian0202: Mal ein Beispiel wie man zu Objekten kommen kann. Ausgangspunkt ist eine funktionale Lösung mit Codes die nicht auf 4 Stellen festgelegt sind, denn sonst gibt es hier fast nichts was man zu einem Objekt zusammenfassen kann:

Code: Alles auswählen

#!/usr/bin/env python
from __future__ import absolute_import, division, print_function


def get_cross_sum(number):
    result = 0
    while number:
        number, digit = divmod(number, 10)
        result += digit
    return result


def code_as_string(code_length, code_value):
    return str(code_value).zfill(code_length)


def shifted_code(code_length, code_value, digit):
    return code_value * 10 % 10**code_length + digit


def get_next_code(code_length, code_value):
    return shifted_code(code_length, code_value, get_cross_sum(code_value) % 10)


def calculate_days(code_length, start_code_value):
    days = 0
    code_value = start_code_value
    while True:
        days += 1
        code_value = get_next_code(code_length, code_value)
        if code_value == start_code_value:
            return days


def main():
    code_length = 4
    for code_value in range(10**code_length):
        print(
            code_as_string(code_length, code_value),
            calculate_days(code_length, code_value)
        )


if __name__ == '__main__':
    main()
Wie man sieht besteht ein Code aus zwei Komponenten, der Länge und dem Zahlwert, die durch viele Funktionen durchgereicht werden müssen. Das wären im ersten Schritt die Kandidaten die man zu einem Objekt zusammenfassen könnte. Machen wir das mal mit `collections.namedtuple()` (die geänderten Funktionen):

Code: Alles auswählen

Code = namedtuple('Code', 'length value')


def code_as_string(code):
    return str(code.value).zfill(code.length)


def shifted_code(code, digit):
    return Code(code.length, code.value * 10 % 10**code.length + digit)


def get_next_code(code):
    return shifted_code(code, get_cross_sum(code.value) % 10)


def calculate_days(start_code):
    days = 0
    code = start_code
    while True:
        days += 1
        code = get_next_code(code)
        if code == start_code:
            return days


def iter_codes(length):
    return (Code(length, i) for i in range(10**length))


def main():
    length = 4
    for code in iter_codes(length):
        print(code_as_string(code), calculate_days(code))
Jetzt kann man sich überlegen, welche von den Funktionen zu dem Objekt gehören könnten um das `namedtuple()` zu beerben und um Methoden zu erweitern. `code_as_string()` ist sinnvoll als `__str__()` auf der Klasse. Des weiteren würde ich in diesem Beispiel alle Funktionen dort hin verschieben die ein `Code`-Objekt als Argument bekommen *und* die interne Repräsentation kennen (müssen). Dazu gehört `calculate_days()` *nicht*, denn diese Funktion weiss nicht, das ein `Code` aus Länge und Wert besteht. Die `iter_codes()`-Funktion bekommt zwar keinen Code übergeben, erzeugt aber welche, und wäre damit ein Kandidat für eine Klassenmethode:

Code: Alles auswählen

class Code(namedtuple('Code', 'length value')):

    def __str__(self):
        return str(self.value).zfill(self.length)

    def shifted(self, digit):
        return Code(self.length, self.value * 10 % 10**self.length + digit)

    def get_next(self):
        return self.shifted(get_cross_sum(self.value) % 10)

    @classmethod
    def iter_all(cls, length):
        return (cls(length, i) for i in range(10**length))


def calculate_days(start_code):
    days = 0
    code = start_code
    while True:
        days += 1
        code = code.get_next()
        if code == start_code:
            return days


def main():
    length = 4
    for code in Code.iter_all(length):
        print(code, calculate_days(code))
karolus
User
Beiträge: 140
Registriert: Samstag 22. August 2009, 22:34

Hallo

Ich hab mal einen Code als tuple von vier Zahlen (0 … 9) aufgefasst, und das ganze nach Größe und Anzahl von geschlossenen Codefolgen aufgedröselt.

Code: Alles auswählen

from itertools import product
from collections import Counter

alle = set(product(range(10),repeat=4))
seen = set()

def next_code(code):
    return code[1:] + (sum(code) % 10,)

def main():
    ringcounter = Counter()
    for code in alle:
        if code in seen:
            continue
        codering = []
        start = code[:]
        c = 0
        while True:
            code = next_code(code)
            codering.append(code)
            c+=1
            if code == start:
                break:
        seen.update(codering)
        ringcounter[c] += 1
    kontrolle = 0
    for key, value in ringcounter.items():
        kontrolle += key * value
        print( "{} Codereihen aus {} Codes".format(value, key))
    print("kontrollsumme ist {}".format(kontrolle))
                
            
main()
karolus
User
Beiträge: 140
Registriert: Samstag 22. August 2009, 22:34

Hallo

Oder ein wenig übersichtlicher:

Code: Alles auswählen

from itertools import product
from collections import Counter

def next_code(code):
    return code[1:] + (sum(code) % 10,)        

def main():
    pool = set(product(range(10),repeat=4))
    ringcounter = Counter()    
    while pool:
        code = pool.pop()
        codering = []
        start = code[:]
        c = 0
        while True:
            code = next_code(code)
            codering.append(code)
            c += 1
            if code == start:
                break
        pool = pool.difference(codering)
        ringcounter[c] += 1
            
    kontrolle = 0
    for key, value in ringcounter.items():
        kontrolle += key * value
        print( "{} Codereihen aus {} Codes".format(value, key))
    print("kontrollsumme ist {}".format(kontrolle))
karolus
User
Beiträge: 140
Registriert: Samstag 22. August 2009, 22:34

Version 0.0.3 mit Generatorfunktion:

Code: Alles auswählen

from itertools import product
from collections import Counter

def iter_code(code): 
    nextcode = code
    while True:
        nextcode = nextcode[1:] + (sum(nextcode) % 10,)
        if code == nextcode:
            return
        yield nextcode        

def main():
    pool = set(product(range(10),repeat=4))
    ringcounter = Counter()    
    while pool:
        code = pool.pop()
        codering = [code]
        for icode in iter_code(code):
            codering.append(icode)
        pool = pool.difference(codering)
        ringcounter[len(codering)] += 1
            
    kontrolle = 0
    for key, value in ringcounter.items():
        kontrolle += key * value
        print( "{} Codereihen aus {} Codes".format(value, key))
    print("kontrollsumme ist {}".format(kontrolle))
sebastian0202
User
Beiträge: 168
Registriert: Montag 9. Mai 2016, 09:14
Wohnort: Berlin

@BlackJack
Der Code kann mit einer Leichtigkeit gelesen werden, dass ist wahnsinn.
Jetzt ist mir einiges klarer.
Ich werde mir den Leitfaden ausdrucken und für neue Projekte als Vorlage hinlegen. :mrgreen:
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Hier eine Variante, die deque() verwendet:

Code: Alles auswählen

from itertools import count
from collections import deque

def count_days(code):
    digits = deque(map(int, code), len(code))
    old = deque(digits)
    for num_days in count(1):
        digits.append(sum(digits) % 10)
        if digits == old:
            return num_days

def main():
    num_days = count_days('1986')
    print('Code wiederholt sich nach', num_days, 'Tagen.')

if __name__ == '__main__':
    main()
Der Einsatz von deque() hat den Vorteil, dass man beim Verschieben nichts herum kopieren muss. Gleichzeitig erspart einem die Betrachtung der Ziffern als Sequenz die entsprechende Rechnerei. Nur das Hinzufügen der letzten Stelle aus der Quersumme habe ich rechnerisch gelöst, da dies ein "billiger" Einzeiler ist.
BlackJack

@snafu: Kleiner Bug in der Funktion: die funktioniert nur für Codes ≥1000.

Edit: Und geht auch davon aus das der Code jemals wieder erreicht wird, was man ohne Begründung IMHO nicht so einfach annehmen darf.
BlackJack

@karolus: Beim ersten Quelltext ist es äusserst unschön das `alle` und `seen` globale Variablen sind. Wobei `alle` auch gar kein `set` sein muss, denn es wird im `Code` ja nur darüber iteriert. Das ``product(range(10),repeat=4)`` hätte man gleich in die ``for``-Schleife schreiben können.

Der Code geht davon aus das man disjunkte Ringe/Kreise hat. Das muss man ja schon vorher wissen, oder irgendwie begründen können, dass der Graph so aussieht.
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

BlackJack hat geschrieben:@snafu: Kleiner Bug in der Funktion: die funktioniert nur für Codes ≥1000.

Edit: Und geht auch davon aus das der Code jemals wieder erreicht wird, was man ohne Begründung IMHO nicht so einfach annehmen darf.
Woran machst du fest, dass der Code nicht für Zahlen unter 1000 funktioniert? Der Code wird ja als String übergeben und danach werden die Ziffern einzeln betrachtet. Ich sehe da kein Problem mit führenden Nullen, falls das gemeint ist.

Und dass der Code theoretisch endlos laufen könnte, ist doch bei allen bisher gezeigten Lösungen so. Das ist ja vom Prinzip her ein typisches Halteproblem.
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Man könnte natürlich einbauen, dass man nach 1 Million Versuchen aufgibt oder sowas. Ansonsten stelle ich mir das Erkennen von Zirkeln schwierig vor, da diese prinzipiell sehr groß sein können. Nur den Fall, dass alle Stellen auf Null stellen könnte man mit aufnehmen bzw wenn sich der Code unmittelbar wiederholt (bei 11 Einsen und ähnliches).
Sirius3
User
Beiträge: 17712
Registriert: Sonntag 21. Oktober 2012, 17:20

@snafu: eine n-stellige Zahl kann maximal 10^n Zustände annehmen. Da der interne Zustand des Automaten auch eine n-stellige Zahl ist, muß sich die Folge spätestens nach 10^n Schritten wiederholen.
karolus
User
Beiträge: 140
Registriert: Samstag 22. August 2009, 22:34

Hallo
Der Code geht davon aus das man disjunkte Ringe/Kreise hat. Das muss man ja schon vorher wissen, oder irgendwie begründen können, dass der Graph so aussieht.
Bei der Betrachtung spätestens der Zweiten Zahlenreihe sollte einem schon auffallen das:
1.) jede Kombination nur jeweils einen eindeutigen Vorläufer|Nachfolger hat. ( haben kann!! )
2.) nur über einen begrenzten Vorat (hier 10**4) an Kombinationen iterieren kann.
3.) →irgenwann (<=10**4) Iterationen wieder jeder mögliche Ausgangspunkt erreicht wird.
4.) Aus 1.) folgt auch das es keine Schnittmengen zwischen verschiedenen Ringen geben kann.

Letzlich beweisst mein Code das ja empirisch.
BlackJack

@snafu: Okay ich hatte das nicht vorhandene Problem der führenden Nullen gesehen. :oops:

Das der Code endlos laufen könnte ist nicht bei allen Lösungen so. Der könnte zudem nicht nur theoretisch endlos laufen sondern auch praktisch, sofern man nicht vorher erklären kann warum jeder Code irgendwann wieder zu sich selbst führt.

Meine erweiterte Frage war ja: „Wie lange brauchen andere Kombinationen und wie viele Kombinationen gibt es, die nie wieder zum Ausgangscode zurückkehren?“

Wenn man also nicht (vorher) erklären kann warum es keine Kombination gibt, bei der nie wieder zum Ausgangscode zurückgekehrt wird, dann ist ein Programm das diese Frage nicht explizit berücksichtigt IMHO fehlerhaft, weil es die Frage nur dadurch beantwortet, weil es nicht hängengeblieben ist.

Und ja, den Fehler habe ich in meinem „von funktional nach OOP“ auch gemacht.

Die Lösungen von sebastian0202 und mein C-Programm berücksichtigen den Fall aber. Seins verwendet die -1 als Kennzeichen und meins 'inf'.

Halteproblem triffts nicht ganz weil es dort ja darum geht, dass ganz allgemein nicht beweisen kann ob ein beliebiges gegebenes Programm zum Ende kommt. Hier haben wir aber ein konkretes Programm, sogar ohne Eingaben von aussen und mit einer endlichen Wertemenge. Ob es hängen bleibt oder nicht, kann man als Grapgenproblem formulieren. Knoten sind die 10.000 Codes. Kanten bestehen zwischen Knoten die für einen Code und dessen Folgecode stehen. Zu beweisen wäre jetzt, dass jeder Code genau einen möglichen Vorgänger hat. Denn er hat auf jeden Fall einen Nachfolger. Wenn jeder genau einen Vor- und Nachgänger hat, dann muss der Graph aus einem oder mehreren Kreisen bestehen und somit käme auch jeder Code wieder zu sich selbst.

Ein Kreis kann nur maximal so gross sein wie es verschiedene Kombinationen gibt. Bei vier Stellen kann er also maximal 10.000 Codes umfassen. Eine Million Durchläufe wäre demnach eine sinnvolle Begrenzung für sechsstellige Codes. Alternativ muss man sich nur merken welche Codes man schon gesehen hat, damit man keinen, beziehungsweise nicht die falschen, mehr als einmal berechnet. Das ist eine Abwägung zwischen Laufzeit und Speicherverbrauch.

@karolus: 3. Sehe ich so ohne weitere Erklärung nicht. Es sind Graphen möglich die 1, 2, und 4 erfüllen, bei denen 3 nicht gilt.
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Sirius3 hat geschrieben:@snafu: eine n-stellige Zahl kann maximal 10^n Zustände annehmen. Da der interne Zustand des Automaten auch eine n-stellige Zahl ist, muß sich die Folge spätestens nach 10^n Schritten wiederholen.
Prima. Damit hätte man schon einen guten Wert für's Limit.
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

karolus hat geschrieben:Hallo
4.) Aus 1.) folgt auch das es keine Schnittmengen zwischen verschiedenen Ringen geben kann.

Letzlich beweisst mein Code das ja empirisch.
Nicht wirklich. Aus dem Zustand 0000 käme der Code bei den vorliegenden Regeln nicht mehr raus.

Ich wollte 3 zitieren. Bin gerade am Handy...
karolus
User
Beiträge: 140
Registriert: Samstag 22. August 2009, 22:34

Hallo
@karolus: 3. Sehe ich so ohne weitere Erklärung nicht. Es sind Graphen möglich die 1, 2, und 4 erfüllen, bei denen 3 nicht gilt.
Da kann ich jetzt nicht ganz folgen, welche sollten das sein? (Wir sind uns doch darüber einig das kein Ring aus der gegebenen Grundmenge "ausbrechen" kann?)
Hätte ich 3. hinter 4.plazieren sollen?
snafu hat geschrieben:Nicht wirklich. Aus dem Zustand 0000 käme der Code bei den vorliegenden Regeln nicht mehr raus.
'0000' → Nachfolger ist '0000'
Das ist dann lediglich ein Ring der Länge 1, ansonsten werden alle Regeln erfüllt.
Letzlich kommt kein Ring aus seinem "Zustand" heraus, sie sind nur unterschiedlich lang.
Zuletzt geändert von karolus am Freitag 10. Februar 2017, 17:01, insgesamt 1-mal geändert.
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Es gibt mindestens eine Situation, wo der Ausgangspunkt nicht mehr erreicht wird. Wie gesagt, bei 0000 fährt er sich fest. Die Quersumme daraus ist Null. Diese wird hinten dran gehangen und es wird kein andere Zustand mehr erreicht. Insofern widerspricht dies deiner Annahme, dass spätestens nach 10^n Versuchen der Ausgangspunkt erreicht wird. Man kann nur folgern, dass nach 10^n Versuchen garantiert kein bis dahin unbekannter Zustand erreicht wird und man somit aufhören kann.
BlackJack

@karolus: Das hier sollte 1, 2, und 4 erfüllen:

[codebox=text file=Unbenannt.txt]1->2->3->4
^ |
| v
6<-5[/code]

Jeder hat genau einen Nachfolger, es gibt einen begrenzten Vorrat von 6 Knoten, es wird aber nicht für jeden Knoten nach spätestens 6 Schritten wieder der selbe Knoten erreicht. Daran ändert auch nichts das 4 gilt. Man könnte auch mehrere Komponenten dieser Art haben wenn es mehr Knoten gäbe. Und es könnte zu so einem Kreis auch mehrere ”Zufahrten” geben statt nur einer. Und mehrere ”eingehende Äste” bei den ”Zufahrten”.

Man müsste für ausschliesslich Kreise also noch zeigen, dass jeder Knoten auch genau *einen* Vorgänger hat.

@snafu: Beim Code '0000' hat man wie karolus schon sagte einen Kreis der Länge 0. Das heisst nach genau einem Tag/Schritt hat man den Ausgangszustand wieder erreicht. Da fährt sich nichts fest.
Antworten