珍珠湾ART

标题: 多少航空公司 [打印本页]

作者: 野菜花 时间: 2006-1-31 18:06
标题: 多少航空公司

某国家有21个城市，一个航空公司可以把5个城市完全连起来，也就是说这个航空公司在这5个城市中每两个城市间都有航班。问最少需要多少航空公司才能保证每两个城市间都有航班？

作者: constant 时间: 2006-1-31 18:32
标题: 回复：多少航空公司

14?

作者: 任何人 时间: 2006-1-31 18:41
标题: 6个

6个

作者: 野菜花 时间: 2006-1-31 18:49
标题: 是要保证每两个城市间都有直接的航班[;)]

是要保证每两个城市间都有直接的航班

作者: 有空想想 时间: 2006-1-31 18:52
标题: 回复：多少航空公司

一个航空公司需提供 10 条航线，以达到在五个城市中每两个城市间都有航线。（5选2）

21个城市则需要 210 条航线，以达到任何每两个城市间都有航线。而一个航空公司只能提供 10 条。

所以我们需要 21 个航空公司？

作者: 任何人 时间: 2006-1-31 18:55
标题: [:D)]看错了，看成25个城市。 21个城市 - 5家航空公司

5加航空公司，每家占5个城市，5个城市有4个是独占，1个共享。 5 x 4 + 1 = 21

本贴由[任何人]最后编辑于：2006-1-31 10:56:0

本贴由[任何人]最后编辑于：2006-1-31 10:59:40

作者: 任何人 时间: 2006-1-31 19:02
标题: [:>]又错了

又错了

作者: 99-99 时间: 2006-1-31 19:05
标题: 要不要俺借给你一个钢盔？[:D)][:E]

要不要俺借给你一个钢盔？

作者: 任何人 时间: 2006-1-31 19:10
标题: [:>]俺继续努力

俺继续努力

作者: 任何人 时间: 2006-1-31 19:34
标题: [:%]

2 个城市 1条航线

3 个城市 3条航线

4 个城市 6条航线

5 个城市 10条航线

6 个城市 15条航线

21 个城市？？？条航线www.ddhw.com

作者: ob 时间: 2006-1-31 19:36
标题: 回复：多少航空公司

C21(2)/C5(2)=21?

作者: 任何人 时间: 2006-1-31 19:40
标题: (21！)/(2! x 19!) = 210 ， 210/10 = 21

你的答案应该是对的 (21！)/(2! x 19!) = 210

210/10 = 21

本贴由[任何人]最后编辑于：2006-1-31 11:41:57

作者: 野菜花 时间: 2006-1-31 20:34
标题: 回复：回复：多少航空公司

不错，说明至少需要21个航空公司。www.ddhw.com但是21个是否够呢？如果够的话，要给出一个具体的分配---这是更难的部分。

作者: 野菜花 时间: 2006-1-31 20:34
标题: 回复：回复：多少航空公司

不错，说明至少需要21个航空公司。www.ddhw.com但是21个是否够呢？如果够的话，要给出一个具体的分配---这是更难的部分。

作者: 有空想想 时间: 2006-2-1 00:17
标题: 我的想法，欢迎拍砖。。。[:E]

如果没有两个公司运营同一航线就应该够。

实际分配也不应该太难，可以设计个算法。譬如：

21个公司，21个城市。每个公司占据一个城市做为大本营。每个公司都从自己的大本营出发，选10坐城市建立航线（即每个公司提供10条航线）。这样也照顾到公司不想飞跟自己大本营不相连的航线。

要求：

1）循环21个公司，在一次循环中，每个公司选一条航线。共循环 10 次。

2）不可以选别的公司已经建立的航线作为自己公司航线；

3）每个城市应有20条航线，每个城市已建航线数量的倒数应记作该城市被选作连接的优先级（以避免有航空公司被封死，无航线可选），任何公司在选航线时，要从自己可连接的最高优先级的城市选起。每有一条新的航线建立，优先权就要重新计算一次。

4）如果两个可连最高优先级城市的优先级一样，任选其中一个。

还有什么要注意的要求？

这个程序应该不难写。

本贴由[有空想想]最后编辑于：2006-1-31 16:19:26

作者: 野菜花 时间: 2006-2-1 00:42
标题: 回复：我的想法，欢迎拍砖。。。[:E]

先申明不是拍砖，没看懂你的分析

你说：“每个公司都从自己的大本营出发，选10坐城市建立航线（即每个公司提供10条航线）”

可是题目里，每个公司只能连5个城市呀

作者: huxlnn 时间: 2006-2-1 07:31
标题: 29个?

4+5*5=29

作者: 任何人 时间: 2006-2-1 13:28
标题: [:%]这题好复杂，之前想得太简单了

这题好复杂，之前想得太简单了

作者: 有空想想 时间: 2006-2-1 17:02
标题: 回复：回复：我的想法，欢迎拍砖。。。[:E]

你原题中说的是“一个航空公司可以把5个城市完全连起来，也就是说这个航空公司在这5个城市中每两个城市间都有航班”。你没有说，“并且最多连接5个城市”。我理解那句话是说明航空公司的能力，换句话说就是，每个航空公司可以提供10条航线。所以给出那个想法。

如果加上条件“并且最多连接5个城市”，那情况就完全不同了。

我想是我理解错了。

作者: huxlnn 时间: 2006-2-1 17:22
标题: 更改答案为25

4+25-4=25,问题应该不大了

作者: 野菜花 时间: 2006-2-1 19:09
标题: 抱歉，是我题目没说清楚[:P] 应该这样说

一个航空公司可以也只可以把5个城市完全连起来

作者: 野菜花 时间: 2006-2-1 19:12
标题: 回复：更改答案为25

不是最小值

作者: huxlnn 时间: 2006-2-2 04:01
标题: 更改答案为24

4+5*5-5=24,

作者: full-form 时间: 2006-2-2 04:42
标题: 回复：多少航空公司

1,2,3,4,5

1,6,7,8,9

1,10,11,12,13

1,14,15,16,17

1,18,19,20,21

2,6,10,14,18

2,7,11,15,19

2,8,12,16,20

2,9,13,17,21

3,6,11,16,21

3,7,10,17,20

3,8,13,14,19

3,9,12,15,18

4,6,12,17,19

4,7,13,16,18

4,8,10,15,21

4,9,11,14,20

5,6,13,15,20

5,7,12,14,21

5,8,11,17,18

5,9,10,16,19

作者: huxlnn 时间: 2006-2-2 07:16
标题: 真是仔细啊[@};-][>:D<]

真是仔细啊[@};-][>:D<]

本贴由[huxlnn]最后编辑于：2006-2-1 23:18:40

作者: ob 时间: 2006-2-2 21:05
标题: [@};-][@};-][@};-]赶快注册吧[>:D<][>:D<]

赶快注册吧

作者: 野菜花 时间: 2006-2-4 19:25
标题: 厉害！PF![:B][@};-][@};-]

厉害！PF!

欢迎光临珍珠湾ART (http://zzwav.com/)