アルゴリズム 教えてください

必修科目「数学」、選択必修科目「歴史」と選択必修科目「地理」の3科目がある。ある2人の学生に対して「二人とも進級」か「一人が留年」あるいは「二人とも留年」を出力する問題を考える。ただし、進級条件は「必修科目に合格し、かつ2科目の選択必修科目の少なくとも1科目に合格していること」とし、全学生が3科目とも履修しているものとする。

実行結果
ある一人の学生が進級する科目取得パターンを全て書いてください
(例) 数学「合格」歴史「不合格」地理「合格」

実行結果
この問題に対するアルゴリズム（手順）のステップを書いてください

実行結果
そのときの最大時間計算量(1点)、領域計算量(1点)をそれぞれ求めよ。

すべて教えていただきたいです。

No.3 回答者： takahashi22 回答日時： 2013/06/29 18:51

この種の、授業で出された課題を、そのまま、ok waveに質問する事は、禁じられています。

No.2 回答者： pixie-grasper 回答日時： 2013/06/28 15:47

アルゴリズムじゃなくて確率論と計算機工学ですよね？

1.
数学「合格」歴史「不合格」地理「合格」
数学「合格」歴史「合格」地理「不合格」
数学「合格」歴史「合格」地理「合格」

2.
次の数式を(JavaならJavaで)ゴリッと計算すればよろしいのでは。
{x ∈ {数学,歴史,地理}×{「合格」,「不合格」} | {数学,「合格」} ∈ x ∧ ({歴史,「合格」} ∈ x ∨ {地理,「合格」} ∈ x)}

3.
あなたがどのようなアルゴリズムを用いて実装するかにもよる。
おそらく多項式時間・多項式領域となるかと

No.1 回答者： Tacosan 回答日時： 2013/06/28 15:30

「教えてほしい」ってのは「質問」じゃないよな.

「
実行結果
ある一人の学生が進級する科目取得パターンを全て書いてください
(例) 数学「合格」歴史「不合格」地理「合格」
」
も何を言っているのかわからんし. 何の「実行結果」なんだ?