Array in Rekursion

[drpingoo]

Ja, genau

 

[Mizi Mace]

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]

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

 

[drpingoo]

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]

Hi.

Seit wann verwendet man denn Umlaute in Bezeichnern?

Gruß

 

[drpingoo]

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]

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]

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]

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