プログラミングテスト

先日、会社でプログラミングのテストが行われました。
使用言語は自由だったのでC言語を選択してみました。
それに関するメモ的な何か。

問題は以下の通りです。

与えられた文字列に対して、数字を挿入する関数を記述してください。
挿入ルールは、最初に”1″、1文字あけて”2″、2文字あけて”3”、・・・（英字が与えられる前提でOK、スペースやカンマも1文字と数える。）
ただし最後は、あける文字数によらず数字で終わらせる。

例）
Hello Jason, how are you?
→1H2el3lo 4Jaso5n, ho6w are 7you?8

一応解けたんですが、出力文字列の長さの計算が分からなかったので適当に決め打ちの長さでやってしまいました。
なので、その部分を後で考えなおしました。数学やアルゴリズムに長けている訳ではないので結構苦労したり(；´∀｀)
とりあえず以下ソース。

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

int get_triangular_number(int x) {
    double n = (sqrt((double)(8*x + 1)) - 1) / 2;
    return (int)ceil(n);
}

int get_total_num_strlen(int n) {
    int i = 1, s = 0;
    int x, x1 = 10, x2 = 1;

    while (n >= x1) {
        x = x1 - x2;
        s += x * i;
        n -= x;
        x2 = x1;
        x1 = (int)pow(10.0f, ++i);
    }

    return s + i*n;
}

char* insert_num(char *str) {
    int i, j, n, d, slen;
    char *num;
    char *dst, *psrc, *pdst;

    psrc = str;
    slen = strlen(psrc);

    n = get_triangular_number(slen) + 1;
    d = (int)log10((double)n) + 1;

    num = (char *)malloc((d + 1) * sizeof(char));
    pdst = dst = (char *)malloc((get_total_num_strlen(n) + slen + 1) * sizeof(char));

    for (i = 1; *psrc != '\0'; i++) {
        itoa(i, num, 10);
        strcpy(pdst, num);
        pdst += strlen(num);

        for (j = 0; j < i && *psrc != '\0'; j++) {
            *pdst = *psrc;
            pdst++;
            psrc++;
        }
    }

    itoa(i, num, 10);
    strcpy(pdst, num);

    return dst;
}

int main(int argc, char *argv[]) {
    char *out;

    if (argc < 2) return EXIT_FAILURE;

    out = insert_num(argv[1]);
    puts(out);
    free(out);

    return EXIT_SUCCESS;
}

要は
出力文字列の長さ = 元の文字列の長さ + 埋め込む数字の総文字数
ということですが、埋め込む数字の最大値を求め、総文字数を求めています。

まず、get_triangular_number()の部分ですが、ここで三角数の判定の数式を用いて導きだしたn以上の直近の三角数のn（nって正しくはなんて言うんだ？わかりづらいですねｗ）を返します。それを利用して桁数を文字数として、総文字数の算出をget_total_num_strlen()で行なっています。

という感じで出力する文字列の長さが割り出せればあとは大したことないですね。
なんか途中で間違って常用対数の総和とか使いそうになってました。
PHPとかでやればこんな計算要らないのですが、自分としてはこういった数学的要素が絡むほうが好きなので、敢えて難易度の高いやり方を選んだわけです。

以上！

追記

atoi()はANSI標準ライブラリ関数なのにitoa()ってそうじゃないらしいですね…
VC++でやってたら気づきませんでした。
あとでその部分修正するか(-_-;)