拼图：N人坐在圆桌上。没有穿过任何其他握手的握手方式

Question

我们有n个人坐在圆桌旁。任何人都可以与任何其他人握手。这些人可以通过多少方式进行握手，这样就不会有两次握手相互交叉。

我在技术访谈论坛中发现了这个难题，但没有答案。我能想到的一种方法是找到握手的所有排列，然后检查每个排列是否满足。

任何人都可以建议任何其他更有效的解决方案。

@edit：评论澄清：N会是均匀的。

Answer 1

我会尝试分而治之的解决方案。如果人1与人x握手，则将其余人分成两组，可以视为坐在两个圆桌旁。

Answer 2

作为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的分而治之的方法。另一个解决方案，一旦我们知道答案与Catalan numbers有关：

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)

Answer 3

我会尝试分而治之的解决方案。如果人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

Answer 4

什么是回溯？

1. 从一次握手开始，寻找仍然可能的握手。如果没有更多的non crossing握手是可能的，回溯。继续，直到non crossing握手不再扩展搜索树的分支。
2. 生成的搜索树的所有顶点都是non crossing握手。

因为您的表是圆的（对称），您可以通过假设人0始终是最顶级握手的一部分来优化问题。

Answer 5

我认为这可能是甚至n=2m.的解决方案

将圈子周围的人数从1到2米。

在圆形的j, 1≤j≤m,人j与人j+1握手，并且所有其他握手与此“平行”（因此，j-1与j + 2，j-2与j + 3，依此类推 - 在整个过程中，标签被解释模数n，必要时）。在这几轮比赛结束时，每个人都与所有人握手，奇怪的人数。

在圆形m + j，1≤j≤m中，j与j + 2抖动，并且所有其他握手是平行的（因此j-1与j + 3，j-2与j + 4等）。这可以处理偶数人的所有对。总共是2米轮。

如问题陈述所述，2m-1轮是不可能的，因此2m就是答案。

奇怪的情况更容易。在第j轮中，人j坐下，而j-1迎接j + 1，j-2迎接j + 2等，再次使用n轮。

Answer 6

这里结果遵循加泰罗尼亚数字系列。这是我在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;
}

Answer 7

人们可以与(n-1)+(n-2)+.....+1 ways握手这是线性的

n圆桌会议的方式