Logikproblem (Teilbarkeit)

[Zuckerbaum]

Hallo,

ich habe hier ein kleines LOGIK-Problem:

Ich habe eine natürliche Zahl X und eine Liste [a,b,c,d,e,...] natürlicher Zahlen. Ich möchte nun alle möglichen Teiler UND Teilerkombinationen der Zahl X herausfinden.

Beispiel:

X := 10;
Liste := [2,3,5,10];

Ergebnis := UnbekannteFunktion(X,Liste);

Und in Ergebnis sollte dann etwas in der Art stehen: [[2], [2,5], [5], [10]].

Also 10 (mod 2) = 0, 10 (mod 2*5) = 0, 10 (mod 5) = 0, 10 (mod10) = 0.


Das ganze müsste irgendwie rekursiv geschehen, aber mir fehlt die Praxis um das mal so zu programmieren. Vielleicht hat jemand eine Idee?

Die Programmiersprache ist unwichtig. Es geht mir nur um das Prinzip.

 

[Housechen]

Naja wirklich rekursiv hmm..

Rekursiv macht nicht wirklich Sinn, weil ´ne Schleife hier viel besser ist. Rekursiv lohnt sich erst bei einer Weiterführbedingung, die abhängig von dem Berechnungsergebnis ist.

Wenn am Ende eine Zeichenkette mit den Zahlen stehen soll dann so:

for(int i=0; i<Zahlenliste.Length; i++){
    if(Testzahl%Zahlenliste[i]==0){
        Ausgabestring += Zahlenliste[i].ToString() + " "
    }
}

Also das wäre jetzt die einfachste Variante, wenn ich dein Problem verstanden habe. Man kjönnte das dann natürlich noch ausweiten etc...

 

[impressive]

"ich habe hier ein kleines logistisches Problem"

bist du dir da sicher?

 

[Zuckerbaum]

Hallo,

du erhältst aber nur die Teiler i von X für die X (mod i) = 0 für i aus der Liste gilt. Kombinationen gehen dann ja verloren, z.B. X (mod i^2) = 0 oder X (mod i_1 * i_2), etc.

Ich dachte etwa an so etwas: Man ruft eine Funktion (etwa funktion(X,Liste) ) auf, welche eine Teilerliste zurückliefert (quasi das, was dein Programm erzeugt). Dann ruft man die Funktion erneut auf mit funktion(X/(erster Teiler),Liste) , etc. ... und zwar solange, bist die Funktion eine leere Teilerliste liefert...

Daher war rekursiv mein erster Gedanke.

Danke auch an impressive, mit korrekter Formulierung fällt es mir schlagartig viel leichter...

 

[tfuint]

Wie groß darf denn die Liste werden, bzw. für wieviel Elemente möchtest du das lösen? Das Problem ist nämlich garnicht ohne.

 

[impressive]

war doch nicht böse gemeint
leider kann ich dir bei deinem problem nicht wirklich weiterhelfen.

 

[tfuint]

Wenn es wenige Zahlen in der Liste sind, würde ich per quasi bruteforce machen. Also von deiner Liste ein kartesisches Produkt bilden, dann kannst du ganz einfach Testen ob die Kombi passt. Für größere Zahlen und Listen wird das dann aber schnell zu langsam, hier würde ich den erweiterten euklidischen Algorithmus verwenden. Der ist einfach zu impelmentieren. Für ganz große Mengen wird auch das zu langsam sein und du wirst sowas wie Ferma bzw. den Miller-Rabin-Test benötigen.

 

[Zuckerbaum]

Hallo,

es werden vermutlich meist wenige (< 10) mäßig große (~ 10^10) Zahlen in der Liste stehen. Wobei in den meisten Fällen überhaupt nur ein Teiler enthalten ist. Die wenigen Ausnahmen untersuche ich gerade (Geschwindigkeit ist daher nicht oberste Priorität) Das kartesische Produkt hatte ich als Notlösung angedacht, weil mir dann aus anderen Gründen die Struktur meiner Liste abhanden kommt.

Könntest du die Idee mit den euklidischen Algorithmus kurz erläutern. Da stehe ich wohl auf der Leitung... (oder wolltest du damit nur die Teilbarkeit prüfen?)

 

[tfuint]

Das mit der Teibarkeit ist ein schöner Nebeneffekt, aber der erweiterte Euklid gibt dir ja zusätzlich auch den größten gemeinsamen Teiler aus. Wenn du also deine Zahl X und ein Element deiner Liste auf ggT prüfst, bekommst wenn sie einen Teiler haben, auch den ggT. So kannst du schon mal alle Zahle die Größer als der ggT sind in deiner Liste Ignorieren (im zweiten Schritt) für diese Zahl X und das Listenelement a. Dann Prüfst du (wie du schon sagtest rekursiv), wenn der ggT in deiner Liste stand, dieses Listenelement wieder auf ggT mit den kleineren Elementen in der Liste.
So mußt du nicht alle Kombinationen durchprüfen und bei 10x10 Zahlen wirst du auch recht schnell die Rekursion abbrechen können.
Das Schicke ist, du kannst das alles in eine Funktion packen und brauchst nicht ewig viele If Abfragen und tausend cases. Denn grade kombis wie a*b*c=X sind sonst recht Aufwendig.

 

[Zuckerbaum]

Hallo,

also nochmal danke für die Anregung mit dem kartesischen Produkt. Ich hatte das vorhin zwischen zwei VL mal programmiert und meine Liste läßt sich nach etwas probieren nun doch noch handhaben.

Auch wenn ich deine Idee immer noch nicht verstehe. Betrachte etwa das Beispiel aus Beitrag 1. ggT(10,2)=2, aber im zweiten Schritt kann ich 5 nicht ignorieren. Vermutlich meintest du das aber anders.

Ich habe als "Aufnahmebedingung" in die Liste einfach auf X(n)=0 geprüft

 

[tfuint]

ggT(10,2)=2 ok ausgeben
in der Liste ist nichts kleineres 2 --> fertig nächste Zahl

ggT(10,3)=1 also nicht ausgeben --> fertig nächste Zahl

ggT(10,5)=5 ok ausgeben
in der Liste ist was kleineres (2 und 3) --> also ggT(5,3)=1 ggT(5,2)=1 bedeutet 5 kann nicht weiter zerlegt werden mit Zahle aus der Liste. --> also prüfe die Kombination mit Zahlen aus der Liste < 5 (2,3) 2*5 ok 3*5 fehler.
Der ggT reduziert also die Kombinationen die du Überprüfen musst, sehr strak.

 

[Zuckerbaum]

Ah ok. Zugegeben hatte ich vorhin nicht weiter darüber nachgedacht. Sorry.

Bin gerade fertig mit dem Programm und konnte aus den ersten 40000 interessanten Fällen 5 relevante herausfiltern (was erstaunlich wenige sind). Der Aufwand hat sich gelohnt