Znalezienie liczb o podanych kryteriach

Odpowiedz Nowy wątek
2015-01-04 23:10
0

Algorytm mam chyba dobry, bo w 1 i 2 podpunkcie miałem szukać takich "specjalnych" liczb z przedziału od 1 do 20, no i od 21 do 1000.
A w c) mam już szukać od 1001 do 1000000.. Myślałem, że to na początku zmienna, ale przecież może ona tyle pomieścić... Więc o co chodzi?
Program działa tak, jakby się nie kończył. Co trzeba poprawić? Nie mogę doszukać się błędu.

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
 
bool dzielniki(unsigned int n)
{
    for(unsigned int i=2; i<n; i++)
        {
        if(n%i==0)
            {
                if(i%3==1) return false;
            }
        }
 
return true;
}
 
int main(int argc, char** argv) 
{
    unsigned int n=0;
    unsigned int i=0;
    int a=0;
    int b=0;
    unsigned int c=0;
    int d=0;
 
    ofstream plik("zadanie4.txt");
 
//a
    for(n=2; n<=20; n++)
        {
        if(n%3==1)
            {
 
            if(dzielniki(n))
                a++;
 
            }
        }
//b 
    for(n=21; n<=1000; n++)
        {
        if(n%3==1)
            {
 
            if(dzielniki(n))
                b++;
 
            }
        }
//c 
    for(n=1001; n<=1000000; n++)
        {
        if(n%3==1)
            {
 
            if(dzielniki(n))
                c++;
 
            }
        }
 
    plik << "a) " << a << endl;
    plik << "b) " << b << endl;
    cout << c;
    return 0;
}
Int bez problemu pomieści zakres liczb z podpunktu c. - _borisov8 2015-01-04 23:15
w podpunkcie d mam do 10 000 000 więc chyba również. - Bartolinho10 2015-01-04 23:18

Pozostało 580 znaków

2015-01-04 23:18
1

Złożoność twojego algorytmu to O(n^2), a w c) masz do sprawdzenia ~1000000 liczb, więc "trochę" to potrwa.

Podaj treść zadania.

edytowany 1x, ostatnio: some_ONE, 2015-01-04 23:21
Czyli ten algorytm po prostu jest zły? - Bartolinho10 2015-01-04 23:22
@Bartolinho10 jest po prostu wolny nie koniecznie zły - rafal612b 2015-01-04 23:26
@rafal612b czyli dla zadanego problemu jest po prostu zły :P - some_ONE 2015-01-04 23:27

Pozostało 580 znaków

2015-01-04 23:22
0

ostatnią zmienną c wyrzucasz na ekranie cout zamiast zapisać do pliku ;) Jak chcesz zobaczyć na ekranie to daj getch(); żeby zatrzymać program przed zamknięciem konsoli.

edytowany 1x, ostatnio: rafal612b, 2015-01-04 23:24
Program działa tak, jakby się nie kończył. Raczej przez to nie rozumiem, żeby konsola się od razu zamykała. - some_ONE 2015-01-04 23:25
a ja myślę ze o to chodzi bo program mu nie zapisuje 3 liczby więc jest zdziwienie ze chyba się nie wykonał do końca skoro nie ma ostatniej liczby :D - rafal612b 2015-01-04 23:29
To nie myśl tylko spróbuj uruchomić ten kod co podał i zobaczysz w czym jest problem. - some_ONE 2015-01-04 23:34
Zostawiłem na dłużej i w końcu się skończył, ale wypluł zły wynik. O wiele za duży. Powinno być ponad 1000 a jest ponad 9000. - Bartolinho10 2015-01-04 23:35

Pozostało 580 znaków

2015-01-04 23:28
0

Zapisywałem do pliku, ale chciałem podglądać co się dzieje, dlatego dawałem na ekran :)
Tutaj jest zadanie --> http://kraczkowski.info/wp-co[...]2011/09/informatyka_PR_II.pdf

Pozostało 580 znaków

2015-01-04 23:31
2

Nic dziwnego bo próbujesz wykonać jakieś 2E12 dzieleń - na oko jakieś 3 godziny.
Poniżej masz zoptymalizowany twój program:

#include <iostream>
using namespace std;
 
bool dzielniki(unsigned int n)
  {
   for(unsigned i=4; i<n; i+=3) if(!(n%i)) return false;
   return true;
  }
 
int main()
  {
   unsigned n,a=0,b=0,c=0;
   ofstream fout("zadanie4.txt");
   for(n=4;n<=20;n+=3) if(dzielniki(n)) ++a;
   fout << "a) "<<a<<endl;
   for(n=22;n<=1000;n+=3) if(dzielniki(n)) ++b;
   fout << "b) "<<b<<endl;
   for(n=1003;n<=1000000;n+=3) if(dzielniki(n)) ++c;
   fout << "c) "<<c<<endl;
   return 0;
  }

ale to i tak zdecydowanie za mało, poczytaj o Sito Eratostenesa.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-04 23:42
0

A dlaczego program daje zły wynik dla c) skoro dla b i c jest dobrze. Przecież w C niczym się nie różni, tylko złożonością czasową tak jak mówicie, i tym, że ma sprawdzić więcej liczb..

Już kiedyś było tutaj to zadanie i z tego co kojarzę to tam chyba musi być błąd w odpowiedziach. - some_ONE 2015-01-04 23:45
Spoko :) Dzięki. - Bartolinho10 2015-01-04 23:47
Ale twój algorytm tak czy siak jest zły. - some_ONE 2015-01-04 23:48
Trzeba zastosować tutaj te Sito Eratostenesa? - Bartolinho10 2015-01-05 11:43

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0