Heyho,
ich habe eine Informatik Hausaufgabe aufbekommen, die Aufgabe ist das man von mehreren eingegebenen Zahlen 5er "Teams" bildet die sich dem Durchschnitt großtmöglichst annähern - Natürlich muss die Eingabeoberfläche angenehm sein. Dabei sind die Zahlen im Bereich von 1 bis 27 (warum auch immer in diesen Zahlbereich )
Also ich erklär nochmal:
Erstmal muss man Zahlen eingeben können(Listbox), eine Zahl rausslöschen können und den Durchschnitt, die Gesamtanzahl und die Übriggebliebenen anzeigen. Außerdem halt das Zählen welche Zahl wie oft vertreten ist.
--> Soweit ist es ja noch einfach.
Nun wird schwerer und ich hab keinen Plan wie ich das machen soll.
Es sind die 14 Zahlen 2,3,6,9,6,10,25,6,2,6,7,8,20,9(Als Beispiel) eingegeben, Durchschnitt von 8,5, übrig 4 (dabei ist es zum Glück egal welche übrig sind), daraus kann man ja 2 5er-"Teams" erstellen, nur hab ich jetzt keine Ahnung wie man mit den gegebenen Zahlen die zwei, dem Durchschnitt von 8,5 am nähesten kommenden, "Teams" bilden soll.
Ich hoffe jemand kann einen guten Ansatz liefern.
Grüße Fightfire
Dem Durchschnitt annähern
-
- Beiträge: 623
- Registriert: Do 27. Sep 2012, 00:07
- OS, Lazarus, FPC: Win10Pro-64Bit, Immer letzte Lazarus Release mit SVN-Fixes
- CPU-Target: x86_64-win64
- Wohnort: Hamburg
Re: Dem Durchschnitt annähern
Heyho auch,
ich glaube das kann man mit Kombinatorik lösen.
Aus deinen 14 Zaheln kannst du 5er Kombinationen bilden, Durchschnitt rechnen und die beiden 5er Kombination, die dem Durchschnitt am besten nähern nehmen.
z.B. Bei 4 Zahlen kann man so 2er Kombinationen erstellen (Zahlen als BUchstaben dargestellt):
Das nennt sich "Auswahl von k Objekten aus einer Menge mit n Objekten ohne Beachtung von Reihenfolge und ohne zurücklegen".
Es gibt vielleicht andere Wege aber ich würde auf die schnelle so vorgehen, so mußte es auch richtig sein.
ich glaube das kann man mit Kombinatorik lösen.
Aus deinen 14 Zaheln kannst du 5er Kombinationen bilden, Durchschnitt rechnen und die beiden 5er Kombination, die dem Durchschnitt am besten nähern nehmen.
z.B. Bei 4 Zahlen kann man so 2er Kombinationen erstellen (Zahlen als BUchstaben dargestellt):
Code: Alles auswählen
a,b,c,d sind die Zahlen
1. Durchschnitt von a,b,c,d rechnen
2. Zweier Kombinationen davon bestimmen und Durchschnitt rechnen:
ab
ac
ad
bc
bd
cd
3. Vergleichen und die 2 geigneten Kombinationen nehmen.
Das nennt sich "Auswahl von k Objekten aus einer Menge mit n Objekten ohne Beachtung von Reihenfolge und ohne zurücklegen".
Es gibt vielleicht andere Wege aber ich würde auf die schnelle so vorgehen, so mußte es auch richtig sein.
-
- Beiträge: 201
- Registriert: Do 24. Jan 2013, 21:22
Re: Dem Durchschnitt annähern
Hallo Fightfire,
eventuell könne das funktionieren.
Lineare Regression
https://de.wikipedia.org/wiki/Lineare_Regression
Methode der kleinsten Quadrate
https://de.wikipedia.org/wiki/Methode_d ... n_Quadrate
Polynomial regression
https://en.wikipedia.org/wiki/Polynomial_regression
Curve fitting
https://en.wikipedia.org/wiki/Curve_fitting
Gruß
Frank
eventuell könne das funktionieren.
Lineare Regression
https://de.wikipedia.org/wiki/Lineare_Regression
Methode der kleinsten Quadrate
https://de.wikipedia.org/wiki/Methode_d ... n_Quadrate
Polynomial regression
https://en.wikipedia.org/wiki/Polynomial_regression
Curve fitting
https://en.wikipedia.org/wiki/Curve_fitting
Gruß
Frank
www.flz-vortex.de
-
- Beiträge: 1908
- Registriert: Di 23. Sep 2014, 17:46
- OS, Lazarus, FPC: Win10 | Linux
- CPU-Target: x86_64
Re: Dem Durchschnitt annähern
Fightfire hat geschrieben:Heyho,
ich habe eine Informatik Hausaufgabe aufbekommen, die Aufgabe ist das man von mehreren eingegebenen Zahlen 5er "Teams" bildet die sich dem Durchschnitt großtmöglichst annähern - Natürlich muss die Eingabeoberfläche angenehm sein. Dabei sind die Zahlen im Bereich von 1 bis 27 (warum auch immer in diesen Zahlbereich )
Also ich erklär nochmal:
Erstmal muss man Zahlen eingeben können(Listbox), eine Zahl rausslöschen können und den Durchschnitt, die Gesamtanzahl und die Übriggebliebenen anzeigen. Außerdem halt das Zählen welche Zahl wie oft vertreten ist.
--> Soweit ist es ja noch einfach.
Nun wird schwerer und ich hab keinen Plan wie ich das machen soll.
Es sind die 14 Zahlen 2,3,6,9,6,10,25,6,2,6,7,8,20,9(Als Beispiel) eingegeben, Durchschnitt von 8,5, übrig 4 (dabei ist es zum Glück egal welche übrig sind), daraus kann man ja 2 5er-"Teams" erstellen, nur hab ich jetzt keine Ahnung wie man mit den gegebenen Zahlen die zwei, dem Durchschnitt von 8,5 am nähesten kommenden, "Teams" bilden soll.
Ich hoffe jemand kann einen guten Ansatz liefern.
Grüße Fightfire
Dieses Problem müsste NP-Vollständig sein (eine Form vom Partition bzw SubSetSum Problem), und auch wenn es vielleicht nicht so aussieht, das bedeutet das es zu den Schwersten Problemen der Informatik gehört. Eine korrekte Lösung wäre (nach heutigem Forschungsstand) nur mit Trail & Error alles durchzuprobieren, so wie es Soner vorgeschlagen hat. Das Problem damit ist nur das es mit Exponentiellen Zeitaufwand eine herzlichst beschissene Lösung ist, da es bei großen Inputs ewig dauert. Mit Diversen Approximationsalgorithmen die das ganze in Polynomieller Zeit lösen allerdings nicht 100% korrekt sind. Beispiel zu einem Approximationsalgorithmus für SUBSETSUM: Link