Vorzeichenkombinationen < Folgen+Grenzwerte < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:22 Do 24.01.2013 | | Autor: | bronko |
Hallo,
ich habe mal eine Frage:
Ich habe eine beliebige Anzahl an positiven Zahlen und möchte nun den kleinsten Wert von dem Betrag, der Summe aller Vorzeichenkombinationen ermitteln, ohne die Summe aller Vorzeichenkombinationen berechnen zu müssen.
Hier ein Beispiel für die Zahlen 10, 8, 4:
abs(10+8+4)=22
abs(10+8-4)=14
abs(10-8+4)=6
abs(10-8-4)=2
Ergebins = 2
Wie komme ich auf die 2, ohne alles ausrechnen zu müssen?
Meine Idee ist, alle Zahlen der Größe nach zu sortieren und dann immer die größte minus die zweitgrößte Zahl zu rechnen. Danach wieder der Größe nach, absteigend sortieren, usw.
Also:
10-8=2 (übrige Zahlen: 8, 4, 2)
8-4=4 (übrige Zahlen: 4, 2)
4-2=2 -> Ergebnis = 2
Funktioniert das immer so und kann man das beweisen?
Vielen Dank für Eure Hilfe!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:06 Do 24.01.2013 | | Autor: | Teufel |
Hi!
Dein Algorithmus klappt, glaube ich, nicht für Eingaben wie (1, 1, 1). Oder wie würde er da lauten?
Aber ich glaube auch, dass das Problem schwierig ist (in etwa NP-vollständig von der Härte her), d.h. ich glaube nicht, dass es da überhaupt einen schnellen Algorithmus für gibt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:14 Do 24.01.2013 | | Autor: | bronko |
Hallo,
bei 1, 1, 1 würde das so aussehen:
1-1=0 (bleibt 1, 0)
1-0=1 -> Ergbnis = 1
müsste passen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:39 Do 24.01.2013 | | Autor: | Teufel |
Hm ok, und wenn du nur (1,1) als Eingabe hast? Dann hast du ja auch
1-1=0
1-0=1, obwohl 0 als Lösung rauskommen müsste.
Oder wenn du 10 und 6 hast.
Dann würde das doch so gehen:
Übrig: 10, 6
10-6=4
Übrig: 6, 4
6-4=2
Übrig: 4,2
4-2=0
Übrig: 2, aber 2 passt ja nicht.
Kann aber auch sein, dass ich deinen Algorithmus nicht richtig anwende. Formulier ihn in diesem Fall am besten mal ganz exakt!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:37 Do 24.01.2013 | | Autor: | bronko |
Mein Problem ist, dass es sehr schnell ziemlich rechenintensiv wird, wenn ich alle Kombinationen berechnen muss: 2^(n-1) Berechnungen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:39 Do 24.01.2013 | | Autor: | reverend |
Hallo nochmal,
es geht kürzer. Schau mal weiter unten.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:47 Fr 25.01.2013 | | Autor: | Teufel |
Hi!
Ja, etwas Polynomielles wirst du vermutlich allerdings nicht bekommen können (außer wenn P=NP, wovon man aber nicht ausgeht). Was ich dir noch anbieten könnte, wäre ein pseudopolynomieller Algorithmus.
Angenommen, [mm] S=\{a_1, ..., a_n\} [/mm] sei die Eingabe und [mm] d_{min} [/mm] sei das Minimum, das du berechnen willst. Dann würde für [mm] S'=\{a_1, ..., a_n, d_{min}\} [/mm] ja 0 rauskommen, d.h. du könntest S' in 2 gleich große Teile zerlegen, wie ich schon weiter unten geschrieben habe (![[]](/images/popup.gif) PARTITION-Problem).
Für besagtes Problem gibt es einen Algorithmus, der recht schnell läuft, wenn die Eingabewerte nicht all zu groß sind.
Was du nun machen könntest, ist Folgendes: Teste einfach alle Werte von [mm] d_{min} [/mm] angefangen bei 0 der Reihe nach durch und lasse den Partition-Algorithmus jeweils auf [mm] S'=\{a_1, ..., a_n, d_{min}\} [/mm] laufen. Wenn der Algorithmus meldet, dass es keine Zerlegung in 2 gleich große Teilsummen gibt, erhöhe [mm] d_{min} [/mm] um 1. Irgendwann hast du den richtigen Wert für [mm] d_{min} [/mm] und genau dann liefert der Partitionsalgorithmus ein positives Ergebnis.
Alternativ könntest du mit [mm] d_{min}=\summe_{i=1}^{n}a_i [/mm] anfangen und dich dann mit binärer Suche an den wahren, gesuchten Wert herantasten.
Der Algorithmus läuft zwar schneller als Brute-Force, aber vermutlich ist es anstrengender das von Hand auszuführen (Tabelle malen etc). Für kleine Eingabelängen (n klein) würde ich daher einfach alle Vorzeichen einigermaßen geschickt durchprobieren.
Ich hoffe, dass dir das trotzdem helfen konnte. Bei Fragen, einfach nochmal melden!
|
|
|
| |
|
Hallo Bronko,
wie entwickelt man einen Algorithmus?
Am besten ist, man fängt einfach vorn an. Wenn der Algorithmus für zwei Werte ein richtiges Ergebnis ausgibt, ist das ein guter Anfang und unbedingt nötig. Erst dann lohnt es sich, einen dritten Weg hinzuzunehmen.
Oft hat man allerdings gerade für den ersten Schritt viele Möglichkeiten. Die muss man dann in den nächsten Schritten ausdünnen, aber meistens braucht man nicht mehr als sagen wir 3 bis 6 dazu.
Hier ist der Ansatz doch einfach.
Wir haben zwei beliebige Zahlen [mm] a_1,a_2\in\IR.
[/mm]
Wenn Du nur natürliche Zahlen hast oder ganze oder rationale, sind die ja mit inbegriffen. Trotzdem sollte man sicherheitshalber nachprüfen, ob die (jetzt noch zu findende) Lösung dann auch zutrifft.
Wenn der minimale "Abstand" [mm] d_{min} [/mm] zweier Zahlen positiv definiert ist, dann wäre der naheliegendste Ansatz für [mm] a_1,a_2 [/mm] doch dieser:
[mm] d_{min,1}=||a_1|-|a_2||
[/mm]
Soweit, so gut. Nun kommt eine dritte Zahl [mm] a_3 [/mm] hinzu. Vorschlag:
[mm] d_{min,2}=||d_{min,1}|-|a_3||
[/mm]
Die Betragsstriche um [mm] d_{min,1} [/mm] sind verzichtbar. Wir wissen ja schon, dass das nicht negativ sein kann.
So kann man nun einfach weitermachen: [mm] d_{min,k}=||d_{min,k-1}|-|a_{k+1}||
[/mm]
Es sollte Dir auch nicht schwerfallen, das zu beweisen.
Deine letzte Frage (Thema Laufzeit) stelle ich mal auf beantwortet.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:07 Fr 25.01.2013 | | Autor: | Teufel |
Hi!
Der Algorithmus sieht sehr plausibel aus! Aber ich konnte ihn austricksen. Probiere mal [9, 8, 4, 3, 2].
Möglich wäre 9-8+4-3-2=0. Der Algorithmus liefert aber
[mm] d_{min, 1}=|9-8|=1
[/mm]
[mm] d_{min, 2}=|1-4|=3
[/mm]
[mm] d_{min, 3}=|3-3|=0
[/mm]
[mm] d_{min, 4}=|0-2|=2.
[/mm]
Es kann natürlich eine geeignete Eingabereihenfolge für die Elemente geben, aber diese zu finden erzeugt auch einen Aufwand von n!.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:16 Fr 25.01.2013 | | Autor: | reverend |
Oha.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:25 Fr 25.01.2013 | | Autor: | Teufel |
Das Problem dabei ist Folgendes: Wenn man einen Algorithmus hat, der in Polynomialzeit (n-1 wäre hier super) läuft und dieses Problem löst, dann könnte man diesen z.B. nutzen um zu schauen, ob eine Menge natürlicher Zahlen so in 2 Teilmengen partitioniert werden kann, die beide die gleiche Summe haben. Indem man einfach schaut, ob [mm] d_{min}=0 [/mm] ist.
Bei [9,4,5,3,2,1] wäre das der Fall, [mm] M_1=\{9,3\}, M_2=\{4,5,2,1\} [/mm] z.B. Dieses Problem ist das sogenannte PARTITION-Problem aus der theoretischen Informatik. Für dieses Problem gibt es *vermutlich* keinen effizienten Algorithmus, der es löst. Hätte dein Algorithmus in voller Allgemeinheit funktioniert, dann hättest du das sogenannte P-NP-Problem gelöst und wärst um eine Million Dollar reicher. :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:01 Fr 25.01.2013 | | Autor: | bronko |
Vielen Dank für Eure Beiträge.
Meine Idee war, die Zahlen nach jeder Subtraktion der Größe nach zu sortieren. Für die Zahlen [9,4,5,3,2,1] ergbit sich:
9-5=4 (bleibt: 4, 4, 3, 2, 1)
4-4=0 (bleibt: 3, 2, 1, 0)
3-2=1 (bleibt: 1, 1, 0)
1-1=0 (bleibt: 0, 0)
0-0=0
Ich bin kein Mathematiker und habe noch nie von Dingen wie P-NP-Problem oder NP-Vollständig gehört, darum bin ich mir nicht sicher, ob das immer so funktioniert.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:45 Fr 25.01.2013 | | Autor: | bronko |
Also ich kann irgendwie keine Zahlekombination finden, bei der es nicht funktioniert? Was meint Ihr?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:59 Fr 25.01.2013 | | Autor: | Teufel |
Hi!
Nein, der Algorithmus klappt leider auch nicht immer.
Nimm mal $[9,7,6,5,5]$. Es sollte 0 rauskommen, wegen 9+7-6-5-5=0.
Der Algorithmus macht aber folgendes:
9 7 6 5 5, 9-7=2
6 5 5 2, 6-5=1
5 2 1, 5-2=3
3 1, 3-1=2
2
Um nochmal das ganze P-NP-Gerede zusammenzufassen: Es gibt so ein paar Problemstellungen, die man vermutlich nicht effizient beantworten kann, bei denen man also wohl nur probieren kann. z.B. das PARTITION-Problem, wo man eine gegebene Zahlenmenge in 2 Teilmengen aufteilen soll, sodass in beiden die gleiche Summe ist. Für [mm] \{1,2,3\} [/mm] wäre die Aufteilung [mm] \{3\} [/mm] und [mm] \{1,2\} [/mm] so eine Partition, die ok wäre. Die Menge [mm] \{1,1,4\} [/mm] besitzt aber keine solche Zerlegung. Das Problem sieht recht einfach aus, aber es ist kein schneller Weg bekannt, zu testen, ob man eine Menge so zerlegen kann.
Ein anderes ähnliches Beispiel ist das Subset-Sum-Problem. Gegeben eine Menge von Zahlen [mm] M=\{a_1, ..., a_n\} [/mm] und eine weitere Zahl S, gibt es dann eine Auswahl von Elementen aus M, die aufsummiert S ergeben?
z.B. [mm] M=\{2,5,7,9,10\} [/mm] und S=18. Hier würde es eine Lösung geben, nämlich 2+7+9. Aber auch bei diesem Problem gibt es keinen allgemein gültigen, schnellen Algorithmus, obwohl das Problem ja auch nicht so schwierig aussieht.
Dein Problem ist nun so ähnlich wie das Partition-Problem. Könnte man dein Problem schnell lösen (z.B. in n Schritten oder so etwas), so könnte man das besagte Partition-Problem ebenfalls schnell lösen, von dem man aber nicht glaubt, dass das geht. Also kann es (vermutlich) keinen vernünftigen Algorithmus für dein Problem geben. Soll also heißen, dass du nicht viel besser als durchprobieren werden kannst.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:22 Sa 26.01.2013 | | Autor: | bronko |
Vielen Dank für Deine Hilfe!
Jetzt weiß ich zumindest, dass es so nicht geht und brauch mir nicht mehr den Kopf darüber zerbrechen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:58 Sa 26.01.2013 | | Autor: | Teufel |
Ja, also probieren geht halt immer, wenn du nicht zu viele Zahlen hast. Als Mensch kann man ja auch durch "scharf hinsehen" manchmal eine Lösung erkennen. Wenn ich als Eingabe [mm] \{1,2,3,6,8,9,20\} [/mm] habe, dann werde ich wohl nicht alle Zahlen addieren, sonder werden ein paar Minuszeichen verteilen. Somit muss man als Mensch nicht stur alles durchprobieren.
Aber für größere Eingaben wird das schwierig. Da würde ich dann doch lieber einen Computer fragen.
|
|
|
|
