Python实现火柴棍摆数：最小数字求解困境求助

首先明确数字对应的火柴棍数量（闹钟显示风格）：

最大数字构造思路 #

这个逻辑非常直接：位数越多，数字越大，所以优先使用火柴棍最少的数字1（2根）：

• 计算最大位数：k_max = n // 2，剩余火柴棍r = n % 2
• 如果r=0：直接构造k_max个1，即字符串'1'*k_max
• 如果r=1：剩余1根无法单独用，把其中一个1换成7（3根），即字符串'7' + '1'*(k_max-1)

例：n=5 → 71，n=7 → 711，n=4 → 11

最小数字构造思路 #

暴力枚举所有组合完全不可行（n=100时会生成50位数字，组合数爆炸），需用贪心逐位构造，核心是在所有可能的位数中，找到对应最小的数字，再取全局最小。

步骤1：确定所有可能的位数范围 #

• 最大位数k_max = n // 2（全用1的情况）
• 最小位数k_min = (n + 6) // 7（向上取整，全用8的情况）
• 遍历k从k_min到k_max，对每个k构造该位数下的最小数字，最后取所有结果中的最小值

步骤2：对单个k构造最小数字 #

2.1 确定第一位数字

第一位不能为0，按火柴数从小到大+对应数字从小到大的顺序尝试候选：
1(2根) → 7(3根) → 4(4根) → 2(5根) → 6(6根) → 8(7根)

对每个候选第一位的火柴数s1，计算剩余火柴数m = n - s1，需满足：
2*(k-1) ≤ m ≤7*(k-1)（剩余k-1位，每位至少用2根，最多用7根）
满足条件则进入剩余位数构造。

2.2 构造剩余k-1位数字

从左到右逐位构造，每一位优先选最小的数字，同时满足：

• 当前数字的火柴数s
• 剩余火柴数m_remaining = m - s
• 剩余t = (k-1) - 当前已构造位数，需满足2*t ≤ m_remaining ≤7*t

找到第一个满足条件的数字后，更新剩余火柴数，继续构造下一位。

2.3 取当前k的最小数字

因为第一位是从小到大尝试的，第一个可行的组合就是该k下的最小数字。

步骤3：全局最小数字 #

比较所有k对应的最小数字，取其中数值最小的作为最终结果。

例子验证 #

• n=7：
  • k范围：1~3
  • k=1：数字8（7根）
  • k=2：第一位选1（2根），剩余5根选最小数字2，得到12
  • k=3：最小数字是117
  • 全局最小为12
• n=8：
  • k范围：2~4
  • k=2：第一位选1（2根），剩余6根选最小数字0，得到10
  • k=3：最小数字是114
  • k=4：数字1111
  • 全局最小为10

内容的提问来源于stack exchange，提问作者Lucky