CodeIQ の @riverplus さん出題の問題。 の有理数の項を求めよというもの。 他の方のコードが http://togetter.com/li/911507 にある。 とすると、求める数 F(n) は を解に持つ方程式 を頑張って展開すると になるから、F(n) は差分方程式 を満たす。 なので…

最近 Project Euler の問題を解いているのだけど、使い回せるコードを探すのが大変になってきたのでここにまとめておくことにする。 前に他のプログラム中で使ったものだが、とりあえず Miller-Rabin 素数判定と Pollard のρ法(またはモンテカルロ法)による…

CodeIQ の Kawazoe さん出題の問題。 問題と他の方の解答が http://togetter.com/li/875421 にある。とりあえず項数 1 の数列を許すとして考える。項数が奇数のとき、m を項数とすると、(m によって定まる)初項 a(m) は 数列が整数列であるための必要十分条…

CodeIQ の Kawazoe さん出題の問題。 問題と他の方のコードが http://togetter.com/li/866620 にある。 をそれぞれ 0〜9 の数字の出現回数とする。 の10個の数を昇順に並べ替えたものを とする。 例えば n=4 のとき の組は次のいずれかになる。 0, 0, 0, 0, …

CodeIQ の Kawazoe さん出題の問題。 問題と他の方のコードが CodeIQ「カット・アンド・スクエア」問題 みんなのコード にまとまっている。 とする。 求める n 桁の整数の上下 n/2 桁をそれぞれ x, y とすると が成り立つ。 変形して として つまり を2平方…

CodeIQ の Kawazoe さん出題の問題。 他の方のコードが CodeIQ「フィズ・バズ・エクストリーム」問題 みんなのコード にまとまっている。 を互いに素な2以上の整数とし、f(n,k) を n 以下の正整数のうち のいずれかの倍数となるものの和とする。このとき と…

点集合の最小抱合円(点集合を周を含む内部に持つ最小の円)を O(N) の時間で求める Welzl のアルゴリズムというのがある。 論文が http://www.inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf で読める。 論文通りに実装すると、点の数が多…

前に書いたトリボナッチ数と同じようなやり方でフィボナッチ数を計算する方法。 自分が調べた範囲では、フィボナッチ数を計算する一番速いアルゴリズムだと思う。フィボナッチ数 とリュカ数 を で定義する。リュカ数を次の漸化式から計算して 、 フィボナッ…

CodeIQ の鍋谷武典さん出題の問題。 問題と解説はこちら。 CodeIQ に出した「中学入試から：対称軸の本数を数えよう」の 解説・解題下が解答に添えた説明。 円周が n 等分されているとして、図形を F とする。F を構成する線は2本以上とする。 円の中心と n …

CodeIQ の鍋谷武典さん出題の問題。 問題と解説はこちら。 CodeIQ に出した「中学入試から：概数と計算」の 解説解題下が提出したコード。言語は Ruby。浮動小数点で計算するとまずそうなので、有理数で計算するようにした。 コメントで '下限' を次の意味で…

CodeIQ のマシューさんの出題で、129桁の整数 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541 を素因数分解する問題が出た。 まともに計算すると、高速な素因数分解…

遠い世界の数式 http://nabetani.sakura.ne.jp/kanagawa.rb/evalex/ 解いてみた。まず最初に考えたもの。結構強引。 問題は最後の5問だけ。 class Fixnum def -(x) self | x end def ^(x) self + x end def >(x) self * x end end DATA.each do |expr| p eva…