R.Tanaka.Ichiro's Blog

主にC# な話題です

目次

Blog 利用状況

ニュース

ホワイトボードプログラミング

http://japan.zdnet.com/sp/feature/07tenthings/story/0,3800082984,20409456-2,00.htm
プログラマーの力量を見極める--面接官になったら尋ねるべき質問実例集(ZDNet Japan)

ここの「ループを使わずに配列の順序を逆にする。」って、どういう解答になるんだろう?
まさか、「array.Reverse();」ってことはないですよね。

ってことは、

再帰


を使う方法しか思い浮かばないけど・・・

こんな感じかなぁ?

static void Main(string[] args)
{
  var array = new [] { 1, 2, 3, 4, 5 };
  Reverse(array, 0, array.Length - 1);
  array.ToList().ForEach(Console.WriteLine);
  Console.ReadLine();
}
static void Reverse(int[] array, int begin, int end) {
  if (begin >= end) return;
  int t = array[begin];
  array[begin] = array[end];
  array[end] = t;
  Reverse(array, begin + 1, end - 1);
}

投稿日時 : 2010年3月4日 16:27

Feedback

# re: ホワイトボードプログラミング 2010/03/04 16:47 επιστημη

↓手動トラックバックぅ
http://blogs.wankuma.com/episteme/archive/2010/03/04/186775.aspx

# re: ホワイトボードプログラミング 2010/03/04 22:00 Gushwell

僕もかいてみました。
http://gushwell.ldblog.jp/archives/51982731.html

# re: ホワイトボードプログラミング 2010/03/04 22:59 長月葵

 最近再帰とループが区別つきません。

# re: ホワイトボードプログラミング 2010/03/05 11:04 みきぬ

配列を前半と後半にぶったぎって、後半を逆にしたものと前半を逆にしたものをつなげる。

…ていうのが、昔読んだ本に書いてあった。

# re: ホワイトボードプログラミング 2010/03/05 15:16 R・田中一郎

επιστημη さん

絶対反応すると思いましたw

------------------------------
Gushwell さん

>僕もかいてみました。

この手の問題って、見るとムラムラと解きたくなりますよね。

------------------------------
長月葵 さん

>最近再帰とループが区別つきません。

最近は、関数型言語の人ですか?

------------------------------
みきぬ さん

>配列を前半と後半にぶったぎって、後半を逆にしたものと前半を逆にしたものをつなげる。

うーん、今ひとつ想像ができない・・・

# re: ホワイトボードプログラミング 2010/03/05 15:54 みきぬ

配列を真ん中で分割して再帰すると言えばいいのかしら。
{ 1, 2, 3, 4, 5 } を { 1, 2, 3 } と { 4, 5 } に分けて、
{ 4, 5 } を逆にしたもの({ 5, 4 })と { 1, 2, 3 } を逆にしたもの({ 3, 2, 1 })を連結すれば、{ 5, 4, 3, 2, 1 } になるよね、と。

コードも一応書いてみたけど、他の方法と比べて優位な点が見あたらなかったので載っけない方向で…。

# re: ホワイトボードプログラミング 2010/03/08 16:15 R・田中一郎

なるほど、コッチのほうが速いのかな?

# re: ホワイトボードプログラミング 2010/03/08 18:30 みきぬ

> なるほど、コッチのほうが速いのかな?

どうだろう。
再帰の回数だけで考えても、R さんのに比べて多い気がするし…。

# re: ホワイトボードプログラミング 2010/03/10 15:41 R・田中一郎

再帰の深さは、みきぬさんの提示したロジックの方が浅くなりそうですが、要素の入れ替えの回数が多くなりますね。

QuickSort のアルゴリズムに近い気もしますけど、今回の場合は代入演算しか使わないので単純に入れ替え回数の少ない方が高速になるのかなぁ、と思いました。

後で検証してみましょう。

# re: ホワイトボードプログラミング 2010/03/11 10:01 みきぬ

一番の難点は、毎回の処理で配列のコピーが発生することだと思うんですよ。それでポイしました。
もしかして、もっといい実装方法があるのかなあ。

# re: ホワイトボードプログラミング 2010/03/12 16:51 R・田中一郎

入れ替えるとき、代入演算が3回実行されますから、これを減らせることができれば速くなるように思いますね。

# re: ホワイトボードプログラミング 2010/08/19 10:02 jpy

ループを使わずに配列の順序を逆にする。
* 再帰呼び出しはループに含めますか?→再帰呼び出しを知っていることを試したい?
* ライブラリを使ってもよいですか?→なんでも自作するのではなく、ライブラリを活用することを考えるかどうかを試したい?
* gotoとか使ってもよいですか?→細部にこだわりすぎ。パズル感覚で問題を解くのに夢中になりすぎかな?
* 質問すること自体が正解かもしれない。→仕様や前提条件の確認をするかどうか試したい?

私なら、回答と一緒に上の文章を添えておくかもしれないです。

# Having read this I thought it was very informative. I appreciate you taking the time and effort to put this information together. I once again find myself spending a lot of time both reading and commenting. But so what, it was still worth it! 2019/05/03 12:08 Having read this I thought it was very informative

Having read this I thought it was very informative. I appreciate
you taking the time and effort to put this information together.
I once again find myself spending a lot of time both reading and commenting.
But so what, it was still worth it!

# I don't even understand how I ended up here, however I believed this publish was once great. I don't know who you are however certainly you're going to a famous blogger for those who aren't already. Cheers! 2019/06/08 0:10 I don't even understand how I ended up here, howev

I don't even understand how I ended up here, however I believed
this publish was once great. I don't know who you are however certainly you're going to a
famous blogger for those who aren't already. Cheers!

タイトル  
名前  
Url
コメント