整数表示

质数的数目

数字转换

# 传入当前可能的数据，输出下一步可能转化的数据 def nextNum(curr): next = [] for i in curr: for j in range(2,int(i ** 0.5) + 1): if i % j == 0: next.extend([i + j , i + i//j]) next.extend([i + 1, i + i]) return list(set(next)) #集合去重 def solve_it(a,b): if a &gt;= b: return -1 curr = [a] step = 1 while b not in curr: curr = nextNum(curr) step += 1 return step - 1 print(solve_it(a,b))

当前和下一步动态变化即可

<a href="http://www.gznb.xyz/posts/pythonTip-88-数字转换/">题解： http://www.gznb.xyz/posts/pythonTip-88-数字转换/</a>

<div style="top: 0px;">﻿﻿</div>主要三个想法1、两头凑，用集合思想，a 走一步可以到的点集叫L，b退一步的点集叫S，但是注意除重，去过的点集要删掉。另外设个上限，如果a出发，走到超过b的点集也要删掉2、a、b很远的时候，a-&gt;2a-&gt;4a-&gt;8a-&gt;这样跑3、只要a比b小，a一点点加一都能到b，所以达不到只有一种情况，就是a&gt;b def d(L,b): &nbsp;&nbsp;&nbsp; D=set([]) &nbsp;&nbsp;&nbsp; for i in L: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for j in range(1,i+1): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i%j==0 and j+i&lt;=b: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; D.add(j+i) &nbsp;&nbsp;&nbsp; return D &nbsp;&nbsp;&nbsp; def x(S,a): &nbsp;&nbsp;&nbsp; D=set([]) &nbsp;&nbsp;&nbsp; for i in S: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for j in range(1,i+1): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i%j==0 and i-j&gt;=a: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; D.add(i-j) &nbsp;&nbsp;&nbsp; return Ddef f(a,b): &nbsp;&nbsp;&nbsp; if a&lt;=b: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; t=0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while a*2&lt;b: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; t=t+1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a=a*2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L=set([a]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; S=set([b]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L2=set([]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; S2=set([]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while L&amp;S==set([]): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; t=t+1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L2=L|L2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L=d(L,max(S))-L2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if L&amp;S&lt;&gt;set([]): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; t=t+1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; S2=S|S2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; S=x(S,min(L))-S2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return t &nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return -1 print f(a,b)

不过您的代码还是挺优秀的，我测试了一下时间，比我少很多很多倍。 大佬，膜拜！！！

a= 1  b = 527
应该只需要12步
1 2 3 6 12 24 48 96 192 384 480 496 527
而您的程序运行结果为13。 但是网站的判定里面可能为13 或者没有这个测试数据。

啊啊啊啊，大佬 '&lt;&gt;'这个符号是什么意思啊&nbsp; 啊啊&nbsp; 人傻了都

我是第一个留言的吗？

错误代码 贻笑大方&nbsp; 而且当时没学过贪心 随便写的a=5 b=3351 def c_f(a): &nbsp;&nbsp;&nbsp; k=[] &nbsp;&nbsp;&nbsp; for i in range(1,int(a/2)): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if a%i==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; k.append(i) &nbsp;&nbsp;&nbsp; return k if a==b: &nbsp;&nbsp;&nbsp; print 0 elif a&gt;b: &nbsp;&nbsp;&nbsp; print -1 else: &nbsp;&nbsp;&nbsp; i=0 &nbsp;&nbsp;&nbsp; while a&lt;b: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (b-a)&gt;a: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a+=a &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i+=1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; elif a%(b-a)==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i+=1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; #print a &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; elif (b-a)&lt;a: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; k=c_f(a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (b-a)&gt;k[-1]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a+=k[-1] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; #print a &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i+=1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for j in k[::-1]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if j &lt;(b-a): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a+=j &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i+=1 &nbsp;&nbsp;&nbsp; print i

如果找不到错误数据请试一下 a=5 b=3351贪心算法过不去的

本来以为只是一个广度优先搜索的题目，但是超时了<pre class="prettyprint lang-py linenums">def get_factors(n):
	rsl = []
	for i in range(1,n+1):
		if n % i == 0:
			rsl.append(i)
	return rsl

def bfs(start, end):
	history = [start] #如果已经计算过的就不要再计算了
	stack = [(start, 0)] #是一个tuple，第一个数字表示数字，第二个表示步数
	while len(stack):
		node = stack.pop(0)
		factors = get_factors(node[0])
		for value in factors:
			value += node[0]
			if value == end:
				return node[1] + 1
			if value not in history:
				history.append(value)
				new_node = (value, node[1] + 1)
				stack.append(new_node)
	return -1

print bfs(a,b)
</pre>

本来以为

啊 原来如此 我说我为什么过不去 却找不到过不去的数据，谢谢各位！

def zh(a, b, step=0): &nbsp; &nbsp; &nbsp; &nbsp; for i in range(a, 0, -1): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if a % i == 0 and a + i &lt; b: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return zh(a + i, b, step + 1) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; elif a % i == 0 and a + i == b: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return step + 1 &nbsp; &nbsp; &nbsp; &nbsp; return -1

数据已加强，贪心算法现在无法通过了

题目是错的，要不超时，要么不准确用dijkstra准确但超时,只用贪心速度快但不完全准确，可是贪心通过了如a=5,b=3351dijkstra：[5,10,15,30,31,62,93,186,279,558,1116,1674,3348,3351] 13步 贪心：[5,10,20,40,80,160,320,640,1280,2560,3200,3328,3344,3348,3351] 14步又如a=5,b=3359dijkstra：[5,6,12,24,48,51,102,204,207,414,828,1656,1679,3558,3559] 14步 贪心：[5,10,20,40,80,160,320,640,1280,2560,3200,3328,3354,3357,3358,3359] 15步不过绝大部分一样的

贪心a先不断乘2，然后两头不断取最大约数，搞定

第88题：数字转换

回文子串

换位置

地板覆盖

Py扔铅球