د ګرځنده شمیره کیپيډ ستونزه


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon MAQ د Microsoft سپرینکلر
ګډ متحرک برنامې جدول تار

ستونزه بیان

د ګرځنده شمیرو کیپیډ ستونزې کې ، موږ د شمیره کیپيډ په پام کې نیولو سره. موږ اړتیا لرو د ورکړل شوي اوږدوالي ټول احتمالي شمیرې لړۍ ومومئ چې تاسو ته یوازې د ت buttۍ فشار کیدلو اجازه ورکړل شوې چې د اوسني ت buttonۍ ښیې ، ښکته ، کی left او ښیې دي. تاسو اجازه نلرئ د لاندینۍ قطار کونج ت pressۍ (* (ستوري) او # (هیش) فشار ورکړئ ، کوم چې لاندې عکس کې خړ رنګ لري.

شمیره کیپډ

بېلګه

1
10

توضیحي: تاسو کولی شئ ټول ګ digitې (0 څخه تر 9 پورې) وکاروئ ، پدې توګه د ځواب لپاره 10 برخه کول.

2
36

توضیحي: په پام کې ونیسئ چې تاسو 0 غوره کوئ ، نو تاسو کولی شئ 0 او 8 د دوهم نمبر په توګه غوره کړئ.

په پام کې ونیسئ چې تاسو 1 غوره کوئ ، نو تاسو کولی شئ 1 ، 2 ، 4 د دوهم نمبر په توګه غوره کړئ. په ورته ډول ، موږ دا د ټولو ګ forو لپاره کوو.

 

د ګرځنده شمیرو کیپیډ ستونزې لپاره لاره

تکراري چلند

د ګرځنده شمیري کیپډ ستونزې لپاره ، لومړی شی چې په ذهن کې راځي د تکراري چلند لاره ده. نو ، موږ کولی شو ستونزه حل کړو په تکرار سره لکه که چیرې موږ په I ، j حالت کې یو او موږ د شمیر لپاره انتخاب شمیره لرو نو بیا موږ پورته خوا ته حرکت کولی شو (i-1، j)، ښکته لوري (i + 1 ، j) ، کی left لوري (i ، j-1) ) ، سمه لار (i ، j + 1) او اوسني موقعیت کې پاتې شئ (i ، j) د n-1 شمیرو سره اوس غوره کړئ. دا طریقه په سمه توګه سمه ده مګر په کافي اندازه موثره نده.

//Base Case
if (N = 1) return 10
else
    return sum of all findNumberOfSequences(i, j, n) where i,j is new position after a valid move from current position

متحرک برنامې

کله چې موږ د n سره برابر د شمیر ترتیب اوږدوالي لپاره د ګرځنده شمیري کیپیډ ستونزه حلولو هڅه کوو. موږ لیدلی شو چې لومړنۍ ستونزه په کوچني فرعي ستونزو پورې اړه لري. ستونزې ته پام وکړئ کله چې موږ د 3 مساوي 2 لپاره حل کوو. بیا به موږ ګورو چې زموږ ستونزه د اوږدوالي له اندازې 2 سره تړاو لري. XNUMX بیا به موږ پورته خوا ته ښکته لوري ته خوا ته او سم لور ته ځو یا به په ځای پاتې شو ورته ځای مګر مګر چې موږ دا دریځ (ډیجیټ) اخیستی او په ځواب کې مو اضافه کړي. ستونزه د n = XNUMX سره کوچنۍ ستونزې ته راټیټه شوې. اوس که موږ وګورو چې موږ له یوې شمیره څخه پیل شوی او اجازه لیکونو کې حرکت کړی دی نو بیا موږ ګورو چې موږ له فرعي ستونزو سره مخ یو نو دا کار موږ ته د کارولو تجربه راکوي. متحرک برنامه.

په عموم کې متحرک برنامه، هغه څه چې موږ یې کوو لومړی د کوچني ستونزو لپاره حل کوو او بیا زموږ د لومړنۍ ستونزې حل کولو لپاره د کوچنیو ستونزو پایلې یوځای کوو نو هغه څه چې به کوي د n برابر 1 لپاره n بیا د 2 مساوي حل کول ، او داسې نور.

کوډ

C ++ کوډ

#include <bits/stdc++.h> 
using namespace std;

int findNumberOfSequences(int n) 
{ 
  char keypad[4][3] = {{'1','2','3'}, 
                       {'4','5','6'}, 
                       {'7','8','9'}, 
                       {'*','0','#'}};
  
  //Base Case
  if(n <= 0) 
    return 0; 
  if(n == 1) 
    return 10; 

  //Directions to move to
  int dir[][2]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};

  //dp[i][j] = number of sequences of length j starting with digit i
  int dp[10][n+1];
  memset(dp,0, sizeof dp);
  
  // fill the numbers starting with digit i and of length 1 
  for(int i=0; i<=9; i++)
    dp[i][1] = 1;

  // Now solve problem for n=2,3,.. using smaller sub-problems
  for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
  { 
    for(int row=0; row<4; row++)
    { 
      for (int col=0; col<3; col++)
      { 
        if (keypad[row][col] != '*' && keypad[row][col] != '#') 
        { 
          //fixing the first digit
          int num = keypad[row][col] - '0';

          //Now select the remaining digit in sequence
          for(int step=0; step<5; step++) 
          { 
            int new_row = row + dir[step][0]; 
            int new_col = col + dir[step][1]; 
            if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
            && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
            { 
              int nextNum = keypad[new_row][new_col] - '0'; 
              dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
            } 
          } 
        } 
      } 
    } 
  } 

  // Add the number of sequences of length starting with digit i(0 to 9)
  int ans = 0; 
  for(int i=0; i<=9; i++) 
    ans += dp[i][n]; 
  return ans; 
} 

int main() 
{ 
  int t;cin>>t;
  while(t--){
    int n;cin>>n;
    cout<<"Number of sequences of length "<<n<<" = "<<findNumberOfSequences(n)<<endl;
  }
} 
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36 
Number of sequences of length 3 = 138 
Number of sequences of length 4 = 532 
Number of sequences of length 5 = 2062

 

جاوا کوډ

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static int findNumberOfSequences(int n) 
    { 
      	char keypad[][] = {{'1','2','3'}, 
    		           {'4','5','6'}, 
    	         	   {'7','8','9'}, 
    			   {'*','0','#'}};
      
      	//Base Case
    	if(n <= 0) 
    		return 0; 
    	if(n == 1) 
    		return 10; 
    
    	//Directions to move to
    	int dir[][]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};
    
    	//dp[i][j] = number of sequences of length j starting with digit i
    	int dp[][] = new int[10][n+1];
        
        for(int i=0;i<10;i++)
            for(int j=0;j<n+1;j++)
                dp[i][j]= 0;
                
    	// fill the numbers starting with digit i and of length 1 
    	for(int i=0; i<=9; i++)
    		dp[i][1] = 1;
    
    	// Now solve problem for n=2,3,.. using smaller sub-problems
    	for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
    	{ 
    		for(int row=0; row<4; row++)
    		{ 
    			for (int col=0; col<3; col++)
    			{ 
    				if (keypad[row][col] != '*' && keypad[row][col] != '#') 
    				{ 
    					//fixing the first digit
    					int num = keypad[row][col] - '0';
    
    					//Now select the remaining digit in sequence
    					for(int step=0; step<5; step++) 
    					{ 
    						int new_row = row + dir[step][0]; 
    						int new_col = col + dir[step][1]; 
    						if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
                                                && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
    						{ 
    							int nextNum = keypad[new_row][new_col] - '0'; 
    							dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
    						} 
    					} 
    				} 
    			} 
    		} 
    	} 
    
      	// Add the number of sequences of length starting with digit i(0 to 9)
    	int ans = 0; 
    	for(int i=0; i<=9; i++) 
    		ans += dp[i][n]; 
    	return ans; 
    } 

    public static void main(String[] args) 
    { 
        
    	Scanner sc = new Scanner(System.in); 
    	int t = sc.nextInt(); 
    	while(t-- > 0){ 
            int n = sc.nextInt();
            int ans = findNumberOfSequences(n);
    	    System.out.println("Number of sequences of length "+n+" = "+ans);
    	}
    } 
}
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36
Number of sequences of length 3 = 138
Number of sequences of length 4 = 532
Number of sequences of length 5 = 2062

د پیچلتیا تحلیل

د وخت پیچلتیا: O (n) د ګرځنده شمیرو کیپیډ ستونزې لپاره

حتی که څه هم موږ ډیری ځړول شوي لوپونه کارولي مګر بیا یې هم موږ دوی په دوامداره وخت کې پرمخ وړلو لپاره په پام کې نیسو ، پدې توګه موږ د بیروني لوپ له امله د خطي وخت پیچلتیا O (n) لرو.

د ځای پیچلتیا: O (n) د ګرځنده شمیرو کیپیډ ستونزې لپاره

له هغه وخته چې موږ د 1 ابعادي DP اندازه اندازه n لرو. موږ د O (n) یو خطي ځای پیچلتیا لرو.