problema informatica

Numarul minim de iteratii ar fi atunci cand se folosesc doar valorile necesare gen 2,3,5,7,11,13... adica numerele prime, ce rost ar avea sa mai impart la 9,15,21 samd.
Initial ma gandeam la altceva mai greu de am scris 16, dar dupa am realizat ca este doar cel mai mare divizor, normal cel mai simplu ar fi sa imparti la 2*k+1 cu k de la 1 la n div 4 si sa pui un break imediat dupa verificarea nr div i(contor), astfel la prima impartire exacta vei afla cel mai mare divizor adica nr/i, simplu si eficient pentru numere mici pana in 10^6.
Spre exemplu luam 303, dupa algoritmul tau am sqrt(303)/2 iteratii adica 9 iteratii, dar asta este maximul, normal ar fi sa ma opresc la 303 div 3, si cel mai mare divizor sa fie 303/3.

 takemeintoyourskin, on 12 februarie 2014 - 13:51, said:

Pai da, dar rezolvarea asta e valabila daca calculezi cmmd pe hartie, nu informatic.
Cand faci un program pentru asta, trebuie sa verifici divizibilitatea cu numerele prelucrate anterior si asta te-ar costa mult mai multe iteratii decat daca ai verifica 2 si numerele impare pana la sqrt(n)

In exemplul tau precedent, ar fi trebuit sa verifici divizibilitatea lui 9 cu 3, calculatorul "nu stie" ca 9 este divizibil cu 3 (numar prelucrat anterior).

Ok, pe scurt, scrie tu programul care foloseste algoritmul tau, iar daca are mai putine iteratii decat al meu, fac mea culpa

e aceeasi chestie.
ce facea el era sa afle cel mai mic divizor. dupa ce-l afla, automat, cel mai mare divizor ar fi fost n/cel_mai_mic.

Editat de RegeleCocalarilor, 12 februarie 2014 - 14:14.

 cristina81, on 12 februarie 2014 - 14:09, said:

In ce programez eu exista deja un vector cu numere prime, deci eu nu verific nimic, si sigur gasesti si in orice ai lucra tu acest vector(sunt constante pana la urma). In fine ideea este ca sqrt(n)/2 ar trebui sa fie numarul maxim de pasi, atunci cand numarul in cauza este prim, in algoritmul tau, sper ca ai inteles acum, numarul minim de iteratii este intre 1 si sqrt(n)/2 ca pentru dang dang.

haha, pt cel mai mic numar de iteratii, scrii un program in care verifici de fiecare cu nre prime. ))
gen imparti la 2, 3, 5, 7, 11 etc. valorile impartitorului fiind date in program, nu generate de un algoritm.
iar daca ar fi generate de algoritm, in loc sa elimini doar elementele care sunt divizibile cu 2, poti elimina elementele care sunt divizivile cu 2 si 3, cum am zis eu. intr-adevar, limita superioara e data de ceva cu sqrt(n).

gen, in afara de 2 si 3, pe care le introduci fara algorism, avem asa:

6*i-1 -> posibil prim
6*i -> divizibil cu 6
6*i+1 -> posibil prim
6*i+2 -> divizibil cu 2
6*i+3 -> divizibil cu 3
6*i+4 -> divizibil cu 2
6*i+5 = 6*(i+1)-1 -> posibil prim
6*(i+1) -> divizibil cu 6
etc.

Editat de RegeleCocalarilor, 12 februarie 2014 - 14:23.

 takemeintoyourskin, on 12 februarie 2014 - 14:17, said:

Limbajul de programare este irelevant.
Chiar daca ai vreo librarie care contine o functie gen Prim(), numarul de iteratii ramane din background este acelasi pt orice limbaj de programare pentru ca primalitatea tot trebuie verificata de catre functia ta, chiar daca aparent apelezi functia si gata.

(De exemplu strlen(sir) este functia care returneaza lungimea unui sir, cu toate ca scrii doar o linie de cod, in background, la un moment dat, se executa un numar de iteratii cel putin egale cu numarul de caractere din sir.)

In limbajele din gama low level, cum ar fi asm, nu ai astfel de functii, trebuie sa calculezi tot.

Deci, repet, ca sa nu ne mai lovim de bariera limbajului de programare folosit, scrie pseudocodul (banuiesc ca stii ce-i ala), ca sa putem numara iteratiile. Asa putem vedea clar cine are dreptate.

Editat de cristina81, 12 februarie 2014 - 15:36.

nu este o functie care verifica daca numarul este prim, ci un vector cu numerele prime cunoscute, sunt constante si daca tot le-a calculat cineva cu un calculator foarte destept de ce pana mea sa nu le folosim cu totii?, nu este o variabila cum ai dat tu exemplu strlen(sir). Nu-mi plac persoanele care atunci cand gresesc nu recunosc nici chip, ba mai mult o intorc pe toate partile posibile, in loc sa spui ca ai debitat o prostie cu acele n/2 n/3 si apoi ai continuat cu sqrt(n)/2.

 cristina81, on 12 februarie 2014 - 15:31, said:

Limbajul de programare (sau mai bine zis software-ul corespunzator) este relevant. De multe ori, datele "batute in cuie" de acest gen sunt stocate deja in software (de exemplu, Maple "stie" o gramada de factoriale fara sa le calculeze, doar le culege din memorie). Pentru programare este mult mai eficient sa memorizezi un vector cu numere prime si sa faci probe de divizibilitate cu elementele vectorului mai curand decat cu toate numerele impare (sau chiar 6k-1 si 6k+1) luate la rand (evident, in caz ca numarul de verificat nu este mai mare decat patratul celui mai mare numar prim stocat in memorie, altfel de la un punct incolo, treaba se complica). Limbajul de programare nu este relevant doar daca elimini aceasta posibilitate si fiecare primalitate a unui numar intermediar trebuie dedusa in prealabil (caz in care intr-adevar, numarul de operatii creste semnificativ).

Editat de mdionis, 12 februarie 2014 - 16:08.

 takemeintoyourskin, on 12 februarie 2014 - 15:50, said:

Nu mai revin la greseala mea de exprimare, oboseala in exces si-a spus cuvantul si intr-adevar desi am gandit una, am scris altceva. Dar nu trebuie sa ma justific in fata nimanui asa ca pentru linistea ta, considera ca am debitat o aberatie. Continuand pe acelasi ton, nu esti tu cel care ar trebui sa imi corecteze greselile avand in vedere aberatia cu 16, apoi cu 10 iteratii.

Pentru ca tot ai mentionat ce fel de oameni nu iti plac, iti spun si eu ceva: cand vii cu tonul cu care ai venit initial, adaugand si ironia ieftina care nu isi avea sensul, asteapta-te sa fii tratat ca atare, sa nu emiti pretentii. Tonul face muzica.

Insa altul este subiectul acum. Asa cum a spus si domnul mdionis, daca este eliminata memorarea vectorului de numere prime (iar eu am spus clar ca nu iau in considerare astfel de adaugiri ale unui limbaj de progamare, asta era conditia initiala), numarul de iteratii creste substantial, iar solutia mea este cea corecta.

Am lucrat destul de multi ani in dezvoltarea de solutii antivirus, si una dintre cerinte era lucrul in assembler, unde nu avem astfel de vectori predefiniti, lucram direct cu registrele procesorului.

Deci, scrii pseudocodul ala sau nu?


@mdionis,
Maple, ca si MatLab sau MT4, precum si alte softuri folosite in analiza financiara, prelucrarea datelor sau rezolvarea problemelor matematice complexe se bazeaza pe scripting language, nu sunt limbaje de programare propriuzise, e normal sa aiba astfel de elemente predefinite.

Dupa parerea mea, nu te poti numi programator (vorbesc in cazul general, nu ma refer la dumneavoastra) daca nu cunosti un limbaj low level.

Editat de cristina81, 12 februarie 2014 - 16:39.

vai de capu meu, si tot nu ai inteles ca solutia ta era o aberatie? ca sqrt(n)/2 este numarul maxim de iteratii posibile in cazul in care numarul caruia doream sa-i calculam cmmd era prim?

Editat de takemeintoyourskin, 12 februarie 2014 - 16:44.

 takemeintoyourskin, on 12 februarie 2014 - 16:43, said:

Reciteste cu atentie cerinta problemei. Nu spune nicaieri ca numarul este prim. Nu stim daca e prim sau nu.

Inca odata si renunt: scrii pseudocodul ala sau nu? Asa vedem cel mai bine cum sta treaba. Putem numara clar iteratiile. Daca gresesc, recunosc si nici nu mai postez de rusine.

hai ca mi-ai fost simpatica pe celalalt topic :
tu ai spus :
1. Testam daca numarul se divide cu 2, daca da, STOP. Daca nu, trecem la pasul 2
2. Testam numerele impare, pana la sqrt(n), si vom avea sqrt(n)/2 iteratii (nu, nu vom avea sqrt(n)/2 iteratii mereu)
eu spun :
1. Testam daca numarul se divide cu 2, daca da, STOP. Daca nu, trecem la pasul 2
2. Testam numerele impare, pana la sqrt(n), primul numar la care n div cu i(numar impar contor) ne oprim si aflam cmmd = n/i, celelalte numere impare pana la sqrt(n) nu ne mai intereseaza deoarece am afalt cmmd de aia este bine ca iteratiile urmatoare sa nu se mai FACA.
3. Putem concluziona ca numarul de iteratii este cuprins in intervalul (1, sqrt(n)/2), in functie de cel mai mic factor prim continut de n.

Si ca sa vezi cat plin de bunavointa sunt iti dau si un exemplu real : luam 303.
aplicam pasul 1, nu este par, trecem la pasul 2
303 mod 3 =0(true) ne oprim si aflam cmmd=303/3=101
astfel s-a realizat 1 pas(sau 2 daca pui si impartirea la 2 la socoteala)
sqrt(n) este 17
de ce s-ar mai calcula 303 mod 5....303 mod 17 ???

Si sa stii si tu ca in orice limbaj cat de mama lui "low" o fi, daca procedurile pentru a calcula ceva necesita mult mai multe resurse decat daca acel ceva ar fi deja in memorie atunci se apeleaza la memorie.
Spre exemplu eu lucrez in C si am nevoie de numere foarte mari prime, destul de des, nu o sa fiu tampit sa apelez mereu o functie care sa-mi calculeze acele numere, cand pentru a le stoca ai nevoie de cativa kb.

Editat de takemeintoyourskin, 12 februarie 2014 - 17:13.

Faci misto de mine, right? Altfel nu imi explic cum nu poti intelege faptul ca eu mi-am definit conditiile astfel: nu se foloseste niciun vector, template sau librarie.
Totusi tu insisti, ok, o lasam asa, consider discutia incheiata.

ce librarie iti trebuie ca sa faci :
1. Testam daca numarul se divide cu 2, daca da, STOP. Daca nu, trecem la pasul 2
2. Testam numerele impare, pana la sqrt(n), primul numar la care n div cu i(numar impar contor) ne oprim si aflam cmmd = n/i, celelalte numere impare pana la sqrt(n) nu ne mai intereseaza deoarece am afalt cmmd de aia este bine ca iteratiile urmatoare sa nu se mai FACA.
3. Putem concluziona ca numarul de iteratii este cuprins in intervalul (1, sqrt(n)/2), in functie de cel mai mic factor prim continut de n.
Incep sa cred ca o faci pe "proasta".

Editat de takemeintoyourskin, 12 februarie 2014 - 20:00.

Ti-am raspuns la ultimul paragraf in care pomeneai de numere prime foarte mari si de vectori predefiniti.

Cat despre algoritmul tau, asta ti-am cerut, recunosc ca ai dreptate si ca e solutia optima, trebuia sa-l postezi de la inceput fara sa aduci in discutie vectorii predefiniti si polemica nu mai exista. Deobicei nu stau sa optimizez pt ca nu am nevoie, asa ca nu m-am gandit la solutia asta.

Cum ai dreptate, imi respect partea mea de intelegere, imi cer scuze, si nu mai postez

Editat de cristina81, 12 februarie 2014 - 21:28.

Nu asta era intentia mea, nici pe departe si ar fi chiar pacat sa nu mai postezi atat timp cat ai lucruri interesante de spus, eu doar incercam sa intelegi ceva, cum nu prea mi-a reusit probabil este si vina mea, eu recunosc nu am fost niciodata un bun pedagog poate pentru ca mereu ma asteptam ca si celalalt sa vada lucrurile cum le vad eu.
In ultimul paragraf explicam cum se lucreaza cand ai nevoie de factorizari dese, iti definesti si singur daca nu gasesti librariile respective, iar foarte usor poti sa faci un algoritm care sa le calculeze pe cele prime pana la un max, apoi le stochezi si le folosesti in factorizari sau alti algorimi, in schimb daca este pentru un proiect in care singurul scop este sa afli cmmd atunci faci cum am scris mai sus si pare un compromis decent.

Editat de takemeintoyourskin, 12 februarie 2014 - 22:30.

De acord cu tine. Eu momentan lucrez la softuri de prelucrare statistica a datelor financiare, nu am mai lucrat cu numere prime de ceva vreme, asa ca daca nu am nevoie, imi permit luxul sa uit unele formule. Asa cum am uitat si algoritmii de sortare (am invatat o groaza la vremea mea) pentru ca nu am nevoie de ei, daca vreau sa sortez un vector aplic cea mai simpla metoda care nu este neaparat si cea optima (aici nu se aplica briciul lui Occam). Insa daca am nevoie de ceva neaparat, am de unde sa imi amintesc. E usor sa iti amintesti ce ai stiut odata.

Daca spui ca lucrezi cu numere prime mari, banuiesc ca lucrezi la softuri de criptografie, ca alta aplicabilitate nu prea vad. In acest caz, stocarea este absolut necesara, dificultatea factorizarii creste proportional cu numarul de cifre al numarului. Ar fi crima sa factorizezi un intreg mare de fiecare data cand ai nevoie de el.