Question

Se da operatia − : {1, 2} → {1, 2} astfel ıncat- 1 = 2 si -2 = 1. Operatia se extinde asupra oricarei secvente formate cu cifre de 1 si 2 de exemplu
–(1211212121) = 2122121212. Se considera sirul infinit s format cu cifre de 1 si 2, generat incremental prin extindere dupa urmatoarea regula de concatenare: s1 = 1221, s2 = 1221211221121221, . . . , sk+1 = sk(-sk)(-sk)sk, . . ., pentru orice numar natural nenul k. Fie n un numar natural nenul, n < 1000000 ~ 4 la 10.
(a) Sa se scrie un program care citeste n si afiseaza primele n cifre ale sirului s. Exemplu: Pentru n = 18 programul va afisa 122121122112122121.
(b) Sa se scrie un program care citeste n si afiseaza a n-a cifra a sirului s, astfel ıncat numarul de pasi ai programului sa fie proportional cu log2 n (complexitate timp logaritmica ın functie de n). Exemplu: Pentru n = 11 programul va afisa 1, iar pentru n = 20 programul va afisa 2


Cum rezolv aceasta problema in C++ ?

Answer 1

De fiecare data cand cere cautare proportionala cu log2(n) aproape intotdeauna implica un proces de reprezentare a datelor in binar. Daca vrei sa cauti un anumit numar in grupul de 16 valoride exemplu, in zecimal ar trebui sa verifici fiecare numar in parte adica 0,1,2,3...15, deci algoritmul ar fi proportional cu n.
In schimb, daca am reprezenta in binar, ar trebui sa cauti in 0000,0001,0010,...1111 trebuie sa verifici decat 4 cifre binare, de 0 sau 1.
$\log_{2}{16}=\log_{2}{2^{4}}=4$
In cazul nostru, observi ca schimbarile de afisari se fac din 4 in 4 grupuri, deci ti-ar veni ideea ca 2 cate 2 biti din sir ar conta.
Pentru primul grup 1221 daca faci reprezentarea binara de la 0 la 3(considerand ca e un vector care porneste de la 0) avem
00 1
01 2
10 2
11 1
Deci daca ultimele 2 cifre binare sunt egale, atunci e 1, altfel e 2
Apoi urmatoarea runda stim ca sunt negate, asa ca avem
0100 2
0101 1
0110 1
0111 2
Deci aici observam ca se respecta regula: avand pe primele 2 pozitii binare combinatia 01, 2 pozitii binare, acestea vor nega toate valorile caracterului precedent, adica 1 sau 2 in functie de combinatia precedenta
01 00 de la dreapta la stanga prima combinatie este '1' o negam,obtinem '2'
01 01  de la dreapta la stanga prima combinatie este '2' o negam,obtinem '1'
si asa mai departe
in schimb la in cazul lui 
1100 (care este termenul 13 nu uita se scade 1 din termen pentru a reprezenta combinatia binara) e inceputul celui de-al patrulea grup de cate 4, care nu mai este negat, deci va incepe cu '1'. Daca citim de la dreapta la stanga, avem mai intai '1' si apoi pentru ca avem combinatie de 2 cifre binare tot egale 11, caracterul ramane acelasi '1'
Cam asta ar fi logica cautare mai rapida.
Ai programul mai jos
 #include <iostream>
#include <string.h>
using namespace std;


char neg_caracter(char c){
if(c=='1'){
return '2';
}
else{
return '1';
}
}
string decimal_binar(int n){
string s="";
while(n>0){
if(n%2==0){
s="0"+s;
}
else{
s="1"+s;
}
n=n/2;
}
if(s.length()%2==1){
s="0"+s;
}
return s;
}
char cautare_binara(int n){
string s=decimal_binar(n-1);
char c;
int i;
if(s[s.length()-1]==s[s.length()-2]){
c='1';
}
else{
c='2';
}
if(s.length()<3){
return c;
}
for(i=s.length()-3;i>=0;i=i-2){
if(s[i]!=s[i-1]){
c=neg_caracter(c);
}
}
return c;
}

int main(){
int n;
cin>>n;
cout<<cautare_binara(n);
return 0;
}

Mai jos ai si codul de generare al sirului:
#include <iostream>
#include <fstream>
#include <string.h>
#include <cmath>
using namespace std;

//constanta care arata sirul de baza s1
const string baza="1221";
//functie pentru negarea sirului din 1->2 si 2->1
string neaga_sir(string s){
int c;
for(c=0;c<s.length();c++){
if(s[c]=='1'){
s[c]='2';
}
else if(s[c]=='2'){
s[c]='1';
}
}
return s;
}
//functie pentru obtinerea celei mai mari puteri de 4
//mai mica decat nr actual. Ex pentru 18, 4^2=16<18, 
//programul returneaza 2
int obtine_putere_4(int n){
int exp_4=0;
while(n>=4){
exp_4++;
n=n/4;
}
return exp_4;
}
//genereaza termenul complet anterior: s+negat(s)+negat(s)+s
string generare_termen(int exp_4){
string s=baza;
while(exp_4>1){
s=s+neaga_sir(s)+neaga_sir(s)+s;
exp_4--;
}
return s;
}
//functie care genereaza sirul

string generare_sir(int n){
int exp,i,grup;
string s,s_prev;
//daca mai mic decat 4, este chiar din sirul de baza
if(n<4){
return baza.substr(0,n);
}
else{
//obtinem exponent pentru putere mai mica decat n
    exp=obtine_putere_4(n);
    //determinam termen anterior
s_prev=generare_termen(exp);
//aflam cate caractere vor fi din termenul actual
n=n-pow(4,exp);
//daca nu sunt caractere, inseamna ca este exact termenul anterior
if(n==0){
return s_prev;
}
//aflam cate grupuri de s_prev trebuie sa afisam
grup=n/(int)pow(4,exp);
//afla cate caractere din s_prev trebuie afisate
n=n%(int)pow(4,exp);
i=0;
s=s_prev;
//cat timp exista grupuri, ele sunt negate
while(i<grup){
s=s+neaga_sir(s_prev);
i++;
}
//daca sunt 3 grupuri(0 1 si 2) atunci extragem din s_prev pozitiv
if(grup==2){
s=s+s_prev.substr(0,n);
}
//daca sunt mai putine grupuri extragem din s_prev negat
else{
s=s+neaga_sir(s_prev).substr(0,n);
}
}
return s;

}
int main(){
int n;
cin>>n;
cout<<generare_sir(n);
//ofstream fof("functie.out");
//fof<<generare_sir(n);

return 0;
}