•miculprogramator
|
|
« : Ianuarie 16, 2009, 21:10:15 » |
|
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...
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #1 : Ianuarie 16, 2009, 22:17:28 » |
|
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
|
|
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #2 : Ianuarie 16, 2009, 22:23:42 » |
|
multumesc pentru sugestie, insa nu am inteles prea bine ce vrei sa spui...mai detaliat se poate?
|
|
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #3 : Ianuarie 16, 2009, 22:41:22 » |
|
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: 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!
|
|
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #4 : Ianuarie 17, 2009, 10:49:38 » |
|
adica asa? 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.
?
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #5 : Ianuarie 17, 2009, 11:32:57 » |
|
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].
|
|
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #6 : Ianuarie 17, 2009, 11:47:52 » |
|
imi raspunde cu exit code=201 in ambele variante
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #7 : Ianuarie 17, 2009, 13:30:25 » |
|
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 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.
|
|
« Ultima modificare: Ianuarie 17, 2009, 13:56:50 de către alexandru »
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #8 : Ianuarie 17, 2009, 14:37:52 » |
|
In primul rand sper ca nu ai scris exact asa in sursa, pentru ca nici macar n-o sa-ti compileze. Incearca asa: 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).
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #9 : Ianuarie 17, 2009, 15:01:46 » |
|
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 #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
|
|
« Ultima modificare: Ianuarie 17, 2009, 19:13:12 de către alexandru »
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #10 : Ianuarie 18, 2009, 10:32:05 » |
|
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?
|
|
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #11 : Ianuarie 18, 2009, 11:23:05 » |
|
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: 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 )
|
|
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #12 : Ianuarie 18, 2009, 12:00:38 » |
|
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
|
|
« Ultima modificare: Ianuarie 21, 2009, 21:00:15 de către miculprogramator »
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #13 : Ianuarie 18, 2009, 12:54:07 » |
|
Scuze nu stiu Pascal , ar trebui , l-am facut in a 5 si a 6, dar l-am uitat complet plus.............
|
|
|
Memorat
|
|
|
|
•miculprogramator
|
|
« Răspunde #14 : Ianuarie 18, 2009, 13:05:20 » |
|
lasa ca nu-i nimic, vad eu care-i treaba miercuri...pana atunci ma gandesc sa incerc caz particular cu solutia lui Sima Cotizo
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #15 : Ianuarie 18, 2009, 20:19:08 » |
|
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.......
|
|
« Ultima modificare: Ianuarie 24, 2009, 21:00:53 de către alexandru »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #16 : Februarie 14, 2009, 18:01:42 » |
|
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.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•alexandru92
|
|
« Răspunde #17 : Februarie 15, 2009, 20:21:30 » |
|
Uite aici forumla 1/√5 {⌈(1+√5)/2⌉^n│-⌈(1-√5)/2⌉^n } unde √5=sqrt(5);
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #18 : Februarie 15, 2009, 20:59:50 » |
|
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.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•boond
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #19 : Decembrie 11, 2016, 22:40:52 » |
|
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.
|
|
|
Memorat
|
|
|
|
|