Latest Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Problem51--60

Problem 51:

Problem41--50

Problem 41:
最大の pandigital prime を求める問題.
Pandigital number を生成して prime かどうかをチェックしていく.
試してないけど brute force でもいける気がする.

Problem 42:
三角数に関する問題.
三角数かどうかの判定が書けるかどうかを試されている?

Problem 43:
Pandigital numbers に関する問題.
d_8,d_9,d_10 としてあり得るものを列挙 => d_7 としてあり得るものを列挙 => ... という手順で求める.

Problem 44:
五角数に関する問題.
P_kに対して小さい方から網羅的にDの候補を求めていき,より小さいものがないと分かるまで続ける.

Problem 45:
三角数であり五角数でもあり六角数でもある数を求める問題.
Brute force.

Problem 46:
Goldbach の conjecture の反例を求める問題.(あの有名な conjecture ではない)
Brute force.

Problem 47:
Consecutive numbers に関する問題.
問題文がわかりずらいので,問題を少し変えると次のようになる.
-- ここから問題 --
自然数に関する述語Pを次のように定義する.
P(n) = n の約数のうち素数であるものの個数が 4.
このとき,P(n) かつ P(n+1) かつ P(n+2) かつ P(n+3) となるような n を求めよ.
-- 問題ここまで --
これであれば誤解を生まないでしょう.
Brute force.

Problem 48:
大きな数の計算問題.
多倍長整数が扱えるのであれば単純に計算するだけ.
なくとも計算の度に剰余を取れば 64bit で足りる.

Problem 49:
等差数列,素数,permutations に関する問題.
Brute force.

Problem 50:
Consecutive primes に関する問題.
とりあえず50万までの素数p_iを求める.
あとは小さい方からの総和(p_0 + ... + p_i)を求めておいて,和が大きいほうから探索すればいいでしょう.

Problem 31--40

後輩ががんばってるようなので,久しぶりに続きを.

Problem 31:
最適なコインの組み合わせ問題.
DP の典型的な例.

Problem 32:
Pandigital に関する問題.
Product として取りうる範囲の上界は簡単に計算できるので,あとは brute force.

Problem 33:
分数の約分に関する問題.
範囲が狭いので brute force.

Problem 34:
階乗に関する(?)問題.
探索範囲の上界は簡単に求まるので,他と同様 brute force.

Problem 35:
素数に関する問題.
これも brute force.

Problem 36:
回文数に関する問題.
これまた brute force.

Problem 37:
素数に関する問題.
またまた brute force.

Problem 38:
Pandigital に関する問題.
Brute force.

Problem 39:
直角三角形に関する問題.
Brute force.

Problem 40:
なぜ少数にしたのかがよくわからない問題.
n が与えられたら d_n を求める O(log) の関数は比較的簡単に定義できるので,それを使って直接求める.


雑感:
まだ brute force が多い.
学部の教科書に載ってるようなアルゴリズムをちゃんと理解できる人
(かつ,問題文の意味がちゃんとわかる人)ならまだまだ簡単な問題ばかりでしょう.

Problem 21--30

数年前からプロフィールを変えていなかったので,正しい情報に更新しました.
って誰も見てないだろうけど…

ということで(?),早速 Project Euler.

Problem 21:
友愛数を求めろという問題.
範囲が狭いので単純に計算すればいいでしょう.

Problem 22:
問題の意図がよくわからない.
ソートしてからそれぞれのスコアを計算するだけ.

Problem 23:
過剰数(で合ってたかな?)に関する問題.
28124以上の数は2つの過剰数の和で表されることが証明されている(?)らしい.
要求されているのは過剰数の和で表すことができない数をすべて求めろというもの.
範囲が狭いので,過剰数を求めてからすべての組み合わせを考えればOK.

Problem 24:
実際にすべての組み合わせを生成してから数えても1分もかからないと思う.
もっと早く計算したければ,階乗を基にした表現(階乗進数とでもいうのだろうか)に変換するとほとんど答えがでる.

Problem 25:
フィボナッチに関する問題.
単純に計算するだけ.

Problem 26:
循環小数に関する問題.
こちらも単純に数えるだけ.

Problem 27:
素数生成式に関する問題.
これも範囲が狭いのでループをぶん回しましょう.

Problem 28:
数表の対角線の合計を求める問題.
各層(一周)の隅の合計値は簡単に求められるので,501番目の層までの合計を求めればいい.

Problem 29:
a^b の並べ替え(?).
全部求めてから,ソートするなりなんなりして違う数が何個あるのかを数えましょう.
ライブラリで集合を使える場合は,集合を使えば楽ですね.

Problem 30:
各桁の5乗の和が元の数字になる数を探す問題.
元の数が999999以上だと演算結果が元の数に届かなくなるので,999999まで調べればいい.

Problem11--20

前回の記事から1ヶ月も経っていますが,Project Eulerです.
どういう形式で書いていたかも忘れてしまった.

Problem 11:
数表の中で隣り合う数の積が最大となるものを探す問題.
brute force で問題ないでしょう.

Problem 12:
約数の数を数えさせる問題.
探索範囲(?)がそんなに広くないので,素因数分解してもいいし,単純に約数を数えてもいいでしょう.

Problem 13:
大きい数を扱う問題.
多倍長整数を扱えるなら単純に足して問題ないでしょう.
扱えなくても,この程度の精度であれば浮動小数点数を使えば答えが出る.

Problem 14:
コラッツ予想に関する問題.
何も工夫することはない.

Problem 15:
組み合わせの問題.
重複順列(であってたっけ?)を計算するだけ.

Problem 16:
大きい数を扱う問題.
何も考えず計算するだけ.

Problem 17:
Let's count in English! というわけで,これはかなり面倒.
問題設定(流儀)にあったライブラリがあれば楽なんだけどなぁ.
あと,デバッグ法が一つ一つ見ていくしかないというのも嫌だ.

Problem 18:
いかにもな DP(Dynamic Programming) の問題.
…他にコメントなし.

Problem 19:
曜日を判定する問題.
有名なアルゴリズムがいくつかあるので,それを使いましょう.
言語によっては標準ライブラリにあるかもしれないですね.

Problem 20:
単純に計算するだけ.

Appendix

プロフィール

airobo

Author:airobo
プログラミング言語理論をやっている大学院生.

ブログ検索

FC2カウンター

ブロとも申請フォーム

この人とブロともになる

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。