прыжки игры с рекуррентным

Question

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

Индекс начала он номер, который вы стоите на так вы можете прыгать влево или вправо по линии, перепрыгивая количество мест, обозначенных номером, на котором вы стоите

Цель: вы хотите добраться до 0 в дальнем конце (справа) от линии. Вы также гарантированно, что будет только один ноль, который, опять же, будет на правой стороне.

Итак, метод возвращает True, если я достиг цели и вернул False Если бы я этого не сделал.

Это пример:

Первое число является индексом начала и второе число длина массива и массив остальных чисел

6 8 2 3 4 6 3 5 2 0 : True 

Это мой код:

public static boolean game(int startindex,int[] array){ 

    int startgame=array[startindex]; 

    for(int p=0;p<=10;p++){ 

     int play=array[0+startgame]; 

     startgame+=play; 

     if(startgame>=array.length){ 

      startgame-=play; 
      startgame-=play; 

     } 

     if(array[startgame]==0) 
     return true; 

    } 

    return false; 

} 

при попытке этот пример

3 8 2 3 4 6 3 5 2 0 возврата Tru е

но должен вернуться ложным, так как индекс старт 3 так что я начинаю с его значением = 6 прыгать либо влево 6 пробелов и 6 правых пространств, но я не мог добраться до 0.

и когда пытаются это

6 8 9 9 9 9 9 9 1 0 показать Exception

Я не знаю why.Can кто-нибудь помочь мне

Answer 1

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

Ваш текущий алгоритм не работает должным образом, так как вы будете (1) выполнять максимум 10 шагов, и (2) вы будете только отступать, если перебор вперед слишком далеко. Кроме того, вы никогда не проверяете, может ли обратный прыжок заканчиваться за пределами границ.

Создание этого рекурсивный алгоритм очень прост: В принципе, вы только три случая:

• если текущая позиция находится вне границ, возвращающие false
• , если значение в текущей позиции 0, возвращение true
• иначе, возвращение приведет ли либо прыжок влево или прыжок вправо к цели

Кроме того, вы можете захотеть вспомнить «ступеньки», на которых вы уже были, чтобы увидеть, «вы прыгаете по кругу». В этом случае также возвращайтесь false.

Собирает все вместе, алгоритм может выглядеть следующим образом:

// inpt: input array, current: current position, seen: list/set of visited positions 
boolean function jump(inpt, current, seen): 

    if current < 0 or current >= length(inpt) then 
     return false // jumped too far 

    if inpt[current] == 0 then 
     return true  // goal found 

    if current in seen then 
     return false // jumping in circles 

    return (jump(inpt, current + inpt[current], seen + [current]) 
     or jump(inpt, current - inpt[current], seen + [current])) 

И называет это как jump([6, 8, 2, 3, 4, 6, 3, 5, 2, 0], 0, <empty list>)