In I linie a fisierului TABEL.IN este inscris numarul natural n cuprins intre 2 .. 100, care indica numarul de elemente ale unui tabel T de elemente reale. In urmatorul al doilea rand sunt inscrise elementele respective ale tabelului separate prin spatii.
Elaborati un program pascal cu ajutorul caruia se va crea un fisier TABEL.OUT, in care se va inscrie in liniile respective solutiile urmatoarelor probleme:
LINIA I. Trei numere separate prin cate un spatiu: numarul de elemente negative, numarul de elemente nule si numarul de elemente pozitive din tabelul T.
LINIA II. Un singur numar natural, care va reprezenta numarul de elemente intregi ale tabelului T.
LINIA III. Un singur numar real, care va reprezenta Media aritmetica a celui mai mare si celui mai mic elemente ale tabelului dat T.
LINIA IV. Un singur numar natural care va reprezenta numarul de cazuri in care T va fi mai mic ca T[i+1].
LINIA V. Un singur numar natural care reprezinta numarul de elemente distincte ale tabelului dat T.
Remarci:
In cazul in care problemei i nu-i gasesti solutia in linia respectiva se va inscrie 0 (zero).
prima linie am facuto am nevoie de ajutor la urmatoarele daca ma puteti ajuta va rog frumos
Multumesc Anticipat.
tipul array pascal
-
Cosmin_NTG
- junior
- Mesaje: 240
- Membru din: 23 Aug 2010, 13:46
- Localitate: Bucuresti
Linia III: Calculezi maximul si minimul elementelor din vector (daca ai memorat toate elementele intr-un vector) si apoi utilizezi formula (Max+Min)/2.
Linia IV: Cu un for peste toate elementele tabloului verifici daca T<T[i+1]. Daca se indeplineste conditia, pui un contor care sa numere cazurile.
Linia V: Aici merge cu manipulare directa a tabloului, asta daca nu ai restrictii care sa priveasca performanta. Cu un for imbricat verifici daca un element al matricii apare de 2 sau mai multe ori. Daca e asa, ii atribui valoarea zero, sau orice valoare care sa il diferentieze de celelalte elemente. Dupa aceasta parcurgere, cu un for testezi daca numerele ramase in tablou sunt diferite de zero si le numeri.
La linia II e cam naspa. Ideea care imi vine in minte e sa creezi un vector paralel si sa verifici cu un for imbricat daca elementele din tabloul tau sunt egale cu cele din tabloul creat si le numeri cu un contor. Nu prea e eficienta metoda asta, dar e functionala.
Eu nu pot sa iti implementez in Pascal pentru ca nu il studiez la scoala deci nu stiu mai nimic legat de acest limbaj. Daca vrei iti pot implementa in C++ sau C.
Linia IV: Cu un for peste toate elementele tabloului verifici daca T<T[i+1]. Daca se indeplineste conditia, pui un contor care sa numere cazurile.
Linia V: Aici merge cu manipulare directa a tabloului, asta daca nu ai restrictii care sa priveasca performanta. Cu un for imbricat verifici daca un element al matricii apare de 2 sau mai multe ori. Daca e asa, ii atribui valoarea zero, sau orice valoare care sa il diferentieze de celelalte elemente. Dupa aceasta parcurgere, cu un for testezi daca numerele ramase in tablou sunt diferite de zero si le numeri.
La linia II e cam naspa. Ideea care imi vine in minte e sa creezi un vector paralel si sa verifici cu un for imbricat daca elementele din tabloul tau sunt egale cu cele din tabloul creat si le numeri cu un contor. Nu prea e eficienta metoda asta, dar e functionala.
Eu nu pot sa iti implementez in Pascal pentru ca nu il studiez la scoala deci nu stiu mai nimic legat de acest limbaj. Daca vrei iti pot implementa in C++ sau C.
-
Blaugranas
Linia II cred ca ar merge mai rpd cu conditia T==(int)T.
Linia V Daca ai studiat sortarile "smechere" cele in N*logN gen (MergeSort, HeapSort etc) ai putea sa faci mai rapid. Sortezi vectorul T apoi cu un for vezi care 2 sau mai multe elemente consecutive sunt egale. Dar ma cam indoiesc ca ai invatat sortarile asha ca mai bine faci ca Cosmin. Mai e o greseala in ce a spus Cosmin... nu-i atribui valoarea 0 ca 0 poate sa fie element al lui T si ai probleme atunci... ii atribui o valoare care sigur nu se gaseste in T.
In rest n-am ce comenta, totul e bine, parerea mea. Gandesti foarte bine Cosmin ptr un elev de cls a 10-a. Daca ai mai exersa si prb mai dificile, adica ai avea un antrenament eu zic ca te-ai descurca si la OJI (olimpiada judeteana de informatica si poate chiar mai sus cu putin bulan si stiinta la ONI). Ce n-ash da eu sa fiu de varsta ta... sa-mi incerc fortele cu ceilalti pe la OJI, ONI. Vise de-ale mele.
Linia V Daca ai studiat sortarile "smechere" cele in N*logN gen (MergeSort, HeapSort etc) ai putea sa faci mai rapid. Sortezi vectorul T apoi cu un for vezi care 2 sau mai multe elemente consecutive sunt egale. Dar ma cam indoiesc ca ai invatat sortarile asha ca mai bine faci ca Cosmin. Mai e o greseala in ce a spus Cosmin... nu-i atribui valoarea 0 ca 0 poate sa fie element al lui T si ai probleme atunci... ii atribui o valoare care sigur nu se gaseste in T.
In rest n-am ce comenta, totul e bine, parerea mea. Gandesti foarte bine Cosmin ptr un elev de cls a 10-a. Daca ai mai exersa si prb mai dificile, adica ai avea un antrenament eu zic ca te-ai descurca si la OJI (olimpiada judeteana de informatica si poate chiar mai sus cu putin bulan si stiinta la ONI). Ce n-ash da eu sa fiu de varsta ta... sa-mi incerc fortele cu ceilalti pe la OJI, ONI. Vise de-ale mele.
-
Cosmin_NTG
- junior
- Mesaje: 240
- Membru din: 23 Aug 2010, 13:46
- Localitate: Bucuresti
Am fost la OJI anul trecut. Stiu cu ce "se mananca". Dar am luat 8 puncte din 200 si...ce sa vezi...m-am calificat! Asta pentru ca unicul concurent al meu a luat si el tot 8 puncte. Am spus cred intr-un post...nu mai stiu in care ca vreau sa devin programator sau inginer IT. Am observat insa ca pentru asta imi trebuie mai mult matematica (imi trebuie foarte mult matematica), si de aceea o sa ma axez pe asta. Din cate am observat, in domeniul asta (IT-ul) trebuie sa stii foarte multe lucruri pentru a putea "face ceva". Eu incerc sa imi dezvolt cunostintele cat pot (mai am OOP-ul la C++ si termin limbajul - doar partea teoretica); in vara imi propun sa "invat" PHP, Java, C# eventual Perl si daca mai am timp si Scala. Daca vrei si tu sa activezi in domeniul asta, am putea fi parteneri, de ce nu?
P.S. Pot sa te intreb ce varsta ai?
P.S. Pot sa te intreb ce varsta ai?
-
Blaugranas
26. Daca iti place asha de mult IT-ul tb sa te duci la o facultate pe profil. Chiar nu inteleg cum de ai timp sa inveti atatea. Eu ori imi gestionez prost timpul ori chiar n-am timp. Eu inca nu mi-am incheiat conturile cu C-ul ... ce pretentii sa mai am de la altele. Tot zic de vreo 3 ani incoace ca ma inscriu si eu la concursurile astea de pe site-urile specializate in cazul meu infoarena... dar nu indraznesc pe masura ce incerc sa rezolv mai multe pe atat imi dau seama ca n-am acoperit toata materia cum tb... e groaznic.
-
Cosmin_NTG
- junior
- Mesaje: 240
- Membru din: 23 Aug 2010, 13:46
- Localitate: Bucuresti
Wow! Eu sincer credeam ca esti clasa a 11-a sau a 12-a. Da, intentionez sa intru la Automatica. In timpul scolii nu am timp aproape de loc pentru "vocatia" asta ca sa zic asa. Dar in vacante...incerc sa acopar cat pot de mult...si imi dau seama ca nu prea reusesc, dar tot incerc si incerc si incerc.
C-ul e un limbaj foarte inteligent, rapid si iti da posibilitatea sa controlezi totul (pana si afisarile variabilelor cu specificatorii aceia de format), de aceea il folosesc mai mereu cand vine vorba de probleme de algoritmica. In domeniul IT nu iti trebuie multa algoritmica, adica spre exemplu, daca vrei sa devii programator, trebuie sa stii sa rezolvi toate problemele de pe infoarena, spre exemplu. Nu. Nu spun ca nu trebuie sa stii algoritmica de loc pentru ca unii algoritmi sunt foarte necesari, de exemplu algoritmii de sortare, cum ar fi quicksort (foarte inteligent algoritmul, l-am abordat vara trecuta) pentru ca e destul de clar rolul lor. Ideea e ca IT-ul, in special partea de programare presupune multa viabilitate, adica sa fii capabil sa poti schimba paradigma, eventual limbajul daca e nevoie, pentru a putea realiza ceva eficient si cu consum de memorie mic. Spre exemplu sa analizezi performanta unui program in C++ prin observarea numarului de instructiuni din ASM generate din transpunerea codului din C++ in ASM. E foarte greu dar in acelasi timp si frumos.
Un alt site cu probleme de informatica, nu stiu daca il stii, este www.campion.edu.ro. Eu unul cred ca porblemele de pe acest site sunt mult mai grele decat cele de pe infoarena.
C-ul e un limbaj foarte inteligent, rapid si iti da posibilitatea sa controlezi totul (pana si afisarile variabilelor cu specificatorii aceia de format), de aceea il folosesc mai mereu cand vine vorba de probleme de algoritmica. In domeniul IT nu iti trebuie multa algoritmica, adica spre exemplu, daca vrei sa devii programator, trebuie sa stii sa rezolvi toate problemele de pe infoarena, spre exemplu. Nu. Nu spun ca nu trebuie sa stii algoritmica de loc pentru ca unii algoritmi sunt foarte necesari, de exemplu algoritmii de sortare, cum ar fi quicksort (foarte inteligent algoritmul, l-am abordat vara trecuta) pentru ca e destul de clar rolul lor. Ideea e ca IT-ul, in special partea de programare presupune multa viabilitate, adica sa fii capabil sa poti schimba paradigma, eventual limbajul daca e nevoie, pentru a putea realiza ceva eficient si cu consum de memorie mic. Spre exemplu sa analizezi performanta unui program in C++ prin observarea numarului de instructiuni din ASM generate din transpunerea codului din C++ in ASM. E foarte greu dar in acelasi timp si frumos.
Un alt site cu probleme de informatica, nu stiu daca il stii, este www.campion.edu.ro. Eu unul cred ca porblemele de pe acest site sunt mult mai grele decat cele de pe infoarena.
-
Blaugranas
Te contrazic quicksort-ul e un algoritm f slab. Pe cazul defavorabil ajunge la N^2. Cei mai buni algoritmi sunt aia pe care i-am zis eu mai sus. Infoarena e peste campion. Studiaza mergeSort-ul si heapSort-ul par ei grei dar odata ce-i intelegi o sa-mi dai dreptate. Am zis ca infoarena e peste campion deoarece cele 2 site-uri sunt "prietene" si totodata adversare.. Oamenii dintr-o parte si alta sunt cam aceeasi.(staff-ul e format cam din acelasi nucleu). Vreau sa devin programator si ca sa fiu bun in domeniu tb sa termin problemele de pe infoarena ma rog nu pe toate dar sa sar de 3/4 din ele. In privinta sortarii sunt si algoritmi mai rapizi ca cei pe care i-am mentionat eu care ruleaza chiar in N... dar acestia sunt restrictionati... tb sa stii min si max din sir si cateva informatii suplimentare. CountingSort si RadixSort merg asha. Cei de pe infoarena deseori ptr a le arata superioritatea celor de pe campion iau prb de acolo si le fac intr-o complexitate mai mica... adica mai pe inteles... daca pe campion timpul de rulare e o secunda pe infoarena poate ajunge la juma de secunda. Succes la Automatica... o sa ai nevoie.
-
Cosmin_NTG
- junior
- Mesaje: 240
- Membru din: 23 Aug 2010, 13:46
- Localitate: Bucuresti
Cred ca ai vrut sa zici ca quicksort-ul e "f slab" in comparatie cu algoritmii pe care i-ai mentionat ceea ce e o diferenta pentru ca quicksort-ul nu e greu de implementat si e recursiv ceea ce-i imprima un avantaj (cel putin ca timp de executie) fata de insert-sort sau bubble-sort sau select-sort care toate ruleaza in O(n^2). Am incercat odata sa inteleg metodele astea pe care le-ai mentionat dar am renuntat ulterior pentru ca nu le intelegeam. Stiu doar ca Heap-Sort nu e stabil si ca e greu de implementat. Din cate am citit "pe ici pe colo" am observat ca Intro-Sort e cel mai eficient algoritm de sortare. Parca scria ca e un fel de combinatie intre quicksort si heap-sort. In orice caz, e un algoritm "full logaritmic"; ruleaza in NlogN in toate cazurile. Asta e sortare eficienta, cred eu.
Thanks!
Thanks!
Quicksort e mai rapid in cazul mediu decat heapsort sau mergesort.
Sunt situatii patologice in care se ajunge intr-un caz degenerat pentru quicksort (iar performanta devine O(n^2)), dar sunt putin probabile in cazul unei implementari de calitate a quicksort-ului.
Ceea ce e interesant este ca se poate depista usor situatiile in care intri intr-un caz degenerat pentru quicksort, masurand numarul de apeluri recursive (adancimea de recusivitate). Cand aceasta depaseste k * log n (unde k e de multe ori 2), se trece la o sortare ce garanteaza O(n log n) (exemplu heapsort).
O alta optimizare este folosirea insertion-sort-ului cand detectezi ca array-ul de sortat a devenit suficient de mic, in urma divizarii si a opri recursivitatea mai repede.
Cele doua optimizari sunt facute de introsort. De exemplu, in toate implementarile STL pe care le cunosc, algoritmul sort e implementat folosind introsort iar stable_sort e implementat cu mergesort (quicksort si implicit introsort nu sunt stabile).
Un alt algoritm de sortare foarte eficient, care garanteaza O(n * log n) si in cazul cel mai defavorabil e Timsort. E "the new kid in the block", java 7 SDK a trecut de la o versiune tunata de quicksort la Timsort pentru sortarea array-urilor de primitive (vezi Arrays.sort()). Sortarea array-urilor de obiecte se face in continuare folosind mergesort, deoarece se vrea sa fie stabila.
In concluzie, quicksort e un algoritm util, din mai multe motive:
- in cazul mediu, in practica, e mai eficient decat heapsort, mergesort, shell sort. In plus, practica a aratat ca quicksort in cazul mediu foloseste mult mai eficient cacheurile procesorului din cauza unei localizari mai bune
- considerand o implementare de quicksort non-naiva (macar folosind median of three), e surprinzator de improbabil sa ajung in cazul cel mai defavorabil
- in general, in lumea reala nu vei folosi direct quick-sort ci o sortare adaptiva (cum e introsort), care detecteaza cazurile degenerate ale quicksort-ului si trece la un alt algoritm ce garanteaza O(n*log n) si in acele cazuri degenerate. Totusi, quicksort e una din "caramizile" de baza ale acestor algoritmi adaptivi, ceea ce il face un algoritm valoros.
Un document foarte util este acesta: http://www.cs.fit.edu/~pkc/classes/writ ... eering.pdf
Multe din implementarile de quicksort din diverse framework-uri se bazeaza pe analiza de acolo.
Sunt situatii patologice in care se ajunge intr-un caz degenerat pentru quicksort (iar performanta devine O(n^2)), dar sunt putin probabile in cazul unei implementari de calitate a quicksort-ului.
Ceea ce e interesant este ca se poate depista usor situatiile in care intri intr-un caz degenerat pentru quicksort, masurand numarul de apeluri recursive (adancimea de recusivitate). Cand aceasta depaseste k * log n (unde k e de multe ori 2), se trece la o sortare ce garanteaza O(n log n) (exemplu heapsort).
O alta optimizare este folosirea insertion-sort-ului cand detectezi ca array-ul de sortat a devenit suficient de mic, in urma divizarii si a opri recursivitatea mai repede.
Cele doua optimizari sunt facute de introsort. De exemplu, in toate implementarile STL pe care le cunosc, algoritmul sort e implementat folosind introsort iar stable_sort e implementat cu mergesort (quicksort si implicit introsort nu sunt stabile).
Un alt algoritm de sortare foarte eficient, care garanteaza O(n * log n) si in cazul cel mai defavorabil e Timsort. E "the new kid in the block", java 7 SDK a trecut de la o versiune tunata de quicksort la Timsort pentru sortarea array-urilor de primitive (vezi Arrays.sort()). Sortarea array-urilor de obiecte se face in continuare folosind mergesort, deoarece se vrea sa fie stabila.
In concluzie, quicksort e un algoritm util, din mai multe motive:
- in cazul mediu, in practica, e mai eficient decat heapsort, mergesort, shell sort. In plus, practica a aratat ca quicksort in cazul mediu foloseste mult mai eficient cacheurile procesorului din cauza unei localizari mai bune
- considerand o implementare de quicksort non-naiva (macar folosind median of three), e surprinzator de improbabil sa ajung in cazul cel mai defavorabil
- in general, in lumea reala nu vei folosi direct quick-sort ci o sortare adaptiva (cum e introsort), care detecteaza cazurile degenerate ale quicksort-ului si trece la un alt algoritm ce garanteaza O(n*log n) si in acele cazuri degenerate. Totusi, quicksort e una din "caramizile" de baza ale acestor algoritmi adaptivi, ceea ce il face un algoritm valoros.
Un document foarte util este acesta: http://www.cs.fit.edu/~pkc/classes/writ ... eering.pdf
Multe din implementarile de quicksort din diverse framework-uri se bazeaza pe analiza de acolo.
-
Blaugranas
@morpheus. Ce vrei sa demonstrezi? In primul rand complexitatea (daca stii ce-i aia) se ia pe cazul defavorabil care in cazul quicksort-ului e N^2. Nu ma lua pe mine cu optimizari nu stiu de care etc. N-am spus ca mergeSort-ul si heapSort-ul sunt cele mai bune, am spus doar ca-s mai bune ca quickSort. HeapSort-ul dintre algoritmii in N*logN se comporta foarte bine pe cand Quick-ul de care vb e as in N^2(in N logN nu face fatza...). In practica heap-ul si merge-ul mentionate de mine se comporta mult mai bine ca orice quick a-i implementa tu, te asigur. Asha ca lasa-ma cu povestile astea... daca ai intrat sa te contrazici cu mine nu-ti mai dau satisfactie.. n-o sa mai raspund la asha ceva. Chiar nu-mi vine sa cred ca s-a gasit cineva care sa afirme o asemenea grozavie... Cunostintele tale in ale programarii ma lasa indiferent (mai ales ca vorbesti in necunostinta de cauza)... poate pe altii ii "misca" dar pe mine nu. Totusi daca vrei sa demonstrezi ceva pune algoritmul tau pe infoarena la algoritmii de sortare nu stiu cum se cheama exact problema... si vedem atunci care are dreptate (evident daca te tine). O sa ne spuna evaluatorul tot stai fara grija. Daca accepti provocarea .. sa fie quickSort nu alte vrajeli.
Nu ma intereseaza infoarena, nu sunt elev.
Ultima oară modificat 03 Feb 2012, 15:47 de către morpheus, modificat de 3 ori în total.
-
Cosmin_NTG
- junior
- Mesaje: 240
- Membru din: 23 Aug 2010, 13:46
- Localitate: Bucuresti
Am vazut postul lui Blaugranas. Nu imi plac certurile sub nici o forma. Oricum, am urcat un cod pe infoarena la problema cu numele "Sortare prin comparare", cod care ilustreaza implementarea algoritmului quicksort in forma sa simpla, fara vreo optimizare sau modificare.
Acesta este codul:. Am luat 100 de puncte. Desigur, nu o sa ma crezi, deci iti dau link-ul catre borderou: http://infoarena.ro/job_detail/672954. Acum sper ca totul e clar.
Codul e scris de mine. Nu vreau sa se inteleaga ca tin cu morpheus. Daca este acel morpheus pe care il stiu eu, adica cel de pe bitcell, inseamna ca e programator deci stie mult mai multe decat noi doi la un loc. Dar nu sunt sigur de acest lucru, poate fi oricare alt utilizator sub acest nume.
P.S. Vorbele nu au prea multa valoare in programare. "Armele" unui programator sunt: codul si inteligenta.
Acesta este codul:
Cod: Selectaţi tot
#include<fstream>
#define CT 501010
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");
void quicksort(int v[CT], int left, int right);
int main()
{
int N, v[CT], i;
f>>N;
for(i=1; i<=N; i++)
{
f>>v[i];
}
quicksort(v, 1, N);
for(i=1; i<=N; i++) g<<v[i]<<" ";
return 0;
}
void quicksort(int v[CT], int left, int right)
{
int aux, mid, i,j;
i=left;
j=right;
mid=v[(left+right)/2];
while(i<=j)
{
while(v[i]<mid)
i++;
while(v[j]>mid)
j--;
if(i<=j)
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
i++;
j--;
}
}
if(left<j)
quicksort(v, left, j);
if(i<right)
quicksort(v, i, right);
}
Codul e scris de mine. Nu vreau sa se inteleaga ca tin cu morpheus. Daca este acel morpheus pe care il stiu eu, adica cel de pe bitcell, inseamna ca e programator deci stie mult mai multe decat noi doi la un loc. Dar nu sunt sigur de acest lucru, poate fi oricare alt utilizator sub acest nume.
P.S. Vorbele nu au prea multa valoare in programare. "Armele" unui programator sunt: codul si inteligenta.
Imi cer public scuze daca am jignit utilizatorii acestui forum, in special pe @Blaugranas ... m-am cam lasa dus de val. Nu-mi sta in obisnuinta sa jignesc pe cineva.
In ceea ce priveste partea tehnica a afirmatiilor mele (discutia despre sortari), sustin ce am spus, dar nu are rost sa adancim discutia si mai mult in contradictoriu. Fiecare e liber sa creada ce vrea.
@Cosmin_NTG, da, ne cunoastem de pe forumul pe care l-ai mentionat.
Happy coding.
In ceea ce priveste partea tehnica a afirmatiilor mele (discutia despre sortari), sustin ce am spus, dar nu are rost sa adancim discutia si mai mult in contradictoriu. Fiecare e liber sa creada ce vrea.
@Cosmin_NTG, da, ne cunoastem de pe forumul pe care l-ai mentionat.
Happy coding.