Übungsaufgabe in C
-
Problem:
Ein König hat in seinem Kerker 100 Zellen, vor jeder Zelle steht ein Wärter. An seinem Geburtstag hat der König die Idee Gefangen zu entlassen, da er aber nicht alle frei lassen will hat er sich ein Schema überlegt mit dem er entscheiden will wer freigelassen werde soll.Schema:
Die Zellen sind von 1 - 100 durchnummeriert, dieselbe Nummer hat auch jeder Wärter. Der Ablauf beginnt nun mit Wärter Nummer 1, der an alle Zellentüren vorbei geht und jede Zelle öffnet. Anschließend ist der Wärter 2 an der Reihe, der jede zweite Tür betrachtet und ihren Zustand verändert (ist die Tür offen schließt er sie ist die Tür geschlossen öffnet er diese).
Nun kommt der dritte Wärter an die Reiher der beginnend mit der Tür drei, vor der er steht, jede dritte Tür betrachtet und deren Zustand verändert (ist die Tür offen schließt er Sie ist die Tür geschlossen öffnet er diese).Fragestellung:
Wieviel gefangen kommen frei, und aus welchen Zellen.Versuche dies gerade als Programm in C zu schreiben - schaffe es aber nicht.
Nur schlaflose Nächte...
-
Mathematischerseits sieht man, daß nur Zahlen übrigbleiben, deren Anzahl an Teilern (wobei ich die eins und sich selbst hier dazurechne) ungerade ist, also entweder 1, 3, 5 ... Teiler haben. Ganz offensichtlich trifft das auf die 1 zu, die nur von sich geteilt wird, womit die Tür offen bleibt.
Es gibt aber auch für die Quadrate von Primzahlen, denn die sind nur durch die Primzahl, eins und sich selbst teilbar, also die Klasse mit drei Teilern abdeckt. Es gilt aber auch für alle anderen Quadratzahlen, denn wenn z = k^2, wobei k nicht prim (also k = a*b, wobei a prim und b passend sein sollte) sein muß, dann kommt man auf z = a2*b2. Also ist z nun teilbar durch 1, a, z und durch die Teiler von b. Die Frage ist nun, ob man zeigen kann, daß b eine gerade Anzahl an Teilern hat:
Da b nicht prim ist, wähle man nun z = b = k^2 und führe den obigen Absatz so lange durch, bis man b = 1 oder b = prim erhält. Dann muß man nur noch zeigen, daß <gerade>+<ungerade> = <ungerade> und man hat gezeigt, daß alle Leute, die an Quadratzahlen stehen freikommen.Für andere z = a*b != k^2 kann man nun so ähnlich argumentieren, indem man ausnutzt, daß jede Primzahl zwei "Teiler" hat und <gerade>+<gerade> = <gearde>, dann behaupte ich, daß nur Leute die an Position 1 oder an der Position einer Quadratzahl stehen freikommen. 1^2 = 1 ... 10^2 = 100, also gibt es neun Leute, die freikommen.
Verzeiht, wenn das alles häßlich, umständlich oder falsch ist, von Zahlentheorie versteh ich so gut wie nix.
In C kann man sich die Mathematik auch einfach sparen und die Aufgabe originalgetreu umschreiben und ist recht einfach:
int main(void) { int i, j, tuer[100] = { 0 }; /* Alle Türen zu! */ for (i = 0; i < 100; ++i) { for (j = i; j < 100; j += i+1) /* nachfolgende Türen bearbeiten */ tuer[j] = !tuer[j]; putchar("GF"[tuer[i]]); /* F = frei, G = gefangen */ } }
-
Hallo,
danke für die schnelel Antwort. Ich bekomme jedoch ein ganz anderes Ergebnis raus:
Bei dir sind die Zellen wie folgt deklariert:
1 = F
2 = G
3 = G
4 = F
5 = G
6 = G
7 = G
8 = G
9 = F
usw.Ich habe das mal auf dem 'Fußweg' nachgerechnet - dann komme ich zu dieser Deklarierung:
1 = F
2 = G
3 = G
4 = G
5 = F
6 = F
7 = F
8 = G
9 = G
usw.Denn der erste Wächter macht alle Türen auf - der zweite Wächter ändert den Zustand jeder 2. Tür. Damit sind nur noch die ungeraden Türen auf. Der dritte
Wächter ändert den Zusatnd jeder 3. Tür.Oder sollte ich jetzt total falsch liegen
-
Spawny schrieb:
Denn der erste Wächter macht alle Türen auf - der zweite Wächter ändert den Zustand jeder 2. Tür. Damit sind nur noch die ungeraden Türen auf. Der dritte Wächter ändert den Zusatnd jeder 3. Tür.
Dann zeig doch mal die ersten paar Schritte her, die Du gemacht hast.
-
wie gesagt - bislang nur auf dem 'fußweg':
Wärter1 Wärter2 Wärter3 Zelle 1 auf auf auf Zelle 2 auf zu zu Zelle 3 auf auf zu Zelle 4 auf zu zu Zelle 5 auf auf auf Zelle 6 auf zu auf Zelle 7 auf auf auf Zelle 8 auf zu zu Zelle 9 auf auf zu Zelle 10 auf zu zuWärter1 macht alle Türen auf.
Wärter2 macht jede zweite (gerade) Tür zu.
Wärter drei ändert den Zustand jeder dritten Tür.
-
Äh, und nach dem dritten Wächter soll Schluß sein? Dann habe ich das Problem ja komplizierter gemacht, als es in Wirklichkeit ist. Ich dachte, als nächstes ist Wächter vier an der Reihe, der von Position 4 ab jeden 4. verändert, dann der 5. Wärter, der ab Pos. 5 jede 5. Tür usw. usf. Ansonsten ist das Problem tatsächlich erledingt, das Programm wird noch einfacher und die Lösung auch einfach von Hand ausrechenbar. Wo ist da dein Problem? Poste doch mal deinen C-Code.
Vielleicht kann uns bei der Gelegenheit gleich mal ein Moderator verschieben? Danke.
-
Genau - nach dem 3. Wächter ist Schluß.
Wenn das aus deiner Sicht so einfach ist, kannst du bitte dein Code dementsprechend ändern
Die Lösung sollte bei mir 49 offene Zellen sein...
DANKE
-
@Spawny
Vielleicht hilft dir das weiter:#include <stdio.h> int main() { const unsigned int len = 100; bool door[len]; unsigned int waerter1, waerter2, waerter3, i; unsigned int nrOpenDoors = 0, nrClosedDoors = 0; for(waerter1 = 0; waerter1 < len; ++waerter1) door[waerter1] = true; for(waerter2 = 1; waerter2 < len; waerter2 += 2) door[waerter2] = false; for(waerter3 = 2; waerter3 < len; waerter3 += 3) door[waerter3] = !door[waerter3]; for(i = 0; i < len; ++i) { printf("%d. Tuer, Status: ", i + 1); if(door[i]) { ++nrOpenDoors; printf("offen\n"); } else { ++nrClosedDoors; printf("geschlossen\n"); } } printf("\n\n Offene Tueren: %d\n", nrOpenDoors); printf(" Geschlossene Tueren: %d\n", nrClosedDoors); return 0; }//edit: Hab's in C umgeschrieben, hoffentlich ist es korrekt. (Ist nämlich mein erstes C-Programm)
Caipi
-
Super - Danke!
-
Kleine Frage, könnte man das nicht auch unter Verwendungen von XOR lösen?
Ich mein im Prinzip ist das was der Wächter da macht ja eine simple XOR Operation. Jeder Wächter hat ein anderes XOR-Muster, diese wendet man hintereinander an und hat danach sein "End"-Bitmuster.cya
liquid
-
klar geht das mit xor - mit daniel E.'s code z.b.:
statttuer[j] = !tuer[j];nimmt man
tuer[j] ^= true;ist aber krank
sonst macht man das ja nur, wenn man bitfelder hat, also vector<bool> oder ähnliches. dann kriegst du aber probleme mit dem padding, oder du musst eben die xor-maske ständig rotieren.