Python配列の最右端に左または右のホップで到達できるかどうかを確認します

Question

私はゲームが解決可能かどうかを調べるプログラムを書いています。ゲームの ルールは以下のとおりです。

1. あなたは左または右の位置で配列の値によって、あなたは、エンドポイントを超えて行くことができないホップすることができ、左端の位置
2. からスタート。例：a = {4,4,1,5,2,6,3,4,2,0}あなたは左から2番目に4つの場所を右にジャンプすることができます（左はできません）

3. 私たちは、右端に達することができるならば、我々は常に0

4. に等しいもう一方の端に達することができるかどうかを確認する必要がある（すなわち0）、それは

解くことができない他解けるある私が使って試してみましたPythonでの再帰は、どのように進むべきかわかりません。

def KAuhop(b,c,d,current_position): 
     position_move=b[current_position] 
     if b[current_position+position_move]==0: 
      print("found") 
     else: 
      KAuhop(b,current_position+position_move,d,current_position) 
      print("Not found") 




    a=[4,4,1,5,2,6,3,4,2,0] 
    print(KAuhop(a,0,len(a)-1,0)) 

Answer 1

左または右のいずれかの位置にジャンプすることができる場合は、プログラムを終了または終了する必要がある場合は、別の場所にジャンプする無限ループになることを言います。

再帰関数を使用して右ジャンプのみを行う下記の解を見つけてください。

lis=[4,4,1,5,2,4,3,4,2,0] 
last_pos=len(lis)-1 
pos = 0+lis[0] 

def kauhop(lis,pos): 
    if (pos==last_pos): 
     print("found") 
     exit; 
    else: 
     new_pos = pos+lis[pos] 
     if(new_pos <= last_pos): 
      kauhop(lis,new_pos) 
     else: 
      print("Not found") 

kauhop(lis,pos) 

Answer 2

ここでは、すでにsetオブジェクトで見てきた位置を把握し、我々：

In [25]: def kauhop(seq): 
    ...:  seen = set() 
    ...:  maxlen = len(seq) - 1 
    ...:  def helper(pos): 
    ...:   if pos > maxlen or pos < 0 or pos in seen: 
    ...:    return False 
    ...:   elif pos == maxlen: 
    ...:    return True 
    ...:   else: 
    ...:    jump = seq[pos] 
    ...:    seen.add(pos) 
    ...:    left = helper(pos - jump) 
    ...:    right = helper(pos + jump) 
    ...:    return left or right 
    ...:  return helper(0) 
    ...: 

In [26]: kauhop(a) 
Out[26]: True 

基本的には、すべての可能なパスを確認するために再帰を使用することができます。あなたの現在のポジションを考えてみましょう。どちらの方向にも外れている場合、またはすでにポジションを確認している場合は（seen）、Falseを返します。それ以外の場合は、表示されている位置にマークを付け、左のジャンプと右のジャンプをチェックし、左か右が成功すれば戻る。注：私はヘルパー内部関数を使用します。これにより、がseenを超えて閉じられているので、seenをそのまま通過する必要はありません。その点については、maxlenです。

今私はブルートフォースよりも優れたアプローチがあるのだろうかと思っています。