3

基数 2 で 8 ビットをカウントする場合、結果は次のようになります。

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

この問題のアルゴリズムの 1 つは、ほとんどの生徒が通常幼稚園で習う「リップル キャリー」加算のようなものですが、わずかに変更が加えられています。2 つの数を足すときは、1 桁ずつ足します。最初に 1 の位、次に 10 の位、次に 100 の位というように。 =15)、次にマイナス 10 を書き留めて、その 10 を次の場所に「持ち越し」、そこで足します (1 になります)。これは、多くの場所で「さざなみ」になる可能性があります (例: 999+1=1000)。このアルゴリズムを使用して 1 を繰り返し追加することで、1 つずつカウントアップできます。

私たちが求めているものを明確にすることが重要です。異なる場所に異なる拠点を持つことは何を意味するのでしょうか。場所に任意の数の範囲を持たせ、任意の数を表すことを許可すると、いくつかの悪いことが起こる可能性があります: 数が複数の方法で記述されたり、一部の 10 進数が記述されなかったりする可能性があります。したがって、場所iの基数がb iである場合、有効な数字は 0,1,2,..., b i -1であるという「健全な」スキームに限定します(通常、10 進数の場合と同様)。 ) であり、その桁は右側のすべての基数の積のb i倍を表します ( b i-1 x b i-2 x ...). For example, if our bases were [10,10,10], the values of the digits would be [1000,100,10,1]; if our bases were [5,10,5], the values of the digits would be [250,50,5,1]

How to add 1 to a number:

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)

Repeat the above algorithm until you have all numbers you desire.

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

Demo, where place n has base 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

この形式の8桁の「数字」だけに本当に興味がある場合は、次の疑似コードを使用して開始できます。

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 に答える