数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 330|回复: 20

在五座岛屿之间建造四座桥,使它们能够联通,请问有几种建桥方案?

[复制链接]
发表于 2019-11-15 19:57 | 显示全部楼层 |阅读模式
本帖最后由 luyuanhong 于 2019-11-15 22:21 编辑

計數問題
108 xu4 g0.jpg
发表于 2019-11-16 06:57 | 显示全部楼层
本帖最后由 王守恩 于 2019-11-16 13:26 编辑

在五座岛屿之间建造四座桥,使它们能够联通,请问有几种建桥方案?

共有125种建桥方案。
先固定3座桥(等号左边),
再选第4座桥的建桥方案(等号右边)。

04:12,13,14=15,25,35,45
07:12,13,15=24,34,45
07:12,13,23=0
10:12,13,24=25,35,45
12:12,13,25=34,45
14:12,13,34=35,45
15:12,13,35=45

18:12,14,15=23,34,35
21:12,14,23=25,35,45
21:12,14,24=0
23:12,14,25=34,35
25:12,14,34=35,45
26:12,14,35=45

29:12,15,23=24,34,45
31:12,15,24=34,35
31:12,15,25=0
33:12,15,34=35,45
34:12,15,35=45

37:12,23,24=25,35,45
39:12,23,25=34,45
41:12,23,34=35,45
42:12,23,35=45

44:12,24,25=34,35
46:12,24,34=35,45
47:12,24,35=45
49:12,25,34=35,45
50:12,25,35=45
50:12,34,35=0

53:13,14,15=23,24,25
56:13,14,23=25,35,45
59:13,14,24=25,35,45
61:13,14,25=35,45
61:13,14,34=0
61:13,14,35=0

64:13,15,23=24,34,45
67:13,15,24=25,34,45
69:13,15,25=34,45
69:13,15,34=0
69:13,15,35=0

72:13,23,24=25,35,45
74:13,23,25=34,45
76:13,23,34=35,45
77:13,23,35=45

79:13,24,25=34,35
81:13,24,34=35,45
82:13,24,35=45
84:13,25,34=35,45
85:13,25,35=45
85:13,34,35=0

89:14,15,23=24,25,34,35
91:14,15,24=34,35,
93:14,15,25=34,35
93:14,15,34=0
93:14,15,35=0

96:14,23,24=25,35,45
98:14,23,25=34,45
100:14,23,34=35,45
101:14,23,35=45

103:14,24,25=34,35
105:14,24,34=35,45
106:14,24,35=45
108:14,25,34=35,45
109:14,25,35=45
109:14,34,35=0

112:15,23,24=25,35,45
114:15,23,25=34,45
116:15,23,34=35,45
117:15,23,35=45

119:15,24,25=34,35
121:15,24,34=35,45
122:15,24,35=45
124:15,25,34=35,45
125:15,25,35=45
125:15,34,35=0








回复 支持 反对

使用道具 举报

发表于 2019-11-18 16:44 | 显示全部楼层
在五座岛屿之间建造四座桥,使它们能够联通,请问有几种建桥方案?.GIF

在五座岛屿之间建造四座桥,使它们能够联通,请问有几种建桥方案?.rar (22.02 KB, 下载次数: 5)

点评

謝謝老師  发表于 2019-11-18 18:39
回复 支持 反对

使用道具 举报

发表于 2019-11-18 17:45 | 显示全部楼层
我想起啦欧拉的什么桥问题
回复 支持 反对

使用道具 举报

发表于 2019-11-18 19:36 | 显示全部楼层
本帖最后由 王守恩 于 2019-11-18 19:41 编辑


谢谢陆老师!精彩的解答!我的方法不行。
4 座桥有 8 个点,5 个岛 5 个点(每个岛肯定要 1 个点),还剩 3 个点,只有下列第 1 种类型 (1+1+1),第 2 种类型 (3),第 3 种类型 (1+2) 3 种可能。
5 座桥有10个点,6 个岛 6 个点(每个岛肯定要 1 个点),还剩 4 个点,只有下列第 1 种类型(1+1+1+1),第 2 种类型(4),第 3 种类型(1+1+2),第 4 种类型(1+3),第 5 种类型(2+2)5种可能。
谢谢陆老师!能再来一次精彩的解答吗?谢谢陆老师!
回复 支持 反对

使用道具 举报

发表于 2019-11-24 08:43 | 显示全部楼层
王守恩 发表于 2019-11-18 19:36
谢谢陆老师!精彩的解答!我的方法不行。
4 座桥有 8 个点,5 个岛 5 个点(每个岛肯定要 1 个点),还 ...

楼主可是有标准答案?
在 2 座岛屿之间建造 1 座桥,使它们能够联通,有 1 种建桥方案。
在 3 座岛屿之间建造 2 座桥,使它们能够联通,有 3 种建桥方案。
在 4 座岛屿之间建造 3 座桥,使它们能够联通,有 16 种建桥方案。
在 5 座岛屿之间建造 4 座桥,使它们能够联通,有 125 种建桥方案。
在 6 座岛屿之间建造 5 座桥,使它们能够联通,有 1296 种建桥方案。
.............
回复 支持 反对

使用道具 举报

发表于 2019-11-24 17:22 | 显示全部楼层
本帖最后由 王守恩 于 2019-11-24 17:41 编辑

在五座岛屿之间建造四座桥,使它们能够联通,请问有几种建桥方案?

1,给 5 个岛编上号:1,2,3,4,5;
     给10座桥编上号:12,13,14,15,23,24,25,34,35,45。
     每种建桥方案就是在这10座桥中选择合适的4座桥(8个数字),
2,我们注意到:在满意的答案里,每个岛出现的次数肯定是相同的,
    我们只要统计 “1” 出现的次数就可以了
    “1”出现4个:4×1=12,13,14,15出现1次
    “1”出现3个:3×4×3=12,13,14,12,13,15,12,14,15,13,14,15 各出现3次,
    “1”出现2个:2×6×8=12,13,12,14,12,15,13,14,13,15,14,15 各出现8次,
    “1”出现1个:1×4×16=12,13,14,15 各出现16次。
     4×1+3×4×3+2×6×8+1×4×16=200
     200×5÷8=125,可以有 125 种建桥方案。
回复 支持 反对

使用道具 举报

发表于 2019-11-24 19:01 | 显示全部楼层
:lol典型的图论问题。成熟的算法。
回复 支持 反对

使用道具 举报

发表于 2019-11-25 04:00 | 显示全部楼层
图老师 发表于 2019-11-24 19:01
典型的图论问题。成熟的算法。

在六座岛屿之间建造五座桥,使它们能够联通,请问有几种建桥方案?

1,给 6 个岛编上号:1,2,3,4,5,6;
     给15座桥编上号:12,13,14,15,16,23,24,25,26,34,35,36,45,46,56。
     每种建桥方案就是在这15座桥中选择合适的5座桥(10个数字),
2,我们注意到:在满意的答案里,每个岛出现的次数肯定是相同的,
    我们只要统计 “1” 出现的次数就可以了
    “1”出现5个:5×1=12,13,14,15,16出现1次
    “1”出现4个:4×5×4=12,13,14,15,12,13,14,16,12,13,15,16,12,14,15,16,13,14,15,16 各出现4次,
    “1”出现3个:3×10×15=12,13,14,12,13,15,12,13,16,12,14,15,12,14,16,12,15,16,13,14,15,13,14,16,13,15,16,14,15,16 各出现3次,
    “1”出现2个:2×10×50=12,13,12,14,12,15,12,16,13,14,13,15,13,16,14,15,14,16,15,16 各出现50次,
    “1”出现1个:1×5×125=12,13,14,15,16 各出现125次。
     5×1+4×5×4+3×10×15+2×10×50+1×5×125=2160
     2160×6(个岛)÷10(10个数字5座桥)=1296,可以有 1296 种建桥方案。
补充:
1,“1”出现4个与“1”出现1个是互补的一对;“1”出现3个与“1”出现2个是互补的一对。
2,可以这样来理解 “1”:1×5×125=12,13,14,15,16 各出现125次,
     5岛4桥已经有125种方案,我们把 “125” 里的每个数字都+1,变成没有”1“的方案,......
回复 支持 反对

使用道具 举报

发表于 2019-11-29 13:24 | 显示全部楼层
图老师 发表于 2019-11-24 19:01
典型的图论问题。成熟的算法。

在 2 座岛屿之间建造 1 座桥,使它们能够联通,有 1 种建桥方案。
在 3 座岛屿之间建造 2 座桥,使它们能够联通,有 3 种建桥方案。
在 4 座岛屿之间建造 3 座桥,使它们能够联通,有 16 种建桥方案。
在 5 座岛屿之间建造 4 座桥,使它们能够联通,有 125 种建桥方案。
在 6 座岛屿之间建造 5 座桥,使它们能够联通,有 1296 种建桥方案。
这串数是: 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691,
61917364224, 1792160394037, 56693912375296, 1946195068359375, 72057594037927936,
2862423051509815793, 121439531096594251776, 5480386857784802185939,..............................
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2019-12-12 06:55 , Processed in 0.312737 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表