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

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

［改訂新版］C言語による標準アルゴリズム事典 Software Technology

を用いる。実装には勉強もかねて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.　誤り検出符号

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

	(1)	とし、またを検出対象とする。さらにとする。
	(2)	の桁目を取り、とする。
	(3)	が偶数ならば、が奇数ならばとする。
	(4)	ならばとする。
	(5)	とする。
	(6)	として(2)に戻る。
	(7)	をで割った余りがならば正しい、そうでなければ誤りとする。

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");
}