使用电话键盘生成10位数字
使用电话键盘生成10位数字
提问于 2010-05-24 05:10:56
给定如下所示的电话键盘：
1 2 3
4 5 6
7 8 9
0从1开始可以组成多少个不同的10位数字？约束是从1个手指到下一个手指的移动类似于国际象棋游戏中骑士的移动。
例如。如果我们在1，那么下一个数字可以是6或8，如果我们在6，那么下一个数字可以是1，7或0。
允许重复数字- 1616161616是有效数字。
有没有解决这个问题的多项式时间算法？这个问题要求我们只给出10位数字的计数，而不一定要列出这些数字。
编辑:我尝试将其建模为一个图形，每个数字都有2或3个数字作为其邻居。然后我使用DFS导航到10个节点的深度，然后在每次我到达10个节点的深度时递增数字计数。这显然不是多项式时间。假设每个数字只有2个邻居，这将需要至少2^10次迭代。
这里的变量是位数。我已经接受了急救。十位数的数字。它也可以是n位数。
回答 12
Stack Overflow用户
回答已采纳
发布于 2010-05-24 05:37:59
当然，它可以在多项式时间内完成。在dynamic programming或memoization中，这是一个很好的练习。
在本例中，假设N(位数)等于10。
像这样递归地思考:从1__开始，我可以用10位数字构造多少个数字？
答案是
[number of 9-digit numbers starting from 8] +
[number of 9-digit numbers starting from 6].那么有多少个“从8开始的9位数字”呢？井,
[number of 8-digit numbers starting from 1] +
[number of 8-digit numbers starting from 3]诸若此类。当你得到一个问题“有多少个从X__开始的1位数”(答案显然是1)时，就达到了基本情况。
当涉及到复杂性时，关键的观察结果是重用以前计算的解决方案。例如，当回答“有多少个6位数字从8__开始”和“有多少个6位数字从4__开始”时，都可以使用“有多少个5位数字从3__开始”的答案。这种重用使得复杂度从指数级崩溃到多项式。
让我们仔细看看动态编程解决方案的复杂性：
这样的实现将以以下方式填充矩阵：
num[1][i] = 1, for all 0<=i<=9 -- there are one 1-digit number starting from X.
for digits = 2...N
for from = 0...9
num[digits][from] = num[digits-1][successor 1 of from] +
num[digits-1][successor 2 of from] +
...
num[digits-1][successor K of from]
return num[N][1] -- number of N-digit numbers starting from 1.该算法简单地一次填充矩阵的一个单元，并且矩阵的维度为10*N，因此在线性时间中运行。
从我的头顶上写下来，如果有任何拼写错误，请纠正我。
Stack Overflow用户
发布于 2016-01-28 15:43:37
我决定解决这个问题，并尽可能地使其具有可扩展性。此解决方案允许您：
定义您自己的棋盘(电话簿、棋盘等)
定义您自己的棋子(Knight、Rook、Bishop等)；您必须编写具体的类并从工厂生成它。
通过一些有用的实用方法检索几条信息。
这些类如下所示：
PadNumber:定义电话键盘上的按钮的类。可以重命名为“square”来表示一个棋盘正方形。
ChessPiece:为所有棋子定义字段的抽象类。
移动:定义移动方法并允许工厂生成部件的接口。
PieceFactory:生成国际象棋棋子的工厂类。
Knight:继承自ChessPiece并实现移动的具体类
PhoneChess:入门类。
Driver:驱动代码。
好的，下面是代码:)
package PhoneChess;
import java.awt.Point;
public class PadNumber {
private String number = "";
private Point coordinates = null;
public PadNumber(String number, Point coordinates)
{
if(number != null && number.isEmpty()==false)
this.number = number;
else
throw new IllegalArgumentException("Input cannot be null or empty.");
if(coordinates == null || coordinates.x < 0 || coordinates.y < 0)
throw new IllegalArgumentException();
else
this.coordinates = coordinates;
}
public String getNumber()
{
return this.number;
}
public Integer getNumberAsNumber()
{
return Integer.parseInt(this.number);
}
public Point getCoordinates()
{
return this.coordinates;
}
public int getX()
{
return this.coordinates.x;
}
public int getY()
{
return this.coordinates.y;
}
}ChessPiece
package PhoneChess;
import java.util.HashMap;
import java.util.List;
public abstract class ChessPiece implements Movement {
protected String name = "";
protected HashMap<PadNumber, List<PadNumber>> moves = null;
protected Integer fullNumbers = 0;
protected int[] movesFrom = null;
protected PadNumber[][] thePad = null;
}移动接口：
package PhoneChess;
import java.util.List;
public interface Movement
{
public Integer findNumbers(PadNumber start, Integer digits);
public abstract boolean canMove(PadNumber from, PadNumber to);
public List<PadNumber> allowedMoves(PadNumber from);
public Integer countAllowedMoves(PadNumber from);
}PieceFactory
package PhoneChess;
public class PieceFactory
{
public ChessPiece getPiece(String piece, PadNumber[][] thePad)
{
if(thePad == null || thePad.length == 0 || thePad[0].length == 0)
throw new IllegalArgumentException("Invalid pad");
if(piece == null)
throw new IllegalArgumentException("Invalid chess piece");
if(piece.equalsIgnoreCase("Knight"))
return new Knight("Knight", thePad);
else
return null;
}
}骑士班级
package PhoneChess;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public final class Knight extends ChessPiece implements Movement {
/**Knight movements
* One horizontal, followed by two vertical
* Or
* One vertical, followed by two horizontal
* @param name
*/
public Knight(String name, PadNumber[][] thePad)
{
if(name == null || name.isEmpty() == true)
throw new IllegalArgumentException("Name cannot be null or empty");
this.name = name;
this.thePad = thePad;
this.moves = new HashMap<>();
}
private Integer fullNumbers = null;
@Override
public Integer findNumbers(PadNumber start, Integer digits)
{
if(start == null || "*".equals(start.getNumber()) || "#".equals(start.getNumber()) ) { throw new IllegalArgumentException("Invalid start point"); }
if(start.getNumberAsNumber() == 5) { return 0; } //Consider adding an 'allowSpecialChars' condition
if(digits == 1) { return 1; };
//Init
this.movesFrom = new int[thePad.length * thePad[0].length];
for(int i = 0; i < this.movesFrom.length; i++)
this.movesFrom[i] = -1;
fullNumbers = 0;
findNumbers(start, digits, 1);
return fullNumbers;
}
private void findNumbers(PadNumber start, Integer digits, Integer currentDigits)
{
//Base condition
if(currentDigits == digits)
{
//Reset
currentDigits = 1;
fullNumbers++;
return;
}
if(!this.moves.containsKey(start))
allowedMoves(start);
List<PadNumber> options = this.moves.get(start);
if(options != null)
{
currentDigits++; //More digits to be got
for(PadNumber option : options)
findNumbers(option, digits, currentDigits);
}
}
@Override
public boolean canMove(PadNumber from, PadNumber to)
{
//Is the moves list available?
if(!this.moves.containsKey(from.getNumber()))
{
//No? Process.
allowedMoves(from);
}
if(this.moves.get(from) != null)
{
for(PadNumber option : this.moves.get(from))
{
if(option.getNumber().equals(to.getNumber()))
return true;
}
}
return false;
}
/***
* Overriden method that defines each Piece's movement restrictions.
*/
@Override
public List<PadNumber> allowedMoves(PadNumber from)
{
//First encounter
if(this.moves == null)
this.moves = new HashMap<>();
if(this.moves.containsKey(from))
return this.moves.get(from);
else
{
List<PadNumber> found = new ArrayList<>();
int row = from.getY();//rows
int col = from.getX();//columns
//Cases:
//1. One horizontal move each way followed by two vertical moves each way
if(col-1 >= 0 && row-2 >= 0)//valid
{
if(thePad[row-2][col-1].getNumber().equals("*") == false &&
thePad[row-2][col-1].getNumber().equals("#") == false)
{
found.add(thePad[row-2][col-1]);
this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
}
}
if(col-1 >= 0 && row+2 < thePad.length)//valid
{
if(thePad[row+2][col-1].getNumber().equals("*") == false &&
thePad[row+2][col-1].getNumber().equals("#") == false)
{
found.add(thePad[row+2][col-1]);
this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
}
}
if(col+1 < thePad[0].length && row+2 < thePad.length)//valid
{
if(thePad[row+2][col+1].getNumber().equals("*") == false &&
thePad[row+2][col+1].getNumber().equals("#") == false)
{
found.add(thePad[row+2][col+1]);
this.movesFrom[from.getNumberAsNumber()] = this.movesFrom[from.getNumberAsNumber()] + 1;
}
}
if(col+1 < thePad[0].length && row-2 >= 0)//valid
{
if(thePad[row-2][col+1].getNumber().equals("*") == false &&
thePad[row-2][col+1].getNumber().equals("#") == false)
found.add(thePad[row-2][col+1]);
}
//Case 2. One vertical move each way follow by two horizontal moves each way
if(col-2 >= 0 && row-1 >= 0)
{
if(thePad[row-1][col-2].getNumber().equals("*") == false &&
thePad[row-1][col-2].getNumber().equals("#") == false)
found.add(thePad[row-1][col-2]);
}
if(col-2 >= 0 && row+1 < thePad.length)
{
if(thePad[row+1][col-2].getNumber().equals("*") == false &&
thePad[row+1][col-2].getNumber().equals("#") == false)
found.add(thePad[row+1][col-2]);
}
if(col+2 < thePad[0].length && row-1 >= 0)
{
if(thePad[row-1][col+2].getNumber().equals("*") == false &&
thePad[row-1][col+2].getNumber().equals("#") == false)
found.add(thePad[row-1][col+2]);
}
if(col+2 < thePad[0].length && row+1 < thePad.length)
{
if(thePad[row+1][col+2].getNumber().equals("*") == false &&
thePad[row+1][col+2].getNumber().equals("#") == false)
found.add(thePad[row+1][col+2]);
}
if(found.size() > 0)
{
this.moves.put(from, found);
this.movesFrom[from.getNumberAsNumber()] = found.size();
}
else
{
this.moves.put(from, null); //for example the Knight cannot move from 5 to anywhere
this.movesFrom[from.getNumberAsNumber()] = 0;
}
}
return this.moves.get(from);
}
@Override
public Integer countAllowedMoves(PadNumber from)
{
int start = from.getNumberAsNumber();
if(movesFrom[start] != -1)
return movesFrom[start];
else
{
movesFrom[start] = allowedMoves(from).size();
}
return movesFrom[start];
}
@Override
public String toString()
{
return this.name;
}
}PhoneChess入门类
package PhoneChess;
public final class PhoneChess
{
private ChessPiece thePiece = null;
private PieceFactory factory = null;
public ChessPiece ThePiece()
{
return this.thePiece;
}
public PhoneChess(PadNumber[][] thePad, String piece)
{
if(thePad == null || thePad.length == 0 || thePad[0].length == 0)
throw new IllegalArgumentException("Invalid pad");
if(piece == null)
throw new IllegalArgumentException("Invalid chess piece");
this.factory = new PieceFactory();
this.thePiece = this.factory.getPiece(piece, thePad);
}
public Integer findPossibleDigits(PadNumber start, Integer digits)
{
if(digits <= 0)
throw new IllegalArgumentException("Digits cannot be less than or equal to zero");
return thePiece.findNumbers(start, digits);
}
public boolean isValidMove(PadNumber from, PadNumber to)
{
return this.thePiece.canMove(from, to);
}
}驱动程序代码：
public static void main(String[] args) {
PadNumber[][] thePad = new PadNumber[4][3];
thePad[0][0] = new PadNumber("1", new Point(0,0));
thePad[0][1] = new PadNumber("2", new Point(1,0));
thePad[0][2] = new PadNumber("3",new Point(2,0));
thePad[1][0] = new PadNumber("4",new Point(0,1));
thePad[1][1] = new PadNumber("5",new Point(1,1));
thePad[1][2] = new PadNumber("6", new Point(2,1));
thePad[2][0] = new PadNumber("7", new Point(0,2));
thePad[2][1] = new PadNumber("8", new Point(1,2));
thePad[2][2] = new PadNumber("9", new Point(2,2));
thePad[3][0] = new PadNumber("*", new Point(0,3));
thePad[3][1] = new PadNumber("0", new Point(1,3));
thePad[3][2] = new PadNumber("#", new Point(2,3));
PhoneChess phoneChess = new PhoneChess(thePad, "Knight");
System.out.println(phoneChess.findPossibleDigits(thePad[0][1],4));
}
}Stack Overflow用户
发布于 2010-05-26 02:32:57
这可以在O(log )内完成。将键盘和在其上可能的运动看作一个图G(V，E)，其中顶点是可用的数字，边表示哪些数字可以跟随在哪些数字之后。现在，对于每个输出位置i，我们可以形成一个向量路径(I)，其中包含每个顶点可以到达的不同路径的数量。现在很容易看出，对于给定的位置i和数字v，它可以到达的可能路径是可能的前几个数字可以到达的不同路径的总和，或者路径(I ) v= v2 (路径(i-1)v2*(1if (v，v2) in E else 0)，对于V中的v2)。现在，这是将前面的向量的每个位置乘以邻接矩阵列中的相应位置之和。因此，我们可以将其简化为路径(I)=路径(i-1)·A，其中A是图的邻接矩阵。去掉递归并利用矩阵乘法的结合性，这就变成了路径(I)=路径(1)·A^(i-1)。我们知道路径( 1 )：我们只有一条路径，到数字1。
N位数字的路径总数是每个数字的路径之和，因此最终的算法为: TotalPaths(n) = sum( 1,0,0,0,0,0,0,0,0,0，0·A^(n-1) )
幂可以通过平方计算O(log(n))时间，给定常数时间乘法，否则O(M(n) * log(n))，其中M(n)是您喜欢的n位数的任意精度乘法算法的复杂度。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2893470
复制相关文章
相似问题
腾讯云开发者
