рекурсивный алгоритм для списка чисел, чтобы выяснить, достаточно ли у меня шагов, чтобы дойти до конца

ProgramBox

рекурсивный алгоритм для списка чисел, чтобы выяснить, достаточно ли у меня шагов, чтобы дойти до конца

Post author:admin
Запись опубликована:8 июля, 2022
Post category:Вопросы по программированию

#python #recursion #logic

#python #рекурсия #Логические

Вопрос:

Если у меня есть список чисел ,

например [3,4,5,7,0,5,2] .

Каждый элемент в списке представляет количество максимальных шагов, которые я могу продвинуть вперед из этой ячейки. хороший список — это когда я могу добраться до конца списка, плохой список — это когда у меня недостаточно шагов, чтобы добраться до конца списка .

Я пытаюсь написать следующий код, но это неправильно :

 def recu(li):

    if li[0] == 0:
        print("not working")
        return 'Null'

    if li[0] >= len(li):
        print('finished with success')
        return 'Null'

    if li[0] < len(li):
        print(li[li[0]:])
        return recu(li[li[0]:])




recu(list1)

не могли бы вы мне помочь?

1. это игра с переходом в leetcode?, в вашем коде вам нужно отслеживать прыжок , который вы совершаете, и в какой позиции вы присутствуете, я думаю, что рекурсия — неправильный подход

2. «Я пытаюсь написать следующий код, но он неправильный» Не могли бы вы более подробно объяснить, почему вы считаете, что это «неправильно»? Что не так? Выдает ли код сообщение об ошибке при запуске в определенном списке ввода? Возвращает ли он неправильный результат? Пожалуйста, объясните более подробно.

Ответ №1:

Это та логика, которую вы ищете?

 def is_good(l):
    e = l[0]
    return False if e == 0 else True if e >= len(l) -1 else is_good(l[e:])

Я попробовал несколько списков — и это имеет смысл, исходя из моего понимания проблемы:

 is_good([0,1,3])           # Returns False
is_good([3,3,5,0,1])       # Returns False 
is_good([1,7,2,3,0])       # Returns True
is_good([[3,4,5,7,0,5,2])  # Returns True

Я предполагаю, что вам нужно перейти на последний элемент или за его пределы — если вам просто нужно выйти за его пределы

 def is_good(l):
    e = l[0]
    return False if e == 0 else True if e >= len(l) else is_good(l[e:])

1. «если что-то, то false, иначе true» немного запутано. Вы могли бы использовать логические операторы вместо if / else: return e > 0 and (e >= len(l) or is_good(l[e:]))

2. @Stef Я согласен с вами, и ясно, что многие из этих условий часто можно записать более компактным способом. С другой стороны, я думаю, что он читается очень четко, и для некоторых решений я все еще предпочитаю ясность, а не компактность, особенно в ситуации, когда существующий код является ошибочным или чрезвычайно избыточным! Я бы сказал, что после одного урока программирования вы поймете if else else , в то время как для более компактной версии, которую вы предлагаете, вам нужно остановиться на секунду.

3. Тогда это должно быть делом вкуса, потому что я бы утверждал с точностью до наоборот. Я нахожу python if else очень сложным для чтения, когда он вложен; в то and / or время как версия чрезвычайно логична и интуитивно понятна. «и» и «или» — это логические английские слова, которыми я привык манипулировать при разговоре, чтении и записи, а не только при программировании; но использование True и False явно внутри вложенного выражения if / else не выглядит отдаленно как английское предложение и требует довольно умственных усилий для правильного анализа(Мне нужно буквально нарисовать дерево выражений в моей голове и обдумать его)

4. Ваше решение не работает. Например print(is_good([2, 2, 0, 2, 1])) , возвращает False , но это неверно.

5. @Ratery разве каждое число не представляет количество шагов вперед, которые вы можете предпринять? l [0] = 2, вы получаете l [2], который равен 0, следовательно, вы застряли там, нет?

Ответ №2:

Для этого вы можете использовать динамическое программирование.

 def solution(x):
    a = [False] * len(x)  # list of accessible cells
    a[0] = True  # first cell accessible
    for i, (p, k) in enumerate(zip(a, x)):
        if p:
            for j in range(i, i   k   1):
                try:
                    a[j] = True  # mark all the cells that can be reached from the processed to the cells
                except IndexError:
                    return True
    return False

print(solution([3,4,5,7,0,5,2]))

Вы также можете использовать рекурсию:

 arr = [3, 4, 5, 7, 0, 5, 2]

def f(i):
    if i   arr[i] >= len(arr):
        print(True)
        exit(0)
    for j in range(i   1, i   arr[i]   1):
        f(j)

f(0)
print(False)

1. не могли бы вы объяснить, что вы сделали?

2. Эй , спасибо за ответ , но он не рекурсивный .

3. Привет! Я отредактировал свой ответ. И написал решение с использованием рекурсии.

Ответ №3:

Я могу предложить решение вашей проблемы, используя алгоритм поиска в глубину.

 #include <iostream>
#include <vector>
using namespace std;
const int maximumSize=40;
vector<int> visited(maximumSize, 0);
void dfs(int current, int previous, vector<int>amp; input)
{
    if(visited[current]==1)
    {
        return;
    }
    if(current>=(input.size()-1))
    {
        cout<<"finished with success"<<endl;
        return;
    }
    if((input[current]==0) amp;amp; (current<(input.size()-1)))
    {
        cout<<"not working"<<endl;
        return;
    }
    visited[current]=1;
    int newCurrent=(current input[current]);
    for(int next=newCurrent; next<=newCurrent;   next)
    {
        if(next==previous)
        {
            continue;
        }
        dfs(next, current, input);
    }
    return;
}
void solve()
{
    vector<int> inputVector={3, 4, 5, 7, 0, 5, 2};
    dfs(0, -1, inputVector);
    return;
}
int main()
{
    solve();
    return 0;
}

Входные данные:

 {3, 4, 5, 7, 0, 5, 2}

Вот результат:

 finished with success

Ввод:

 {3, 4, 5, 0, 7, 0, 5}

Вот результат:

 not working

Метки: достаточно ли у меня шагов, рекурсивный алгоритм по списку чисел, чтобы выяснить, чтобы дойти до конца