找回密码
 欢迎注册
楼主: 王守恩

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

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

--------------------------------------------------------------------------------
python3.6程序运行 21.166463375091553 秒。
--------------------------------------------------------------------------------
>>>
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-28 22:57:35 | 显示全部楼层
northwolves 发表于 2019-11-18 23:54
$a_n=n^(n-2)$?怎么证明?

Cayley凯莱定理
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-11-29 20:30:28 | 显示全部楼层

受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]];

  14. If[(arr[[x]]==1) || (arr[[y]]==1),arr[[x]]=1;
  15. arr[[y]]=1](*;
  16. Print["i=",i," j=",j," arr=",arr]*),
  17. {j,1,Length[line]}],
  18. {i,1,Length[line]}];
  19. x=Sum[arr[[i]],{i,1,Length[line]+1}];
  20. If[ x !=(Length[line]+1),ret=False];
  21. 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. resline;(*如果去掉分号则显示各个建桥方案*)
  33. Print["=== ==="]
  34. time2=AbsoluteTime[];
  35. Print[ToString[nn]<>"岛"<>ToString[nn-1]<>"桥全联通建桥方案数=
  36. "<>ToString[Length[resline]]]
  37. 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

点评

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

评分

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

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-11-30 07:07:04 | 显示全部楼层
dlpg070 发表于 2019-11-29 20:30
受markfang2050鼓舞,
剔除的方法,在岛数较少时,还是可以接受的,
庆幸今天偶然机会,对特别丑的代码 ...

如何用简单的语言,把题目与乘法原理扯上号?
又:这答案可以用多项式系数来解读吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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]];

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

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


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

  51. For[i=1,i<=Length[resline],i++,
  52. lines={};
  53. m=resline[[i]];

  54. Do[AppendTo[lines,fm[j,m]],{j,1,Length[m]}];
  55. AppendTo[listgra,gra[lines,pts,i]]
  56. ];

  57. out=Table[
  58. listgra[[i]],
  59. {i,1,Min[50,Length[listgra]]}](* ;-不显示图形 ,50是任意选择值 *)
  60. (*为了在图形太多时,选取显示少量 (50)样本*)


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

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

点评

赞  发表于 2019-11-30 17:26
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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 种建桥方案。
................
看着这些美妙的数字,您不想试一试?!

点评

你这个是没有意义的工作。  发表于 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\)

点评

这玩意不就是二项式定理  发表于 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次。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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“吧
有了这些算法,递推公式就归纳出来了,
虽然特繁杂,但独特,好玩儿



毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-10-10 21:33 , Processed in 0.027093 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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