Како се штампа максималан број А користећи дата четири тастера


Ниво тешкоће Средњи
Често питани у амазонка фацебоок гоогле ПаиПал Паитм
Динамичко програмирање

Изјава о проблему

Како се штампа максималан број А користећи дата четири тастера, овај проблем наводи да имате могућност да изаберете који тастер да притиснете. Тастери извршавају следеће задатке:

  1. Тастер 1 - Штампа 'А' на екрану
  2. Тастер 2 - Изаберите цео екран.
  3. Тастер 3 - Копирајте изабрани садржај.
  4. Тастер 4 - Одштампајте копирани садржај.

Можете притиснути тастере само Н пута, сазнати максималан број А који се могу одштампати. Користећи било коју комбинацију коју можете да направите, пронађите максималан број А који се могу одштампати.

Пример

Number of keys that can be pressed = 2
Number of A's that can be printed = 2

Објашњење: Будући да било која друга комбинација неће моћи да нађе бољи резултат. Користећи било коју другу комбинацију притиска тастера, нећете моћи да одштампате већи број А. Можемо пробати било коју другу комбинацију. Рецимо да одштампамо један А. Јер ако не одштампамо „А“, не можемо да изаберемо „А“, а затим да га одштампамо. Дакле, боље је одштампати један 'А'. После тога можемо извршити било коју од три комбинације, одабир, штампање и копирање. Али било која од ових комбинација неће моћи да пружи боље резултате.

Како се штампа максималан број А користећи дата четири тастера

Number of keys that can be pressed = 6
Number of A's that can be printed = 6

Објашњење: Користићемо следећих 6 притиска тастера, Кеи1 (исписује 'А'), Кеи1, Кеи1, Кеи2 (Бира садржај целог екрана), Кеи3 (Копирање изабраног садржаја), Кеи4 (Штампа копирани садржај). Могу постојати и други притисци на тастере који могу исписати исти број А.

Приступ

Проналажење начина штампања максималног броја А користећи дата четири тастера, може се решити ако кренемо од броја притиска тастера = Н-3 до 1 и покушамо да сазнамо максималан број А.
Сматраћемо да је и-та позиција тачка одакле притиснемо тастере2, тастер3, а затим секвенцу тастера4. Ако се петљамо са Н-3 на 1. Тачака може бити много.

Као и увек, потребан нам је основни случај јер проблем користи динамичко програмирање. Овде је случај ако је н <= 6 једноставно исписујемо број. Зашто ово зовемо динамичко програмирање иако у коду не користимо ниједан ДП низ? Јер проблем задовољава два услова: подпроблеми који се преклапају и оптимална подструктура. Сваки проблем се може даље поделити, а затим се даље дели.

код

Ц ++ код за проналажење максималног броја Ас који се може одштампати

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

int maximumNumberOfAsPrinted(int numberOfKeyPresses)
{
  if(numberOfKeyPresses <= 6)
    return numberOfKeyPresses;

  int maxNumberOfAs = 0;
  for(int i = numberOfKeyPresses-3; i>=1;i--) {
    // here we consider that after ith keystroke we are performing only selection, copy once and then paste
    // thus starting from numberOfKeyPresses-3
    int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    if (numberOfAs > maxNumberOfAs)
      maxNumberOfAs = numberOfAs;
  }
  return maxNumberOfAs;
}

int main()
{
  int numberOfKeyPresses;cin>>numberOfKeyPresses;
  int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
  cout<<numberOfAsPrinted;
}
18
192

Јава код за проналажење максималног броја Ас који се може одштампати

import java.util.*;

class Main{
    static int maximumNumberOfAsPrinted(int numberOfKeyPresses)
    {
    	if(numberOfKeyPresses <= 6)
    		return numberOfKeyPresses;
    
    	int maxNumberOfAs = 0;
    	for(int i = numberOfKeyPresses-3; i>=1;i--) {
    		// here we consider that after ith keystroke we are performing only selection, copy once and then paste
    		// thus starting from numberOfKeyPresses-3
    		int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    		if (numberOfAs > maxNumberOfAs)
    			maxNumberOfAs = numberOfAs;
    	}
    	return maxNumberOfAs;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    	int numberOfKeyPresses = sc.nextInt();
    	int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
    	System.out.println(numberOfAsPrinted);
    }
}
18
192

Анализа сложености

Сложеност времена: НА)

Будући да смо једноставно прешли преко петље на бројне притиске тастера. Алгоритам има линеарну временску сложеност О (Н).

Сложеност простора: О (1)

Пошто чувамо само неке одређене целобројне бројеве и елементе. Имамо сталну сложеност простора.