首页 > 试题广场 >

“村长”带着5对父子参加“爸爸去哪儿”第三季第二站某村庄的拍

[单选题]

“村长”带着5对父子参加“爸爸去哪儿”第三季第二站某村庄的拍摄。村里为了保护小孩不被拐走有个千年的规矩，那就是吃饭的时候小孩左右只能是其他小孩或者自己的父母。那么5对父子在圆桌上共有______种坐法。(旋转一下，每个人面对的方向变更后算是一种新的坐法)

```
960
```
```
3120
```
```
2400
```
```
7200
```
```
7440
```
```
9600
```

徘徊的路人甲

简单画图分析一下，孩子可能的坐法是：

1.2个坐一起，3个坐一起，这种情况下父亲分为2人，3人两组进行插入，首先坐好孩子A₅ ⁵，由于孩子旁边不能有其他父亲，所以在5个孩子中选出2个插入一组父亲C₅ ²，剩下一组父亲有两种坐法，所以该方法坐法为 A ₅ ⁵* C ₅ ²*2 = 2400

2.5个孩子坐一起，5个父亲坐一起，有两个父亲是要挨着自己孩子的，必须坐在父亲组的两侧，所以该种坐法为 A ₅ ⁵* 3！*10 = 7200

注意第一种方法最后不要乘10，总共坐法2400+7200 = 9600

发表于 2015-11-19 17:15:08 回复(1)

更多回答

鱼骨1101

（F） A 父 B 子 1、排序种类一开始想到ABABAB。。这种排序第一个老爸会挨着两个孩子，除非曹格能挨着自家的两个孩子敏感词人都违反游戏规则了。所以就想到AAAAABBBBB这种。 AAAAABBBBB 最左边的父亲c(5, 1)与中间的父亲c（4, 1）和自己的孩子挨着敏感词家的父子全排列 A(3,3) * A(3,3)，旋转后*10. c(5, 1) * c（4, 1） * A(3,3) * A(3,3) * 10 AABBAAABBB 一共有四对父子能享受天伦之乐，挨着坐A(5, 4)，旋转后*10 A(5, 4) * 10 AAABBAABBB A(5,4) * 10

发表于 2014-10-13 23:25:57 回复(0)

濺亽翔

答案应该是9600

孩子的坐法只有两种

1、2个坐一起、3个坐一起 AABBBAAABB 或者 AABBAAABBB

这样的情况是 A₅ ⁵ × C₅ ² × 2 × 10 = 2400

2、5个全坐一起 AAAAABBBBB

这样的情况是 A₅ ⁵ × A₃ ³ × 10 = 7200

穷举法代码实现：

0~9 共 10 个座位，坐 0~9 个人，假设 1和0 是父子，3和2是父子，依次类推。

1、先找出 0~9 的全排列数组，共 10！ = 3 628 800 个；

2、对每一个全排列数组做校验，校验每一位相邻的数字符不符合规则。

这样做的难点是：0~9 的全排列的列举，我用了Johnson-Trotter算法（尊重原作者，来源：http://introcs.cs.princeton.edu/java/23recursion/JohnsonTrotter.java.html）：

代码如下：

package com.leex.suanfa;

import java.util.ArrayList;

public class Sf150802 {
	/**
	 * 保存10!
	 */
	static ArrayList<String> list = new ArrayList<>();
	
	public static void main(String[] args) {
		int count = 0;
		Sf150802.perm(10);
		System.out.println(list.size());
		for (int i = 0; i < list.size(); i++) {
			if(check(list.get(i))){
				System.out.println(list.get(i));
				count ++;
			}
		}
		System.out.println(count);
	}
	
	public static void perm(int N) {
        int[] p   = new int[N];     // permutation
        int[] pi  = new int[N];     // inverse permutation
        int[] dir = new int[N];     // direction = +1 or -1
        for (int i = 0; i < N; i++) {
            dir[i] = -1;
            p[i]  = i;
            pi[i] = i;
        }
        perm(0, p, pi, dir);
    }

    public static void perm(int n, int[] p, int[] pi, int[] dir) { 
        if (n >= p.length) {
        	String tmp = "";
            for (int i = 0; i < p.length; i++) {
            	tmp += p[i];
            }
            list.add(tmp);
            return;
        }
        perm(n+1, p, pi, dir);
        for (int i = 0; i <= n-1; i++) {
        	int z = p[pi[n] + dir[n]];
            p[pi[n]] = z;
            p[pi[n] + dir[n]] = n;
            pi[z] = pi[n];
            pi[n] = pi[n] + dir[n];
            perm(n+1, p, pi, dir);
        }
        dir[n] = -dir[n];
    }
	
	/**
	 * 检查 字符串 是否符合要求
	 * @param str
	 * @return
	 */
	public static boolean check(String str) {
		char[] c = str.toCharArray();
		for (int i = 0; i < 10; i++) {
			int x = c[i];
			int y = (i == 9) ? c[0] : c[i+1];
			if(x % 2 == 0) {
				if(y % 2 != 0 && y != x + 1) {
					return false;
				}
			} else {
				if(y % 2 == 0 && y != x - 1) {
					return false;
				}
			}
		}
		return true;
	}

}

编辑于 2015-08-02 22:22:41 回复(2)