Say və deyin

Say və deyin burada N sayını verdik və saymanın N-ci müddətini tapıb deməyimiz lazımdır ardıcıllıq. Əvvəlcə saymanın nə olduğunu başa düşməli və ardıcıllığı söyləməliyik. Əvvəlcə ardıcıllığın bəzi şərtlərinə baxın:

1-ci müddət “1” -dir.

2-ci dövr "11" dir.

3-cü dövr "21" dir.

4-cü dövr “1211” dir.

5-ci dövr “111221” dir

6-cı dövr “312211” dir…. və sair.

Giriş Formatı

Yalnız N tam ədədi olan bir sətir.

Çıxış formatı

Nəticəni a sim format. Başqa bir şəkildə deyirik ki, N-ci dövrü əhatə edən yalnız bir sətir çap edin.

Məhdudiyyətlər

• 1 <= N <= 50.

Example Input: 
5

Example Output:
111221

Saymaq və Söyləmək üçün İzahat

Budur a naxış burada n-1-ci müddətin istifadəsi ilə n-ci hissəni tapırıq. N-1-ci dövrü keçib cavabını n-ci müddətə əlavə etməliyik. N-1 dövründə yalnız neçə dəfə davamlı gəldiyini sayırıq. Sonra bu sayını n-ci dönəmdə, sonra n-1-ci dövrdə keçdiyimiz sayda saxlayın. Budur addım-addım tətbiqetmə:

1-ci dövr: Bizim əsas işimiz olan "1".

2-ci dövr: davamlı olaraq n-1-ci dövrdə mövcud olan sayın_sayımları. Burada “1” -in sayı 1-dir. Yəni ikinci müddətimiz “11” dir.

3-cü dövr: n-1-ci dövrdə “1” in sayları 2-dir. Beləliklə, 3-cü dövrümüz “21” -dir.

4-cü dövr: n-2-ci hissədəki “1” nin sayı 1-ə, “1” inin sayı isə 1-ə bərabərdir. Beləliklə, 4-cü dövrümüz “1211” dir.

5-cü dövr: n-1-ci hissədəki “1” in sayları 1, sonra “2” nin sayı 1-dir və son fasiləsiz “1” sayının sayı 2-dir.

Beləliklə, 5-ci dövr “111221” dir.

Saymaq və söyləmək üçün tətbiqetmə

/*C++ Implementation of Count and Say Problem*/ 
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
    int n;
    /*take N as input*/
    cin>>n;
    /*create a vector to store the count and say sequence terms till N.*/
    vector<string> v;
    for(int i=0;i<n;i++)
    {
        /*Base case: 1st term is "1".*/
        if(i==0)
        {
            v.push_back("1");
        }
        else
        {
            /*store the ith term in check string*/
            string check=v[i-1];
            int sz=check.size();
            /*i+1 th term*/
            string ins="";
            /*calculation to find the i+1th term*/
            for(int j=0;j<sz;j++)
            {
                /*freq store the freq of the number which we traverse in the ith term*/
                int freq=1;
                /*number which we traverse in the ith term*/
                char ch=check[j];
                /*move to the next value in ith term and count the frequency of number(ch)*/
                while(j+1<sz&&check[j]==check[j+1])
                {
                    freq++;
                    j++;
                }
                /*convert frequency of ch into string and add to i+1th term*/
                ins+=to_string(freq);
                /*Now, add the number(ch) to i+1th term*/
                ins+=ch;
            }
            /*push the i+1th term into the vector*/
            v.push_back(ins);
        }
    }
    /*Print the Nth term of count and say problem*/
    cout<<v[n-1]<<endl;
    return 0; 
}

15

311311222113111231131112132112311321322112111312211312111322212311322113212221

Zamanın mürəkkəbliyi

Burada zamanın mürəkkəbliyi düzəldilə bilməz çünki N> 30-u götürsək, ən pis ssenari üçün vaxtın mürəkkəbliyi üçün çıxış sətrini saxlamaq heç mümkün deyil O (10 ^ 6).

References