征解问题[10] 计数问题

《征解问题[10] 计数问题》有2条回应

1. Steven说：

   2025年7月26日 下午5:16

   我用递归搜索的方法来解决这个问题。

   首先分析约束条件：如果当前位是数字x，那么下一位只能是满足|y-x|≤2的数字y。

   对于数字1,2,3,4,5,6,7，每个数字可以跟在哪些数字后面：

   1后面可以放：2,3（|1-2|=1, |1-3|=2）
   2后面可以放：1,3,4（但要排除已用的）
   3后面可以放：1,2,4,5（但要排除已用的）
   4后面可以放：2,3,5,6（但要排除已用的）
   5后面可以放：3,4,6,7（但要排除已用的）
   6后面可以放：4,5,7（但要排除已用的）
   7后面可以放：5,6（但要排除已用的）
   由于首位固定是1，我从第二位开始搜索：

   第二位可以是2或3

   情况1：第二位是2
   按照约束条件逐步搜索，找到以下有效序列：

   [1,2,3,4,5,6,7]
   [1,2,3,4,5,7,6]
   [1,2,3,4,6,5,7]
   [1,2,3,4,6,7,5]
   [1,2,3,5,4,6,7]
   [1,2,3,5,7,6,4]
   [1,2,4,3,5,6,7]
   [1,2,4,3,5,7,6]
   [1,2,4,6,7,5,3]
   情况2：第二位是3
   同样按照约束条件搜索，找到以下有效序列：
   10. [1,3,2,4,5,6,7]
   11. [1,3,2,4,5,7,6]
   12. [1,3,2,4,6,5,7]
   13. [1,3,2,4,6,7,5]
   14. [1,3,5,7,6,4,2]

   验证其中一个序列[1,3,5,7,6,4,2]：

   |1-3|=2≤2 ✓
   |3-5|=2≤2 ✓
   |5-7|=2≤2 ✓
   |7-6|=1≤2 ✓
   |6-4|=2≤2 ✓
   |4-2|=2≤2 ✓
   因此，满足条件的七位正整数共有14个。

   登录以回复
   • Steven说：

     2025年7月26日 下午5:17

     def count_valid_numbers():
     def is_valid_next(current, next_digit):
     return abs(current - next_digit) <= 2

     def dfs(position, last_digit, used):
     if position == 7: # 已经放了7位数字
     return 1

     count = 0
     for digit in range(1, 8):
     if digit not in used and is_valid_next(last_digit, digit):
     count += dfs(position + 1, digit, used | {digit})

     return count

     # 从第二位开始，首位已经是1
     return dfs(1, 1, {1})

     登录以回复