パズル：おいらの回答

one offやりまくってしまった。orz ideaとしてはheadとtailをとって短くしていく、tailとheadを入れ替える、ということ。再起が分からない人にはかけないやつね。

#include 
#include 
#include 


void reverse (char *str) {
  char head, tail;
  int len;


  len = strlen(str);
  if (len == 0){
    return;
  }
  if (len == 1){
    return;
  }

  tail = *(str+len -1);
  *(str+len -1) = '\0';
  head = *str;
  reverse(str+1);
  *(str+len -1) = head;
  *str = tail;
  return;
}

int main (int argc, char *argv[]) {
  if (argc *lt;= 1) {
    printf("give me a string\n");
    exit(1);
  }
  char *str = argv[1];

  reverse(str);
  printf("%s\n", str);
  return 0;
}

思ったこと：

strlenを使ってよい（というか仕方ないだろう）はどーなのでしょうか。中身loopだからこれ実行したらO(n^2)だよ、多分。

まあ、パズルだから許されるだろうけど、職場で同僚がこういうコードを書いていたらヤバい。なぜなら：

from ゲリラ的雇用面接のすすめ 関数の実行速度は充分速いか？ strlen を何回呼ぶ事になるのか考えてみよう。 かつて私はO(n)であるべきstrrevのアルゴリズムがO(n^2)になってしまっている アルゴリズムを目にした事がある。彼らは繰り返しの strlen をループの中で呼ん でしまっていたのだ。 まあ、問題を

void reverse (char *start, char *end) {
    return;
}

とか書き換えればいいのですが（C++のイテレータチックだな）そうすると問題が変わってしまう。

やる気に関する驚きの科学 (TED Talks)に出てくる、この絵の問題のようなものだ。

オリジナルCパズルの問題は前者、書き換えたものはfor dummiesになっているのではないかと思う。