DAU FUNDA! Cine le are la Informatica C++?

Nu stiu cum determini numarul elementelor prime dintr-un vector ( v[30] ) in c++. Ma poate ajuta cineva? Funnndaaa!

Question

DAU FUNDA!  Cine le are la Informatica C++? 

 Nu stiu cum determini numarul elementelor prime dintr-un vector ( v[30] ) in c++. Ma poate ajuta cineva? Funnndaaa!

CM7YRE · Answer

Fa-ti o functie care testeaza daca un numar e prim,si aplici functia pe fiecare element din vector. Apoi iti iei un contor, si pui un if:
Daca functia determina ca e prim, contorul creste si trece la urmatorul element, daca nu, doar trece la urm. element.

SexoasaTha · Answer

Ai facut functiile?

SexoasaTha · Answer

Foloseste site-ul asta ca sa iti faca escape la < > ca altfel iti mananca tot comentariul
http://www.htmlescape.net/htmlescape_tool.html

SexoasaTha · Answer

Numai debifeaza "Replace newline with "

Da, am vazut ca iti merge mai repede programelul tau, dar atat timp cat poate fi imbunatatit mai mult... credeam ca te-ar interesa.
Si spam nu prea cred ca facem. Cel care a pus intrebarea sigur nu mai e peaici.

CaffeBoy · Answer

Si asa am transformat in chat.
In fine, m-am plictisit de o tampenie de prim.
Daca vrei sa stam la "taclale" de informatica arata-mi ceva interesant nu cum se verifica un nr prim (de clasa a5-a)

SexoasaTha · Answer

Facand chestii aparent simple inveti cel mai mult... dar daca tu zici.
Exista metode mai rapide de a afla sqrt decat cea din math.h
De exemplu, in programarea grafica e nevoie foarte des sa normalizezi vectori. Si formula respectiva implica extragerea unui radical (sqrt), mai exact sqrt^-1. Dar sqrt e o functie foarte inceata si costisitoare. Daca o folosesti de cateva milioane de ori pe secunda se duce fps-ul jocului in jos. Asa ca au folosit o aproximare a lui sqrt^-1.
De asemenea, exista si metode mai rapide de a afla sqrt, nu doar sqrt^-1
Uite:
http://en.wikipedia.org/wiki/Fast_inverse_square_root
http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi?msg=4264365#xx4264365xx
Asta ti se pare interesant?

Ai putea de exemplu, sa faci un programel care afiseaza primele n numere prime din sirul lui fibonacci, in ordine descrescatoare? (de clasa a cata ti se pare asta?)

CaffeBoy · Answer

Da, mi se pare interesanta faza cu radicalul
Programul cu n nr prime din sirul lui fibonacci e usor de facut, dar in momentul de fata daca l-as face, l-as face ineficient (prima ideea ce mi-a venit fu sa pun fiecare nr din sir pe vector si sa-l afisez descrescator) dar probabil ca exista si o formula  sa le gasesti descrescator.

Apropo de chestia cu prim, mai exista o formula ciudata (daca suntem la capitolul "interesant"):
if (!(x % (x-1)! + 1)) atunci x este prim

SexoasaTha · Answer

Ideea cu pusul in vector pare cea mai ok.
Ai putea sa folosesti functii/stiva pentru a afisa numerele recursiv, dar asta o sa fie mai inceata pentru n mare.
Dar daca chiar vrei sa optimizezi si exercitiul asta, iti mai dau un hint: eu m-as uita la formula F(n-2)=F(n)-F(n-1) de aici http://en.wikipedia.org/wiki/Fibonacci_number

if (!(x % (x-1)! + 1)) atunci x este prim 
Si ce marja de eroare are chestia asta? Pentru ce fel de numere merge? Chiar arata ciudat rau :))

CaffeBoy · Answer

Am gasit intr-o carte de algoritmi sub numele de "Algoritmul lui Wilson" dar e cam ineficient si nu merge pe numere mari (are un factorial acolo)

Daca insisti cu fibonacci fa-l tu recursiv si eu pe vector si vedem care-i mai rapid.
De fapt cea mai usoara cale (cum sirul lui fibonacci nu merge prea extins pe long long int) este sa faci un vector initiat cu valorile din sir.

SexoasaTha · Answer

Eu ma refeream doar la afisare sa fie recursiva, ca sa nu trebuiasca vector pentru a fi afisate descrescator. Dar si asta o sa fie inceata pentru multe numere de afisat...

CaffeBoy · Answer

Nu stiu la ce te referi.
Ai spus numerele prime din sirul lui fibonacci afisate descrescator, eu doar atat am scris: http://pastebin.com/82XRa5ut

SexoasaTha · Answer

Ehm, ideea era sa le calculezi tu. Nu sa le faci copy paste intr-un vector si sa le afisezi. Asta poate sa faca oricine.

SexoasaTha · Answer

Stii sa implementezi operatii pe numere mari?

CaffeBoy · Answer

Nu, enuntul dat de tine spune clar sa afisezi numerele prime din sirul lui fibonacci in ordine descrescatoare. Nicidecum sa nu folosesc un vector prestabilit sau sa calculez intr-un mod anume numerele. Ai precizat "afisaza".
Dar asa cum am calculat acele numere din vector asa le pot pune in sursa si putem considera problema rezolvata (iar timpul de executie este sub 1s cu mult)

SexoasaTha · Answer

Dar asa nu inveti nimic.
Si daca dau n=20 Ce se intampla?

CaffeBoy · Answer

Daca dai n=20 nu arata corect :)
Si aici intervin fabuloasele operatii pe numere mari pe care nu le-am implementat vreodata (de fapt, nu mi-au folosit pana acum) - dar stiu ca se fac pe 2 vectori unde pozitia x este cifra x din nr n

SexoasaTha · Answer

Poate ca acum ar fi momentul potrivit sa incerci sa le implementezi:P
De exemplu(sa usuram problema initiala): sa afisezi primele n numere din sirul fibonacci in ordine crescatoare, cu n maxim 300
Cum suna?

CaffeBoy · Answer

Suna bine doar ca daca n depaseste 12 (peste long... ) deja intervin adunarile / scaderile cu 2 vectori
Pana aici e totul usor si frumos, dar cum verifici ca numarul cu cifrele pe vector este prim? asta nu stiu eu.

SexoasaTha · Answer

Da, e mai nasol asta. Trebuie sa implementezi si impartirea pe numere mari.
Cred ca adunarea ar ajunge pentru inceput...

CaffeBoy · Answer

In fine, am sa implementez pe zi si voi reveni cu "programelul" (asa cum spui tu si minunata mea prof. de info)
E cam tarziu si nu stiu despre tine dar am scoala.

SexoasaTha · Answer

Cand ai timp&chef, of course

CaffeBoy · Answer

Am implementat eu jumate, e randul tau sa faci verificarea daca e prim.
Dedapt sa faci o impartire (pe 2 numere mari) si, ca sa nu stai ani sa calculeze, sa calculezi radical dintr-un numar pe vector.
http://pastebin.com/TAFGAkYe

SexoasaTha · Answer

`

bruuu · Answer

#include
void main()
{int numar, i, s;
s=0;
coutnumar;
for(i=1; i

bruuu · Answer

Http://pastebin.com/vPrtvRMx

CaffeBoy · Answer

Da-mi funda ca le am.

Nu e ideea cea mai eficienta
Practic n-ai nevoie de vector, presupunand ca ai un N citit de la tastatura si un vector cu N numere poti face direct de la citirea "vectorului" verificarea daca  e prim dar daca tii sa scrii mai mult si sa-l faci si mai ineficient atunci il faci cu vector

Pt prim verifici daca nr e par, daca da, nu e prim altfel iei un contor de la 3 pana la radical din nr cu pas2 (pentru a elimina contorul pozitiv) si incepi sa verifici daca nr tau se imparte la contor
Daca numarul nu s-a impartit la contor atunci incrementezi o variabila pe care o afisezi la sfarsit.


Ideea ar fi cam asa:

int p(int x)
{int i; if(! x%2)return 0; for(i=3; i>n;
for(i=0; i>x; v[i]=x; }
for(i=0; i

SexoasaTha · Answer

Ce face  if(! x%2)return 0;?

CaffeBoy · Answer

Daca x este par (restul impartirii la 2 = 0)  functia returneaza 0 (fals)
Asa ar fi cea mai eficienta metoda pentru ca la:
x= 1,     000,    000,   001
metoda cu "pentru i=2, n dc x mod i = 0 return 0" parcurge 1,     000,    000,   000 iar cu sqrt parcurge  32 mii si metoda mea doar  15 mii
M-am uitat si pe sursa lui raindrops, daca obs trebuie sa pa rcurga pentru x de mai sus, 1 miliard de numere, atribuiri si comparatii. ( pentru i=1 i

SexoasaTha · Answer

Daca x este par (restul impartirii la 2 = 0) functia returneaza 0 (fals)
Nu cred ca face asta. Ai testat cumva?

SexoasaTha · Answer

Asa ar fi cea mai eficienta metoda pentru ca la:
x= 1,     000,    000,    001
metoda cu "pentru i=2, n dc x mod i = 0 return 0" parcurge 1,     000,    000,    000 iar cu sqrt parcurge 32 mii si metoda mea doar 15 mii

"Metoda ta" nu a fost postata pe site. Foloseste pastebin.com ca raindrops.
1, 000,     000,    001 se divide cu 7,     dar daca zici ca ai gasit o metoda mai rapida ca sqrt(nr) is curios s-o vad.

CaffeBoy · Answer

Am testat
Daca spui ca se imparte la 7 bine, ideea era ca un nr ff mare prim ar dura mult sa-l verifice.

Daca faci c++ am sa-ti dau o sursa in limbajul de programare s-o testezi ca sa vezi si faza cu functia:


Pentru x = 330000067 pe sursa mea (http://pastebin.com/2nNj9730) am stat mai putin de 1 secunda pentru rezultat, pe sursa lui raindrops (http://pastebin.com/s4yvqvxt) pe acelasi x am stat lejer 6 minute.
Testeaza si vei vedea diferenta.

CaffeBoy · Answer

E de mentionat si urmatorul lucru :
Executarea unui program decurge mai rapid daca nu trebuie apelate functii si toate variabilele sunt locale (se lucreaza mai greu cu cele global) (!)SI functiile de i/o sa fie in C nu in C++ (C lucreaza mai rapid) asta pentru timp de executie mai mic

SexoasaTha · Answer

In postul initial uitasesi o paranteza la if(! x%2)return 0; 
Ma rog, dar si 2 e numar prim... dar programelul tau zice ca nu e.
Si int i ala din functie nu cred ca e cea mai inspirata alegere... ce se intampla daca sqrt(x) depaseste 32mii?

CaffeBoy · Answer

Asa e, daca modifici in if( (x%2)==0 && x>2 ) atunci pentru x=2 iti arata ca e prim (ca sa te simti bine)
Si aia cu int i este tot un lucru minor, il faci long int si gata (long long nu are rost pentru ca merge pana la sqrt (asta asa ca sa economisesti si memorie))

SexoasaTha · Answer

Stiai ca in for(i=3; i

CaffeBoy · Answer

Da

SexoasaTha · Answer

Foarte amuzant. Am uitat ca TPU mananca...

Stiai ca in for(i=3; i<=sqrt(x); i+=2), expresia de test i<=sqrt(x) se executa la fiecare iteratie? Adica sqrt(x) e recalculat de fiecare data cand testeaza, indiferent daca x e acelasi sau nu...

CaffeBoy · Answer

Daca tot n-ai inteles lasa-mi id-ul tau sa nu mai facem spam

CaffeBoy · Answer

Da, dar daca observi, cu sau fara, tot imi rezolva problema in mai putin de 0 secunda.
Oricum observatia e buna, dar atata timp cat am scos 6 minute din sursa precedenta este irelevant faptul ca se recalculeaza un radical totul facandu-se in

DAU FUNDA! Cine le are la Informatica C++? Nu stiu cum determini numarul elementelor prime dintr-un vector ( v[30] ) in c++. Ma poate ajuta cineva? Funnndaaa!

DAU FUNDA! Cine le are la Informatica C++?

Nu stiu cum determini numarul elementelor prime dintr-un vector ( v[30] ) in c++. Ma poate ajuta cineva? Funnndaaa!