Na programowaniu dostałem poniższe zadanie. Nauczycielka nie przyjmuje do wiadomości, że większość uczniów nie miało do czynienia wcześniej z programowaniem i chce żeby je bezwzględnie wykonać :o
Czy mógłby mi ktoś pomóc z tym zadaniem proszę o wypowiedzi tylko osoby znające się na tym
Postaraj się zaimplementować algorytm przedstawiony np. tutaj:
http://pl.wikipedia.org/wiki/Liczba_doskona%C5%82a
i pochwal się nim, wtedy pomożemy. Jest tam wyraźnie napisane, jaka jest postać liczby doskonałej i że kluczem do jej obliczenia jest znajomość liczb pierwszych. Do znalezienia liczb pierwszych możesz zastosować np. sito Eratostenesa (pewnie są szybsze algorytmy).
Pascala nie znam, ale w Pythonie to by było coś takiego (napisane w 5 minut więc się nie czepiać :D)
def znajdz_liczby_doskonale(od, do):
for n in range(od, do+1):
m = 0
for k in znajdz_dzielniki(n):
m = m + k
if m == n:
print "%d - liczba doskonala" % (n)
def znajdz_dzielniki(liczba):
dzielniki = []
for n in range(1, int(liczba/2)+1):
if ((liczba % n) == 0):
dzielniki.append(n)
return dzielniki
znajdz_liczby_doskonale(1, 10000)
wynik:
6 - liczba doskonala
28 - liczba doskonala
496 - liczba doskonala
8128 - liczba doskonala
następna liczba doskonała wynosi już 33 550 336 więc tym algorytmem w rozsądnym czasie jej nie znajdziesz
Jeśli chodzi o sito Eratostenesa to to ponoć mniej więcej wygląda tak w języku pascala
program Eratostenes;
var
liczby: array [2..64000] of boolean;
n: longint;
procedure Zakoncz;
{ wypisanie listy liczb pierwszych i zakończenie programu }
var
i: longint;
begin
for i:=2 to n do
if liczby[i] then write(i:8);
writeln;
halt
end;
var
k, m: longint;
begin
write('Podaj n: ');
read(n);
for k:=2 to n do
liczby[k] := true;
k := 2;
while true do
begin
m := 2*k;
while m <= n do
begin
liczby[m] := false;
m := m + k
end;
repeat
k := k+1;
if k > n then
Zakoncz;
until liczby[k]
end
end.
A z tą liczbą doskonałą znalazłem coś takiego
program doskonale;
uses crt;
var
i,n,z: longint;
begin
clrscr;
j := 0;
write('Podaj gorna granice przedzialu: ');
readln(n);
for z:=1 to a do
begin
for i:=1 to z div 2 do
begin
if z mod i = 0 then
begin
j := j+i;
end;
if j = z then begin write (z,' '); end
end;
end;
readln;
end.
ale chyba jest błędny. BO to miało wyglądać niby tak. że w programie ma się pojawić okno w którym się wpisuje liczbę, i program ma właśnie wyświetlić liczby doskonałe od “0” do wpisanej wartości.
Jak dla mnie to trochę za dużo jak na początek programowania #-o
Nie rozumiem o czym wy tu mówicie.
Sito Eratostenesa niewiele tu pomoże, bo trzeba zsumować wszystkie podzielniki czyli zastosować wszystkie kombinacje iloczynów liczb pierwszych na którą ta liczba się dzieli.
Czyli np liczba 210=2*3*5*7, ale to za mało zsumować 1+2+3+5+7, trzeba jeszcze dołożyć 2*3,2*5,2*7,2*3*5,2*3*7 i td.
w sumie jeszcze 10 podzielników.
Jedyny słuszny algorytm (jak się wydaje na pierwszy rzut oka) to:
sumę zacząć od 1 (aby nie sprawdzać podzielności przez 1)
w przedziale D - Liczba/2 do 2 (z odrzuceniem reszty)
2.1. sprawdzać czy Liczba dzieli się przez D jeżeli tak to dołożyć D do sumy
2.1.1. jeżeli po dodaniu Suma>Liczba to można przerwać pętle.
Dużo oszczędniej byłoby:
2.1. sprawdzać czy Liczba dzieli się przez D jeżeli tak to dołożyć (D + (Liczba div D)) do sumy
Przykład: dla Liczba = 10000 zamiast maksymalnie 5000 operacji modulo, wykona tylko 100.
Taka jest definicja liczby doskonałej.
Tylko jak to w praktyce zastosować w pascalu.
Ciekawe czy nauczycielka doczepiłaby się gdybym zastosował, że jeśli liczba mniejsza równa 6 to wynik jest 6, jeśli mniejsza równa 28 to wynik 6, 28. Ale tu nie o to chodzi to algorytm sam ma pokazywać wynik tej operacji
prz3mo podał poprawny kod w Pythonie (przecież to nie Lisp), alex go opisał. Jedyne, co Ty zrobiłeś to wygooglałeś sito Erastotenesa i jakiś algorytm na liczby doskonałe. Jakby chciało Ci się choć trochę pomyśleć, to już byś dawno to napisał, bo w tym wątku powiedziano już wszystko, czego potrzebujesz.
BTW: To, co próbujesz zrobić nazywa się tablicowaniem (czasem się przydaje), ale Ty masz napisać algorytm.
Spoko, ale ja jeszcze wcześniej nie miałem do czynienia z programowaniem a mam napisać w Delphi pascsalu 7 program który znajduje wszystkie liczby doskonałe w przedziale (1, a)
Więc początki są trochę trudne i jeszcze się trochę gubię.
program doskonale;
function czy_doskonala(Liczba : longint) : boolean;
{ funkcja sprawdza, czy dana liczba jest doskonala.
zwraca odpowiednia wartosc logiczna }
var
Suma_dzielnikow, N, P : longint;
begin
if Liczba < 2 then { liczby mniejsze od 2 nie sa doskonale }
czy_doskonala := false
else
begin
Suma_dzielnikow := -Liczba; { male oszustwo, zeby for byl zawsze poprawnie okreslony }
{
Dla wszystkich N z przedzialu (1, P), gdzie P := trunc(sqrt(Liczba))
Jezeli N dzieli Liczbe (bez reszty, czyli ((Liczba mod N) = 0)) to
Suma_dzielnikow := Suma_dzielnikow + N + (Liczba div N)
(zawauzmy, ze jesli N dzieli Liczbe,
to (Liczba div N) takze dzieli Liczbe, wiec za kazdym razem
mozemy dodac az dwie liczby do sumy. Jeśli Liczba rozklada sie na iloczyn
dwoch liczb p, q i p <= q to zawsze p <= sqrt(Liczba) oraz q >= sqrt(Liczba)
Zastanow się, dlaczego obydwie jednoczesnie nie moga byc mniejsze albo wieksze od pierwiastka.
Dlatego wlasnie wystarczy, ze znajdziemy wszystkie liczby p <= sqrt(Liczba))
Jezeli Suma_dzielnikow > Liczba to
przerwij petle, np. break; (czesciowa suma wyszla za duza, i nie zanosi sie na to, zeby zmalała)
zwroc Suma_dzielnikow = Liczba
}
end;
end; { czy_doskonala }
var
N, i : longint;
begin
writeln('Podaj gorne ograniczenie liczb doskonalych');
readln(N);
for i := 1 to N do
if czy_doskonala(i) then
write(i, ' ');
writeln;
end.
Tu jest cały schemat programu, wystarczy że przepiszesz komentarz w funkcji czy_doskonala na kod Pascala.
Dobra dzięki, teraz powinienem sobie poradzić 8)
No jak to nie pomoże 
jak pomoże… Wziąłem algorytm na sito z wikipedi i podmieniłem jedną linijkę kodu (minuta roboty), teraz wypisuje mi po kolei liczby doskonałe dla kolejnych liczb pierwszych… 6, 28, 496, 8128 etc…
const int n = 15;
bool numbersTable[n + 1]; // tablica o indeksach od 0 do 100 | wszystkie false (czyli: 0);
int main(int argc, char* argv[])
{
for (int i = 2; i*i <= n; i++ ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie są liczbami pierwszymi
{
if (numbersTable[i] == true) // jeżeli dana liczb jest już wykreślona
continue; // to przejdź do kolejnej
for (int j = 2 * i ; j <= n; j += i) // przejdź od liczby 2 * i do n przesuwając się o i
numbersTable[j] = true; // i każdą z nich usuwaj ze zbioru
}
cout << "Liczby pierwsze z przedziału od 0 do " << n << ":" << endl;
for (int i = 2; i <= n; i++) // przeszukaj liczby od 2 do n
if (numbersTable[i] == false) // jeśli liczba nie została usunięta ze zbioru
{
int n = (pow(2,i)-1)*pow(2,i-1);
cout << n << endl; // to ją wypisz
}
system("PAUSE");
return 0;
}
Oczywiście jest trochę naddatku obliczeniowego, ale da się to przecież zoptymalizować. Pozdrawiam.
gregus , i w czym to pomogło?
Czy przeczytałeś chociażby nazwę tematu?
alex , lubię twoje posty ale teraz to nie wiem o co Ci chodzi… Przecież “mój” program liczy to o co prosił autor na początku, tylko trzeba zawęzić działanie sita żeby zlikwidować naddatek obliczeniowy. Życzę dobrej nocy.
Fakt że i jest pierwsze nie gwarantuje, że pow(2,i)-1 jest liczbą pierwszą (Mersenna), więc nie musi być doskonała (np. dla i = 11). Dlatego należy dorzucić jeszcze test pierwszości (1<
BTW: Nie wiem, czy ten algorytm można uznać za poprawny w ogóle. Dlaczego? Otóż zakłada on nieistnienie nieparzystych liczb doskonałych. Wiem, wiem… to jak z tą inteligentną blondynką, ale pewności nie ma.
W tym, że zap… jak należy. Na piątą liczbę doskonałą zamiast godziny czekasz kilka milisekund.
Więc tak udało mi się napisać ten program lecz mam pewien problem z jego działaniem po wpisaniu liczb które miały jeszcze dołożyć wynik 33550336, 8589869056 i 137438691328.
Czeka się strasznie długo nie wiem czy jest może jakiś sposób na skrócenie działania ?
dołączam kod w konsoli
program Doskonale;
{$APPTYPE CONSOLE}
Var
Suma,Liczba,Mozliwosci:LongInt;
a : integer;
Begin
write('Podaj liczbe calkowita a: ');
readln(a);
writeln('Liczby doskonale od 1 do a:');
For Liczba:=1 to a do
Begin
Suma:=0;{Poczatkowa wartosc sumy=0}
Mozliwosci:=0; {ustala wstepna wartosc mozliwosci.. dzielenie przez wszystkie liczby od 1
do 1 mniej niz podana liczba}
While Mozliwosci< Liczba-1 do
Begin
Inc(Mozliwosci); {zwiekszenie zmiennej mozliwosci o 1}
if Liczba mod Mozliwosci=0 then
Suma:=Suma+Mozliwosci;{dodajemy dzielniki}
end;
If Suma=Liczba then write(Liczba,',');
End;
writeln('wcisnij < Enter> , aby kontynuowac...');
readln;
End.
A wie może ktoś z was jak sprawdzić czas działania? (chodzi mi żeby program sam odliczał jak długo pracował)