24

以下に示すような電話のキーパッドがあるとします。

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 の反復が必要になります。

ここでの変数は桁数です。私は例を取った。10桁の数字。n桁でも構いません。

4

12 に答える 12

42

確かに多項式時間で実行できます。これは、動的プログラミングまたはメモ化の優れた演習です。

この例では、N (桁数) が 10 に等しいと仮定します。

次のように再帰的に考えてみてください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 です)。

複雑さに関して言えば、重要な観察事項は、以前に計算されたソリューションを再利用することです。つまり、たとえば、「 から始まる 5 桁の数字はいくつあるか」という答え、 「「」から始まる 6 桁の数字はいくつある3と「「」から始まる 6 桁の数字はいくつあるか」という8答えの両方で使用できます。から4。この再利用により、複雑さが指数関数から多項式に崩壊します。

動的計画法ソリューションの複雑さを詳しく見てみましょう。

このような実装は、次の方法で行列を埋めます。

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.

このアルゴリズムは、一度に 1 つのセルを行列に入力するだけで、行列の次元は 10*N であるため、線形時間で実行されます。


勝手に書いたので誤字脱字等ありましたら訂正お願いします。

于 2010-05-23T21:37:59.063 に答える
2

私はこの問題に取り組み、可能な限り拡張可能にすることにしました。このソリューションにより、次のことが可能になります。

独自のボードを定義する (フォーン パッド、チェス ボードなど)

独自のチェスの駒 (ナイト、ルーク、ビショップなど) を定義します。具体的なクラスを作成し、ファクトリから生成する必要があります。

いくつかの便利なユーティリティ メソッドを使用して、いくつかの情報を取得します。

クラスは次のとおりです。

PadNumber: 電話パッドのボタンを定義するクラス。ボードの正方形を表すために「Square」に名前を変更できます。

ChessPiece: すべてのチェスの駒のフィールドを定義する抽象クラス。

移動: 移動方法を定義し、ピースのファクトリ生成を可能にするインターフェイス。

PieceFactory: チェスの駒を生成するファクトリ クラス。

Knight: ChessPiece を継承し、Movement を実装する具象クラス

PhoneChess: 入学クラス。

ドライバー: ドライバーコード。

OK、これがコードです:)

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;
}

}

チェスの駒

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);
}

ピースファクトリー

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));
}

}
于 2016-01-28T07:43:37.270 に答える
1

これは O(log N) で実行できます。キーパッドとその上で可能な動きをグラフG(V, E)として考えます。ここで、頂点は使用可能な数字であり、エッジはどの数字がどの数字に続くかを示します。これで、各出力位置iに対して、各頂点に到達できるさまざまなパスの数を含むベクトルPaths(i)を形成できます。これで、特定の位置iと数字vに対して、可能なパスを簡単に確認できます。経由する可能性のある先行する数字に到達する可能性のあるさまざまなパスの合計、またはPaths(i)[v] = sum(Paths(i-1)[v2] * (E の (v,v2) の場合は 1)そうでなければ 0) V の v2 の場合). ここで、これは、隣接行列の列内の対応する位置を前のベクトルに掛けた各位置の合計をとっています。したがって、これをPaths(i) = Paths(i-1) · A のように簡略化できます。ここで、Aはグラフの隣接行列です。再帰を取り除き、行列乗算の結合性を利用すると、これはPaths(i) = Paths(1) · A^(i-1)になります。Paths(1)を知っています: 数字 1 へのパスは 1 つしかありません。

n 桁の数値のパスの総数は各桁のパスの合計であるため、最終的なアルゴリズムは次のようになります。TotalPaths(n) = sum( [1,0,0,0,0,0,0,0, 0,0] · A^(n-1) )

べき乗は、 O(log(n))時間の2 乗によって計算できます。一定の時間が乗算される場合、それ以外の場合はO(M(n) * log(n))です。M(n)は、お気に入りの任意精度乗算アルゴリズムの複雑さです。n桁の数字の場合。

于 2010-05-25T18:32:56.877 に答える
1

何かを見逃したかどうかはわかりませんが、問題の説明を読んでこの解決策にたどり着きました。O(n) の時間の複雑さと O(1) の空間の複雑さがあります。

1番は角にあると思いましたよね?各コーナーでは、いずれかの辺 (9 と 3 から 4、または 7 と 1 から 6) または「垂直」辺 (3 と 1 から 8、または 9 と 7 から 2) のいずれかに移動できます。したがって、コーナーは 2 つの動きを追加します: 横の動きと「垂直」の動きです。これは 4 つのコーナーすべて (1、3、9、7) に当てはまります。

それぞれの側から、2 つのコーナー (6 から 7 と 1、4 から 9 と 3) に移動するか、一番下のキー (0) に到達できます。それは3つの動きです。2 つのコーナーと 1 つの底。

下のキー (0) では、両側 (4 と 6) に移動できます。したがって、各ステップで、前の長さのパスのすべての可能なエンディング (つまり、コーナー、サイド、「垂直」または「ボトム」ゼロ キーで終了する数) をチェックしてから、新しいエンディングを生成します。前述の生成規則に従ってカウントされます。

  • 各角の終点は、側面と垂直を追加します。
  • 各サイドエンドは、2 つのコーナーとボトムを追加します。
  • 垂直方向の端点ごとに 2 つのコーナーが追加されます。
  • 各下端は 2 つの側面を追加します。

前のステップから可能性を生み出す

「1」キーから開始する場合は、1 つの可能なコーナー ソリューションから開始します。各ステップで、前のステップのコーナー、サイド、垂直、およびボトム エンドの数をカウントし、ルールを適用して次のカウントを生成します。

プレーンな JavaScript コードで。

function paths(n) {
    //Index to 0
    var corners = 1;
    var verticals = 0;
    var bottom = 0;
    var sides = 0;

    if (n <= 0) {
        //No moves possible for paths without length 
        return 0;
    }

    for (var i = 1; i < n; i++) {
        var previousCorners = corners;
        var previousVerticals = verticals;
        var previousBottom = bottom;
        var previousSides = sides;

        sides = 1 * previousCorners + 2 * previousBottom;
        verticals = 1 * previousCorners;
        bottom = 1 * previousSides;
        corners = 2 * previousSides + 2 * previousVerticals;
        //console.log("Moves: %d, Length: %d, Sides: %d, Verticals: %d, Bottom: %d, Corners: %d, Total: %d", i, i + 1, sides, verticals, bottom, corners, sides+verticals+bottom+corners);  
    }

    return sides + verticals + bottom + corners;

}

for (var i = 0; i <= 10; i++) {
    console.log(paths(i));  
}
于 2016-04-11T02:40:04.383 に答える
1

より簡単な答え。

#include<stdio.h>

int a[10] = {2,2,2,2,3,0,3,2,2,2};
int b[10][3] = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}};

int count(int curr,int n)
{
    int sum = 0;
    if(n==10)
        return 1;
    else
    {
        int i = 0;
        int val = 0;
        for(i = 0; i < a[curr]; i++)
        {
            val = count(b[curr][i],n+1);
            sum += val;
        }
        return sum;
    }
}

int main()
{
    int n = 1;
    int val = count(1,0);
    printf("%d\n",val);
}

祝う!!

于 2010-05-29T21:40:25.127 に答える
0
//Both the iterative and recursive with memorize shows count as 1424 for 10 digit numbers starting with 1. 
int[][] b = {{4,6},{6,8},{7,9},{4,8},{0,3,9},{},{1,7,0},{2,6},{1,3},{2,4}};
public int countIterative(int digit, int length) {
    int[][] matrix = new int[length][10];
    for(int dig =0; dig <=9; dig++){
          matrix[0][dig] = 1;
    }
    for(int len = 1; len < length; len++){
        for(int dig =0; dig <=9; dig++){
          int sum = 0;
          for(int i : b[dig]){
            sum += matrix[len-1][i];
          }
          matrix[len][dig] = sum;
        }
    }
    return matrix[length-1][digit];
}

public int count(int index, int length, int[][] matrix ){
    int sum = 0;
    if(matrix[length-1][index] > 0){
        System.out.println("getting value from memoize:"+index + "length:"+ length);
        return matrix[length-1][index];
    }
    if( length == 1){
        return 1;
    }
    for(int i: b[index] )  {
         sum += count(i, length-1,matrix);
    }
    matrix[length-1][index] = sum;
    return sum;
}
于 2016-04-04T15:06:31.623 に答える
0

この問題は、制約充足問題(略して CSP)としてモデル化することもできます。

ここにあるMinionソルバー (高速でスケーラブル)を使用することをお勧めします

モデリングは退屈で時間がかかるかもしれません (学習曲線が急です)。

Minion 言語入力を使用する代わりに、 ESSENCEなどのソルバーに依存しないモデリング言語でモデルを定式化し、それに応じてコンバーターを見つけることをお勧めします。

于 2011-12-14T07:21:40.990 に答える