قم بإنشاء رقم مكون من 10 أرقام باستخدام لوحة مفاتيح الهاتف
https://stackoverflow.com/questions/2893470
-
04-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
بالنظر إلى لوحة مفاتيح الهاتف كما هو موضح أدناه:
1 2 3
4 5 6
7 8 9
0
كم عدد أرقام 10 أرقام مختلفة يمكن تشكيلها بدءًا من 1؟ القيد هو أن الحركة من رقم واحد إلى التالي تشبه حركة الفارس في لعبة الشطرنج.
على سبيل المثال. إذا كنا في 1 ، فيمكن أن يكون الرقم التالي 6 أو 8 إذا كان لدينا في السادسة من العمر ، فيمكن أن يكون الرقم التالي 1 أو 7 أو 0.
يُسمح بتكرار الأرقام - 1616161616 هو رقم صالح.
هل هناك خوارزمية زمنية متعددة الحدود تحل هذه المشكلة؟ تتطلب المشكلة منا أن نعطي عددًا من 10 أرقام وليس بالضرورة سرد الأرقام.
تحرير: حاولت نمذجة هذا كرسوم بيانية مع كل رقم يحتوي على 2 أو 3 أرقام كجيرانه. ثم استخدمت DFS للتنقل حتى عمق 10 عقد ثم زيادة عدد الأرقام في كل مرة وصلت فيها إلى عمق 10. هذا من الواضح أنه ليس وقتًا متعدد الحدود. على افتراض أن كل رقم كان له جيران فقط ، فقد يتطلب ذلك ما لا يقل عن 2^10 تكرار.
المتغير هنا هو عدد الأرقام. لقد أخذت على سبيل المثال. من 10 أرقام أرقام. يمكن أن يكون أرقام n.
المحلول
من المؤكد أنه يمكن القيام به في وقت الحدود. إنه تمرين ممتاز في البرمجة الديناميكية أو المذكرات.
دعنا نفترض n (عدد الأرقام) يساوي 10 للمثال.
فكر في الأمر بشكل متكرر مثل هذا: كم عدد الأرقام التي يمكنني إنشاءها باستخدام 10 أرقام تبدأ من 1?
الإجابه هي
[number of 9-digit numbers starting from 8] +
[number of 9-digit numbers starting from 6].
لذا كم عدد الأرقام المكونة من 9 أرقام تبدأ من 8 "؟ نحن سوف،
[number of 8-digit numbers starting from 1] +
[number of 8-digit numbers starting from 3]
وهلم جرا. يتم الوصول إلى حالة الأساس عندما تحصل على السؤال "كم عدد الأرقام المكونة من رقم واحد تبدأ من X" (والجواب واضح 1).
عندما يتعلق الأمر بالتعقيد ، فإن الملاحظة الرئيسية هي إعادة استخدام الحلول المحسوبة مسبقًا. هذا على سبيل المثال ، الجواب على "كم عدد الأرقام المكونة من 5 أرقام تبدأ من 3" هناك ، يمكن استخدامها على حد سواء عند الرد "كم عدد الأرقام المكونة من 6 أرقام تبدأ من 8" و "كم عدد الأرقام المكونة من 6 أرقام تبدأ من 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.
تملأ الخوارزمية ببساطة خلية المصفوفة في وقت واحد ، والمصفوفة ذات البعد 10*n ، وبالتالي تعمل الوقت الخطي.
كتبها من أعلى رأسي ، يرجى تصحيحني إذا كان هناك أي أخطاء مطبعية.
نصائح أخرى
قررت معالجة هذه المشكلة وجعلها قابلة للتمديد قدر الإمكان. يتيح لك هذا الحل:
حدد اللوحة الخاصة بك (لوحة الهاتف ، لوحة الشطرنج ، وما إلى ذلك)
حدد قطعة الشطرنج الخاصة بك (Knight ، Rook ، Bishop ، إلخ) ؛ سيكون عليك كتابة الفصل الخرساني وإنشائه من المصنع.
استرجاع عدة أجزاء من المعلومات من خلال بعض أساليب المنفعة المفيدة.
الفصول هي كما يلي:
Padnumber: فئة تحديد زر على لوحة الهاتف. يمكن إعادة تسمية "المربعة" لتمثيل ميدان اللوحة.
الشطرنج: فئة مجردة تحدد الحقول لجميع قطع الشطرنج.
الحركة: واجهة تحدد طرق الحركة وتسمح بتوليد المصنع من القطع.
PITEFACTORY: فئة المصنع لتوليد قطع الشطرنج.
فارس: فئة ملموسة ترث من الشطرنج وتنفذ الحركة
Phonechess: فئة المدخل.
برنامج التشغيل: رمز برنامج التشغيل.
حسنًا ، هذا هو الرمز :)
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);
}
picefactory
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;
}
}
فئة المشتركة الصوتية
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));
}
}
يمكن القيام بذلك في O (log n). النظر في لوحة المفاتيح والتحركات المحتملة عليها كرسم بياني ز (الخامس ، هـ) حيث تكون القمم هي الأرقام والحواف المتاحة التي تقول الأرقام التي يمكن أن تتبع أيها. الآن لكل موضع مخرج أنا يمكننا تشكيل متجه مسارات (ط) تحتوي على عدد من المسارات المختلفة التي يمكن الوصول إليها كل قمة. أنا والرقم الخامس, ، المسارات المحتملة التي يمكن الوصول إليها هي مجموع المسارات المختلفة التي يمكن الوصول إليها من خلال الأرقام السابقة المحتملة أو المسارات (i) [v] = sum (مسارات (i-1) [v2] * (1 إذا (v ، v2) في e else 0) لـ v2 في v). الآن ، هذا يأخذ مجموع كل موضع في أوقات المتجه السابقة موضعًا مقابلًا في عمود من مصفوفة المجاورة. حتى نتمكن من تبسيط هذا كـ المسارات (i) = المسارات (I-1) · أ, ، أين أ هي مصفوفة المجاورة من الرسم البياني. التخلص من العودة والاستفادة من ارتباط تكاثر المصفوفة ، يصبح هذا المسارات (i) = المسارات (1) · a^(i-1). نعلم مسارات (1): لدينا مسار واحد فقط ، إلى الرقم 1.
إجمالي عدد المسارات لرقم N هو مجموع المسارات لكل رقم ، وبالتالي تصبح الخوارزمية النهائية: TotalPaths (n) = sum ([1،0،0،0،0،0،0،0،0] · a^(n-1))
يمكن حساب الأسعار عن طريق التربيع في س (سجل (ن)) الوقت ، بالنظر إلى مضاعفات وقت ثابت ، وإلا o (m (n) * log (n)) أين م (ن) هو تعقيد خوارزمية الضرب الدقة التعسفية المفضلة لديك ن أرقام أرقام.
إجابة أبسط.
#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);
}
احتفل!!
حل وقت تشغيل الوقت الثابت:
#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;
}
تقوم الطريقة بإرجاع قائمة أرقام 10 أرقام تبدأ بـ 1. مرة أخرى العدد هو 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;
}
لست متأكدًا مما إذا فاتني شيء ما ، لكن قراءة وصف المشكلة التي جئت إلى هذا الحل. لديها تعقيد الوقت (ن) و O (1) تعقيد الفضاء.
كنت أحسب أن الرقم 1 في زاوية ، أليس كذلك؟ في كل زاوية ، يمكنك إما الانتقال إلى أحد الجانبين (4 من 9 و 3 ، أو 6 من 7 A 1) أو أحد الجانبين "العمودي" (8 من 3 و 1 ، أو 2 من 9 و 7). لذلك ، تضيف الزوايا حركتين: خطوة جانبية وحركة "رأسية". هذا صحيح لجميع الزوايا الأربعة (1،3،9،7).
من كل جانب ، يمكنك إما الانتقال إلى زاويتين (7 و 1 من 6 و 9 و 3 من 4) أو يمكنك الوصول إلى المفتاح السفلي (0). هذه ثلاث تحركات. زاويتان وأسفل واحد.
على المفتاح السفلي (0) ، يمكنك الانتقال إلى كلا الجانبين (4 و 6). لذلك ، في كل خطوة ، يمكنك التحقق من جميع النهايات الممكنة لمسار الطول السابق (أي ، كم من ينتهي في الزاوية أو جانب أو "عمودي" أو مفتاح صفر "أسفل") ثم إنشاء نهاية جديدة التهم وفقا لقواعد التوليد المذكورة من قبل.
- كل زاوية تنتهي يضيف جانبًا ورأسيًا.
- كل جانب ينتهي يضيف 2 زاوية وأسفل.
- كل نهاية عمودية تضيف 2 زاوية.
- كل نهاية أسفل يضيف جانبين.
إذا بدأت من مفتاح "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));
}
قد يتم أيضًا تصميم هذه المشكلة على أنها أ مشكلة رضا القيد (الملقب CSP لفترة قصيرة).
أقترح استخدام تابع حلال (سريع وقابل للتطوير) الذي يمكنك العثور عليه هنا.
النمذجة ربما مملة ومهمة للوقت (منحنى التعلم الحاد).
بدلاً من استخدام مدخلات لغة Minion ، نصيحتي هي صياغة النموذج بلغة النمذجة المستقلة Solver مثل جوهر وابحث عن محول وفقًا لذلك.
//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;
}
نهج المذكرات العودية:
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);
}
لقد قمت بتنفيذ كل من نماذج القوة الغاشمة ونماذج البرمجة الديناميكية
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')
الوظيفة العودية في جافا:
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;
}
}
}
