2015年04月26日

C#で割り算の筆算をシミュレート

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その87

■問題 (出題者:不明)
整数 n, m を与えれば、 n ÷ m の筆算を出力するような プロシージャ(関数)を創ってください。

ウィンドウに描画するもよし、
コンソールに出力するもよし、です。

コンソールアプリで。
今回は、説明を省略します。 コメント書いてあるので、そっち見てください。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            while (true) {
                var str = Console.ReadLine();
                if (str == "")
                    break;
                var data = str.Split('/');
                int dividend = int.Parse(data[0].Trim());
                int divisor = int.Parse(data[1].Trim());

                DivisionByWriting d = new DivisionByWriting();
                var a = d.Divide(dividend, divisor);
                Console.WriteLine();
                foreach (var s in a)
                    Console.WriteLine(s);
            }
        }
    }

    class DivisionByWriting {
        private List<string> note = new List<string>();
        private string _space;
        private string _line;
        private string _originalDividend;  // 割られる数 (被除数) divisorは除数

        /// <summary>
        /// dividentをdivisorで割る
        /// </summary>
        /// <param name="dividend">被除数</param>
        /// <param name="divisor">除数</param>
        /// <returns></returns>
        public string[] Divide(int dividend, int divisor) {
            // 準備
            _space = new string(' ', divisor.ToString().Length + 1);
            _line = _space + new string('-', dividend.ToString().Length);

            // まず、割り算の問題を noteに書く
            _originalDividend = dividend.ToString();
            string s = divisor.ToString() + ")" + dividend.ToString();
            note.Add(new string(' ', s.Length));   //            ; 商を書ききれる場所
            note.Add(_line);                       //    -----
            note.Add(s);                           // xx)xxxxx

            // 筆算でdividendから最初に割られる数を求める
            // 例えば、123 / 8 ならば、12 を求める
            // 同時に、答えを書く最初の位置も求める
            // 例えば、823 / 5 ならば、0となる (8の位置)
            //         123 / 5 ならば、1となる (2の位置)
            //         123 / 50 ならば、2となる (3の位置)
            string dd = dividend.ToString();
            int i = 0;
            int n;
            do {
                i++;
                n = int.Parse(dd.Substring(0, i));
            } while (n / divisor == 0);

            // ここからが実際の割り算  (_divideは、再帰関数)           
            return _divide(n, divisor, i - 1);
        }

        private string[] _divide(int dividend, int divisor, int col) {
            // 部分的な割り算をする
            int q = dividend / divisor;    // 商
            int r = dividend % divisor;    // 余り

            // 先頭行をもとめ、そこに商を書き込む
            char[] array = note[0].ToCharArray();
            array[col + divisor.ToString().Length + 1] = q.ToString()[0];
            note[0] = new string(array);
            col++;

            // 商と序数を掛けた値を下に追加する
            if (q > 0) {
                note.Add(_space + FormatNumber(divisor * q, col));
                note.Add(_line);
            } else {
                // 商が0なら、最後の行をいったん取り消す。(後で、正しいものが追加される)
                note.RemoveAt(note.Count - 1);
            }
            if (col == _originalDividend.Length) {
                // 最後の一桁まで計算をした。
                // 最後の余りを書き込む 0の場合もある
                note.Add(_space + FormatNumber(r, col));
                return note.ToArray();
            }
            // 次の対象となる除数をNoteの最後に追加する
            int newdividend = r * 10 + (_originalDividend[col] - '0');
            note.Add(_space + FormatNumber(newdividend, col + 1));
            // 割り算を実施する。
            return _divide(newdividend, divisor, col);
        }

        // width が 3ならば、"{0,3}" という文字列を作成し、 numを整形する。
        private string FormatNumber(int num, int width) {
            string format = string.Format("{{0,{0}}}", width);
            return string.Format(format, num);
        }
     }
 }

実行例


6542/23

    284
   ----
23)6542
   46
   ----
   194
   184
   ----
    102
     92
   ----
     10

もうひとつの例。商の途中で0が入るパターン。


65436/603

      108
    -----
603)65436
    603
    -----
     5136
     4824
    -----
      312

ぴったり割り切れるパターン。


7200/32

    225
   ----
32)7200
   64
   ----
    80
    64
   ----
    160
    160
   ----
      0

いちおう、これで、「どう書く?orgに感謝を込めて」のシリーズを終わりにします。
読んでいただきありがとうございました。

といっても、このブログのアクセス解析みると、上位の記事はほとんどがWPF関連の記事なので、このシリーズはあまり人気がなかったようです。
まあ、当たり前と言えば当たり前ですが...
でも、こういったアルゴリズムの勉強になるコードを自分で書いてみるってとても大切だと思うんですよね。

調べてみたら、去年の4月から始めたので、なんと1年も続けていました。
自分でもびっくり。

さて、次は何を書こうかな。




 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52412633