2015年01月28日

C#で整数の漢数字表記

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

キーボードから正の整数を入力すると、それを漢数字で表示するプログラムを作ってください

☆ 例えば「1732050807568877」なら「千七百三十二兆 五百八億 七百五十六万 八千八百七十七」といった感じです
☆ 「一七三二兆 〇五〇八億 〇七五六万 八八七七」ではダメですよ^^;

このお題は匿名での投稿です。 与えられる整数の範囲は一京未満(10000000000000000未満)としたいと思います。 ご投稿ありがとうございます。

int, kong の拡張メソッドとして定義してみました。
一万未何の数を漢数字に変換する ToKansuujiUnder10000 というprivateメソッドを定義し、 それを利用することで、それよりも大きな数でも対応できるようにしています。
一京以上かどうかのチェックはやってません。 ちなみに、 0は'零'と表示するようにしました。

using System;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            while (true) {
                string s = Console.ReadLine();
                Console.WriteLine(long.Parse(s).ToKansuuji());
            }
        }
    }

    public static class KanjiExtentions {
        static string[] digit = { "", "一", "二", "三", "四", "五", "六", "七", "八", "九" };
        static string[] subUnit = { "", "十", "百", "千" };
        static string[] unit = { "", "万", "億", "兆" };

        public static string ToKansuuji(this int n) {
            return ToKansuuji((long)n);
        }
        public static string ToKansuuji(this long n) {
            int unitCol = 0;
            string s = "";
            // 一の位から順に大きな位へ
            for (; n > 0; n /= 10000, unitCol++ ) {
                int x = (int)(n % 10000);            // 10000(一万)の単位で処理をしていく。
                string t = ToKansuujiUnder10000(x);
                s = x == 0 ? t + s
                           : t + unit[unitCol] + " " + s;
            }
            return s.Length == 0 ? "零" : s;
        }

        private static string ToKansuujiUnder10000(long n) {
            string s = "";
            for (int subCol = 0; subCol < 4; subCol++) {
                long amari = n % 10;
                if (amari > 0)                 // ゼロの時はその単位を表示しない
                    s = subUnit[subCol] + s;
                if (amari != 1 || subCol == 0) // 一百のようにならないように制御
                    s = digit[amari] + s;               
                n /= 10;
            }
            return s;
        }
    }
}
  

Posted by gushwell at 22:00Comments(0)TrackBack(0)

2015年01月25日

C#で漢数字で九九の表

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

■問題 (出題者: 出題:syatさん)
漢数字で九九の表を作ってください。
ただし以下の条件をつけます。

条件
一.アラビア数字(0〜9)禁止。
    プログラムにも出力結果にもアラビア数字を含んではいけない。(全角・半角とも)
二.結果の数字は、「七」とか「一○」(=10)とか「六四」(=64)のような形式とする。
三.九九の結果をそのままプログラム中に書き込んではいけない。

出力例

 一  二  三  ・・・・
 二  四  六  ・・・・
 三  六  九  ・・・・
 四  八 一二  ・・・・
 五 一〇 一五  ・・・・
 ・
 ・

アラビア数字禁止なので、どうやって 1から9の数を生成するかが問題になってきますが、 ここでは、LINQのSelectメソッドを使っています。 なお、以下の2つの制約もつけて解いてみました。

1. Length,Count プロパティも使わない。 
2. メソッド名、変数名にもアラビア数字は禁止。

制約付けないで解いたら面白くもなんともない問題ですが、制約つけることで 頭の体操になりますね。

using System;
using System.Linq;

namespace Doukaku.Org {
    class Program {
        static string KanjiString = "一二三四五六七八九";
        static void Main(string[] args) {
            var nums = KanjiString.Select((c, i) => ++i);
            foreach (var m in nums) {
                foreach (var n in nums)
                    Console.Write(ToKanji(n * m) + " ");
                Console.WriteLine();
            }
            Console.ReadLine();
        }

        static string ToKanji(int n) {
            string str = "";
            bool isOneDigit = false;
            foreach (var ch in n.ToString()) {
                str += CharToKanji(ch);
                isOneDigit = !isOneDigit;
            }
            return isOneDigit ? " " + str : str;
        }

        static char CharToKanji(char ch) {
            int n = int.Parse(ch.ToString());
            return ("〇" + KanjiString)[n];
        }
    }
}
  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年01月21日

C#で10000以下のダブル完全数をすべて求める

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

■問題 (出題者:にしお さん)
「完全数」とは、自分以外の約数の和が自分自身と等しいような整数のことです。
ここで「自分以外の約数の和が自分自身の2倍と等しいような整数」を「ダブル完全数」と呼ぶことにします。10000以下のダブル完全数をすべて求めるコードを書いてください。

最初に書いたコード。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
           
            for (long i = 0; i <= 10000; i++)
                if (IsDoublePerfect(i)) 
                    Console.WriteLine(i);
                
            Console.WriteLine("end");
            Console.ReadLine();
        }

        static bool IsDoublePerfect(long n) {
            long r = 1;
            for (int i = 2; i <= n / 2; i++) {
                if (n % i == 0)
                    r += i;
            }
            return (n * 2 == r);
        }
    }
}


10000までのダブル完全数は、120, 672 の2つでした。
では、672の次のダブル完全数はいくつかな、と思って、 10000 を 1000000 までにしてみたら遅い。
いつまで待っても終わりません。 とんでもなく遅いです。いくらなんでも遅すぎます(T T)

ということで、ちょっと改良したコード。

static bool IsDoublePerfect(long n) {
    long r = 1;
    long limit = (long)Math.Sqrt(n);
    for (int i = 2; i <= limit; i++) {
        if (n % i == 0)
            r += i + (n / i);
    }
    return (n * 2 == r);
}

例えば、18 の約数を調べるとすると、2で割り切れたら、その商である 9も約数であることは明白なので、
r += i + (n / i);

で、2と9を加えています。当
然、約数かどうかは、(long)Math.Sqrt(n) まで調べれば 良いことになります。
たったこれだけで、随分と速くなりました。
3つ目のダブル完全数が知りたい方は、実際に動かしてみてください。
   
Posted by gushwell at 23:00Comments(0)TrackBack(0)

2015年01月18日

C#で数列が急勾配かどうかを判定する

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

■問題 (出題者:nobsun さん)
有限の長さの数列で,各要素の値が,その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします(空列の和は0とします). 任意の長さ(ただし有限の長さの)数列を与えられたとき,それが「急勾配の列」であるかどうかを判定する述語関数を定義してください. 必須ではありませんが,効率についてコメントがあれば面白いかもしれませんね.

まずは、素直に解いたもの。 再帰とLINQ使ってます。
急勾配の判定の定義を、ほぼそのままコードにしています。

private static bool IsSteepSlope(IEnumerable<int> nums) {
    if (!nums.Any())
        return true;
    var x = nums.First();
    var xs = nums.Skip(1);
    return (x > xs.Sum()) && IsSteepSlope(xs);
}
このIsSteepSlopeを使ったコードはこんな感じ。
static void Main(string[] args) {
    int[] nums = { 32, 16, 8, 4, 2, 1 };
    bool r = IsSteepSlope(nums);
    Console.WriteLine(r.ToString());
    Console.ReadLine();
}

でも、何回も何回も、数列を走査する必要があるので、効率的とは言えません。 もう少し効率の良い方法も考えてみました。
有限個の数列なので、先頭から走査するのではなく、最後尾から走査すれば効率よく、急勾配かどうかを判定できそうです。
つまり、急な下り斜面かどうかを調べるのではなく、急な上り斜面かどうかを調べるコードにするということですね。

private static bool IsSteepSlope(IEnumerable<int> nums) {
    int sum = 0;
    foreach (var n in nums.Reverse()) {
        if (n <= sum)
            return false;
        sum += n;
    }
    return true;
}
  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年01月14日

C#で括弧の対応を保存したまま文字列を反転させる

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

今回の問題は、括弧の対応を維持したまま文字列を反転させるというもの。
長めの問題文ですが、そのまま引用させてもらいます。

■問題 (出題者:nobsun さん)
与えられた文字列を前後反転する関数 ReverseString を書いてください。
ただし、ReverseString は単純に文字列を反転するのではなく、括弧の対応を保存するようにしてください。

以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す reverseString では
  reverseString("文字列(もじれつ)の反転(はんてん)")
    → ")んてんは(転反の)つれじも(列字文"

のように括弧の対応は保存されませんが、ReverseString では
  ReverseString("文字列(もじれつ)の反転(はんてん)")
    → "(んてんは)転反の(つれじも)列字文"

のように括弧の対応が保存されます。
括弧文字は、'('と')'、'{'と'}'、'['と']'で、それぞれASCII文字と仮定してください。
  ReverseString("対応[の{とれている(さまざまな)括弧}の(例)]です。")
    → "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"

入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はないと解釈してください。たとえば、
  ReverseString("これ(は(対応のとれていない)括弧がある例です。")
    → "。すで例るあが弧括(いないてれとの応対)は(れこ"

次のような場合は対応のとれている括弧はないという解釈になります。
  ReverseString("これ(も{対応の)とれていない}括弧の例です")
    → "。すで例の弧括}いないてれと)の応対{も(れこ"

日本語対応にする場合の文字のエンコーディングは実装側で都合のよいように仮定してください。
日本語対応であることは望ましいですが、必須ではありません。

対応する開き括弧と閉じ括弧を入れ替えてから、最後に一気に反転させるという方法で実装してみました。
括弧の入れ替えは StackとListを使って実現しています。
こうやれば、もっと簡単に実現できるよ! という目から鱗のアルゴリズムがあれば、どなたか教えてください。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            ReverseAndPrint("文字列(もじれつ)の反転(はんてん)");
            ReverseAndPrint("対応[の{とれている(さまざまな)括弧}の(例)]です。");
            ReverseAndPrint("これ(は(対応のとれていない)括弧がある例です。");
            ReverseAndPrint("これ(も{対応の)とれていない}括弧の例です");

            Console.ReadLine();
        }

        static void ReverseAndPrint(string s) {
            Console.WriteLine(ReverseString(s));
            Console.WriteLine();
        }

        static string ReverseString(string s) {
            char[] ParenthesesA = { '{', '(',  '[' };
            char[] ParenthesesB = { '}', ')',  ']' };
            Stack<CharAadIndex> stack = new Stack<CharAadIndex>();
            List<char> chars = new List<char>();
            int index = 0;
            foreach (var c in s) {
                if (ParenthesesA.Contains(c)) {
                    // 開き括弧
                    stack.Push(new CharAadIndex(c, index));
                    chars.Add(c);
                } else {
                    int i = Array.IndexOf(ParenthesesB, c);
                    if (i >= 0 && stack.Count > 0) {
                        CharAadIndex pair = stack.Peek();
                        if (pair.Char == ParenthesesA[i]) {
                            // 閉じ括弧:対応取れている
                            char temp = stack.Pop().Char;
                            chars[pair.Index] = c;
                            chars.Add(temp);
                        } else {
                            // 閉じ括弧:対応取れていない
                            stack.Push(new CharAadIndex(c, index));
                            chars.Add(c);
                        }
                    } else {
                        chars.Add(c);
                    }
                }
                index++;
            }
            StringBuilder sb = new StringBuilder();
            foreach (var c in chars.Reverse<char>()) {
                sb.Append(c);
            }
            return sb.ToString();
        }
    }

    class CharAadIndex {
        public CharAadIndex(char c, int index) {
            Char = c;
            Index = index;
        }
        public char Char { get; set; }
        public int Index { get; set; }
    }
}

  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年01月11日

C#でUTF-16をUTF-8に変換

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

■問題 (出題者:greentea さん)
UTF-16の文字コードを16進(1オクテットごとにスペース区切り)の形で入力します。入力した文字コードを、2進数の形(1オクテットごとにスペース区切り)で出力してください。 入力する文字コードはUCS-2の範囲(サロゲートペアを使わなくてもよい範囲)のみに限定しても構いませんが、可能ならばサロゲートペアにも対応したものに挑戦してください。
     * 例1: abc(U+0041 U+0042 U+0043)

          * 入力 00 41 00 42 00 43
          * 出力 01000001 01000010 01000011

     * 例2: あいう(U+3042 U+3044 U+3046)

          * 入力 30 42 30 44 30 46
          * 出力 11100011 10000001 10000010 11100011 10000001 10000100 11100011 10000001  10000110
正攻法からトリッキーな手段まで、いろいろお待ちしております。 参考: 通信用語の基礎知識 UTF-8


出題例から、出力は、UTF-8形式に直したものを2進形式で出力するということだと理解しました。 単に16進形式→2進形式ならば、UTF16と明示する必要がないですからね。

UTF16形式のバイト配列をUTF8形式のバイト配列に直接変換する方法が分からなかったので、 いったん文字列に変換後、UTF8に変換しています。

これらは、.NET Frameworkの機能を利用しているだけなので、ごりごり書かないといけないのは、 16進形式の文字列をbyte配列に変換するところだけです。これは、HexTextToBytes メソッドとして 実装しています。

お題は、2進数の形式で出力してくださいとのことですが、元がどんな文字列かが分かったほうが良いので、ついでに、文字列に変換したもの(上の例では「abc」「あいう」)も出力するようにしました。

サロゲートペアには対応してません。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            PrintUtf16BEByBit("00 41 00 42 00 43");
            PrintUtf16BEByBit("30 42 30 44 30 46");
            PrintUtf16BEByBit("30 D7 30 ED 30 B0 30 E9 30 DF 30 F3 30 B0");
            Console.ReadKey();     
        }

         private static void PrintUtf16BEByBit(string hexText) {
            byte[] utf16 = HexTextToBytes(hexText);
            string s = Encoding.GetEncoding("UTF-16BE").GetString(utf16);
            Console.WriteLine(s);

            byte[] utf8 = Encoding.UTF8.GetBytes(s);
            foreach (var b in utf8) {
                Console.Write("{0} ", Convert.ToString(b, 2));
            }
            Console.WriteLine();
        }

        private static byte[] HexTextToBytes(string hexText) {
            hexText = hexText.Replace(" ", "");
            List<byte> list = new List<byte>();
            for (int i = 0; i < (hexText.Length / 2) * 2; i += 2) {
                string s = "" + hexText[i] + hexText[i + 1];
                list.Add(Convert.ToByte(s, 16));
            }
            return list.ToArray();
        }

    }
}
  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年01月07日

C#で文字列を指定した行数に均等分割する

   このエントリーをはてなブックマークに追加 Clip to Evernote
皆さん、あけましておめでとうございます。
本年もどうぞよろしくお願いします。

昨年から懲りずに続けている 「どう書く?orgに感謝を込めて」シリーズ その60 です。


■問題 (出題者:nobsun さん)
一行の文字列を指定した数の行にできるだけ文字数が均等になるように分割してください. ただし,除算や剰余算を使わないで書いてみてください.
sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく"

divid 4 sample =>
"ゆめよりもはかなき世のなかを"
"なげきわびつゝあかしくらすほ"
"どに四月十よひにもなりぬれ"
"ば木のしたくらがりもてゆく"

divid 5 sample => 
"ゆめよりもはかなき世の"
"なかをなげきわびつゝあ"
"かしくらすほどに四月十"
"よひにもなりぬれば木の"
"したくらがりもてゆく"

divid 6 sample => 
"ゆめよりもはかなき"
"世のなかをなげきわ"
"びつゝあかしくらす"
"ほどに四月十よひに"
"もなりぬれば木のし"
"たくらがりもてゆく"
除算や剰余算を使わないでというのがいやらしいですね。
でも、高さ(行数)が分かっているわけですから、文字列を横に順に置いてゆく代わりに、 縦方向に置いてゆき、一番下までいったら、1行目に戻るようにしていけば、 各行の幅が分かります。
実際コードでは、文字を置いてゆくのではなく、カウントアップすることで、各行の幅を求めています。

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


namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            string sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく";
            PrintText(sample, 4);
            Console.WriteLine();
            PrintText(sample, 5);
            Console.WriteLine();
            PrintText(sample, 6);
            Console.ReadLine();
        }

        private static void PrintText(string sample,int height) {
            var list = DivideEqually(sample, height);
            foreach (var s in list)
                Console.WriteLine(s);
        }

        // 除算や剰余算を使わない方法
        static IEnumerable<string> DivideEqually(string s, int height) {
            int[] counts = new int[height];
            // 最初に、一行の幅を求めてしまう
            for (int i = 0, j = 0; j < s.Length; j++) {
                counts[i]++;
                if (++i >= height)
                    i = 0;
            }
            // 求めた幅にあうように、文字列を切り出してゆく。
            int start = 0;
            for (int i = 0; i < height; i++) {
                yield return s.Substring(start, counts[i]);
                start += counts[i];
            }
        }
    }
}

でも、後半部分で、Substringしているところがイヤだったので、Interactive Extensions(Ix) の Shareメソッド 使って 書き直してみました。

static IEnumerable<string> DivideEqually(string s, int height) {
    int[] counts = new int[height];
    // 最初に、一行の幅を求めてしまう
    for (int i = 0,j = 0; j < s.Length; j++) {
        counts[i]++;
        if (++i >= height)
            i = 0;
    }
    // 求めた幅にあうように、文字列を切り出してゆく。
    var q = s.Share();
    foreach (var count in counts) {
          yield return string.Concat(q.Take(count));
    }
}

ちょっとはすっきりしたかな。
でも、実際の仕事で書くとしたら、除算や剰余算を使うと思うので、 そのバージョンも書いてみました。

// 除算や剰余算を使った方法
static IEnumerable<string> DivideEqually2(string s, int height) {
    int width;
    int start = 0;
    for (int length = s.Length; length > 0; length -= width) {
        width = (int)Math.Ceiling((double)length / height--);
        yield return s.Substring(start, width);
        start += width;
    }
}

結局、Substring使うことになっちゃいました(^^;  
Posted by gushwell at 21:30Comments(0)TrackBack(0)