Skośny system dwójkowy: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
kolejność |
program |
||
Linia 105:
Liczby skośne mogą być również użyte do implementacji [[kolejka (informatyka)|kolejek]] z dostępem swobodnym w językach funkcyjnych.
== Przykład implementacji ==
Przykład operacji dodawania, oraz konwersji na liczbę lub notację pozycyjną. Używa formatu rzadkiej w notacji wykładnikowej, np. 92 = [2,2,3,5].
<source lang="erlang">
zero() -> [].
% Operacja inc wykonuje się w czasie stałym!
inc([X,X|T]) -> [X+1|T];
inc([X|T]) -> [0,X|T];
inc([]) -> [0].
% [2,2,3,5] -> 92.
to_number([]) -> 0;
to_number(L) -> to_number(L, 0).
to_number([X | T], Acc) -> to_number(T, Acc + ((1 bsl (X+1)) - 1));
to_number([], Acc) -> Acc.
% [2,2,3,5] -> "101200".
to_display([]) -> [$0];
to_display(L) -> to_display(L, [], false, 0).
to_display([X,X|T], Acc, _, X) -> to_display(T, [$2 | Acc], false, X+1);
to_display([X|T], Acc, _, X) -> to_display(T, [$1 | Acc], false, X+1);
to_display([_|_T]=L, Acc, _, X) -> to_display(L, [$0 | Acc], true, X+1);
to_display([], Acc, true, _X) -> [$1 | Acc];
to_display([], Acc, false, _X) -> Acc.
% pokazuje pierwsze N liczb
first(N) -> lists:foldl(fun(I, X) ->
io:format("~p: \t~p = ~p \t= ~p~n", [I-1, X, ral:to_number(X), ral:to_display(X)]),
ral:inc(X)
end, [], lists:seq(1, N)).
</source>
Wynik działania
first(101).
0: [] = 0 = "0"
1: [0] = 1 = "1"
2: [0,0] = 2 = "2"
3: [1] = 3 = "10"
4: [0,1] = 4 = "11"
5: [0,0,1] = 5 = "12"
6: [1,1] = 6 = "20"
7: [2] = 7 = "100"
8: [0,2] = 8 = "101"
9: [0,0,2] = 9 = "102"
10: [1,2] = 10 = "110"
11: [0,1,2] = 11 = "111"
12: [0,0,1,2] = 12 = "112"
13: [1,1,2] = 13 = "120"
14: [2,2] = 14 = "200"
15: [3] = 15 = "1000"
...
90: [0,0,1,2,3,5] = 90 = "101112"
91: [1,1,2,3,5] = 91 = "101120"
92: [2,2,3,5] = 92 = "101200"
93: [3,3,5] = 93 = "102000"
94: [4,5] = 94 = "110000"
95: [0,4,5] = 95 = "110001"
96: [0,0,4,5] = 96 = "110002"
97: [1,4,5] = 97 = "110010"
98: [0,1,4,5] = 98 = "110011"
99: [0,0,1,4,5] = 99 = "110012"
100: [1,1,4,5] = 100 = "110020"
== Zobacz też ==
| |||