python - 以pythonic方式实现递归
问题描述
我有一个递归:
C(n) = min{
C(n/3) + 1 if n ⋮ 3,
C(n/2) + 1 if n ⋮ 2,
C(n-1) + 1
}
基本情况是
C(n) = 0 for n <= 1
如何以 pythonic 方式实现此递归?这是解决我能够成功解决的给定问题的尝试,但我觉得也需要实现递归解决方案。
Problem 1: Primitive Calculator
You are given a primitive calculator that can perform the following three operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x. Your goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.
Problem Description
Task. Given an integer n, compute the minimum number of operations needed to obtain the number n starting from the number 1.
Output Format. In the first line, output the minimum number k of operations needed to get n from 1. In the second line output a sequence of intermediate numbers. That is, the second line should contain positive integers a0, a2,…, a(k-1) such that a0 =1, a(k-1) =n and for all 0≤i<k-1, ai+1 is equal to either ai + 1, 2 x ai, or 3 x ai. If there are many such sequences, output any one of them.
Sample 1.
Input: 5
Output:
3
1 2 4 5
Explanation:
Here, we first multiply 1 by 2 two times and then add 1 ( ((1 x 2) x 2) + 1). Another possibility is to first multiply by 3 and then add 1 two times. Hence “1 3 4 5” is also a valid output in this case.
Sample 2:
Input: 96234
Output:
14
1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
Explanation:
Again, another valid output in this case is “1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234”.
Your goal is to design and implement a dynamic programming solution for this problem. A natural subproblem in this case is the following: C(n) is the minimum number of operations required to obtain n from 1 (using the three primitive operations). How to express C(n) through C(n/3), C(n/2), C(n-1)?
解决方案
def C(n):
if n <= 1:
return 0
m= C(n-1)
if n % 3 == 0:
m= min(m, C(n/3))
if n % 2 == 0:
m= min(m, C(n/2))
return m + 1
可能值得考虑记忆化。
Cache= {}
def C(n):
global Cache
if n <= 1:
return 0
try:
return Cache[n]
except:
m= C(n-1)
if n % 3 == 0:
m= min(m, C(n/3))
if n % 2 == 0:
m= min(m, C(n/2))
m+= 1
Cache[n]= m
return m
我不确定首先测试是否更好n <= 1
。
推荐阅读
- docker - 通过 docker-compose 公开 DNS 条目
- java - 无法使用 Java API 从 Google Cloud Storage 下载文件
- python - 使用带有字典值的 INSERT TO sql
- c - 使用 SDL_Rect 创建多个矩形
- android - android:elevation 不显示阴影
- python - TypeError: 'str' 对象在制作 peewee 模型时不可调用
- java - 如何在不引发编译错误的情况下更改不可变字符串值。
- php - 通过内部点击对父用户列表进行排序弹性搜索
- c++ - 在 Visual Studio Code 中编译 C++11
- html - 如何使图像适合视口比例