数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【综合大厅】 › 开心茶馆 › 在 6 座岛屿之间建造 5 座桥，使它们能够联通，请问有几 ...
1234下一页
返回列表 发新帖
楼主: 王守恩

[转载] 在 6 座岛屿之间建造 5 座桥，使它们能够联通，请问有几种建桥方案？

[复制链接]
markfang2050
发表于 2019-11-28 22:50:01 | 显示全部楼层
=======================华丽的分割线============================
8座岛屿之间建造7座桥，使它们能够联通，共有262144种建桥方案。

--------------------------------------------------------------------------------
python3.6程序运行 21.166463375091553 秒。
--------------------------------------------------------------------------------
>>>
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

markfang2050
发表于 2019-11-28 22:57:35 | 显示全部楼层
northwolves 发表于 2019-11-18 23:54
$a_n=n^(n-2)$?怎么证明？

Cayley凯莱定理
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

dlpg070
发表于 2019-11-29 20:30:28 | 显示全部楼层
markfang2050 发表于 2019-11-28 22:57
Cayley凯莱定理

受markfang2050鼓舞，
剔除的方法，在岛数较少时，还是可以接受的,
庆幸今天偶然机会，对特别丑的代码做了些整容,丑得有些可爱

例如:
6岛5桥全联通建桥方案数= 1296
耗时 0.4520259 不显示方案 / 0.4830276 显示方案
速度尚可
isok函数还需要优化，7岛6桥 8岛7桥时特别慢!!!
贴出代码，请指正

  1. Clear["Global`*"];
  2. (*判断 line 是否全联通，ok 待优化 ，改进 True/False
  3. 各岛建桥情况： arr[] 1:联通 2:未联通，有另外1组 0:无桥 *)
  4. isok[line_]:=isok[list]=Module[{ret=True,x=0,y=0,
  5. arr=Array[0&,{Length[line]+1}]},
  6. x=line[[1,1]];
  7. y=line[[1,2]];
  8. arr[[x]]=1;
  9. arr[[y]]=1;
  10. Table[
  11. Table[
  12. x=line[[j,1]];
  13. y=line[[j,2]];

  15. If[(arr[[x]]==1) || (arr[[y]]==1),arr[[x]]=1;
  16. arr[[y]]=1](*;
  17. Print["i=",i," j=",j," arr=",arr]*),
  18. {j,1,Length[line]}],
  19. {i,1,Length[line]}];
  20. x=Sum[arr[[i]],{i,1,Length[line]+1}];
  21. If[ x !=(Length[line]+1),ret=False];
  22. ret(*{x,arr}*)];(* end *)

  24. time1=AbsoluteTime[];(*计算时间开始*)
  25. nn=6;
  26. resline={};
  27. tup2=With[{n=nn,m=2},Subsets[Range[n],{m}]];
  28. Print["tup2 长度= ",Length[tup2]," ",tup2]
  29. tup2line=With[{n=Length[tup2],m=nn-1},Subsets[tup2,{m}]];
  30. Print["tup2line 长度= ",Length[tup2line]]
  31. Do[(*i *)line=tup2line[[i]];
  32. If[isok[line]==True,AppendTo[resline,line]]
  33. ,{i,1,Length[tup2line]}]
  34. resline;(*如果去掉分号则显示各个建桥方案*)
  35. Print["=== ==="]
  36. time2=AbsoluteTime[];
  37. Print[ToString[nn]<>"岛"<>ToString[nn-1]<>"桥全联通建桥方案数=
  38. "<>ToString[Length[resline]]]
  39. Print["耗时 ",time2-time1]
复制代码


输出:
tup2 长度= 15 {{1,2},{1,3},{1,4},{1,5},{1,6},{2,3},{2,4},{2,5},{2,6},{3,4},{3,5},{3,6},{4,5},{4,6},{5,6}}
tup2line 长度= 3003
=== ===
6岛5桥全联通建桥方案数= 1296
耗时 0.4470256

点评

markfang2050
缺个画图的。最好把画图的语句加上。  发表于 2019-11-29 20:45
markfang2050
赞一个！  发表于 2019-11-29 20:39

评分

参与人数 1威望 +1 金币 +1 贡献 +2 鲜花 +2 收起 理由
markfang2050 + 1 + 1 + 2 + 2

查看全部评分

毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 2 反对 0

使用道具 举报

王守恩
 楼主| 发表于 2019-11-30 07:07:04 | 显示全部楼层
dlpg070 发表于 2019-11-29 20:30
受markfang2050鼓舞，
剔除的方法，在岛数较少时，还是可以接受的,
庆幸今天偶然机会，对特别丑的代码 ...

如何用简单的语言，把题目与乘法原理扯上号？
又：这答案可以用多项式系数来解读吗？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

dlpg070
发表于 2019-11-30 08:33:58 | 显示全部楼层
本帖最后由 dlpg070 于 2019-11-30 08:45 编辑
dlpg070 发表于 2019-11-29 20:30
受markfang2050鼓舞，
剔除的方法，在岛数较少时，还是可以接受的,
庆幸今天偶然机会，对特别丑的代码 ...


画图部分只是一个自制简易视觉调试工具，
解题完毕，则其任务就结束了
应要求把画图部分附上，没什么特色，倒挺好玩的(集中在代码尾部，测试通过)

  1. Clear["Global`*"];
  2. (*判断 line 是否全联通，ok 待优化 ，改进 True/False 各岛建桥情况： arr[] 1:联通 2:未联通，有另外1组 0:无桥 *)
  3. isok[line_]:=isok[list]=Module[{ret=True,x=0,y=0, arr=Array[0&,{Length[line]+1}]},
  4. x=line[[1,1]];
  5. y=line[[1,2]];
  6. arr[[x]]=1;
  7. arr[[y]]=1;
  8. Table[
  9. Table[
  10. x=line[[j,1]];
  11. y=line[[j,2]];

  13. If[(arr[[x]]==1) || (arr[[y]]==1),arr[[x]]=1;
  14. arr[[y]]=1](*;
  15. Print["i=",i," j=",j," arr=",arr]*),
  16. {j,1,Length[line]}],
  17. {i,1,Length[line]}];
  18. x=Sum[arr[[i]],{i,1,Length[line]+1}];
  19. If[ x !=(Length[line]+1),ret=False];
  20. ret(*{x,arr}*)];(* end *)

  22. time1=AbsoluteTime[];(*#计算时间开始*)
  23. nn=6;(* 岛数 *)
  24. resline={};
  25. tup2=With[{n=nn,m=2},Subsets[Range[n],{m}]];
  26. Print["tup2 长度= ",Length[tup2]," ",tup2]
  27. tup2line=With[{n=Length[tup2],m=nn-1},Subsets[tup2,{m}]];
  28. Print["tup2line 长度= ",Length[tup2line]]
  29. Do[(*i *)line=tup2line[[i]];
  30. If[isok[line]==True,AppendTo[resline,line]]
  31. ,{i,1,Length[tup2line]}]
  32. Grid[Table[{j,resline[[j]]},{j,1,Length[resline]}]];
  33. (*如果去掉分号则格式化显示各个建桥方案*)
  34. Print["=== ==="]
  35. time2=AbsoluteTime[];
  36. Print[ToString[nn]<>"岛"<>ToString[nn-1]<>"桥全联通建桥方案数= "<>ToString[Length[resline]]]
  37. (* 绘图用 简单的视觉调试工具*)
  38. pts=Table[{Sin[Pi*2/nn*i],Cos[Pi*2/nn*i]},{i,0,nn-1}];
  39. (*点序号变坐标 岛桥专用,已修改 *)
  40. fm[n_,line_]:=Module[{i=n,lst={},x=0,y=0},
  41. x=line[[i,1]];
  42. y=line[[i,2]];
  43. AppendTo[lst,{pts[[x]],pts[[y]]}];
  44. lst
  45. ];
  46. (*画一张图*)
  47. gra[lines_,pts_,xh_]:=Graphics[{Opacity[0.7],Green,Circle[{0,0},1.0],Table[{Red,Disk[pts[[i]],0.1],
  48. Opacity[1],Black,Text[Style[ToString[i],Bold,FontSize->10],pts[[i]]]},{i,1,nn}],
  49.      Black,Arrow[#]&/@lines,Disk[{0,0},0.05]},Axes->False,PlotRange->{-1.1,1.1},
  50. PlotLabel->Style[Framed["  "<>ToString[xh]<>"  "],10,Blue,Background->Yellow],ImageSize->100]


  53. listgra={};(*图形列表*)
  54. lines={};(*连线坐标*)

  56. For[i=1,i<=Length[resline],i++,
  57. lines={};
  58. m=resline[[i]];

  60. Do[AppendTo[lines,fm[j,m]],{j,1,Length[m]}];
  61. AppendTo[listgra,gra[lines,pts,i]]
  62. ];

  64. out=Table[
  65. listgra[[i]],
  66. {i,1,Min[50,Length[listgra]]}](* ;-不显示图形 ，50是任意选择值 *)
  67. (*为了在图形太多时，选取显示少量 （50）样本*)


  70. Export[ToString[nn]<>"岛"<>ToString[nn-1]<>"桥.png",out];
  71. Print["测试 Import:"]

  73. Import[ToString[nn]<>"岛"<>ToString[nn-1]<>"桥.png"]
  74. Print["耗时 ",time2-time1]
  75. Print["--- rnd ---"]
复制代码

点评

markfang2050
赞  发表于 2019-11-30 17:26
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 1 反对 0

使用道具 举报

王守恩
 楼主| 发表于 2019-11-30 15:15:26 | 显示全部楼层
王守恩 发表于 2019-11-24 21:46
在六座岛屿之间建造五座桥，使它们能够联通，请问有几种建桥方案？

1，给 6 个岛编上号：1，2，3，4 ...


接 7 楼。
   
1×1=1
   1×2(个岛)÷2(个数字1座桥)=1，可以有 1 种建桥方案。

2×1+1×2×1=4
   4×3(个岛)÷4(个数字2座桥)=3，可以有 3 种建桥方案。

3×1+2×3×2+1×3×3=24
   24×4(个岛)÷6(个数字3座桥)=16，可以有 16 种建桥方案。

4×1+3×4×3+2×6×8+1×4×16=200
   200×5(个岛)÷8(个数字4座桥)=125，可以有 125 种建桥方案。

5×1+4×5×4+3×10×15+2×10×50+1×5×125=2160
   2160×6(个岛)÷10(个数字5座桥)=1296，可以有 1296 种建桥方案。

6×1+5×6×5+4×15×24+3×20×108+2×15×432+1×6×1296=28812
   28812×7(个岛)÷12(个数字6座桥)=16807，可以有 16807 种建桥方案。

7×1+6×7×6+5×21×35+4×35×196+3×35×1029+2×21×4802+1×7×16807=458752
   458752×8(个岛)÷14(个数字7座桥)=262144，可以有 262144 种建桥方案。

8×1+7×8×7+6×28×48+5×56×320+4×70×2048+3×56×12288+2×28×65536+1×8×262144=8503056
   8503050×9(个岛)÷16(个数字8座桥)=4782969，可以有 4782969 种建桥方案。

9×1+8×9×8+7×36×63+6×84×486+5×126×3645+4×126×26244+3×84×177147+2×36×1062882+1×9×4782969=180000000
   180000000×10(个岛)÷18(个数字9座桥)=100000000，可以有 100000000 种建桥方案。
................
看着这些美妙的数字，您不想试一试？！

点评

markfang2050
你这个是没有意义的工作。  发表于 2019-11-30 17:27
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
 楼主| 发表于 2019-11-30 17:28:09 | 显示全部楼层
本帖最后由 王守恩 于 2019-11-30 17:48 编辑
王守恩 发表于 2019-11-30 15:15
接 14 楼。
   
1×1=1


接 26 楼。
   
1×1=1
   2 岛 1 桥有 1 种建桥方案。

2×1+1×1=3
   3 岛 2 桥有 3 种建桥方案。

3×3+3×2+1×1=16
   4 岛 3 桥有 16 种建桥方案。

4×16+6×8+4×3+1×1=125
   5 岛 4 桥有 125 种建桥方案。
   
5×125+10×50+10×15+5×4+1×1=1296
   6 岛 5 桥有 1296 种建桥方案。

6×1296+15×432+20×108+15×24+6×5+1×1=16807
   7 岛 6 桥有 16807 种建桥方案。

7×16807+21×4802+35×1029+35×196+21×35+7×6+1×1=262144
   8 岛 7 桥有 262144 种建桥方案。

8×262144+28×65536+56×12288+70×2048+56×320+28×48+8×7+1×1=4782969
   9 岛 8 桥有 4782969 种建桥方案。

9×4782969+36×1062882+84×177147+126×26244+126×3645+84×486+36×63+9×8+1×1=100000000
   10 岛 9 桥有 100000000 种建桥方案。
...........
9×4782969+36×1062882+84×177147+126×26244+126×3645+84×486+36×63+9×8+1×1=100000000
  表示 ：1个“1” + 2个“1” + 3个“1” + 4个“1” + 5个“1” + 6个“1” + 7个“1” + 8个“1” + 9个“1” =100000000
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
 楼主| 发表于 2019-11-30 19:55:37 | 显示全部楼层
王守恩 发表于 2019-11-30 17:28
接 26 楼。
   
1×1=1

求证：

\(\frac{8!*9^8}{0!*8!}+\frac{8!*9^7}{1!*7!}+\frac{8!*9^6}{2!*6!}+\frac{8!*9^5}{3!*5!}+\frac{8!*9^4}{4!*4!}+\frac{8!*9^3}{5!*3!}+\frac{8!*9^2}{6!*2!}+\frac{8!*9^1}{7!*1!}+\frac{8!*9^0}{8!*0!}=10^8\)

点评

lsr314
这玩意不就是二项式定理  发表于 2019-12-1 13:55
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
 楼主| 发表于 2019-12-1 18:05:15 | 显示全部楼层
王守恩 发表于 2019-11-30 19:55
求证：

\(\frac{8!*9^8}{0!*8!}+\frac{8!*9^7}{1!*7!}+\frac{8!*9^6}{2!*6!}+\frac{8!*9^5}{3!*5!}+\f ...

谢谢  lsr314！
在 6 座岛屿之间建造 5 座桥，使它们能够联通，请问有几种建桥方案？
     答案可以用展开多项式系数思想来解读。
     给 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个数字)，
     在5座桥(10个数字)里，肯定会出现数字 “1”，
我们只要统计 “1” 出现的次数就可以了，
    展开多项式 (5+x)^4
    (5+x)^4=625 + 500 x + 150 x^2 + 20 x^3 + x^4
    系数合计：625 + 500 + 150 + 20 + 1 =1296，可以有 1296 种建桥方案。
出现 “1” 有5种可能，其中：
    出现1个 “1”：625次，
    出现2个 “1”：500次，
    出现3个 “1”：150次，
    出现4个 “1”：20次，
    出现5个 “1”：1次。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

dlpg070
发表于 2019-12-2 09:06:29 | 显示全部楼层
王守恩 发表于 2019-11-30 17:28
接 26 楼。
   
1×1=1

回复王守恩 27#
您发了2#，5#，7#，26#，27#大量数据，不怀疑其正确性，但多数不能完全理解
直到看见27# "这些美妙的数字",感到太奇妙了
这里隐含着独一无二的 通项的递推公式
希望能说明其中部分乘数的算法
例如:
6×1296+15×432+20×108+15×24+6×5+1×1=16807
                 ---          ---          --      --      --  
   7 岛 6 桥有 16807 种建桥方案。
即 432，108，24，5，1的计算方法
显然不是统计“1“吧
有了这些算法，递推公式就归纳出来了，
虽然特繁杂，但独特,好玩儿



毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-4-26 22:10 , Processed in 0.058636 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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