1

私はこの問題を解決しようとしています:

1  2  3
4  5  6
7  8  9
*  0  #

開始番号を指定して、可能なすべての 6 桁の番号を見つけます。番号は、水平方向または垂直方向にのみダイヤルできます。繰り返しは許可されていません。数字はゼロから始めることはできません。また、* と # を含めることもできません。たとえば、最後にダイヤルした番号が 3 の場合、次の番号は 1、2、6、または 9 の可能性があります。

同じ行と列にある数字のみが隣接するグラフを作成し、開始番号から長さ5のすべての可能なパスを見つけることで、この作成を試みています。しかし、私はまだそれを行うためのアルゴリズムを知りません..

助言がありますか？

4

4 に答える 4

2

数値が2次元配列NUMPADに格納されていると仮定します。ここで、「1」はインデックス[0] [0]にあり、「2」はインデックス[0][1]にあります。

Func permute_nums(digits_so_far)
    If digits_so_far has 6 elements
        print digits_so_far
        return
    Let L = last element of digits_so_far
    Find index (x,y) of L in NUMPAD
    For i from -2 to +2
        if (x+i,y) is NOT out of bounds
            Find number n at (x+i,y)
            permute_nums(digits_so_far + [n])
        if (x,y+i) is NOT out of bounds
            Find number m at (x,y+i)
            permute_nums(digits_so_far + [m])

開始桁を指定sして、permute_nums([s])

于 2012-12-20T07:05:25.170 に答える
0

うーん。それはかなり簡単なはずです。

static var a:Array=[[8],[2,4],[1,3,5],[2,6],[1,5,7],[2,4,6,8],[3,5,9],[4,8],[5,7,9,0],[6,8]];
function giveAllnumbers(numbersSoFar:String,lastSelectedNumber:int,:int) {
    if (howManyToSelectLeft==0) {
        trace(numbersSoFar); // output goes here
        return;
    }
    for (var i:int=a[lastSelectedNumber].length-1;i>=0;i--) 
        giveAllNumbers(numbersSoFar+a[lastSelectedNumber][i].toString(),
            a[lastSelectedNumber][i],
            howManyToSelectLeft-1);
}

これはActionscriptですが、他のどの言語にも対応できます。で呼び出すgiveAllNumbers(''+yourNumber.toString(),yourNumber,desiredLength);

于 2012-12-20T09:46:56.743 に答える
0

私はあなたが正しい道を進んでいると思います。ツリーをトラバースし（繰り返しを避けるために、訪問したすべてのノードにマークを付けます）、長さ5のすべてのパスを出力します。

ここでは、特に新しいものは必要ありません。深さ5に制限されている基本的な幅優先探索でもかまいません。

于 2012-12-20T07:06:03.147 に答える
0

この問題は再帰的に解くことができ、return ポイントは length == 6 のときになります。

private static void countMaxNumbers(String i) {
    if(i.length() == 6)
    {
        numberCount++;
        return;
    }
    if(i.charAt(i.length() - 1) == '1'){
        countMaxNumbers(i+'2');
        countMaxNumbers(i+'3');
        countMaxNumbers(i+'4');
        countMaxNumbers(i+'7');
    }
    else if(i.charAt(i.length() - 1) == '2'){
        countMaxNumbers(i+'5');
        countMaxNumbers(i+'8');
        countMaxNumbers(i+'0');
        countMaxNumbers(i+'1');
        countMaxNumbers(i+'3');
    }
    else if(i.charAt(i.length() - 1) == '3'){
        countMaxNumbers(i+'1');
        countMaxNumbers(i+'2');
        countMaxNumbers(i+'6');
        countMaxNumbers(i+'9');
    }
    else if(i.charAt(i.length() - 1) == '4'){
        countMaxNumbers(i+'1');
        countMaxNumbers(i+'7');
        countMaxNumbers(i+'5');
        countMaxNumbers(i+'6');
    }
    else if(i.charAt(i.length() - 1) == '5'){
        countMaxNumbers(i+'2');
        countMaxNumbers(i+'8');
        countMaxNumbers(i+'0');
        countMaxNumbers(i+'4');
        countMaxNumbers(i+'6');
    }
    else if(i.charAt(i.length() - 1) == '6'){
        countMaxNumbers(i+'3');
        countMaxNumbers(i+'9');
        countMaxNumbers(i+'4');
        countMaxNumbers(i+'5');

    }
    else if(i.charAt(i.length() - 1) == '7'){
        countMaxNumbers(i+'1');
        countMaxNumbers(i+'4');
        countMaxNumbers(i+'8');
        countMaxNumbers(i+'9');

    }else if(i.charAt(i.length() - 1) == '8'){
        countMaxNumbers(i+'7');
        countMaxNumbers(i+'9');
        countMaxNumbers(i+'2');
        countMaxNumbers(i+'5');
        countMaxNumbers(i+'0');
    }else if(i.charAt(i.length() - 1) == '9'){
        countMaxNumbers(i+'3');
        countMaxNumbers(i+'6');
        countMaxNumbers(i+'7');
        countMaxNumbers(i+'8');
    }else if(i.charAt(i.length() - 1) == '0'){
        countMaxNumbers(i+'2');
        countMaxNumbers(i+'8');
        countMaxNumbers(i+'5');
    }
}

答えは次のとおりです: 12855

于 2013-08-22T19:04:49.500 に答える