题目：跳石板

题目描述

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......

这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。

例如：

N = 4，M = 24：

4->6->8->12->18->24

于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板

输入描述:

输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

输出描述:

输出小易最少需要跳跃的步数,如果不能到达输出-1

示例1

输入

4 24

输出

自己的解法思路为：建立一个M+1的数组，数组元素为-1，N位置为0，获取N的约数，并且前进，对应到达位置设置为当前步数，代码如下，复杂度过高，没有提交成功：

N,M=[int(each) for each in input().split()]def getNYueShu(n):    mid=n//2    result=[]    for i in range(2,mid+1):        if i not in result:            # 判断是否是约数            if n%i==0:                result.append(i)                j=int(n/i)                if j not in result:                    result.append(j)    return resultdef getCounts(N,M):    # ys=getNYueShu(N)    # ys=sorted(ys,reverse=True)    count=0    step=[-1]*(M+1)    step[N]=0    cur_val=[N]    while cur_val:        next=[]        count+=1        #print(count)        for j in cur_val:            ys=getNYueShu(j)            ys = sorted(ys, reverse=True)            for i in ys:                if j+i<=M and i+j not in next:                    next.append(i+j)        tmp_next=[]        for n in next:            if step[n]==-1:                step[n]=count                tmp_next.append(n)                if n==M:                    break        cur_val=tmp_next    return step[M]print(getCounts(N,M))

参考解法：

def solution(n, m):    divs = [[] for _ in range(m + 1)]    for i in range(2, m + 1):        t=[j for j in range(i + i, m + 1, i)]        for j in range(i + i, m + 1, i):            divs[j].append(i)    value = [m] * (m + 1)    value[n] = 0    for i in range(n, m + 1):        if value[i] < m:            for x in divs[i]:                if i + x < m + 1:                    value[i + x] = min([value[i + x], value[i] + 1])    if value[m] < m:        return value[m]    else:        return -1data = [int(i) for i in input().strip().split()]n = data[0]m = data[1]print(solution(n, m))

理解的思路是：先求出可达位置的约数，然后在接下来的for循环中去设定每个可达位置的最短步数

转载地址：http://xeyai.baihongyu.com/

你可能感兴趣的文章