Admitere informatica

Rezolvarea problemelor de matematica prin realizarea unor programe.
Pollux
junior
junior
Mesaje: 134
Membru din: 11 Mai 2012, 22:21

Admitere informatica

Mesaj de Pollux » 24 Iul 2014, 01:52

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'' :(

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 24 Iul 2014, 14:06

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.

grapefruit
veteran
veteran
Mesaje: 1063
Membru din: 24 Iul 2013, 17:40

Mesaj de grapefruit » 24 Iul 2014, 14:43

La ce facultate ai intrat xor?

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 24 Iul 2014, 15:07

La Calculatoare, Bucuresti.

grapefruit
veteran
veteran
Mesaje: 1063
Membru din: 24 Iul 2013, 17:40

Mesaj de grapefruit » 24 Iul 2014, 19:36

Felicitari! Ce medie ai avut? Cat ai luat la mate?

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 24 Iul 2014, 20:17

This is classified, unfortunately.

Pollux
junior
junior
Mesaje: 134
Membru din: 11 Mai 2012, 22:21

Mesaj de Pollux » 27 Iul 2014, 12:04

Felicitari, xor! Am si eu 2 intrebari :D

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)?

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 28 Iul 2014, 13:48

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...

grapefruit
veteran
veteran
Mesaje: 1063
Membru din: 24 Iul 2013, 17:40

Mesaj de grapefruit » 28 Iul 2014, 19:37

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 !

Pollux
junior
junior
Mesaje: 134
Membru din: 11 Mai 2012, 22:21

Mesaj de Pollux » 28 Iul 2014, 22:00

Se pare ca am facut o confuzie, eu credeam ca ai intrat la Universitate la F.M.I.:D
Iti multumesc pentru toate clarificarile aduse !

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 28 Iul 2014, 22:29

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.

crs12decoder
junior
junior
Mesaje: 133
Membru din: 31 Mai 2007, 16:43

Mesaj de crs12decoder » 05 Sep 2014, 17:14

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.

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 06 Sep 2014, 13:55

Î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.

crs12decoder
junior
junior
Mesaje: 133
Membru din: 31 Mai 2007, 16:43

Mesaj de crs12decoder » 07 Sep 2014, 14:11

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&#40;int k&#41;&#123; //calculeaza 4^k
    int result=1;
    while&#40;k>0&#41;&#123;
         result=result*4;
         k--;
    &#125;
    return result;
&#125;

int log_4&#40;int n&#41;&#123; //calculeaza log_4&#40;n&#41; si returneaza k
   int k=0;
   int aux=n;
   while&#40;n>0&#41;&#123;        
         k++;
      n=n/4;      
   &#125;
   if&#40;putere_4&#40;k-1&#41; == aux&#41;
     k--;
   return k;
&#125;

short returnare_atom&#40;char stare&#41;&#123; //functie care returneaza atomii in functie de starile 1 si 2
       if&#40;stare==1&#41;
          return 1221;
       else if &#40;stare==2&#41;
          return 2112;
       else
          return -1;
&#125;

int citire_scriere&#40;char aux&#91;&#93;, short a&#91;&#93;, int nr_aux&#41;&#123; //functie care citeste din aux starile si scrie atomii in a
     int i;
     for&#40;i=0; i<nr_aux; i++&#41;&#123;
             a&#91;i&#93;=returnare_atom&#40;aux&#91;i&#93;&#41;;
     &#125;
     return i;
&#125;

int cop_aux&#40;char aux&#91;&#93;,short a&#91;&#93;, int nr_a&#41;&#123; // functie care copiaza starile atomilor lui a in aux
     int nr_aux=0;
     for&#40;int i=0; i<nr_a; i++&#41;&#123; //parcurgem vectorul a
          int x=0;//contor din 4 in 4
          int ax; //variabila auxiliara care retine atomul ce trebuie citit
          ax=a&#91;i&#93;; //copiem atomul din a&#91;i&#93; in ax  
          while&#40;x<4&#41;&#123; //parcurgem starile fiecarui atom                
                aux&#91;nr_aux&#93;=ax%10; // scriem in aux fiecare stare din atom
                ax=ax/10; //trecem la starea urmatoare
                x++;
                nr_aux++; //mai adaugam o stare     
          &#125;           
     &#125;
     return nr_aux; //returnam ca si valoare marimea lui aux ca sa stim in continuare pana unde mergem
&#125;

void show_only_n&#40;short a&#91;&#93;, int cat, int rest&#41;&#123;
     int i;
     for&#40;i=0; i<cat; i++&#41;&#123;//mergem doar pana la primele n/4 elemente
              printf&#40;"%d", a&#91;i&#93;&#41;;//le afisam
     &#125;
     //trecem la elementul&#40;atomul&#41; urmator
     int ax=a&#91;i&#93;; //variabila auxiliara care retine urmatorul atom din a&#91;i&#93;
     
     //citim din el doar restul de elemente
     i=0;
     while&#40;i<rest&#41;&#123;
        printf&#40;"%d", ax%10&#41;;
        ax=ax/10;
        i++;          
     &#125;
&#125;

int main&#40;&#41;&#123;
    printf&#40;"introduceti n = "&#41;;
    int n;
    int i; //contor
    scanf&#40;"%d", &n&#41;; //citire n
    
    int k=log_4&#40;n&#41;; //calculam k pentru sk necesar
   
    short a&#91;nr_at/4&#93;; //alocam memoria pentru vectorul ce il va contine pe sk
    char aux&#91;nr_at/4&#93;; //alocam memoria pentru vectorul auxiliar
    int nr_aux=1; //numarul de elemente din aux
    int nr_a; //numarul de elemente din a
    
    aux&#91;0&#93;=1; //initializam vectorul auxiliar cu starea 1
    
    
    for&#40;i=0; i<k; i++&#41;&#123;//construim vectorul in memorie
             nr_a=citire_scriere&#40;aux,a,nr_aux&#41;; //citim starile din aux si le scriem in a ca atomi in a
             if&#40;i<k-1&#41; //ca sa nu mai umplem aux si ultima oara verificam copiem in aux doar pana la sk-1
                    nr_aux=cop_aux&#40;aux,a,nr_a&#41;; //copiem starile din a, atom cu atom, si le scriem in aux
    &#125;
    
    //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&#40;a,cat,rest&#41;;
    getch&#40;&#41;;    
    return 0;    
&#125;

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 :-?

Zeus
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 14 Oct 2014, 17:46

Aveti nevoie de ajutorul meu ptr pct b) ???

RalucaIoana
utilizator
utilizator
Mesaje: 1
Membru din: 28 Oct 2014, 19:49

Solutie problema

Mesaj de RalucaIoana » 28 Oct 2014, 20:02

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!

Zeus
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 30 Oct 2014, 11:04

Cod: Selectaţi tot

#include<cstdio>
#include<cstdlib>
#include<cmath>
int n,l,c&#91;1000001&#93;,i,j,k,d&#91;1000001&#93;,t,m,u;
int main&#40;&#41; &#123;
    printf&#40;"n="&#41;;
    scanf&#40;"%d",&n&#41;;
    l=&#40;int&#41;ceil&#40;log2&#40;n&#41;/2&#41;;
    c&#91;1&#93;=c&#91;4&#93;=1,c&#91;2&#93;=c&#91;3&#93;=2;
    for&#40;i=1;i<=&#40;1<<&#40;2*l&#41;&#41;;i<<=2&#41; &#123;
         for&#40;j=4*i+1;j<=8*i;j++&#41;
              c&#91;j&#93;=3-c&#91;j-4*i&#93;;
         for&#40;j=8*i+1;j<=12*i;j++&#41;
              c&#91;j&#93;=c&#91;j-4*i&#93;;
         for&#40;j=12*i+1;j<=16*i;j++&#41;
              c&#91;j&#93;=c&#91;j-12*i&#93;;
    &#125;
    for&#40;u=l,t=1;t<=n;t++&#41; &#123;
        l=u,m=t,k=0;
        while&#40;l--&#41; &#123;
             if&#40;&#40;1<<&#40;2*l&#41;&#41;<m&&m<=&#40;1<<&#40;2*l+1&#41;&#41;&#41;
                  m-=&#40;1<<&#40;2*l&#41;&#41;,k=1-k;
             else
                  if&#40;&#40;1<<&#40;2*l+1&#41;&#41;<m&&m<=3*&#40;1<<&#40;2*l&#41;&#41;&#41;
                       m-=&#40;1<<&#40;2*l+1&#41;&#41;,k=1-k;
                  else
                       if&#40;3*&#40;1<<&#40;2*l&#41;&#41;<m&&m<=&#40;1<<&#40;2*l+2&#41;&#41;&#41;
                            m-=&#40;3*&#40;1<<&#40;2*l&#41;&#41;&#41;;
        &#125;
        d&#91;t&#93;=k?&#40;3-c&#91;m&#93;&#41;&#58;c&#91;m&#93;;
    &#125;
    for&#40;i=1;i<=n;i++&#41;
    if&#40;c&#91;i&#93;!=d&#91;i&#93;&#41;
        printf&#40;"c&#91;%d&#93;=%d d&#91;%d&#93;=%d\n",i,c&#91;i&#93;,i,d&#91;i&#93;&#41;;
    system&#40;"pause"&#41;;
&#125;
Daca nu intelegi ceva intreaba-ma!

Tuudoor
utilizator
utilizator
Mesaje: 1
Membru din: 21 Mai 2015, 19:21

Rezolvare

Mesaj de Tuudoor » 21 Mai 2015, 23:53

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;}

MDCristi
utilizator
utilizator
Mesaje: 38
Membru din: 21 Oct 2012, 21:45

Mesaj de MDCristi » 22 Mai 2015, 12:18

Nu este permisa folosirea bibliotecii math.h sau de ce se evita folosirea functiilor din ea?

MDCristi
utilizator
utilizator
Mesaje: 38
Membru din: 21 Oct 2012, 21:45

Mesaj de MDCristi » 23 Mai 2015, 00:07

Salut baieti! Am incercat si eu sa fac problema asta de la unibuc. Ce parere aveti? Eu m-am folosit de siruri de caractere.

Cod: Selectaţi tot

#include <stdio.h>
#include <string.h>

#define MAX_DIGITS 1000000

char conjugaCifra&#40;char cifra&#41;
&#123;
    if&#40;cifra == '1'&#41;
        return '2';
    else
        return '1';
&#125;

void conjugaBucata&#40;char* bucata, char* rezultat, int marime&#41;
&#123;
    int i = 0;
    for&#40;; i < marime; ++i&#41;
    &#123;
        rezultat&#91;i&#93; = conjugaCifra&#40;bucata&#91;i&#93;&#41;;
    &#125;
    rezultat&#91;i&#93; = '\0';
&#125;

void afiseazaSirul&#40;int n&#41;
&#123;
    // +1 pentru caracterul null &#40;'\0'&#41;
    char rezultat&#91;MAX_DIGITS + 1&#93;;

    // Aici stochez temporar conjugatele dintr-un sir de la o iteratie la alta
    // Motivul pentru care impart la patru este ca o conjugata va avea mereu
    // doar 1/4 din marimea sirului din care face parte.
    char tmp&#91;&#40;MAX_DIGITS / 4&#41; + 1&#93;;

    // Atribui valoarea de baza sirului
    strcpy&#40;rezultat, "1221"&#41;;

    // k va lua initial valoarea 4 pentru ca atat este lungimea primului sir.
    // Se observa ca fiecare element al sirului este de 4 ori mai mare decat
    // precedentul.
    for&#40;int k = 4; k < n; k *= 4&#41;
    &#123;
        // Acum am conjugat prima parte a sirului.
        conjugaBucata&#40;rezultat, tmp, k&#41;;

        // Vom concatena de 2 ori conjugata
        strcat&#40;rezultat, tmp&#41;;
        strcat&#40;rezultat, tmp&#41;;

        // Acum conjugam conjugata ca sa obtinem din nou prima parte.
        conjugaBucata&#40;tmp, tmp, k&#41;;

        strcat&#40;rezultat, tmp&#41;;
    &#125;

    for&#40;int i = 0; i < n; ++i&#41;
    &#123;
        printf&#40;"%c\n", rezultat&#91;i&#93;&#41;;
    &#125;
    printf&#40;"\n"&#41;;

&#125;

int main&#40;&#41;
&#123;
    int n;
    printf&#40;"Introduceti n&#58; "&#41;;
    scanf&#40;"%d", &n&#41;;

    printf&#40;"Rezultatul este&#58; "&#41;;
    afiseazaSirul&#40;n&#41;;

    return 0;
&#125;

Scrie răspuns
  • Subiecte similare
    Răspunsuri
    Vizualizări
    Ultimul mesaj