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

... komplette Frage anzeigen

3 Antworten

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.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von PWolff
26.11.2015, 12:46

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

1

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 bewerten Vielen Dank für Deine Bewertung

Okay, und was hast du schon versucht?

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von BattleSheepGG
26.11.2015, 09:00
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();
}
1

Was möchtest Du wissen?