Cách in số chữ A tối đa bằng cách sử dụng bốn khóa đã cho

Chúng ta hãy xem xét, chúng ta sẽ cố gắng viết chữ ‘A’, bằng cách sử dụng bàn phím. Mục tiêu của chúng tôi là chỉ sử dụng bốn phím và cố gắng viết tối đa chữ ‘A’ trên trường văn bản. Các phím là ‘A’, ‘C’, ‘V’ và ‘Ctrl’.

Để viết số A tối đa, chúng ta sẽ sử dụng Ctrl + A để chọn Tất cả, Ctrl + C để sao chép và Ctrl + V để dán.

Đầu vào và Đầu ra

Input:
Number of keystrokes, say 7
Output:
Maximum Number of A's with 7 keystrokes is: 9
Press A three times. Then Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V

Thuật toán

keyNumbers(keyStrokes)

Đầu vào: số lần nhấn phím.

Đầu ra: Số lượng chữ cái tối đa khi sử dụng các tổ hợp phím này.

Begin
   if keyStrokes <= 6, then
      return keyStrokes

   for n := 1 to 6, do
      result[n-1] := n
   done

   for n := 7 to keyStrokes, do
      result[n-1] := 0
      for breakpoint := n-3 down to 1, do
         curr := (n – breakpoint - 1)*result[breakpoint - 1]
         if curr > result[n-1], then
            result[n - 1] := curr
      done
   done
   result[keyStrokes - 1]
End

Ví dụ

#include<iostream>
using namespace std;

int keyNumbers(int keystrokes) {    //find number of 'A's using 4 types of keys
   if (keystrokes <= 6)    //if keystrokes are less than 7
      return keystrokes;

   int result[keystrokes];    //store intermediate results
   for (int n=1; n<=6; n++)    //upto 6 keystrokes, we need that number of keystrokes for max
      result[n-1] = n;

   for (int n=7; n<=keystrokes; n++) {    //for 7th to higher
      result[n-1] = 0;    //initially store 0 as result
      for (int breakPoint=n-3; breakPoint>=1; breakPoint--) {    //find breakpoint to select, copy and paste
         int curr = (n-breakPoint-1)*result[breakPoint-1];
         if (curr > result[n-1])
            result[n-1] = curr;
      }
   }
   return result[keystrokes-1];
}

int main() {
   int keystrokes;
   cout << "Enter Number of keystrokes: "; cin >> keystrokes;
   cout << "Maximum Number of A's with "<<keystrokes << " keystrokes is: "<< keyNumbers(keystrokes)<<endl;
}

Đầu ra

Enter Number of keystrokes: 7
Maximum Number of A's with 7 keystrokes is: 9