綾小路龍之介の素人思考

2と3と5の倍数以外の数列

この前書いた部分を多少変えてみる。

n       0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
2の倍数 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,  1,  0,  1,  0, ...
3の倍数 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,  0,  0,  1,  0, ...
5の倍数 1, 0, 0, 0, 0, 1, 1, 0, 0, 0,  1,  0,  0,  0, ...
i          0,                1,            2,      3, ...
i%8        0,                1,            2,      3, ...
i/8        0,                0,            0,      0, ...

同様に考えると、部分数列と2と3と5の最小公倍数である30ずつにわけ、この部分数列には8つの2と3と5の倍数でない数(1, 7, 11, 13, 17, 19, 23, 29 )が8個含まれる。

unsigned int i_to_n_2_3_5(unsigned int i)
{
        unsigned int n = i;
        unsigned int lcm = 30;
        unsigned int the_number_of_un_multiples = 8;
        unsigned int tmp = i % the_number_of_un_multiples;
        n = uint_dvi(n, the_number_of_un_multiples);
        n = uint_mul(n, lcm);
        if (0 == tmp) {
                n = uint_add(n, 1);
        } else if (1 == tmp) {
                n = uint_add(n, 7);
        } else if (2 == tmp) {
                n = uint_add(n, 11);
        } else if (3 == tmp) {
                n = uint_add(n, 13);
        } else if (4 == tmp) {
                n = uint_add(n, 17);
        } else if (5 == tmp) {
                n = uint_add(n, 19);
        } else if (6 == tmp) {
                n = uint_add(n, 23);
        } else if (7 == tmp) {
                n = uint_add(n, 29);
        }
        return n;
}
unsigned int i_to_n(unsigned int i)
{
        return i_to_n_2_3_5(i);
}

冗長に見えるif文を配列を用いてまとめる。

unsigned int i_to_n_2_3_5(unsigned int i)
{
        unsigned int p[] = { 1, 7, 11, 13, 17, 19, 23, 29 };
        unsigned int lcm = 30;
        unsigned int the_number_of_un_multiples = (sizeof(p) / sizeof(p[0]));
        unsigned int n = i;
        n = uint_dvi(n, the_number_of_un_multiples);
        n = uint_mul(n, lcm);
        n = uint_add(n, p[i % the_number_of_un_multiples]);
        return n;
}

マジックナンバーを引数にする。

unsigned int i_to_n_2_3_5(unsigned int i,unsigned int lcm, unsigned int p[],unsigned int the_number_of_un_multiples )
{
        unsigned int n = i;
        n = uint_dvi(n, the_number_of_un_multiples);
        n = uint_mul(n, lcm);
        n = uint_add(n, p[i % the_number_of_un_multiples]);
        return n;
}
unsigned int i_to_n(unsigned int i)
{
        unsigned int p[] = { 1, 7, 11, 13, 17, 19, 23, 29 };
        unsigned int lcm = 30;
        unsigned int the_number_of_un_multiples = (sizeof(p) / sizeof(p[0]));
        return i_to_n_2_3_5(i,lcm,p, the_number_of_un_multiples );
}

i_to_nは何回も呼び出されるのでいちいち宣言するのは無駄。マジックナンバーをi_to_nが頻繁に呼び出されるループの外に持っていく。ついでに構造体にして引数の量を節約。

typedef struct {
        unsigned int *p;
        unsigned int lcm;
        unsigned int the_number_of_un_multiples;
} i_to_n_conf;
unsigned int i_to_n_2_3_5(unsigned int i, i_to_n_conf conf)
{
        unsigned int n = i;
        n = uint_dvi(n, conf.the_number_of_un_multiples);
        n = uint_mul(n, conf.lcm);
        n = uint_add(n, conf.p[i % conf.the_number_of_un_multiples]);
        return n;
}
unsigned int i_to_n(unsigned int i, i_to_n_conf conf)
{
        return i_to_n_2_3_5(i,conf);
}
void check(void)
{
        unsigned int p[] = { 1, 7, 11, 13, 17, 19, 23, 29 };
        i_to_n_conf conf;
        conf.lcm = 30;
        conf.the_number_of_un_multiples = (sizeof(p) / sizeof(p[0]));
        conf.p = p;
        unsigned int i = 0;
        unsigned int i_sta = 0;
        unsigned int i_end = 0;
        i_sta = 0;
        i_end = 20;
        for (i = i_sta; i < i_end; i++) {
                printf("%10u ", i);
                printf("%10u\n",  i_to_n(i,conf));
        }
        i_sta = (UINT_MAX / 3) - 10;
        i_sta = (UINT_MAX / 6)*2 - 10;
        i_sta = (UINT_MAX / 30)*8 - 10;
        i_end = i_sta + 20;
        for (i = i_sta; i < i_end; i++) {
                printf("%10u ", i);
                printf("%10u\n",  i_to_n(i,conf));
        }
        return;
}

ソーシャルブックマーク

  1. はてなブックマーク
  2. Google Bookmarks
  3. del.icio.us

ChangeLog

  1. Posted: 2007-07-22T03:58:38+09:00
  2. Modified: 2007-07-22T03:56:12+09:00
  3. Generated: 2017-08-12T23:10:32+09:00