puzzle: N Personen sitzen auf einem runden Tisch. Nein von Händeschütteln ohne andere Handschläge zu kreuzen
Wir haben n Personen auf einem runden Tisch sitzen. Jede Person kann mit jeder anderen Person einen Handschlag machen. Auf wie viele Arten können diese n Leute Händeschütteln machen, so dass sich keine zwei Händeschütteln überschneiden.
Ich habe dieses Puzzle in einem technischen Interviewforum gefunden, aber keine Antwort. Eine Möglichkeit, an die ich denken konnte, war, alle Permutationen von Handshakes zu finden und dann jede Permutation zu überprüfen, ob sie befriedigt oder nicht.
Kann jemand bitte eine andere Lösung vorschlagen, die effizienter ist.
@edit: Klarstellung von Kommentaren: N wäre gerade.
7 Antworten
Die Lösung ist ziemlich einfach als Python-Funktion (Python 3.3 +) gegeben:
%Vor%Beispiel:
%Vor%Dies implementiert im Grunde @ Buhb's "Teile und herrsche" Ansatz. Eine andere Lösung, sobald wir die Antwort kennen, ist die katalanische Nummer :
%Vor%Ich würde versuchen, eine Lösung zu teilen und zu erobern. Wenn Person 1 die Hand mit Person x schüttelt, teilt sie den Rest der Personen in zwei Gruppen auf, die so behandelt werden können, als würden sie an zwei runden Tischen sitzen.
@Buhb hat Recht. Diese Wiederholungsbeziehung ist
%Vor%Oder im Code
%Vor%Eine ungerade Anzahl von Personen kann nicht händeschütteln, aber die ersten paar Werte von f sind 1, 2, 5, 14, 42
Wenn man die Enzyklopädie der Integer-Sequenzen durchsucht, sieht das aus wie bekannte katalanische Zahlen Ссылка
Sind die Sequenzen wirklich gleich oder beginnen sie einfach ähnlich? Sie sind gleich. Bestätigte mein Mathematikbuch - unsere Wiederholungsrelation, die f für die katalanischen Zahlen definiert, zu Ссылка
Was für ein Backtracking?
- Beginnen Sie mit einem Handschlag und suchen Sie nach möglichen Handshakes. Wenn keine
non crossingHandshakes mehr möglich sind, backtrack. Fahren Sie fort, bis keine weiteren Zweige Ihres Suchbaums um einennon crossinghandshake erweitert werden können. - Alle Scheitelpunkte des resultierenden Suchbaums sind
non crossinghandshakes.
Da Ihre Tabelle rund ist (Symmetrie), können Sie das Problem optimieren, indem Sie annehmen, dass die Person 0 immer Teil des obersten Handshakes ist.
Ich denke, dass dies eine Lösung für sogar n=2m.
Nummeriere die Personen im Umkreis von 1 bis 2m.
In Runde j, 1≤j≤m, Person j schüttelt Hände mit Person j+1 , und alle anderen Handshakes sind "parallel" zu diesem (also, j-1 mit j + 2, j-2 mit j + 3, und so weiter - durchweg werden die Etiketten modulo n interpretiert, wenn nötig. Am Ende dieser m Runden hat jeder mit einer ungeraden Anzahl von Leuten die Hand geschüttelt.
In Runde m + j, 1≤j≤m, j schüttelt j + 2 und alle anderen Handshakes sind parallel (also j-1 mit j + 3, j-2 mit j + 4, usw.). Dies behandelt alle Paare eine gerade Anzahl von Menschen auseinander. Das sind also 2m Runden.
Wie in der Problembeschreibung erwähnt, sind 2m-1 Runden unmöglich, also ist 2m die Antwort.
Der seltsame Fall ist noch einfacher. In Runde j sitzt Person j, während j-1 grüßt j + 1, j-2 grüßt j + 2, usw., wieder mit n Runden.
Hier folgen Sie der katalanischen Nummerserie. Hier ist mein Code in C ++
%Vor%