Problem 122
の編集
http://odz.sakura.ne.jp/projecteuler/index.php?Problem+122
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[Problem 122:http://projecteuler.net/problem=122]] 「効率的なべき乗計算」 [#yf9288c3] &tex{n^{15}};を求めるのに最も単純な方法では 14 回の掛け算が必要である. >>> n × n × ... × n = &tex{n^{15}}; しかし2進法を用いれば, 6 回の掛け算で計算できる. >>> n × n = &tex{n^{2}};~ &tex{n^{2}}; × &tex{n^{2}}; = &tex{n^{4}};~ &tex{n^{4}}; × &tex{n^{4}}; = &tex{n^{8}};~ &tex{n^{8}}; × &tex{n^{4}}; = &tex{n^{12}};~ &tex{n^{12}}; × &tex{n^{2}}; = &tex{n^{14}};~ &tex{n^{14}}; × n = &tex{n^{15}}; ところがたった 5 回の掛け算のみでも計算できる. >>> n × n = &tex{n^{2}};~ &tex{n^{2}}; × n = &tex{n^{3}};~ &tex{n^{3}}; × &tex{n^{3}}; = &tex{n^{6}};~ &tex{n^{6}}; × &tex{n^{6}}; = &tex{n^{12}};~ &tex{n^{12}}; × &tex{n^{3}}; = &tex{n^{15}}; m(&tex{k};)を &tex{n^{k}}; を求めるのに必要最低限な掛け算の回数と定義する. たとえば m(15)=5 である. 1 ≤ &tex{k}; ≤ 200 に対し, Σ m(&tex{k};) を求めよ.
タイムスタンプを変更しない
*[[Problem 122:http://projecteuler.net/problem=122]] 「効率的なべき乗計算」 [#yf9288c3] &tex{n^{15}};を求めるのに最も単純な方法では 14 回の掛け算が必要である. >>> n × n × ... × n = &tex{n^{15}}; しかし2進法を用いれば, 6 回の掛け算で計算できる. >>> n × n = &tex{n^{2}};~ &tex{n^{2}}; × &tex{n^{2}}; = &tex{n^{4}};~ &tex{n^{4}}; × &tex{n^{4}}; = &tex{n^{8}};~ &tex{n^{8}}; × &tex{n^{4}}; = &tex{n^{12}};~ &tex{n^{12}}; × &tex{n^{2}}; = &tex{n^{14}};~ &tex{n^{14}}; × n = &tex{n^{15}}; ところがたった 5 回の掛け算のみでも計算できる. >>> n × n = &tex{n^{2}};~ &tex{n^{2}}; × n = &tex{n^{3}};~ &tex{n^{3}}; × &tex{n^{3}}; = &tex{n^{6}};~ &tex{n^{6}}; × &tex{n^{6}}; = &tex{n^{12}};~ &tex{n^{12}}; × &tex{n^{3}}; = &tex{n^{15}}; m(&tex{k};)を &tex{n^{k}}; を求めるのに必要最低限な掛け算の回数と定義する. たとえば m(15)=5 である. 1 ≤ &tex{k}; ≤ 200 に対し, Σ m(&tex{k};) を求めよ.
テキスト整形のルールを表示する
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
