Witam. szukam jakiegoś szybkiego algorytmu wskazującego czy liczba jest automorficzna. Liczba może się składać z 50 000 znaków więc muszę ją przechowywać w stringu. Zrobiłem algorytm mnożenia pisemnego ale wykonuję się on zbyt długo. Proszę o jakieś podpowiedzi. Dodam, że po każdym wymnożeniu sprawdzam czy może w aktualnej chwili liczba już nie będzie automorficzna.
0
0
Te linki mi niestety nie pomogą, lub może jestem za głupi żeby je wykorzystać (wtedy proszę o wskazanie kierunku). Jak pisałem liczba może składać się od 1 do 50 000 cyfr, więc nie zmieszczę tego w innym typie niż string, ew. tablica char. Po prostu nie widzę innej możliwości niż mnożenie pisemne no ale algorytm wtedy wykonuje się za długo.
0
Jaki język programowania? Jakaś biblioteka do obsługi dużych liczb nie wystarczy?
0
C++, niestety biblioteka do obsługi dużych liczb nie przejdzie.
0
Wyczuwam dziwne powiązanie z tym: http://4programmers.net/Forum/C_i_C++/239945-zuzycie_pamieci (nazwa funkcji w kodzie)
0
Nikt nic?
0
Mnóż od końca i natychmiast sprawdzaj czy jest ok.
Dla wygody zapisuj liczbę odwrotnie czyli Tb[0] - najmłodsza cyfra.
dig=Tb[0]-'0'; mul=dig*dig; rem=mul/10; if(mul-10*rem!=dig) return false;
Dla następnej cyfry mul już się liczy bardziej skomplikowanie.
mul=2*(Tb[1]-'0')*(Tb[0]-'0')+rem;
Co znaczy "Nikt nic?" dostałeś link do kodu, co prawda jeszcze nie działającego ale ...
0
Czy z tym algorytmem jest na pewno wszystko ok? Bo 3 cyfra już mi nie wychodzi
0
Ja wymiękam ...
bool isAutomorphic(const string &num)
{
int rem=0;
vector<char> tb;
tb.reserve(num.size());
for(auto i=num.crbegin();i!=num.crend();++i) tb.push_back(*i-'0');
for(auto i=tb.begin();i!=tb.end();++i)
{
auto b=tb.begin(),e(i);
while(b<e) rem+=2*(*(b++))*(*(e--));
if(b==e) rem+=(*b)*(*e);
int sum=rem;
if(sum-10*(rem/=10)!=(*i)) return false;
}
return true;
}
0
A biblioteka algorithm?