[TEMĂ] Sortare vector după numărul de divizori
Last Updated: May 05 2016 21:43, Started by
sftpdt
, May 04 2016 15:14
·
0
#1
Posted 04 May 2016 - 15:14
Salut. Se dă un număr natural nenul n (1≤n≤1000) şi n numere naturale nenule (din intervalul [1,109]). Trebuie să ordonez aceste numere descrescător după numărul de divizori (dacă există mai multe numere care au același număr de divizori, acestea vor fi ordonate crescător).
Am luat o structură cu 2 câmpuri unde pentru fiecare număr am pus valoarea şi numărul de divizori, cel din urmă calculat folosind funcţia următoare: unsigned divisor_count(unsigned number) { size_t divisor, count = 0; for(divisor = 1; divisor * divisor <= number; divisor++) if(number % divisor == 0) { count++; if(divisor * divisor != number) count++; } return count; }iar sortarea folosind funcţia qsort din biblioteca stdlib.h, însă pic un test (limita de timp depăşită).
Spoiler
Edited by sftpdt, 04 May 2016 - 15:15. |
#2
Posted 04 May 2016 - 17:20
Quote for(divisor = 1; divisor * divisor <= number; divisor++) gaseste o metoda sa nu folosesti divizor * divizor, pe langa faptul mentionat mai sus pierzi din timp Edited by MarianG, 04 May 2016 - 17:38. |
#3
Posted 04 May 2016 - 20:09
Am încercat şi cu numar_divizori(n) = (a1+1)(a2+1)...(ak+1), unde a1, a2, ..., ak sunt puterile descompunerilor în factori primi ai lui n (am luat şi cazul când n e prim), însă pic 2 teste (tot limita de timp depăşită).
|
#4
Posted 04 May 2016 - 21:27
avand modelul
timp.png 31.94K 20 downloads compara care este mai eficienta ** prima valoare este pentru codul tau numar * numar ... a doua valaore este o alta metoda, tu scrie pentru metoda cu (a1+1)(a2+1)...(ak+1), vezi ce rezultate primesti Edited by MarianG, 04 May 2016 - 21:29. |
#6
Posted 04 May 2016 - 22:45
divisor * divisor <= number
divizor2 <= number divizor <= ...... ? |
#7
Posted 05 May 2016 - 13:16
sqrt(number).
unsigned square_root = (unsigned) sqrt(number); for(divisor = 1; divisor <= square_root; divisor++) { // etc } Tot depasesc limita de timp. Edited by sftpdt, 05 May 2016 - 13:16. |
#8
Posted 05 May 2016 - 13:52
pai arata-ne ce ai pus in loc de // etc
in acest for tot doua if-uri ai ? Edited by MarianG, 05 May 2016 - 13:52. |
#9
Posted 05 May 2016 - 14:52
Iniţial da, dar am modificat după şi am pus
unsigned divisor_count(unsigned number) { size_t divisor, count = 0; double square_root = sqrt(number); for(divisor = 1; divisor <= square_root; divisor++) if(number % divisor == 0) { count++; if(divisor != square_root) count++; } return count; } |
#10
Posted 05 May 2016 - 15:17
for(divisor = 1; divisor <= square_root; divisor++) { if (number % divisor == 0) { count+=1; if ( divizor != square_root) { count+=1; } } } if ( divizor != square_root)chestia aia este falsa doar la ultima iterare, practic o invoci inutil |
|
#11
Posted 05 May 2016 - 20:24
unsigned divisor_count(unsigned number) { size_t divisor, count = 0; double square_root = sqrt(number); for(divisor = 1; divisor <= square_root; divisor++) if(number % divisor == 0) count += 2; if(square_root == (int) square_root) count--; return count; } |
#12
Posted 05 May 2016 - 20:37
strict mai mic
for(divisor = 1; divisor < square_root; divisor++)radicalul il tratezi separat if ( number % square_root == 0) Nu ne-ai spus daca mai ai probleme cu "limita de timp" Edited by MarianG, 05 May 2016 - 20:39. |
#13
Posted 05 May 2016 - 20:56
unsigned divisor_count(unsigned number) { size_t divisor, count = 0; double square_root = sqrt(number); for(divisor = 1; divisor < square_root; divisor++) if(number % divisor == 0) count += 2; if(square_root == (int) square_root && number % (int) square_root == 0) count++; return count; } Pic 2 teste (limita de timp). |
#15
Posted 05 May 2016 - 21:43
Nu-mi precizează. Oricum, văd că e mai eficient dacă nu calculez sqrt.
Attached Files |
|
Anunturi
Bun venit pe Forumul Softpedia!
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users