Eindeutige Zahlen in C ++ [geschlossen]

Sie können Rekursion anwenden. Prototyp dieser Funktion ist dann wie folgt:

EDIT: zur Vervollständigung präsentiere ich hier meine Lösung (ich denke, sie hat eine bessere Lesbarkeit als von Ben Voigt und aufsteigender Ausgabe-Reihenfolge

und hier ist der Testcode

Ссылка

Wie funktioniert das?

Es ist einer der Klassiker in der Rekursion. Zuerst gibt es eine Haltebedingung. Und dann gibt es Hauptschleife.
Hauptschleife, wo von start_from_digit geht, da alle generierten Ziffern in nicht abnehmender Reihenfolge sind. Wenn zum Beispiel current_number 15 ist, wird% code_de% mit

Bei jedem Aufruf wird geprüft, ob wir das Ende mit print_digits erreicht haben, und wenn nicht, wird mit der Ziffer fortgesetzt, die als num_of_remaining_digits (2. Parameter) mit start_from_digit

Sie suchen nach der Kombination einiger Zeichen (0..9) mit einer bestimmten Länge (100 = 2, 1000 = 3).

Sehen Sie sich hier Algorithmus an, um alle Kombinationen zurückzugeben von k Elementen aus n

Ich würde eine Hash-Tabelle verwenden, etwa so

1) Leiten Sie einen Schlüssel von der Zahl ab, die so abgeleitet wurde, dass Ziffern mit derselben Nummer den gleichen Schlüssel haben (z. B. die Ziffern addieren, also "124" und "142" den Schlüssel 7 haben oder das Produkt von die Ziffern (+1), also "124" und "142" haben die Taste 30 - müssen für die Ziffer 0 +1 haben

2) Setzen Sie die Zahlen in eine Hash-Tabelle, die durch den Schlüssel

Nun ist der Test, ob Sie bereits eine Nummer mit den gleichen Ziffern haben, auf Entitäten in der Hash-Tabelle mit demselben Schlüssel beschränkt. Dieser Algorithmus erfordert einen linearen Speicher und seine Leistung hängt davon ab, wie gut ein Schlüssel ist, den Sie sich vorstellen können.

Demo: Ссылка

Beachten Sie zunächst, dass Ihre Regel ein Vielfaches von 11 ausschließt. (Warum?)

Beginnen Sie mit der Generierung aller 2-stelligen Zahlen mit der ersten Ziffer = 1.

Generiere jetzt alle zweistelligen Zahlen mit der ersten Ziffer = 2, aber erzeuge keine Zahlen, die mit den Zahlen in der ersten Liste übereinstimmen.

Wiederhole für 3, aber erzeuge keine Zahlen aus den ersten beiden Listen.

Beachten Sie, dass für jede 2-stellige Zahl ab, damit sie sich qualifiziert, dass ein & lt; b, oder du hättest schon die entsprechende Zahl ba erzeugt.

In PASCAL, nur weil ich mich ornery fühle:

ZUSÄTZLICH SPÄTER

Beachten Sie, dass die Zahlen, die Sie generieren möchten, ihre Ziffern immer streng monoton erhöhen werden. Für eine Nummer 2abc zu qualifizieren, beachten Sie, dass 2 & lt; ein & lt; b & lt; c. (Beispiel: 2539 ist eine Übereinstimmung für 2359 und sollte zurückgewiesen werden.)

Nehmen wir 1 bis 1000. Da es in 1000 1000 Ziffern gibt, drucke ich 1 als 0001, also sind 0001, 0010, 0100, 1000 die gleiche Nummer wie mein Algorithmus. Auch 0120, 0012, 0210, 0102, 0201, 0021 sind gleiche Nummern.

Hier ist das Programm:

Scheint so einfach zu sein:

Wirklich, nur die Bedingung if ist interessant: sie muss alle relevanten Eigenschaften der Listenelemente untersuchen.

Erstellen Sie eine Funktion, die einen String akzeptiert und ein Array mit Strings mit allen möglichen Permutationen der Zeichen in diesem String zurückgibt. Es wäre nicht schwer, aber es wäre wahrscheinlich am einfachsten, rekursiv zu machen. Obwohl, einfacher gesagt als getan.

Sobald Sie diese Funktion haben und das Array zurückgibt, gehen Sie einfach durch das Array und entfernen die Indecies, die eine gemeinsame Nummer haben, mit einer im Array.

Wenn Sie eine Menge von Ziffern haben, ist eine beliebige Permutation dieser Menge keine gültige Lösung, also stellen Sie zuerst eine Funktion her, um festzulegen, ob eine Zifferngruppe eine Permutation einer anderen Gruppe ist. Um einzelne Ziffern zu erhalten, können Sie durch 10 rekursiv dividieren, bis Sie einen Wert von Null erhalten. Wenn Sie alle Ziffern in ein Array wie [1,2,4] schreiben, um zu überprüfen, ob anther-Array eine Permutation ist (Sie überprüfen es nur, wenn sie die gleiche Länge haben) von antaher set:

Ich habe es nicht getestet, aber ich denke, es funktioniert, sonst sag es mir. Was das Setzen aller Ziffern in ein Array angeht, denke ich, dass es ziemlich einfach ist. Sobald Sie alle Zahlen generiert haben, überprüfen Sie, ob eine bestimmte Zahl keine Permutation einer bereits vergebenen Zahl ist.

Hier ist meine Idee, für jeden Wert setzen Sie die Ziffern davon in einen Satz. Verwenden Sie dieses Set als Schlüssel für ein anderes Set, das nachverfolgt, welche Nummern verwendet wurden. In meinem Fall verwende ich ein Bitfeld als eine Menge für die Ziffern, d. H. Die Ziffer 0 wird durch eine 1 repräsentiert, die Ziffer 1 wird durch eine 2 (2 durch eine 4 und so weiter) dargestellt. Zu müde um es zu erklären, hier ist tha codez: