Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Ciurul lui Eratostene  (Citit de 4615 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« : Ianuarie 30, 2008, 19:34:28 »

Vreau sa intreb daca nu ar fi mai corect ca in a patra si a cincea bucata de cod, conditia de oprire a primului for sa fie ((i*i)<<2)+(i<<2)+1<=n in loc de ((i*i)<<1)+(i<<1)<=n? De la (2*i+1)2.
Asta de mai jos ar fi bucata a 4 din articol:

Cod:
//class PrimeNumbersSieve4   
final int MAXSIZE = 1000000/2+1;   
char[] p = new char[MAXSIZE];   
 
//p[i] == 0 if 2*i + 1 is prime   
 
public int getTheNumber(int n) {   
  int i, j, nr = 1;   
  for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1) {   
    if (p[i] == 0) {   
      for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1) {   
        p[j] = 1;   
      }   
    }   
  }   
  for (i=1; 2 * i + 1 <= n; ++i)   
      if (p[i] == 0) nr++;   
  return nr;   

P.S. Problema(Patcas Csaba) : Sa se numere toti bitii egali cu 1 din reprezentarea binara a numerelor de la 1 la n? O(n)
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #1 : Ianuarie 30, 2008, 19:57:24 »

La prima intrebare:
 
((i*i)<<2) inseamna 4i^2     ... (a<<b) inseamna a*(2^b)

Later Edit: (Never mind explicatia de mai sus Tongue) da cred ca e bine cum zici ... ecorect in ambele feluri... e mai optim cum zici tu

La pb cu numarul de biti egali cu 1 din reprezentarea binara a numerelor de la 1 la n in O(n):
1) precalculez a[ i ] ( i=1, 2^16) a[ i ]=nr de bitii al numarului i. Asta se poate face in O(T log T)
   sau  in O(T) (T=2^16) cu memoizare ( ceva in genul codului gray ... din i ma duc in j unde j are un bit de 1 mai putin decat i)

2) pentru i=1 la n
         sol+=a[i %(1<<16)] + a[i>>16]; // O(n)

Sau poti aplica memoizarea pt intregul sir dar s-ar putea sa fie mai lent datorita recursivitatii.
« Ultima modificare: Ianuarie 30, 2008, 21:38:09 de către Mircea Dima » Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #2 : Ianuarie 31, 2008, 14:21:35 »

!.credeam ca am gresit ceva
2. Cam complicata rezolvarea ta... daca n e un milion si timp 0.1 sec..

Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #3 : Ianuarie 31, 2008, 14:32:13 »

P.S. Problema(Patcas Csaba) : Sa se numere toti bitii egali cu 1 din reprezentarea binara a numerelor de la 1 la n? O(n)

Relatiile astea ar trebui sa fie suficiente:

Cod:
v[0] = 0;
v[i*2] = v[i];
v[i*2+1] = v[i]+1;

Problema poate fi rezolvata si in O(log N). Probabil ca se poate si mai bine, insa o rezolvare de complexitate mai buna nu imi vine acum in minte.
« Ultima modificare: Ianuarie 31, 2008, 15:21:17 de către Andrei Grigorean » Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #4 : Ianuarie 31, 2008, 15:08:30 »

sunt suficiente
poti sa-mi9 zici in logn
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #5 : Ianuarie 31, 2008, 15:29:30 »

Scrii numarul N in baza 2. Vei obtine o configuratie de M (M = log N) biti. De exemplu pentru N = 25, vei obtine M = 5, iar configuratia va arata asa:

Cod:
Bit[4] = 1;
Bit[3] = 1;
Bit[2] = 0;
Bit[1] = 0;
Bit[0] = 1;

Vrei sa vezi pentru fiecare pozitie i (0 <= i < M) de cate ori va aparea 1 in scrierea tuturor numerelor de la 1 la N.
Notam cu Left[ i ] numarul format de Bit[M-1], Bit[M-2], ... , Bit[i+1], iar cu Right[ i ] numarul format de Bit[i-1], Bit[i-2], ... , Bit[0]. In exemplul de mai sus, pentru i = 2, Left[2] = 3, iar Right[2] = 1. Numarul de aparitii ale lui 1 pe pozitia i in scrierea tutror numerelor de la 1 la N este:

Cod:
R[i] = Left[i] * 2^i + (Bit[i] ? (Right[i]+1) : 0).

Raspunsul cautat este suma de R[ i ].
« Ultima modificare: Februarie 01, 2008, 21:42:26 de către Andrei Grigorean » Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #6 : Februarie 01, 2008, 13:22:30 »

Cod:
//Left[i] in loc de left[i]-1;
se adauga la ce ai zis tu cazul cu 000...0.  Very Happy
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #7 : Februarie 01, 2008, 21:19:45 »

Da, asa e Smile.
« Ultima modificare: Februarie 01, 2008, 21:42:00 de către Andrei Grigorean » Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
DanielG
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 10



Vezi Profilul
« Răspunde #8 : Februarie 26, 2008, 18:31:17 »

Cod:
public static void main(String[] arg) {   
  double tick = System.currentTimeMillis();   
  for (int i = 0; i < 10; ++i) {   
    System.out.println("Run " + i   
  + " result: "+   
    new PrimeNumbersSieve1().   
    getTheNumber(1000000));   
  }   
  System.out.println(" 10 runs of " 
+ "PrimeNumbersSieve1()."   
+ "getTheNumber(1000000) "   
+ "lasted: "   
+ (System.currentTimeMillis()   
- tick)   
* 1e-3 + " seconds");   



Poate cineva sa scrie acest algoritm in Pascal sau pseudocod? Smile Multumesc!
Memorat
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #9 : Februarie 20, 2009, 02:09:13 »

Discutiile pot continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3682.0
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines