3

次の入力を受け取り、次の出力を生成する関数を作成する方法がわかりません。

in (int) | out (char *)
0        | ""
1        | "a"
2        | "b"
3        | "c"
4        | "aa"
5        | "ab"
6        | "ac"
7        | "ba"
8        | "bb"
...

「a」と「aa」には違いがあるため、単純に入力を 3 進数に変換するわけではありません (一方、 と には違いはありません0) 00。

文字列の長さと入力 (len = floor(log2(in + 1))のみを使用する場合a、およびb:

in (int) | floor(log2(in + 1)) | out (char *)
0        | 0                   | ""
1        | 1                   | "a"
2        | 1                   | "b"
3        | 2                   | "aa"
4        | 2                   | "ab"
5        | 2                   | "ba"
6        | 2                   | "bb"
7        | 3                   | "aaa"
8        | 3                   | "aab"

n異なる有効な文字がある場合、出力の長さと入力値の間の一般的な相関関係は何ですか?

4

4 に答える 4

4

これはC の Calc セル コンバーターに関連していますが、明らかに異なります。このコードは、そのコードから迅速に派生しました。

#include <ctype.h>
#include <stdio.h>
#include <string.h>

/* These declarations should be in a header */
extern char     *b3_row_encode(unsigned row, char *buffer);
extern unsigned  b3_row_decode(const char *buffer);

static char *b3_encode(unsigned row, char *buffer)
{
    unsigned div = row / 3;
    unsigned rem = row % 3;
    if (div > 0)
        buffer = b3_encode(div-1, buffer);
    *buffer++ = rem + 'a';
    *buffer = '\0';
    return buffer;
}

char *b3_row_encode(unsigned row, char *buffer)
{
    if (row == 0)
    {
        *buffer = '\0';
        return buffer;
    }
    return(b3_encode(row-1, buffer));
}

unsigned b3_row_decode(const char *code)
{
    unsigned char c;
    unsigned r = 0;
    while ((c = *code++) != '\0')
    {
        if (!isalpha(c))
            break;
        c = tolower(c);
        r = r * 3 + c - 'a' + 1;
    }
    return r;
}

#ifdef TEST

static const struct
{
    unsigned col;
    char     cell[10];
} tests[] =
{
    {    0,      "" },
    {    1,     "a" },
    {    2,     "b" },
    {    3,     "c" },
    {    4,    "aa" },
    {    5,    "ab" },
    {    6,    "ac" },
    {    7,    "ba" },
    {    8,    "bb" },
    {    9,    "bc" },
    {   10,    "ca" },
    {   11,    "cb" },
    {   12,    "cc" },
    {   13,   "aaa" },
    {   14,   "aab" },
    {   16,   "aba" },
    {   22,   "baa" },
    {  169, "abcba" },
};
enum { NUM_TESTS = sizeof(tests) / sizeof(tests[0]) };

int main(void)
{
    int pass = 0;

    for (int i = 0; i < NUM_TESTS; i++)
    {
        char buffer[32];
        b3_row_encode(tests[i].col, buffer);
        unsigned n = b3_row_decode(buffer);
        const char *pf = "FAIL";

        if (strcmp(tests[i].cell, buffer) == 0 && n == tests[i].col)
        {
            pf = "PASS";
            pass++;
        }
        printf("%s: Col %3u, Cell (wanted: %-8s vs actual: %-8s) Col = %3u\n",
               pf, tests[i].col, tests[i].cell, buffer, n);
    }

    if (pass == NUM_TESTS)
        printf("== PASS == %d tests OK\n", pass);
    else
        printf("!! FAIL !! %d out of %d failed\n", (NUM_TESTS - pass), NUM_TESTS);

    return (pass == NUM_TESTS) ? 0 : 1;
}

#endif /* TEST */

このコードには、文字列から整数に変換するテスト プログラムと関数、および整数から文字列に変換する関数が含まれています。テストは連続した変換を実行します。コードは空の文字列をゼロとして扱いません。

出力例:

PASS: Col   0, Cell (wanted:          vs actual:         ) Col =   0
PASS: Col   1, Cell (wanted: a        vs actual: a       ) Col =   1
PASS: Col   2, Cell (wanted: b        vs actual: b       ) Col =   2
PASS: Col   3, Cell (wanted: c        vs actual: c       ) Col =   3
PASS: Col   4, Cell (wanted: aa       vs actual: aa      ) Col =   4
PASS: Col   5, Cell (wanted: ab       vs actual: ab      ) Col =   5
PASS: Col   6, Cell (wanted: ac       vs actual: ac      ) Col =   6
PASS: Col   7, Cell (wanted: ba       vs actual: ba      ) Col =   7
PASS: Col   8, Cell (wanted: bb       vs actual: bb      ) Col =   8
PASS: Col   9, Cell (wanted: bc       vs actual: bc      ) Col =   9
PASS: Col  10, Cell (wanted: ca       vs actual: ca      ) Col =  10
PASS: Col  11, Cell (wanted: cb       vs actual: cb      ) Col =  11
PASS: Col  12, Cell (wanted: cc       vs actual: cc      ) Col =  12
PASS: Col  13, Cell (wanted: aaa      vs actual: aaa     ) Col =  13
PASS: Col  14, Cell (wanted: aab      vs actual: aab     ) Col =  14
PASS: Col  16, Cell (wanted: aba      vs actual: aba     ) Col =  16
PASS: Col  22, Cell (wanted: baa      vs actual: baa     ) Col =  22
PASS: Col 169, Cell (wanted: abcba    vs actual: abcba   ) Col = 169
== PASS == 18 tests OK
于 2013-07-11T04:09:28.377 に答える
1

あなたは正しい道を歩んでいました: 各 N 文字グループは、基数 M の N 桁の数です。ここで、M はシンボルの数です。したがって、シーケンスは 0 桁の 3 進数 ("") の後に 1 桁の 3 進数 ("a"、"b"、"c") などが続きます。

ランクの桁数は でfloor(log3(2n+1))、各シーケンスの最初のランクは です(3**d-1)/2。したがって、シーケンスの 10000 番目は 9 桁です。最初の 9 桁のシーケンス ("aaaaaaaaa") は 9841 です。10000-9841 は 159 で、基数 3 では 12220 であるため、10000 番目のシーケンスは "aaaabccca" です。

于 2013-07-11T04:37:10.380 に答える
0

単純に a = 1、b = 2、c = 3 に 3^n を掛けたもの (n は文字列内の位置) ではありませんか? 三項の少し奇妙な定義のようです。空の文字列は、a、b、および c 以外のすべてが出力値に 0 を与えるため、空の文字列の長さに関係なく同等です。

さらに、質問の 2 つのテーブルが競合しているようです。最初のテーブルでは 5 --> "ab"、2 番目のテーブルでは 5 --> "ab" です。それは意図的なものですか？もしそうなら、関数は1対1ではなく、あなたの質問はもっと曖昧です.

于 2013-07-11T04:28:50.313 に答える