[已解决]Python：每日一题 256

__mrsq__

克里斯保罗 发表于 2019-10-15 13:12
看不太懂，可以解释一下吗

有点像最短路径法，把输入数值到小于输入数值的值和到达这个值的最小步数存在queue里面，然后把这个值标记为访问过了，因为后面再次访问这个值的步数都大于等于第一次访问这个值所用的步数，所以就没必要再次访问了。比如13 到 12是一步 13-1，13到9也是一步 13-4，13到4也是一步 13-9。然后第二次外层循环依次再对12 9 4做同样的操作把没访问过的remain存在queue里，内部循环在对9操作的时候的时候发现9-3*3为0，输出 step+1就是2程序结束

549491637

两种方法：递归与迭代，前者在递归允许范围内效率更高，后者没有层数限制
递归：
import math

def Pingfang(numb,max_gen,count=0):
    if numb >= max_gen**2:
        return Pingfang(numb-max_gen**2,max_gen,count+1)
    elif numb == 0:
        return count
    else:
        return Pingfang(numb,max_gen-1,count)

def Juece(numb):
    max_gen = int(math.sqrt(numb))
    numb_list = []
    while True:
        if max_gen**2 < numb/3:
            return min(numb_list)
        numb_list.append(Pingfang(numb,max_gen))
        max_gen -= 1

迭代：
import math

def Pingfang(numb,max_gen,count=0):
    while True:
        if numb >= max_gen**2:
            numb -= max_gen**2
            count += 1
        elif numb == 0:
            return count
        else:
            max_gen -= 1

def Juece(numb):
    max_gen = int(math.sqrt(numb))
    numb_list = []
    while True:
        if max_gen**2 < numb/3:
            return min(numb_list)
        numb_list.append(Pingfang(numb,max_gen))
        max_gen -= 1
测试请使用Juece函数

学习者q

啦啦啦