[Delphi] Liczby zaprzyjaźnione


(Marcin8004) #1

Cześć,

potrzebuję pomocy przy tworzeniu aplikacji w Delphi XE2 na zajęcia z programowania. Mam problem z algorytmem na sprawdzanie liczb zaprzyjaźnionych z zakresu 1 -> max (wprowadzony przez użytkownika) i wyświetlanie ich w ListBoxie.

Program wyświetla mi wszystkie liczby, które sprawdził, zamiast tych które są parami wzajemnie zaprzyjaźnionymi. Pomożecie?

unit zadanie;

    interface

    uses
      Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
      Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

    type
      TForm1 = class(TForm)
        Label1: TLabel;
        Edit1: TEdit;
        Label2: TLabel;
        Edit2: TEdit;
        Label3: TLabel;
        Button1: TButton;
        Button2: TButton;
        ListBox1: TListBox;
        procedure Button1Click(Sender: TObject);
      private
        { Private declarations }
      public
        { Public declarations }
      end;

    var
      Form1: TForm1;

    implementation

    {$R *.dfm}

    procedure TForm1.Button1Click(Sender: TObject);
    var
      liczba1,liczba2,maks,temp,i:Integer;
      k,q:Boolean;
    begin
      maks:=StrToInt(Edit1.Text);
      for liczba1:=200 to maks do
      begin
        for liczba2:=200 to maks do
          begin
            temp:=0;
            for i:=1 to (liczba1 div 2) do if ((liczba1 mod i)=0) then temp:=temp+i;
            if (temp=liczba2) then q:=true else q:=false;
            temp:=0;
            for i:=1 to (liczba2 div 2) do if ((liczba2 mod i)=0) then temp:=temp+i;
            if (temp=liczba1) then k:=true else k:=false;
            if (k=true and q=true) then Listbox1.Items.Add(IntToStr(liczba1)+' '+IntToStr(liczba2));
          end;
      end;
    end;
    end.

(Marcin Obala) #2

Pierwsze co mi się rzuca w oczy to for liczba2:200. Zaczynasz od 200 a nie od 1. Przepisałem ten kod do C# i w miarę działa, choć pokazuje też liczby które są identyczne np. 28 28, 6,6 ale to wystarczy dodać w ostatnim ifie liczba1<> liczba2. Chyba że przepisując do C# udało mi się ominąć jakiś mechanizm języka delphi. Poniżej mój kod, który działa w C#, napisałem go tak żeby wyglądał praktycznie identycznie jak Twój.

private void button1_Click(object sender, EventArgs e)
        {
            int maks = 300;
            int liczba1, liczba2, temp, i;
            bool k, q;
            for (liczba1 = 1; liczba1 <= maks; liczba1++)
            {
                for (liczba2 = 1; liczba2 <= maks; liczba2++)
                {
                    temp = 0;
                    for (i = 1; i <= liczba1/2; i++) if (liczba1%i == 0) temp = temp + i;

                    if (temp == liczba2) q = true; else q = false;

                    temp = 0;
                    for (i = 1; i <= liczba2/2; i++) if (liczba2%i == 0) temp = temp + i;

                    if (temp == liczba1) k = true; else k = false;

                    if (k==true && q==true && liczba1 != liczba2)
                        listBox1.Items.Add(liczba1.ToString() + " " + liczba2.ToString());
                }
            }
        }

(system) #3

Przeczytaj:

http://pl.wikibooks.org/wiki/Object_Pascal/Typy_zmiennych

 

Nima reszty z dzielenia jeśli zmienna jest Integer, więc zawsze = 0

 

for i:=1 to (liczba1 div 2) do if ((liczba1 mod i)=0)


(Pablo_Wawa) #4

Kilka uwag optymalizacyjnych do powyższego programu:

  1. Druga instrukcja for

    for liczba2:=200 to maks do

nie musi i nie powinna odliczać od 200, tylko od liczba1+1

for liczba2:=liczba1+1 to maks do

przez co i przyspieszysz algorytm, jak i unikniesz dwóch “problemów”: dublowania tej samej liczby i powtarzania danej pary (raz byłoby 220 i 284, drugi raz miałeś 284 i 220) - teraz będziesz miał posortowane pary.

 

  1. Zamiast konstrukcji

    liczba1 div 2

można użyć (z reguły szybszej) takiej (przesunięcia bitowego)

liczba1 shr 1

Przydatne w niektórych językach, nie mających dzielenia całkowitoliczbowego (jak np. JavaScript).

 

  1. Zamiast konstrukcji

    if (temp = liczba1) then k := true else k := false;

prościej jest zastosować taką

k := (temp = liczba1);
  1. Podobne uproszczenie możesz (a nawet powinieneś) zastosować dla kodu

    if (k=true and q=true)

poprzez taki

if (k and q)

(Marcin8004) #5

Bardzo dziękuję Wam za wszystkie wskazówki. Algorytm działa tak jak powinien. Nie zastosowałem jednak rady z zamianą div na shr, ponieważ nie było żadnego efektu przy zmiennych typu Integer i LongInt. Div współpracował dopiero z LongInt.

Pozdrawiam!

 

Kod dla potomnych :slight_smile:

procedure TForm1.Button1Click(Sender: TObject);
var
      maks,temp,i:Integer;
      liczba1,liczba2:LongInt;
      k,q:Boolean;
    begin
      maks:=StrToInt(Edit1.Text);
      for liczba1:=1 to maks do
      begin
        for liczba2:=liczba1+1 to maks do
          begin
            temp:=0;
            for i:=1 to (liczba1 div 2) do if ((liczba1 mod i)=0) then temp:=temp+i;
            q:=(temp=liczba2);
            temp:=0;
            for i:=1 to (liczba2 div 2) do if ((liczba2 mod i)=0) then temp:=temp+i;
            k:=(temp=liczba1);
            if (k and q) then Listbox1.Items.Add(IntToStr(liczba1)+' '+IntToStr(liczba2));
          end;
      end;
    end;
end.

(Pablo_Wawa) #6

@everest8004: tak jest oczywiście bardzo dobrze, ale pierwszą instrukcję for

for liczba1:=1 to maks do

mógłbyś pozostawić taką, jak miałeś na początku, czyli

for liczba1:=200 to maks do

ponieważ - za Wikipedią http://pl.wikipedia.org/wiki/Liczby_zaprzyja%C5%BAnione - najmniejszą liczbą, jaka może wchodzić w grę (jako liczba zaprzyjaźniona), jest 220. Dzięki temu zaoszczędzisz trochę “niepotrzebnych obrotów” pętli for, choć i tak nie ma to znaczenia przy obecnych szybkościach procesorów ( i może to z jedynką jest bardziej “eleganckie”, bo nie bazuje na znanych już wynikach ).


(Marcin8004) #7

Właśnie tym faktem, iż pierwsza liczba to 220, kierowałem się gdy wstawiłem tam 200. Jednak stwierdziłem, że to i tak nie robi różnicy w wydajności algorytmu i zmieniłem to na niewinne 1, bardziej eleganckie - tak jak to ująłeś.

 

Jeszcze raz dziękuję za pomoc i pozdrawiam!


(martyna2897) #8

Witajcie. Program przy ustawieniu zakresu większego od 10000 przestaje działać. W czym może tkwić problem?