Frage von BattleSheepGG, 54

Programmieraufgabe, 32 Personen sitzen im Kreis, jede 3. fliegt nach und nach raus bis zum ende?

Hi Leute,

Also wie gesagt ich komme nicht weiter bei folgender aufgabe.

In c++ soll ein Programm geschrieben werden...

Die Aufgaben stellung lautet: Es sitzen 32 Personen im Kreis, jede 3. fliegt bis zum ende raus. In welcher Reinfolge sind die Personen ausgeschieden?

Könnt ihr mir weiterhelfen?

Zu beachten ist halt das bereits ausgeschiedene Personen nicht erneut ausscheiden können.

Antwort
von PWolff, 25

Welche Möglichkeiten der Programmiersprache kennt ihr schon?

Bei uns waren "Abzählpermutationen" Beispiele und Übungen zu verketteten Listen.

Natürlich kann man das auch ohne verkettete Listen mit einfachen Arrays lösen, hier gibt es mehrere Möglichkeiten, je nachdem, ob man den Array verkleinern will oder einen Merker verwenden will, ob die betreffende Person schon ausgeschieden ist.

Also hierbei entweder

int person[n];
// person mit den Zahlen von 1 bis n füllen

void rausnehmen(int wo) {
n--;
for (i=wo; i<n; i++) {person[i] = person[i+1]};
};

oder

bool drin[n];
// alle Elemente von drin mit true initialisieren

int weiterzaehlen(int start, int wieweit) {
int wo = start;
for (i=0; i<wieweit; i++) {
wo++;
while(!drin[wo]) {
wo++;
if (wo>=n) {wo-=n};
};
};
return wo;
};

Ob die Syntax stimmt, weiß ich nicht, meine C-Erfahrungen liegen schon lange zurück.

Kommentar von PWolff ,

Hier ist noch mindestens ein Bug drin, findest du ihn?

Expertenantwort
von TeeTier, Community-Experte für programmieren, 12

Wie PWolff schon geschrieben hat, eignen sich dafür besonders gut Listen, aber ich habe (zugegeben aus Faulheit) einen Vektor eingesetzt:

#include <cstdlib>
#include <iostream>
#include <vector>

int main(void) {
using namespace std;

const size_t count = 32;
const size_t step = 3;

vector persons(count);
for (size_t i = 0; i < count; ++i) {
persons[i] = i + 1;
}

for (size_t add = step - 1, i = add; !persons.empty(); i+=add) {
size_t size = persons.size();

while (i >= size) {
i -= size;
}

cout << persons[i] << endl;
persons.erase(persons.begin() + i);
}

return EXIT_SUCCESS;
}

Dazu noch einige Gedanken:

1) Die Aufgabe ist schlecht bzw. mehrdeutig formuliert. Man weiß nicht, ob beim Abzählen bei Index 0 oder 2 (also bei der ersten oder bei der dritten Person) angefangen werden soll. Ich bin von letzterem Fall ausgegangen, weil das eher dem "natürlichen Empfinden" entspricht.

2) Der Code ist nicht sonderlich effektiv, da intern viele Verschiebungen im Vektor stattfinden.

3) Die zweite for-Schleife ist evtl. auf den ersten Blick schwer verständlich.

4) Warum wird wohl der Index in einer while-Schleife statt einer einfachen if-Bedingung überprüft? Kann i tatsächlich eine mehrfache Größe von size annehmen?

Ehrlich gesagt bin ich mit meinem Lösungsansatz überhaupt nicht zufrieden, und ich spüre, dass dort Fehler auftreten werden, wenn man die Anzahl der Personen, oder die Schrittweite auf ungünstige Werte ändert. Aber ich habe mich da jetzt nur ein oder zwei Minuten rangesetzt, also halb so wild.

Sind ja schließlich deine Hausaufgaben! :)

PS: Als idealen Lösungsansatz würde ich dir eine Zirkuläre Liste mit Prüfung auf Indexüberlauf empfehlen. Das dürfte eine ziemlich kompakte Klasse werden, in der man alles schön kapseln kann. Ich könnte mir vorstellen, dass dein Lehrer genau so etwas erwartet. :)

Antwort
von KnusperPudding, 54

Okay, und was hast du schon versucht?

Kommentar von BattleSheepGG ,
int
main(int
argc, char
*argv[])
{
 QCoreApplication a(argc, argv);
 int person[31];
 int i, j=1;
 int l=1;
 for(i=0;i<=31;i++)
 {
 person[i]=0;
 }
 for(i=0;i<=31;i++)
 {
 j++;
 if(j==3)
 {
 do
 {
 if(person[i]==0)
 {
 person[i]=l;
 l++;
 }
 else
 {
 i++;
 }
 }while(person[i]!=0);
 }
 }
 for(i=0;1<=31;i++)
 {
 cout<<person[i]<<", ";
 }
 return a.exec();
}
Kommentar von KnusperPudding ,

Freut mich zu hören, dass du es wirklich versucht hast. Allerdings hast du dich hierbei ein Stück weit verrechnet. 

Ein wichtiger Aspekt für einen Lösungsansatz dieser Aufgabenstellung bedeutet: Rekursion. - Dies bewerkstelligst du, indem du eine Methode erstellst, die sich mit anderen Parametern selbst aufrufst. - Bei deiner bisherigen Vorgehensweise hast du noch den ein oder anderen Käfer drin: Wenn du eine Schleife durchläufst und mit dem entsprechenden int wert einen Array-Wert abfragen möchtest: mach niemals <=  Verwenden, denn das führt zwangsläufig zum Fehler, da bei Arrays der Index mit 0 beginnt.

Sollte dir das bei der Lösung noch nicht geholfen haben, kannst du dich gerne nochmal erneut mit den Neu gewonnen Erkenntnissen melden und es gäbe dann den nächsten Tipp.

Kommentar von BattleSheepGG ,

Rekursion ist doch eine Selbstaufrufende Funktion oder?

Zu welchem Stichwort kann ich mich noch Schlau lesen um dem Ziel der Aufgabe ein Stück näher zu kommen?

PS: auch ohne das <= ändert sich nicht viel es kommt ein riesen durcheinander obwohl doch am ende nur 32 Zahlen ausgeben werden dürften, stehen bei mir mindestens 100.

Und keine Angst ich wollte mir die Lösung nicht erschleichen, und tut mir leid wenn es so rüber kam :D aber wie man sieht will ich es doch versuchen und habe auch schon seid gestern dran gearbeitet, nur stehe irgendwie echt auf dem schlauch.

Kommentar von KnusperPudding ,

Rekursive Funktionen sind selbstaufrufende Funktionen, richtig. 

Ich weiß nicht ob es hier explizite Seiten für sowas gibt, daher kann ich dir da keinen Rat geben, jedoch hat mich deine Testaufgabe doch gereizt und ich hab sie via Java gelöst (code ist fast identisch). Daher kann ich dir einen Tipp geben, der dich in die richtige Richtung schubst:

Zum einen: Du brauchst eine Methode, die als Rückgabewert eine int[] zurückliefert und ebenso auch eine int[] als Parameter besitzt so wie ein int Parameter. in den ersten gibst du deine ausgangsarray aus int[31] an, in den zweiten dein Intervall, die 3.

Damit du damit nun aber effektiv 'rekursiv' arbeiten kannst, muss unter bestimmten Bedingungen (und nur wenn diese erfüllt sind) die Methode sich selbst aufrufen.

Ein "Klassiker" hierbei wäre, wenn du überprüfst, ob du an der stelle in der Array einen Wert > 0 gesetzt hast. Mit dieser Bedingung würdest du die Rekursion beenden und eine reale Array zurück liefern.

Kommentar von PWolff ,

Bei dieser Art von Aufgabe halte ich Rekursion für deutlich komplizierter als Iteration.

Kommentar von KnusperPudding ,

Ich denke das ist subjektiv zu betrachten, ich finde den weg über die Rekursion leichter. - Aber es führen ja mehrere Wege nach Rom.

Kommentar von maximilianus7 ,

nochn tip: den programmcode besser auf http://pastie.org/ ablegen und hier verlinken

Kommentar von KnusperPudding ,

Stimmt, guter Tipp.

Kommentar von BattleSheepGG ,

Genau sowas habe ich gesucht und nicht Gefunden danke ^^

Nun weiter an der Aufgabe rum spielen. Wenn ich fragen habe melde ich mich.

Keine passende Antwort gefunden?

Fragen Sie die Community