<分区>
Possible Duplicate:
Help with algorithm problem from SPOJ
遇到这个面试问题。给定两个 n 位质数,将第一个质数转换为第二个质数,一次改变一位数。中间数也必须是质数。这需要以最少的步骤完成(检查素数和更改数字被视为步骤)
例如将 1033 转换为 8179 (1033->1733->3733->......->8179)
<分区>
Possible Duplicate:
Help with algorithm problem from SPOJ
遇到这个面试问题。给定两个 n 位质数,将第一个质数转换为第二个质数,一次改变一位数。中间数也必须是质数。这需要以最少的步骤完成(检查素数和更改数字被视为步骤)
例如将 1033 转换为 8179 (1033->1733->3733->......->8179)
最佳答案
在下雨的星期一晚上,这是一个不错的挑战(无论如何,它就在这里!)。这可以使用 Dijkstra's algorithm 来完成.第一步是创建一个 graph包含所有 4 位素数。然后使用 Dijkstra 算法找到起始/结束素数之间的最短路径。这是 Python 中的一个实现:
#! /usr/bin/python -tt
# run as: findpath start end
import sys
(start, end) = map(int, sys.argv[1:3])
# http://primes.utm.edu/lists/small/10000.txt
f = open("10000.txt", "r")
lines = f.readlines()
f.close
lines = lines[4:-1] # remove header/footer
all = "".join(lines) # join lines
all = all.split()
all = map(int, all)
# only want the 4-digit primes
fourdigit = [p for p in all if 1000 <= p and p <= 9999]
# returns digits in a number
digits = lambda x: map(int, str(x))
# cache of digits for each prime
digits_for_nums = {}
# returns digits in a number (using cache)
def digits_for_num(x):
global digits_for_nums
if x not in digits_for_nums:
digits_for_nums[x] = digits(x)
return digits_for_nums[x]
# returns 1 if digits are same, 0 otherwise
diff = lambda pair: 1 if pair[0] == pair[1] else 0
# computes number of identical digits in two numbers
def distance(a, b):
pair = (a, b)
pair = map(digits_for_num, pair)
pair = zip(pair[0], pair[1])
pair = map(diff, pair)
same = sum(pair)
return same
# adjacency list representation of graph of primes
edges = {}
# construct graph
for a in fourdigit:
edges[a] = []
for b in fourdigit:
if distance(a, b) == 3:
edges[a].append(b)
infinity = sys.maxint
def smallest():
global dist, Q
minimum = infinity
which = None
for v in Q:
if dist[v] <= minimum:
which = v
minimum = dist[v]
return which
# Dijkstra's algorithm
dist = {}
previous = {}
Q = edges.keys()
for v in Q:
dist[v] = infinity
previous[v] = None
dist[start] = 0
while len(Q) > 0:
u = smallest()
if dist[u] == infinity:
break
Q.remove(u)
for v in edges[u]:
alt = dist[u] + 1
if alt < dist[v]:
dist[v] = alt
previous[v] = u
# get path between start/end nodes
num = end
path = [num]
while num != start:
num = previous[num]
path.insert(0, num)
print path
关于algorithm - 转换素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3653475/