所有可能的數字我試圖解決這個問題：從鍵盤
1 2 3
4 5 6
7 8 9
* 0 #
給定的起始編號，發現所有6位數字可能，數字只能水平或垂直撥打。不允許重複。數字不能從零開始，不包括*和＃。例如，如果最後撥打的號碼是3，則下一個號碼可能是1,2,6或9.
我試圖通過創建一個圖形，其中一個數字只有那些相鄰的數字相同的行和列，然後從起始號碼中查找長度爲5的所有可能路徑。但我不知道這樣做的任何算法呢..
有什麼建議嗎？
假設號碼存儲在一個2-d陣列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])
我認爲你是在正確的道路上。 只是遍歷樹（標記每個訪問的節點，以避免重複），並輸出每個路徑長度爲5.
你真的不需要什麼新東西，即使是基本的Breadth first search限於深度5將做。
嗯。這應該很容易。
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);
此問題調用可以遞歸解決，和返回點將是當長度== 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
「出界」 =外線的NUMPAD，或對應於*或＃ – tom
我認爲「不重複」只意味着相同的數字不能連續出現兩次（例如122345錯誤，但123245可以）。如果6位數字的每個數字都必須是唯一的，那麼除了「越界」檢查外，我們還需要檢查數字n（或m）是否已經位於digits_so_far中。 – tom
但是digit_so_far的大小不會無限增長嗎？一旦它有6位數字，它不需要刪除元素嗎？ – Bruce