裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

ブルートフォースで十分

2015年11月04日 | ブログラミング

「グー」「チョキ」「パー」の「じゃんけん」により多数決をする。
一番多くの人が出した手が勝つ。
「一度で」勝つ手が決まるような人数の組み合わせは何通りあるか。
例えば、4 人の場合は 12 通り。3 種の人数は以下の 4 通り× 3。
4 0 0
3 0 1
3 1 0
2 1 1

ブルートフォースで簡単に書けるが,出題元のコンピュータが遅いので,このままでは時間制限に引っかかる。

> f = function(n) {
+     count = 0
+     for (a in n:0) {
+         bc = n-a
+         for (b in bc:0) {
+             c = bc-b
+             if (a == max(c(a, b, c)) && a != max(c(b, c))) {
+                 count = count+1
+             }
+         }
+     }
+     3*count
+ }
> system.time(f(1234))
   ユーザ   システム       経過  
     1.301      0.009      1.299

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

PVアクセスランキング にほんブログ村

PVアクセスランキング にほんブログ村