#python #dynamic #primes
Вопрос:
Существует задача, аналогичная проекту Эйлера 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
Во-первых, попытался решить ее без 3-го условия(только пройдитесь по не простому числу):
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]))
Как я должен заставить его пропустить простые числа и продолжить с не простыми числами?
Ответ №1:
На самом деле я пытался решить эту проблему несколькими способами, но все другие методы, которые я пробовал, намного медленнее, чем этот. Я почти уверен, что это не лучший метод, но он все равно работает. Для вызова нужной вам функции 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
Надеюсь, это поможет. Дайте мне знать, если что-то все еще неясно.
Ответ №2:
Вы можете идентифицировать все простые числа, используя сито Эратосфена, и отметить их в списке треугольников (я не использую их в качестве индикатора).
Затем перейдите снизу вверх, отслеживая текущие максимумы на основе предыдущего результата. Каждая итерация уменьшит размер пути на одну запись, и вы получите список из одного элемента, содержащий максимальный путь.
Это практически то же самое, что делает ваш код, за исключением помечения простых чисел и пропуска помеченных записей.
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"""
tri = [ [*map(int,line.split())] for line in num.split("n") ]
Найдите простые числа в диапазоне наибольшего значения
maxValue = max(map(max,tri))
isPrime = [0,0] [1]*(maxValue-1) # Sieve of Eratosthenes
p,inc = 2,1
while p*p<=maxValue:
if isPrime[p]:
isPrime[p*p::p] = [0]*len(range(p*p,len(isPrime),p))
p,inc = p inc,2
Отметьте простые числа как отсутствующие в списке треугольников:
tri = [ [None if isPrime[n] else n for n in row] for row in tri ]
Накопите наибольшее общее количество снизу вверх (не пропуская ни одной записи)
path = tri[-1]
for row in tri[-2::-1]:
path = [ None if n is None or (a,b)==(None,None) else n max(a or 0,b or 0)
for n,a,b in zip(row,path,path[1:]) ]
print(path[0]) # 8186 (113 microseconds on my laptop)