วิธีพิมพ์จำนวนสูงสุดของ A โดยใช้ปุ่มสี่ปุ่มที่ให้มา

มาพิจารณากัน เราจะพยายามเขียนตัวอักษร 'A' โดยใช้แป้นพิมพ์ เป้าหมายของเราคือใช้เพียงสี่ปุ่มและพยายามเขียน 'A' สูงสุดลงในช่องข้อความ ปุ่มคือ 'A', 'C', 'V' และ 'Ctrl'

ในการเขียนจำนวนสูงสุดของ A เราจะใช้ Ctrl + A เพื่อเลือกทั้งหมด, Ctrl + C เพื่อคัดลอก และใช้ Ctrl + V เพื่อวาง

อินพุตและเอาต์พุต

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

อัลกอริทึม

keyNumbers(keyStrokes)

ป้อนข้อมูล: จำนวนการกดแป้น

ผลลัพธ์: จำนวนตัวอักษรสูงสุดที่ใช้การกดแป้นเหล่านี้

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

ตัวอย่าง

#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;
}

ผลลัพธ์

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