1

我正在尝试解决这个问题：

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

给定一个起始号码，找出所有可能的 6 位号码，号码只能横拨或竖拨。不允许重复。数字不能从零开始，并且不包括 * 和 #。例如，如果最后拨打的号码是 3，则下一个号码可能是 1、2、6 或 9。

我正在尝试通过创建一个图表来实现这一点，其中一个数字只有在同一行和同一列中的相邻数字，然后从起始数字中找到长度为 5 的所有可能路径。但我还不知道有什么算法可以做到这一点..

有什么建议么？

4

4 回答 4

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

我认为你在正确的道路上。只需遍历树（标记每个访问过的节点，以避免重复），并输出长度为 5 的每条路径。

您在这里并不需要任何新东西，即使是限制为深度 5的基本广度优先搜索也可以。

于 2012-12-20T07:06:03.147 回答
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

这个问题可以递归解决，返回点在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 回答