Decimal to Base of Three System with a Twist
Everyone knows how to convert number from decimal system to binary. I also do. Everyone also knows how to convert from decimal to the base of three system.
However, I have a problem where I need to convert decimal number to a "strange base 3" system where one symbol cannot be the first one and should be surrounded by the remaining two. So, one symbol cannot be repeated before one of the other two has been used.
开发者_Python百科So, if "0" is the symbol that cannot be the first one and that cannot repeat:
perfectly legit numbers: 120, 110202, 1020
numbers that should not exist: 01212(zero should not be in the front), 120012 (zeros cannot repeat)
Can somebody, please, help to come up with an algorithm that converts from decimal system to this "strange base 3" system and back.
Thank you in advance
Is the following the desired mapping?
0 <- illegal
1 0
2 1
10 2
11 3
12 4
20 5
21 6
22 7
100 <- illegal
101 8
102 9
110 10
111 11
112 12
120 13
121 14
122 15
200 <- illegal
201 16
202 17
210 18
211 19
212 20
220 21
221 22
222 23
1000 <- illegal
1001 <- illegal
1002 <- illegal
1010 24
1011 25
1012 26
1020 27
1021 28
1022 29
1100 <- illegal
1101 30
1102 31
1110 32
1111 33
1112 34
1120 35
1121 36
1122 37
1200 <- illegal
1201 38
1202 39
1210 40
1211 41
1212 42
1220 43
1221 44
1222 45
2000 <- illegal
Based on @Daniel's mapping, from Dec to strange-3-based:
x := n; // Original number
y:= 0;
do
y0:= y;
z:= DecToThree(x); // Convert x from Decimal to 3-based.
y:= IllRep(z); // Calculate the number y of numbers with at least 2
// consecutive 0 with a representation in 3- based.
x:= n + y; // Add illegal representations to original number;
until (y = y0);
Result:= DezToThree(x); // Convert x from Decimal to 3-based.
Example:
16 -> 121 y = 2 // {0, 100}
16+2 -> 200 y = 3 // {0, 100, 200}
16+3-2 -> 201 y = 3
The other way around:
y:= IllRep(x); // calculate the number y of illegal representations
z:= ThreeToDec(x); // convert x from 3-based to dec
result:= z-y;
Now all you need is a function that finds all illegal representations up to a certain number.
精彩评论