17 Seeräuber und ein Koch

willikufalt · 09.07.2003

Eine Bande von 17 Seeräubern hat eine Kiste mit n Goldstücken gleichen Wertes
erbeutet. Sie entschließen sich, diese unter sich gleichmäßig aufzuteilen und den
Rest ihrem chinesischen Koch zu geben. Dann bekäme dieser 3 Münzen. Dann aber
streiten die Piraten sich, wobei 6 von ihnen umkommen. Jetzt bekäme der Koch 4
Münzen. Bei einem nachfolgenden Schiffsbruch werden nur 6 Seeräuber, der Koch
und die Kiste gerettet, jetzt bekäme der Koch 5 Münzen. Auf wie viele Münzen
darf der Koch mindestens hoffen, wenn er jetzt die restlichen Seeräuber vergiftet ?

TIPP: Es handelt sich um einen chinesischen Koch.

Zusatz: Wie lauten alle möglichen Lösungen ?

therealconqueror · 09.07.2003

785
1907
3029
4151
5273
6395
7517
8639
9761
usw. immer 1122 dazuzählen.

Eine Frage dazu: kann man das im Kopf bzw. auf einem Blatt Papier lösen? Wenn ja wie?

trc

p.s. ich hab das Rätsel nicht gekannt, bzw. nur irgendwo schon mal gehört (gesehen hier im pf?), aber hab's jetzt schon selbst gelöst.

ppm007 · 09.07.2003

Meinst Du mit dem Tip das "chinese remainder theorem"

Beste Grüße
ppm007

willikufalt · 09.07.2003

>> Eine Frage dazu: kann man das im Kopf bzw. auf einem Blatt Papier lösen? Wenn ja wie?

Ein Blatt Papier empfiehlt sich durchaus.

>> Wenn ja wie?
Die Antwort hat im Prinzip ppm007 gegeben:

Es läuft auf den chinesischen Restsatz hinaus. Bei weiterem Interesse empfiehlt es sich, ein Buch über Zahlentheorie zu besorgen.

therealconqueror · 09.07.2003

na ich hab's halt programmiertechnisch gelöst:
Hier der mini-c#-Code:

Code:

for (int i = 1; i<10000; i++) 
	{
		int z = Convert.ToInt32(Math.Floor(i/17)*17 +3);
		int zz = Convert.ToInt32(Math.Floor(i/11)*11 + 4);
		int zzz = Convert.ToInt32(Math.Floor(i/6)*6 + 5);					
		if ((z==i) && (zz==i) && (zzz==i)) Console.WriteLine("Ergebnis: " + z);
	}

trc

willikufalt · 09.07.2003

Muss man das in C# so umständlich machen ?

Warum benutzt du nicht die modulo-Funktion:

void main()
{
for (int i=20;i<10000;i+=17) {
if ( (i%11==4) && (i%6==5) ) cout << i << endl;
}
}

Ausserdem ist es sehr ineffizient, alle i zu überprüfen !

matmike · 09.07.2003

Hallo,

ich habe es gerade mal mit dem Chinese Remainder Theorem probiert (Kryptologie lässt grüßen).
Allerdings kenne ich das nur in der Form, dass man aus zwei Formeln der Art
s=x mod(y)
t=x mod(z)
den Wert von x rausfinden kann, wenn der Rest gegeben ist. Allerdings weiß ich nicht, wie ich das ganze (ohne perverse Linearkombinationen) auf 3 Formeln erweitern kann.
Weiß da Jemand Bescheid und kann das hier posten?

MatMike

P.S.: Mir ist klar, dass ich es einfach durch dazuaddieren des Moduls zu den Werten, die ich aus den ersten beiden Formeln finde, rauskriege. Allerdings ist das nur für kleine Zahlen möglich, irgendwann wird es dann relativ unbequem (insbesondere ohne Rechner)

willikufalt · 09.07.2003

Hier werden Sie geholfen:

http://www.uni-mainz.de/~pommeren/Kryptologie/Asymmetrisch/1_RSA/chinrest.pdf

Muss man sich schon bißchen mit beschäftigen, ist aber nicht sehr schwer.

matmike · 09.07.2003

Du solltest mal schnell das Leerzeichen aus der URL nehmen, sonst gibt es nur ein "Document not found".

MatMike

therealconqueror · 10.07.2003

@willikufalt
natürlich geht's einfacher mit modulo. Hab's halt nur mit meinem ersten Gedanken, den ich hatte programmiert, und mir nicht weitere Gedanken darüber gemacht, wie's einfacher zu lösen wäre.
trc

willikufalt · 10.07.2003

Ist mir schon klar, dass du das nur eben so hingehackt hast.

Allerdings habe ich auch nicht verstanden, wofür du die Funktionen Math.Floor und Convert.ToInt32 verwendest. i ist doch schon ein Integer.

Oder funktionert die Typkonvertierung in C# anders ?

matmike · 10.07.2003

Math.Floor dient vermutlich dazu, eine Modulo-Operation durchzuführen. Denn genau das ist das Ergebnis.
Die Konvertierung nach Int verstehe ich auch nicht. Aber vielleicht war zuerst mal geplant, die Modulo-Operation durch eine Integer-Division zu ersetzen. Das geht auch.

MatMike

willikufalt · 10.07.2003

Wofür die Funktionen gut sein sollen, ist schon klar.
Allerdings sind sie in normalem C überflüssig.

int z = ((i/17)*17 + 3) reicht völlig aus.

i ist integer => i/17 ist integer. (Entspricht i DIV 17)

Könnte aber sein, dass C# Sharp das anders behandelt und i in einen Typ double o.ä. umwandelt. Daher meine Frage.

therealconqueror · 10.07.2003

[OT]
o.k. o.k. war etwas zu schnell. Arbeite sellten mich mathematischen Funktionen. Und da habe ich gedacht, wenn man eine Division 2er Integers macht kein integer mehr rauskommen kann, sondern ein Decimal oder Double. Denn 3 / 2 ist nunmal im richtigen Leben nicht 1 sondern 1,5. Also ich gebe zu, das habe ich nicht gewußt(!!!!)
Schlussfolgerung: Natürlich reicht (i/17)*17 +3 vollkommen aus.
Math.Floor diente eigentlich nur dazu um aus z.b. 13,8 (Decimal) eine 13 und keine 14 zu machen - wenn durch Division 2er integers kein Integer mehr rausgekommen wäre.In diesem Fall war's natürlich vollkomen sinnlos.
Jetzt bich jedenfals wieda gscheita!

[/OT]
trc
p.s. das nächste mal schau ich mir das ganze genauer Durch bevor ich sourcecode poste :be:

17 Seeräuber und ein Koch

willikufalt

therealconqueror

ppm007

willikufalt

therealconqueror

willikufalt

matmike

willikufalt

matmike

therealconqueror

willikufalt

matmike

willikufalt

therealconqueror

17 Seeräuber und ein Koch

ANGEBOTE & SPONSOREN

Neueste Beiträge

Statistik des Forums