Witam, mam problem z obliczeniem NWD z liczb reprezentowanych jako obiekty (o długości do 10100). Próbuję rozwiązać zadanie z: http://main.edu.pl/pl/user.phtml?op=showtask&task=nwd&con=ALG
Nie mogę wykorzystać algorytmu Euklidesa, ponieważ w kursie nie było mowy o reszcie z dzielenia, a:
while(a != b) {
a > b ? a -= b : b -= a
}
jest zbyt wolne. Proszę o jakieś wskazówki.
Binarne NWD niekoniecznie musi być szybsze od normalnego algorytmu Euklidesa czy też np hybrydy dzielenia modulo i odejmowania, ponieważ przed binarnym GCD trzeba zamienić liczbę z postaci dziesiętnej na binarną. Ta hybryda polegałaby na odejmowaniu wielokrotności, np dla liczb n i m, przybliżamy długość tych liczb (czyli log10 n i log10 m) i np jeżeli pierwsza cyfra n jest większa od pierwszej cyfry m oraz liczba n jest dłuższa o k cyfr to robimy działanie: n -= m * 10 k, przy czym możenie przez potęgi dwójki to po prostu dodawanie iluś tam kopii cyfry zero na koniec stringa. Jeżeli warunek dla pierwszych cyfr nie zachodzi to robimy działanie: n -= m * 10 (k - 1). Szybka zamiana ze stringa zawierającego postać liczby w systemie dziesiętnym na liczbę zapisaną w systemie binarnym wymaga liczenia reszty z dzielenia lub stosowania podobnego triku co tu opisałem.
Nie ma może innego sposobu? Zadanie powinno być do zrobienia wykorzystując techniki z kursu, czyli tylko +, -, *, /(przez int) i porównywanie. Siedzę nad tym binarnym GCD, ale na razie nie bardzo mi to idzie. Jeżeli nie ma łatwiejszego sposobu to jeszcze pokombinuję, bo to kwestia czasu, aż mi wyjdzie.
Binarny GCD nie wypali bo przecież w standardzie nie ma funkcji które wczytują liczby rzędu 10^100 i konwertują na postać binarną. Jeśli użyjesz dodatkowej biblioteki, np GMP to równie dobrze mógłbyś użyć funkcji modulo z GMP.
Wykorzystaj mój sposób. Nie wykorzystuje on modulo (reszty z dzielenia) wprost.
Kod poglądowy:
C++ #include <cstdio>
int potega(int podstawa, int wykladnik) {
return wykladnik ? potega(podstawa, wykladnik - 1) * podstawa : 1;
}
//#define MOZNA_UZYWAC_MODULO
#define UZYJ_HYBRYDY
int gcd(int a, int b) {
#ifdef MOZNA_UZYWAC_MODULO
a %= b;
#else
#ifdef UZYJ_HYBRYDY
int wykladnik = 0;
while (a >= b * potega(10, wykladnik + 1)) {
wykladnik++;
}
if (a >= b) {
a -= b * potega(10, wykladnik);
}
#endif
while (a >= b) {
a -= b;
}
#endif
return a ? gcd(b, a) : b;
}
int main(int argc, char** argv) {
printf("%d\n", gcd(95675769, 5675768));
return 0;
}
Oczywiście zamiast intów będziesz miał stringi i zamiast mnożenia przez potęgi 10 będziesz miał doklejanie znaku '0' na koniec stringa.
PS:
Cały kod w #if to albo dzielenie modulo, albo emulacja dzielenia modulo - tak, powtarzane odejmowanie to emulowanie dzielenia modulo.
Edit:
Mam kod, trochę działa ale na testach się wywłaszcza (tylko 14 pkt zdobywa):
#include <iostream>
#include <string>
std::string odejmij(const std::string a, const std::string b) {
std::string w;
std::string::const_reverse_iterator ita = a.rbegin();
std::string::const_reverse_iterator itb = b.rbegin();
bool pozyczenie = false;
char c;
while (itb != b.rend()) {
if (pozyczenie) {
c = (*ita >= *itb + 1 ? *ita - *itb - 1 : *ita - *itb + 9) + '0';
pozyczenie = *ita < *itb + 1;
} else {
c = (*ita >= *itb ? *ita - *itb : *ita - *itb + 10) + '0';
pozyczenie = *ita < *itb;
}
w = c + w;
ita++;
itb++;
}
if (ita != a.rend()) {
if (pozyczenie) {
c = *ita - 1;
w = c + w;
ita++;
}
while (ita != a.rend()) {
c = *ita;
w = c + w;
ita++;
}
}
while ((w.size() > 1) && (w[0] == '0')) {
w = w.substr(1, w.size() - 1);
}
return w;
}
std::string gcd(std::string a, std::string b) {
std::string c(b);
while ((a.size() > c.size() + 1) || ((a.size() == c.size() + 1) && (a >= c + '0'))) {
c += '0';
}
if ((a.size() > c.size()) || ((a.size() == c.size()) && (a >= c))) {
a = odejmij(a, c);
}
while ((a.size() > b.size()) || ((a.size() == b.size()) && (a >= b))) {
a = odejmij(a, b);
}
return a != "0" ? gcd(b, a) : b;
}
int main(int argc, char** argv) {
//std::cout << odejmij("996", "995") << std::endl;
//std::cout << gcd("95675769", "5675768") << std::endl;
std::string a;
std::string b;
std::cin >> a >> b;
while ((a.size() > 1) && (a[0] == '0')) {
a = a.substr(1, a.size() - 1);
}
while ((b.size() > 1) && (b[0] == '0')) {
b = b.substr(1, b.size() - 1);
}
std::cout << gcd(a, b) << std::endl;
return 0;
}
modulo(a,b) = a- (a/b)*b; <-- dzielenie całkowitoliczbowe. ale pewnie da się jakoś szybciej - chociaz to i tak wydaje sie byc szybsze niz wersja z odejmowaniem