Verilən dörd düymədən istifadə edərək maksimum A sayını necə yazdırmaq olar

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook google PayPal Paytm
Dinamik proqramlaşdırmaBaxılıb 24

Problem bəyanat

Verilən dörd düyməni istifadə edərək A-nın maksimum sayını necə yazdırmaq olar, bu problem hansı düyməni basacağınızı seçmək seçiminizin olduğunu bildirir. Düymələr aşağıdakı vəzifələri yerinə yetirir:

  1. Key1 - Ekranda 'A' yazdırır
  2. Key2 - Bütün ekranı seçin.
  3. Açar3 - Seçilmiş məzmunu kopyalayın.
  4. Key4 - Kopyalanan məzmunu çap edin.

Düymələri yalnız N dəfə basa bilərsiniz, yazdırıla bilən maksimum A sayını tapa bilərsiniz. Yapabileceğiniz hər hansı bir kombinasiyadan istifadə edərək, yazdırıla bilən maksimum A sayını tapın.

misal

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

İzahat: Başqa birləşmələr daha yaxşı bir nəticə tapa bilməyəcəyi üçün. Düymə basmalarının başqa hər hansı bir kombinasiyasından istifadə edərək, daha çox A düyməsini çap edə bilməyəcəksiniz. Başqa hər hansı bir kombinasiyanı sınaqdan keçirə bilərik. Deyək ki, tək bir A. çap edirik, çünki 'A' yazmırıqsa 'A' seçib sonra çap edə bilmərik. Beləliklə, tək bir 'A' yazdırmaq daha yaxşıdır. Bundan sonra, seçim, çap və kopyalama üç kombinasiyadan birini həyata keçirə bilərik. Ancaq bu kombinasiyalardan heç biri daha yaxşı nəticə verə bilməyəcək.

Verilən dörd düymədən istifadə edərək maksimum A sayını necə yazdırmaq olarPin

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

İzahat: Aşağıdakı 6 düyməni istifadə edəcəyik, Key1 ('A' yazdırır), Key1, Key1, Key2 (Bütün ekran məzmununu seçir), Key3 (Seçilmiş məzmunu kopyalayın), Key4 (Kopyalanan məzmunu yazdırırıq). Eyni A düyməsini çap edə biləcək digər düymələr də ola bilər.

Yanaşma

Verilən dörd düymədən istifadə edərək A-nın maksimum sayının necə yazdırılacağını tapmaq, düymə basma sayından = N-3-dən 1-ə başlayaraq A-nın maksimum sayını tapmağa çalışsaq həll edilə bilər.
İth mövqeyinin Key2, Key3 və sonra Key4 ardıcıllığına basdığımız nöqtə olduğunu düşünəcəyik. İndi N-3-dən 1-ə dönsək. Belə məqamlar çox ola bilər.

Həmişə olduğu kimi, problem istifadə etdiyi üçün əsas bir işə ehtiyacımız var dinamik proqramlaşdırma. Burada vəziyyət, əgər n <= 6 olarsa, ədədi sadəcə çap edirik. Niyə buna zəng edirik dinamik proqramlaşdırma kodda heç bir DP dizisi istifadə etməməyimizə baxmayaraq? Çünki problem iki şərti təmin edir: üst-üstə düşən alt problemlər və optimal alt quruluş. Hər problem daha da bölünə bilər və daha sonra bölünür.

Kodu

Çap edilə bilən maksimum sayını tapmaq üçün C ++ kodu

#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

Çap edilə bilən maksimum sayını tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (N)

Sadəcə bir neçə düyməyə basaraq bir döngə apardıq. Alqoritm O (N) xətti zaman mürəkkəbliyinə malikdir.

Kosmik Mürəkkəblik: O (1)

Yalnız bəzi tam ədədləri və elementləri saxladığımız üçün. Daimi kosmik mürəkkəbliyimiz var.

Translate »