infoarena

infoarena - concursuri, probleme, evaluator, articole => Teme => Subiect creat de: A Cosmina - vechi din Ianuarie 16, 2009, 21:10:15


Titlul: problema pascal
Scris de: A Cosmina - vechi din 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... :fool:

Titlul: Răspuns: problema pascal
Scris de: Pripoae Teodor Anton din 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 :)

Titlul: Răspuns: problema pascal
Scris de: A Cosmina - vechi din Ianuarie 16, 2009, 22:23:42
multumesc pentru sugestie, insa nu am inteles prea bine ce vrei sa spui...mai detaliat se poate?  :sad:

Titlul: Răspuns: problema pascal
Scris de: Sima Cotizo din 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:
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!

Titlul: Răspuns: problema pascal
Scris de: A Cosmina - vechi din Ianuarie 17, 2009, 10:49:38
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.
   ?

Titlul: Răspuns: problema pascal
Scris de: Gabriel Bitis din 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].

Titlul: Răspuns: problema pascal
Scris de: A Cosmina - vechi din Ianuarie 17, 2009, 11:47:52
imi raspunde cu exit code=201 in ambele variante

Titlul: Răspuns: problema pascal
Scris de: alexandru din 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
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.

Titlul: Răspuns: problema pascal
Scris de: Sima Cotizo din 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:
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).

Titlul: Răspuns: problema pascal
Scris de: alexandru din 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
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
    }
:D Sarmanul   i-am dat  atatea  metode de rezolvare  incat  poate scrie o carte

Titlul: Răspuns: problema pascal
Scris de: A Cosmina - vechi din 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....
Citat
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?  :-k

Titlul: Răspuns: problema pascal
Scris de: Sima Cotizo din 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:
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 :P )

Titlul: Răspuns: problema pascal
Scris de: A Cosmina - vechi din 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 :peacefingers:

Titlul: Răspuns: problema pascal
Scris de: alexandru din 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............. :P

Titlul: Răspuns: problema pascal
Scris de: A Cosmina - vechi din 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 :)

Titlul: Răspuns: problema pascal
Scris de: alexandru din 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....... 

Titlul: Răspuns: problema pascal
Scris de: Andrei Grigorean din 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 (http://infoarena.ro/problema/iepuri) din arhiva.

Titlul: Răspuns: problema pascal
Scris de: alexandru din Februarie 15, 2009, 20:21:30
Uite aici forumla
1/√5 {⌈(1+√5)/2⌉^n│-⌈(1-√5)/2⌉^n }
unde  √5=sqrt(5);

Titlul: Răspuns: problema pascal
Scris de: Andrei Grigorean din 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.

Titlul: Răspuns: problema pascal
Scris de: redco mihai din 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.


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines