python - python中带有质数检查的最大路径和
问题描述
有一个类似于 project euler 18 的任务，但这次你只能走过非素数。任务是：
您将在下面有一个三角形输入，您需要根据下面给定的规则找到数字的最大总和；
1
8 4
2 6 9
8 5 9 3
1-您将从顶部开始并向下移动到相邻的数字，如下所示。
2-您只能向下和斜着走。
3-您只能走过非质数。
根据上述规则，以下输入的最大总和是多少？这意味着请将此金字塔作为您的实现的输入（作为文件或直接在代码中的常量）并使用它来解决。
215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233
首先，尝试在没有第三个条件的情况下解决它（只走过非素数）：
num="""215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233"""
rows=num.split("\n")
array=list()
for row in rows:
num_list=row.split(" ")
array.append(num_list)
for i in range(0,len(array)):
for j in range(0,i+1):
array[i][j] = int(array[i][j])
for i in range(len(array)-1, -1, -1):
for j in range(0,i):
array[i-1][j] += max(array[i][j], array[i][j+1])
print(array[0])
此时，我不知道如何将质数检查放入此代码并找到真正的解决方案，因为上面的代码输出是9022
- -编辑 - -
我添加了质数检查以打印一个数字是否是/不是质数：
def isprime(n):
if n < 2: return False
for i in range(2, n):
if n % i == 0:
print("non prime")
break
else:
print("prime")
for i in range(0,len(array)):
for j in range(0,i+1):
print(isprime(array[i][j]))
我应该如何让它跳过素数并继续使用非素数？
解决方案
我实际上尝试用多种方法解决它，但我尝试的所有其他方法都比这个慢得多。我很确定这不是最好的方法，但无论如何它都有效。要调用您需要的函数solvearray(num)，num 必须始终具有与您作为示例提供的格式相同的格式。我采用了您的isprime(n)功能，但稍微修改了结构。这是我的代码：
num="""215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233"""
def solvearray(num):
def get_array(num):
rows = num.split("\n")
array = []
for row in rows:
num_list=row.split(" ")
num_list = list(map(int, num_list))
array.append(num_list)
print(num_list)
return array
print('array: this is the array to be solved')
array = get_array(num)
def isprime(n):
if n < 2: return False
for i in range(2, n):
if n % i == 0:
p = 0 # is prime
break
else:
p = 1 # not prime
return p
dim = len(array)
def get_isprime(array):
primearray = []
for row in range(len(array)):
parray = []
for col in range(len(array[row])):
parray.append(isprime(array[row][col]))
primearray.append(parray)
print(parray)
return primearray
print('parray: this shows if each number in array is prime')
primearray = get_isprime(array)
path = [0]
branch = []
for row in range(len(path),dim):
col = path[-1]
if primearray[row][col] == 0 and primearray[row][col+1] == 1:
col = col
path.append(col)
elif primearray[row][col] == 1 and primearray[row][col+1] == 0:
col = col + 1
path.append(col)
elif primearray[row][col] == 1 and primearray[row][col+1] == 1:
break
elif primearray[row][col] == 0 and primearray[row][col+1] == 0:
col = col
path.append(col)
branch.append(row)
allpath = []
while len(path) != dim or branch != []:
try:
del path[branch[-1]+1:len(path)]
del branch[-1]
path[-1] = path[-1] + 1
except IndexError:
break
for row in range(len(path),dim):
col = path[-1]
if primearray[row][col] == 0 and primearray[row][col+1] == 1:
col = col
path.append(col)
elif primearray[row][col] == 1 and primearray[row][col+1] == 0:
col = col + 1
path.append(col)
elif primearray[row][col] == 1 and primearray[row][col+1] == 1:
break
elif primearray[row][col] == 0 and primearray[row][col+1] == 0:
col = col
path.append(col)
branch.append(row)
if len(path) == dim:
if path not in allpath:
allpath.append(path[:])
actualpath = []
maxsum = []
for i in range(len(allpath)):
onepath = []
for j in range(dim):
onepath.append(array[j][allpath[i][j]])
actualpath.append(onepath)
maxsum.append(sum(onepath))
print('index path :', allpath[maxsum.index(max(maxsum))])
print('actual path:', actualpath[maxsum.index(max(maxsum))])
print('sum of path: ',max(maxsum))
import time
t1 = time.time()
solvearray(num)
t2 = time.time()
print(f'the function took {t2-t1} s to solve this problem')
import time实际上不是函数的一部分，只是为了让我检查计算时间。我打印了很多，这样你就可以真正看到在哪个步骤中做了什么。这是完整的输出：
array: this is the array to be solved
[215]
[193, 124]
[117, 237, 442]
[218, 935, 347, 235]
[320, 804, 522, 417, 345]
[229, 601, 723, 835, 133, 124]
[248, 202, 277, 433, 207, 263, 257]
[359, 464, 504, 528, 516, 716, 871, 182]
[461, 441, 426, 656, 863, 560, 380, 171, 923]
[381, 348, 573, 533, 447, 632, 387, 176, 975, 449]
[223, 711, 445, 645, 245, 543, 931, 532, 937, 541, 444]
[330, 131, 333, 928, 377, 733, 17, 778, 839, 168, 197, 197]
[131, 171, 522, 137, 217, 224, 291, 413, 528, 520, 227, 229, 928]
[223, 626, 34, 683, 839, 53, 627, 310, 713, 999, 629, 817, 410, 121]
[924, 622, 911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233]
parray: this shows if each number in array is prime
[0]
[1, 0]
[0, 0, 0]
[0, 0, 1, 0]
[0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1]
[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1]
index path : [0, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 8]
actual path: [215, 124, 237, 935, 522, 835, 207, 716, 560, 632, 931, 778, 528, 713, 253]
sum of path: 8186
the function took 0.006632566452026367 s to solve this problem
希望能帮助到你。如果还有什么不清楚的地方，请告诉我。
推荐阅读
- java - 添加到列表时的JavaFX ListView空指针
- java - Firebase 存储图像检索 RecyclerView
- javascript - 如何在 HTML 中的每个项目之间打印具有延迟的列表
- java - 端口打开时tomcat服务器未启动
- c# - 如何编写循环来设置 sum[i] 的值并删除 sum[i] <= 0 的数据表列
- r - 基于值范围的ggplot2图形框（最小值最大值）
- python - 从段落中提取复杂的单词
- python - 启动 Spyder 内核时出错
- jmeter - JMeter 能像 Selenium 那样做自动化测试吗？
- docker - kubernetes yaml 文件中的容器端口是什么