多少航空公司

野菜花 · 发表于 2006-1-31 18:06:39

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

constant · 发表于 2006-1-31 18:32:05

14?

任何人 · 发表于 2006-1-31 18:41:47

6个

野菜花 · 发表于 2006-1-31 18:49:52

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

有空想想 · 发表于 2006-1-31 18:52:44

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

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

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

任何人 · 发表于 2006-1-31 18:55:14

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:34

又错了

99-99 · 发表于 2006-1-31 19:05:33

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

任何人 · 发表于 2006-1-31 19:10:13

俺继续努力

任何人 · 发表于 2006-1-31 19:34:57

2 个城市 1条航线

3 个城市 3条航线

4 个城市 6条航线

5 个城市 10条航线

6 个城市 15条航线

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

ob · 发表于 2006-1-31 19:36:08

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

任何人 · 发表于 2006-1-31 19:40:36

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

210/10 = 21

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

野菜花 · 发表于 2006-1-31 20:34:14

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

野菜花 · 发表于 2006-1-31 20:34:42

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

有空想想 · 发表于 2006-2-1 00:17:00

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

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

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

要求：

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

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

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

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

还有什么要注意的要求？

这个程序应该不难写。

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

野菜花 · 发表于 2006-2-1 00:42:31

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

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

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

huxlnn · 发表于 2006-2-1 07:31:36

4+5*5=29

任何人 · 发表于 2006-2-1 13:28:21

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

有空想想 · 发表于 2006-2-1 17:02:40

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

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

我想是我理解错了。

huxlnn · 发表于 2006-2-1 17:22:01

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

野菜花 · 发表于 2006-2-1 19:09:04

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

野菜花 · 发表于 2006-2-1 19:12:39

不是最小值

huxlnn · 发表于 2006-2-2 04:01:36

4+5*5-5=24,

full-form · 发表于 2006-2-2 04:42:15

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:36

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

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

ob · 发表于 2006-2-2 21:05:04

赶快注册吧

野菜花 · 发表于 2006-2-4 19:25:22

厉害！PF!

		自动登录	找回密码
密码			立即注册

动态微博

多少航空公司

回复：多少航空公司

6个

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

回复：多少航空公司

[:D)]看错了，看成25个城市。 21个城市 - 5家航空公司

[:>]又错了

要不要俺借给你一个钢盔？[:D)][:E]

[:>]俺继续努力

[:%]

回复：多少航空公司

(21！)/(2! x 19!) = 210 ， 210/10 = 21

回复：回复：多少航空公司

回复：回复：多少航空公司

我的想法，欢迎拍砖。。。[:E]

回复：我的想法，欢迎拍砖。。。[:E]

29个?

[:%]这题好复杂，之前想得太简单了

回复：回复：我的想法，欢迎拍砖。。。[:E]

更改答案为25

抱歉，是我题目没说清楚[:P] 应该这样说

回复：更改答案为25

更改答案为24

回复：多少航空公司

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

[@};-][@};-][@};-]赶快注册吧[>:D<][>:D<]

厉害！PF![:B][@};-][@};-]