[ZT] Zusammengesetzte Zahl und deren Teilbarkeit |
05.06.2016, 15:57 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
[ZT] Zusammengesetzte Zahl und deren Teilbarkeit Es gilt zu bestimmen, wie viele solcher Zahlen exisitieren, die durch eine andere Zahl n teilbar sind. Für kleinere Ziffernmengen wie oben ist es m. E. recht einfach und schnell möglich, Permutationen zu bilden und die Teilbarkeit zu prüfen. Für n = 11 gibt es demnach für das obige Beispiel, wenn mein Rechenprogramm nicht falsch ist, 593 Lösungen, bspw. (8, 7, 4, 1, 0, 7, 4, 1) => 87410741 / 11 = 7946431. Wenn die Menge aber größer wird und die möglichen Zahlen aus 15 oder mehr Ziffern bestehen, ist dieser Ansatz mächtig zeitraubend. Für den Fall einer Länge von 15 Ziffern gibt es bereits 1.307.674.368.000 mögliche Permutationen. Die alle zu prüfen dauert ewig. |
||||||||||||||
05.06.2016, 18:00 | Elvis | Auf diesen Beitrag antworten » | ||||||||||||
Das kann nicht ewig dauern, aber bestimmt sehr lange für große Zahlen. ![]() |
||||||||||||||
05.06.2016, 18:04 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
14-stellige benötigen ca. 20 Minuten... Gibt es ggf. eine Möglichkeit, schneller zum Ergebnis zu kommen? |
||||||||||||||
05.06.2016, 18:09 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Nun, bei speziellen Teilern kann man natürlich auch mehr an Vorwissen reinstecken. Wenn wir mal das obige Beispiel der Teilbarkeit durch 11 nehmen: Da gibt es ja die bekannte Teilbarkeitsregeln mit der alternierenden Quersumme. D.h., die Summe der Ziffern an den geraden Positionen muss mit der Summe der Ziffern an den ungeraden Positionen modulo 11 übereinstimmen. Nehmen wir das Beispiel (1,1,4,4,7,7,8,0) oben: Gesamtsumme der Ziffern ist , daher muss zwangsläufig gelten. Klar, da ist noch etwas Arbeit zu tun. Dennoch reduziert das die zu untersuchende Menge schon mal gewaltig. ![]()
Ganz sicher nicht, es sind deutlich weniger, zumindest wenn du im Dezimalsystem bleibst: Bei 15 Ziffern gibt es sicher Mehrfachvorkommen von Ziffern, daher ist hier nicht einfach 15! zu rechnen, sondern die Anzahlformel für Permutationen mit Wiederholung. |
||||||||||||||
05.06.2016, 20:07 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Da hast du recht! Ohne Mehrfachvorkommen sind es 15! Möglichkeiten. Ich versuche mal, mir so etwas wie eine rekursive Funktion zu bauen, um mir "g" und "u" zu bauen. Natürlich erstmal im kleineren Maßstab ![]() |
||||||||||||||
05.06.2016, 21:58 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Der Plan mit rekursiver Funktion war wohl etwas zu kühn ![]() Permutationen sind auf jeden Fall der einfachere, aber zeitaufwendigere Weg. Wenn ich als Menge (1,1,2,2,3,3,4,4,5,5,6,6,0,0) und n = 11 zugrunde lege und wirklich nur 14-stellige Zahlen betrachte, also abbreche sobald die Zahl mit 0 beginnt, dauert das Permutieren bereits knapp 29 Sekunden. Für die Berechnung kommen dann nochmal unbedeutende 4 Sekunden. Als Anzahl für diese Menge erhalte ich 58.679.513. Gibt es denn einen Algorithmus, der nur "distinkte Pemutationen" betrachtet, also die Doppelung von Ziffern ausblendet und überspringt? Ich habe Zweifel ![]() |
||||||||||||||
Anzeige | ||||||||||||||
|
||||||||||||||
05.06.2016, 22:53 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Nochmal: Wie willst du 15 Ziffern ohne Mehrfachvorkommen aus einer Menge von nur 10 verschiedenen Ziffern auswählen? ![]()
Die Summe deiner 14 Werte ist 42. Das hat zur Folge, damit kommen als Summen der jeweils 7 Zahlen die Werte 10, 21 oder 32 in Frage. Durch händisches Abzählen aller dann noch in Frage kommenden Fälle komme ich auf , allerdings zähle ich die Zahlen mit einer oder auch zwei führenden Nullen mit.
Auch nach Abzug der Nullen ziehe ich diese Zahl in Zweifel. Sicher, dass dein Algorithmus korrekt ist? Was bekommst du denn für ein "kleineres" Beispiel ohne Nullen heraus, sagen wir mal (1,1,2,2,3,3,4,4) ? ![]() |
||||||||||||||
05.06.2016, 23:56 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Nur mit (1,1,2,2,3,3,4,4) komme ich auf 648. |
||||||||||||||
06.06.2016, 00:15 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Hmm, das stimmt noch. Hab jetzt mal selber simuliert (Rechenzeit < 15s), und stelle fest: Beide Resultate für (1,1,2,2,3,3,4,4,5,5,6,6,0,0) sind falsch - deine und meine: Es sind Zahlen, davon ohne Null am Anfang. Nur mal so als Vermutung: Kann es sein, dass du nicht bedacht hast, dass deine 14stelligen Zahlen die 32Bit-Integer-Grenze sprengen? |
||||||||||||||
06.06.2016, 00:49 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Die Zahlen selbst brauche ich doch eigentlich nicht ![]() Ich bin für n = 11 mit der nicht alternierenden Zweierquersumme rangegangen, und setze dabei voraus, dass die zu untersuchenden Zahlen eine gerade Länge haben. Hier ist mein Programm in C++:
Wenn ich C++ und nicht D benutze, brauche ich hierfür ca. 6 Sekunden. |
||||||||||||||
06.06.2016, 06:47 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Jetzt weiß ich, welchen Bock du geschossen hast: Nicht mit 32Bit-Zahlen, sondern mit der Startpermutation! Die kleinste Zahl (und damit kleinste Permutation), die eine echt 14stellige Zahl mit deinen gegebenen Ziffern liefert, ist NICHT 11223344556600, sondern 10012233445566. ![]() Und ich hatte mich oben auch verzählt: Richtig ist , für alle Zahlen, inklusive derer mit führenden Nullen. ![]() Das ganze resultiert aus der Aufteilung der 14 Zahlen auf die Gruppe der geraden bzw. ungeraden Positionen in folgender Weise: 0,0,1,1,2,2,4 und komplementär 3,3,4,5,5,6,6 0,0,1,1,2,3,3 und komplementär 2,4,4,5,5,6,6 0,0,1,3,5,6,6 und komplementär 1,2,2,3,4,4,5 0,0,1,4,4,6,6 und komplementär 1,2,2,3,3,5,5 0,0,1,4,5,5,6 und komplementär 1,2,2,3,3,4,6 0,0,2,2,5,6,6 und komplementär 1,1,3,3,4,4,5 0,0,2,3,4,6,6 und komplementär 1,1,2,3,4,5,5 0,0,2,3,5,5,6 und komplementär 1,1,2,3,4,4,6 0,0,2,4,4,5,6 und komplementär 1,1,2,3,3,5,6 0,0,3,3,4,5,6 und komplementär 1,1,2,2,4,5,6 0,0,3,4,4,5,5 und komplementär 1,1,2,2,3,6,6 0,1,1,2,5,6,6 und komplementär 0,2,3,3,4,4,5 0,1,1,3,4,6,6 und komplementär 0,2,2,3,4,5,5 0,1,1,3,5,5,6 und komplementär 0,2,2,3,4,4,6 0,1,1,4,4,5,6 und komplementär 0,2,2,3,3,5,6 0,1,2,2,4,6,6 und komplementär 0,1,3,3,4,5,5 0,1,2,2,5,5,6 und komplementär 0,1,3,3,4,4,6 0,1,2,3,3,6,6 und komplementär 0,1,2,4,4,5,5 Sonderfall ist der Summand für 0,1,2,3,4,5,6 und komplementär 0,1,2,3,4,5,6 In jedem der aufgezählten 13+5+1=19 Fälle kann nun noch innerhalb der Gruppen permutiert werden. |
||||||||||||||
06.06.2016, 10:38 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Wenn ich auf viel kleinerer Ebene (1, 0, 2, 3) voraussetze und permutiere, erhalte ich 18 Möglichkeiten, bei denen solche mit führenden Nullen gar nicht erst auftauchen. |
||||||||||||||
06.06.2016, 10:51 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Vielleicht war ich nicht deutlich genug: Mein Einwand bezieht sich nicht darauf, dass du später als 00112233445566 anfangen darfst. Sondern darauf, dass du mit 11223344556600 zu spät anfängst, und dir dadurch alle Lösungen zwischen durch die Lappen gehen! Und genau das macht die Differenz zwischen deiner zu kleinen Anzahl und der richtigen Anzahl aus. ![]() |
||||||||||||||
06.06.2016, 11:38 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
![]() Ich hatte meinen letzten Post eingefügt, weil mir scheint, dass ich mir nach der Umformung der Startanordnung der Menge von bspw. (1,1,2,2,3,3,4,4,0,0) nach (1,0,0,1,2,2,3,3,4,4) keine Sorgen mehr um führende Nullen machen muss. |
||||||||||||||
06.06.2016, 11:47 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Das mit dem Weglassen der Zahlen mit führenden Nullen macht die Sache (wie so oft) in der händischen Berechnung schwieriger. Ich mache es trotzdem mal: Zählen wir also die durch 11 teilbaren Zahlen, die mit 0 beginnen im Szenario (0,0,1,1,2,2,3,3,4,4,5,5,6,6). Das sind: 1) aus den blau gekennzeichneten Fällen (die alle mit 0,0 starten): Die eine Null wird an die vorderste linke Position festgenagelt, die anderen 6 Ziffern sowie die 7 aus der anderen Gruppe dürfen wieder wie gehabt permutieren. 2) für die rot gekennzeichneten Fälle, die mit 0,0 starten. 3) für die rot gekennzeichneten Fälle, die mit 0,1 starten. In den Fällen hat man auch die Varianten zu zählen, wo die rechte Gruppe Zahlen liefern kann, die mit Null beginnen, daher der generelle Vorfaktor 2. 4) für die Zahlen mit jeweils 0,1,2,3,4,5,6,7 in den Gruppen. Macht summa summarum , und damit die auch die Gesamtanzahl , wie in der Simulation. ![]() Blöd ist natürlich, dass man das für beliebige Ziffernmengen besser automatisieren muss, insbesondere die Fallerfassung - ich hatte mich beim Durchzählen der Fälle ja auch erst vertan (11 rote statt richtigerweise 13 rote Fälle). Dennoch ist das der Weg, wenn du nicht bei 14,15 Stellen hängen bleiben willst - mit dem Weg kommst du locker über 20, vielleicht sogar 25. |
||||||||||||||
06.06.2016, 16:56 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Da war ich wohl übervorsichtig. ![]() Ich hab mal ein Progrämmchen geschrieben, was nur die Teibarkeit durch 11 untersucht, dafür aber mit deutlich größeren Zahlen zurecht kommt: Nehmen wir z.B. jeweils 6mal die Ziffern 0..9, so gibt es ja solche 60-stelligen Zahlen. Das Programm berechnet, dass davon durch 11 teilbar sind, darunter ohne führende Null (RunTime < 5s). |
||||||||||||||
06.06.2016, 18:13 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
![]() Davon bin ich noch ein Stück entfernt. |
||||||||||||||
06.06.2016, 19:29 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Ich bin noch nicht völlig von der Korrektheit überzeugt ... wir könnten ja mal für ein paar "mittelgroße" Testdatensätze (also so 13 oder 14 Ziffern) von dir die Resultate vergleichen, d.h., für was anderes als je zwei gleiche Ziffern 0...6. ![]() P.S.: Zur Absicherung habe ich noch was eingebaut: Man kann nicht nur die Anzahl der Zahlen bestimmen, die durch 11 teilbar sind, sondern für jeden Wert die Anzahl der Zahlen, die durch 11 geteilt den Rest ergeben. Die Summe der Anzahlen von ist eine kleine Überprüfung des Algorithmus, die muss ja notwendigerweise gleich der Gesamtzahl aller Permutationen der Zifferngruppe sein. |
||||||||||||||
07.06.2016, 14:04 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Ich muss dich leider auf Donnerstag vertrösten... Dann setze ich mich dran und versuche was zu finden ![]() |
||||||||||||||
07.06.2016, 15:07 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Was mein letztes "P.S." betrifft - sowas kannst du bei dir auch ganz leicht einbauen, ohne nennenswerte Performance-Verluste:
Damit überprüfst du z.B., ob dein "next_permutation" wirklich alle relevanten Permutationen durchgeht. Im Beispielfall ( 1, 0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6 ) muss diese zuletzt ausgegebene j-Summe z.B. betragen. |
||||||||||||||
09.06.2016, 15:49 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Deine Zahlen konnte ich reproduzieren: Für long Z[] = { 1, 0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6 }; erhalte ich insgesamt 58.3783.200 Permutationen, mit 60.555.600 möglichen Zahlen, die sich restfrei durch 11 dividieren lassen. Für long Z[] = { 1, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5 }; sind es insgesamt 114.354.240.000 Permutationen mit 8.594.208.000 Werten = 0 (mod 11). Für long Z[] = { 1, 0, 0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 5, 5 }; sind es insgesamt 79.279.200 Permutationen und 5.775.000 Werte = 0 (mod 11). Weil du ja weiter oben nach anderen Mengen zur Verifikation gefragt hattest... |
||||||||||||||
09.06.2016, 16:38 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Ok, wenn ich einen Batchfile mit dem Inhalt
(MB_569128 ist der wenig kreative Name meines Programms) starte, so bekomme ich folgende result.txt:
Sieht nach Übereinstimmung aus. Und oben das Beispiel war Aufruf MB_569128 0 6 6 6 6 6 6 6 6 6 6 mit Ergebnis
Ich stell mal den Quelltext zur Verfügung, aber ohne jede Gewähr und jeden Support. Zum Kompilieren benötigst du noch die gmp (unter linux oder cygwin kein Problem - mit Visual Studio aber schon mit gewissen Anstrengungen verbunden ![]() [attach]41987[/attach] |
||||||||||||||
09.06.2016, 20:01 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Danke danke ![]() Ich werde mir das anschauen! Ich habe Mint als Zweitsystem laufen. Das sollte also kein Problem sein ![]() |
||||||||||||||
09.06.2016, 20:21 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Die gmp ist natürlich nur an Board, weil so extrem große Zahlen rauskommen können. Solange das Ergebnis unter 20 Stellen bleibt, kommst du auch mit 64-Bit-Integer (auf den meisten Systemen long long) statt mpz_class aus. Oder mit double, dann eben nicht in der vollen Genauigkeit. ![]() ---------------------------------------------- Zur "Theorie" hinter dem Programm: Wir haben als Vorgabe für jede Ziffer die Anzahl , mit der sie in der gesuchten Zahl auftauchen soll. Somit ist die Stellenzahl der gesuchten Zahl, mit Ziffern an ungeraden Positionen sowie Ziffern an geraden Positionen (wir beginnen "hinten" zu zählen mit Position 0, der Einerstelle). Außerdem ist die Quersumme dieser Zahlen. Für eine passende solche -stellige Zahl möge die Quersumme an den geraden und an den ungeraden Positionen sein. Dann ist natürlich zu fordern, außerdem muss bei Vorgabe des Restes bei Division durch 11 die Bedingung erfüllt sein. Aus beidem ergibt sich , was sich eindeutig nach auflösen lässt - eine Bedingung an die Auswahl der Ziffern an den ungeraden Positionen! Nun bestimmen wir, welche Möglichkeiten es gibt, die Ziffern an den ungeraden Positionen zu wählen. Dazu genügt es erstmal, aufsteigend geordnete mit dieser Eigenschaft zu finden. D.h., wir suchen:
Letzten Endes ist eine möglichst effiziente Umsetzung des Aufspürens dieser Tupel der entscheidende Faktor für die Programmlaufzeit. (In dem Punkt bin ich mir auch ziemlich unsicher, ob das nicht noch viel besser geht, als ich es hingewerkelt habe.) Einem solchen gefundenen -Tupel lässt sich eineindeutig die Häufigkeiten der darin vorkommenden Ziffern zuordnen. Die Menge all dieser 10-Tupel sei mit bezeichnet. Für jedes solche 10-Tupel gibt es nun genau Möglichkeiten, diese Ziffern zu permutieren. Jedem solchen 10-Tupel ist nun aber auch ein 10-Tupel der Ziffernanzahlen für die geraden Positionen zugeordnet, und zwar muss die entsprechende Anzahl für Ziffer dort sein (die, die eben noch übrig sind nach Belegung der ungeraden Positionen ![]() Damit ist die gesuchte Zahlenanzahl für festes 10-Tupel gleich und summa summarum über alle Fälle dann . Kommen wir nun noch zum Problem der führenden Null: Ist gerade, so ist die vorderste, -te Position eine ungeradzahlige - ist dagegen ungerade, so ist es eine geradzahlige Position. Betrachten wir zunächst den ersten Fall, der andere folgt analog: Wir wollen nun alle Zahlen zählen, die mit einer Null beginnen. Solche kann es natürlich nur dann geben, wenn ist. In diesem Fall nageln wir diese Ziffer 0 fest und dürfen nur noch den Rest permutieren. Das führt dann auf . Ist hingegen ungerade, so folgt analog . Die Anzahl der gesuchten Zahlen ohne führende Null ist letzten Endes dann . |
||||||||||||||
09.06.2016, 20:34 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
Ich schätze wenn bei größerer Länge Ziffern häufiger vorkommen als bspw. bei 20 Stellen alle Ziffern doppelt, dann erhöht sich die Anzahl der Zahlen, die die Voraussetzungen der Dividierbarkeit mitbringen. Versuch mach kluch. |
||||||||||||||
09.06.2016, 20:53 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Da gibt's nicht viel zu schätzen, das ist das Schubfachprinzip: Bei einer 21stelligen Zahl muss es mindestens eine Ziffer geben, die mindestens dreimal drin vorkommt. ![]() |
||||||||||||||
10.06.2016, 22:46 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
g++ -O3 -Wall -o 569128 MB_569128.cpp -lgmp will kompilieren, schafft es aber nur bis hierher:
|
||||||||||||||
10.06.2016, 23:13 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||||
Kompilieren hat geklappt, nur das Linken nicht - füg mal noch ein -lgmpxx an. ![]() |
||||||||||||||
10.06.2016, 23:17 | Nicht_Adam_Ries | Auf diesen Beitrag antworten » | ||||||||||||
So hat's geklappt ![]() |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |