Szukam algorytmu, który pozwala na zaokrąglenie liczby w dół. Niestety mogę używać tylko podstawowych działań matematycznych. Szukałem źródeł funkcji floor(), ale jest tam tylko odwołanie do funkcji trunc(), której już nie udało mi się znaleźć. Właściwie nie musi to być nawet floor, obcięcie końcówki ułamkowej, jak w trunc() zupełnie by wystarczyło, ponieważ liczby mają być nieujemne. Ale pomotałem :). Mam jednak nadzieję, że ktoś zna rozwiązanie tego problemu.
Pozdrówka
Chwila. Jak masz zapisaną liczbę? Chodzi ci jak wyzerować odpowienie bity (przy zapisie stałoprzecinkowym) lub dopasować cechę i mantysę (przy zapisie zmienno przecinkowym)?
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers.net
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
Mam po prostu dowolną liczbę nieujemną, np. 1.836496 i chcę się pozbyć kocówki ułamkowej, czyli zostawić samo 1. Nie mogę użyć żadnych funkcji, bo właściwie ma to być użyte w algorytmie.
Pozdrówka
Mam po prostu dowolną liczbę nieujemną, np. 1.836496 i chcę się pozbyć kocówki ułamkowej, czyli zostawić samo 1. Nie mogę użyć żadnych funkcji, bo właściwie ma to być użyte w algorytmie.
Spytaj Kapustki :)
--
Vogel [Delphi 6 PE]
Life is just a dream, you know...
[Cowboy Bebop]
a nie przypadkiem trunc() ale nie bijcie :)
[cya]
Nie wiem w jakim Języku masz ten problem?
W DELPHI jest bardzo pomocna zmienna typu VARIANT.
Za pomocą niej możesz wykonać to zadanie. Z tym że zawsze zaokrągli w DÓŁ.
Oto procedura spełniająca to zadanie pod warunkiem że wpisana dana zmienno przecinkowa jest z przecinkiem a nie z kropką rozdzielającą.
(Oczywiście w wersji polskiej systemu).
JacekS
[browar] [browar] [browar]
"Małe piwko przed śniadaniem"
procedure TForm1.Button2Click(Sender: TObject);
var
i: integer;
x1:variant;
zrob dzielenie tej liczby na jeden bez reszty - dostaniesz tylko liczbe calkowita...
zrob dzielenie tej liczby na jeden bez reszty - dostaniesz tylko liczbe calkowita...
Hehe, problem w tym, że właśnie próbuję zrobić dzielenie całkowite za pomocą tego :).
a div b=floor(a/b)
Jednak nie ma to być żaden język programowania, tylko algorytm.
Pozdrówka
[niewinnosc]
Witaj thenkles.
Mam dwa pytania:
część całkowita liczby a
Oczywiście jest wiele różnych algorytmów, w zależności od tego jakie przyjmiemy ograniczenia.
Jednocześnie byłbym wdzięczny za sprecyzowanie zadania, tzn. czy chodzi o wyciągnięcie części całkowitej z podanej liczby, czy też może interesuje nas dokładność do np. 2 miejsc po przecinku, jeśli tak to który schemat zaokrąglania? 1.5 = 1 czy 2? itd.
Bowiem jak ktoś słusznie napisał (na tym forum)- kluczem do rozwiązania jest sprecyzowanie problemu.
Pozdrawiam
Co o tym wszystkim myślisz - Dryobates?
[niewinnosc]
No więc tak:
Mam nadzieję, że nie ma już żadnych wątpliwości co do tego, jak to ma wyglądać :)
Pozdrówka
Mam już kilka propozycji algorytmów, ale zanim je podam muszę wiedzieć z jakiego zakresu pochodzą dane wejściowe, czy są to liczby dodatnie?
Ciekawe czy wiecie ile wynosi część całkowita z liczby -0.43 ?
Pozdrawiam (i niecierpliwie czekam na odpowiedź)
[niewinnosc]
Wcześniej już mówiłem, że liczby mają być nieujemne, czyli od 0 w górę. A część całkowita z -0.43 powinna chyba wynosić 0?
Pozdrówka
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 ...)
[...] Wartości k=[0,1) wymagają osobnego potraktowania, wystarczy dodać jedną linijkę (ale jej tu nie podam, bo NIE WYŚWIETLA JEJ POPRAWNIE !).
Zauważmy że wiersze 4-5 to wcześniej wypisany algorytm. Nowością jest natomiast wstępne wymnażannie liczby i przez 2 (nie jest to przypadek, gdyż mnożenie przez 2 jest szybko realizowane przez mikroprocesor w postaci odpowiedniego przesunięcia bitowego).
A teraz ostatni algorytm:
Poruszyłem ten temat dziś, przy obiadowym stole. Zapytałem swoją 5 lat młodszą siostrę :"Anka, w jaki sposób byś obliczyła część całkowitą z pewnej liczby rzeczywistej? np. 43.52". Siostra odrobinę zdziwiona, że zadaję jej tak banalne pytanie szybko odpowiedziała "Bardzo łatwo, po prostu wszystko po przecinku wywalam, wszystko po przecinku out".
TO JEST TO !
Kluczem do szybkiego i prostego algorytmu jest potraktowanie liczby wejściowej k nie jako liczby typu rzeczywistego, tylko jako łańcuchu znaków, tzw. typu String.
Genialnie proste:
CZĘŚĆ-CAŁKOWITA-3(k>=0)
1 Zapisz liczbę k w postaci Stringu s1 //konwersja Double do String,s1=k
2 String s2=""
3 n=0
4 Jeśli s1[n]!="." to s2[n]=s1[n]
5 Zinterpretuj napis s2 jako liczbę całkowitą c //konwersja String do Int,c=s2
6 Return c
Inaczej mówiąc liczbę k zapisz jako napis (łańcuch znaków) s1 przepisuj kolejne znaki (char) z napisu s1 do napisu s2 tak długo aż napotkasz na znak kropki dziesiętnej (kropka dziesiętna czy przecinek dziesiętny jak myślicie?) a potem napis s2 odczytaj jako liczbę całkowitą (100% bezpieczna konwersja, pod warunkiem że wpisana liczba k była prawidłowa).
Ile razy program będzie wykonywał główną pętlę? Tyle razy ile jest cyfr w części całkowitej k (uwaga: można odnieść wrażenie że to jest błędna rekurencja, ale w istocie tak nie jest).
Ile jest takich cyfr w liczbie k? 1+log k (logarytm dziesiętny z k)
Więc jaka jest jego złożoność obliczeniowa? Logarytmicza, czyli równa O(log n). (Notacja wielkie O pomija stałe dlatego +1 do niej nie weszło)
Bez wątpienia jest to najefektywniejszy algorytm pod warunkiem że:
Do operacji elementarnych należy:
konwersja Double na String,
konwersja String na Integer,
sprawdzanie czy dwa znaki są takie same
konkatenacja (czyli rozszerzanie napisu s1 o literę s2[n])
dodawanie algebraiczne
Pozdrawiam i gratuluję tym, którzy doczytali do końca! :-)
[niewinnosc]
Ok udało się, miałem ogromne problemy z poprawnym wyświetleniem tego postu.
W jaki sposób napisać że k jest mniejsze od 2 żeby to wyświetlił ?
Ale nie chcę obchodzić problemu przez wpisanie 2>k !
Ponadto prawdopodobnie nie ma limitu znaków w poście, błąd polegał na tym że znak "jest mniejszy" był interpretowany jako polecenie HTML.
może nie zakumałem o co chodzi, ale wydaje mi się, że problem jest śmiesznie prosty - przynajmniej dla mnie ;-( .
mamy sobie round(); round jest o tyle niemiłe, że zaokrągla w górę, no więc trzeba posadzić if-a, który sprawdzi, czy część po przecinku (frac()) jest >= od 0.5 i jeśli tak, to zmiejszy wynik o jeden.
ale może po prostu nie zakumałem o co chodzi :-P .
Chyba nie przeczytałeś całej dyskusji. Chodziło o podanie algorytmu, który by to robił a nie skorzystanie z gotowej funkcji:
"[...] Jednak nie ma to być żaden język programowania, tylko algorytm", thenkles
trochę jaśniej?
Swoją drogą to już we wcześniejszych dyskusjach pojawiali się ludzie którzy mówili coś w stylu "być może nie rozumiem, ale czemu by nie skorzystać z takiej a takiej funkcji?" (np. przy okazji wyciągania pierwiastka dowolnego stopnia n z liczby x).
Powtarzam: jasne, jeśli masz dostępną odpowiednią funkcję to z niej korzystaj. Ja sam bym z niej skorzystał.
Ale jeśli takiej funkcji nie ma? Albo jesteś ciekaw jak ta funkcja działa (przecież ostatecznie ktoś musiał ją napisać, prawda?) to co wtedy robisz? (w twoim przypadku prawdopodobnie zmieniasz język programowania)
Pozdrawiam
Jee, działa. Drugi sposób, ten ze stringiem niestety też nie mógł być użyty, bo nie można było wykorzystać funkcji do konwersji typów, ani nawet traktować tekstu jako tablicę, czyli korzystać z tekst[nr literki]. Ale za to 1 sposób jest idealny :)
Wielkie dzięki [browar]
Pozdrówka
Świetnie. (szkoda że ten pomysł ze stringami nie wypalił, jest najszybszy).
Dryobates, mam nadzieję że na tym przykładzie zobaczyłeś jak kluczowe w programowaniu jest określenie operacji elementarnych... .
Thenkles, dzięki za tak ciekawy temat ! Już cie lubię chłopie !
Pozdrowienia
Dryobates, mam nadzieję że na tym przykładzie zobaczyłeś jak kluczowe w programowaniu jest określenie operacji elementarnych... .
Zgadza się, ale w realnym świecie (tzn. przy przełożeniu tego na konkretny język) nie jestem pewien, czy ten sposób z konwersją byłby szybszy (zwiększenie wartości rejestru i proste porównanie kontra rozpoznanie cyfry, pomnożenie jej przez odpowiednią potęgę dziesięciu i dodanie do reszty - kto wie, być może szybsze).
Co do znaku większości i mniejszości. Znak mniejszości wpisuj w postaci:
& l t ;
Oczywiście bez spacji (ampersand, "l", "t", średnik)
a większości:
& g t ; (czyli ampersand, "g", "t", średnik)
--
Jest jeszcze jeden błąd ... :)
--------Oficjalny kanał----------
Service for programmers w IRC:
Kanał: #4programmers.net
Serwer: warszawa.ircnet.pl
Sieć: POLNet
Port: 6667
Jestem pewien że algorytm 3 jest szybszy od 2, (czyli konwersja na String jest szybsza od zwiększania rejestru). Wynika to wprost ze złożoności:
algorytm 3 wykonuje pętlę niezależnie od wpisanych danych dokładnie 1+log n razy.
algorytm 2 pod tym względem jest zależny od wpisanej liczby,
w wariancie pesymistycznym liniowy O(n), czyli wykonuje pętlę n-k razy,
w wariancie optymistycznym (wtedy gdy wpisana liczba wynosi (2^k)-1 )jest logarytmiczny, ale podstawą logarytmu jest 2 (a nie 10, a to jest spora różnica) czyli wykonuje się (w najlepszym wypadku) log2 n
Czyli algorytm 2 jest pomiędzy (log2 n <-> n)
Istnieje jeszcze inny, wydajniejszy sposób zwiększania rejestru.
Niestety jest on niewątpliwie bardziej skomplikowany od wszystkich poprzednich metod (o czym możecie się przekonać na własne oczy) oraz, pomimo że jest szybszy od algorytmów 1 i 2 to i tak pozostaje w tyle za algorytmem 3 (o czym też możecie się przekonać na własne oczy).
Zapraszam do lektury:
Poniższy algorytm znajduje największą liczbę całkowitą c, która jest mniejsza (lub równa w szczególnym wypadku) od liczby rzeczywistej k. W istocie liczba c jest więc wprost z definicji częścią całkowitą liczby k.
CZĘŚĆ-CAŁKOWITA-4(k>=0)
1 c=0
2 while(k>=1)
2.1 i=1
2.2 while(i<=k)
2.2.1 i=i*10
2.3 i=i/10
2.4 n=i
2.5 while(i<=k)
2.5.1 i=i+j
2.6 i=i-j
2.7 c=c+i
2.8 k=k-i
3 return c
Mówiąc szczerze, ja sam czytam to z trudem.
Do czego się sprowadza ten algorytm? Zwiększamy liczbę "i" wymnażając ją przez 10 aż do chwili gdy będzie większa od k, wtedy cofamy się o jeden krok (2.3 i=i/10) i ponownie zwiększamy liczbę "i" tym razem mnożąc ją przez kolejne liczby naturalne do chwili gdy będzie większa od k. Wtedy ponownie cofamy się o jeden krok.
Ile wynosi liczba "i" w tym momencie? Wynosi tyle ile najbardziej znacząca cyfra k pomnożona przez odpowiednią potęgę 10, czyli jeśli k=7498.55 to w tej chwili i=7000.55
Ponadto c=0, na końcu programu c jest naszym wynikiem (3 return c) , natomiast w trakcie trwania programu c przechowuje sumy częściowe. Dlatego teraz (2.7 c=c+i) czyli c=7000 oraz (2.8 k=k-i) czyli k=498.55
Potem następuje ustalenie i=1 oraz wykonanie ciągu instrukcji po których
i=400, c=c+i=7400, k=k-i=98.55
Ostatecznie gdy k<1 (a dokładnie k=0.55) wtedy c=7498 i program kończy pracę.
Skoro mamy cztery algorytmy, porównajmy ich szybkości. Będziemy liczyć ile razy kolejne algorytmy będą musiały wchodzić do pętli algorytmu dla takiej samej wartości wejściowej k
Dla k=7498.55
CZĘŚĆ-CAŁKOWITA-1: wchodzi do pętli 7499 razy.
CZĘŚĆ-CAŁKOWITA-2: robi to 13+3402=3415 razy (13 razy mnożenie przez 2)
CZĘŚĆ-CAŁKOWITA-3: cztery razy! 4 (tyle jest cyfr po lewej stronie znaku ".")
CZĘŚĆ-CAŁKOWITA-4: 5+8+4+5+3+10+2+9=46 razy (sprawdźcie sami)
Wyrażając to w stosunkach względnych:
CZĘŚĆ-CAŁKOWITA-3: x
CZĘŚĆ-CAŁKOWITA-4: 11x
CZĘŚĆ-CAŁKOWITA-2: 853x
CZĘŚĆ-CAŁKOWITA-1: 1874x
Czy wszyscy są przekonani ?
Pozdrawiam.