Projekt C++

TESLA · Napísal **TESLA**: 22.10.2011 17:38

cavte mam za ulohu naprogramovat Eratosthenovo sito- Program na vypísanie prvočísel co som aj spravil, no ucitel mi povedal aby som to upravil tak aby to pracovalo aj s velmi velkymi cislami (
take,ktore sa nevmestia do ziadnej atomickej premennej)

Kód:

#include <iostream>
#include <math.h>
#include <stdlib.h> 

using namespace std;

/** 
* horna hranica intervalu v ktorom budu hladane prvocisla
*/
long double N;    
               
/**
* Nastavi vsetky prvky pola na hodnotu true 
* @param p je pole typu bool  ktore vstupuje do funkcie
* @param n je velkost vstupujuceho pola
*/
void Nastav(bool p[], int n)
{
     for (int i = 0; i <= n ; i++) 
            p[i] = true; 
}

/**
* Prvky pola ktore niesu prvocisla nastavi na false
* @param p je pole typu bool ktore vstupuje do funkcie
* @param n je velkost vstupujuceho pola
*/
void IbaPrvo(bool p[], int n)
{
   for (int i = 2; i <= (int) sqrt((double)n); i++) 
   {
      int k = i * i;
      while (k <= n) 
      {
         p[k] = false;          
         k += i;
      }
   }       
}


/**
* Na obrazovku vypise len prvocisla cize indexy prvkov pola na ktorych je ulozena logicka jednotka
* @param p je pole typu bool ktore vstupuje do funkcie
* @param n je velkost vstupujuceho pola
*/
void VypisPrvo(bool p[], int n)
{
     for (int i = 2; i <=n; i++)
         if (p[i]) cout << i << " \n";         
}


/**
* funkcia main je hlavna funkcia
*/
int main()                                          
{   
   cout << "Eratosthenovo sito" << endl;
   cout << "\nZadejte hornu hranicu intervalu: "; 
   cin >> N;
   
/** 
* alokacia celeho pola bool hodnot o velkosti zadefinovanej uzivatelom
*/                  
   bool *pole = new bool[N];       
      
   Nastav(pole, N);     
   IbaPrvo(pole, N);
   VypisPrvo(pole, N);
   system("pause");
   return 0;
}

Vedel by mi s tym niekto pomoct ? vdaka

Fico · Napísal **Fico**: 23.10.2011 11:20

RollOrDie píše:

take,ktore sa nevmestia do ziadnej atomickej premennej

Ani do typu long double? Lebo to by si potom nemohol pouzit ani funkciu sqrt. Este som si vsimol v tvojom kode drobnu chybu, kde zapisujes za pole:

Kód:

bool *pole = new bool[N];
Nastav(pole, N);

Pole je velkosti N a to davas ako argument funkcie Nastav ( a ostatnych dalsich ). Pole ma ale hranice <0, N-1> cize v kazdej z tvojich troch funkcii pracujes aj N-tym prvkom. Oprava:

Kód:

void Nastav(bool p[], int n)
{
     for (int i = 0; i < n ; i++)
            p[i] = true;
}

void IbaPrvo(bool p[], int n)
{
   for (int i = 2; i <= (int) sqrt((double)(n-1)); i++)
   {
      int k = i * i;
      while (k < n)
      {
         p[k] = false;
         k += i;
      }
   }
}

void VypisPrvo(bool p[], int n)
{
     for (int i = 2; i < n; i++)
         if (p[i]) cout << i << " \n";
}

A este dalsia vec, v C++ by sa na explicitne pretypovanie malo pouzivat klucove slovo static_cast miesto C-ckovskeho (novyTyp). Nie je to sice chyba, ale podla konvencie by to tak malo byt. Ak teda chces, zmen si riadok:

Kód:

for (int i = 2; i <= (int) sqrt((double)(n-1)); i++)

na

Kód:

for (int i = 2; i <= (int) sqrt( static_cast<double>(n-1) ); i++)

// ak ste to v skole nebrali, tak to nechaj tak

TESLA · Napísal autor témy **TESLA**: 23.10.2011 11:48

vdaka za opravene chyby....a neviem co si podtym "take,ktore sa nevmestia do ziadnej atomickej premennej" ....takze asi ani long double...vobec ma nenapada ako by sa to dalo spravit ://

Fico · Napísal **Fico**: 23.10.2011 13:23

Spytaj sa ucitela, aspon nejake informacie ti musi dat. Mna narychlo napada len jeden sposob uchovania vacsich cisel a to v poli znakov, ale realizovat odmocninu na taketo nieco si teda ozaj neviem predstavit. Long double je dost velke cislo, tak neviem, co presne od vas ocakava ucitel, ci nejaky neobmedzeny algoritmus, alebo tam je povolena nejaka hranica.

chrono · Napísal **chrono**: 23.10.2011 16:57

1. Používať float/double... tam, kde sa očakáva celé číslo nie je príliš rozumné (pretože napr. 3 môže byť v skutočnosti 2.99999999999 a teda v podstate 2).

2. Je otázne, či má zmysel trápiť sa s veľkosťou N, pretože do pamäte sa aj tak nezmestí dosť veľké pole prvkov typu bool. Samozrejme mohol by si tam namiesto bool používať jednotlivé bity, takže by sa tam toho zmestilo 8 krát viac, ale na 32 a aj 64 bitovej platforme by na to hravo stačilo nejaké 64 bitové číslo. Takže tiež odporúčam opýtať sa, čo je myslené tými veľmi veľkými číslami.

Projekt C++

Podobné témy