Mersi mult xor. Nu mi se parea prea precis exemplul lor ca sa-mi dau seama de regula. Acum am inteles.
Ok.. as putea sa incerc o rezolvare.
Dupa cum a zis si xor, numarul de cifre creste dupa regula 4^k
Daca facem o dezvoltare pana la k=3 avem:
s1=1221;
s2=1221 2112 2112 1221
s3=
1221 2112 2112 1221
2112 1221 1221 2112
2112 1221 1221 2112
1221 2112 2112 1221
Se observa faptul ca atat 1221 cat si 2112 sunt palindromuri.
Se observa de asemenea ca oricare ar fi sk, se genereaza palindromuri perfecte. Indiferent cum l-ai citi, de la dreapta la stanga sau de la stanga la dreapta tot la aceeasi scriere ajungi.
Cel mai important lucru este ca se observa o relatie intre cifrele din s(k-1) si elementele generate de sk.
Adica:
Daca
il definim pe 1 ca fiind o stare corespunzatoare pentru 1221
si daca
il definim pe 2 ca fiind o stare corespunzatoare pentru 2112
Din s1 putem observa ca 1 2 2 1 genereaza atomii 1=1221; 2=2112 ;2=2112 si 1=1221 Adica il genereaza practic pe s2.
La fel se intampla si pentru s3 citindu-l pe s2 si pentru oricare sk citindu-l pe sk-1.
De aceea putem sa ne folosim de starile date din atomii anteriori pentru a-i genera pe urmatorii.
Daca citim stare cu stare(cifra cu cifra) putem sa generam pentru fiecare cifra 1 un 1221 si pentru fiecare cifra 2 un 2112. Iar problema merge recursiv pana la oricare sk.
Asa ca fiecare cifra dintr-un sk am denumit-o "stare" si fiecare string de 1221 sau 2112 am denumit-o "atom generat de acea stare".
Daca e vorba despre admitere, am incercat sa fac o implementare pe vectori fara sa apelez la pointeri (Desi as fi folosit mai degraba string-uri pentru ca 1221 si 2112 nu au nicio valoare numerica. Nu se fac niciun fel de operatii cu ele).
Codul ar fi:
Cod: Selectaţi tot
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int putere_4(int k){ //calculeaza 4^k
int result=1;
while(k>0){
result=result*4;
k--;
}
return result;
}
int log_4(int n){ //calculeaza log_4(n) si returneaza k
int k=0;
int aux=n;
while(n>0){
k++;
n=n/4;
}
if(putere_4(k-1) == aux)
k--;
return k;
}
short returnare_atom(char stare){ //functie care returneaza atomii in functie de starile 1 si 2
if(stare==1)
return 1221;
else if (stare==2)
return 2112;
else
return -1;
}
int citire_scriere(char aux[], short a[], int nr_aux){ //functie care citeste din aux starile si scrie atomii in a
int i;
for(i=0; i<nr_aux; i++){
a[i]=returnare_atom(aux[i]);
}
return i;
}
int cop_aux(char aux[],short a[], int nr_a){ // functie care copiaza starile atomilor lui a in aux
int nr_aux=0;
for(int i=0; i<nr_a; i++){ //parcurgem vectorul a
int x=0;//contor din 4 in 4
int ax; //variabila auxiliara care retine atomul ce trebuie citit
ax=a[i]; //copiem atomul din a[i] in ax
while(x<4){ //parcurgem starile fiecarui atom
aux[nr_aux]=ax%10; // scriem in aux fiecare stare din atom
ax=ax/10; //trecem la starea urmatoare
x++;
nr_aux++; //mai adaugam o stare
}
}
return nr_aux; //returnam ca si valoare marimea lui aux ca sa stim in continuare pana unde mergem
}
void show_only_n(short a[], int cat, int rest){
int i;
for(i=0; i<cat; i++){//mergem doar pana la primele n/4 elemente
printf("%d", a[i]);//le afisam
}
//trecem la elementul(atomul) urmator
int ax=a[i]; //variabila auxiliara care retine urmatorul atom din a[i]
//citim din el doar restul de elemente
i=0;
while(i<rest){
printf("%d", ax%10);
ax=ax/10;
i++;
}
}
int main(){
printf("introduceti n = ");
int n;
int i; //contor
scanf("%d", &n); //citire n
int k=log_4(n); //calculam k pentru sk necesar
short a[nr_at/4]; //alocam memoria pentru vectorul ce il va contine pe sk
char aux[nr_at/4]; //alocam memoria pentru vectorul auxiliar
int nr_aux=1; //numarul de elemente din aux
int nr_a; //numarul de elemente din a
aux[0]=1; //initializam vectorul auxiliar cu starea 1
for(i=0; i<k; i++){//construim vectorul in memorie
nr_a=citire_scriere(aux,a,nr_aux); //citim starile din aux si le scriem in a ca atomi in a
if(i<k-1) //ca sa nu mai umplem aux si ultima oara verificam copiem in aux doar pana la sk-1
nr_aux=cop_aux(aux,a,nr_a); //copiem starile din a, atom cu atom, si le scriem in aux
}
//ca sa parcurgem doar primele n elemente din a afisam primii atomi din cat si urmatoarele stari din rest
int cat=n/4; //catul
int rest=n%4; //restul
show_only_n(a,cat,rest);
getch();
return 0;
}
Codul merge dar poate fi optimizat ca memorie sau poate fi gasita o cu totul alta abordare pentru problema.
Am folosit un vector auxiliar denumit aux in care retinem starile(vector de char-uri pentru ca sunt mai mici ca dimensiune iar noi nu avem nevoie decat de numerele 1 si 2. de asemenea, mult mai bine ar fi sa folosim in loc de char-uri, tipuri booleane din <stdbool.h> iar starile vor fi scrise pe un singur bit (1=0; 2=1), astfel s-ar folosi de 8 ori mai putina memorie pentru scrierea lui aux. Sau folosire de operatii pe biti<de exemplu 0110 se vede ca este xor-ul lui 1111 cu 1001 si invers).
In vectorul a copiem atomii 1221 sau 2112 in functie de starea corespondenta vectorului aux. (vector de short pentru ca sunt numere prea mari pentru char).
Dupa ce am creat in memorie tot vectorul a, am parcurs din el doar elementele care ma intereseaza(pana la n).
O optimizare foarte buna ar fi sa nu se mai creeze chiar tot vectorul a ci doar elementele care ne intereseaza(pana la n, s-ar economisi mai multa memorie).
Nu m-am folosit de <math.h>.
Cred ca cel mai lejer de lucrat ar fi fost de fapt cu o abordare pe stiva(din moment ce lucram doar cu palindromuri.
De asemenea as fi curios daca cineva ar veni cu o implementare pe arbore. ar fi vorba de un arbore cu adancime k si latime 4^k.
Pentru punctul b....
Pare destul de clar ca cere ca acea complexitate (log2) sa fie pentru programul care genereaza sirul si nu pentru cautarea n-ului in sirul generat.
O abordare care sa aiba complexitate binar logaritmica ar fi un algoritm de tip cautare binara.
Ceva de genul:
Daca se cere sa zicem al 18-lea element, se incepe de la s1 care este 1221 si se genereaza sirul urmator doar pentru jumatatea din partea dreapta a lui 1221 adica pentru 21. apoi din sirul rezultat prin generarea atomilor 2112 1221. se imparte iarasi la 2 si se cauta doar in atomul 2112, pe care il impartim iarasi la 2 apoi iarasi la 2 si generam ultimul atom 2112 din care il alegem pe 1 ca fiind al 18-lea numar. (Cred ca ar fi buna o implementare cu arbore dar merge si cu vectori).
Ar fi o interesant sa vad o implementare pentru punctul b
