3

如果要计数超过 8 位，以 2 为底，结果如下：

0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1;
0 0 0 0 0 0 1 0;
.....
1 1 1 1 1 1 1 1;

但是，您如何制作一个算法来计算 - 对于每个位 - 基于不同的基数，例如：如果最低有效位根据基数 5 计算，而最高有效位在基数 2 上，则结果应如下所示：

0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1;
0 0 0 0 0 0 0 2;
0 0 0 0 0 0 0 3;
0 0 0 0 0 0 0 4;
1 0 0 0 0 0 0 0;
1 0 0 0 0 0 0 1;
1 0 0 0 0 0 0 2;
...
1 0 0 0 0 0 0 4;

你能给我生成这些向量的算法吗？

4

3 回答 3

5

这个问题的一种算法是大多数学生通常在幼儿园学习的那种“ripple-carry”加法，除了稍加修改。当您将两个数字相加时，您将逐个数字地进行：首先是个位，然后是十位，然后是百位，等等。如果您必须写下一个大于 10 的数字（例如 7+8 =15），然后你把它写下来 -10 并将 10 “携带”到下一个地方，在那里你添加它（它变成 1）；这可能会“影响”许多地方（例如 999+1=1000）。通过使用这种算法重复加一个，我们可以一个一个地计数。

重要的是要澄清我们所追求的：不同的地方有不同的基地意味着什么。如果您允许位置具有任意数字范围，并代表任意数字，那么可能会发生一些不好的事情：一个数字可以用多种方式写入，和/或某些十进制数不能写入。因此，我们将自己限制在一个“理智”的方案中，如果一个地方i有一个基数b i，这意味着有效数字是 0,1,2,..., b i -1（像往常一样，就像十进制一样)，并且那个地方的数字代表b i乘以右边所有基的乘积 ( b i-1 x b i-2X ...）。例如，如果我们的基数是 [10,10,10]，则数字的值将是 [1000,100,10,1]；如果我们的基数是 [5,10,5]，则数字的值将是 [250,50,5,1]

数字加1的方法：

Increment the least-significant digit (LSD)
Perform ripple-carry as follows:
    Set the current place to the LSD
    Repeat as long as the current place exceeds its allowed max digit:
        Set the digit at the current place to 0
        Advance the current place one to the left
        Increment the number at the new place (now on the left)

重复上述算法，直到获得所需的所有数字。

Python：

from itertools import *

def multibaseCount(baseFunction):
    currentDigits = [0]
    while True:
        yield currentDigits[::-1]

        # add 1
        currentDigits[0] += 1

        # ripple-carry:
        for place,digit in enumerate(currentDigits):
            if currentDigits[place]>=baseFunction(place):    # if exceeds max digit
                currentDigits[place] = 0         # mod current digit by 10
                if place==len(currentDigits)-1:  # add new digit if doesn't exist
                    currentDigits += [0]
                currentDigits[place+1] += 1      # add 1 to next digit
            else:    # doesn't exceed max digit; don't need to carry any more
                break

演示，其中 n 位置的底数为 n+1：

>>> for digits in islice(multibaseCount(lambda n:n+1),30):
...     print( ''.join(map(str,digits)).zfill(5) )
... 
00000
00010
00100
00110
00200
00210
01000
01010
01100
01110
01200
01210
02000
02010
02100
02110
02200
02210
03000
03010
03100
03110
03200
03210
10000
10010
10100
10110
10200
10210
于 2012-05-02T06:53:18.917 回答
0

如果您真的只对这种格式的八位“数字”感兴趣，这里有一些伪代码可以帮助您入门：

for (a=0; a<2: a++)
  for (b=0; b<5; b++)
    for (c=0; c<2; c++)
      for (d=0; d<2; d++)
        for (e=0; e<2; e++)
          for (f=0; f<2; f++)
            for (g=0; g<2; g++)
              for (h=0; h<2; h++)
                printf("%d%d%d%d%d%d%d%d\n", a, b, c, d, e, f, g, h);

在这种情况下，它将是基数 2、5、2、2、2、2、2、2。根据需要更改索引。

于 2012-05-02T06:24:09.590 回答
0

为时已晚，但这是 C 中的解决方案。

#include <stdio.h>
#include <assert.h>

void
odo(int base, int len)
{
    int stack[len+1];
    int pos=0;
    #define DIGIT (stack[pos])
    #define LOOP(code) for(int i=0; i<len; i++) code
    #define PRINT LOOP(printf("%d", stack[i]));printf("\n");
    LOOP(stack[i]=-1);
    while(pos>=0)
    {
        if (pos<len-1)
        {
            if (DIGIT<base)
            {
                DIGIT++;
                pos++;
                assert(DIGIT==-1);
            }
            else
            {
                DIGIT=-1;
                pos--;
                continue;
            }
        }
        else
        {
            assert(pos==len-1);
            if (DIGIT<base)
            {
                DIGIT++;
                PRINT;
            }
            else
            {
                DIGIT=-1;
                pos--;
            }
        }
    }
}

int
main(void)
{
    odo(4,6);
}
于 2021-09-24T21:07:23.117 回答