W tym poście podam trzy sposoby rozwiązania tego problemu, ale wpierw wyjaśnijmy jedną rzecz:
"[...] część całkowita z -0.43 powinna chyba wynosić 0?", thenkles.
Otóż nie! Wynika to wprost z definicji matematycznej:
Część całkowita liczby x to największa z liczb całkowitych mniejszych lub równych x
Czyli część całkowita z -0.43 wynosi -1. Skoro już wiemy czego szukamy, zdefiniujmy formalnie nasz problem:
Dane wejściowe: Nieujemna liczba wymierna k w postaci skończonego rozwinięcia dziesiętnego.
Wynik: Część całkowita liczby k.
Pierwsze, najbardziej narzucające się rozwiązanie:
CZĘŚĆ-CAŁKOWITA-1(k>=0)
1 i=1
2 Wykonuj do chwili gdy i>k
2.1 i=i+1
3 return i-1
To chyba najbardziej czytelne, ale jednocześnie najbardziej czasochłonne rozwiązanie. Na początku zakładamy że wynikiem jest i=0. Następnie liczbę i zwiększamy o +1 tyle razy aż i będzie większe od k. Ostatecznie i-1 jest częścią całkowitą k.
Ile razy program będzie wykonywał główną pętlę (2.1)? k-razy.
Więc jaka jest jego złożoność obliczeniowa? Liniowa, czyli równa O(n).
Za tak brzydki program powinniśmy zostać ukarani ! Szybko zaimplementowałem go na potwornie powolnej platformie programistycznej jaką bez wątpienia jest interpretowana Java i zażądałem części całkowitej z liczby 10000.342. Niestety wynik otrzymałem natychmiastowo.
W tym miejscu należy sobie zadać pytanie: Jak duża może być wartość wejściowa k? Jeżeli już na etapie specyfikacji wiemy, że 10000>k>=0, to prawdopobnie możemy pozostać przy algorytmie CZĘŚĆ-CAŁKOWITA-1(k).
Załóżmy że k>10000. Jak usprawnić nasz algorytm?
Podzielmy kod na dwie części, w pierwszej będziemy chcieli z grubsza oszacować wielkość i, a następnie przejdziemy do wyszukiwania precyzyjnej wartości posługując się w rzeczywistości podanym powyżej algorytmem.
CZĘŚĆ-CAŁKOWITA-2(k>=1)
1 i=2
2 Wykonuj do chwili gdy i>k
2.1 i=i*2
3 i=i/2
4 Wykonuj do chwili gdy i>k
4.1 i=i+1
5 return i-1
(kontynuacja w kolejnym poście, w tym się nie mieści. Swoją drogą ktoś mógłby mi powiedzieć jaki jest limit ilości znaków w jednym poście?, oszczędziło by mi to pracy ...)