Решение задач Java с использованием массивов

Question

Я пытаюсь закодировать решение вопроса, связанного с массивами в Java. Вопрос звучит так:

Вам дается массив длины п, индексированный от 0 до п - 1. Каждый элемент массива является 0 или 1. Вы можете перемещать только к индекс, который содержит 0. Сначала вы находитесь на позиции 0 ^th. В каждом ходу вы можете выполнить одно из следующих действий:

• Пройдите на один шаг вперед или назад.
• Сделайте скачок точно длины m вперед.

Это означает, что вы можете перейти от позиции х к х + 1, х - 1 или х + м в один ход. Новая позиция должна содержать 0. Также вы можете перейти в любое положение, большее, чем n-1.

Вы не можете переместиться назад из положения 0. Если вы переместитесь в любую позицию больше n - 1, вы выиграете игру.

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

Вот пример тестовых примеров:

6 5 
0 0 0 1 1 1 
YES 
6 3 
0 0 1 1 1 0 
NO 

Мой код:

import java.io.*; 
import java.util.*; 

public class hcrkarryjump { 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int n = sc.nextInt(); 
     int m = sc.nextInt(); 
     int a[]=new int[n]; 
     for(int k=0;k<n;k++) 
      a[k]=sc.nextInt(); 
     int i=0; 
     while(i<n){ 
      if(a[i]==0) 
       i++; 
      if(a[i]==1){ 
       if(a[i+1]==0 &&(i+m>=n-1)) 
        System.out.println("YES"); 
       else 
        System.out.println("NO"); 
      } 
     } 
    } 
} 

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

Answer 1

Вы получаете бесконечный цикл, потому что вы никогда не увеличиваем, как только вы получите в [I] == 1.

Чтобы избежать бесконечного цикла, ваш код должен быть:

import java.io.*; 
import java.util.*; 

public class hcrkarryjump { 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int n = sc.nextInt(); 
     int m = sc.nextInt(); 
     int a[]=new int[n]; 
     for(int k=0;k<n;k++) 
      a[k]=sc.nextInt(); 
     int i=0; 
     while(i<n){ 
      // Check if we have something to do 
      if(a[i]==1){ 
       // We do stuff 
       if(a[i+1]==0 &&(i+m>=n-1)) 
        System.out.println("YES"); 
       else 
        System.out.println("NO"); 
      } 
      // and increment for the while check and next loop 
      i++; 
     } 
    } 
} 

Answer 2

Если вы когда-нибудь приземлились на случай, когда [i]! = 0 (поэтому он равен 1), вы закончите итерацию, но вы не добавите что-то к своей переменной i.

Так, например:

Take 1 step i => 1 
Land on 0, ok i => 2 
Land on 1, print yes or no, i=> 2 
Land on the same 1, print ... , i => 2 

Therefor состояние в то время как (я < п) постоянно верно.

Answer 3

Как другие сказал, вы никогда не увеличиваете i раз a[i] == 1. Он будет просто сидеть там, вращаясь в том же положении (i значение).

Однако ваш алгоритм является ошибочным.Рассмотрите этот случай:

8 3 
0 1 0 0 1 0 1 1 
↑     start position 
     ↑   forward 3 (couldn't forward 1 or backward 1) 
    ↑    backward 1 (couldn't forward 1 or 3) 
      ↑  forward 3 (couldn't backward 1 and already been to forward 1) 
       ↑ forward 3 (couldn't forward 1 or backward 1) WIN !!! 

Вы не проверяете все 3 варианта (назад 1, вперед 1, вперед X).

Вы также не проверяете, были ли вы уже где-то. Не проверяя, что вы где-то были, ваш код может закончиться циклическим: вперед 1, назад 1, вперед 1, назад 1, вперед 1, назад 1, вперед 1, назад 1 и так далее ...

Теперь рассмотрим этот один:

16 5 
0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 1 
↑         start position 
      ↑       forward 5 
        ↑    forward 5 
        ↑     backward 1 DEAD END !!! (or loop if not checking "been there") 
↑         backtrack to here 
    ↑         forward 1 
    ↑        forward 1 
       ↑      forward 5 
         ↑   forward 5 
            ↑ forward 5 WIN !!! 

Как вы можете видеть, вы, возможно, придется вернуться назад, чтобы найти правильный путь. Это верно независимо от того, из какого из трех вариантов (назад 1, вперед 1, вперед X) вы пытаетесь в первую очередь.

Логика обратного отслеживания, как это чаще всего реализуется с использованием рекурсивного метода, но также может быть выполнена путем ручного поддержания стека.

Наконец, вы должны напечатать YES или NO только тогда, когда вы закончили поиск, то есть, если вы дойдете до конца, распечатать YES и остановить поиск, или если вы уже пробовали все комбинации, не получив до конца, печать NO.