Գոլոմբի հաջորդականություն


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Կադենս Հնդկաստան Իսկապես Times ինտերնետ Yatra
Դինամիկ ծրագրավորում Հերթականություն

Խնդիրի հայտարարություն

«Գոլոմբի հաջորդականություն» խնդրում նշվում է, որ ձեզ ներդրում են տրվում ամբողջ թիվ n և դուք պետք է գտնեք Golomb հաջորդականության բոլոր տարրերը մինչև n-րդ տարրը:

Օրինակ

n = 8
1 2 2 3 3 4 4 4

բացատրություն
Գոլոմբի հաջորդականության առաջին 8 տերմինները հայտնաբերվում և տպվում են: Քանի որ ելքը նշում է Գոլոմբի հաջորդականության առաջին 8 տարրերը, ելքը ճիշտ է:

Մոտեցում

Մաթեմատիկայում տրված հաջորդականությունը կոչվում է նաև Սիլվերմանի հաջորդականություն: Հաջորդականությունը կոչվում է Սողոմոն Վ. Գոլոմբի անունով: Դա չի նվազում ամբողջ թվով հաջորդականությամբ, երբ a (n) - ը այն դեպքերի քանակն է, երբ n տեղի է ունենում հաջորդականություն: Գոլոմբի հաջորդականության առաջին տարրը 1. Օրինակ ՝ a1 = 1-ը ասում է, որ 1-ը հաջորդականության մեջ լինում է միայն մեկ անգամ, ուստի a2- ն էլ չի կարող լինել 1, բայց կարող է լինել և, հետեւաբար, պետք է լինի 2:

Հաջորդականության առաջին մի քանի տերմիններն են ՝ 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, XNUMX:

Մենք գիտենք Գոլոմբի հաջորդականության տարրերը գեներացնելու կրկնության հարաբերությունը: Ռեկուրսիվ բանաձեւն է

Գոլոմբի հաջորդականություն
Օգտագործելով ռեկուրսիվ բանաձևը ՝ մենք կլուծենք խնդիրը: Մեկ միջոց է խնդիրը լուծել ռեկուրսիայի միջոցով: Բայց դա մեզ վրա կարժենա էքսպոնենտալ ժամանակի բարդություն, քանի որ մենք կրկին ու կրկին հաշվարկելու ենք նույն արժեքները: Քանի որ, ինչպես տեսնում ենք կրկնության հարաբերությունից, հաջորդականության n-րդ տարրը կախված է նախկինում հաշվարկված պայմաններից: Այսպիսով, մենք կօգտագործենք Դինամիկ mingրագրավորում `խնդիրը լուծելու համար, քանի որ այն օգտագործելով, մենք ստիպված չենք լինի այլ արժեքներ վերահաշվարկել:

Կոդ

Golomb Sequence- ի C ++ կոդը

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

int main(){
  // number of elements of Golomb sequence which are required
  int n;cin>>n;

  cout<<1<<" ";
  int dp[n+1];
  dp[1] = 1;
  for(int i=2;i<=n;i++){
    dp[i] = 1 + dp[i-dp[dp[i-1]]];
    cout<<dp[i]<<" ";
  }
}
10
1 2 2 3 3 4 4 4 5 5

Golomb Sequence- ի Java կոդ

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements of Golomb sequence which are required
    int n = sc.nextInt();

    System.out.print("1 ");
    int dp[] = new int[n+1];
    dp[1] = 1;
    for(int i=2;i<=n;i++){
      dp[i] = 1 + dp[i-dp[dp[i-1]]];
      System.out.print(dp[i]+" ");
    }
  }
}
10
1 2 2 3 3 4 4 4 5 5

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N), քանի որ n- ի տարրը կախված է մեկ նախապես հաշվարկված տարրից, որը յուրաքանչյուր տարրի համար այս գործողությունը դարձնում է O (1) ժամանակային բարդ: Քանի որ կան n տարրեր, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

O (N), քանի որ մենք n տարրեր ենք պահում, տարածության բարդությունը նույնպես գծային է: