[Pascal] liczby doskonałe

[Fritillaria]

Napisać program który sprawdzi czy podana liczba całkowita większa od 1 jest liczbą doskonałą.

Jestem skrajnie początkująca w programowaniu i chciałam zapytać co należy zrobić z moim kodem aby działał.

Kod: Zaznacz cały

program liczbadoskonala;
var l,k,suma_dzielnikow,doskonala: integer;
begin
  l:=1;
k:=doskonala;
suma_dzielnikow:=0;

while l < k do
begin
   suma_dzielnikow:=suma_dzielnikow+l+k;
   repeat
      l:=l+1;
   until (k mod l) = 0;
   k:=(k div l);
end;

if l = k then doskonala:=true;

if suma_dzielnikow <> k then writeln(doskonala:=false) ;
end. 

[SlotaWoj]

Błędy składni i wykonania:

1. Deklarujesz: var doskonala : integer;, a podstawiasz: doskonala := true;.
2. Podstawiasz k := doskonala gdy wartość prawej strony jest niezdefiniowana.
3. Nie wprowadzasz wartości sprawdzanej liczby.
4. Tak nie można: writeln(doskonala:=false).
5. suma_dzielnikow:=suma_dzielnikow+l+k; Ponieważ liczby doskonałe są sumami swoich dzielników mniejszych od niej samej, wiec do wartości początkowe sumy dzielników równej 0 nie można dodać sprawdzanej liczby.
6. Skoro później jest k:=(k div l)

   Kod: Zaznacz cały

   repeat
     l:=l+1;
   until (k mod l) = 0;
   

   Należy zmodyfikować warunek zakończenie tej pętli.[/color][/b]

[Fritillaria]

Bardzo dziękuję za pomoc, udało mi się już poprawić mój kod

[SlotaWoj]

Mój kod funkcji sprawdzającej „doskonałość” liczby jest taki:

Kod: Zaznacz cały

Function  JestDoskonala ( Liczba : longint ) : Boolean;
  var
    Dzielna        : longint;
    Dzielnik       : longint;
    SumaDzielnikow : longint;
  begin { JestDoskonala }
    Dzielna        := Liczba;
    Dzielnik       := 1;
    SumaDzielnikow := 1;
    while  Dzielnik <= Dzielna
      do
        begin
           if  Dzielnik > 1
             then
               SumaDzielnikow := SumaDzielnikow + Dzielnik + Dzielna;
           repeat
             Dzielnik := Dzielnik + 1
           until  ( Dzielnik > Dzielna ) or ( Liczba mod Dzielnik = 0 );
           Dzielna  := Liczba div Dzielnik
        end;
    JestDoskonala := SumaDzielnikow = Liczba
   end;  { JestDoskonala }

LongInt, aby można było sprawdzić liczbę 33550336 .

[ksisquare]

381185.htm#p5311699-- 12 mar 2015, o 16:26 --chyba znacznie szybszy

Kod: Zaznacz cały

function test(n:int64):boolean;
var
  pn:int64;
  m:cardinal;
begin
  m:=537036843;
  pn:=6;
  test:=false;
  repeat
    if n=pn then begin
      test:= (m and 1)=1;
      break;
    end;
    m:=m shr 1;
    pn:= (pn or (pn shl 1)) shl 1;
  until m=0;
end;

[Andreas]

Liczb doskonałych które mieszczą się w zakresie longinta jest... 5.
6,
28,
496,
8128,
33550336,
8589869056,

Robisz więc tablicę 5-elementową, i potem sprawdzasz czy wczytana liczba nie jest którąś z tej tablicy. Szybkość działania: błyskawiczna.

[SlotaWoj]

...
-- 12 mar 2015, o 16:26 --

chyba znacznie szybszy

Kod: Zaznacz cały

function test(n:int64):boolean;
{ ... }
end;

Rzeczywiście algorytm jest znacznie szybszy i byłoby super gdyby był również poprawny: zwraca pozytywny wynik testu dla liczb, które doskonałe nie są. Oto pierwsze z nich: 120, 2016, 32640, 130816, 523776, 2093128, 8386560, ...

Edit: Zamieniłem stałą 537036843 na MaxLongInt i stąd inne wyniki.

Do Andreasa: To co proponujesz jest niedydaktyczne.

[ksisquare]

a mnie wychodzi, że poprawny

[SlotaWoj]

Implementując kod podany przez KsisQuare nie analizowałem go i uznawszy stałą 537036843 za jakieś ograniczenie zmieniłem ją na MaxLongInt. Po poście ww. przywróciłem poprzednią postać tej stałej i algorytm zaczął działać zgodnie z oczekiwania. W wyniku analizy algorytmu stwierdziłem, że w stałej tej są zakodowane wykładniki \(\displaystyle{ p}\) w liczbach pierwszych Mersenne'a.

• \(\displaystyle{ m= \sum_{i}2^{p_i-1}}\)

gdzie: \(\displaystyle{ p_i}\) i \(\displaystyle{ 2^{p_i}-1}\) są liczbami pierwszymi.

W typie Int64 można zakodować jeszcze jedną liczbę Mersenne'a (dla p=61) i wtedy ta stała będzie miała wartość szesnastkową $080000002002882B.

[ksisquare]

Jeszcze jedna Mersenne'a się zmieści, ale odpowiadająca jej liczba doskonała wykracza poza zakres "wbudowanych" typów całkowitoliczbowych.
Binarna reprezentacja parzystych Doskonałych to \(\displaystyle{ p}\) jedynek i \(\displaystyle{ p-1}\) zer, wystarczy więc tablica 48 małych liczb.
Szukanie doskonałych przez rozkład na czynniki to zadanie zbyt poważne na pracę domową.

[SlotaWoj]

Przy tym kodowaniu w typie Int64 następna pierwsza liczba Mersenne'a (\(\displaystyle{ p=89}\)) się nie zmieści. Trzeba by zmienić kodowanie, np. pomijać \(\displaystyle{ p}\) , które nie są pierwsze. Tylko po co, gdy są inne ograniczenia.
Zwróć uwagę, ze w tym algorytmie nie ma żadnej operacji arytmetycznej. Można zdefiniować typ np. Int4096 i niezbędne operacje dla niego. Dla ostatniej znalezionej liczby Mersenne'a potrzebny byłby typ Int8M.
Gdyby poszukiwać nowych liczb Mersenne'a potrzebna byłaby też operacja mod, do sprawdzania pierwszości \(\displaystyle{ p}\) i dla testu Lucasa-Lehmera.

[ksisquare]

... Gdyby poszukiwać nowych liczb Mersenne'a potrzebna byłaby też operacja mod ...

Już mnożenie to spore wyzwanie

[Andreas]

Do Andreasa: To co proponujesz jest niedydaktyczne.

A dlaczego?

[SlotaWoj]

Domyślam się, że jest to zadanie z Podstaw Informatyki, w którym należy: napisać program który sprawdzi czy podana liczba całkowita większa od 1 jest liczbą doskonałą, czyli należy wykazać się umiejętnością konstruowania i implementacji algorytmu sprawdzania niebanalnego warunku matematycznego.
Ty w zamian za to proponujesz algorytm: sprawdź, czy liczba jest zawarta w tablicy.