Se da operatia â : {1, 2} â {1, 2} astfel ıncat 1(barat) = 2 si 2(barat) = 1. Operatia se extinde
asupra oricarei secvente formate cu cifre de 1 si 2, de exemplu 1211212121(barat) = 2122121212. Se considera sirul
inďŹnit s format cu cifre de 1 ¸si 2, generat incremental prin extindere dupa urmatoarea regula de concatenare:
pentru orice numar natural nenul k.
Fie n un numar natural nenul, n < 1000000.
(a) Sa se scrie un program care citeste n ¸si aďŹseaza primele n cifre ale sirului s.
Exemplu: Pentru n = 18 programul va aďŹsa 122121122112122121.
(b) Sa se scrie un program care citeste n si aďŹseaza a n-a cifra a sirului s, astfel ıncat numarul de pasi ai
programului sa ďŹe proportional cu log2 n (complexitate timp logaritmica ın functie de n).
Exemplu: Pentru n = 11 programul va aďŹsa 1, iar pentru n = 20 programul va aďŹsa 2.
Nu prea am idei, iar punctul b) imi pare imposibil, din moment ce nu inteleg conceptul de ”complexitate timp logaritmica in functie de n”
Si eu am dat aceasta admitere. Am incercat la primul punct sa abordez o solutie recursiva, care sa genereze sirul si sa afiseze toate elementele. Practic se afisa doar partitii de forma 1221 sau 2112, in functie de pasul recursiv. Problema mea era ca nu mai stiam cum sa ies din lantul de apeluri.
As vrea si eu o solutie de la cineva care a rezolvat aceasta problema.
La ce facultate ai intrat xor?
La Calculatoare, Bucuresti.
Felicitari! Ce medie ai avut? Cat ai luat la mate?
This is classified, unfortunately.
Felicitari, xor! Am si eu 2 intrebari😀
1.Prin Calculatoare te referi la Tehnologia Informatiilor si a Comunicatiilor?
2.Care dintre cele doua sectiuni(TIC sau informatica) este mai avantajoasa (ma refer si la ce ai putea face dupa termini)?
Facultatea de Automatică și Calculatoare din cadrul Universității Politehnica din București are două secții: Calculatoare și Tehnologia Informației(,) și Ingineria Sistemelor. Prima se prescurtează C.T.I., a doua I.S.
Tehnologia Informației și a Comunicațiilor este secția Facultății de Electronică, dacă nu mă înșel, deci e altceva decât Facultatea de Automatică.
Parcă și Facultatea de Matematică și Informatică are o asemenea secție de Tehnologia Informației și a Comunicațiilor.
În orice caz, dacă termini la CTI obții o diplomă de inginer (bachelor sau așa ceva…) iar dacă termini F.M.I la Informatică, obții o diplomă de informatician.
Atât CTI cât și F.M.I sunt recunoscute ca facultăți de Computer Science, deci diploma are valoare în domeniu.
Fiecare facultate are atât avantaje cât și dezavantaje, una în raport cu cealaltă.
De la CTI ieși inginer software, deci teoretic ai cunoștințe solide software dar dispui, de asemenea, și de cunoștințe hardware, fără de care nu s-ar completa conceptul de âinginerâ. Poți să lucrezi și din timpul facultății, dacă ai cunoștințele necesare. Evident, poți lucra ca programator, cercetător, chestii un pic mai âușoareâ, dar după ce termini, ai toate șansele să te angajezi la o firmă de soft pe un post de inginer IT, dacă ai suficientă experiență. Vorbesc aici de studenți care într-adevăr se țin de treabă…
Dacă termini F.M.I., aparent ai un avantaj, întrucât dispui de cunoștințe avansate de limbaje de programare imperative, orientate pe obiect, precum C#, Java, C++, se face și Python, parcă…Cu alte cuvinte, ai șanse foarte mari să te angajezi într-o firmă de soft. Singurul dezavantaj este că nu ai prea mare legătură cu structura internă a computerului, granița dintre hardware și software, limbaje de asamblare, electronică digitală, etc. Asta îți limitează oarecum orizontul, dacă vorbim de firme mari, cu un specific orientat pe hardware.
P.S.: Asta e doar o viziune proprie legată de aceste facultăți, pe care mi-am format-o din ce am mai citit și eu, din mărturiile unor studenți, deci nu aș vrea să fiu condamnat pentru orice interpretare inadecvată sau greșită.
P.S.2: Grapefruit: la CTI am intrat cu 9.52 iar la FMI am avut medie 7.43, din păcate…aș fi intrat pe locul 170 și ceva, întrucât s-au retras peste 70 de admiși…
E bine cand munca pe tot timpul liceului se concretizeaza in a intra in una din cele mai bune facultati din tara,astfel exista un echilibru normal;iar ce mai putin silitori simt o defaimare valorica !
Se pare ca am facut o confuzie, eu credeam ca ai intrat la Universitate la F.M.I.😀
Iti multumesc pentru toate clarificarile aduse !
A lucra singur îți oferă un avantaj foarte mare, comparativ cu a face pregătire în particular cu un profesor. Acest avantaj nu este văzut imediat, și există șansa de a nu-și dovedi utilitatea într-un examen apropiat, ci treptat, în timp.
Dacă vrei neapărat să iei un examen, faci meditații, acel profesor, având experiență, îți transmite raționamente, idei, tipuri de exerciții, pe care tu le preiei în mod direct, fără să muncești pentru a le înțelege substraturile (sau cu o înțelegere superficială a lor), foarte importante, de atlfel. Neînțelgerea acestor substraturi duce la o imagine greșită asupra a ceea ce crezi tu că ești dispus să faci în viață, deci la o alegere greșită a direcției în viață. Te trezești după 2 ani de facultate, atunci când lucrurile devin foarte serioase și când doar pasiunea te poate âține în viațăâ, că tu de fapt vroiai să te faci altceva (de făcut meditații nu cred că se mai pune problema).
Eu pot demonstra oricând veridicitatea notelor pe care le-am luat. Evident, în spatele acestor cifre stau zeci de ore de studiu, fără de care nu aș fi reușit.
Această siguranță, proprie oricărui autodidact, îți permite să faci față și altor provocări, cu care te poate întâmpina viața (încă din timpul facultății), provocări care apar atunci când meditatorul nu e lângă tine, spunându-ți calea cea sigură către reușită. Această alegere a căii corecte trebuie să vină din instinct, care are în spate o experiență substanțială, clădită pe zeci de eșecuri, zeci de succese, un echilibru natural.
Deci munca din timpul liceului, realizată într-o manieră autodidactă, este un element crucial pentru alegerea drumului în viață și pentru menținerea unei atitudini strict pozitive, optimiste, indispensabilă succesului.
Am o singura intrebare pentru ca nu mi se pare foarte explicit formulata regula.
Pana la urma este vorba de o forma de genul: s(k)=s(k-1) s(k-1)<barat> s(k-1)<barat> s(k-1) ?
sau este pur si simplu un sir de genul:
1221 2112 2112 1221 2112 2112 1221 2112 2112 1221
sau este vorba despre ceva de genul[ce ar contrazice cazul n=18]
1221 2112 2112 1221 1221 2112 2112 1221 1221 2112 2112 1221
Adica din descriere nu am inteles care e de fapt regula.
Într-adevăr, e cam ciudată regula, dar are totuși o logică.
Spune că șirul este generat incremental prin extindere. Asta înseamnă că termenul k este, ca lungime, mai mare decât termenul k-1, dar nu oricum, ci după o regulă de concatenare:
Mai exact, cum se construiește șirul:
Observăm că pentru termenul k, șirul are cifre, deci pentru n = 18, ai 4 la puterea 18 cifre…deci…multe.
La punctul a) al problemei spune să se afișeze primele 18 cifre ale șirului , deci în acel exemplu nu îți afișază tot șirul, ci doar primele 18 cifre ale lui.
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:
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😕
Aveti nevoie de ajutorul meu ptr pct b) ???
Mi-ar fi de mare ajutor explicatiile tale si eventual o rezolvare completa la punctul b). Imi bat capul de ceva timp cu problema asta si nu gasesc o rezolvare corecta…
Multumesc!
Daca nu intelegi ceva intreaba-ma!
Problema am avut-o la admitere.Punctul a):
#include<math.h>
#include<iostream>
using namespace std;
int sub2(int x,int n,int *a);
int sub1(int x,int n,int *a)
{
if (x==0)
if(*a<n)
{cout<<1;
*a=*a+1;}
if(x!=0)
{sub1(x-1,n,a);
sub2(x-1,n,a);
sub2(x-1,n,a);
sub1(x-1,n,a);}}
int sub2(int x,int n,int *a)
{
if (x==0)
if(*a<n)
{cout<<2;
*a=*a+1;}
if(x!=0)
{sub2(x-1,n,a);
sub1(x-1,n,a);
sub1(x-1,n,a);
sub2(x-1,n,a);}}
int a,i,x;
long n;
int main()
{cin>>n;
for(i=0;i<=n;i++)
if((pow(4,i)<=n)&&(pow(4,i+1)>=n))
{x=i+1;
i=n+1;}
sub1(x,n,&a);
return 0;}
Punctul b)
#include<math.h>
#include<iostream>
using namespace std;
int sub2(int x,int n,int *a);
int sub1(int x,int n,int *a)
{
if (x==0)
if(*a==n-1)
cout<<1;
*a=*a+1;
if(x!=0)
{sub1(x-1,n,a);
sub2(x-1,n,a);
sub2(x-1,n,a);
sub1(x-1,n,a);}}
int sub2(int x,int n,int *a)
{
if (x==0)
if(*a==n-1)
cout<<2;
*a=*a+1;
if(x!=0)
{sub2(x-1,n,a);
sub1(x-1,n,a);
sub1(x-1,n,a);
sub2(x-1,n,a);}}
int a,i,x;
long n;
int main()
{cin>>n;
for(i=0;i<=n;i++)
if((pow(4,i)<=n)&&(pow(4,i+1)>=n))
{x=i+1;
i=n+1;}
sub1(x,n,&a);
return 0;}
Nu este permisa folosirea bibliotecii math.h sau de ce se evita folosirea functiilor din ea?
Salut baieti! Am incercat si eu sa fac problema asta de la unibuc. Ce parere aveti? Eu m-am folosit de siruri de caractere.
Salut din nou! Am facut o incercare si la punctul b, de data asta am scris codul in engleza (comentarii si nume de functii, variable). Ce parere aveti?
[/code]