Cine ma poate ajuta cu o metoda eficienta din punct de vedere el timpului de executie de determinare a numarului de divizori ai unui numar in C++? Eu am gasit o metoda insa nu este prea eficienta si am ramas fara idei….Astept daca nu un raspuns complet macar o idee care sa ma ajute.
As vrea sa vad si metoda ta!
Scuze, nu am prea avut timp in ultima vreme sa mai intru…Metoda postata de tine nu prea pare a afisa numarul de divizori daca inteleg bine, ci cateva din numerele care sunt divizori ai lui n, ma insel? Si din ce am observat eu incercand sa descopar o metoda eficienta divizorii trebuie sa mearga pana la jumatatea numarului, nu pana la radical din el pentru ca daca nu atunci nu contorizeaza toti divizorii (ia exemplul lui 8 ). Iata si metoda mea, care insa, repet, nu stiu daca e cea mai eficienta:
#include<iostream.h>
int main ()
{int n, nr=0,m;
cout<<„numarul este:”;
cin>>n;
for(int d=2;d<=n/2;d++)
if(n%d==0)nr++;
cout<<„Numarul de divizori ai numarului „<<n<<” este „<<nr+2;
cin>>m;
return 0;
}
Astept pareri in continuare!
Ba da! Algoritmul tau este optim! Intr-adevar… nu am fost atent am postat un algoritm care se foloseste la descomp in fac primi!
Ok. Multumesc pentru timpul pe care mi l-ai acordat!
#include<stdio.h>
#include<conio.h>
#include<math.h>
int main()
{int n,nr=0,i,m;
printf(„n=”);
scanf(„%d”,&n);
m=sqrt(n);
for(i=2;i<=m;i++)
if(n%i==0)
nr+=2;
if(sqrt(n)==m)
nr–;
printf(„%d\n”,nr+2);
getch();
return 0;}
Am urmarit discutia voastra … am gasit si eu o rezolvare putin imbunatatita fata de cea a elenei. Sper sa nu va suparati pe mine ca ma bag dar mi se pare mai optim asha. Nici nu stiu daca-i cel mai optim poate unu` gaseste ceva si mai optim ca al meu dar in fine cred ca sunt prin zona.
Stai linistit…nu cred ca este cineva care sa se supere pentru idei, doar de asta am si postat problema. pentru pareri…In ceea ce priveste algoritmul tau nu as putea sa spun daca este mai eficient sau nu pentru ca nu am invatat sa folosesc printf si scanf …daca ai timpul si rabdarea sa imi explici atunci poate as putea sa imi dau cu parerea…insa ceea ce pot spune e ca l-am rulat si nu prea afiseaza corect numarul de divizori pentru oricare numar, adica pentru unele da, pentru altele nu, de exemplu pentru 10 afiseaza 5 si daca nu gresesc 10 are doar 4 divizori (1, 2, 5,10). Oricum, repet, trebuie mers pana la jumatatea numarului pentru a contoriza toti divizorii, nu pana la radacina lui patrata. Merci oricum ca te-ai deranjat si ai rupt din timpul tau pentru a rezolva problema.
Mie-mi afiseaza 4. Nu tb sa te duci pana la jumatatea drumului. Daca te duci pana la radacina lui patrata gasesti ca ceea ce e in stanga e si in dreapta adica ptr cazul n=10. Radacina lui patrata e 2,… noi il luam intreg si anume 2.
Daca 2 e divizor si se vede clar ca e, atunci si 10/2 adica 5 e divizor si tot asha se observa ca nu ne mai tb. Ceea ce am scris acolo e ca automat si celalalt termen 10/d unde d e divizoru` gasit e tot divizor si in loc sa adunam cu 1 la fiecare iteratie adunam cu 2 ca am gasit 2 divizori dintr-un foc. Sa dau un exemplu mai complicat acum.
n=24 : Divizorii lui sunt : 1,2,3,4,6,8,12,24 in numar de 8. Mergem pana la radical de ordin 2 din 24 care ne da aproximativ 4 (in parte intreaga). Luam for-ul de la 2 la 4 inclusiv. 2 e divizor ok il punem si pe 12 in sinea noastra si-l adunam cu 2 la nr divizorilor. 3 e divizor da il punem si pe 8 in sinea noastra si-l adunam cu 2 la nr divizorilor. la fel si cu 4 si 6. Luam un fel de oglindit nu stiu cum sa explic altfel sper ca ai inteles. 2*12=3*8=4*6=24…si o sa vezi ca rezultatu` e 8.
Ceea ce e interesant e ce se intampla ptr 16 sau 25 sau ma rog alte nr patrate perfecte. Luam cazul n=9 : divizori: 1,3,9 radacina patrata 3.
Luam de la 2 la 3 for-ul 2 nu e divizor dar 3 e.
Il punem de 2 ori pe 3 iar daca radacina lui 9 e totuna cu radacina intreaga a lui 9 se scade un divizor…ca l-a pus pe 3 ca si cand ar fi de 2 ori. Sper ca ai inteles. Nu inteleg ce-ti da tie 5 ca mie-mi da toata ziua 4 si am dat copy paste la program n-am modificat nimic. Iar in ceea ce priveste printf si scanf sunt 2 functii din stdio.h exact cum sunt cout si cin din iostream.h . printf e aproape totuna cu cout iar scanf e aproape totuna cu cin.
Pardon la 10 e 3,….si il luam 3 nu stiu unde mi-a fost capu`…
Aha…da, am inteles…deci practic atunci cand descoperi un divizor impartind numarul la el adaugi si si catul ca fiind un alt divizor…da, corect…astfel scutesti destul timp decat daca ai fi mers pana la jumatatea numarului. Bine gandit! In ceea ce priveste printf si scanf, cum e mai eficient sa folosesc cout si cin sau printf si scanf? Si presupun ca au si ele o forma generala, care ar fi aia? Multumesc pentru explicatii!
Faza e ca eu lucrez cu printf si scanf si derivatele lor. La cout din cate stiu eu el ghiceste tipu` pe care vrei sa-l afisezi ei bine la printf nu ghiceste! Daca nu-i pui formatul corespunzator iti crapa. Deci printf(„%d”,x) cand vrei sa afisezi un intreg. %d reprezinta formatu` intreg ; %ld reprezinta formatu` long ; %f -> real(float) ; %lf -> double ; %c pentru un caracter iar %s pentru un sir de caractere… La citire folosesti scanf(„%d”,&x); sa zicem pui adresa de chestia pe care o citesti(indiferent ca-i vector sau alta chestie)
Cu scanf si printf poti jongla mai bine zic eu…exista si alte functii ajutatoare care merg cot la cot cu astea cum ar fi getc,putc sau gets,puts cel mai bine e sa exersezi pe borland c tb asta…eventual daca ai si un help si mai bine…Nu prea ma pricep la explicat si incerc sa imbunatatesc lucru` asta dar nu prea-mi iese oricum sper ca ai inteles ceva acolo. la fel ca si la cout poti sa scrii mesaje intre ghilimele nu tb neaparat sa afisezi un nr sau un char etc .
E destul de complicat cu printf si scanf dar eu unu` consider ca e eficient.
Ok. Mersi mult oricum…o sa cer mai multe detalii profului meu de info ca a cam uitat sa ne explice cum sta treaba cu functiile astea…eu am folosit doar cout si cin dar ar vrea sa invat si chestii noi, sanu raman doar la stadiul asta si de aia te-am intrebat..oricum mersi inca o data ca ai incercat sa imi explici, si asa cum zici tu ca nu te prea pricepi, am reusit totusi sa-mi fac o idee!
Cu placere
Mi se pare ca c++ pt a calcula radicalul foloseste devoltarea Taylor cu un epsilon maxim stabilit. Pentru valori mici ale lui n, este mai rapid sa utilizam n/2, iar pentru valori mari ale lui n este preferabil sa folosim radical din n. Mai exact devine utila utilizarea radicalului atunci cand diferenta dintre n/2 si radical din n este semnificativa… (nr de iteratii pt calculul radicalului + radical din n iteratii < n/2 iteratii)!😛 😀
Ma bucur ca sunteti interesati de informatica..!
Ok… Multumesc pentru raspuns, insa avand in vedere ca in informatica majoritatea problemelor au aspect de generalitate, cum ar trebui sa imi dau seama cand trebuie sa folosesc o metoda,si cand cealalta? De exemplu daca am un sir de numere in care am atat numere mici cat si numere mari…care metoda e mai eficienta? Sper ca intelegi ce am vrut sa zic…astept raspuns cand poti….
1. Domnule larry91 daca faci informatica de liceu cred ca folosesti valori mici ale lu` n dar daca avansezi in domeniu observi ca lucru` cu numerele mici devine o raritate. 1/2=0 radical(1)=1 2/2=1 radical(2)=1.4142 luand valori intregi se opreste tot la 1…deci de la 2 incolo lucrurile devin limpezi cred…singura valoare discutabila e 1.
2. Nr de calcul al radicalului e mare zici u, adica mai mare ca n/2. Domnule cand o sa studiezi la facultate complexitati o sa-mi dai dreptate ca nu ne intereseaza cum s-a ajuns la radical e o functie din biblioteca si e oricand mai eficienta ca nr de iteratii decat n/2-ul tau.
3. Daca u consideri ca e distractiv sa gasesti divizorii lui 1 cu metoda n/2 etc inseamna ca chiar vrei sa devii amuzant!
Sper ca te-am convins…cu alte cuvinte NU e eficient sa lucrezi cu n/2 cand exista metode mult mai bune ca acest radical. Asta poate sa ti-o zica orice programator, in complexitate si in calculul timpului de executie nu intereseaza pe nimeni de unde apare radicalu` ne intereseaza ca pentru n>1 [sqrt(n)]<=n/2 .
Domnule Blaugranas, in primul rand mesajul tau ar fi fost mult mai bine primit daca nu ar fi inclus si arogranta respectiva… mesajul meu nu cred ca te-a insultat! In al 2-lea rand daca consideri ca esti programator nu poti spune ca nu ne pasa de unde vine radicalul si cum e implementat in librariile c++-ului! Normal ca este implementat optim! In al 3-lea rand nu vad unde este greseala in ceea ce am zis eu, daca tu o gasesti te rog sa o prezinti!
In al 4-lea rand, domnule, pt valorile din cls care nu sunt mari dupa cum ai spus si tu, utilizarea oricarei metode dintre cele 2 este rapida! Vreau sa iti spun ca pe 2.2 GHz dual core pana la valoarea de 50000 a lui n nu se observa nicio diferenta in practica!(verificat!).
In cel mai rau caz in inegalitatea mea prezentata mai sus nu ar exista solutii, dar in niciun caz nu este eronata!
Domnule larry91 n-am vrut sa te insult sub nici o forma dar chiar nu pot fi de acord cu tine cand zici ca e la fel de eficient. NU este. Pentru calculul complexitatii (timpului de executie sau spatiului din memorie) e nevoie de un algoritm cat mai eficient. Stiu si eu cum e implementat radicalu` dar nu asta e important. Daca ne legam de fiecare detaliu nu mai ajungem sa vorbim de ceea ce e mai important(eficienta). Normal ca nu se vede nimic ptr valori mari… ptr ca presupun ca n-ai facut buna implementarea ptr calculu` timpului (tb luat un decalaj de la o iteratie la alta, numai asha se vede…) daca vrei iti dau programu` cu decalaj si ai sa te convingi! Revenind la ce am zis prima oara…cu insultatu` … eu insult in momentu` in care sunt contrazis si am dreptate pe tema respectiva…de fapt pot face 2 lucruri…ori sa nu raspund ori sa „insult” cum ai zis tu…
Oricum n-are rost sa ne certam pe o tema ca asta…am vazut ce programe faci si ptr un tanar te descurci excelent…dar la nivel de liceu. Poate de aici apare si problema…eu nu vad lucrurile ca in liceu. Nici acum n-am vrut sa jignesc daca am facut-o scuze, n-a fost cu intentie…chiar am vrut sa sune bine chiar a lauda.
Domnule, nu vreau sa continuam subiectul acesta pentru ca nu cred ca s-ar sfarsi candva si nu vreau sa conducem subiectul catre off-topic! Vreau sa mai spun doar ca nu am zis ca e optim sa folosesti n/2, ci din potriva am zis ca e preferabil sa folosesti radical din n, insa pana la o valoare mica ( nu stiu care o fi ea… ), s-ar putea sa fie mai rapid n/2. Nu este gresita afirmatia mea
dupa cum am zis… in cel mai rau caz nu exista solutie, sau solutia este cazul trivial! Am sa incerc sa fac rost de codurile de care am nevoie pentru a calcula complexitatile si pentru a putea sa determin n-ul acela, plus ca am zis ca in practica nu se observa nicio diferenta pana la 50000 si nu ca nu ar fi…! Exista una nesemnificativa! Sper ca de data aceasta am fost foarte clar si ca am trimis corect idea mea mai departe!(Nu ma ocup numai cu programarea de liceu, ci ma ocup si cu coduri care nu au treaba cu liceul!)
Ok atunci nu mai continuam. Succes in proiecte(cele care n-au tb cu liceu`).
acela nu e un algoritm deloc eficient. cel mai eficient algoritm de calculare a numarului de divizori este:
P.S.: se gasea pe google
Da!😀 Nu pot decat sa te felicit! Cel putin la prima vedere asa mi se pare mult mai eficient, nu am avut timp sa ii analizez complexitatea, dar asa pare!
Mi se pare super tare algoritmul pe care l-ai gasit!
Legat de aceste functii: ele sunt incluse, printre multe altele in fisierul antet <stdio.h> (std input/output.header) si se comporta, cum a sus si Balugranas, ca functiile cout si cin ale fisierului antet <iostream> (input/output stream). Diferenta este data de faptul ca fisierul antet <stdio.h> este unul dintre factorii ce definesc limbajul C, spre deosebire de fisierul antet <iostream> care este unul dintre factorii ce definesc limbajul C++.
Limbajul C este caracterizat de nivelul ridicat de libertate ce il confera programatorului. Adica programatorul trebuie sa specifice toate datele necesare unei intructiuni, de ex. unei instructiuni de afisare (printf) trebuie specificat tipul datei pe care o afisaza, si data respectiva.
Aceasta libertate acordata programatorului, de cele mai multe ori influenteaza in mod negativ atat programatorul cat si programul,datorita riscului crescut de aparitie a erorilor. Dar trebuie sa recunosc faptul ca limbajul C, poate conferi un avantaj programatorului daca este utilizat in mod corect.
Spre deosebire de limbajul C, limbajul C++ are un caracter mai restrictiv, ceea ce avantajaza programatorul, datorita scaderii riscului de aparitie a erorilor.
Sa luam un exemplu:
Ne propunem sa atribuim valoarea 6 unei variabile de tip intreg pe nume „variabila” si sa o afisam.
In limbajul C:
In limbajul C++:
In primul caz, se observa aparitia lui %d ceea ce desemneaza tipul datei ce se va afisa, si o virgula(,) dupa care apare variabila.
%d este un specificator de format. Balugranas a explicat mai sus aceasta problema.
Ca o comparatie intre cele 2 functii, pot spune ca s-a schimbat numele in primul rand, apoi operatorii relationali „<<” au fost inlocuiti cu paranteze respectiv cu o virgula.
Sper ca acum e un pic mai clar.
Legat de aceste functii: ele sunt incluse, printre multe altele in fisierul antet <stdio.h> (std input/output.header) si se comporta, cum a sus si Balugranas, ca functiile cout si cin ale fisierului antet <iostream> (input/output stream). Diferenta este data de faptul ca fisierul antet <stdio.h> este unul dintre factorii ce definesc limbajul C, spre deosebire de fisierul antet <iostream> care este unul dintre factorii ce definesc limbajul C++.
Limbajul C este caracterizat de nivelul ridicat de libertate ce il confera programatorului. Adica programatorul trebuie sa specifice toate datele necesare unei intructiuni, de ex. unei instructiuni de afisare (printf) trebuie specificat tipul datei pe care o afisaza, si data respectiva.
Aceasta libertate acordata programatorului, de cele mai multe ori influenteaza in mod negativ atat programatorul cat si programul,datorita riscului crescut de aparitie a erorilor. Dar trebuie sa recunosc faptul ca limbajul C, poate conferi un avantaj programatorului daca este utilizat in mod corect.
Spre deosebire de limbajul C, limbajul C++ are un caracter mai restrictiv, ceea ce avantajaza programatorul, datorita scaderii riscului de aparitie a erorilor.
Sa luam un exemplu:
Ne propunem sa atribuim valoarea 6 unei variabile de tip intreg pe nume „variabila” si sa o afisam.
In limbajul C:
In limbajul C++:
In primul caz, se observa aparitia lui %d ceea ce desemneaza tipul datei ce se va afisa, si o virgula(,) dupa care apare variabila.
%d este un specificator de format. Balugranas a explicat mai sus aceasta problema.
In rest, caracterele escape si operatorii de adresare si de redirectare (pointeri) sunt la fel ca cei din C++.
Ca o comparatie intre cele 2 functii, pot spune ca s-a schimbat numele in primul rand, apoi operatorii relationali „<<” au fost inlocuiti cu paranteze respectiv cu o virgula.
Sper ca acum e un pic mai clar.
Nu se foloseste dezvoltarea Taylor in implementarea functiei sqrt din biblioteca standard C++. Considerand arhitectura x86, se foloseste instructiunea fsqrt (FPU) pentru asta.
O implementare tipica ar fi:
iSeLast …stiu ca pare greu de crezut…dar ciuru` lui eratostene se poate imbunatati simtitor fata de ce ai scris tu acolo. Deci in concluzie te-ash ruga sa nu vii cu afirmatii gen : asta e algoritmul cel mai eficient de calculare a nr de divizori…ptr ca lucrurile nu stau asha… Dar fiindca ai gasit unu` mai eficient ca al meu…(la vremea respectiva) te felicit…
Scuze atunci. Eu asa stiu din ce am auzit. Il stiu pe primul cu radicalul si pe asta. Si n-ar strica sa ne arati un exemplu cu ciurul lui Eratostene:P
01.#include<fstream.h>
02.#include<iostream.h>
03.#include<math.h>
04.#define N 1000000
05.int test,u,nr,p[N]={0};
06.long long n,t,s;
07.long k=0,i,j,l,q,r,x[N];
08.
09.void sieve(long x[N],long *k,int p[N])
10.{long i,j;
11.x[++(*k)]=2;
12.for(i=1;((i*i)<<1)+(i<<1)<=N;i+=1)
13.if((p[i>>3]&(1<<(i&7)))==0)
14. {for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=N;j+=(i<<1)+1)
15. p[j>>3]|=(1<<(j&7));}
16.for(i=1;2*i+1<=N;++i)
17.if((p[i>>3]&(1<<(i&7)))==0)
18. x[++(*k)]=2*i+1;}
19.
20.int main()
21.{ifstream f1(„ssnd.in”);
22.ofstream f2(„ssnd.out”);
23.f1>>test;
24.sieve(x,&k,p);
25.for(u=1;u<=test;u++)
26. {f1>>n;
27. i=1;
28. t=n;
29. s=1;
30. nr=1;
31. while(t>1&&x<=sqrt(t))
32. {j=0;
33. while(t%x==0)
34. {j++;
35. t/=x;}
36. if(j!=0)
37. {nr=nr*(j+1);
38. if(j==1)
39. s=s*(x+1);
40. else
41. {q=x+1;
42. for(r=1;r<j;r++)
43. q=q*x+1;
44. s*=q;}}
45. i++;}
46. if(t>1)
47. {nr*=2;
48. s=s*(t+1);}
49. if(s==1)
50. {nr=2;
51. s+=n;}
52. f2<<nr<<” „<<s%9973<<endl;}
53.f1.close();
54.f2.close();
55.return 0;}
Asta e dupa parerea un algoritm eficient. E sursa mea de 100 de pct de pe infoarena. Nu zic ca-i cel mai eficient dar se apropie mult de zona aia.
In prb am calculat si suma divizorilor modulo 9973… Ptr a verifica eficienta baga-i niste exemple de nr f mari…numai asha observi la timpi modificari fata de ceilalti algoritmi. Din pacate nu e 100% rezolvarea mea… ideea cu ciurul optimizat (sieve) e a celor de pe infoarena si e recomandarea lor ptr prb asta. Vezi ca sursa are un anumit format aici…ca sa vezi ca functioneaza da intrari de fisiere text cu extensia .txt in loc de in si out.
#include<fstream>
#include<stdio.h>
int ciur[100000];
using namespace std;
int main()
{
long long int n,d=2,x,sol,nrdiv=1,p,nr=1,ct=0,a;
int i,j;
ifstream f(„p.in”);
ofstream g(„p.out”);
f>>n;
a=n;
for(i=3;i<1000;i+=2)ciur=1;
for(i=3;i<=1000;i+=2)
{
if(ciur)
for(j=3*i;j<=1000;j+=i)
ciur[j]=0;
}
ciur[2]=1;
while(n%2==0)
{
ct++;
n=n/2;
}
nr=nr*(ct+1);
for(i=3;i<=1000;i+=2)
{
if(i>a){break;}
ct=0;
if(ciur)
{
while(a%i==0)
{
ct++;
a=a/i;
}
nr=nr*(ct+1);
}
}
g<<nr;
}