プログラム

C#プログラミングレッスン

C#での .NETプログラミングを易しく丁寧に解説するメールマガジンです。「C#プログラミング・レッスン」で、.NETプログラミングをマスターしましょう。

全て表示する >

【C#プログラミングレッスン】- アルゴリズム編 文字列操作(3)

2013/12/26

■━ [C#プログラミングレッスン] ━━━━━━━━━━━━━━━ No.383 ━□

「アルゴリズム編」-- 文字列操作(3)
                                                           by Gushwell
□━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━■

みなさんおはようございます。寒い日が続きますね。
2013年もあと残り僅かとなりましたが、いかがお過ごしでしょうか。
これが今年最後のメールマガジンです。文字列操作の最後の問題となります。


■□───────────────────────────────────
■□ 問題

文字列内に出現するすべての空白文字を"%20"で書き換えるメソッドを書いてくださ
い。ただし、文字列の後ろには新たな文字を追加するためのスペースが十分にある
(バッファーのサイズは気にしなくてもよい)ことと、その追加用スペースを除い
た文字列の真の長さが与えられます。
(注意:Javaで実装する場合は、追加の領域を使用せずに処理できるような文字配
列を使ってください)

  出展:『世界で闘うプログラミング力を鍛える150問』
  http://www.amazon.co.jp/exec/obidos/ASIN/4839942390/gaius-22/



■□───────────────────────────────────
■□ 方針を決める

これを実際のアプリでやるのならば、
 
 string s = "Mr  John Smith";
 s = s.Replace(" ", "%20");

で済んじゃいますが、アルゴリズムのスキルアップが目的ですから、問題の趣旨の
通りにプログラムを書いてみようと思います。

注意には「Javaで実装する場合は」とありますが、C#でも同様に文字配列を使うこ
ととします。

" " 一文字が "%20" と3文字になり、2文字分長くなるため、文字を後ろに移動す
る処理がこのプログラムのカギとなりますね。
移動後に、空白の位置から、"%20"を埋め込むという処理をすることで目的を達する
ことができます。
すべての空白に対してこれをやれば良いわけですね。


■□───────────────────────────────────
■□ 問題を解く

最初からすべての機能を実装するのではなく、問題をさらに小さな問題に分解する
ことが大切です。
プログラミングの世界も「分割して統治せよ」が当てはまります。ということで、
まずは、文字配列の特定の位置から指定文字数分後ろに移動するメソッドを作成し
てみましょう。

このとき作業用のバッファがあれば、文字列の左から順に移動先バッファに文字を
セットしていけばよいのですが、バッファーが使えない場合は、文字配列の最後か
ら先頭に向かって処理をしていかなくてはなりません。
なぜなら、"ABC  " という文字列があった場合、左の文字かから順に移動した場合、
先頭の A を2文字分右に移動すると、" BA  " となり、'C' が消えてしまうからで
す。

指定文字数分後ろに移動するメソッド ShiftArray を示します。

 private static void ShiftArray(char[] chars, int start, int count) {
     for (int i = chars.Length - 1 - count; start <= i; i--) {
         chars[i + count] = chars[i];
     }
 }


ループの中では、

        chars[i + count] = chars[i];

として、文字を移動させています。
このとき、chars[i + count] が、インデックスオーバーとならないようにループ変
数 i の初期値を

  i = chars.Length - 1 - count

としています。
また、配列の start 位置から count 個数までは、空白で埋めることはせずに、そ
のままとしておきます。どのみち、"%20"で埋められてしまうのですから。
この ShiftArray メソッドを汎用的で再利用可能にしたいのなら、空白で埋めるほ
うが良いと思いますが、ここでは、この問題を解くためだけのメソッドということ
で、これでOKとします。

そういう意味では引数 Countも必要ないかもしれませんね。
でも、このメソッドを作成するときに、再利用可能なインターフェースを考えるとい
う意識が働いたので、Count を引数に受け取ることとしました。

このShiftArrayメソッドができれば、あとは1文字ずつ走査し、空白だったら、残
りの文字を2文字分後ろに移動し、空いたところに、"%20"をセットしていけばOKで
すね。そのメソッドを以下に示します。

  private static void ChangeSpace(char[] chars) {
      for (int i = 0; i < chars.Length; i++) {
          if (chars[i] == ' ') {
              ShiftArray(chars, i, 2);
              chars[i++] = '%';
              chars[i++] = '2';
              chars[i] = '0';     // ここはi++ではない。
          }
      }
  }


ShiftArrayメソッドを作成したことで、ChangeSpaceは実に単純でわかり易い
コードになりました。
ShiftArrayに引数 Countがあることで、よりやりたいことがはっきりしたと
思います。


■□───────────────────────────────────
■□ 確認のコードを書く

最後に、このメソッドの動作を確認するためのコードです。

  static void Main(string[] args) {
      string original = "Mr  John Smith      ";        
      char[] chars = original.ToArray();
      ChangeSpace(chars);
      string result = new string(chars);
      Console.WriteLine("[{0}]",result);

      string s = original.TrimEnd();
      string result2 = s.Replace(" ", "%20");
      Console.WriteLine("[{0}]",result2);
      Console.WriteLine(result == result2);
      Console.ReadLine();
  }

    ※ trueが表示されれば OK.



■□───────────────────────────────────
■□ 次回の問題 (ビット操作)

最大32ビットの整数NとM、ビットの位置を指す値iとjが与えられています。このと
き、Nのjビット目からiビット目にMを挿入するメソドを書いてください。ただし、
jとiの幅はMのビット数と一致していると仮定してかまいません。
つまり、M=10011であれば、jとiの幅は5と仮定してかまいません。j=3, i=2のよう
な、Mの幅と合わないような値は考えなくてもかまいません。

  入力:N = 10000000000, M= 10011, i = 2,  j= 6  
  出力:N = 10001001100

  出展:『世界で闘うプログラミング力を鍛える150問』
  http://www.amazon.co.jp/exec/obidos/ASIN/4839942390/gaius-22/



それでは良いお年を!
来年また『C#プログラミングレッスン』でお会いしましょう。
1月中旬ごろに No384を発行する予定です。


─────────────────────────────────────
『C#プログラミングレッスン』  (ほぼ週刊)
☆皆さまからの感想をお待ちしています。http://gushwell.ifdef.jp/mail.html
─────────────────────────────────────
Published by Gushwell.
Copyright (C) 2013 Gushwell All rights reserved.
Microsoft MVP for Visual C#(Apr 2005 - Mar 2014)

■Gushwell's Page
facebook Page                     : http://www.facebook.com/CSharpLesson
Gushwell's C# Dev Notes           : http://gushwell.ldblog.jp/
Gushwell's C# Programming Page    : http://gushwell.ifdef.jp/
気ままな読書ノート                : http://gwbooks.hatenablog.com/
Twitterアカウント                 : @gushwell
─────────────────────────────────────

規約に同意してこのメルマガに登録/解除する

メルマガ情報

創刊日:2004-08-12  
最終発行日:  
発行周期:ほぼ週刊  
Score!: 非表示   

コメント一覧コメントを書く

この記事にコメントを書く

上の画像で表示されている文字を半角英数で入力してください。

※コメントの内容はこのページに公開されます。発行者さんだけが閲覧できるものではありません。 コメントの投稿時は投稿者規約への同意が必要です。

  • コメントはありません。