003 Fractii

[•svalentin]

Numere prime cu N? 3 nu e prim cu 9
Vrea sa spuna ca P1, P2.. sunt numerele prime mai mici ca N, care se divid cu N

vezi exemplu: Tot(36) = Tot(2^2 * 3^2) = 36 * (1 - 1/2) * (1 - 1/3) = 36 * 1/2 * 2/3 = 12

mai multe informatii se pot gasi pe wikipedia: http://en.wikipedia.org/wiki/Euler's_totient_function
... sau pe mathworld: http://mathworld.wolfram.com/TotientFunction.html

Btw, Paul, nu trebuie sa fii rau!

Later edit: Eddy, prin faptul ca ai fost la judeteana la mate nu inseamna ca stii mate! (un exemplu este sa tocesti tipuri de exercitii, dar sa nu poti gandi probleme 'din afara tiparului'). Informatica se imparte in mai multe domenii. Unul dintre ele este 'computer science', dupa cum zicea si azotlichid, acesta se ocupa cu studiul algoritmilor si eficentei programelor (..altii pot sa iti detalieze mai bine decat mine; daca doresti sa aflii). Prin faptul ca tu stii C nu inseamna ca stii 'computer science'. Aceasta este, teoretic, independenta de limbajul de programare (intr-o anumita masura). De aceea am si inteles ca s-a restructurat materia si in cls 9 nu se mai preda nici un limbaj de programare (se lucreaza in pseudocod).
Ideea este sa intelegi de aceasta problema se face cu ciurul lui Erathostene, ce face functia Totient (eventual sa intelegi in mare formula) si abia apoi sa ai cunosctintele de C necesare ca sa pui in practica toate acestea.

[nivan]

   Faza cu olimpiada de mate nu prea are legatura cu ce a scris azotlichid.
   Adica ce a vrut azot lichid sa zica e sa incerci sa si intelegi de ce rezolvarea merge. Sa nu citesti intr-o carte(sau pe forum) cum se face, sa o implementezi, sa iei un punctaj considerabil si sa nu inveti nimic din ea.
   Eu unu am inteles ideea, dar n-am reusit sa o implementez de 100 pct... sucess si spor la 

[•pauldb]

N-am vrut sa fiu rau. Dar...

TOATE NUMERELE SE DIVID.

4 se divide cu 1,2 si 4. Deci 4 se divide cu ceva.

[•wefgef]

am sa iti dau si definitia matematica:un nr a se divide cu alt nr b daca si numai daca exista un nr c ,astfel incat a=b*c.

sa mori tu?

[u-92]

nici un motiv sa va certati 

[•k_ounu_eddy]

Eddy, prin faptul ca ai fost la judeteana la mate nu inseamna ca stii mate! (un exemplu este sa tocesti tipuri de exercitii, dar sa nu poti gandi probleme 'din afara tiparului').

Crezi ca daca mergi la olimpiada la mate,trebuie sa ai niste modele de exercitii,care sa le inveti pe de rost,si apoi sa lucrezi dupa model?Sau trebuie sa stii sa ai o gandire foarte buna?Habar n-ai ce se da pe la geometrie cred.ma faci tu sa inteleg altceva despre tine dar nu mai zic nimic,ca vad ca orice as zice sunt interpretat ca am spus ceva rau.Cine stie matematica ,cei care raman repetenti?am avut si media 10 pe toti anii,niciodata nu am avut probleme cu matematica.Adica daca am fost la judeteana la mate,si am luat si un loc onorabil,inseamna ca nu stiu mate?ma cam indoiesc

Adica ce a vrut azot lichid sa zica e sa incerci sa si intelegi de ce rezolvarea merge.

Voi chiar ma credeti prost adica,voi credeti ca un tocilar ar avea sanse la o olimpiada de mate sau informatica,in care singurul lucru important este sa ai o gandire si o logica foarte buna?
Am inteles foarte bine algoritmul,insa am apelat la ajutorul vostru sa aflu forma generala a functiei totient,ca nu prea am inteles din linkul ala,ca erau foarte multe cazuri particulare.

sa mori tu?

Ia si mai invata matematica.Ia uite si un link aici http://www.referatele.com/referate/matematica/online2/Definitie-DIVIZIBILITATE--Divizor-si-multiplu-propriu-si-impropriu--Numere-prime-referatele-com.php,sa iti arat dovada.
Oricum multumesc ca m-ati ajutat,nu am sa mai apelez la ajutorul vostru,ca vad ca sunt inteles gresit;daca nu ma ajutati voi,stateam si nu dormeam o saptamana intreaga si tot o rezolvam.Acum ma duc sa incerc sa implementez algoritmul.

[•svalentin]

Nu stiu de ce te-ai suparat asa tare... ce am vrut sa zic este ca daca o persoana are note mari la scoala si daca a fost la olimpiada la X, NU implica automat ca chiar stie X! Invatamantul este de departe perfect! Dar NU m-am legat de tine!
Cunosc persoane olimpice la info care iau 8 in teza la info, cunosc colegi din generala care au avut 10 pe linie in generala, insa chair ei recunosteau ca sunt persoane mai destepte in materii ca matematica. Atat am vrut sa zic, ca nu este o relatie directa intre note-clasa si cat stie cu adevarat acea persoana.

Am mai incercat sa clarific termenul de 'computer science'.. de ce? pentru ca gradul de cunostiinta al unui limbaj de programare nu implica direct ca "rupi" de olimpiada la info. (de ex pointeri pot fi evitati uneori prin alte implementari, dar algoritmul sa fie la fel)

Repet, nu vreau sa iei totul asa personal, nu am zis ca nu stii info, nu am zis ca nu stii mate; poate am incercat sa te fac sa privesti putin altfel lucrurile!

De ajutat te-am ajutat pe cat am putut.. mai este ceva ce nu ai inteles?

[nivan]

 Ai inteles gresit ce am vrut eu sa zis (si cred ca si ce au vrut altii sa zica, desi eu vorbesc doar in numele meu). Ce ai scris mai sus cu tocilar si restu... poi eu nu te cunosc pe tine deci in nici un caz nu am incercat sa insinuez ca esti nici prost nici tocilar.
 Cat despre chestia cu faptul ca nu mai apelezi la ajutorul celor de pe forum... nu vad dc? Nu imi pare ca in topicul asta a scris cineva ceva ofensiv la adresa ta (cum observ ca ai interpretat tu)...... ce am scris eu cu intelesul rezolvarii, pur si simplu un sfat, mie imi pare mesajul scris chiar intr-o maniera calda.
 Nu vreau sa vorbesc in numele altora... dar mie si majoritatea celorlalte mesaje imi pare scrise tot intr-o maniera calda cu scopul de a te ajuta. 
 
 Oricum deja asta devine off-topic (nu mai are legatura cu problema)... ce vreau sa zic e ca nu am incercat sa te jicnesc in nici un fel (direct sau indirect). 

[•k_ounu_eddy]

Mii de scuze celor care au vrut sa ma ajute,care au avut intentii bune,dar cred ca eu am fost cel care a interpretat gresit lucrurile.Si scuze si celorlalti care  poate i-am jignit fara sa vreau.

[•Coty]

Iata cateva notiuni de aprofundat si de inteles, necesare acestei probleme:
* numere relativ prime
* factorizarea numerelor naturale
* ciurul lui Erathostene
* formula generala (functia Totient a lui Euler), cand intelegi demonstratia si reusesti sa o refaci singur 
* formula recursiva pentru calculul numarului de numere relativ prime cu un numar dat, mai mici decat acesta
* solutia finala
Spor 

numerele alea relativ prime sunt tot aia cu numerele aproape prime, notiune data, din cate stiu eu, de Ciucu la ONI 2006?

PS, pt Eddie: Cum au mai zis-o toti, nu o mai lua asa personal, iar daca gasesti o definitie in referatele de pe internet, nu o lua ca e cea mai buna... si pe de alta parte,  nu trebuie sa consideri ca toti de pe infoarena nu se pricep la nimica altceva decat informatica (cum ai adus aminte in faza cu problemele de geometrie) crede-ne ca in liceu e un pic altfel decat in gimnaziu si ca uneori mai stie lumea ce vorbeste legat si de olimpiadele de la alte materii (si de multe ori nu doar din auzite )...

[•Adriana_S]

numerele alea relativ prime sunt tot aia cu numerele aproape prime, notiune data, din cate stiu eu, de Ciucu la ONI 2006?

In engleza numerele prime intre ele se cheama 'relatively prime', deci presupun ca la asta se referea, altfel nu prea vad legatura cu problema.

[•k_ounu_eddy]

OK,am reusit si eu intr-un final sa ma incadrez in timpul de executie,folosind un alt algoritm,deoarece cel care l-ati implementat voi imi lua si mai mult decat cel initial(nu stiu daca v-am spus dar prima data comparam fiecare 2 numere mai mici ca n,si vedeam daca sunt prime intre ele cu algoritmul lui Euclid,dar imi iesea din timp),si incredibil fiecare test nu dureaza mai mult de 0.1 secunde,cu exceptia ultimelor 2 ,care dureaza 0,4 secunde  .Cu toate acestea nu inteleg de ce la toate obtin raspunsuri gresite,cu toate ca Silviug a pus un test pe prima pagina a topicului in care se da n-> rezultat,iar eu am introdus si eu aceleasi valori si am obtinut acelasi raspuns:

N -> Rezultat

11 -> 83
15 -> 143
31 -> 615
99 -> 6007
100 -> 6087
1000000 -> 607927104783

Am sa va spun si algoritmul pe care l-am folosit ,si inca un avantaj in afara de cel al timpului ar fi ca nici nu trebuie sa introduci mai mult de 25 de randuri.Deci sa va spun cum am gandit:
- se porneste de la fractia 1 / 1, aceasta constituind primul nivel
- pe al doilea nivel se trece sub prima fractie 1 / 2 in stanga, si 2 / 1 in dreapta
...........................
- pe un nivel oarecare x, sub fiecare fractie i / j din nivelul precedent, se trece i / (i + j) in stanga si (i + j) / j in dreapta.
Ex. n = 3
1 / 1
1 / 2 2 / 1
1 / 3 3 / 2 2 / 3 3 / 1.
Totusi imi puteti spune de ce obtin raspunsuri gresite?

[•Coty]

... sigur merge... CORECT ?!? Mai fii atent si la afisare... poate gresesti acolo...

[ditzone]

Raspunsul poate fi foarte mare esti sigur ca ai dat si testul
1000000 -> 607927104783
?

[•k_ounu_eddy]

La testul cu 1.000.000 nu imi merge ,imi da o eroare;ma gandesc ca asta ar fi din cauza ca eu am alocat doi vectori ,unul se numeste numitor,altul numarator,fiecare are cate 1000000 de elemente,si ca dimensiunea lor ar fi prea mare(am mai vazut vorbindeu-se despre asta pe prima pagina).Totusi la celelalte teste am raspunsul corect,sunt sigur 100%.Nu am inteles ce ai vrut sa spui Coty ,sa fiu atent la afisare poate gresesc acolo.cum adica?

[•Coty]

Pai zic si eu, daca folosesti long long sa pui la afisare "%lld" in loc de "%ld" sau "%Ld"... sau treburi d-astea, minore... zic si eu, nu stiu sursa ta si nu sugerez nimica.
Pe de alta parte, ai zis ca ai doi vectori de 10000000 de elemente... stai calm, daca elementele sunt long (si long long cred ca merg), iti incap in memorie. Daca nu incapea iti dadea Segmentation Fault sau Invalid Memory Refference, parca... era un articol legat de erori pe http://info.devnet.ro... incearca sa te uiti pe forum si prin articolele de pe info.devnet legate de rhide... o sa te ajute daca lucrezi in C / C++, pentru ca scapi de anumite limitari pe care le ai in Borland...


 

[•k_ounu_eddy]

Pai asta imi da Invalid Memory Reference.Am voie sa postez codul?Am compilat cu Visual C++ 6.0

[ditzone]

problema este ca raspunsul este mult mai mare decat cat ai alocat tu in vectorii aia, nu poti sa tii 607927104783 de elemente intr-un vector de 10000000 elemente....

[•k_ounu_eddy]

Dar chiar daca introduc si 5000 tot imi da eroare

[ditzone]

Pentru ca si raspunsul pentru 5000 depaseste 10 000 000...

[•k_ounu_eddy]

Ba nu depaseste,ca nu am folosit un algoritm de complexitate (n*n) sau (n*log n).Pur si simplu fiecare pozitie a vectorului numitor si numarator retine o fractie.De ex numitor[4]=4 ,numitor[3]=3,iar fractia este 3/4.alt ex :numitor[6]=8 numarator[6]=3,iar fractia este 3/8.

[ditzone]

Ce vreau eu sa zic este ca nu poti sa retii toate fractiile in memorie pentru ca sunt prea multe...

[•k_ounu_eddy]

De ce nu pot?Din cauza compilatorului BorlandC?SIlviug a zis ca e okay sa declari un vector cu 1 milion de int-uri.Atunci exista vreo solutie?

[•Coty]

Pe infoarena este compilator Gnu C / C++ ... incearca sa cauti niste detalii despre el, daca nu esti familiarizat.
Ideea e ca oricat de multe ar putea tine in memorie programele compilate cu gcc/g++, au si ele o limita, setata pe infoarena la 64MB. Ce zice Ditzone cred ca se refera la faptul ca numarul tau de fractii o sa fie mai mare decat poti retine... Incearca sa calculezi de cata memorie ai nevoie.

[•k_ounu_eddy]

Si atunci cum pot sa fac sa imi mearga?dar totusi intrebarea mea initiala era de ce nu imi da raspuns corect la testele cu numere mici?