Wielki Kaczor napisał(a):
Wielki Kaczor napisał(a):
Bogaty Rycerz napisał(a):
odejmowania na a - b, gdzie a > b raczej nie powinniśmy rozpatrywać
- b > a
A czemu, jak Masz odejmowanie to Masz już wszystko, do reszty podałem pseudokod.
0
0
lion137 napisał(a):
Wielki Kaczor napisał(a):
Wielki Kaczor napisał(a):
Bogaty Rycerz napisał(a):
odejmowania na a - b, gdzie a > b raczej nie powinniśmy rozpatrywać
- b > a
A czemu, jak Masz odejmowanie to Masz już wszystko, do reszty podałem pseudokod.
nie wiem, czy widziałeś, ale podałem druga wersję, zgodną z Twoimi zaleceniami. napisałem, że przy a - b b > a w FUNKCJI ODEJMOWANIA nie powinniśmy rozpatrywać, bo mamy oddzielną funkcję mniejsze_równe :)
0
To o co chodzi, wszystko już jest.
0
boost + gmp i
#include <boost/multiprecision/gmp.hpp>
#include <iostream>
using namespace boost::multiprecision;
using namespace std;
mpz_int gcd(mpz_int a, mpz_int b)
{
mpz_int c;
while(b != 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int main()
{
mpz_int a, b;
while (cin >> a >> b)
{
cout << gcd(a, b) << '\n';
}
return 0;
}
Niestety nie wiem jak zmusić wandbox by linkował gmp: https://wandbox.org/permlink/Jpbj3JffDxBoYgw8 :(
0
MarekR22 napisał(a):
boost + gmp i
#include <boost/multiprecision/gmp.hpp> #include <iostream> using namespace boost::multiprecision; using namespace std; mpz_int gcd(mpz_int a, mpz_int b) { mpz_int c; while(b != 0) { c = a % b; a = b; b = c; } return a; } int main() { mpz_int a, b; while (cin >> a >> b) { cout << gcd(a, b) << '\n'; } return 0; }Niestety nie wiem jak zmusić wandbox by linkował gmp: https://wandbox.org/permlink/Jpbj3JffDxBoYgw8 :(
a co jeżeli ma to być zweryfikowane przez sędziego, kiedy nie możemy dołączyć żadnych bibliotek zewnętrznych?
0
@MarekR22: czyli porzucasz koncpecję wykonywania działań arytmetycznych bezpośrednio na stringach, tylko, np. sam wynik obliczony z własnego systemu liczbowego wrzucilibyśmy bezpośrednio do tego typu danych? rzeczywiście rozwiązanie trafne i do wykonania, ale wciąż zachodzę w głowę dlaczego zadania nie mogę zrealizować na przedstawiony przeze mnie sposób? i dlaczego nikt nie jest w stanie znaleźć jakiejś niezgodności w kodzie?
0
A funkcje mod I less_than_eq dzialaja chociaz?
0
lion137 napisał(a):
A funkcje mod I less_than_eq dzialaja chociaz?
tak, dzialaja
0
Smutny Polityk napisał(a):
lion137 napisał(a):
A funkcje mod I less_than_eq dzialaja chociaz?
tak, dzialaja
Czyli problem z odejmowaniem, wydaje mi sie, ze mam dzialajacy proof of concept w pythonie ale Nie testowalem, wrzuce wieczorem.
0
Oto dzialająca funkcja odejmowania (pseudokod):
fun sub(a, b):
# Tu stringi wejściowe zamieniamy na listy cyfr, np. : "12" -> [1, 2]
# a -> a_list, b -> b_list
out = tworzymy tablicę zer (intów) o długości wejścia a (dłuższego)
if less_or_eq(a, b): return "0" # zwróć zero jak druga liczba większa
b_list = zeroes(a_list, b_list) # drugą liczbe dopełniamy zerami na początku, by zrównać
# z długością pierwszej
carry_bit = 0 # na początku, carry równe, oczywiście, zero
i from length(a_list) - 1 to 0:
# algorytm odejmowania, w pętli odejmujemy cyfry i przekazujemy carry bit
out[i] = ((a_list[i] - b_list[i]) + 10 - carry_bit) % 10
if a_list[i] - b_list[i] < 0:
carry_bit = 1
else:
carry_bit = 0
out = remove_leading_zeroes(out) # usunąć zera z poczatku jak są
# Tu zamienić out na string
return out_str
Teraz można to wszystko poskładać. Napisałem w pseudokodzie, gdyż funkcje zamieniające stringi na listy i na odwrót są w zupełnie inne niż w C i tak Ci nic nie powiedzą. Zmiana (stringa na listę) jest potrzebna, gdyż ten algorytm ciężko w pythonie zrefaktoryzować na stringi (są immutable) - tak było najłatwiej. Nie wiem jak w C++, ale w Pythonie funkcja mod bardzo szybko rozwala stos - domyślam się, że, również, przez implementację stringów.