Πρόβλημα αριθμητικού πληκτρολογίου για κινητά


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις αμαζόνα MAQ Microsoft Sprinklr
Συνδυαστικό Δυναμικός προγραμματισμός Μήτρα κορδόνι

Δήλωση προβλήματος

Στο πρόβλημα αριθμητικού πληκτρολογίου για κινητά, θεωρούμε ένα αριθμητικό πληκτρολόγιο. Πρέπει να βρούμε όλο τον αριθμό των πιθανών αριθμητικών ακολουθιών δεδομένου μήκους έτσι ώστε να επιτρέπεται μόνο να πατάτε κουμπιά που είναι πάνω, κάτω, αριστερά και δεξιά του τρέχοντος κουμπιού. Δεν επιτρέπεται να πατάτε κουμπιά γωνίας κάτω γραμμής (* (αστέρι) και # (κατακερματισμός)), τα οποία επισημαίνονται γκρι στην παρακάτω εικόνα.

αριθμητικό πληκτρολόγιο

Παράδειγμα

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

 

Κωδικός Java

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) για πρόβλημα αριθμητικού πληκτρολογίου για κινητά

Δεδομένου ότι έχουμε έναν 1-διαστατικό πίνακα DP μεγέθους n. Έχουμε μια γραμμική πολυπλοκότητα χώρου O (n).