Jakiego algorytmu użyć do rozwiązania zadania?

Odpowiedz Nowy wątek
2014-06-12 19:38
0

Witam.
Mam takie oto zadanie: http://ideone.com/3BPcEo (nie jest to spoj ani nic podobnego, żeby nie było).
Zastanawiam się jakiego algorytmu użyć, żeby było jak najszybciej? Myślałem nad alg. Karatsuby, ale może jest coś szybszego?
Jak przechowywać tę dużą liczbę z wejścia? Podzielić ją na mniejsze i wpakować w tablicę?
Proszę o sugestie i pomysły.
Pozdrawiam i dziękuję :) .

PS: Mogę tu użyć potęgowania modularnego?

to zadanko ze spoja? pewnie nie możesz tak zrobić, ale był powiedziała; GMP ! - karolinaa 2014-06-13 17:53
karolinaa możesz troszkę jaśniej bo nie zrozumiałem? - Ursinus 2014-06-13 17:58

Pozostało 580 znaków

2014-06-12 20:54
1

Na szybko:
http://pl.wikipedia.org/wiki/[...]tm_szybkiego_pot%C4%99gowania

plus użyj jakiejś gotowej implementacji bignumów np. z biblioteki standardowej javy lub napisz własną (jeśli nie ma jej w twoim jezyku, bo własna najprawdopodobniej będzie wolniejsza).
http://docs.oracle.com/javase[...]api/java/math/BigInteger.html

Modulo raczej nic Ci nie pomoże, bo i tak musisz mieć koncowy wynik n^m (żeby policzyć sumę cyfr).

(Mogę się mylić, bo to "rozwiązanie" jest w połowie drogi miedzy prysznicem a wyjściem do znajomych, jak wrócę to się zgłębię).


"A human being should be able to change a diaper, plan an invasion, butcher a hog, conn a ship, design a building, write a sonnet, balance accounts, build a wall, set a bone, comfort the dying, take orders, give orders, cooperate, act alone, solve equations, analyze a new problem, pitch manure, program a computer, cook a tasty meal, fight efficiently, die gallantly. Specialization is for insects." Robert Heinlein.
edytowany 1x, ostatnio: datdata, 2014-06-12 20:55

Pozostało 580 znaków

2014-06-13 10:42
yarel
1

Rozważałeś reprezentację liczby potęgowanej jako wielomianu ? A potęgowania jako mnożenia wielomianów z wykorzystaniem szybkiej transformaty Fouriera?

http://www.cs.cmu.edu/afs/cs/[...]s10/www/lectures/lect0423.txt

Pozostało 580 znaków

2014-06-13 13:36
0

Dziękuję za podpowiedzi i jeśli mogę to zapytam jeszcze o jedno:
Czy ten kod do big num: http://ideone.com/pH8YBD się nada?
Znalazłem go w jednej z moich książek z listingami kodu.

Pozostało 580 znaków

2014-06-13 16:41
0

Skoro odpowiedź (w zadaniu) ma być: 14848102 oznacza to że należy obstawiać że ilość cyfr wyniku będzie 14848102/5 czyli około 2969620 (niecałe 3 mln).
Big num też się nie wyrobi.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-06-13 18:01
0

Więc co proponujesz _13th_Dragon?

Pozostało 580 znaków

2014-06-13 18:20
0

To samo co podał @yarel zwłaszcza pierwsze zdanie jego postu.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-06-13 18:25
0

Czyli co szybkie potęgowanie i alg. Karatsuby mogły by być?

Pozostało 580 znaków

2014-06-14 10:32
yarel
1

Masz wybór różnych algorytmów:
Standardowo - O (N^2)
Karatsbua - O(N^1.58..)
Fast Fourier Transformation - O(n log n)
Schonhage-Strassen - O(n log n loglog n)

Ja bym się zastanowił nad tym, którego implementacja będzie najbardziej dla Ciebie korzystna. Nie z punktu widzenia rozwiązania problemu, ale wiedzy jaką zdobędziesz próbując zrozumieć i zaimplementować coś innego niż trywialne rozwiązanie w O(N^2).

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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