我们有 n 个人坐在一张圆桌上。任何人都可以与任何其他人握手。这 n 个人可以用多少种方式进行握手，以使两次握手不会相互交叉。
我在一个技术面试论坛上发现了这个谜题，但没有答案。我能想到的一种方法是找到握手的所有排列，然后检查每个排列是否满足。
任何人都可以建议任何其他更有效的解决方案。
@edit：来自评论的澄清：N 会是偶数。
问问题
13008 次
8 回答
15
我会尝试分而治之的解决方案。如果人 1 与人 x 握手，则将其余人分成两组，可以视为坐在两个圆桌旁。
于 2013-08-06T09:39:53.987 回答
12
作为 Python 函数（Python 3.3+）给出的解决方案非常简单：
@lru_cache(maxsize=None) # memoize
def num_handshakes(n):
if n % 2 == 1: return 0
elif n == 0: return 1
res = 0
for i in range(0, n, 2):
res += num_handshakes(i) * num_handshakes(n-2-i)
return res
例子：
>>> num_handshakes(8)
14
这基本上实现了@Buhb 的分而治之的方法。另一个解决方案，一旦我们知道答案与加泰罗尼亚数字有关：
from math import factorial as fac
def catalan(n):
return fac(2*n) // fac(n+1) // fac(n)
def num_handshakes(n):
if n % 2 == 1: return 0
return catalan(n//2)
于 2013-08-06T10:17:30.630 回答
8
我会尝试分而治之的解决方案。如果人 1 与人 x 握手，则将其余人分成两组，可以视为坐在两个圆桌旁。
@Buhb 是对的。该递归关系是
f(n) = sum( f(i-2) + f(n-i) for i in range(2, n))
或者在代码中
def f(n):
if n == 0:
# zero people can handshake
return 1
if n == 1:
# it takes two to tango
return 0
ways = 0
# what if person 1 shakes with person i ?
for i in range(2, n+1):
# splits table into independent sets 2 .. i-1 and i+1 .. n
ways += f(i-2) * f(n-i)
return ways
奇数人不能握手，但 f 的前几个偶数位是 1、2、5、14、42
搜索整数序列的百科全书，这看起来像著名的加泰罗尼亚数字http://oeis.org/A000108
序列真的是一样的，还是只是开始相似？他们是一样的。证实了我的一本数学书——我们定义 f 的递归关系也适用于加泰罗尼亚数字https://en.wikipedia.org/wiki/Catalan_number#Properties
于 2013-08-06T10:34:29.403 回答
0
我认为这甚至可能是一个解决方案n=2m.
将圆圈周围的人从 1 到 2m 编号。
在圆形中，j, 1≤j≤m,人 j 与人j+1握手，并且所有其他握手都与此“平行” （因此，j−1 与 j+2，j−2 与 j+3，依此类推——自始至终，标签被解释为模 n ，根据需要）。在这 m 轮结束时，每个人都与奇数人握手。
在第 m+j 轮中，1≤j≤m，j 与 j+2 握手，所有其他握手是平行的（因此 j-1 与 j+3，j-2 与 j+4 等）。这可以处理所有偶数人的配对。所以总共是2m发。
如问题陈述中所述，2m-1 轮是不可能的，所以 2m 是答案。
奇怪的情况更容易。在第 j 轮中，人 j 坐在外面，而 j-1 向 j+1 打招呼，j-2 向 j+2 打招呼，等等，再次使用 n 轮。
于 2013-08-06T11:31:34.083 回答
0
什么是回溯？
- 从一次握手开始，寻找仍然可能的握手。如果无法再
non crossing握手，则回溯。继续直到你的搜索树的分支不能通过non crossing握手来扩展。 - 结果搜索树的所有顶点都是
non crossing握手。
因为您的桌子是圆形的（对称），您可以通过假设该人0始终是最频繁握手的一部分来优化问题。
于 2013-08-06T09:45:48.360 回答
0
这里结果遵循加泰罗尼亚数字系列。这是我在 C++ 中的代码
#include <bits/stdc++.h>
using namespace std;
long c[17] ;
void sieve(){
c[0] = 1;
c[1] = 1;
for(int i =2;i<=15;i++){
for(int j =0;j<i;j++){
c[i] += c[j]*c[i-j-1];
}
}
}
int main(void){
sieve();
int t;
scanf("%d",&t);
while(t--){
int n ;
scanf("%d",&n);
if(n%2!=0){
cout<<"0"<<endl;
}
else{
n = n>>1;
cout<<c[n]<<endl;
}
}
return 0;
}
于 2017-12-30T02:08:31.107 回答
0
由于有 n 人和 2 人一次会握手，而且如果让我们说 A 与 B 握手和 B 与 A 握手，我们不能数两次，即。AB 和 BA 都不能计算，这最终意味着没有安排，即。排列不是这种情况，但组合是......
因此，应用组合公式，求解后变为： nC2 => (n*(n-1))/2 。
所以我们可以直接把这个公式应用到问题上来得到答案。
于 2020-01-05T15:46:26.683 回答
-1
人们可以用(n-1)+(n-2)+.....+1 waysIt's for linear握手
n圆桌会议方式
于 2013-08-06T09:45:27.770 回答