「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。

MENU

アルゴリズムの学習(001/XXX)

 コンピュータ科学を学ぶべくアルゴリズムを学んでいく。参考として定番書であり古典的名著でもある

を用いる。実装には勉強もかねてC#を使う。

1. 値の交換

 2つの型が等しい変数があるときにそれらの値を交換する。

static void Main(string[] args)
{
    // P.1値の交換:C#の場合、参照渡しとしてrefを付ける
    void swap(ref int a, ref int b)
    {
        b = a - b;
        a -= b;
        b += a;
    }

    // 変数値を適当に与える
    int a = 5;int b= 6;

    // 出力用に元の変数値を格納する
    int tmp1 = a;
    int tmp2 = b;

    // C#ではポインタは原則禁止されている
    // 参照渡しをする
    swap(ref a, ref b);

    // 出力:ちゃんと交換されているか?
    Console.WriteLine("a={0},b={1}は{2},{3}に交換されました。", tmp1, tmp2, a,b);
}

2. 誤り検出符号

 数字の列(たとえばクレジットカード番号)を扱うときに誤記・誤読を防ぐためにある素数で割ったら余りが特定の値になるような値のみを利用することである。こうすれば、誤記・誤読を\displaystyle{\frac{1}{素数+1}}の確率で検出できる。
 検出方法として、たとえばLuhnのアルゴリズムがある。

  (1) t=1とし、またsを検出対象とする。さらにSum=0とする。
  (2) st桁目を取り、kとする。
  (3) tが偶数ならばk=2ktが奇数ならばk=kとする。
  (4) k\geq10ならばk=k-9とする。
  (5) Sum=Sum+kとする。
  (6) t=t+1として(2)に戻る。
  (7) Sum10で割った余りが0ならば正しい、そうでなければ誤りとする。
static void Main(string[] args)
{
    //PP.1-2 誤り検出符号:Luhnのアルゴリズム
    string strCrdtNmbr = "5555555555554444"; /*カード番号*/
    int i, d, w = 1, t = 0; /* w:(偶数番目の)桁に掛ける数*/

    for (i = strCrdtNmbr.Length - 1; i >= 0; i--)
    {
        d = w * (strCrdtNmbr[i] - '0'); /* カード番号の*/
        if (d > 9) d -= 9;
        t += d;
        w = 3 - w; /*今が奇数番目の桁ならば次のためにw=1->2に、偶数番目の桁ならば次のためにw=2->1に変換*/
    }
    if (t % 10 == 0) Console.WriteLine("有効\n"); else Console.WriteLine("無効\n");
}
プライバシーポリシー お問い合わせ