Question

Se generează un şir de numere naturale ai cărui primi termeni sunt, în această ordine:
1, 20, 21, 300, 301, 320, 321, 4000, 4001, 4020, 4021, 4300, 4301, 4320, 4321, 50000,...
Dându-se numerele naturale k, n și x, să se determine: a) numărul de termeni ai şirului care au prima cifră (cea mai semnificativă) egală cu k; b) cel de-al n-lea termen al şirului din enunţ; c) cel mai mare termen al şirului, mai mic sau egal decât x.

Answer 1

a)

Se observa ca pe fiecare pozitie, cifra nu poate lua decat doua valori: 0, sau un anumit numar k.
De exemplu, ultima cifra nu poate fi decat 0 sau 1; a doua cifra poate fi 0 sau 2, si tot asa.
Regula sirului este foarte asemanatoare cu adaugarea cu cate o unitate numerelor din baza 2. Deoarece fiecare cifra nu poate lua decat 2 valori, atunci exista o corespondenta bijectiva(unu la unu) intre aceste numere si cele in baza 2, inlocuind toate cifrele diferite de 0 cu 1:

    1  <->      1
  20  <->    10
  21  <->    11
300  <->  100
301  <->  101
320  <->  110
321  <->  111
...

Se observa ca in sirul initial, a n-a cifra a unui numar(numarand de la ultima) va fi fie 0, fie n. Astfel, pentru ca prima cifra a unui astfel de numar sa fie k, pozitia acesteia trebuie sa fie tot k. Asta inseamna ca numarul sa aiba k cifre.

Asadar, problema determinarii numarului de termeni care au prima cifra k s-a transformat in determinarea numarului de termeni care au k cifre. Analizand sirul de numere in baza 2, vom avea urmatorul numar:

[tex]\underbrace{1***...*}_{\text{k cifre}}\\\\ 1\underbrace{***...*}_{\text{k-1 cifre}}[/tex]

Stiind ca stelutele nu pot lua decat valorile 0 si 1(2 posibilitati), numarul total de posibilitati, conform regulei produsului, va fi:
$\underbrace{2\cdot2\cdot2\cdot...\cdot2}_{\text{k-1 termeni}}=2^{k-1}$

b)
Toate numerele in baza doi au o reprezentare in baza 10:

   1  <->      1  <->  1
  20  <->    10  <->  2
  21  <->    11  <->  3
300  <->  100  <->  4
301  <->  101  <->  5
320  <->  110  <->  6
321  <->  111  <->  7  (in baza 10)
...

Se observa ca pozitia numerelor coincide cu numerele din baza 10. Noua ni se da pozitia, si vom face trecerea lui n in baza 2.

c)
Plecand de la ideea ca sirul nu poate avea numere cu mai mult de 9 cifre, generarea tuturor nu ar fi costisitoare(sunt 2^10). Asa, ca generam toate numerele pana cand sunt mai mari decat x.


Codul:

#include <iostream>
using namespace std;

int main()
{
    int n, k, x;
 
    cin >> k >> n >> x;
  
    //a)
    int p = 1;  // p = 2^(k-1)
    while (k > 1)
    {
        p *= 2;
        k--;
    }   
    cout << p << '\n';

   //b)
   int i = 1, p = 1, b2 = 0;  /*b2 = numarul n in baza 2; nu e nevoie neaparat de el; p va lua pe rand puterile lui 2; va fi folosit pentru a-l construi pe b2
    i = pozitia in numar, incepand de la ultima cifra*/
   while (n)
   {
      //nu e nevoie de aceste doua randuri; aici se formeaza numarul in baza 2
      b2 += (n % 2) * p;
      p *= 2;

      /*Daca in baza 2, cifra este 1, atunci in sirul initial cifra va fi i, unde i este pozitia in numar; Daca este 0, atunci si in numarul initial este 0*/
      if (n % 2 == 0) cout << i << ' ';
      else                 cout << 0;
      i++;
      n /= 2;
   }

   //c)
   /*Vom face acelasi lucru ca la b, numai ca in loc sa afisam cifrele, le vom pune intr-o variabila*/
 
   n = 1;
   int last = 0, nr = 0;  //nr va lua pe rand valoarea fiecarui termen din sir
   while (nr <= x)
   {
      int aux = n, p = 1; //p = puterile lui 10
      i = 1;
      nr = 0;
      //generarea termenului de pe pozitia n/aux
      while (aux)
      {
           if (aux % 2 == 1)
               nr = nr + p * i;
 
           p *= 10;
           i++;
           aux /= 2;
      }
      last = nr;
      n++;
   }
   cout << last;

}