課題(2002年度)の講評と解答例

• 深さ優先探索と幅優先探索ですが、実は計算量が違います。 深さ優先探索の場合、問題 2 は、同じリンクを何度もたどる必要があります。 このため、ノード数 n に対して、最悪の計算量は O(nの二乗)になってしまいます。

• プログラムの作成ですが、まずは概略をつかむのが重要でしょうね。たとえば、問題 1 (解答例D1的)なら、

  
  void problem1(Page_tp page) {
      if(page がHTMLなら) {
          for(子供に対して) {
              リンクを増やして、
              if(子供への最初の訪問なら) 
                  子供への再帰的処理
          }
      }
  }
  

  とかね。で、これって、ヒントに書いているのとあまり変わらないすよね？
  で、ここまで出来れば、その詳細を埋めるだけです。すこしずつ頑張ればいい。

• コンパイルをすると Warning が出る人が結構いました。 というのも、program 中に problem1() とかいう関数をつくっているのですが、 関数定義する前に、それを使っている人が多かったからです。
  そういう場合は、使う前に宣言してから使いましょう。 内部用途に使う関数に関しては、 head file にいれてくれてもいいですが、たとえば冒頭にまとめて書いておくと 良いでしょう。こんな感じ。

  void problem1(Page_tp page);
  void problem2(Page_tp page, int depth);
  
  void userSearch(Page_tp page) {
      problem1(page);
      problem2(page, 0);
  }
  

• index.html の扱いに苦労している人が多いようですね。 で、毎回 strcmp をしている人も多かったのですが、正直、あんまりお薦めできません。毎回文字列比較することに なりますし。
  ということで、たとえば、index.html かどうかの flag なりを持つ方が無難でしょう。 今回なら、visited flag を持たせれば解決出来そうですが。

  それから、visited flag に関しては、うまく処理するとなくすこともできます。

  • たとえば、inverseLink を使って最初の訪問か確認するとか。
  • index.html の depth に関しては、0 以外の値を設定するようにして、 depth == 0 かどうかをみることで、最初の訪問かどうか判定するとか。
  とはいえ、無理せず分かりやすいプログラムを心掛けるのがよいでしょう。

• 文字列の比較は str0 == str1 ではダメです。 以下のプログラムを見れば実感できるでしょう。sample0 と sample1 は内容が一緒でも別の配列ですから。

  
  int foo() {
      char sample0[] = "index.html";
      char sample1[] = "index.html";
      if(sample0 == sample1) => false になるでしょう、、、
  

• segmentation fault とかがでる人は、まずは gdb 上で走らせてみる。 で、止まったときの状態をみます。
  print コマンドを使って、各 pointer がおかしな値でないか確認する。
  where コマンドを使って、呼び出し関係がおかしくなっていないか確認。

• 実行中にエラーは出ないが、実行結果がおかしい。
  こういうときは、おかしくなった瞬間を知りたいものでしょう。 たとえば、XXXX.html の depth が本来 2 なのに 4 になっていると します。そういうときは、僕ならこんな感じにします。

  void whywhywhy() { /* 停止したいときは、  *NULL = 0; とか書いておく*/}
  
  void problem2(Page_tp page) {
       ......
  
       /* 以下のコードを挿入 */
       {
           Page_tp target = 調査したいもの;
           if((strcmp(getName(target), "XXXX.html") == 0) && (userArea(target)->depth >= 3)) 
               whywhywhy();
       }
  
       ......
  }
  

  で、gdb で break whywhywhy しておけば、トラブルが起きた瞬間を捕らえることができます。 入力が大きい場合でも、問題箇所を簡単に終えるでしょう。

• 挙動を追っ掛けましょう。
  たとえば、しっかり追っ掛けたい関数に break point をいれて実行を 追っ掛けるとか。
  あるいは、各関数の冒頭に引数などを print してみるとか。
  入力が大きくて分かりにくい場合は、問題サイズを小さくしてみましょう。 ちなみに、このプログラムは、input.def を編集すれば問題を変更できます。採点プログラムは機能しないけど。

まずは、深さ優先的に問題を解いた場合について載せます。 この場合、再帰を使って書くのが素直でしょう。