problema pascal

[•miculprogramator]

Buna! Sunt noua pe aici...Invat Pascal de ceva timp, insa am dat de o problema care imi cam da batai de cap: Se da sirul 1,2,2,3,3,3,4,4,4,4,5.... Se da un nr k , sa se afiseze elementul de pe pozitia k. A doua parte cred ca stiu sa o fac, insa cum initializez eu sirul acela cu 1,2,2,3,3,3,4,4,4,4,5 si tot asa? Dati-mi macar un indiciu...

[•toni2007]

Salut

E clar ca sirul e format in felul urmator

1 ... 1 * 2 / 2 .................................1
2 ... 2 * 3 / 2 .................................2
3 ... 3 * 4 / 2 .................................3
...
N ... N * (N + 1) / 2 ........................N

Deci tu trebui sa afli N astfel incat N * (N + 1) / 2 < K. Pe pozitia K se va afla N + 1. Cum afli N-ul depinde in functie de limitele valorii K. o(1), o (sqrt(K)), cum iti este mai usor.

Spor

[•miculprogramator]

multumesc pentru sugestie, insa nu am inteles prea bine ce vrei sa spui...mai detaliat se poate? 

[•sima_cotizo]

In sir ai 1 de 1, 2 de 2, 3 de 3 ... n de n. In total ai n*(n+1) / 2 numere (adica 1+2+3+..+n). Tu vrei sa stii cam pentru ce n ai valoarea respectiva mai mica decat k, dar pentru n+1 nu. De ce? Pentru ca e clar ca al k-lea numar este unul dintre cele n+1 numere de valoare n+1. Incearca pe hartie cateva valori si ai sa vezi cum functioneaza Nu cred ca ai nevoie de sir, dar in orice caz:

Cod:

var a: array[1..1000] of integer;
{...}
k := 0;
for i:=1 to n do
     for j:=1 to i do begin
          a[k] := i;
          k := k+1;
     end;

Mentionez ca nu am mai programat in Pascal de vreo 3 ani asa ca se poate sa fi scris prostii

@Toni: nu cred ca era neaparat nevoie sa ii zici de complexitati Keep it simple!

[•miculprogramator]

adica asa?

Cod:

program vect_sir;
var v:array[1..100]of integer;
n,i,j,k:integer;
Begin
write('n=');readln(n);
var a: array[1..1000] of integer;
{...}
k := 0;
for i:=1 to n do
     for j:=1 to i do begin
          v[k] := i;
          k := k+1;
     end;
write('k=',k);
readln;
End.

   ?

[•gabitzish1]

Nu cred ca e bine. Tu folosesti k pentru a pune numerele in vector pe pozitii consecutive. La finalul ciclurilor, k = n * (n + 1) / 2.
Din cum am inteles eu enuntul, citesti o valoare K (tu ai citit n), si trebuie afisat numarul de pe pozitia respectiva in vectorul format. Cred ca trebuie sa afisezi v[n].

[•miculprogramator]

imi raspunde cu exit code=201 in ambele variante

[•alexandru92]

hm daca  te  uiti  atent   gasesti ca  fiecare  sir  incepe  de la    N(N-1)/2+1  si se  termina   N*(N+1)/2.  Deci  ai  avea
N*(N-1)/2+1<k<N*(N+1)/2;  le  inmultesti  cu  2 si da    N(N-1)+2<2*k<N(N+1);
Acum  trebuie  sa-l  scoti pe  N:)
N(N-1)+2<2*k; si ai
N^2-N+2(1-k)<0;
delat=1+8(k-1)  //ar fi venit   1-8(1-k) dar cum k>1 o sa avem  numar negativ
si rezultatul  cautat este   {1+sqrt(delta)}/2;
x^y- inseamna  x  la  puterea  y deci   o  implementare ar fi

Cod:

cin>>k;  //citesc  k
cout<<((1+(int)sqrt(1+8*(k-1)))/2);  // afiez  direct  rezultatul  sqrt(...)  radical de  ordinul 2 dintr-un numar
//Scuze  nu  stiu  pascal.

[•sima_cotizo]

In primul rand sper ca nu ai scris exact asa in sursa, pentru ca nici macar n-o sa-ti compileze. Incearca asa:

Cod:

program vect_sir;
var v:array[1..100]of integer;
n,i,j,k,x:integer;
Begin
write('n=');readln(n);
write('k='); readln(x);
k := 0;
for i:=1 to n do
     for j:=1 to i do begin
          v[k] := i;
          k := k+1;
     end;
write(v[x]);
readln;
End.

Observa in cod ca daca as citi in variabila k, as pierde-o mai incolo, asa ca citesc in altceva(x). Ai nevoie si de n citit pentru implementarea asta. Exit code 201 cred ca iti da pentru ca ai declarat vectorii doar de 100. Pune o valoare mai mare, gen 100000 acolo (in borland se poate sa nu mearga chiar asa). Gandeste-te ca n-ul trebuie sa indeplineasca conditia n*(n+1)/2 <= 100000 cand introduci datele, altfel abordarea asta nu e posibila (repet, in borland).

@Gabrel : nu v[n], ci v[k] sau v[ x ] in codul de mai sus. Eu asta inteleg
@Alexandru: buna rezolvarea in O(1) dar, repet, cred ca o ajuta sa incerce si "varianta babeasca" (pentru limbaj).

[•alexandru92]

sau alta  rezolvare  "babeasca"  dar  fara a  genera  sirul.  Observam  ca fiecare numar  N se repeta de  N  ori pe  scurt
1 odata
2 de doua ori
3 de  trei  ori etc.
deci  putem parcurge  cu un for de la  i=1 pana   cand suma numerlor este  <k
adica

Cod:

#include<iostream.h>
void main()
   {
    int i,s=0,k;//declar  varibilele
    cin>>k;//citesc
    for(i=1;s<k;i++) s+=i;  //parcurg  cu for-u 
    cout<<(i-1);  //afisez
    }

Sarmanul   i-am dat  atatea  metode de rezolvare  incat  poate scrie o carte

[•miculprogramator]

Buna dimineata  :oops:si mersi pentru solutii! poate ca nu chiar sa scriu o carte, dar in orice caz o sa am la ce ma gandi cand merg pe strada....

In primul rand sper ca nu ai scris exact asa in sursa, pentru ca nici macar n-o sa-ti compileze. Incearca asa:
Cod:
program vect_sir;
var v:array[1..100]of integer;
n,i,j,k,x:integer;
Begin
write('n=');readln(n);
write('k='); readln(x);
k := 0;
for i:=1 to n do
     for j:=1 to i do begin
          v[k] := i;
          k := k+1;
     end;
write(v

• );

readln;
End.
Observa in cod ca daca as citi in variabila k, as pierde-o mai incolo, asa ca citesc in altceva(x). Ai nevoie si de n citit pentru implementarea asta. Exit code 201 cred ca iti da pentru ca ai declarat vectorii doar de 100. Pune o valoare mai mare, gen 100000 acolo (in borland se poate sa nu mearga chiar asa). Gandeste-te ca n-ul trebuie sa indeplineasca conditia n*(n+1)/2 <= 100000 cand introduci datele, altfel abordarea asta nu e posibila (repet, in borland).

Eu am freePascal si vad ca merge...Insa cum pot sa fac sa-mi afiseze si sirul? 

[•sima_cotizo]

Afisarea sirului este un lucru "clasic" pe care il inveti intr-a 9-a. Daca ai trecut de siruri la clasa, atunci ar fi trebuit sa fii mai atenta, daca nu atunci te-ar ajuta sa discuti cu profesoara (daca te pregatesti pentru olimpiada).

In cod adauga asta inainte de ultimul readln:

Cod:

for i:=1 to k do write(v[i],' ');

@alexandru: tradu si in Pascal codul si o vei ajuta mai mult ( poti sa-ti editezi mesajele )

[•miculprogramator]

multumesc, ar fi util sa traduci codul...nu ma pregatesc pt olimpiada era doar o problema data...o sa discut cu ea, sa-mi explice  :thumbup:mersi

[•alexandru92]

Scuze  nu stiu  Pascal , ar  trebui ,  l-am facut in  a  5 si a 6, dar  l-am  uitat complet plus.............

[•miculprogramator]

lasa ca nu-i nimic, vad eu care-i treaba miercuri...pana atunci ma gandesc sa incerc caz particular cu solutia lui Sima Cotizo

[•alexandru92]

Si o  mica  sugestie cand  mai ai  probleme  cu siruri de generat sau aflat al k termen  nu genera tot sirul incearca sa gasesti o relatie astfel incat  sa nu generezi sirul ca deobicei  e  o  pierdere de timp si memorie, vor exista relatii intre numere  doar trebuie sa le gasesti si daca  nu  ramane   varianta  babeasca dar si aici trebuie sa  muncesti destul de mult la ea ca sa fie foarte performanta, caz in care mergi la concursuri sau olimpiada   .....
Si ca sa  dau exemplu  pentru  sirul  lui  fibonaci  Cine stie  cum pot genera   al  n-lea  termen  si  programu l sa aibe complexitatea  O(1) ?
Sirul  fibonaci    0 1 1 2 3 5 8 13 21  34....... 

[•wefgef]

Nu poti in O(1), dar poti in O(log N), cu ridicare logartimitca la putere a unei matrice. Pentru mai multe detalii studiaza problema iepuri din arhiva.

[•alexandru92]

Uite aici forumla
1/√5 {⌈(1+√5)/2⌉^n│-⌈(1-√5)/2⌉^n }
unde  √5=sqrt(5);

[•wefgef]

Din pacate formula nu are complexitatea O(1) si nici nu poate fi aplicata cu succes, deoarece trebuie sa ridici un numar real la o putere.

[•boond]

buna ajutati-ma va rog nu prea ma pricep la stringuri
De la tastatură se introduce un text.Elaborați un program care va afișa pe ecran lungimea celui mai lung cuvînt.