[Systemy liczbowe] Różne systemy pozycyjne.
-
- Użytkownik
- Posty: 1824
- Rejestracja: 11 sty 2007, o 20:12
- Płeć: Mężczyzna
- Lokalizacja: Katowice, Warszawa
- Podziękował: 73 razy
- Pomógł: 228 razy
[Systemy liczbowe] Różne systemy pozycyjne.
Mamy system pozycyjny o podstawie \(\displaystyle{ (-2)}\), w którym mamy cyfry \(\displaystyle{ 0}\) oraz \(\displaystyle{ 1}\). W jaki sposób mogę na ten system zamienić liczbę z systemu dziesiętnego? Czy w ogóle istnieje jakiś algorytm, który pozwala na przechodzenia z jednego systemu do drugiego nawet w takich "mniej sensownych" przypadkach?
-
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
[Systemy liczbowe] Różne systemy pozycyjne.
Uniwersalnym sposobem przejścia z jednego systemu na drugi jest konwersja z tego systemu do dziesiętnego, a następnie z dziesiętnego do docelowego. Niezależnie od systemu konwersję z/do dziesiętnego wykonuje się w taki sam sposób.
-
- Użytkownik
- Posty: 1824
- Rejestracja: 11 sty 2007, o 20:12
- Płeć: Mężczyzna
- Lokalizacja: Katowice, Warszawa
- Podziękował: 73 razy
- Pomógł: 228 razy
[Systemy liczbowe] Różne systemy pozycyjne.
W takim razie jak przejdziesz z liczby \(\displaystyle{ 42}\) do systemu o podstawie \(\displaystyle{ (-2)}\)? Można strzelać, że jest to \(\displaystyle{ (1111110)_{-2}}\), ale ja jakoś nie widzę, jak to zalgorytmizować. Dzielenie przez \(\displaystyle{ -2}\) i branie reszt też za bardzo nie wychodzi.
[Systemy liczbowe] Różne systemy pozycyjne.
Trzeba pamiętać, że mamy ujemne liczby i uważać przy reszcie
\(\displaystyle{ \begin{array}{cllcc}{ 42 &:& (-2) = -21&r&0\\
-21 &:& (-2) = 11&r&1\\
11 &:& (-2) = -5&r&1\\
-5 &:& (-2) = 3&r&1\\
3 &:& (-2) = -1&r&1\\
-1 &:& (-2) = 1&r&1\\
1 &:& (-2) = 0&r&1} \end{array}}\)
-
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
[Systemy liczbowe] Różne systemy pozycyjne.
Istotna jest sprawa jak konwertować liczby z systemu dziesiętnego na systemy o ujemnej podstawie, bo tutaj z tym widzę się pojawił problem (trudno się dziwić, bo informacji o tym jak na lekarstwo można znaleźć). Załóżmy, że chcemy przekonwertować na system o podstawie \(\displaystyle{ -r}\). Wtedy bierzesz liczbę, dzielisz ją całkowicie przez \(\displaystyle{ -r}\) i spisujesz resztę z tego dzielenia. Reszta może być z zakresu \(\displaystyle{ (-r+1,...,0,...,r-1)}\), np. dla systemu negabinarnego reszta będzie wynosić \(\displaystyle{ -1 \vee 0 \vee 1}\). Jeżeli reszta jest ujemna to robisz dwie rzeczy:
1. Do aktualnej liczby (wynik dzielenia całkowitego) dodajesz \(\displaystyle{ 1}\).
2. Do otrzymanej reszty dodajesz \(\displaystyle{ |-r|=r}\) czyli dla systemu negabinarnego dodajesz do ujemnych reszt \(\displaystyle{ 2}\).
Jeżeli reszta była dodatnia to nic nie zmieniasz. Dalej powtarzasz takie dzielenie dopóki wynik nie będzie \(\displaystyle{ 0}\), przy czym reszta otrzymana z dzielenia, którego wynikiem jest \(\displaystyle{ 0}\) musi być dodatnia. Czyli dla Twojej liczby będzie to tak:
Liczba dziesiętna: \(\displaystyle{ 42}\)
1. \(\displaystyle{ 42/(-2)=-21, \mbox{ reszty }0}\)
Reszta dodatnia, więc zostawiamy bez zmian.
2. \(\displaystyle{ -21/(-2)=10, \mbox{ reszty }-1}\)
Reszta ujemna, więc do liczby dodajemy \(\displaystyle{ 1}\), a do reszty \(\displaystyle{ 2}\) więc zamiast powyższego mamy aktualną liczbę \(\displaystyle{ 10+1=11}\) oraz resztę \(\displaystyle{ -1+2=1}\).
3. \(\displaystyle{ (10+1)/(-2)=-5, \mbox{ reszty }1}\)
4. \(\displaystyle{ -5/(-2)=2, \mbox{ reszty }-1}\)
Po zmianach: liczba \(\displaystyle{ 2+1=3}\) oraz reszta \(\displaystyle{ -1+2=1}\)
5. \(\displaystyle{ (2+1)/(-2)=-1, \mbox{ reszty }1}\)
6. \(\displaystyle{ -1/(-2)=0, \mbox{ reszty }-1}\)
Po zmianach: liczba \(\displaystyle{ 0+1=1}\) oraz reszta \(\displaystyle{ -1+2=1}\).
7. \(\displaystyle{ (0+1)/(-2)=0, \mbox{ reszty }1}\)
Wynikiem dzielenia jest \(\displaystyle{ 0}\) oraz reszta jest dodatnia, więc kończymy konwersję.
Więc spisujemy reszty od końca i otrzymujemy postać negabinarną: \(\displaystyle{ 1111110}\).
EDIT: Widzę, że powyżej już zostało napisane jak to zrobić, być może w nieco prostszy sposób nawet dla człowieka, bo nie trzeba się z ujemnymi resztami bawić, ale jeśli chcesz napisać algorytm do tego, który wykonuje dzielenie całkowite to będziesz to musiał zrobić w taki sposób jak opisałem, bo będzie otrzymywał ujemne reszty.
1. Do aktualnej liczby (wynik dzielenia całkowitego) dodajesz \(\displaystyle{ 1}\).
2. Do otrzymanej reszty dodajesz \(\displaystyle{ |-r|=r}\) czyli dla systemu negabinarnego dodajesz do ujemnych reszt \(\displaystyle{ 2}\).
Jeżeli reszta była dodatnia to nic nie zmieniasz. Dalej powtarzasz takie dzielenie dopóki wynik nie będzie \(\displaystyle{ 0}\), przy czym reszta otrzymana z dzielenia, którego wynikiem jest \(\displaystyle{ 0}\) musi być dodatnia. Czyli dla Twojej liczby będzie to tak:
Liczba dziesiętna: \(\displaystyle{ 42}\)
1. \(\displaystyle{ 42/(-2)=-21, \mbox{ reszty }0}\)
Reszta dodatnia, więc zostawiamy bez zmian.
2. \(\displaystyle{ -21/(-2)=10, \mbox{ reszty }-1}\)
Reszta ujemna, więc do liczby dodajemy \(\displaystyle{ 1}\), a do reszty \(\displaystyle{ 2}\) więc zamiast powyższego mamy aktualną liczbę \(\displaystyle{ 10+1=11}\) oraz resztę \(\displaystyle{ -1+2=1}\).
3. \(\displaystyle{ (10+1)/(-2)=-5, \mbox{ reszty }1}\)
4. \(\displaystyle{ -5/(-2)=2, \mbox{ reszty }-1}\)
Po zmianach: liczba \(\displaystyle{ 2+1=3}\) oraz reszta \(\displaystyle{ -1+2=1}\)
5. \(\displaystyle{ (2+1)/(-2)=-1, \mbox{ reszty }1}\)
6. \(\displaystyle{ -1/(-2)=0, \mbox{ reszty }-1}\)
Po zmianach: liczba \(\displaystyle{ 0+1=1}\) oraz reszta \(\displaystyle{ -1+2=1}\).
7. \(\displaystyle{ (0+1)/(-2)=0, \mbox{ reszty }1}\)
Wynikiem dzielenia jest \(\displaystyle{ 0}\) oraz reszta jest dodatnia, więc kończymy konwersję.
Więc spisujemy reszty od końca i otrzymujemy postać negabinarną: \(\displaystyle{ 1111110}\).
EDIT: Widzę, że powyżej już zostało napisane jak to zrobić, być może w nieco prostszy sposób nawet dla człowieka, bo nie trzeba się z ujemnymi resztami bawić, ale jeśli chcesz napisać algorytm do tego, który wykonuje dzielenie całkowite to będziesz to musiał zrobić w taki sposób jak opisałem, bo będzie otrzymywał ujemne reszty.
-
- Użytkownik
- Posty: 1824
- Rejestracja: 11 sty 2007, o 20:12
- Płeć: Mężczyzna
- Lokalizacja: Katowice, Warszawa
- Podziękował: 73 razy
- Pomógł: 228 razy
-
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
[Systemy liczbowe] Różne systemy pozycyjne.
Jesteś pewien? Weź liczbę \(\displaystyle{ -21}\) i wykonaj dzielenie modulo przez \(\displaystyle{ -2}\) w jakimś języku programowania. Otrzymasz \(\displaystyle{ -1}\) Albo wykonaj sobie dzielenie całkowite - otrzymasz w wyniku \(\displaystyle{ 10}\). Czyli resztą jest właśnie \(\displaystyle{ -1}\), co oczywiśćie wiąże się z tym dzieleniem modulo.abc666 pisze:pawellogrd, reszta z dzielenia zawsze jest nieujemna.
-
- Użytkownik
- Posty: 18
- Rejestracja: 7 gru 2012, o 23:15
- Płeć: Mężczyzna
- Lokalizacja: Kruszwica
- Pomógł: 2 razy
[Systemy liczbowe] Różne systemy pozycyjne.
zawsze można uzyc jakiejś biblioteki zewnętrznej (albo po prostu if'a) żeby wyciągnąc wartośc bezwzględną
-
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
[Systemy liczbowe] Różne systemy pozycyjne.
Ale tutaj wcale nie masz mieć wartość bezwzględną. Może i w negabinarnym tak, ale w negaternarnym już to nie zadziała - jeśli otrzymasz resztę \(\displaystyle{ -2}\) to masz ją zmienić na \(\displaystyle{ -2+3=1}\), a nie na \(\displaystyle{ 2}\). A poza tym wynik dzielenia i tak trzeba zmienić. Więc to, co napisałem, to tak naprawdę prosty algorytm ale innego sposobu raczej nie ma.
[Systemy liczbowe] Różne systemy pozycyjne.
pawellogrd, mówię o tym jak zdefiniowana jest reszta z dzielenia w matematyce. Jeśli dopuścisz ujemną resztę to możemy wtedy dostać, że
\(\displaystyle{ 5:2=3\text{ r } -1}\)
Czy w większości języków programowania podawany jest błędny wynik - tak
Czy można go łatwo "naprawić" - tak
Czy podałeś algorytm jak to zrobić - tak
Osobiście bym polecał raczej napisać własną funkcyjkę mod, która podaje dobry wynik. Wtedy nie musimy nic zmieniać w ogólnym algorytmie.
\(\displaystyle{ 5:2=3\text{ r } -1}\)
Czy w większości języków programowania podawany jest błędny wynik - tak
Czy można go łatwo "naprawić" - tak
Czy podałeś algorytm jak to zrobić - tak
Osobiście bym polecał raczej napisać własną funkcyjkę mod, która podaje dobry wynik. Wtedy nie musimy nic zmieniać w ogólnym algorytmie.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Systemy liczbowe] Różne systemy pozycyjne.
Czasami wynik dzielenia z resztą jest niezdefiniowany w obrębie samego języka i zależy od implementacji, z tego też powodu w języku C istnieje na przykład ta funkcja: Dlatego często lepiej jest napisać własną implementację, aby ustrzec się od błędów.
-
- Użytkownik
- Posty: 1824
- Rejestracja: 11 sty 2007, o 20:12
- Płeć: Mężczyzna
- Lokalizacja: Katowice, Warszawa
- Podziękował: 73 razy
- Pomógł: 228 razy
[Systemy liczbowe] Różne systemy pozycyjne.
To może kolejny problem: mają daną liczbę \(\displaystyle{ n}\) zapisaną w systemie negabinarnym, napisać funkcję, która działając na cyfrach liczby \(\displaystyle{ n}\), zwróci wartość \(\displaystyle{ n+1}\).
Ustalmy, że nie stosujemy ciosów poniżej pasa typu "zamieńmy na dziesiętny, dodajmy jedynkę i zamieńmy z powrotem"
Ustalmy, że nie stosujemy ciosów poniżej pasa typu "zamieńmy na dziesiętny, dodajmy jedynkę i zamieńmy z powrotem"
-
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
[Systemy liczbowe] Różne systemy pozycyjne.
abc666, Afish, oczywiście w ten sposób też można, to zależy już od podejścia, ew. od języka. Ale zgadzam się rzecz jasna z tym, co napisaliście.
Marcinek665, popatrz na to: - może coś pomoże.
Marcinek665, popatrz na to: - może coś pomoże.