NWD dla dużych liczb.

0

Witam. Mam do napisania program który obliczy nwd z bardzo dużych liczb(do 100 cyfr).Nie mogę użyć funkcji systemowych tylko muszę napisać swoje. Wykombinowałem to tak:

  1. Wczytuję liczby z pliku do listboxów( listbox_a- pierwsza liczba, listbox_b - druga liczba).
  2. Liczby trzymam w zmiennej string. Czyli w tablicy charów.
    3.Napisałem funkcję która sprawdza czy a>b.
  3. Algorytm obliczania Nwd wygląda tak:
while (a<>b) do begin

    if (porownaj(a,b)=True) then
       a:=odejmij(a,b)
    else
       b:=odejmij(b,a);  
  1. Teraz potrzebuję funkcję która odejmie od siebie dwie liczby w formacie string w najbardziej wydajny sposób.

Pytania:
a) czy operacje lepiej wykonywać na tablicy charów czy lepiej wprowadzić to do tablicy integer?
b) Jak sprawdzić długość tablicy? Gdy wpiszę setlength(tablica,20) to elementy będą numerowane od 1 do 20?
c) jak prościej napisać ten program?

0
  1. Operuj na 32-bitowych intach. Do takiego możesz włożyć każdą 9 cyfrową liczbę.
  2. Odejmuj wielokrotności liczb, np jeśli a jest co najmniej 100x większa od b, to zrób a := odejmij(a, przesunprzecinek(b, 2)), gdzie funkcja przesunprzecinek przesuwa przecinek :P tzn dodaje zera na końcu liczby. Jak sprawdzić szybko ile razy większa jest dana liczba? Po pierwsze porównaj ilość intów które zajmują. Jak już będzie miał ten zgrubny wynik to podziel najbardziej znaczące inty z reprezentacji obu liczb.
0

Tylko ja mam z góry narzucone że mam użyć funkcji która odejmuje dwie liczby "pisemnie"... i właśnie jej potrzebuję.

0

No to zrób tak jak napisałem.

Jeśli masz wejściowego stringa: "123456789111222333", to grupując to po 9 cyfr dostaniesz dwa inty: 123456789 i 111222333.

Odejmowanie pisemne jest banalnie proste. Startujesz od ostatnich cyfr - tutaj cyfra to w rzeczywistości 9 cyfr - jeśli odjemna ma mniejszą cyfrę niż odjemnik to robisz przeniesienie, tzn przy klasycznym systemie dziesiętnym (przecinki oddzielają cyfry):

1,5,2 - 6,8 = 1,4,12 - 6,8 = 14,12 - 6,8 = 8,4

0

Jeśli masz wejściowego stringa: "123456789111222333", to grupując to po 9 cyfr dostaniesz dwa inty: 123456789 i 111222333.

A ja jednak bym proponował robić to na bajtach, bo dużo wolniej nie będzie, a program się uprości zdecydowanie.

Odejmowanie pisemne jest banalnie proste.

No właśnie na bajtach TAK, na intach NIE. Na intach to masa roboty, debuggowania itd. Zwłaszcza że autor tematu nie wygląda na orła w programowaniu.

b) Jak sprawdzić długość tablicy? Gdy wpiszę setlength(tablica,20) to elementy będą numerowane od 1 do 20?
c) jak prościej napisać ten program?

b) length(tablica) , nie będą numerowane od 0..19 jeżeli to array, a 1..20 jeżeli to string (eheh, te niuanse <3 )
c) Na bajtach, ja bym dla jeszcze większego uproszczenia cyfry przerobił na zwykłe chary tzn. '0'=> #0 '1'=>#1 itd. Potem napisać jakąś funkcję odejmującą/porównującą i gotowe... Co prawda nie będzie to rozwiązanie optymalne, ale proste. Widać po twoim algorytmie NWD że na wydajności ci nie zależy.

0

No to dobra może prościej.
Mam dwie tablicę tab_a i tab_b typu integer. W tablicach mam wpisanę po kolei liczby.
np.
Liczba 13431 to będzie tab_a[0]=1, tab_a[1]=3 itd.

Teraz potrzebuję procedurę lub funkcję która odejmie te dwie liczby(tablice) pisemnie i wynik zapiszę w tablicy a, oczywiście z uwzględnieniem rozmiaru.

Pytanie: Czy jeśli przypiszę tablicę o rozmiarze 5 do tablicy o rozmiarze 6, to czy tablica do której przypisałem zmieni rozmiar na 5?

0

123:
Operowanie na grupach cyfr raczej nie byłoby dużo trudniejsze. No chyba, że masz jakieś konkretne zastrzeżenia, to napisz, a nie takie ogólnikowe krytyki.

Widać po twoim algorytmie NWD że na wydajności ci nie zależy.

Chcesz, żeby zaimplementował modulo na stringach?

Alternatywą jest też: http://en.wikipedia.org/wiki/Binary_GCD_algorithm Nie trzeba wtedy implementować funkcji przesunprzecinek, ale trzeba zaimplementować funkcję podzielprzezdwa.

0

Teraz potrzebuję procedurę lub funkcję która odejmie te dwie liczby(tablice) pisemnie i wynik zapiszę w tablicy a, oczywiście z uwzględnieniem rozmiaru.

To ją napisz...?

Pytanie: Czy jeśli przypiszę tablicę o rozmiarze 5 do tablicy o rozmiarze 6, to czy tablica do której przypisałem zmieni rozmiar na 5?

Tak, bo operacje de facto deklaracja tablicy dynamicznej to tylko pointer na realną tablicę (przy czym tablica^ to nie @tablica[0] bo są jeszcze dane do pamiętania rozmiaru, referencji itd.).

Operowanie na grupach cyfr raczej nie byłoby dużo trudniejsze. No chyba, że masz jakieś konkretne zastrzeżenia, to napisz, a nie takie ogólnikowe krytyki.

Jeżeli mamy dwa integery w których jest po 9 cyfr, to żeby znaleźć cyfrę do przeniesienia w dół (przy odejmowaniu) to trzeba przewidzieć możliwości że znajduje się w tym samym incie albo w innym. To taki dosyć mały problem niby, ale nadal mam przeczucie (sic) że będzie sporo trudniej :P .

Chcesz, żeby zaimplementował modulo na stringach?

Właśnie problem w tym, że nawet gdyby odejmowanie byłoby superszybkie to i tak program działałby wolno. Nie mówię jak to ma rozwiązać, po prostu stwierdzam fakt. Więc cała implementacja odejmowania na intach byłaby po nic.

0

Jeżeli mamy dwa integery w których jest po 9 cyfr, to żeby znaleźć cyfrę do przeniesienia w dół (przy odejmowaniu) to trzeba przewidzieć możliwości że znajduje się w tym samym incie albo w innym. To taki dosyć mały problem niby, ale nadal mam przeczucie (sic) że będzie sporo trudniej .

Ale ja chcę żeby zamienił stringa "123456789" na inta 123456789. I wtedy niech odejmuje całymi intami. Akurat samo odejmowanie nie różni się prawie niczym od implementacji na bajtach. Problemy są raczej przy innych operacjach.

Właśnie problem w tym, że nawet gdyby odejmowanie byłoby superszybkie to i tak program działałby wolno. Nie mówię jak to ma rozwiązać, po prostu stwierdzam fakt. Więc cała implementacja odejmowania na intach byłaby po nic.

Dlatego opisałem mój pomysł odejmowania wielokrotności, aby zbić złożoność. W zasadzie z tym odejmowaniem wielokrotności może mieć złożoność identyczną z algorytmem opartym o dzielenie modulo.

0

Ale ja chcę żeby zamienił stringa "123456789" na inta 123456789. I wtedy niech odejmuje całymi intami. Akurat samo odejmowanie nie różni się prawie niczym od implementacji na bajtach. Problemy są raczej przy innych operacjach.

No ale mówimy tutaj na operacjach na dużych liczbach czyż nie?

Dlatego opisałem mój pomysł odejmowania wielokrotności, aby zbić złożoność. W zasadzie z tym odejmowaniem wielokrotności może mieć złożoność identyczną z algorytmem opartym o dzielenie modulo.

Może, nie znaczy że będzie mieć...
Daj sobie 99999999999999999999999999999999999999999999999 i 2, zobacz ile będzie liczyć...
To jest bardzo wolny algorytm znajdowania NWD, ja bym od niego zaczął optymalizację.

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