Zerlegung in beliebige Summen < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:43 Mo 25.08.2014 | | Autor: | Cebalrai |
Hallo, in der Hoffnung hier das richtige Subforum erwischt zu haben, hier mein Problem:
Ich muss in C++ eine beliebige natürliche Zahl in beliebig viele Summanden (ebenfalls [mm] $\in\IN$) [/mm] zerlegen.
Die Ergebnisse sollen als [mm] $\texttt{vector>}$ [/mm] abgespeichert werden, wobei eben [mm] $\texttt{vector}$ [/mm] konkret eine solche Zerlegung wäre. Durch die verschiedenen Längen der Vektoren, die die einzelnen Zerlegungen mit sich bringen, hab ich keine Ahnung, wie ich das bewerkstelligen soll. Es scheint aber irgendwie eine Rekursion da reinzugehören.
Ganz am Ende soll eine Liste dabei rauskommen, die der Größe nach geordnet ist und doppelt auftretende Tupel eliminiert sind, z.B. für 10 dann eben:
9 1
8 2
8 1 1
7 3
7 2 1
7 1 1 1
etc.
Vielen Dank schon mal vorab ;)
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:51 Mo 25.08.2014 | | Autor: | Diophant |
Hallo,
deine Frage ist für meinen Geschmack aus zweierlei Hinsicht zu unkonkret:
- Welche Kenntnisse hast du hinsichtlich Programmmierung im Allgemeinen und C++ im Speziellen, insbesondere hinsichtlich Sortieralgorithmen und Zeigern?
- Welche algorithmischen Gedanken hast du dir schon gemacht?
Also ich persönlich wäre hier erst in dem Moment bereit, über mögliche Lösungen nachzudenken, wenn du auf die beiden oberen Punkte etwas näher eingehen köntest. Und selbst wenn sich ein Helfer/eine Helferin findet, der/die das nicht so eng sieht: so jemand würdest du es auch leichter machen, wenn a) dein Kenntnisstand bekannt und b) eigene Überlegungen von deiner Seite aus Überlegungen vorhanden wären.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:01 Mo 25.08.2014 | | Autor: | Cebalrai |
Nun ja, in Informatik hab ich eine Vorlesung gehabt, Numerisch noch ein paar weitere, und benötige i.d.R. auch Infokenntnisse nur für numerische Zwecke, wie man es als Phy-Student braucht.
Mit Pointern komm ich ganz gut klar, aber Verwirrung ist trotzdem immer mal gewährleistet. Zu den Zwecken, wozu ich C++ bisher so gebraucht habe, konnte man sich da aber auch vieles sparen - wie eben z.B. durch [mm] $\text{\texttt{vector}}$. [/mm] Von Algorithmik sonst hab ich keine Ahnung. Ich schätze, dass ich da auch etliche Tricks einfach nicht kenne, da ich sie nie gebraucht hab ....
Zu meinen Überlegungen:
Naja .... ich hab versucht die Problematik mithilfe von ein paar for-Schleifen, später auch einer while-Schleife irgendwie hinzukriegen, ohne dass ich [mm] $N^N$-Möglichkeiten [/mm] aufschreiben und sortieren muss. Woran das scheitert, ist die dynamische Länge der Vektoren, die meine Summanden repräsentieren, sodass man das nicht schön in Schleifen packen kann.
Dann hab ich versucht, da es micht irgendwie an Turm von Hanoi erinnert hat, mit Rekursionen da ranzugehen. Abgesehen von den Standardbeispielen für Übungsserien und Klausuren hab ich damit aber auch noch nicht hantiert, sodass ich absolut kein Gefühl dafür habe. Was bei meinen Ansätzen da oft das Problem war: bei einer Schleife mit Rekursion drin, die theoretisch hätte funktionieren können, konnte ich meine Ergebnisse nicht mehr sinnvoll abspeichern.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:25 Mo 25.08.2014 | | Autor: | felixf |
Moin!
Ich nehme mal an, dass die Zahlen in der Summe wie in deinem Beispiel absteigend (oder gleich) sein sollen, also $3 3 2 1 1$ ist in Ordnung, $3 2 3 1 1$ dagegen nicht.
Schreib doch eine Funktion, die folgendes bekommt:
* eine Referenz auf std::vector<std::vector<int>>;
* einen std::vector<int> (als Referenz oder als Value), der den Anfang einer Zahlenfolge darstellt;
* einen Wert $max$, so dass alle folgenden Werte in der Zahlenfolge [mm] $\le [/mm] max$ sein muessen;
* die Summe der verbleibenden Zahlen in der Folge.
Diese Funktion soll alle Folgen an die Ergebnisliste anhängen, die mit der gegebenen Teilfolge anfangen.
(Der Wert $max$ ist also das Minimum der Werte im std::vector<int> falls dieser nicht leer ist, und gleich dem letzten Parameter andernfalls.)
Wenn du diese Funktion implementiert hast (rekursiv!), musst du sie einmal richtig aufrufen, und schon erzeugt sie dir die komplette Liste.
LG Felix
|
|
|
|
