Question

Salut problema admitere la facultate :
V. Informatic˘a
Se consider˘a ¸sirul de numere naturale x = 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, . . . (fiecare num˘ar natural nenul
apare, ˆın ordine, de un num˘ar de ori egal cu el ˆınsu¸si). a) Se d˘a un num˘ar natural nenul n. S˘a se
scrie un program care afi¸seaz˘a primii n termeni al ¸sirului x. b) Se d˘a un num˘ar natural nenul n. S˘a
se scrie un program care afi¸seaz˘a ˆın timp constant (care nu depinde de n) al n-lea termen al ¸sirului
x. c) Se d˘a un num˘ar natural nenul n ¸si n numere naturale nenule y1, . . . , yn. S˘a se scrie un program
care verific˘a (afi¸sˆand ”DA”, respectiv ”NU”) dac˘a exist˘a o permutare a termenilor y1, . . . , yn care s˘a
fie identic˘a cu primii n termeni ai ¸sirului x. d) Dat¸i o solut¸ie ˆın timp liniar (ˆın funct¸ie de n) cerint¸ei
de la punctul c).


La punctul a si b l-am rezolvat
puncutl a
#include
#include
#include
unsigned int n;
unsigned int *v;
void main()
{
cout<<"n=";cin>>n;
int nr=n*(n+1)/2
a=malloc(nr*sizeof(int));
int i=1;
int j;
while(i==nr)
{
for(j=1;j<=i;j++)
v[i]=i;
i++;
}
for(i=1;i<=nr;i++)
cout< free v;
getch();
}Am observat ca sunt n*(n+1)/2 numere alocam spatiu pentru un vector fix de n*(n+1) numere .creem vectorul dupa care il afisam.
la punctul 2
#include
#include
#include
unsgined int n;
double sol;
void main ()
{
cout<<"n=";cin>>n;//al n-lea element;
//stind ca suma celor n elemente este n*(n+1)/2 si fie solsolutia
sol*sol+sol-n=0;
float delta;
delta=1+4*n;
sol=(-1+sqrt(delta))/2;
sol=ceil(sol);//daca este un numar de exemplu 7,5 inseamna ca sunt otate cifrele cu 7 doar ca mai sunt si cifre cu 8 cateva nu ne intereseaza cate cifre de 8 sunt stim doar ca sunt dar nu toate
cout<<"al "< getch();}
LA punctul c nu inteleg cine este y1 y2 .... nu am idee cum ar trebui sa incep

Answer 1

La c practic iti cere sa creezi o lista cu toate permutarile numerelor date y1,...yn si sa gasesti in acea lista subsirul de n elemente din x(x=1,2,2,3,3,3,.).
   Numerele y1,..,yn se dau. De fapt nici nu cred ca trebuie sa faci permutari (complexitatea ar putea fi n! si e prea mult). Poti verififca daca POATE exista o permutare care sa semene cu primele elemente n din sirul x. Adica verifici in primele n elemente ale sirului x cati de "1", de "2", "3" ,.."n" se afla (ex. in x=1,2,2,3,3,3 va fi un "1" ,doi de "2" si trei de "3") si inmagazinezi aceste informatii. Apoi vezi daca aceleasi numere si aceeasi cantitate se afla in (sa-l numim) sirul Z (format din y1,..,yn). Daca exista atunci desigur ca la o permutatie se va gasii acel un sir in Z care sa coincida cu cel din X.
    De fapt nici nu mai trebuie sa inmagazinezi ceva (decat pentru sirul Z).
Pentru un management mai bun al memoriei poti stoca asa valorile:
     -intr-un array indexul unui element va reprezenta valoarea acestuia iar valoarea in array la acel index va fi de cate ori se repeta acel numar 
         Ex. :array [0]=>0 ; [1]=>1 ; [2]=>2 ; [3]=>4 (asta se poate intampla in Z. [3] TREBUIE sa aiba valoarea 3 nu 4 adica sa fie doar de 3 ori).
         De asemenea trebuie sa te asiguri la inceput ca cel mai mare nr. din Z e egal cu n. Daca nu e egal afiseaza direct NU.

Cod:

int Z[]; //vector sau un array initializat la maximum

cin>>n;
for(int i=0;i<n;i++){
   cin>>yi;
   Z[yi]++;  //cantitatea
   //introdu in Z valoarea yi.
}

int i=0;
for(i=0;i<n && Z[i]==i;i++);  //Va rula atata timp cat se respecta conditia Z[x]=x

if(i==n) {        //a rulat pana la capat
  cout<<"DA";
}else cout <<"NU";

Il poti face chiar mai rapid. In primul for..acolo poti deja testa daca nu se respecta conditia:
int Z[]; //vector sau un array initializat la maximum
bool terminated=false;

cin>>n;
for(int i=0;i<n;i++){
   cin>>yi;
   Z[yi]++;  //cantitatea
   if(Z[yi]>y1) {terminated=true;break;}
   //introdu in Z valoarea yi.
}

if(terminated){
   cout<<"NU";
} else{
   //Desi terminated e false tot nu stim daca se respecta in totalitate conditia
   //Acest cod va fi apelat de mai putine ori ca cel trecut
   //Daca terminated e false inseamna ca fiecare numar apare de cate ori trebuie in Z. Insa probabil ca te intrebi :dar daca apare de mai putine ori? Am testat doar daca apare de mai multe ori ("if(Z[yi]>y1) {terminated=true;break;}"). Nu-ti fa griji. Daca un numar apare de mai putine ori decat ar trebuii (ex: 3 apare numai de doua ori in Z) atunci un alt numar trebuie sa apara de mai multe ori (pantru a fi tot n numere in Z.) Asa ca un numar tot va trebuii sa fie mai mare. Si deci in acest else nu mai trebuie sa pui nimic.


}