Rekursive Aufgabe (+Backtracking)

herda

Man kriegt eine Summe vorgegeben, z.B. 42. Jetzt soll man einen 9-stelligen rekursiv so ausfüllen, dass am Ende die richtige Summe rauskommt. Als math. Operatoren dürfen "+" und "-" genutzt werden und Ziffern 0-9.
Das ganze sieht also folgendermaßen aus:

Zahl1 +/- Zahl2 +/- Zahl3 +/- Zahl4 +/- Zahl5 = SUMME.

Eine Abbruchbedingung wäre, wenn man gerade die richtige Summe aller zahlen rauskriegt, dann würde ich return 1 ausgeben.

Wie soll ich jetzt die Aufgabe anpacken, dass man alle Möglichkeiten rekursiv ausprobiert. Dies war übrigens eine PG1 Kulturaufgabe...

SeppJ

Wozu so kompliziert? Addier solange 9en bis du weniger als 9 vom Ergebnis weg bist. Danach das addieren was bis zum Ergebnis fehlt. Den Rest Nullen. Das ist zwar iterativ, aber das kannst du auch als rekursiven Backtracking-Algorithmus formulieren. Der Algorithmus probiert dann immer erst eine 9 hinzuzufügen und wenn er über das Ergebnis hinausschießt, dann versucht er stattdessen eine 8 usw. Wenn er unter oder auf dem Ergebnis landet geht es weiter mit der nächsten Ziffer.

Bashar

SeppJ schrieb:

Das ist zwar iterativ

Wenn du Modulo iterativ nennst ...

Ich glaube, wir haben hier nicht die ganze Wahrheit gehört. Sind die Zahlen vielleicht vorgegeben? Oder müssen die Zahlen alle verschieden sein? Müssen es genau 5 sein?

herda

Woah, genial. Also 9 reinschreiben, schauen ob 9 < als die Summe ist. Dann von der Summe 9 substrahieren und zur nächsten Ziffer. Warum bin ich nicht selbst drauf gekommen Obwohl das geht nur, wenn man nur Addition benutzt. Zu beachten ist aber, dass sowohl "+" als auch "-" vorkommen kann. Die erschwert die Aufgabe.

herda

Bashar schrieb:

SeppJ schrieb:

Das ist zwar iterativ

Wenn du Modulo iterativ nennst ...

Ich glaube, wir haben hier nicht die ganze Wahrheit gehört. Sind die Zahlen vielleicht vorgegeben? Oder müssen die Zahlen alle verschieden sein? Müssen es genau 5 sein?

Ja, es müssen 5 sein, wobei 0 erlaubt ist. Die Zahlen sind NICHT vorgegeben, nur die Summe, z.B. 42. Es dürfen jedoch "+" oder auch "-" vorkommen. Also z.B. 1+2-3+4-5.

SeppJ

Aber es ist ebenfalls nicht vorgegeben, ob da + oder - steht. Das ist auch dir überlassen? Falls ja, dann ist die 9er-Addition tatsächlich eine gute Lösung.

Irgendwie glaube ich aber auch, dass du etwas vergessen hast. Das ist zu einfach.

Und selbst wenn vorgegeben ist, dass an einigen Stellen - stehen muss: Dann folgt da drauf eben immer eine 0.

herda

SeppJ schrieb:

Aber es ist ebenfalls nicht vorgegeben, ob da + oder - steht. Das ist auch dir überlassen? Falls ja, dann ist die 9er-Addition tatsächlich eine gute Lösung.

Irgendwie glaube ich aber auch, dass du etwas vergessen hast. Das ist zu einfach.

Und selbst wenn vorgegeben ist, dass an einigen Stellen - stehen muss: Dann folgt da drauf eben immer eine 0.

Ja, du kannst "+" oder "-" selbst festlegen. Aber ich glaube die "-" ist eh egal, du kommst ja auf jede Zahl mit nem "+".

ps. Vielleicht erscheint dir die Aufgabe einfach, aber als Klausuraufgabe zum ersten Semester Programmieren1 hat diese Aufgabe fast keiner gelöst, sodass sie gestrichen wurde.

herda

Ich habe die Aufgabe gelöst. Ich habe die Aufgabestellung erschwert, so dass Arrays beliebige ungerade Länge haben dürfen. Das Array darf leer sein, Voraussetzung ist die abschließende \0.

ps. Bei der Klausur sollte das Array Platz für 5 Ziffer haben. Klingt einfach, aber unter Zeitdruck den Code mit dem Stift auf dem Papier zu schreiben war nicht so einfach

int findSummands(char* Array, int Summe)
{
	char * p = Array;
	for (int i = 0;i<10;i++)				// 0-9 ausprobieren
	{
		if (i==Summe)				
		{
			*p=i+48;						//Wenns stimmt - reinschreiben

			while(*(p+1)!='\0')				//Ausfüllen des restlichen Arrays mit "+"en und 0en
			{
				*(p+1)='+';
				p=p+2;
				*p=0+48;
			}
			return 1;
		}  
	}

	if (*(p+1)=='\0')	return 0;

	*p=9+48;								// 9 reinschreiben
	*(p+1)='+';								// "+" reinschreiben

	if (*(p+1)!='\0')						//Solange das Array nicht zu Ende ist...
	{
		p=p+2;								//Neuen Anfang des Arrays festlegen
		return findSummands(p,Summe-9);		//Und mit der Summe-9 wieder aufrufen
	}
}

int main()
{
	char Array[]="          ";				//Ungerade Länge !!!
	int Summe = 42;

	if (findSummands(Array,Summe))
		cout << Array<<" = "<<Summe<<endl;
	else
		cout << "Keine Loesung fuer "<<Summe<<endl;

	system("pause");
	return 0;
}

Was für ein Dreckscode

cooky451

Kann mir mal jemand den Sinn hinter der Aufgabe erklären.
@herder
Sehr schönes C mit cout statt printf. Habt ihr denn gar keine Strings/Vektoren durchgenommen?

herda

cooky451 schrieb:

Kann mir mal jemand den Sinn hinter der Aufgabe erklären.
@herder
Sehr schönes C mit cout statt printf. Habt ihr denn gar keine Strings/Vektoren durchgenommen?

Deine Religion verbietet dir wohl ersten Beitrag durchzulesen.
Wir dürfen cin and cout verwenden, obwohl wir nur C gemacht haben. Im 2. Sem kamen erst Bit-Vektoren, Strings, OOP.

shitstorm schrieb:

Was für ein Dreckscode

Erstens sag mir was an dem Code unsauber ist und zeig mir wie man's besser schreibt. Wenn nicht - shut the fu*k up.
Und zweitens ist mir unklar was du mit der Aussage beweisen willst. Das du besser proggen kannst als die Erstsemestler? Geh noch ins Kindergarten und sag du kannst besser Mathe als die Kinder. Lachmichtot.

otze

nur skizziert:

void findSummands(int Summe)
{
    if(Summe != 0){
        int nummer = Summe > 9?9:Summe;//min(Summe,9) wenn erlaubt
        std::cout<<"+"<<nummer;//das durch beliebige stringfummelei ersetzen
        findSummands(Summe-nummer);
    }
}

und du solltest Trolle nicht füttern. Beachte den Namen. Und dir generell mal einen dickeren pelz zulegen. Dies ist das Internet.