使用最小的可能基数表示 d 位上的整数
Represent integers on d digits using smallest possible base
我想创建一个函数，其中对于任意整数输入值（比如无符号 32 位）和给定的 d 位数，return 值将是 d 数字 B 基数，B 是可用于表示 d 数字上给定输入的最小基数。
这是一个示例输入 - 我想到的 3 位数字的输出：
Input Output
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1
8 0 0 2
9 0 1 2
10 1 0 2
11 1 1 2
12 0 2 0
13 0 2 1
14 1 2 0
15 1 2 1
16 2 0 0
17 2 0 1
18 2 1 0
19 2 1 1
20 0 2 2
21 1 2 2
22 2 0 2
23 2 1 2
24 2 2 0
25 2 2 1
26 2 2 2
27 0 0 3
28 0 1 3
29 1 0 3
30 1 1 3
.. .....
赋值应该是1:1，对于每个输入值，应该只有一个唯一的输出值。把它想象成函数应该 return 来自奇怪排序的 B 基数列表的 nth 值。
实际上，这是迄今为止我能想到的唯一方法 - 给定一个输入值，以尽可能小的 B 为基数生成所有数字，以表示 d 数字上的输入，然后对结果应用自定义排序（'penalizing' 较高的数字值并将它们放在排序的后面），以及 return 来自已排序数组的 nth 值。这会起作用，但这是一个非常低效的实现 - 我想在不生成输入值的所有数字的情况下执行此操作。
实现此功能的有效方法是什么？任何语言或伪代码都可以。
假设所有值都是正数，让我们做一个简单的数学运算：
d-digit B-based number 可以容纳值 N if
Bd > N
所以
B > N1/d
所以计算N1/d的值，向上取整（整数则递增），得到最小的底数B。
(注意可能会出现数值错误)
示例：
d=2, N=99 => 9.95 => B=10
d=2, N=100 => 10 => B=11
d=2, N=57 => 7.55 => B=8
d=2, N=33 => 5.74 => B=6
Delphi代码
function GetInSmallestBase(N, d: UInt32): string;
const
Digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
Base, i: Byte;
begin
Base := Ceil(Power(N, 1/d) + 1.0E-12);
if Base > 36 then
Exit('Big number, few digits...');
SetLength(Result, d);
for i := d downto 1 do begin
Result[i] := Digits[1 + N mod Base]; //Delphi string is 1-based
N := N div Base;
end;
Result := Result + Format(' : base [%d]', [Base]);
end;
begin
Memo1.Lines.Add(GetInSmallestBase(99, 2));
Memo1.Lines.Add(GetInSmallestBase(100, 2));
Memo1.Lines.Add(GetInSmallestBase(987, 2));
Memo1.Lines.Add(GetInSmallestBase(1987, 2));
Memo1.Lines.Add(GetInSmallestBase(87654321, 6));
Memo1.Lines.Add(GetInSmallestBase(57, 2));
Memo1.Lines.Add(GetInSmallestBase(33, 2));
99 : base [10]
91 : base [11]
UR : base [32]
Big number, few digits...
H03LL7 : base [22]
71 : base [8]
53 : base [6]
MBo 的回答显示了如何找到最小的基数来表示具有给定位数的整数。
我不太确定您示例中的顺序。我的答案是基于不同的顺序：创建所有可能的 n 位数字，直到基数 b（例如，所有数字最多为 999 的最大值。基数 10 和 3 位数字）。首先根据最大数字对它们进行排序。数字在具有相同最大数字的组内正常排序。这保留了从8到26的所有值必须以3为底的特性，但内部排序不同：
8 0 0 2
9 0 1 2
10 0 2 0
11 0 2 1
12 0 2 2
13 1 0 2
14 1 1 2
15 1 2 0
16 1 2 1
17 1 2 2
18 2 0 0
19 2 0 1
20 2 0 2
21 2 1 0
22 2 1 1
23 2 1 2
24 2 2 0
25 2 2 1
26 2 2 2
当你的基数是二时，生活很简单：只需生成合适的二进制数。
其他基数，我们看第一个数字。在上面的例子中，五个数字以0开头，五个数字以1开头，九个数字以2开头。当第一个数字为2时，最大数字保证为2。因此，我们可以将2与9个2位数字组合基数 3.
当第一个数字小于组中的最大数字时，我们可以将其与9个3进制的2位数字组合，但不能使用与组中有歧义的4个2位数字4 以 2 为基数的 2 位数字。这为数字 0 和 1 提供了五种可能性。这些可能性 - 02、12、20、21 和 22 - 可以描述为根据相同方案的两位数的唯一数字，但有一个偏移量：
4 0 2
5 1 2
6 2 0
7 2 1
8 2 2
这导致递归解决方案：
- 对于一个数字，只是 return 数字本身；
- 对于基数 2，return 基数 2 的直接表示；
- 如果第一个数字是确定基数的最大数字，则将其与该基数中的直接表示相结合；
- 否则将其与递归确定的相同算法的表示相结合，少一位。
这是 Python 中的示例。表示形式是 returned 作为数字列表，因此您可以将 2^32 − 1 表示为 [307, 1290, 990]。
import math
def repres(x, ndigit, base):
"""Straightforward representation of x in given base"""
s = []
while ndigit:
s += [x % base]
x /= base
ndigit -= 1
return s
def encode(x, ndigit):
"""Encode according to min-base, fixed-digit order"""
if ndigit <= 1:
return [x]
base = int(x ** (1.0 / ndigit)) + 1
if base <= 2:
return repres(x, ndigit, 2)
x0 = (base - 1) ** ndigit
nprev = (base - 1) ** (ndigit - 1)
ncurr = base ** (ndigit - 1)
ndiff = ncurr - nprev
area = (x - x0) / ndiff
if area < base - 1:
xx = x0 / (base - 1) + x - x0 - area * ndiff
return [area] + encode(xx, ndigit - 1)
xx0 = x0 + (base - 1) * ndiff
return [base - 1] + repres(x - xx0, ndigit - 1, base)
for x in range(32):
r = encode(x, 3)
print x, r
我想创建一个函数，其中对于任意整数输入值（比如无符号 32 位）和给定的 d 位数，return 值将是 d 数字 B 基数，B 是可用于表示 d 数字上给定输入的最小基数。
这是一个示例输入 - 我想到的 3 位数字的输出：
Input Output
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1
8 0 0 2
9 0 1 2
10 1 0 2
11 1 1 2
12 0 2 0
13 0 2 1
14 1 2 0
15 1 2 1
16 2 0 0
17 2 0 1
18 2 1 0
19 2 1 1
20 0 2 2
21 1 2 2
22 2 0 2
23 2 1 2
24 2 2 0
25 2 2 1
26 2 2 2
27 0 0 3
28 0 1 3
29 1 0 3
30 1 1 3
.. .....
赋值应该是1:1，对于每个输入值，应该只有一个唯一的输出值。把它想象成函数应该 return 来自奇怪排序的 B 基数列表的 nth 值。
实际上，这是迄今为止我能想到的唯一方法 - 给定一个输入值，以尽可能小的 B 为基数生成所有数字，以表示 d 数字上的输入，然后对结果应用自定义排序（'penalizing' 较高的数字值并将它们放在排序的后面），以及 return 来自已排序数组的 nth 值。这会起作用，但这是一个非常低效的实现 - 我想在不生成输入值的所有数字的情况下执行此操作。
实现此功能的有效方法是什么？任何语言或伪代码都可以。
假设所有值都是正数，让我们做一个简单的数学运算：
d-digit B-based number 可以容纳值 N if
Bd > N
所以
B > N1/d
所以计算N1/d的值，向上取整（整数则递增），得到最小的底数B。
(注意可能会出现数值错误)
示例：
d=2, N=99 => 9.95 => B=10
d=2, N=100 => 10 => B=11
d=2, N=57 => 7.55 => B=8
d=2, N=33 => 5.74 => B=6
Delphi代码
function GetInSmallestBase(N, d: UInt32): string;
const
Digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
Base, i: Byte;
begin
Base := Ceil(Power(N, 1/d) + 1.0E-12);
if Base > 36 then
Exit('Big number, few digits...');
SetLength(Result, d);
for i := d downto 1 do begin
Result[i] := Digits[1 + N mod Base]; //Delphi string is 1-based
N := N div Base;
end;
Result := Result + Format(' : base [%d]', [Base]);
end;
begin
Memo1.Lines.Add(GetInSmallestBase(99, 2));
Memo1.Lines.Add(GetInSmallestBase(100, 2));
Memo1.Lines.Add(GetInSmallestBase(987, 2));
Memo1.Lines.Add(GetInSmallestBase(1987, 2));
Memo1.Lines.Add(GetInSmallestBase(87654321, 6));
Memo1.Lines.Add(GetInSmallestBase(57, 2));
Memo1.Lines.Add(GetInSmallestBase(33, 2));
99 : base [10]
91 : base [11]
UR : base [32]
Big number, few digits...
H03LL7 : base [22]
71 : base [8]
53 : base [6]
MBo 的回答显示了如何找到最小的基数来表示具有给定位数的整数。
我不太确定您示例中的顺序。我的答案是基于不同的顺序：创建所有可能的 n 位数字，直到基数 b（例如，所有数字最多为 999 的最大值。基数 10 和 3 位数字）。首先根据最大数字对它们进行排序。数字在具有相同最大数字的组内正常排序。这保留了从8到26的所有值必须以3为底的特性，但内部排序不同：
8 0 0 2
9 0 1 2
10 0 2 0
11 0 2 1
12 0 2 2
13 1 0 2
14 1 1 2
15 1 2 0
16 1 2 1
17 1 2 2
18 2 0 0
19 2 0 1
20 2 0 2
21 2 1 0
22 2 1 1
23 2 1 2
24 2 2 0
25 2 2 1
26 2 2 2
当你的基数是二时，生活很简单：只需生成合适的二进制数。
其他基数，我们看第一个数字。在上面的例子中，五个数字以0开头，五个数字以1开头，九个数字以2开头。当第一个数字为2时，最大数字保证为2。因此，我们可以将2与9个2位数字组合基数 3.
当第一个数字小于组中的最大数字时，我们可以将其与9个3进制的2位数字组合，但不能使用与组中有歧义的4个2位数字4 以 2 为基数的 2 位数字。这为数字 0 和 1 提供了五种可能性。这些可能性 - 02、12、20、21 和 22 - 可以描述为根据相同方案的两位数的唯一数字，但有一个偏移量：
4 0 2
5 1 2
6 2 0
7 2 1
8 2 2
这导致递归解决方案：
- 对于一个数字，只是 return 数字本身；
- 对于基数 2，return 基数 2 的直接表示；
- 如果第一个数字是确定基数的最大数字，则将其与该基数中的直接表示相结合；
- 否则将其与递归确定的相同算法的表示相结合，少一位。
这是 Python 中的示例。表示形式是 returned 作为数字列表，因此您可以将 2^32 − 1 表示为 [307, 1290, 990]。
import math
def repres(x, ndigit, base):
"""Straightforward representation of x in given base"""
s = []
while ndigit:
s += [x % base]
x /= base
ndigit -= 1
return s
def encode(x, ndigit):
"""Encode according to min-base, fixed-digit order"""
if ndigit <= 1:
return [x]
base = int(x ** (1.0 / ndigit)) + 1
if base <= 2:
return repres(x, ndigit, 2)
x0 = (base - 1) ** ndigit
nprev = (base - 1) ** (ndigit - 1)
ncurr = base ** (ndigit - 1)
ndiff = ncurr - nprev
area = (x - x0) / ndiff
if area < base - 1:
xx = x0 / (base - 1) + x - x0 - area * ndiff
return [area] + encode(xx, ndigit - 1)
xx0 = x0 + (base - 1) * ndiff
return [base - 1] + repres(x - xx0, ndigit - 1, base)
for x in range(32):
r = encode(x, 3)
print x, r