配列を使ったJavaタスクの解決

Question

Javaの配列に関連する質問に対する解決策をコーディングしようとしています。質問はこのように書きます：

あなたは、長さnはの配列を与えられた0からにインデックス付けのnされている - 1配列の各要素は、0または1のどちらかであるあなただけに移動することができます最初にあなたは0 ^thの位置にいます。各移動では、次のいずれかの操作を行うことができます。

• 一歩前進または後退します。
• 正確な長さのジャンプを正確にm前方に作成します。一手に1又はX + メートル - あなたは、+ 1×、XにX位置から移動できる手段

。新しい位置には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 

そのための条件（I < n）の中には、常に真です。

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を考えます。これは3つのオプション（後方1、前方1、前方X）のどちらを先に試しても同じです。

このようなバックトラッキングロジックは、再帰的メソッドを使用して実装されることが最も一般的ですが、手動でスタックを維持することによっても実行できます。

最後に、あなただけがあなたの検索を完了したとき、あなたが最後に到達すなわち場合、YESまたはNOを印刷する印刷YESと検索を停止、またはあなたが最後に取得せずにすべての組み合わせを試してみた場合には必要があり、 NOを印刷します。