Laden...

Algorithmus Berechnung von Vielfachen

Erstellt von hier0 vor 13 Jahren Letzter Beitrag vor 13 Jahren 7.593 Views
H
hier0 Themenstarter:in
5 Beiträge seit 2011
vor 13 Jahren
Algorithmus Berechnung von Vielfachen

Hallo zusammen,

Ich brauche einen algorithmus der folgende aufgabe erledigt:

Eine Zahl x soll in die passenden Vielfachen von 3 aufgeteilt werden,
d.h. wenn x = 12 dann Ergebnis: 12, 2x6, 6+2x3, 4x3

dabei dürfen bestimmte Vielfache nicht berücksichtigt werden
(27,30,33 und alles >36)

Wenn jemand nen Ansatz hat oder mir vernünftige Suchbegriffe für google nennen kann wäre ich wirklich sehr begeistert. (Wie Ihr am Threadtitel merkt fällt es mir schon schwer das Thema zu benennen 😃

Vielen Dank im Voraus

731 Beiträge seit 2006
vor 13 Jahren

Hi hier0,

das sieht mir ganz nach Primfaktorzerlegung aus.

Auch hilfreich: Verfahren

MfG
wax

H
hier0 Themenstarter:in
5 Beiträge seit 2011
vor 13 Jahren

Hi Wax und danke für die schnelle Antwort.

Ja das stimmt, es sieht sehr nach Primfaktorzerlegung aus, allerdings brauche ich ja nicht alle primfaktoren von x sondern nur einen, die 3.

Ich habe für einen ersten Entwurf versucht das ganze in IF Abfragen zu realisieren


WENN x < 3
 DANN ergebnis = 3;
WENN x zwischen 3 UND 6
 DANN ergebnis = 6, 3-3;
usw

Das ist natürlich sehr unschön und auch nicht vollständig möglich.

edit: Ich habe vergessen zu erwähnen, dass wenn x nicht furch 3 Teilbar ist (bspw 13) die nächsthöhere, durch 3 teilbare Zahl genommen wird (bspw 15)

731 Beiträge seit 2006
vor 13 Jahren

Hi,

nur mal Interesse halber: wofür? 😉

Mfg
wax

H
hier0 Themenstarter:in
5 Beiträge seit 2011
vor 13 Jahren

Das Ganze wird eine Lizensverwaltung.
Alte (ungültig gewordene)Lizenzen mit Restzeit werden durch neue aus der DB ersetzt.

x aus meinem Beispiel ist die Summe von Restzeiten dieser Lizensen in Monaten.
(Pro Fall können mehrere ungültige Lizenzen eingegeben werden)

Anforderung ist (leider) das es zunächst eine Vorschlagsliste von neuen Lizensen gibt (nach o.g. Muster) aus denen der User dann die für sich passende Konstellation wählt, dafür soll die Vorschlagsliste möglichst vollständig sein.
Die kleinste Lizensdauer die vergeben werden kann sind dabei 3 Monate.

MfG
hier0

Gelöschter Account
vor 13 Jahren

Ok. also nicht kleiner als 3 Monate... aber warum ein vielfaches von 3? und warum nicht 27 und 30 oder 33?

B
20 Beiträge seit 2010
vor 13 Jahren

vielleicht sowas?
bin mir nicht sicher ob ich es richtig verstanden habe aber sollte nen guter
ansatz sein ..


static List<Faktor> Berechne(int anzahl) {
            Faktor fac = null;
            var list = new List<Faktor>();

            if (anzahl < 3)
                return list;
            for (int i = 3; i <= anzahl; i += 3) {
                if (anzahl % i == 0) {
                    fac = new Faktor { Fac1 = anzahl / i, Fac2 = i };
                    list.Add(fac);
                }
            }
            return list;
        }
        class Faktor {
            public int Fac1 { get; set; }
            public int Fac2 { get; set; }
        }
5.742 Beiträge seit 2007
vor 13 Jahren

Ich habe vergessen zu erwähnen, dass wenn x nicht furch 3 Teilbar ist (bspw 13) die nächsthöhere, durch 3 teilbare Zahl genommen wird (bspw 15)

Auf die Gefahr hin, dass ich dich falsch verstanden habe:


int result = zahl;
if ((zahl % 3) != 0)
   result = (zahl % 3) + 3;

Das wäre somit ein idealer Fall für Modulo, welches sich verwenden lässt, um auf Teilbarkeit zu testen.

Die Vielfachen brauchst du ja scheinbar gar nicht, oder?

H
hier0 Themenstarter:in
5 Beiträge seit 2011
vor 13 Jahren

Bin grad dabei die Lösungsvorschläge und Ansätze durchzuprobieren.
Bisher leider ohne Erfolg, aber ich beantworte schonmal zunächst die aufgekommenen Fragen:

@ JAck30lena:

Ok. also nicht kleiner als 3 Monate... aber warum ein vielfaches von 3? und warum nicht 27 und 30 oder 33?

3 Monate ist die kürzeste Lizensdauer die es bei uns gibt. es gibt weiterhin keine Lizenzschlüssel für 27,30,33 oder >36 Monate Laufzeit haben.

wenn also 27 Monate Restlaufzeit bestehen muss mindestens ein 24 Monate + ein 3 Monate Schlüssel ausgegeben werden. Allerdings ist der Wunsch da das z.B. auch 12 Monate + 9 Monate + 6 Monate auswählbar ist.

@biu

vielleicht sowas?
bin mir nicht sicher ob ich es richtig verstanden habe aber sollte nen guter
ansatz sein ..

Danke für deinen Code, momentan gibt er mir zwar kein vernünftiges Ergebnis, aber ich sehe ihn als Ansatz und teste weiter daran rum

@winSharp93

Das wäre somit ein idealer Fall für Modulo, welches sich verwenden lässt, um auf Teilbarkeit zu testen.

Die Vielfachen brauchst du ja scheinbar gar nicht, oder?

Den modulo werd ich sicherlich brauchen, aber da das Ergebnis nicht nur eine Zahl sondern mehrere (wie beschrieben z.B. '6' UND '2x 3' oder '9' UND '6+3' UND '3x3') muss ich schon mit Vielfachen rechnen (Glaube ich zumindest 😉

Ich hoffe ich konnte die Fragen klären.
Herzlichen Dank schon einmal an alle die sich hier dem Problem annehmen.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo hier0,

wenn ich dich richtig verstehe, geht es gar nicht um Vielfache, sondern um eine Zusammenfassung einer vorgegebenen Anzahl von Summanden (die alle den Wert 3 haben), z.B. 12 = 3 + 3 + 3 + 3 oder 6 + 3 + 3 oder 6 + 6 oder 9 + 3 und zwar so, dass die größten Summanden immer vorne stehen, also nicht 3 + 6 + 3 und nicht 3 + 9.

Da alle Ausgangssummanden 3 sind, geht es eigentlich nur darum, viele Summanden man zusammenfasst. Bei 6 + 3 + 3 die ersten beiden. Bei 6 + 6 die ersten beiden und die letzten beiden, bei 9 + 3 die ersten drei.

Im Grunde ist also die Frage, wie kann ich eine Kette von x Summanden so in mehrere Ketten von Summanden aufteilen, dass die Anzahl Summanden in allen Ketten zusammen wieder x ergibt und nie eine Kette, die länger ist, hinter einer Kette steht, die kürzer ist. Also (3 + 3 + 3 + 3) oder (3 + 3) + (3) + (3) oder (3 + 3) + (3 + 3) oder (3 + 3 + 3) + (3).

Das kann man rekursiv ganz einfach lösen. Die erste Rekursionsebene wählt der Reihe nach eine Kette der Länge 1 bis n, wobei n das Minimum aus der Gesamtlänge der Eingabekette und der Zahl 8 ist (wegen der Einschränkung, dass es keine Lizenzen mit mehr als 3 *8 = 24 Monaten gibt). Der jeweils nicht verbrauchte Rest wird an die nächste Rekursionsebene übergeben, wobei die nur noch die Auswahl hat zwischen 1 und m, wobei m das Minimum aus die Länge der in der darüberliegenden Ebene gewählten Kette und der verbleibenden Restlänge ist.

Geht also in Richtung Kombinatorik.

Anschließend kann man natürlich die Summanden innerhalb einer Kette aufsummieren (oder - was da gleiche ist - die Kettenlänge mit 3 multiplizieren), also 6 + 3 + 3 statt (3 + 3) + (3) + (3). Und außerdem kann man noch aufeinanderfolgende Ketten gleicher Länge zusammenfassen, also 6 + 2*3 statt 6 + 3 + 3.

herbivore

H
hier0 Themenstarter:in
5 Beiträge seit 2011
vor 13 Jahren

Hallo herbivore

Dein Vorschlag klingt gut, ich werde mich mal dransetzten, auch wenn ich noch nicht wirklich weiss ich es progammiertechnisch umsetzen kann 😕

Vielen Dank dafür

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo hier0,

das kann man - 1:1 wie ich es beschrieben habe - in ca. 20 Zeilen runterprogrammieren. 😃 Zumindest wenn einem Rekursion was sagt.

herbivore

H
116 Beiträge seit 2008
vor 13 Jahren

Moin!

Also wenn es nur um mögliche Vertragslaufzeiten geht, würde ich mich nicht mit einer mathematischen Lösung beschäftigen, sondern die ganze Problematik über mehr oder weniger simple Listen lösen.

Dann kann ich die verschiedenen Laufzeiten und deren Kombinationen auch später ändern und beispielsweise auch nachträglich 48 Monate ermöglichen, ohne im Source wühlen zu müssen.

Hinrich