Autor artykułu: mgr Jerzy Wałaszek, wersja1.0
©2010 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
|
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2010 mgr
Jerzy Wałaszek
|
Czasami programista staje przed zadaniem obliczenia wartości leżącej poza zakresem standardowych typów danych. Załóżmy, że chcemy wyznaczyć wartość 21000. Jeśli zastosujemy największy typ całkowity unsigned long long int, to największą liczbą, którą może on przedstawić, jest 264 - 1. To jest niestety zbyt mało. Co zatem możemy zrobić? Odpowiedź jest jedna - zaprojektować działania arytmetyczne na liczbach o dowolnej długości. Do tego celu wykorzystamy znany wszystkich algorytm dodawania liczb dziesiętnych.
Liczby będziemy reprezentowali jako łańcuchy znakowe, które zawierają poszczególne cyfry. Dodawanie rozpoczynamy od ostatnich cyfr każdego z łańcuchów:
"157766872237632767623867637"
"779723827372323329"
Wyznaczamy ostatnie cyfry 2 i 3, i wykonujemy ich dodawanie, otrzymując wynik w.
7 + 9 = 16
Ostatnia cyfra w przechodzi do wyniku dodawania.
157766872237632767623867637
+ 779723827372323329
-----------------------------
6
Jeśli wynik dodawania cyfr jest większy od 9, to otrzymujemy przeniesienie 1 do następnej kolumny. Przeniesienie to należy dodać do wyniku sumowania cyfr w kolejnej kolumnie. Operację przerywamy, gdy przetworzymy wszystkie cyfry najdłuższej liczby - brakujące cyfry krótszej liczby zastępujemy zerem. Jeśli po dodaniu wszystkich cyfr przeniesienie wynosi 1, to dopisujemy je do wyniku.
Ostatnią cyfrę w otrzymamy jako
w % 10
Przeniesienie do następnej kolumny otrzymamy jako
w / 10 (dzielenie całkowitoliczbowe)
Musimy jeszcze pamiętać, iż cyfry wyniku otrzymujemy od tyłu, zatem muszą one być wstawiane na początek tekstu w łańcuchu wynikowym.
Na podstawie tej metody tworzymy pierwszy program, który dodaje liczby zapisane w postaci łańcuchów cyfr.
// Dodawanie dowolnych liczb dziesiętnych
// (C)2011 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------
#include <iostream>
#include <string>
using namespace std;
// funkcja zwraca ciąg znaków będący wynikiem dodawania argumentów
//----------------------------------------------------------------
string dodaj(string a, string b)
{
// wyznaczamy pozycję ostatniej cyfry w obu łańcuchach
int pa = a.length() - 1;
int pb = b.length() - 1;
// zerujemy łańcuch wynikowy
string wynik = "";
// na początku przeniesienie wynosi 0
int p = 0;
// w pętli dodajemy kolejne cyfry a i b
while(pa >= 0 || pb >= 0)
{
// wyliczamy wartości cyfr w łańcuchach a i b
int ca, cb, w;
if(pa >= 0) ca = a[pa] - 48; else ca = 0;
if(pb >= 0) cb = b[pb] - 48; else cb = 0;
// obliczamy sumę cyfr z a i b, uwzględniając przeniesienie
w = ca + cb + p;
// do łańcucha wynikowego wstawiamy ostatnią cyfrę w
wynik = "0" + wynik;
wynik[0] = 48 + w % 10;
// obliczamy przeniesienie do następnej kolumny
p = w / 10;
// modyfikujemy indeksy kolumn w łańcuchu a i b
pa--; pb--;
}
// jeśli przeniesienie wynosi 1, dopisujemy cyfrę 1 do wyniku
if(p) wynik = "1" + wynik;
return wynik;
}
int main()
{
string a, b;
cin >> a >> b;
cout << a << " + " << b << " = " << dodaj(a,b) << endl;
return 0;
}
|
Kolejne potęgi liczby 2 możemy obliczać jako sumy:
20 = 1
21 = 2 = 20 + 20
22 = 4 = 21 + 21
23 = 8 = 22 + 22
24 = 16 = 23 + 23
Zatem znając wartość potęgi 2n, następną policzymy jako:
2n + 1 = 2n + 2n
Na tej podstawie tworzymy następny program, który liczy dowolną (rozsądnie dużą) potęgę liczby 2. Rozpoczyna on od 20 = 1, a następnie w pętli wykonywanej n razy sumuje tę wartość ze sobą. Do obliczeń wykorzystujemy liczby w postaci łańcuchów cyfr oraz funkcję dodaj().
// Obliczanie potęgi liczby 2
// (C)2011 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------
#include <iostream>
#include <string>
using namespace std;
// funkcja zwraca ciąg znaków będący wynikiem dodawania argumentów
//----------------------------------------------------------------
string dodaj(string a, string b)
{
// wyznaczamy pozycję ostatniej cyfry w obu łańcuchach
int pa = a.length() - 1;
int pb = b.length() - 1;
// zerujemy łańcuch wynikowy
string wynik = "";
// na początku przeniesienie wynosi 0
int p = 0;
// w pętli dodajemy kolejne cyfry a i b
while(pa >= 0 || pb >= 0)
{
// wyliczamy wartości cyfr w łańcuchach a i b
int ca, cb, w;
if(pa >= 0) ca = a[pa] - 48; else ca = 0;
if(pb >= 0) cb = b[pb] - 48; else cb = 0;
// obliczamy sumę cyfr z a i b, uwzględniając przeniesienie
w = ca + cb + p;
// do łańcucha wynikowego wstawiamy ostatnią cyfrę w
wynik = "0" + wynik;
wynik[0] = 48 + w % 10;
// obliczamy przeniesienie do następnej kolumny
p = w / 10;
// modyfikujemy indeksy kolumn w łańcuchu a i b
pa--; pb--;
}
// jeśli przeniesienie wynosi 1, dopisujemy cyfrę 1 do wyniku
if(p) wynik = "1" + wynik;
return wynik;
}
int main()
{
string a = "1";
int i, n;
cin >> n; // odczytujemy wykładnik
// w pętli sumujemy a z a n razy
for(i = 0; i < n; i++) a = dodaj(a, a);
// wyświetlamy wynik
cout << "2^" << n << " = " << a << endl << endl;
return 0;
}
|
Dla dużych n czas obliczeń może być bardzo długi. Oto jeden z wyników pracy tego programu:
| 10000 2^10000 = 1995063116880758384883742162683585083823496831886192454852008949852943 88302219466319199616840361945978993311294232091242715564913494137811175937859320 96323957855730046793794526765246551266059895520550086918193311542508608460618104 68550907486608962488809048989483800925394163325785062156830947390255691238806522 50966438744410467598716269854532228685381616943157756296407628368807607322285350 91641476183956381458969463899410840960536267821064621427333394036525565649530603 14268023496940033593431665145929777327966577560617258203140799419817960737824568 37622800373028854872519008344645814546505579296014148339216157345881392570953797 69119277800826957735674444123062018757836325502728323789270710373802866393031428 13324140162419567169057406141965434232463880124885614730520743199225961179625013 09928602417083408076059323201612684922884962558413128440615367389514871142563151 11089745514203313820202931640957596464756010405845841566072044962867016515061920 63100418642227590867090057460641785695191145605506825125040600751984226189805923 71180544447880729063952425483392219827074044731623767608466130337787060398034131 97133493654622700563169937455508241780972810983291314403571877524768509857276937 92643322159939987688666080836883783802764328277517227365757274478411229438973381 08616074232532919748131201976041782819656974758981645312584341359598627841301281 85406283476649088690521047580882615823961985770122407044330583075869039319604603 40497315658320867210591330090375282341553974539439771525745529051021231094732161 07534748257407752739863482984983407569379556466386218745694992790165721037013644 33135817214311791398222983845847334440270964182851005072927748364550578634501100 85298781238947392869954083434615880704395911898581514577917714361969872813145948 37832020814749821718580113890712282509058268174362205774759214176537156877256149 04582904992461028630081535583308130101987675856234343538955409175623400844887526 16264356864883351946372037729324009445624692325435040067802727383775537640672689 86362410374914109667185570507590981002467898801782719259533812824219540283027594 08448955014676668389697996886241636313376393903373455801407636741877711055384225 73949911018646821969658165148513049422236994771476306915546821768287620036277725 77237813653316111968112807926694818872012986436607685516398605346022978715575179 47385246369446923087894265948217008051120322365496288169035739121368338393591756 41873385051097027161391543959099159815465441733631165693603112224993796999922678 17323580231118626445752991357581750081998392362846152498810889602322443621737716 18086357015468484058622329792853875623486556440536962622018963571028812361567512 54333830327002909766865056855715750551672751889919412971133769014991618131517154 40077286505731895574509203301853048471138183154073240533190384620840364217637039 11550639789000742853672196280903477974533320468368795868580237952218629120080742 81955131794815762444829851846150970488802727472157468813159475040973211508049819 0455803416826949787141316063210686391511681774304792596709376 |
Ciąg liczb Fibonacciego jest ciągiem rekurencyjnym, który definiujemy następująco:
fib0 = 0
fib1 = 1
fibn = fibn-2 + fibn-1,
dla n > 1
Kolejna liczba Fibonacciego (za wyjątkiem pierwszych dwóch) powstaje jako suma dwóch liczb poprzednich. Oto kilka początkowych liczb Fibonacciego:
0 1 1 2 3 5 8 13 21 34 55 89 114 233 377 610 987 ...
Liczby Fibonacciego znajdują bardzo wiele zastosowań w informatyce i matematyce - na pewno spotkasz się z nimi jeszcze wielokrotnie. Ich wzrost jest bardzo szybki. Na przykład:
fib49 = 7,778,742,049
Jeśli chcemy policzyć fib10000, to okaże się,
iż wynik przekroczy szybko dopuszczalny zakres standardowych typów danych.
Rozwiązaniem jest nasze podejście. Algorytm efektywnego obliczania liczb
Fibonacciego opiera się na tak zwanym programowaniu dynamicznym. Polega ono na
tym, iż do wyliczenia kolejnych wartości wykorzystujemy wartości policzone już
wcześniej. W naszym przypadku będziemy zapamiętywać dwie ostatnio wyliczone
liczby Fibonacciego, a kolejną liczbę otrzymamy jako ich sumę. Do rachunków
wykorzystamy łańcuchy znakowe oraz naszą funkcję
// Obliczanie wartości liczb Fibonacciego
// (C)2011 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------
#include <iostream>
#include <string>
using namespace std;
// funkcja zwraca ciąg znaków będący wynikiem dodawania argumentów
//----------------------------------------------------------------
string dodaj(string a, string b)
{
// wyznaczamy pozycję ostatniej cyfry w obu łańcuchach
int pa = a.length() - 1;
int pb = b.length() - 1;
// zerujemy łańcuch wynikowy
string wynik = "";
// na początku przeniesienie wynosi 0
int p = 0;
// w pętli dodajemy kolejne cyfry a i b
while(pa >= 0 || pb >= 0)
{
// wyliczamy wartości cyfr w łańcuchach a i b
int ca, cb, w;
if(pa >= 0) ca = a[pa] - 48; else ca = 0;
if(pb >= 0) cb = b[pb] - 48; else cb = 0;
// obliczamy sumę cyfr z a i b, uwzględniając przeniesienie
w = ca + cb + p;
// do łańcucha wynikowego wstawiamy ostatnią cyfrę w
wynik = "0" + wynik;
wynik[0] = 48 + w % 10;
// obliczamy przeniesienie do następnej kolumny
p = w / 10;
// modyfikujemy indeksy kolumn w łańcuchu a i b
pa--; pb--;
}
// jeśli przeniesienie wynosi 1, dopisujemy cyfrę 1 do wyniku
if(p) wynik = "1" + wynik;
return wynik;
}
int main()
{
string fib;
int n, i;
cin >> n; // odczytujemy numer liczby Fib
// programowaniem dynamicznym wyznaczamy n-tą liczbę Fib
if(n == 0) fib = "0";
else if(n == 1) fib = "1";
else
{
string fib0 = "0";
string fib1 = "1";
for(i = 2; i <= n; i++)
{
// wyznaczamy kolejną liczbę Fib jako sumę dwóch poprzednich
fib2 = dodaj(fib0, fib1);
// zapamiętujemy w fib0 i fib1 dwie ostatnie liczby
fib0 = fib1;
fib1 = fib2;
}
}
// wyświetlamy wyniki
cout << "fib " << n << " = " << fib << endl << endl;
return 0;
}
|
| 10000 fib 10000 = 33644764876431783266621612005107543310302148460680063906564769974680 08144216666236815559551363373402558206533268083615937373479048386526826304089246 30564318873545443695598274916066020998841839338646527313000888302692356736131351 17579297437854413752130520504347701602264758318906527890855154366159582987279682 98751063120057542878345321551510387081829896979161312785626503319548714021428753 26981879620469360978799003509623022910263681314931952756302278376284415403605844 02572114334961180023091208287046088923962328835461505776583271252546093591128203 92528539343462090424524892940390170623388899108584106518317336043747073790855263 17643257339937128719375877468974799263058370657428301616374089691784263786242128 35258112820516370298089332099905707920064367426202389783111470054074998459250360 63356093388383192338678305613643535189213327973290813373264265263398976392272340 78829281779535805709936910491754708089318410561463223382174656373212482263830921 03297701648054726243842374862411453093812206564914032751086643394517512161526545 36133311131404243685480510676584349352383695965342807176877532834823434555736671 97313927462736291082106792807847180353291311767789246590899386354593278945237776 74406192240337638674004021330343297496902028328145933418826817683893072003634795 62311710310129195316979460763273758925353077255237594378843450406771555577905645 04430166401194625809722167297586150269684431469520346149322911059706762432685159 92834709891284706740862008587135016260312071903172086094081298321581077282076353 18662461127824553720853236530577595643007251774431505153960090516860322034916322 26408852488524331580515348496224348482993809050704834824493274537326245677558790 89187190803662058009594743150052402532709746995318770724376825907419939632265984 14749819360928522394503970716544315642132815768890805878318340491743455627052022 35648464951961124602683139709750693826487066132645076650746115126775227486215986 42530711298441182622661057163515069260029861704945425047491378115154139941550671 25627119713325276363193960690289565028826860836224108205056243070179497617112123 3066073310059947366875 |
Posiadamy funkcję dodającą dwie duże liczby. Zastanówmy się, czy możemy ją wykorzystać również przy mnożeniu. W tym celu musimy zauważyć prostą zależność. Załóżmy, że chcemy pomnożyć pewną liczbę a przez 26:
w = 26 × a
Rozłóżmy liczbę 26 na sumę potęg liczby 2:
26 = 16 + 8 + 2 = 24 + 23 + 21
Teraz nasz iloczyn możemy przedstawić następująco:
w = 26 × a = (16 + 8 + 2) × a = 16a + 8a + 2a
Aby policzyć 26 × a wystarczy dodać do siebie 16a, 8a, 2a. Wyznaczenie kolejnych iloczynów a, 2a, 4a, 8a, 16a jest bardzo proste - wystarczy dodawać do siebie kolejne wyrażenia:
| a | |
| 2a | = a + a |
| 4a | = 2a + 2a |
| 8a | = 4a + 4a |
| 16a | = 8a + 8a |
W trakcie wyznaczania tych iloczynów dodajemy do wyniku odpowiedni iloczyn 2i × a, jeśli 2i wchodzi w skład rozkładu liczby 26. Rozkład na potęgi liczby 2 jest równoważny zapisowi binarnemu liczby 26. Kolejne bity od końca liczby binarnej posiadają wagi równe potęgom liczby 2:
| 16 | 8 | 4 | 2 | 1 | |
| 2610 = | 1 | 1 | 0 | 1 | 0 |
Jeśli biti ma wartość 1, to rozkład liczby zawiera potęgę 2i. Pozycje bitów numerujemy od strony prawej do lewej poczynając od 0. W pamięci komputera liczby są przechowywane binarnie, zatem nic nie musimy wyliczać, wystarczy przeglądać poszczególne bity mnożnika za pomocą operacji & maska, gdzie maska posiada tylko jeden bit ustawiony na 1. Jeśli wynik tej operacji będzie różny od 0, to bit mnożnika odpowiadający bitowi maski jest ustawiony na 1. W przeciwnym razie jest on ustawiony na 0.
Wynika stąd prosta zasada mnożenia:
Zerujemy wynik. Ustawiamy mnożną a. W pętli przeglądamy kolejne bity mnożnika poczynając od najmłodszego i idąc w kierunku najstarszego. Jeśli bit jest ustawiony na 1, to do wyniku dodajemy mnożną. Mnożną dodajemy do siebie i wykonujemy następny obieg pętli. Gdy przejrzymy wszystkie bity mnożnika, w wyniku będziemy mieli wartość iloczynu.
// Mnożenie dużych liczb
// (C)2011 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------
#include <iostream>
#include <string>
using namespace std;
// funkcja zwraca ciąg znaków będący wynikiem dodawania argumentów
//----------------------------------------------------------------
string dodaj(string a, string b)
{
// wyznaczamy pozycję ostatniej cyfry w obu łańcuchach
int pa = a.length() - 1;
int pb = b.length() - 1;
// zerujemy łańcuch wynikowy
string wynik = "";
// na początku przeniesienie wynosi 0
int p = 0;
// w pętli dodajemy kolejne cyfry a i b
while(pa >= 0 || pb >= 0)
{
// wyliczamy wartości cyfr w łańcuchach a i b
int ca, cb, w;
if(pa >= 0) ca = a[pa] - 48; else ca = 0;
if(pb >= 0) cb = b[pb] - 48; else cb = 0;
// obliczamy sumę cyfr z a i b, uwzględniając przeniesienie
w = ca + cb + p;
// do łańcucha wynikowego wstawiamy ostatnią cyfrę w
wynik = "0" + wynik;
wynik[0] = 48 + w % 10;
// obliczamy przeniesienie do następnej kolumny
p = w / 10;
// modyfikujemy indeksy kolumn w łańcuchu a i b
pa--; pb--;
}
// jeśli przeniesienie wynosi 1, dopisujemy cyfrę 1 do wyniku
if(p) wynik = "1" + wynik;
return wynik;
}
// Funkcja mnoży małą liczbę 32 bitową przez dużą
//-----------------------------------------------
string mnoz(unsigned a, string b)
{
string wynik = "0";
unsigned maska;
for(maska = 1; maska; maska <<= 1)
{
if(a & maska) wynik = dodaj(wynik, b);
b = dodaj(b, b);
}
return wynik;
}
int main()
{
unsigned a;
string b;
cin >> a >> b;
cout << a << " x " << b << " = " << mnoz(a, b) << endl << endl;
return 0;
}
|
Silnia n jest iloczynem kolejnych liczb naturalnych od 1 do n:
1! = 1
2! = 1 × 2 = 2
3! = 1 × 2 × 3 = 6
4! = 1 × 2 × 3 × 4 = 24
Silnia rośnie bardzo szybko. Dla maksymalnego typu unsigned long long int już 21! przekroczy dopuszczalny zakres liczb. A my zamierzamy policzyć wartość 1000! Wykorzystamy oczywiście naszą funkcję mnoz().
// Silnia!
// (C)2011 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------
#include <iostream>
#include <string>
using namespace std;
// funkcja zwraca ciąg znaków będący wynikiem dodawania argumentów
//----------------------------------------------------------------
string dodaj(string a, string b)
{
// wyznaczamy pozycję ostatniej cyfry w obu łańcuchach
int pa = a.length() - 1;
int pb = b.length() - 1;
// zerujemy łańcuch wynikowy
string wynik = "";
// na początku przeniesienie wynosi 0
int p = 0;
// w pętli dodajemy kolejne cyfry a i b
while(pa >= 0 || pb >= 0)
{
// wyliczamy wartości cyfr w łańcuchach a i b
int ca, cb, w;
if(pa >= 0) ca = a[pa] - 48; else ca = 0;
if(pb >= 0) cb = b[pb] - 48; else cb = 0;
// obliczamy sumę cyfr z a i b, uwzględniając przeniesienie
w = ca + cb + p;
// do łańcucha wynikowego wstawiamy ostatnią cyfrę w
wynik = "0" + wynik;
wynik[0] = 48 + w % 10;
// obliczamy przeniesienie do następnej kolumny
p = w / 10;
// modyfikujemy indeksy kolumn w łańcuchu a i b
pa--; pb--;
}
// jeśli przeniesienie wynosi 1, dopisujemy cyfrę 1 do wyniku
if(p) wynik = "1" + wynik;
return wynik;
}
// Funkcja mnoży małą liczbę 32 bitową przez dużą
//-----------------------------------------------
string mnoz(unsigned a, string b)
{
string wynik = "0";
unsigned maska;
for(maska = 1; maska; maska <<= 1)
{
if(a & maska) wynik = dodaj(wynik, b);
b = dodaj(b, b);
}
return wynik;
}
int main()
{
int i,n;
string silnia = "1";
cin >> n;
for(i = 1; i <= n; i++) silnia = mnoz(i,silnia);
cout << n << "! = " << silnia << endl << endl;
return 0;
}
|
| 1000 1000! = 402387260077093773543702433923003985719374864210714632543799910429938512 39862902059204420848696940480047998861019719605863166687299480855890132382966994 45909974245040870737599188236277271887325197795059509952761208749754624970436014 18278094646496291056393887437886487337119181045825783647849977012476632889835955 73543251318532395846307555740911426241747434934755342864657661166779739666882029 12073791438537195882498081268678383745597317461360853795345242215865932019280908 78297308431392844403281231558611036976801357304216168747609675871348312025478589 32076716913244842623613141250878020800026168315102734182797770478463586817016436 50241536913982812648102130927612448963599287051149649754199093422215668325720808 21333186116811553615836546984046708975602900950537616475847728421889679646244945 16076535340819890138544248798495995331910172335555660213945039973628075013783761 53071277619268490343526252000158885351473316117021039681759215109077880193931781 14194545257223865541461062892187960223838971476088506276862967146674697562911234 08243920816015378088989396451826324367161676217916890977991190375403127462228998 80051954444142820121873617459926429565817466283029555702990243241531816172104658 32036786906117260158783520751516284225540265170483304226143974286933061690897968 48259012545832716822645806652676995865268227280707578139185817888965220816434834 48259932660433676601769996128318607883861502794659551311565520360939881806121385 58600301435694527224206344631797460594682573103790084024432438465657245014402821 88525247093519062092902313649327349756551395872055965422874977401141334696271542 28458623773875382304838656889764619273838149001407673104466402598994902222217659 04339901886018566526485061799702356193897017860040811889729918311021171229845901 64192106888438712185564612496079872290851929681937238864261483965738229112312502 41866493531439701374285319266498753372189406942814341185201580141233448280150513 99694290153483077644569099073152433278288269864602789864321139083506217095002597 38986355427719674282224875758676575234422020757363056949882508796892816275384886 33969099598262809561214509948717012445164612603790293091208890869420285106401821 54399457156805941872748998094254742173582401063677404595741785160829230135358081 84009699637252423056085590370062427124341690900415369010593398383577793941097002 77534720000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000 |
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe