Matematyka.pl

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?

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.

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.

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}}\)

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.

pawellogrd, reszta z dzielenia zawsze jest nieujemna.

pawellogrd, abc666, dziękuję najmocniej za wyjaśnienie

abc666 pisze:pawellogrd, reszta z dzielenia zawsze jest nieujemna.

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.

zawsze można uzyc jakiejś biblioteki zewnętrznej (albo po prostu if'a) żeby wyciągnąc wartośc bezwzględną

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.

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.

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.

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"

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.