Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Intrerupator cu N - doza doar cu ...

Incalzire casa fara gaz/lemne

Incalzire in pardoseala etapizata

Suprataxa card energie?!
 Cum era nivelul de trai cam din a...

probleme cu ochelarii

Impozite pe proprietati de anul v...

teava rezistenta panou apa calda
 Acces in Curte din Drum National

Sub mobila de bucatarie si sub fr...

Rezultat RMN

Numar circuite IPAT si prindere t...
 Pareri brgimportchina.ro - teapa ...

Lucruri inaintea vremurilor lor

Discuții despre TVR Sport HD.

Cost abonament clinica privata
 

[TEMĂ] Sortare vector după numărul de divizori

- - - - -
  • Please log in to reply
14 replies to this topic

#1
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
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
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005

Quote

for(divisor = 1; divisor * divisor <= number; divisor++)
si patratul divizorului nu depaseste un interg, fie el si pe 32 bit ?

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
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
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
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
avand modelul
Attached File  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.


#5
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
4.265 sec

#6
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
divisor * divisor <= number

divizor2 <= number

divizor <= ...... ?

#7
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
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
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
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
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
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
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
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
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
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
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
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
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
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).

#14
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 31,383
  • Înscris: 10.08.2005
cu cat anume depasesti ?

#15
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
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

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate