Générer numéro à 10 chiffres à l'aide d'un clavier de téléphone
https://stackoverflow.com/questions/2893470
-
04-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Étant donné un clavier téléphonique comme indiqué ci-dessous:
1 2 3
4 5 6
7 8 9
0
Combien de numéros à 10 chiffres peut être formé à partir de 1? La contrainte est que le mouvement de 1 chiffre à l'autre est similaire au mouvement du chevalier dans un jeu d'échecs.
Pour exemple. si nous sommes à 1 alors le chiffre suivant peut être 6 ou 8 si nous sommes à 6 alors le chiffre suivant peut être 1, 7 ou 0.
La répétition des chiffres sont autorisés -. 1616161616 est un numéro valide
Yat-il un algorithme polynomial qui résout ce problème? Le problème nous oblige à juste donner le nombre de numéros à 10 chiffres et la liste pas nécessairement les chiffres.
EDIT: J'essayé cette modélisation sous forme de graphique à chaque chiffre ayant 2 ou 3 chiffres que ses voisins. Ensuite, je DFS pour naviguer jusqu'à la profondeur de 10 noeuds, puis augmenter le nombre de numéros chaque fois que j'atteint la profondeur de 10. Ceci est évidemment pas le temps polynomiale. En supposant que chaque chiffre avait seulement deux voisins, il aurait fallu au moins 2 ^ 10 itérations.
La variable est ici le nombre de chiffres. J'ai pris l'exemple. de 10 chiffres. Il pourrait aussi bien être n chiffres.
La solution
Bien sûr, il peut être fait en temps polynomial. Il est un excellent exercice programmation dynamique ou memoization .
permet de supposer N (le nombre de chiffres) est égal à 10 pour l'exemple.
Pensez-y récursive comme ceci: Combien de numéros puis-je construire en utilisant 10 chiffres à partir de 1
La réponse est
[number of 9-digit numbers starting from 8] +
[number of 9-digit numbers starting from 6].
combien de "numéros à 9 chiffres à partir de 8" sont là? Eh bien,
[number of 8-digit numbers starting from 1] +
[number of 8-digit numbers starting from 3]
et ainsi de suite. Cas de base est atteint lorsque vous obtenez la question « Combien de numéros 1 chiffres sont là à partir de X » (et la réponse est évidemment 1).
En ce qui concerne la complexité, l'observation clé est que vous réutilisez des solutions calculées précédemment. C'est par exemple, la réponse à « combien de numéros à 5 chiffres à partir de 3 » il y a, peut être utilisé à la fois en répondant à "le nombre de numéros à 6 chiffres sont là à partir de 8 " et " combien y at-il en partant de 4 " numéros à 6 chiffres. Cette réutilisation fait l'effondrement de la complexité exponentielle de polynôme.
Jetons un coup d'oeil de plus près la complexité d'une solution de programmation dynamique:
Une telle mise en œuvre comblerait une matrice de la manière suivante:
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.
L'algorithme remplit simplement la matrice une cellule à la fois, et la matrice est de dimension 10 * N, et fonctionne ainsi en temps linéaire .
a écrite à partir du haut de ma tête, s'il vous plaît me corriger s'il y a des fautes de frappe.
Autres conseils
J'ai décidé d'aborder ce problème et le rendre aussi extensible que je peux. Cette solution vous permet de:
Définissez votre propre conseil d'administration (clavier téléphonique, carte d'échecs, etc.)
Définissez votre propre pièce d'échecs (chevalier, freux, évêque, etc.); vous devrez écrire la classe de béton et générer de l'usine.
Récupérer plusieurs informations par quelques méthodes utilitaires utiles.
Les classes sont comme suit:
PadNumber: classe définissant un bouton sur le clavier du téléphone. Pourrait être rebaptisé « carré » pour représenter un carré de bord.
ChessPiece. Classe abstraite qui définit des champs pour toutes les pièces d'échecs
Mouvement. Interface qui définit les méthodes de mouvement et permet la production d'usine de pièces
PieceFactory. Classe usine pour produire des pièces d'échecs
Chevalier: Classe de béton qui hérite de ChessPiece et met en œuvre Mouvement
PhoneChess. Classe d'entrée
Driver: Code pilote
.OK, voici le code:)
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;
}
Interface Mouvement:
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;
}
}
class Chevalier
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 classe participant
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);
}
}
Code de Driver:
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));
}
}
Cela peut être fait en O (log N). Considérons le clavier et les mouvements possibles sur elle comme un graphique G (V, E) où les sommets sont les chiffres disponibles et les bords disent quels chiffres peuvent suivre qui. Maintenant, pour chaque position de sortie i nous pouvons former un vecteur Les chemins (i) contenant le nombre de chemins différents chaque sommet peut être atteint. Maintenant, il est assez facile de voir que pour une position donnée i et chiffres v , les chemins possibles que cela peut être atteint par l'intermédiaire est la somme des différents chemins possibles chiffres précédents peuvent être atteints à travers, ou Chemins (i) [v] = somme (chemins (i-1) [v2] * (1 si (v, v2) dans E sinon 0) pour v2 en V) . Or, cela prend la somme de chaque position les précédentes fois un vecteur de position correspondant à une colonne de la matrice de contiguïté. Ainsi, nous pouvons simplifier comme Les chemins (i) = Les chemins (i-1) · A , où A est la matrice de contiguïté du graphique. Se débarrasser de la récursivité et en tirant parti de l'associativité de la multiplication de la matrice, cela devient Les chemins (i) = Les chemins (1) · A ^ (i-1) . Nous savons Chemins (1) :. Nous avons un seul chemin, au chiffre 1
Le nombre total de chemins d'accès pour un nombre n de chiffres est la somme des trajets pour chaque chiffre, de sorte que l'algorithme final devient: TotalPaths (n) = somme ([1,0,0,0,0, 0,0,0,0,0] · A ^ (n-1))
Le exponentiation peut être calculée par élévation au carré dans O (log (n)) temps, multiplications à temps constant donné, sinon O (M (n) * log (n)) où M (n) est la complexité de votre algorithme de multiplication de précision arbitraire favori pour n chiffres.
Une réponse plus simple.
#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);
}
HONORER !!
Durée solution à temps constant:
#include <iostream>
constexpr int notValid(int x, int y) {
return !(( 1 == x && 3 == y ) || //zero on bottom.
( 0 <= x && 3 > x && //1-9
0 <= y && 3 > y ));
}
class Knight {
template<unsigned N > constexpr int move(int x, int y) {
return notValid(x,y)? 0 : jump<N-1>(x,y);
}
template<unsigned N> constexpr int jump( int x, int y ) {
return move<N>(x+1, y-2) +
move<N>(x-1, y-2) +
move<N>(x+1, y+2) +
move<N>(x-1, y+2) +
move<N>(x+2, y+1) +
move<N>(x-2, y+1) +
move<N>(x+2, y-1) +
move<N>(x-2, y-1);
}
public:
template<unsigned N> constexpr int count() {
return move<N-1>(0,1) + move<N-1>(0,2) +
move<N-1>(1,0) + move<N-1>(1,1) + move<N-1>(1,2) +
move<N-1>(2,0) + move<N-1>(2,1) + move<N-1>(2,2);
}
};
template<> constexpr int Knight::move<0>(int x, int y) { return notValid(x,y)? 0 : 1; }
template<> constexpr int Knight::count<0>() { return 0; } //terminal cases.
template<> constexpr int Knight::count<1>() { return 8; }
int main(int argc, char* argv[]) {
static_assert( ( 16 == Knight().count<2>() ), "Fail on test with 2 lenght" ); // prof of performance
static_assert( ( 35 == Knight().count<3>() ), "Fail on test with 3 lenght" );
std::cout<< "Number of valid Knight phones numbers:" << Knight().count<10>() << std::endl;
return 0;
}
Méthode renvoie la liste de 10 numéros de chiffres commençant par 1. Là encore, le comptage est 1424.
public ArrayList<String> getList(int digit, int length, String base ){
ArrayList<String> list = new ArrayList<String>();
if(length == 1){
list.add(base);
return list;
}
ArrayList<String> temp;
for(int i : b[digit]){
String newBase = base +i;
list.addAll(getList(i, length -1, newBase ));
}
return list;
}
Je ne sais pas si je raté quelque chose, mais la lecture de la description du problème que je suis venu à cette solution. Il a O (n) complexité temporelle et O (1) la complexité de l'espace.
Je me suis dit que le numéro 1 est à un coin, non? Dans chaque coin, vous pouvez déplacer vers l'un des côtés (4 et 9 à partir de 3, 6 ou 7 de un 1) ou l'un des côtés « verticaux » (8 à partir de 3 et 1, ou 2 à partir de 9 et 7). Ainsi, les coins ajoutent deux mouvements: un mouvement latéral et un mouvement « vertical ». Cela est vrai pour les quatre coins (1,3,9,7).
De chaque côté, on peut soit déplacer à deux coins (7 et 1 à partir de 6, 9 et 3 de 4) ou on peut atteindre la touche du bas (0). C'est trois coups. Deux coins et un en bas.
Sur la touche inférieure (0), vous pouvez déplacer des deux côtés (4 et 6). Ainsi, à chaque étape, vous vérifiez toutes les fins possibles pour le chemin de la longueur précédente (qui est, combien a pris fin sur un coin, un côté, une « verticale » ou sur la touche zéro « bas »), puis générer nouvelle fin compte selon les règles établies avant génération.
- Chaque coin se termine ajoute un côté et une verticale.
- Chaque côté se terminant ajoute 2 coins et un fond.
- Chaque fin verticale ajoute 2 coins.
- Chaque fin fond ajoute 2 côtés.
Si vous partez de la « 1 » clé, vous commencez avec une solution d'angle possible, à chaque étape que vous comptez le nombre de coin, côté, terminaisons verticales et en bas de l'étape précédente, puis d'appliquer les règles pour générer la prochaine compter.
Dans le code javascript clair.
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));
}
Ce problème peut également être modélisé comme un problème satisfaction Constraint (alias CSP pour faire court).
Je suggère d'utiliser le Minion solveur (rapide et évolutive) que vous pouvez trouver ici .
La modélisation peut-être fastidieux et chronophage consumming (courbe d'apprentissage abrupte).
Au lieu d'utiliser l'entrée de la langue Minion, mon conseil est de formuler le modèle avec le solutionneur langage de modélisation indépendant tel que et ESSENTIEL trouver un convertisseur en conséquence.
//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;
}
récursive approche memoization:
vector<vector<int>> lupt = { {4, 6}, {6, 8}, {9, 7}, {4, 8}, {3, 9, 0},
{}, {1,7,0}, {6, 2}, {1, 3}, {2, 4} };
int numPhoneNumbersUtil(int startdigit, int& phonenumberlength, int currCount, map< pair<int,int>,int>& memT)
{
int noOfCombs = 0;
vector<int> enddigits;
auto it = memT.find(make_pair(startdigit,currCount));
if(it != memT.end())
{
noOfCombs = it->second;
return noOfCombs;
}
if(currCount == phonenumberlength)
{
return 1;
}
enddigits = lupt[startdigit];
for(auto it : enddigits)
{
noOfCombs += numPhoneNumbersUtil(it, phonenumberlength, currCount + 1, memT);
}
memT.insert(make_pair(make_pair(startdigit,currCount), noOfCombs));
return memT[make_pair(startdigit,currCount)];
}
int numPhoneNumbers(int startdigit, int phonenumberlength)
{
map<pair<int,int>,int> memT;
int currentCount = 1; //the first digit has already been added
return numPhoneNumbersUtil(startdigit, phonenumberlength, currentCount, memT);
}
Je mis en œuvre à la fois la force brute et les modèles de programmation dynamique
import queue
def chess_numbers_bf(start, length):
if length <= 0:
return 0
phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
total = 0
q = queue.Queue()
q.put((start, 1))
while not q.empty():
front = q.get()
val = front[0]
len_ = front[1]
if len_ < length:
for elm in phone[val]:
q.put((elm, len_ + 1))
else:
total += 1
return total
def chess_numbers_dp(start, length):
if length <= 0:
return 0
phone = [[7, 5], [6, 8], [3, 7], [9, 2, 8], [], [6, 9, 0], [1, 5], [0, 2], [3, 1], [5, 3]]
memory = {}
def __chess_numbers_dp(s, l):
if (s, l) in memory:
return memory[(s, l)]
elif l == length - 1:
memory[(s, l)] = 1
return 1
else:
total_n_ways = 0
for number in phone[s]:
total_n_ways += __chess_numbers_dp(number, l+1)
memory[(s, l)] = total_n_ways
return total_n_ways
return __chess_numbers_dp(start, 0)
# bf
for i in range(0, 10):
print(i, chess_numbers_bf(3, i))
print('\n')
for i in range(0, 10):
print(i, chess_numbers_bf(9, i))
print('\n')
# dp
for i in range(0, 10):
print(i, chess_numbers_dp(3, i))
print('\n')
# dp
for i in range(0, 10):
print(i, chess_numbers_dp(9, i))
print('\n')
fonction récursive en Java:
public static int countPhoneNumbers (int n, int r, int c) {
if (outOfBounds(r,c)) {
return 0;
} else {
char button = buttons[r][c];
if (button == '.') {
// visited
return 0;
} else {
buttons[r][c] = '.'; // record this position so don't revisit.
// Count all possible phone numbers with one less digit starting
int result=0;
result = countPhoneNumbers(n-1,r-2,c-1)
+ countPhoneNumbers(n-1,r-2,c+1)
+ countPhoneNumbers(n-1,r+2,c-1)
+ countPhoneNumbers(n-1,r+2,c+1)
+ countPhoneNumbers(n-1,r-1,c-2)
+ countPhoneNumbers(n-1,r-1,c+2)
+ countPhoneNumbers(n-1,r+1,c-2)
+ countPhoneNumbers(n-1,r+1,c+2);
}
buttons[r][c] = button; // Remove record from position.
return result;
}
}
}
