找回密码
 欢迎注册
查看: 758|回复: 30

[讨论] 多彩的圆山

[复制链接]
发表于 2025-3-9 11:16:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
多彩的圆山染色方案数求解
多彩的圆山.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-3-9 11:45:55 来自手机 | 显示全部楼层
去掉最下面一层,圆山会形成一些不同数目的山林,于是就可以递归求没有染色的情况了。
而加上染色情况,那么分类除了最下面一层圆的数目,还需要加上颜色分类了,状态数目不少。

比如一阶圆山只有一个分类,底层一个圆,颜色a.
二阶圆山也只有一类,底层两圆,颜色ab
三阶圆山有三类,一类底层两圆,颜色ab,另外两类底层三圆,颜色分别aba和abc
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-3-9 12:06:31 来自手机 | 显示全部楼层
染色数目之和最底下两层分布有关系,最底层的数目加上第二层的数目决定了染色方案数。染色方案为3乘上2的幂,而这个2的幂次应该就是两层数目差。
所以动归可以仅使用最底层的数目加第二层的数目进行分类,这样复杂度就相对比较容易控制了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2025-3-9 12:28:37 | 显示全部楼层
mathe 发表于 2025-3-9 12:06
染色数目之和最底下两层分布有关系,最底层的数目加上第二层的段数决定了染色方案数。
所以动归可以仅使用 ...

是的,但当n较大时,可以行成3行,4行……多行的情况,有的层中圆可以分开形成几个小山,小山上又有小山。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2025-3-9 12:31:27 | 显示全部楼层
这个也是一道国外求算法的难题,应该比砌砖墙那道题更复杂一些,和我前面发的求平衡雕塑那道难度差不多。

点评

两题区别很大。平行雕塑那道题看上去没啥技巧,当然题目最终要求规模也不大,应该穷举即可。  发表于 2025-3-9 12:49
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2025-3-9 12:53:53 | 显示全部楼层
圆山造型方式举例
圆山示例.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-3-9 13:44:04 | 显示全部楼层
定义F(n,k)为总共n个圆盘,底层k个圆盘不考虑染色的方案数目。

F(1,1)=1, T(1)=3 (T(1)比较特殊)
F(2,2)=1, T(2)=6
n=3,   
   i)第一层为3, F(3,3)=1, T(3)+=3*2*2=12
   ii)第一层为2,F(3,2)=1,上面余一个, 上面只能放F(1,1),T(3)+=3*2=6。
   所以T(3)=18
n=4
  i)第一层为4, F(4,4)=1, T(4)+=3*2^3=24
  ii)第一层为3,余下1个,只能在上面放F(1,1),有两种不同选择位置,F(4,3)=2, 染色方案3*2^2=12, 共2*12=24种
  iii)第一层为2,余下2两个,由于两个放的对象最多底为1,底为1的只能F(1,1)所以不合格,淘汰
故T(4)=48
n=5
  i)第一层为5,F(5,5)=1, T(5)+=3*2^4=48
ii)第一层为4,余下1个有三种位置,F(5,4)=3, T(5)+=3*(3*2^3)=72
iii)第一层为3,余下2个圆盘2个位置,只能放F(2,2)一种选择,由于F(2,2)=1,所以F(5,3)=1,T(5)+=3*2*1 (第2层连续k个盘子会导致连乘种k-1个2变1)
   由此T(5)=126

点评

思路好清晰,有条理。看来总方案数很快会攻克。  发表于 2025-3-9 13:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-3-9 16:08:52 | 显示全部楼层
所以对于本题,关键还是先计算所有的F(n,k), 其中\(k\le n\le \frac{k(k+1)}2\),而且对于给定的k,其中n可以取到的范围是稀疏的。
我们可以再手工计算几层,比如
n=6
第一层为6的情况很类似,F(6,6)=1,F(6,5)=4.
而第一层只有4个圆的情况,余下两个圆三格位子,由于n=2,只有F(2,2)=1, n=1只有F(1,1)=1,可以放一个F(2,2)两种位置选择或两个F(1,1)一种选择(中间留一个空),对应
   。     。
。 。 。 。
所以得出F(6,4)=3, 但是计算染色方案时,它们对T(6)的贡献不同,其中使用F(2,2)的两种方案,由于第二层存在两个连续格子,颜色选择为3*2*2*1=12,而对于使用F(1,1)的一种方案,颜色选择为3*2*2*2=24.
而第一层使用3个圆的情况,余下3个圆两个位置,只有F(3,2)=1可用,所以F(6,3)=1. 颜色选择为3*2*1=6
而第一层使用2两个圆,余下4个圆1个位置,由于1个位置最多消耗一个圆,已经位置不够,淘汰。

n=7,
同样我们先考虑第一层5个圆情况,余下两个圆4个位置,同样可以选择F(2,2)或F(1,1)+F(1,1). 其中F(2,2)有三个位置可以选择,F(1,1)+F(1,1),相当于在4个空位选择两个不相邻的位置,我们想象每个圆后面捆绑了一个空位,也就时每个圆占两个位置,而最右边位置可以捆绑一个不存在的空位,所以是\(C_{4+1-2}^2=3\)种选择。也就是F(7,5)=3+3=6, 而前三种染色方案为3*2^3*1^1=24,后三种染色方案为3*2^4=48.
第一层4个圆情况,留下三个圆3个位置。所以可以选择F(3,3), F(3,2). 而将n拆为2+1或1+1+1都会导致3个位置不够(3个位置拆分只能为1+1,因为中间要留空)。其中F(3,3)只有一种选择,3个连续圆是的颜色数相乘中两个2变为1,所以颜色数是3*2^1*1^2, 而F(3,2)有两种位置选择,颜色数为3*2^2*1.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-3-9 16:17:14 | 显示全部楼层
所以一般情况我们为了计算
F(n,k) 我们需要将余下n-k个圆放在k-1个位置上,我们需要将n-k个圆划分为最多k/2组,而且其中组数比较多时,每组可用圆的数目也会比较少。
假设d组,这d组各自拥有圆\(x_1,x_2,...,x_d\),底的宽度为\(y_1,y_2,...,y_d\),于是要求
\(y_1+y_2+...+y_d\le k-d\)
\(1\le y_i \le x_i \le \frac{y_i(y_i+1}2\)
\(x_1+x_2+...+x_d=n-k \le \frac{y_1(y_1+1)}2+\frac{y_2(y_2+1)}2+...+\frac{y_d(y_d+1)}2\)
我们可以利用上面条件先搜索合法的有序的\(y_i\),然后再搜索合适的\(x_i\)让它们满足最后一行等式关系,最后再排列组合考虑它们的位置关系。
最后当然还要检查每个对应的\(F(x_i,y_i)\)非零
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2025-3-9 17:01:01 来自手机 | 显示全部楼层
感觉求圆山布局的方案数比求它们的着色方案容易些。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2025-3-22 18:14 , Processed in 0.085899 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

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