4. Rekutrsionsaufgabe

Rekutrsionsaufgabe

  • M

    Moin, ich habe eine Rekursionsaufgabe bei der ich leider nicht weiter komme und etwas Hilfe gebrauchen könnte:

    Ich habe eine Auswahl an Elementen mit einer bestimmten Höhe und Grundfläche in einem struct array. Meine Aufgabe ist es nun aus einer Kombination von Elementen ( es können auch mehrfach die gleichen sein) ein Stapel zu konstruieren, der nicht höher als 10 ist und die minimale Grundfläche hat.
    ich will dann die Lösung ausgeben, mein Programm findet zwar alle Lösungen, ich weis aber nicht genau, wie ich die beste Lösung finde?

    #include <stdio.h>
#define H 10
#define N 5
#define MAX(A,B) (A) > (B) ? (A) : (B)

struct rect{
	int h;
	int b;
} sammlung[] = {{2,3},{9,1},{4,2},{6,1}};

int find(int h, int max){

	if(h <= H){

		if( h == H ){
			printf("%d, %d\n",h,max);
		}
		for( int i = 0; i < N; i++){
			if(find(h+sammlung[i].h, MAX(max,sammlung[i].b))){ 
				return 1;
			}
		}
	}
	else return 0;
}

int main(){

find(0,0);

return 0;
}

    Wenn Jemand ein Tipp hat würde es mich sehr freuen 😃

    LG Max

    0
  • Mod

    Mir ist aus deiner Beschreibung nicht klar, wie so ein Stapel gebaut wird. Kannst du bitte die Regeln nochmals erläutern, oder besser noch, einfach direkt die Aufgabenstellung wiedergeben?

    0
  • M

    Die Aufgabe verlangt das so, ich habe leider keine schriftliche Aufgabe sondern nur das Konzept der Aufgabe:

    Es soll ein Turm aus Blöcken gebaut werden die eine höhe und eine Grundfläche haben ( hier sind die halt als struct gespeichert), der Turm soll jetzt eine bestimmte höhe nicht überschreiten. und man soll die Kombination an Blöcken wählen, die die minimale Grundfläche haben.

    Ich hoffe das bringt etwas mehr licht rein

    0
  • Mod

    Maximiliandio schrieb:

    Ich hoffe das bringt etwas mehr licht rein

    Nein, überhaupt nicht. Versetz dich mal in die Rolle von jemanden, der nicht bei euch im Unterricht war. Wie soll so jemand anhand deiner Beschreibung verstehen, was gemeint war?

    0
  • W

    Wenn die Aufgabe so ungenau ist, wähle doch einfach die Kombination aus genau 1 Turmstück, das die kleinste Grundfläche hat (sofern dieses eine Stück nicht schon die maximale Höhe überschreitet).

    Oder müssen immer mindestens 2 Blöcke gewählt werden?

    Schritt 1 zur Lösung einer Aufgabe ist es, diese mit all ihren Anforderungen genau zu verstehen. Beispiele können ggf. hilfreich sein.

    0
  • M

    OK anscheinend ist das so wie das Rucksackproblem. Man soll aber auf 2 sachen optimieren:

    Beispiel:
    es gibt 4 Klötze mit Höhe und Fläche {h,F} : {2,1},{2,3},{3,2},{3,1} und die maximale Höhe sei 5

    dann wären die Kombination aus Klötzen, die die maximale Höhe 5 erreichen {2,1} und {3,2} Oder {2,1} und {3,1} Oder {2,3} und {3,2} Oder {2,3} und {3,1}

    Davon hat die kleinste Grundfläche die Kombination {2,1} und {3,1} und ich will zeigen dass diese Kombination das Problem löst.

    ich hoffe das hilt jetzt 😛

    LG

    Ich ahbe mein Code noch einmal verändert mit dem Wissen, dass es ähnlich zu Rucksackproblem ist, jedoch habe ich keine Ahnung wie ich die Bedingung mit der geringen fläche implementieren soll:

    #include <stdio.h>
#define H 10
#define N 6
#define MAX(A,B) (A) > (B) ? (A) : (B)
#define MIN(A,B) (A) < (B) ? (A) : (B)

struct rect{
	int h;
	int A;
} sammlung[] = {{9,1},{5,2},{7,1},{3,3},{2,2},{2,3}};

int turm( int h_current , int i ){
	if( i < N){

		int h1 = turm( h_current , i+1);

		int h2 = 0;
		if( h_current + sammlung[i].h <= H){
			h2 = sammlung[i].h + turm(h_current + sammlung[i].h, i+1);
		}
		if( h1 > h2 ) return h1;
		if( h1 < h2 ) return h2;
		if( h1 == h2 ){ } // rückgabe mit geringerer Fläche
	}
	return 0;
}
int main(){

printf("%d",turm(0,0));
return 0;
}
    0
  • W

    Man soll aber auf 2 sachen optimieren:

    Warum nennst du dann keine und bringst stattdessen ein Beispiel?

    Sorry, bitte genauer!

    Oben schreibst du noch "ein Stapel zu konstruieren, der nicht höher als 10 ist", jetzt soll man "die maximale Höhe 5 erreichen". Was denn nun? Muss man die Höhe erreichen oder muss man <= sein?

    Was ist, wenn man Höhe 10 hat, die Elemente aber (7 hoch, 1 breit) und (8 hoch, 2 breit) sind? Dann ist der eine dichter an der max Höhe, der andere schmaler.

    Du musst das Problem vollständig definieren.

    0
  • M

    OK also die HÖhe soll nur ein Beispiel sein sie kann auch 10000 sein, aber darum geht es nicht. Die höhe muss man nicht erreichen , sonder soll nur so nahe wie möglich dran kommen, das ist die wichtigste Priorität. und wenn man jetzt mehrere Kombinationen hat, die die gleiche maximale Höhe haben, dann soll die Kombination ausgewählt werden, die die geringste Fläche hat.

    0
  • H

    Davon hat die kleinste Grundfläche die Kombination {2,1} und {3,1} und ich will zeigen dass diese Kombination das Problem löst.

    Wenn diese Kombination aus deinem Beispiel die kleinste Grundfläche hast, wie erreichst Du denn dann die Höhe von einem Turm, die fehlt doch. Du bäuchtest doch länge Breite(Grundfläche halt) sowie die Höhe???? 🙄

    0
Anmelden zum Antworten