Chotkos's Blog

Programowanie i informatyka

Bignumy

Postanowiłem zacząć od dosyć banalnego problemu – od bardzo dużych liczb.

Pomyślicie sobie zapewne „Gdzie leży problem?” A sprawa jest dosyć jasna, pozwolę ją sobie przedstawić na przykładzie.

Pewien bardzo wpływowy szejk, posiadacz roponośnych pól w Arabii Saudyjskiej uzbierał po tym jak drastycznie podrożała ropa na całym świecie naprawdę niebagatelną sumę pieniędzy. Zatrudnił bankierów aby zliczyli jak potężny jest jego kapitał. Bankierzy po długich wyliczeniach ustalili jego łączny majątek na 92233720368547758070 euro. Szejk umarł ze szczęścia. Jedynym spadkobiercą okazał się jego kuzyn z Polski , który uznał, że na potrzeby własnych interesów zamieni tą kwotę na polskie złote.

Napisz program, który przeliczy majątek szejka na złotówki, po podanym przez użytkownika kursie. ( Dla ułatwienia liczby całkowitej)

Zadanie wydaje się banalne – wystarczy tylko 92233720368547758070 pomnożyć przez kurs który poda użytkownik i wypisać. Życzę powodzenia.

Naprawdę zacząłeś to pisać?!  Nie żartuj sobie ;]

Zauważ: INT64 typ zmiennej znany tak w C++ jak i w Pascalu jest ograniczony (w obie strony zera) do:

9223372036854775807

dla porównania liczba z treści zadania to:

92233720368547758070

Ta liczba jest za duża, żeby coś z nią zrobić! Nie zmieści się w pamięci a ostatecznie nasz program wysypie się w trakcie kompilacji – innymi słowy kicha!

Co z tym zrobić?

Mam nadzieję że już na to wpadłeś, jeżeli nie, to zaproponuję ci teraz coś co może wydać Ci się trochę głupie – ile to jest 19824 + 1198 . NIE! Nie odpalaj kalkulatora, ani nie licz w pamięci. Weź do ręki ołówek i oblicz na kartce.

Jak widać liczba, której nie mogłeś łatwo wyliczyć od razu w głowie da się bezproblemowo dodać „pod kreską”. Czemu więc nie przenieść tej reguły na grunt naszego programu!

O czym powinniśmy pamiętać pisząc ten program:

– Tak naprawdę to będzie dodanie do siebie majątku n razy;

– Aby dodawać musimy wiedzieć jak

– W dodawaniu należy zacząć od prawej w lewo aby przenosić wartości wykraczające poza 9

– A, no i najważniejsze – na czym to robić!?

Stringi – ciągi znaków, mają właściwie nieograniczoną pamięć ( jeżeli nie wierzysz to spróbuj je zapełnić, szybko Ci się znudzi) dlatego możemy na nich swobodnie operować dużymi liczbami. Jednak dodawanie do siebie stringów ‚1’+’2′ nie da na upragnionego ‚3’ ale ’12’ bo ciągi się skontaktują.

Tutaj z pomocą przychodzi ascII gdzie cyfry zaczynają się od wartości 48 ( 48 to zero), o tym też należy pamiętać.

Postanowiłem napisać kod dodawania bignumów w pascalu bo jest tam mały chocek z funkcją ord(a[i]):

kod umieściłem pod tamtym linkiem bo niestety zapisywanie kodu na wordpressie leży i kwiczy

http://wklej.org/id/262987/

jest tam funkcja ord(a[i]) – oznacza ona wartość liczbową i-tego znaku ciągu a. Cyfry mają kody od 48 w górę co możecie sobie zobaczyć na wiki, w tabeli ascII

Mając gotowe dodawanie spróbujcie z odejmowaniem, no i oczywiście rozwiążcie problem polskiego szejka ;]

Reklamy

Styczeń 14, 2010 - Posted by | Algorytmy, Programowanie |

4 komentarze »

  1. dodam że w c++ zamiast ord(a[i]) można zrobić po prostu int(a[i])

    Komentarz - autor: DarkGL | Styczeń 15, 2010 | Odpowiedz

  2. no i jeszcze coś 😀 gdy zrobimy coś takiego
    unsigned INT64 to nasz zmienna będzie miała pojemność od 0 do 18446744073709551614

    Komentarz - autor: DarkGL | Styczeń 15, 2010 | Odpowiedz

  3. ale i tak wiadomo że cała idea polega na działaniach na dużych liczbach, bo zawsze DGl możemy przyjąć że nasza kwota po pomnożeniu nie zmieści się w int 64 😉

    Komentarz - autor: chotkos | Styczeń 16, 2010 | Odpowiedz

  4. […] Ponieważ głupio mi zostawić sprawdzarkę właściwie pustą postanowiłem dorzucić nowe zadanko, do którego macie dostęp tutaj, jeżeli nie dajecie sobie rady to warto przeczytać jeden z wcześniejszych wpisów. […]

    Pingback - autor: Reklama? « Chotkos's Blog | Styczeń 22, 2010 | Odpowiedz


Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: