6

好奇心の問題ですが、グレイコードはベース2以外のベースに対して定義されていますか？

基数3でカウントしようとしましたが、一度に1つのトリットのみを変更することに注意して、連続する値を書き込みました。26（3 ** 3-1）までのすべての値を列挙することができましたが、機能しているようです。

        000              122              200
        001              121              201
        002              120              202
        012              110              212
        011              111              211
        010              112              210
        020              102              220
        021              101              221
        022              100              222

私が見ることができる唯一の問題は、ゼロにループバックすると3つのトリットすべてが変化することです。しかし、これは奇数ベースにのみ当てはまります。偶数ベースを使用する場合、ゼロにループバックすると、2進数のように1桁しか変更されません。

10進数でも、他の基数に拡張できると思います。これは、10進数で数えるときに別の順序につながる可能性があります... :-)

    0  1  2  3  4  5  6  7  8  9 19 18 17 16 15 14 13 12 11 10
   20 21 22 23 24 25 26 27 28 29 39 38 37 36 35 34 33 32 31 30

さて、質問ですが、誰か聞いたことがありますか？そのためのアプリケーションはありますか？それとも数学的な狂乱ですか？

4

2 に答える 2

10

はい。ウィキペディアのグレイコードの記事をご覧ください。n-aryグレイコードに関するセクションがあります。

バイナリ反射グレイコード以外にも、多くの特殊なタイプのグレイコードがあります。そのようなタイプのグレイコードの1つは、非ブールグレイコードとしても知られるn-aryグレイコードです。名前が示すように、このタイプのグレイコードは、エンコーディングで非ブール値を使用します。

于 2010-10-01T09:43:22.670 に答える
4

完全を期すために（aioobeはすでに正しい答えを出しているので）、00で始まり96の循環コードをマークするベース3の168個の2桁のグレイコードをすべてリストするC++プログラムを次に示します。ウィキペディアのアルゴリズムを使用すると、塩基に対しても長いグレイコードを簡単に作成できます。不均一な塩基の場合、グレイコードに従って生成するようにプログラムを変更できます。

このプログラムで最初に見つかったサイクリック2桁のグレイコードは次のとおりです。

00 01 02 12 10 11 21 22 20

プログラムを変更した後、最初に見つかったサイクリック3桁の灰色は次のとおりです。

000 001 002 012 010 011 021 020 022 122 102 100 101 111
110 112 212 202 222 220 120 121 221 201 211 210 200

コード：

#include <stdio.h>
#include <stdlib.h>

// Highest number using two trits
#define MAXN 9

int gray_code_count, cyclic_count;

bool changes_one_trit(int code1, int code2) {
  int trits_changed = 0;
  if ((code1 / 3) != (code2 / 3)) trits_changed++;
  if ((code1 % 3) != (code2 % 3)) trits_changed++;
  return (trits_changed == 1);
}

int generate_gray_code(int* code, int depth) {
  bool already_used;

  if (depth == MAXN) {
    for (int i = 0; i < MAXN; i++) {
      printf("%i%i ", code[i]/3, code[i]%3);
    }
    // check if cyclic
    if (changes_one_trit(code[MAXN-1], 0)) {
      printf("cyclic");
      cyclic_count++;
    }
    printf("\n");
    gray_code_count++;    
  }

  // Iterate through the codes that only change one trit
  for (int i = 0; i < MAXN; i++) {
    // Check if it was used already
    already_used = false;
    for (int j = 0; j < depth; j++) {
      if (code[j] == i) already_used = true;
    }
    if (already_used) continue;

    if (changes_one_trit(code[depth-1], i)) {
      code[depth] = i;
      generate_gray_code(code, depth + 1);
    }
  }
}

int main() {
  int* code = (int*)malloc(MAXN * sizeof(int));
  code[0] = 0;
  gray_code_count = 0;
  generate_gray_code(code, 1);
  printf("%i gray codes found, %i of them are cyclic\n", gray_code_count, cyclic_count);
  free(code);
}
于 2010-10-01T10:02:58.763 に答える