NWD z ogromnych liczb

0

Witam,
Przychodzę z pewnym problemem. Otóż męczę się nad pewnym informatycznym zadaniem: https://szkopul.edu.pl/problemset/problem/CIoE17XpbV4Y9fk7IEbxpBmB/site/?key=statement
Zadanie polega na obliczeniu NWD dwóch liczb a i b. Problem polega na tym, że liczby te mogą mieć zakres do 10^1000, co nie mieści się w zmiennych liczbowych, więc trzeba zapisywać je w stringach. Czy ktoś zna jakiś prosty sposób na to zadanie?

Wspomnę tylko, że jestem początkujący jeśli chodzi o programowanie.

4

Użyj pythona? ;) W C/C++ będziesz niestety musiał ręcznie zaimplementować sobie dzielenie pisemne.

6

Jeśli zadanie na to zezwala - użyj biblioteki do dużych liczb. Boost.Multiprecision albo GMP powinny na to łatwo pozwolić.

Jeśli tak nie jest, to zaimplementuj podstawowe operacje na dużych liczbach na stringach i użyj algorytmu Euklidesa aby policzyć NWD.

2

Albo użyć libgmp, vide https://gmplib.org/manual/Number-Theoretic-Functions
Tyle tylko, że niekoniecznie musi to przejść w tym zadaniu.
EDIT nie ten link wkleiłem

0

Potrzebuję napisać ten program w C++.
W jaki sposób użyć operacji i jak zastosować algorytm Euklidesa na stringach?
Przepraszam, ale to nie jest dla mnie oczywiste, pierwszy raz spotykam się z tym w zadaniu.

2

Algorytm Euklidesa: https://en.wikipedia.org/wiki/Euclidean_algorithm
Operacje na bigintegerach: https://duckduckgo.com/?q=implementation+of+operations+in+big+numbers&t=ffab&ia=web
W zalezności który pseudokod wybierzesz, takie operacje trzeba zaimplementować; minimum, to chyba ==, >, -, taka funkcja:

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a
3

Całe zadanie sprowadza się do tego, żebyś napisał arytmetykę dużych liczb.
Czyli implementujesz po kolei

  • wczytywanie i wypisanie dużych liczb
  • dodawanie
  • odejmowanie (porównywanie)
  • mnożenie
  • i na końcu dzielenie, które zależy od wcześniejszych punktów
3

"Na stringach" to raczej tak w przenosni.
Mozesz uzyc struktur typu int a[2000] i trzymac w kazdym elemencie jedna cyfre.
A czy to bedzie cyfra 0..9 czy np 0..1023 to juz chyba tylko zalezy od Ciebie.

Edit: ze wzgledu na przyrost cyfr, jesli wystepuje, proponuje trzymac najmniej znaczace cyfry na poczatku tablicy (czyli dla 91 a[0] = 1, a[1] = 9) - kolejnosc odwrotna do zapisu dziesietnego.

1

Zaczął bym od przerobienia powyższego kodu https://godbolt.org/z/W9115W

  • wyrzucił bym niepotrzebne funkcje
  • zmieniłbym go na bardziej czytelny i bliższy dzisiejszym standardom ( C++17 )

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