# Array in Rekursion



## drpingoo (25. November 2008)

Hallo zusammen,

Ich hab da ne Frage. Ist es möglich die Inhalte eines Arrays, das ein Übergabeparameter ist und dessen Funktion rekursiv aufgerufen werden soll, um eine Adresse weiter nach oben bzw nach unten zu verschieben? 

lg


----------



## devDevil (25. November 2008)

was hast du genau vor? Hört sich irgendwie nach ner Referenz eines Zeigers (o. eiger auf Zeiger) an, was du da machen willst, aber kann deiner Schilderung nicht ganu folgen, sorry.


----------



## 3Cyb3r (25. November 2008)

Ja fallfs du noch Platz im Array hast nach oben und unten ansonsten nein oder viel spass beim zerschießen deines Arbeitsspeichers.


----------



## drpingoo (25. November 2008)

Es geht darum ein Puzzle, wenn man das so nennen kann, rekursiv zu programmieren. Das erste Element des übergebenen Arrays ist die jeweilig Summe die erreicht werden soll. Falls dies möglich ist, sollte true oder so was ähnliches zurückgegeben werden, ansonsten false.  Also beispielsweise ./puzzle 34 1 2 3 4
34=1+2+3+4(überprüfen)
34=12+3+4
34=12+34 etc.

Und was ich machen wollte war folgendes: summe(int sum, int liste[], int länge)
Und ich wollte es so rekursiv verändern (es gibt noch einen Schritt, aber zunächst den), dass liste[1]*10+liste[2] den ersten Platz der liste[] belegt, das Element an liste[2] gelöscht/überschrieben wird, und die länge um 1 gekürzt wird. Also ich würde gerne den Rest des Arrays um eine Stelle raufschieben. Geht das überhaupt?


----------



## Ritchie_Fomm (26. November 2008)

Hallo, 

ich bin mir nicht sicher ob ich dich richtig verstanden habe. Das hört sich an als wolltest du einfach nur ein Element eifügen statt draufzupacken. Wenn das so ist, allociere dir ein neues Array von der Größe des alten bzw. Größe -1. Schreibe das erste Element rein und kopiere den Rest aus dem anderen Array per Memorymethoden (memcpy, memmove etc. ) da rein. 

Grüße
R.


----------



## deepthroat (26. November 2008)

Hi.





drpingoo hat gesagt.:


> Es geht darum ein Puzzle, wenn man das so nennen kann, rekursiv zu programmieren. Das erste Element des übergebenen Arrays ist die jeweilig Summe die erreicht werden soll. Falls dies möglich ist, sollte true oder so was ähnliches zurückgegeben werden, ansonsten false.  Also beispielsweise ./puzzle 34 1 2 3 4
> 34=1+2+3+4(überprüfen)
> 34=12+3+4
> 34=12+34 etc.
> ...


Falls ich dich richtig verstanden habe, könntest du das z.B. so machen:

```
int summe(int sum, int liste[], int laenge) {
  if (laenge > 1) {
    // Berechnung durchführen... 
    ...
    liste[1] = liste[0]*10 + liste[1]; // das erste Element hat Index 0!
    summe(sum, liste + 1, laenge - 1);
  } else {
     return ...
  }
}
```
Gruß


----------



## drpingoo (26. November 2008)

Ich glaube, deepthroat denkt in die richtige Richtung. Das erste Element in der Liste ist eben die Summe, die erreicht werden sollte. Die sollte eigtl gleich bleiben. Deswegen habe ich das geschrieben: 





> liste[1]*10+liste[2] ]



Aber ich glaube, es besteht auch noch folgendes Problem.
Sagen wir, wir haetten diese Eingangssequenz: 14 2 3 5.
14 ist also die Summe, die erreicht werden muss. Im ersten Fall versuche ich 14=2+3+5. Das schlaegt fehl. Also weiter. 14=23+5. Und ich glaube eben genau hier liegt noch ein Problem. Die 3 sollte durch die 5 ersetzt und das Array um eine Einheit gekuerzt werden. Wie kriege ich die weg?

lg


----------



## deepthroat (26. November 2008)

drpingoo hat gesagt.:


> Ich glaube, deepthroat denkt in die richtige Richtung. Das erste Element in der Liste ist eben die Summe, die erreicht werden sollte. Die sollte eigtl gleich bleiben.


Wozu dann der erste Parameter bei der Funktion?


drpingoo hat gesagt.:


> Aber ich glaube, es besteht auch noch folgendes Problem.
> Sagen wir, wir haetten diese Eingangssequenz: 14 2 3 5.
> 14 ist also die Summe, die erreicht werden muss. Im ersten Fall versuche ich 14=2+3+5. Das schlaegt fehl. Also weiter. 14=23+5. Und ich glaube eben genau hier liegt noch ein Problem. Die 3 sollte durch die 5 ersetzt und das Array um eine Einheit gekuerzt werden. Wie kriege ich die weg?


Indem du einfach die Länge um eins dekrementierst.

Irgendwie ist mir aber auch noch nicht klar, was du da überhaupt machen willst. Kannst du das mal richtig erkären? Wie sind bei diesem Puzzle die Regeln?

Gruß


----------



## drpingoo (26. November 2008)

Ja stimmt, der erste Parameter erübrigt sich eigtl, da man ihn auch durch liste[0] ausdrücken kann.

Ok, ich versuchs nochmal zu erklären. Es ist eigtl kein Puzzle, die Aufgabe heisst einfach so. Das Programm erhält eine Eingangsseqenz, deren vorderstes Element die Zahl ist, die aus Kombinationen der restlichen Elemente zusammengesetzt werden sollte. Man kann alle Zahlen einzeln addieren oder sie auch zusammennehmen.



> /puzzle 34 1 2 3 4
> 34=1+2+3+4(überprüfen)
> 34=12+3+4
> 34=12+34 etc.



Wichtig ist, dass die Zahlen nicht vertauscht werden dürfen, die Reihenfolge muss gleich bleiben. Lediglich die + ändern sich bzw ihre Position, wenn man so will. Verstehst du die Aufgabenstellung so?

lg


----------



## Mizi Mace (27. November 2008)

Einen wunderschönen guten Tag,

wenn ich das richtig verstanden habe, hast du ein Array mit Zahlen. Die erste Zahl ist gewünschte Summe. Alle weiteren Zahlen stellen Ziffern möglicher Summanden dar. Um dein Beispiel aufzugreifen:


Das Programm erhält die Zahlenfolge: 34 1 2 3 4
Die gewünschte Summe ist: 34
Diese soll aus Zahlen mit den Ziffern 1, 2, 3 und 4 gebildet werden, wobei diese Reinfolge eingehalten werden muss und keine Zahl doppelt vorkommen darf.
Möglich Summanden sind somit: 1, 2, 3, 4, 12, 23, 34, 123, 234 und 1234
Das Programm überprüft rekursiv, ob die Summe mit den möglichen Summanden gebildet werden kann, also: 
34 == 1 + 2 + 3 + 4
34 == 1 + 2 + 34
34 == 1 + 23 + 4
34 == 1 + 234
34 == 12 + 3 + 4
34 == 12 + 34
34 == 123 + 4
34 == 1234


Ist das so korrekt?

Gruss
Mizi


----------



## drpingoo (27. November 2008)

Ja, genau


----------



## Mizi Mace (28. November 2008)

Einen wunderschönen guten Morgen,

damit hast du einen Variantenbaum, dessen Blätter mögliche Additionsbildungen sind. Dein Lösungsvorschlag ist nur bedingt geeignet den gesamten Baum zu durchsuchen. Durch das Zusammenschieben erhälst du z.B. die Addition _1 + 234_. Später müsstest du z.B. _123 + 4_ berechnen, was bedeutet, dass du deine zusammengeschobenen Ziffern wieder auseinandernimmst.

Du solltest vielleicht eher eine Lösung suchen, die diesen Variantenbaum (rekursiv) berechnet. Ich hab für dein Beispiel mal einen solchen Baum aufgezeichnet:

Beispielbaum

Dabei bedeuet eine unterstrichene Ziffer, dass die nächste angehängt wird (mathematisch: Konketation). Das Ergebnis jedes Pfades ist unter den Blättern dargestellt. Die  letzteZiffer (4) wird dabei nicht gebraucht, da deren Verhaltensweise durch die vorhergehende Ziffer (3) bestimmt wird.

Gruss
Mizi


----------



## drpingoo (28. November 2008)

Ah ok, das hoert sich nach Pointern und structs an. ich werds dann mal so versuchen - danke


----------



## drpingoo (29. November 2008)

Also ich hab da mal was neues programmiert. Leider konnte ich es nicht ausprobieren und weiss deshalb nicht, obs läuft. Ich benutze Microsoft Viusal C++ 2008 Express Edition und weiss da nicht, wo ich die Übergabeparameter für das main() mitgeben soll. Ich habs dann noch mit cygwin versucht, der aber beim kompilieren bereits Fehler ausgab, die Visual mir nicht angezeigt hat, und ich finde die Fehleranzeige auch nicht gerechtfertigt.  Auch die Hilfe brachte nicht viel, vermutlich weil ich nicht weiss, wie der Fachbegriff dafür lautet. Ich häng das Programm aber trotzdem mal an, vllt kann mir jemand von euch sagen, ob das funktionieren würde oder wie ich das bei Visual hinbekomme.


```
#include <iostream>
using namespace std;

struct zahlen{
	zahlen *next;
	int value;};

	zahlen *first = NULL;
	int sum;
	int s = 0;

	int summe(int liste[], int index, int laenge){
	
		if(first==NULL){
			first = new zahlen;
			first->value = liste[index];
		}
		else{
			zahlen *z = first;
			first = new zahlen;
			first->value=liste[index];
			first->next=z;
		}

		s=s+first->value;
		if(s==sum){
			return s;
		}
			
		else if(laenge!=0){

			return summe(liste,index+1,laenge-1);
			}
		else if(laenge==0){
			return 0;}
		else{
			liste[index]=liste[index]*10;
			return summe(liste,index+1,laenge-1);}
	}


int main(int argc, char* argv[]){
	/*if(argc<2){
		cout << "zu wenig Argumente" << endl;
		return 0;}*/
	
	
	int *arr = new int [argc-1];
	/*if(argc>1){
		arr[1+argc];}*/
	
	for(int i=2;i<argc;i++){

		arr[i]=atoi(argv[i]);
	}

	sum = atoi(argv[1]);
	summe(arr,2,argc-2);


	return 0;
}
```


----------



## deepthroat (1. Dezember 2008)

Hi.

Seit wann verwendet man denn Umlaute in Bezeichnern?

Gruß


----------



## drpingoo (1. Dezember 2008)

Hallo,

bei Visual was das eigtl nie ein Problem, aber kann schon sein, dass der cygwin-Compiler damit Probleme hat. Bin jetzt leider grad nicht an meinem Computer, wo ich den draufhab. Aber ich versuchs dann nochmal, indem ich länge durch laenge oder so ersetze


----------



## Mizi Mace (2. Dezember 2008)

Einen wunderschönen guten Morgen,

ob deine vorgeschlagene Lösung funktioniert, kann ich leider nicht schreiben, da ich im Moment keine Zeit habe diese auszuprobieren. Ich denke dur wirst das noch machen und uns Bescheid geben.

Ich selbst hätte keinen Ersetzdatentyp in Form einer Liste verwendet, sondern die Liste selbst verwendet. Wenn du dir die entstandenen Additionsterme anschaust wirst du feststellen, dass diese folgende Form annehmen (für dein Beispiel):

1*10^e1 + 2*10^e2 + 3*10^e3 + 4*10^e4​0<=e1<=3​0<=e2<=2​0<=e3<=1​0<=e4<=0​
Somit kann eine Funktion kreiert werden, die diese Information nutzt. Zuerst wird im linken Pfad abgestiegen, da hier keine Veränderung der Exponenten vorkommt und anschließend im rechten mit den entsprechenden Änderungen. Die Funktion selbst gibt den Erfolg der Suche zurück. Hier das ganze mal schematisch:


```
bool summe(int summe, int liste[]; int laenge) {
  bool gefunden;

  if(laenge == 0) {        // beim letzten Element angekommen
    addiere Listenelemente;
    vergleiche mit summe;
    gib ergebnis des Vergleichs zurück;
  }
  else {        // noch nicht beim letzten Element angekommen
    gefunden = summe(int summe, int liste[]; int laenge-1); {        // Aufruf ohne Veränderung
    if(gefunden)
      return 1;        // bei Erfolg wird dies bis zur Wurzel weitergeleitet
    verändere Listenelemente entsprechend der Baumsyntax;
    gefunden = summe(summe; liste[]; laenge-1);        // Aufruf mit veränderter Liste
    return gefunden;
}
```

So in der Art könnte eine rekursive Lösung aussehen. Der komplizierte Teil dabei ist, die Veränderung der Listenelemente. Eventuell solltest du in der Funktion nur mit einer Kopie der Liste arbeiten und diese selbst als konstant übergeben, damit diese nicht ungewünscht verändert wird. Wenn du die Lösung selbst brauchst, kannst du diese noch in einen Parameter übertragen. 

Gruss
Mizi


----------



## drpingoo (6. Dezember 2008)

Guten Abend,

Also das einfache Plusrechnen funktioniert, aber sobald ich Glieder verknüpfen will, versagt es. Muss wohl nochmals über die Bücher. Auch der next-Pointer macht in meinen Augen nicht mehr so Sinn, viel besser wäre wohl etwas wie zahlen *right und zahlen *left.

Kurze Frage noch. Ich hab in meinem Code (der noch in Bearbeitung ist) einige cout-Abfragen reingenommen, umzu gucken, wo der Fehler liegt. Meine Frage nun, ich hab ja ein return 0 drin, wenn die Länge 0 ist. Komischerweise springt er dann ganz aus dem Programm raus. Müsste es nicht so sein, dass er den letzten Funktionenaufruf "schliesst" und dann weiter zum else gehen muss? Ich bin da grad ein bisschen verwirrt und nicht mehr sicher. Ich dachte das würde funktionieren. Aber wenn man bedenkt, dass es bei return s auch ganz aufhört...?

lg


----------



## Mizi Mace (8. Dezember 2008)

Einen wunderschönen guten Morgen,

beim Verknüpfen multiplizierst du immer den Wert am aktuellen Index mit 10. Betrachten wir nun das Beispiel:

sum = 123 + 4

Die 1 wurde schon im vorherigen Schritt mit 10 multipliziert, die 2 im aktuellen Schritt. Nun muss aber auch die 1 nochmal mit 10 multipliziert werden. Zum Ende wird noch die 3 angehängt. Geschieht dies nicht so, wird folgende Summe gebildet:

sum = 10 + 20 + 3 + 4

Dies ist natürlich nicht das Ziel. Betrachten wir nun ein anderes Beispiel:

sum = 12 + 34

Dann muss zunächst die 10 mit 10 multipliziert werden und später die 3. Es ergibt sich somit folgende Addition:

sum = 10 + 2 + 30 + 4

Dabei dürfen die vorherigen Zahlen nicht mit 10 multipliziert werden, ansonsten erhalten wir die Addition:

sum = 1000 + 200 + 30 + 4

Diese ist zwar auch legitim, wird aber schon anderweitig überprüft.

Gruss
Mizi


----------

