zjut acm oj 1786 一个圆上有n(n是偶数)个不同的点,每个点需要和其他一个点连成一条线段.线段两两之间没有交点的连接方法称为“No X”.给定一个n,求出有多少种“No X”的连接方法.递归或公
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/14 12:47:35
![zjut acm oj 1786 一个圆上有n(n是偶数)个不同的点,每个点需要和其他一个点连成一条线段.线段两两之间没有交点的连接方法称为“No X”.给定一个n,求出有多少种“No X”的连接方法.递归或公](/uploads/image/z/8789087-47-7.jpg?t=zjut+acm+oj+1786+%E4%B8%80%E4%B8%AA%E5%9C%86%E4%B8%8A%E6%9C%89n%EF%BC%88n%E6%98%AF%E5%81%B6%E6%95%B0%EF%BC%89%E4%B8%AA%E4%B8%8D%E5%90%8C%E7%9A%84%E7%82%B9%2C%E6%AF%8F%E4%B8%AA%E7%82%B9%E9%9C%80%E8%A6%81%E5%92%8C%E5%85%B6%E4%BB%96%E4%B8%80%E4%B8%AA%E7%82%B9%E8%BF%9E%E6%88%90%E4%B8%80%E6%9D%A1%E7%BA%BF%E6%AE%B5.%E7%BA%BF%E6%AE%B5%E4%B8%A4%E4%B8%A4%E4%B9%8B%E9%97%B4%E6%B2%A1%E6%9C%89%E4%BA%A4%E7%82%B9%E7%9A%84%E8%BF%9E%E6%8E%A5%E6%96%B9%E6%B3%95%E7%A7%B0%E4%B8%BA%E2%80%9CNo+X%E2%80%9D.%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AAn%2C%E6%B1%82%E5%87%BA%E6%9C%89%E5%A4%9A%E5%B0%91%E7%A7%8D%E2%80%9CNo+X%E2%80%9D%E7%9A%84%E8%BF%9E%E6%8E%A5%E6%96%B9%E6%B3%95.%E9%80%92%E5%BD%92%E6%88%96%E5%85%AC)
zjut acm oj 1786 一个圆上有n(n是偶数)个不同的点,每个点需要和其他一个点连成一条线段.线段两两之间没有交点的连接方法称为“No X”.给定一个n,求出有多少种“No X”的连接方法.递归或公
zjut acm oj 1786
一个圆上有n(n是偶数)个不同的点,每个点需要和其他一个点连成一条线段.线段两两之间没有交点的连接方法称为“No X”.给定一个n,求出有多少种“No X”的连接方法.
递归或公式都可以的吧,但是我都没想到怎么做.
zjut acm oj 1786 一个圆上有n(n是偶数)个不同的点,每个点需要和其他一个点连成一条线段.线段两两之间没有交点的连接方法称为“No X”.给定一个n,求出有多少种“No X”的连接方法.递归或公
将n个点设为A1,A2,...,An.
设"No X"的连接方法总共有N(x)种
观察A1,显然A1只能和Ax连线(x为偶数).比如,如果A1和A3连,那么A2将无法和任何其他点连线.
当A1和A2连时,剩下n-2个点,连线方法有N(n-2)种,
当A1和A4连时,A2和A3有N(2)种连线方法;剩下n-4个点有N(n-4)种方法
当A1和A6连时,A2 A3 A4 A5有N(4)种连线方法;剩下n-6个点有N(n-6)种方法
.
N(2) = 1
N(4) = N(2) + N(2) = 2
N(6) = N(4) + N(2) * N(2) + N(4) = 5
N(8) = N(6) + N(4) * N(2) + N(2) * N(4) + N(6) = 14
N(10) = N(8) + N(6) * N(2) + N(4) * N(4) + N(2) * N(6) + N(8) = 42
.