ベ断桥烟雨ミの学习笔记 ベ断桥烟雨ミの学习笔记
首页
机器学习
技术杂谈
  • Qlittle - 一个笔记Blog (opens new window)
  • 冰白寒祭的博客 (opens new window)
GitHub (opens new window)
首页
机器学习
技术杂谈
  • Qlittle - 一个笔记Blog (opens new window)
  • 冰白寒祭的博客 (opens new window)
GitHub (opens new window)
  • Python

    • 函数式编程

      • 纯度、一等实体和不变性
      • 使用递归
      • 高阶函数和装饰器模式
      • λ表达式及其组合
      • 运算符即函数,偏函数和柯里化
      • 列表处理中的工具
      • Python中的惰性计算
    • 回溯法解九数字问题
      • 问题再现
      • 解题思路
      • 算法示例
    • Jupyter Notebook 更换默认 Shell
    • 虚假的布尔类型
    • Selenium 腾讯企业邮箱自动发信
    • Pdb 命令行调试器
  • VSCode

  • Git

  • 技术杂谈
  • Python
Dragon1573
2021-10-05
目录

回溯法解九数字问题

# 问题再现

求一个九位数 M ,已知 M 的各位数由不重复的 1∼9 组成,对于 m∈{2,3,4,⋯,9} ,数 M 左侧的 m 位数都是 m 的倍数。

# 解题思路

左侧 m 的倍数,那么我们能否使用回溯法:从左侧开始,每次向右确定1位数,若从某一位数开始无法找到满足条件的前 m 位数,则向左删除最后一位数并尝试其他值?这样,我们可以减少『无脑枚举』产生的大量无用值,更快地得到结果。

# 算法示例

def check(prev_nums: list, number: int) -> bool:
    ''' 判断当前数位是否满足题目要求 '''

    # 当前数位的数字不能存在于前序数位中
    is_contained = (str(number) not in prev_nums)

    # 前k位数必须能被k整除
    is_zero = (
        (10 * int(''.join(prev_nums)) + number) % len(prev_nums) == 0
    )

    # 同时满足以上2个条件才为真
    return (is_contained and is_zero)


def search_num(prev_nums=['0']):
    ''' 递归搜索数值 '''

    # 遍历数字1~9
    for k in range(1, 10):
        # 检查是否满足要求
        if check(prev_nums, k):
            # 追加此数值
            prev_nums.append(str(k))

            # 如果已经求出了指定位数且满足条件的要求
            if len(prev_nums) - 1 == 9:
                # 返回最终的k位数
                return int(''.join(prev_nums))
            else:
                # 否则继续检索下一位
                temp = search_num(prev_nums)

                # 如果下一位存在可行数值
                if temp is not None:
                    # 返回下一位的检索结果
                    return temp

    # 当前数位没有可行结果,移除上一位,重新检索
    prev_nums.pop()


if __name__ == "__main__":
    ''' 主函数 '''
    print(search_num())
上次更新: 2022/12/30, 20:26:06
Python中的惰性计算
Jupyter Notebook 更换默认 Shell

← Python中的惰性计算 Jupyter Notebook 更换默认 Shell→

Theme by Vdoing | Copyright © 2021-2023 Dragon1573 | CC-BY-SA 4.0
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式