来个难点的题大家做做

yovn

某监狱有8个犯人，分别为A1,A2,A3,A4,A5,A6,A7,A8
其中A1和A2,A2和A3，A3和A4,A4和A5,A5和A6,A6和A7,A7和A1以及A7和A8不能同时在一个牢房。
请问
1.至少可以用多少间牢房安置这些犯人(每间人数不固定)
2.在牢房数最少的情况下，一共有多少中安置方案
补充一点 ，每间牢房不一样。
就是说 A1在牢房1与A1在牢房2属于不同的安置方案

[ 本帖最后由 yovn 于 2007-9-28 13:02 编辑 ]

ssafa

最少要3个，至于配置就不知道了

[ 本帖最后由 ssafa 于 2007-9-28 12:31 编辑 ]

eliry

最少用3间牢房，A7独占一间，A1 A3 A5占一间，A2 A4 A6 占一间，A8再除A7外的另外两个牢房中随便挑一间即可。所以在牢房数最少情况下有两种安置方法

yovn

最少牢房数对了，关于安置方案请看我的补充。

weedeater

1,3,5
2,4,7
6,8

1,3,6
2,5,7
4,8

1,3,8
2,4,6
5,7

1,4,6
2,5,7
3,8

1,4,6
2,5,8
3,7

1,4,8
2,5,7
3,6

有点多了
能编程序么？

[ 本帖最后由 weedeater 于 2007-9-28 13:24 编辑 ]

yovn

原帖由 eliry 于 2007-9-28 12:33 发表
最少用3间牢房，A7独占一间，A1 A3 A5占一间，A2 A4 A6 占一间，A8再除A7外的另外两个牢房中随便挑一间即可。所以在牢房数最少情况下有两种安置方法

即使每间牢房一样，也不只这么几种的。

1)A1,A3,A5,A8
A2,A4,A6
A7

2)A1,A3,A5
A2,A4,A6,A8
A7

3)A1,A4,A8
A2,A5,A7
A3,A6

4)A1,A4,A8
A3,A5,A7
A2,A6

......................

yovn

这是图论问题，可以算出确切的答案的