パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

C言語入門、東京大学情報科学科の場合」記事へのコメント

  • 自己解決能力 (スコア:3, すばらしい洞察)

    by Inetpub (20077) on 2008年01月25日 13時06分 (#1286321)
    PDF「課題について」より抜粋

    •実装上で不明な点があれば,まずGoogle やman コマンド等を駆使して,
      自分で解決することを推奨する.もちろん,適当な書籍を調べるのも構わない.
      •すなわち,課題を解答するだけでなく,「分からない事を自分で調べながら
      解決していく」事も課題の一部とする.

    自由課題の難しさだけクローズアップされてるけど
    ”こういうことをちゃんと教えてる”ってのも結構重要な気がする

    #とりあえず自分が提出するなら2-A
    • Re:自己解決能力 (スコア:1, おもしろおかしい)

      by Anonymous Coward on 2008年01月25日 13時49分 (#1286376)
      そうそう、OKWave [google.com]などに頼るんじゃないよ、学生諸君。
      親コメント
    • by Anonymous Coward on 2008年01月25日 20時14分 (#1286600)
      そういえば、非効率なソートアルゴリズムを考えろという
      課題を出されたことがあったな。そんなもん、調べても
      中々出てないんで参った。考えたアルゴリズムに対して
      無い知恵絞って計算量を見積もってレポートしたっけ……

      # 疎な非負整数列を仮定して 1を探して、2を探して…… という
      # レポートを返却した記憶がある。
      親コメント
      • Re:自己解決能力 (スコア:2, 参考になる)

        by jijijiji (30845) on 2008年01月26日 2時37分 (#1286867)
        少しこの問題を考えてみました。

        与えられた数列(大きさ n)を適当に並べたものを1つの文字列とみなします。
        数列の並べ方は n! 通りあるので、全並べ方を考えると n! 個の文字列ができます。
        この n! 個の文字列を辞書式順でソート(*)すると、先頭に来た文字列は
        元の数列のソートされたものになっているので、これを出力します。

        (*)の部分は挿入ソートを使うことにすると、計算時間は O((n!)^2) となります。

        さらに(*)の部分にこのソート法を使う(n! 個の文字列を並べたもの1つの文字列とみなして、
        (n!)! 通りの並べ方を考える)と、O(((n!)!)^2) になります。

        さらに同様のことを繰り返すと、いくらでも遅いアルゴリズムが作れます。
        親コメント
      • by Anonymous Coward on 2008年01月25日 20時42分 (#1286618)
        運よく整列するまでランダムに並べかえるのを繰り返すってのはどうだろう?
        親コメント
        • by Anonymous Coward on 2008年01月26日 2時28分 (#1286862)
          そのアルゴリズムにはちゃんとボゴソート [wikipedia.org]って名前が付いてますよ。
          親コメント
        • by Anonymous Coward
          整列に成功したかどうか?を判定するために、
          たぶん他の(つまりもっとマシな)ソート手段を使うことになると思う。

          で、それだと流石に「全く無駄な」遠回りでしかないので、
          そんなのまともなセンセイならば認めてもらえないだろう。

          実際には、確実にソート終了に近づくアルゴリズムであり、
          ただしその近づき方が「遅すぎて」非効率だ、
          という回答が、認めてもらえるのだろう。
          • by jijijiji (30845) on 2008年01月26日 2時19分 (#1286860)
            整列に成功したかどうかは a_1 と a_2、a_2 と a_3…と順に 比較するだけで判定できます(計算時間は O(n) )。
            ソーティング(最適アルゴリズムで O(n log n))よりは簡単です。
            親コメント
        • by Anonymous Coward
          これだと必ず停止する保証は無いので、アルゴリズムとは呼べません。
          • by Anonymous Coward
            >これだと必ず停止する保証は無いので、アルゴリズムとは呼べません。

            全ての組み合わせを舐める事を保証すればいいのでは?
            乱数発生ロジックと、全てのパターンを尽くしたかをチェックする
            テーブルを用意しでなんとかなりそうな気がするが。
            もちろん、テーブルを用意するので膨大な記憶空間も必要になり効率は落ちて点数アップですね。
    • by Anonymous Coward
      自己解決能力といえば、
      2chの宿題スレに礼儀正しく質問し、必要な情報を提供し
      よく空気を読み、的確な回答をもらってくる能力のことですね。

      # 何故か宿題スレに来る人はそれができないことが多かったり

あと、僕は馬鹿なことをするのは嫌いですよ (わざとやるとき以外は)。-- Larry Wall

処理中...