მობილური ციფრული კლავიშის პრობლემა


Რთული ტური Hard
ხშირად ეკითხებიან Amazon MAQ microsoft სპრინკლერი
კომბინაციური დინამიური პროგრამირება Matrix სიმებიანი

პრობლემის განცხადება

მობილური რიცხვითი კლავიატურა პრობლემაში, ჩვენ განვიხილავთ ციფრული კლავიატურა. ჩვენ უნდა ვიპოვოთ მოცემული სიგრძის შესაძლო რიცხვითი თანმიმდევრობის მთელი რიცხვი, რათა მხოლოდ ღილაკების დაჭერის უფლება გქონდეთ მიმდინარე ღილაკის ზემოდან, ქვემოთ, მარცხნივ და მარჯვნივ. თქვენ არ გაქვთ უფლება დააჭიროთ ქვედა მწკრივის კუთხის ღილაკებს (* (ვარსკვლავი) და # (ჰაში)), რომლებიც ქვემოთ მოცემულ სურათზე ნაცრისფერია.

რიცხვითი კლავიატურა

მაგალითი

1
10

განმარტება: შეგიძლიათ გამოიყენოთ ყველა ციფრი (0-დან 9-მდე), ასე რომ, თქვენ შეუტანთ პასუხს 10-ს.

2
36

განმარტება: გაითვალისწინეთ, რომ აირჩევთ 0-ს, შემდეგ შეგიძლიათ აირჩიოთ 0 და 8, როგორც მეორე რიცხვი.

გაითვალისწინეთ, რომ აირჩევთ 1-ს, შემდეგ შეგიძლიათ აირჩიოთ 1, 2, 4 მეორე ნომრად. ანალოგიურად, ჩვენ ამას ვაკეთებთ ყველა ციფრისთვის.

 

მიდგომა მობილური ციფრული კლავიატურა პრობლემის მიმართ

რეკურსიული მიდგომა

მობილური ციფრული კლავიშის პრობლემისთვის პირველი, რაც მახსენდება, არის რეკურსიული მიდგომა. ასე რომ, ჩვენ შეგვიძლია პრობლემის მოგვარება რეკურსიულად ისეთი, რომ თუ ჩვენ ვართ პოზიცია i, j და გვაქვს n ნომრები, რომელთა არჩევაც შეგვიძლია, ჩვენ შეგვიძლია გადავიდეთ ზემოთ მიმართულებით (i-1, j), ქვევით (i + 1, j), მარცხენა მიმართულებით (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. ჩვენ ვხედავთ, რომ საწყისი პრობლემა დამოკიდებულია მცირე ქვე-პრობლემებზე. განვიხილოთ პრობლემა, როდესაც n- ს გადაჭრის ტოლია 3-ის. მაშინ დავინახავთ, რომ ჩვენი პრობლემა დამოკიდებულია სიგრძის ტოლი თანმიმდევრობის რაოდენობაზე 2. ჩვენ შემდეგ გადავდივართ ზემოთ მიმართულებით ქვევით მიმართულებით მარცხენა მიმართულებით და სწორი მიმართულებით ან დავრჩებით იმავე ადგილას, მაგრამ მას შემდეგ, რაც ჩვენ დავიკავეთ ეს პოზიცია (ციფრი) და ვამატეთ პასუხი. პრობლემა შემცირდა უფრო მცირე პრობლემად n = 2. ახლა თუ დავინახავთ, რომ დავიწყეთ ციფრიდან და გადავედით დაშვებული მიმართულებებით, მაშინ ვხედავთ, რომ გვაქვს გადაფარებული ქვეპროგრამები, ამიტომ ეს ინტუიციას გვაძლევს, რომ გამოვიყენოთ. დინამიური პროგრამირება.

საერთოდ, შიგნით დინამიური პროგრამირება, რასაც ჩვენ ვაკეთებთ არის ის, რომ პირველ რიგში გადავჭრათ უფრო მცირე პრობლემები და შემდეგ გავაერთიანოთ უფრო მცირე პრობლემების შედეგები, რომ გადავჭრათ ჩვენი საწყისი პრობლემა, ასე რომ, რას გააკეთებს, როგორც 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).