由现今的考古证据可以推测人类计数的历史至少有五万年,并由此发展导致出数学符号及记数系统的发展。
做CF的时一有意思的计数问题
使用 A-Z 26个表示计数,第1个是A,第2个是B,...,第26个是Z;然后是两个字母表示:27是AA,28是AB, 52是AZ;然后是3个数字来表示...
标号系统
单记号系统
数字系统转换的问题,对于数字系统,先由一个极端的例子说起,假设只有一个标记A
标号 数字
A 1
AA 2
AAA 3
AAAA 4
... ...
显然得到的是一个一进制系统,每个位的权重均为1,A的个数即为数值。
数学化表达:
$$sum = \sum{k=0}^n vknk $$
注:
vk表示权重,此时权重均为1,n_k表示当前的值.
双符号系统
本数字系统有两个标记:A B
标号 数字
A 1
B 2
AA 3
AB 4
AAA 5
AAB 6
... ...
显然得到的是一个二进制系统,每个位的权重均为2,但该二进制系统是1-2系统(A的数值为1,B的数值为2)
数学化表达:
$$sum = \sum{k=0}^n vknk $$
注:
vk表示权重,此时权重均为1,2,4,..,n_k表示当前的值.
多符号系统
使用26个标记:A - Z
标号 数字
A 1
B 2
C 3
...
Z 26
AA 27
AB 28
...
AZ 52
BA 53
AAA
...
显然得到的是一个26进制系统,每个位的权重均为2,但该二进制系统是1-26系统(A-1,B-2,C-3,...,Z-26)
数学化表达:
数学化表达:
$$sum = \sum{k=0}^n vknk $$
注:
vk表示权重,此时权重均为1,26,26^2,..,n_k表示当前的值.
数值系统的转换
之前的的数学化表示只是由标号系统到十进制。现在考虑一下十进制到标号系统;任意标号系统间转换
十进制 到 标号系统
与一般的二进制区别主要在于不是0-1系统而是1-2系统,所以转换从低位到高位进行:
标号系统到十进制
void deal(char arr[])
{
int j = 0, c = 0, r = 0;
while(arr[j] >= 'A' && arr[j] <= 'Z'){
c *= 26;
c += arr[j] - 'A' + 1;
j++;
}
for(;j < strlen(arr);j++){
r *= 10;
r += arr[j] - '0';
}
printf("%d\n", r);
}
}
十进制到标号系统
void deal(char arr[])
{
int len = strlen(arr), c = 0, j;
for(j = 0;j < len;j++){
c *= 10;
c += arr[j] - '0';
}
char re[10] = {0};
j = 0;
while(c){
re[j] = (c-1)%26 + 'A';
j++;
c = (c-1) / 26;
}
for(j--;j >=0;j--)
printf("%c", re[j]);
}
}
任意标号间的转换
可以将十进制作为中间值来两步转换
结语
废话这么多,简而言之:非0-(n-1)符号系统,1-n系统。