[Delphi] Liczby Mersenne'a

jf98151
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 7 sty 2021, o 15:05
Płeć: Mężczyzna
wiek: 29

[Delphi] Liczby Mersenne'a

Post autor: jf98151 » 7 sty 2021, o 15:17

Witajcie, jestem studentem pierwszego roku informatyki na PP, mam pierwsze zadanie z Delphi, zrobić schemat blokowy i napisać program. Nigdy wcześniej nie programowałem i nie tworzyłem schematu blokowego. Czy jesteście w stanie dać mi jakieś wskazówki jak zrobić prawidłowo schemat oraz napisać program do tego zadania?

zadanie:
"Liczba Mersenne'a to liczba pierwsza postaci \(\displaystyle{ 2p - 1}\), przy czym \(\displaystyle{ p}\) samo jest liczbą pierwszą. Napisać program znajdujący \(\displaystyle{ k}\) takich liczb.
Wskazówka. W programie wprowadzamy liczbę \(\displaystyle{ k > 0}\), po czym wypisujemy \(\displaystyle{ k}\) znalezionych liczb."
Ostatnio zmieniony 7 sty 2021, o 15:30 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Ponury123
Użytkownik
Użytkownik
Posty: 98
Rejestracja: 5 lip 2015, o 14:48
Płeć: Mężczyzna
Lokalizacja: nie wiem
Podziękował: 10 razy
Pomógł: 14 razy

Re: Pierwsze kroki w Delphi

Post autor: Ponury123 » 7 sty 2021, o 17:13

Zrób pętle, w której będziesz iterował po kolejnych liczbach całkowitych tak długo, aż nie znajdziesz zadanej ilości liczb spełniających podany warunek.

Pseudo kod:

Kod: Zaznacz cały

int number = 2;
int counter = 0;
int k; //get k

while(counter < k){
   if(isMersennePrime(number){
      counter++;
   }
   number++;
}

Jedyna trudność leży w dobrze napisanym warunku sprawdzającym czy liczba jest liczbą Mersenne'a.

Edit: jako że na chwilę obecną znamy zaledwie 51 takich licz, to nie byłoby głupim pomysłem zahardkodowanie tych licz w jakiejś tablicy, a następnie wyświetlanie odpowiedniej ilości z nich w zależności od podanego K. Nie jest to rozwiązanie zapewne, którego oczekuje prowadzący, ale ma dużą zaletę, mianowicie -> działa i działa do tego szybko. A to dlatego, że liczby te rosną bardzo szybko i powyższy pseudo kod, który Ci przedstawiłem bardzo szybko przestałby działać, ponieważ po pierwsze mamy tutaj do czynienia z bardzo dużymi liczbami więc i typy zmiennych powinny być do takich przystosowane, po drugie ta pętla choć nieskończona nie jest to jej iteracje mogą potrwać bardzo długo, to tego z tego co przeczytałem na wikipedii nie ma informacji czy takich liczb Mersenne'a jest nieskończenie wiele, a co za tym idzie możliwe jest podanie takiego k, dla którego nasza pętla stanie się nieskończona.

Plus założyłem, że podana przez Ciebie definicja tych właśnie liczb jest błędna, a ich prawidłowa definicja powinna wyglądać tak:

\(\displaystyle{ M_{p}= 2^{p}-1 }\)
gdzie p jest liczbą pierwszą.

jf98151
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 7 sty 2021, o 15:05
Płeć: Mężczyzna
wiek: 29

Re: [Delphi] Liczby Mersenne'a

Post autor: jf98151 » 14 sty 2021, o 12:15

Dziękuję za odpowiedź. Siadam dziś do zadania, muszę przygotować je w formie okienkowej. Dodatkowo ewidentnie mam problem jak dobrze zrobić schemat blokowy do tego zadania, jak prawidłowo go narysować.

Ponury123
Użytkownik
Użytkownik
Posty: 98
Rejestracja: 5 lip 2015, o 14:48
Płeć: Mężczyzna
Lokalizacja: nie wiem
Podziękował: 10 razy
Pomógł: 14 razy

Re: [Delphi] Liczby Mersenne'a

Post autor: Ponury123 » 14 sty 2021, o 12:38

Wikipedia podaje dokładny opis elementów w schemacie, istnieje też sporo stronek przekształcających kod/pseudokod na graficzną reprezentację. Linku do strony nie podaję bo nie wiem czy moderator nie uznałby tego za kryptoreklamę. Jak wyszukasz coś w stylu "block schema from code", "code to diagram block" czy coś w tym guście to z pewnością znajdziesz.

Wracając do samego zadania, to nie wiem czy dobrze mnie zrozumiałeś, realizacja programu, który w sposób zadowalający(czasowo np.) wykonuję podane założenia jest bardzo trudnym zagadnieniem(zakładając, że nie hardkodujemy znanych wartości, tylko liczymy na bieżąco). Jesteś na pierwszym roku, więc pewnie podany przeze mnie pseudokod wystarczy, jednak jeśli chcesz podejść do zadania ambitnie to proponuję zagłębić się w literaturę i sprawdzić jakich algorytmów użyto do obliczania tych liczb, jak zostały skonstruowane i jak działają. Tutaj pozostaje oczywiście kwestia sporna, czyli czy pracę w całkowicie odtwórcą uznajemy za wartościową, czyli czy napisanie(przepisanie) programu bazując na gotowym kodzie uznajemy za coś ok.

Osobiście uważam, że jeśli napisałbyś swoją implementację któregoś z algorytmów wykorzystanych do obliczenia którejś z tych liczb, bez żadnej modyfikacji tegoż algorytmu to i tak będzie to podejście godne pochwały - zważywszy, że to Twój pierwszy rok.

jf98151
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 7 sty 2021, o 15:05
Płeć: Mężczyzna
wiek: 29

Re: [Delphi] Liczby Mersenne'a

Post autor: jf98151 » 14 sty 2021, o 12:48

Wszelkie słowa, które napisałeś są bardzo pomocne. Oczywiście nie poszedłem na studia tylko po to by robić kopiuj wklej, gdyż prędzej czy później takie postępowanie zostanie zweryfikowane. Problemem okazuje się forma studiów i pozostawieniem nas z zadaniami. Oglądam filmy, czytam ale prawda jest taka, że dopóki nie zapytam to pewnych rzeczy nie zrozumiem. Oczywiście planuję podziałać sam na kodzie.

Pozdrawiam

ksisquare
Użytkownik
Użytkownik
Posty: 132
Rejestracja: 1 cze 2012, o 07:04
Płeć: Mężczyzna
Lokalizacja: Polska
Pomógł: 15 razy

Re: [Delphi] Liczby Mersenne'a

Post autor: ksisquare » 14 kwie 2021, o 02:33

Może się przyda

Kod: Zaznacz cały

var
  p, i, n: longword;   //32 bity
  s, n1: int64;      //64 bity

begin
  p:=2;
  n:=3;  // n  = 2^p - 1
  n1:=2; // n1 = 2^(p-1)
         // n1*n może być liczbą doskonałą
  repeat
    s:=4;                   // 1. Lucas-Lehmer test
    for i:=3 to p do        // 2. 
      s:=(s*s - 2) mod n;   // 3. 
    if (s=0) or (p=2) then  // 4. 

       writeln('Mersenne=2^', p:2, '-1=', n:12, ',  perfect number = ', n1*n);
    p+=1;
    n1:=n+1;
    n:=2*n+1;
  until p>31;
end.[/icode]

ODPOWIEDZ