пути подсчета для заданной ситуации

Question

У меня возник вопрос о ситуации, когда нас просят написать функцию python для подсчета количества путей. Вопрос таков:

Робот расположен в верхнем левом углу 3x7. робот может только двигаться вниз на один квадрат или правый квадрат в любой момент времени и не может двигаться в каком-либо другом направлении. робот пытается достичь нижнего правого угла сетки.

Написать функцию питона, countPaths которая возвращает таблицу (список списков), дорожки. Каждый элемент в дорожках таблицы - это количество возможных путей, которые робот может принимать от . Начните в положение, соответствующее элементу в таблице. Например, пути [0] [0] = 1 и пути [2] [6] = 28.

Вот что я пробовал, но ему нужна некоторая коррекция. Я довольно новичок в python, и мне нужна помощь в исправлении кода.

def countPaths(row,column): 
    row = 1 
    column = 1 
    for row in range(1,n): 
     for column in range(1,n): 
      (n_row-1 + n_column-1) 
    return paths 

Answer 1

В вашем коде есть несколько хороших идей, но вы не правильно их реализуете. Вы правильно добавили два значения массива, чтобы получить новое значение массива, и вы правы в использовании двух вложенных циклов for. Но вы переписываете значения row и col в первых двух строках внутри функции и пытаетесь использовать n, который никогда не определяется. Вы также не получаете доступ к предыдущим значениям массива должным образом. Наконец, вы не принимаете во внимание тот факт, что левый столбец и верхняя строка не добавляют значения вместе, а просто имеют значение 1.

Вот код, который работает. Дайте мне знать, если вам нужно объяснение любой его части.

def countpaths(row, column): 
    result = [[1] * column for r in range(row)] 
    for r in range(1, row): 
     for c in range(1, column): 
      result[r][c] = result[r][c-1] + result[r-1][c] 
    return result 

paths = countpaths(3,7) 
for r in paths: 
    print(r) 
print(paths[0][0]) 
print(paths[2][6]) 

Это печатает

[1, 1, 1, 1, 1, 1, 1] 
[1, 2, 3, 4, 5, 6, 7] 
[1, 3, 6, 10, 15, 21, 28] 
1 
28 

Answer 2

Математическая формулировка: Для достижения элемента [х] [у] робот должен делать X + Y движется. Поэтому он имеет x + y, чтобы выбрать x вариантов, чтобы распределить свои шаги x прямо на его ходы x + y.

Следовательно пути [х] [у] = (х + у)/(х + у!)

А вот реализация питон:

from math import factorial as fac 
def countPaths(): 
    noRows=3 
    noCols=7 
    paths=[] 
    for row in range(0,noRows): 
     #uncomment to see how the list of lists is build 
     #print(paths) 
     paths.append([]) 
     for col in range(0,noCols): 
      paths[row].append(int(fac(row+col)/fac(row)/fac(col))) 
    return paths 

paths=countPaths() 
print('\n\nresult:') 
print(paths) 

Результат:

result: 
[[1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7], [1, 3, 6, 10, 15, 21, 28]] 

Просто используйте команду печати, чтобы следить за содержанием переменных.

Answer 3

Вот рекурсивная реализация:

rowLength = 3 
colLength = 7 
count = 0 
path = [] 
paths = [] 

def countPaths(row,col): 
    global count 
    global path 
    global paths 

    if (row,col) in path: 
     return 
    else: 
     path.append((row,col))  

    if row == rowLength and col == colLength: 
     count += 1 
     print ("Reached end, Path followed: ",path) 
     paths.append(path) 
     path.pop() 
     return 
    if row > rowLength or col > colLength: 
     path.pop() 
     return 

    # Go down 
    countPaths(row+1, col) 

    # Go right 
    countPaths(row, col+1) 

    path.pop() 
    return 

countPaths(0,0)