使用电话键盘产生10位数字 [英] Generate 10-digit number using a phone keypad

问题描述

由于手机键盘，如下所示：

Given a phone keypad as shown below:

1 2 3
4 5 6
7 8 9
  0

有多少种不同的10位号码，可形成从1开始？约束是，从1数位移动到下一个类似于骑士的一盘棋的运动。

How many different 10-digit numbers can be formed starting from 1? The constraint is that the movement from 1 digit to the next is similar to the movement of the Knight in a chess game.

有关，例如。如果我们在1，则下一个数字可以是6或8 如果我们在6再下一个数字可以是1,7或0。

For eg. if we are at 1 then the next digit can be either 6 or 8 if we are at 6 then the next digit can be 1, 7 or 0.

数字重复允许 - 1616161616是有效的数字

Repetition of digits are allowed - 1616161616 is a valid number.

有一个多项式时间算法来解决这个问题？这个问题要求我们只给了10位数字的计数并不见得列表中的号码。

Is there a polynomial time algorithm which solves this problem? The problem requires us to just give the count of 10-digit numbers and not necessarily list the numbers.

编辑：我试图与具有2或3个数字作为其邻国每个数字的图形建模这一点。然后我用DFS导航高达10节点的深度，然后我达到了10本深度显然不是多项式时间每次递增号的个数。假设每个数位刚刚2的邻居，这将需要至少2 ^ 10次迭代。

I tried modeling this as a graph with each digit having 2 or 3 digits as its neighbors. Then I used DFS to navigate upto the depth of 10 nodes and then increment the count of numbers each time I reached the depth of 10. This obviously is not polynomial time. Assuming each digit had just 2 neighbors, this would have required at least 2^10 iterations.

这里的变量是位数。我已如。 10位数字。它可以同时为n个数字。

The variable here is the number of digits. I have taken the eg. of 10 digit numbers. It could as well be n-digits.

推荐答案

当然也可以在多项式时间内完成。这是一个极好的锻炼在动态规划或的记忆化。

Sure it can be done in polynomial time. It's an excellent exercise in dynamic programming or memoization.

让我们假设N（位数）等于10的例子中

Lets assume N (the number of digits) equals 10 for the example.

把它递归是这样的：多少号可以建造使用10位启动 1 的

Think of it recursively like this: How many numbers can I construct using 10 digits starting from 1?

答案是

[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]

等。当你的问题基本情况达成的有多少1位数的号码有从 X启动的（答案是很明显1）

and so on. Base case is reached when you get the question "How many 1-digit numbers are there starting from X" (and the answer is obviously 1).

当谈到复杂性，关键的一点是，你重复使用previously计算解决方案。也就是说，例如，回答的从 3 开始多少5位数字的有，可以应答的 和多少个6位数字是有启动<$ C $有多少6位数的号码有从 8 启动 C> 4 的。这种重用使复杂坍塌指数为多项式。

When it comes to complexity, the key observation is that you reuse previously computed solutions. That is for instance, the answer to "how many 5-digit numbers starting from 3" there are, can be used both when answering "how many 6-digit numbers are there starting from 8" AND "how many 6-digit numbers are there starting from 4". This reuse make the complexity collapse from exponential to polynomial.

让我们来仔细看一下的动态规划解决方案的复杂性：

Let's take a closer look at the complexity of a dynamic programming solution:

这样的实现将填补成矩阵以下面的方式：

Such implementation would fill in a matrix in the following way:

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，并且因此运行在的线性时间

从我的头顶把它写下来，请大家指正，如果有任何错别字。

Wrote it down from the top of my head, please correct me if there are any typos.

这篇关于使用电话键盘产生10位数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！