开发者

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜