Problem 101
の編集
http://www.odz.sakura.ne.jp/projecteuler/index.php?Problem+101
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[Problem 101:http://projecteuler.net/problem=101]] 「最適多項式」 [#j6ed0aef] 数列の&tex{k};個の項を与えられたときに, 次の項を確実に求めることは不可能である. その数列に合うような多項式が無限個存在するからである. 例として, 立方数の数列を考えよう. これは生成関数 &tex{u_{n}}; = &tex{n^{3}}; で定義され, 1, 8, 27, 64, 125, 216, ...となる. この数列の最初の2項のみが与えられているとしよう. "Simple is best"の法則にのっとり, 線形の関係があると仮定し, 3つ目の項が15であると予想する (差分が7). もし最初の3項のみが与えられていたとしても, 同じ原則により, 二次の関係があると仮定して次の項を予測する. 数列の最初の&tex{k};項を生成できる最適な多項式の&tex{n};項を OP(&tex{k};, &tex{n};) で表すことにする. 明らかに, &tex{n}; ≤ &tex{k}; について OP(&tex{k};, &tex{n};) は正しい. 最初の異なる項 (First Incorrect Term, FIT) は OP(&tex{k};, &tex{k+1};) であろう. これを &tex{bad OP}; (BOP) と呼ぶことにする. 原則より, 最初の項しか与えられていない場合には, 定数項とするのが理に適っているだろう; 即ち, &tex{n}; ≥ 2, OP(1, &tex{n};) = &tex{u_{1}};. 従って, 立方数の数列について以下のOPを得る. |OP(1, n) = 1 | 1, &color(red){1};, 1, 1, ...| |OP(2, n) = 7&tex{n};−6 | 1, 8, &color(red){15};, ...| |OP(3, n) = &tex{6n^{2}};−11&tex{n};+6 | 1, 8, 27, &color(red){58};, ...| |OP(4, n) = &tex{n^{3}}; | 1, 8, 27, 64, 125, ...| 明らかに, &tex{k}; ≥ 4 のときにはBOPは存在しない. BOPsのFITs (上の例では赤で示されている) の和は, 1 + 15 + 58 = 74 である. 以下の10次多項式からなる生成関数を考える: CENTER:&tex{u_{n} = 1 - n + n^{2} - n^{3} + n^{4} - n^{5} + n^{6} - n^{7} + n^{8} - n^{9} + n^{10}}; BOPsのFITsの総和を求めよ.
タイムスタンプを変更しない
*[[Problem 101:http://projecteuler.net/problem=101]] 「最適多項式」 [#j6ed0aef] 数列の&tex{k};個の項を与えられたときに, 次の項を確実に求めることは不可能である. その数列に合うような多項式が無限個存在するからである. 例として, 立方数の数列を考えよう. これは生成関数 &tex{u_{n}}; = &tex{n^{3}}; で定義され, 1, 8, 27, 64, 125, 216, ...となる. この数列の最初の2項のみが与えられているとしよう. "Simple is best"の法則にのっとり, 線形の関係があると仮定し, 3つ目の項が15であると予想する (差分が7). もし最初の3項のみが与えられていたとしても, 同じ原則により, 二次の関係があると仮定して次の項を予測する. 数列の最初の&tex{k};項を生成できる最適な多項式の&tex{n};項を OP(&tex{k};, &tex{n};) で表すことにする. 明らかに, &tex{n}; ≤ &tex{k}; について OP(&tex{k};, &tex{n};) は正しい. 最初の異なる項 (First Incorrect Term, FIT) は OP(&tex{k};, &tex{k+1};) であろう. これを &tex{bad OP}; (BOP) と呼ぶことにする. 原則より, 最初の項しか与えられていない場合には, 定数項とするのが理に適っているだろう; 即ち, &tex{n}; ≥ 2, OP(1, &tex{n};) = &tex{u_{1}};. 従って, 立方数の数列について以下のOPを得る. |OP(1, n) = 1 | 1, &color(red){1};, 1, 1, ...| |OP(2, n) = 7&tex{n};−6 | 1, 8, &color(red){15};, ...| |OP(3, n) = &tex{6n^{2}};−11&tex{n};+6 | 1, 8, 27, &color(red){58};, ...| |OP(4, n) = &tex{n^{3}}; | 1, 8, 27, 64, 125, ...| 明らかに, &tex{k}; ≥ 4 のときにはBOPは存在しない. BOPsのFITs (上の例では赤で示されている) の和は, 1 + 15 + 58 = 74 である. 以下の10次多項式からなる生成関数を考える: CENTER:&tex{u_{n} = 1 - n + n^{2} - n^{3} + n^{4} - n^{5} + n^{6} - n^{7} + n^{8} - n^{9} + n^{10}}; BOPsのFITsの総和を求めよ.
テキスト整形のルールを表示する