Dem Durchschnitt annähern

Für alles, was in den übrigen Lazarusthemen keinen Platz, aber mit Lazarus zutun hat.
Antworten
Fightfire
Beiträge: 1
Registriert: Di 26. Apr 2016, 17:59

Dem Durchschnitt annähern

Beitrag von Fightfire »

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. :cry:

Ich hoffe jemand kann einen guten Ansatz liefern.

Grüße Fightfire :wink:

Soner
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

Beitrag von Soner »

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):

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.

Frank Ranis
Beiträge: 201
Registriert: Do 24. Jan 2013, 21:22

Re: Dem Durchschnitt annähern

Beitrag von Frank Ranis »

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
www.flz-vortex.de

Warf
Beiträge: 1908
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Dem Durchschnitt annähern

Beitrag von Warf »

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. :cry:

Ich hoffe jemand kann einen guten Ansatz liefern.

Grüße Fightfire :wink:


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

Antworten