Dragonmasterの日記

新年明けましておめでとうございます。
2009年に当たり、家にある蔵書の紹介と読んだ本の読後感想などを書いていくことにします。我が家には過去に購入した物理、数学、コンピューター、ビジネス系の本があります。これらについて、自らの蔵書リスト作成と同じ分野の本の購入を検討されている人の参考になることを目的としたいと思います。

また、今年は英語のブラッシュ・アップをかねて、年間50冊の洋書の読破を目標、少なくとも月に3冊で30冊クリアを目標にしたいと思います。これまでペーパーバックを何回も買ってはくじけているのですが、日本語でも小説自身を読むタイプではなく、ビジネス書や経済書を読むタイプなので、今年は読む本を買えてそうした経済書、ビジネス書、コンピューター関係の本を読んでいこうと考えています。
　もちろん内容の軽重があるので、大部な本を月3冊は無理だと思いますので読みやすい本を月3冊は読むということになろうかと思います。

パターン分析

　A:1桁の数（被加算数）　足される側です。
　B:1桁の数（加算数）　　足す側です。
　A+Bを考えます。
　
　考えられるのは以下のパターン

BをそのままAに加算することができる。
Bに対して5の補数を考え、+5-Bの5の補数
Bに対して10の補数を考え、+10-Bの10の補数(実はこれは2パターン出てきます。）

＜説明＞

[足す数]

そのまま加算　式　 : 該当する被加算数
5の補数　　　式　 : 該当する被加算数
10の補数　　式　 : 該当する被加算数

[+1]

そのまま加算 +1 : 1,2,3 / 4,5,6
5の補数 +5-4 : 4
10の補数　+10-9 : 9

[+2]

そのまま加算　+2　 : 1,2 / 5,6,7
5の補数　　+5-3　　: 3,4
10の補数　 +10-8 : 8,9

[+3]

そのまま加算　+3　 : 1 / 5,6
5の補数　　+5-2　　: 2,3,4
10の補数　 +10-7 : 7,8,9

[+4]

そのまま加算　+4　 : - / 5
5の補数　　+5-1　　: 1,2,3,4
10の補数　 +10-6 : 6,7,8,9

[+5]

そのまま加算　+5　 : - / -
5の補数　　+5-0　　: 1,2,3,4
10の補数　 +10-5 : 5,6,7,8,9

[+6]

そのまま加算　+6　 : 1,2,3
10の補数1　+10-4　 : 4 / 9
10の補数2　+10-5+1 : 5,6,7,8

[+7]

そのまま加算　+7　 : 1,2
10の補数1　+10-3　 : 3,4 / 8,9
10の補数2　+10-5+2 : 5,6,7

[+8]

そのまま加算　+8　 : 1
10の補数1　+10-2　 : 2,3,4 / 7,8,9
10の補数2　+10-5+3 : 5,6

[+9]

そのまま加算　+9　 : -
10の補数1　+10-1　 : 1,2,3,4 / 6,7,8,9
10の補数2　+10-5+4 : 5

分析

　Aの１のタマをA1s、5のタマをA5、Bの1のタマをB1s、５のタマをB5として場合わけをします。

そのまま加算 A1s+B1s<5で、A5、B5のいずれかもしくはともに0
5の補数　　　A1s+B1s>=5で、A5=B5=0
10の補数　　 A1s+B1s>=5で、A5=1
10の補数1　 A1s+B1s>=5で、A5=0,1, B5=1
10の補数2　　A1s+B1s<5で、 A5=B5=1

これを見ると、どうやら、加算数、被加算数の１のタマの和が、５を越えるかどうか、A5,B5の３つの状態で上の状態をさらに整理できそうです。

A1s+B1s>=5	B5	A5	具体例	操作	解説
0	0	0	1+3	addOnes(B1s)	そのまま3を足す
1	0	0	3+3	setFive(),subOnes(~B1s)	5を足して3の補数2を引く
0	0	1	6+3	addOnes(B1s)	そのまま3を足す
1	0	1	7+4	carryOver(),clearFive(),subOnes(~B1s)	繰り上げして、5を払い、4の補数の1を引く
0	1	0	3+6	setFive(),addOnes(B1s)	5を足して、1のタマを加算
1	1	0	4+7	carryOver(),subOnes(~B1s)	繰り上げして、1のタマの補数の3を引く
0	1	1	6+7	carryOver(),clearFive(),add(B1s)	繰り上げして、5のタマを払い、1のタマの2を加える
1	1	1	8+8	carryOver(),subOnes(~B1s)	繰り上げして、3の補数の2を引く

ここで、carryOver()は、次の桁への10の繰り上がりを示しているとします。また、~B1sは、加算数の1のタマの5に対する補数(=5-B1s)という意味です。

アルゴリズム

　A1s+B1s>=5：条件C5とすると、A5,B5,C5の8パターンで加算が分類できるのですが、よく見ると、
　C5=0　の時（1のタマの加算数・被加算数が5を越えない）　addOnes(B1s)
C5=1 の時（1のタマの加算数・被加算数が5を越える） subOnes(~B1s)
となることが分かります。

それでまず、最初にC5=0,1で場合わけをします。

次に、(A5,B5,C5)の１になる数に着目します。

0の場合　(0,0,0)　addOnes(B1s)
1の場合　(0,1,0),(0,0,1) setFive() にC5に応じてaddOnes(B1s),subOnes(~B1s)

(1,0,0) - C5に応じてaddOnes(B1s),subOnes(~B1s)

2の場合　(0,1,1)　　　　 carryOver()にC5に応じてaddOnes(B1s),subOnes(~B1s)

(1,0,1),(1,1,0) carryOver(),clearFive() + C5に応じてaddOnes(B1s),subOnes(~B1s)

3の場合　(1,1,1)　 carryOver(),subOnes(~B1s)

Pseudo Code

 if (C5 == 1)
    subOnes(~B1s);
 else 
    addOnes(B1s);

 if ( A5+B5+C5 == 1 ) {
    if (A5== 0 ) {
      setFive();
    }
    / * B5 or C5 == 0, do nothing)

 } else {
    // A5+B5+C5 == 2 or 3
    carryOver();
    if ( (B5 == 0) || (C5 == 0 )) {
      clearFive();
    }
 }

上記場合わけについて、A5,B5,C5を0,1の整数値を取るフラグとしてみているので分岐が技巧的かもしれません。（A5,B5,C5)から0-7の数を作ってCase文で分岐させたほうが素直かもしれませんが、実装の際再検討します。

意味の検討

　A5は、被加算数の5のタマの有無、B5は、加算数の5のタマの有無、C5は、1のタマのA1sとB1sを足した際の5へのキャリーが立つかを見ているものです。

（A5,B5,C5)のすべてが０なら、1のタマ同士の足し算でしかも4以内ということ。
（A5,B5,C5)のいずれかが1の場合ですが、結果は5のタマが1個だけで5へのキャリーなし

は、5+[1,2,3,4]となるのでOK。5のキャリーが出る場合も、5のタマがないところに、5のキャリーを立てて、被加算数の1のタマから、5の補数を引くことになります。

(A5,B5,C5)が５のタマが2つある場合は、10のでき方が、加算数の5のタマ＋５への繰り上がりでできる場合は、10ヘのキャリーを作ればOK。被加算数の5と加算数の5のタマ、もしくは5への繰り上がりでできる場合は、10のキャリーを作った上で、既にある5をクリアする必要があります。
(A5,B5,C5)で５のタマが3つ分できるときには、2つで10へのキャリーを立てて、後1個はそのままにしておけばいいということです。

　以上から、

1のタマの個数だけで5へのキャリーがでるか検討、それに応じてB1sをそのまま加算するか、5へのキャリーを立てて補数を引くかが決まる。
A5,B5,C5で、「5」に相当するタマが何個できるかカウント、0,1個なら加算後も0,1個、2個あると、足して10になるので、10へのキャリーと5のタマのクリア、3個あると、15になるので、10へのキャリーと5を残すという操作になります。
1のタマの操作と5のタマの操作が部分的に切れているところがミソですね。

これで加算のコードが書けるようになりましたので関数を定義し、適宜クラスを拡張して必要な計算をできるようにしたいと思います。

　　