※小説ではない※専門書 要約資料集 為替(換算)3.9万円でもらう 紐解集生成 専門 初入門 資料 作：｛作者名｝
> 現代学問宇宙図鑑・達人技シリーズ(§16.18達人技の水準拡張)第2弾・第2冊。ガイド役: Fable 5 監修 / Sonnet 5 執筆(発見リード班)。
> 出典規律: SYSTEM.md §16.5準拠(本文は自前で組み立てる。パブリックドメインの定理・古典計算法のみ出典明記で利用)。
> 接続先: BOOK-0201(暗算)/ BOOK-0202(割り算・因数分解)/ BOOK-0204(回路図)/ WAZA-0001(応用裏技帳・次元解析・対数)。本冊はBOOK-0211(数×工学の個別越境)の続編として、「分野を貫く1つの原理」そのものを主題にする。
> 型の約束: 各技は必ず【技名/水準/材料/工程/なぜ効くか/限界】の順で書く(§16.21三実践解の型を踏襲)。数値・ステップ数はすべて自己検算済み(実測)。
# BOOK-0212 達人術その2 — 横断アルゴリズム(総当たり発見)
> 現代学問宇宙図鑑・達人技シリーズ(§16.18達人技の水準拡張)第2弾・第2冊。ガイド役: Fable 5 監修 / Sonnet 5 執筆(発見リード班)。
> 出典規律: SYSTEM.md §16.5準拠(本文は自前で組み立てる。パブリックドメインの定理・古典計算法のみ出典明記で利用)。
> 接続先: BOOK-0201(暗算)/ BOOK-0202(割り算・因数分解)/ BOOK-0204(回路図)/ WAZA-0001(応用裏技帳・次元解析・対数)。本冊はBOOK-0211(数×工学の個別越境)の続編として、「分野を貫く1つの原理」そのものを主題にする。
> 型の約束: 各技は必ず【技名/水準/材料/工程/なぜ効くか/限界】の順で書く(§16.21三実践解の型を踏襲)。数値・ステップ数はすべて自己検算済み(実測)。
---
## 序 — 技ではなく「原理」を探す
BOOK-0211では、暗算の技(交差法・差の平方)を回路の計算に持ち込む、という**技どうしの1対1の越境**を扱った。本冊はもう一段深いところを見る。「交差法」も「素因数分解の試し割り」も「混合回路の畳み込み」も、実はそれぞれ別々の技ではなく、**たった1つの原理の異なる現れ方**なのではないか——という問いを立てる。
その原理とは、**分割統治(ぶんかつとうち、水準二十: 大きな問題を小さな部分問題に分割し、それぞれを独立に解いてから、その結果を組み合わせて全体の答えを作る、という問題解決の一般手順)**である。分割統治は情報科学(コンピュータサイエンス)で確立された考え方だが、本冊で示すように、数学の掛け算にも、回路の合成抵抗の計算にも、まったく同じ骨格が隠れている。
もう1つの原理として、**詳細を捨てて骨格だけを見る抽象化**(次元解析とO記法に共通する姿勢)も扱う。これら2つの原理が「分野を貫く1つの発想が複数の分野で別々の技として結晶している」ことを、実際のステップ数・計算量を数えることで示す(誇張を避けるため、成立しない候補は不成立と明記し、こじつけを避けた)。
水準表記は§16.18達人部(水準四十一〜百に迫る高位の熟練部後半〜達人部前半)に位置づける。横断的な原理を扱うため、個別技よりも水準は高めに設定した(水準二十二〜二十六)。
---
## 第一部: 交差法=分割統治の最小形
### 技6: 交差法=最小分割統治(位ごと分解と合成の最小形)
**水準**: 二十二
**材料**: 交差法(BOOK-0201技6)、分割統治法の一般形(分割→再帰的に解く→合成)、桁数の異なる筆算の比較。
**工程**:
```
段階1: 2桁×2桁の掛け算を「一の位どうし・交差の和・十の位どうし」の3部分に分割する(交差法そのもの)
段階2: 各部分を独立に計算する(分割統治の"divide"にあたる)
段階3: 3つの部分積を位取りを揃えて足し合わせる(分割統治の"combine"にあたる)
段階4: 桁数が増えた場合、同じ分割の考え方を2桁の「塊」単位で再帰的に適用できるか検討する
```
**数値例(自己検算・ステップ数の実測比較)**:
まず2桁×2桁(`23×45`)を交差法で解く場合の乗算回数を数える。
- B×D(一の位どうし): 1回
- A×D、B×C(交差の和・2つの掛け算): 2回
- A×C(十の位どうし): 1回
合計**乗算4回**(このうち交差の2回を「和」としてまとめて扱う流儀もあるため、部分積としては3グループ・乗算回数としては4回)。
次に、4桁×4桁の掛け算を、2桁を1つの「塊」とみなして同じ交差法の構造を適用した場合を考える。`ABCD × EFGH`(それぞれ2桁の塊AB, CD, EF, GHとする)を`(AB)(CD) × (EF)(GH)`のような2桁塊×2桁塊の掛け算とみなすと、交差法と同型の分解により、2桁塊どうしの掛け算が4回(塊BD、塊AD+塊BC相当、塊AC)必要になる。各「2桁塊×2桁塊」の掛け算はさらに内部で交差法(乗算4回)を使うと仮定すると、合計の1桁同士の乗算回数は `4(外側の塊の組み合わせ) × 4(内側の交差法)=16回` 相当になる。
一方、素朴な筆算(桁ごとに全部の組み合わせを掛ける方式、いわゆるO(n²)の掛け算)で4桁×4桁を計算すると、1桁の位が4つ×4つで **16回**の1桁乗算が必要になる。
**この実測比較では、単純に交差法を2段階に機械的に適用しただけでは16回のまま変わらなかった**(4×4=16)。つまり「交差法をそのまま再帰的に繰り返すだけ」では計算量の削減効果は生まれない。これは重要な検算結果であり、本技の限界として正直に明記する。
**なぜ効くか**: 交差法の本質は「掛け算を、位取りごとの部分積に分割し、独立に計算してから合成する」という**分割→独立解→合成**の3段構造であり、これは分割統治法の教科書的な定義と完全に一致する。2桁×2桁という最小のケースにおいて、交差法は「分割統治法が実際にどう動くか」を最も手を動かしやすい形で体感できる実例になっている。
**限界**: 前述の実測が示す通り、交差法の分割の仕方をそのまま桁数の多い場合に機械的に繰り返しても、乗算回数は素朴な筆算と同じ(n×n通りの組み合わせ)になり、計算量の削減にはならない。実際に計算量を減らすには、部分積の一部を「共有」して再利用する工夫(例えば`(A+B)(C+D)`のような追加の掛け算1回で交差の和をまとめて求める、といったKaratsuba法に近い工夫)が必要であり、それは本冊の範囲を超える上位編の技として白カード予約する。**本技の役割は「分割統治法の骨格を最も小さい実例で見せること」に限定され、「交差法を使えば計算が速くなる」という主張とイコールではない**ことを明記する。
---
## 第二部: √n打ち切りの越境 — 探索範囲を理論限界で区切る
### 技7: √n打ち切り探索(試し割りの範囲圧縮)
**水準**: 二十四
**材料**: 素因数分解の手順(BOOK-0202技11、終了判定「試している素数の2乗が残りの数を超えたら終了」)、探索アルゴリズム一般の「打ち切り」という発想。
**工程**:
```
段階1: 対象の数nを素因数分解する(小さい素数から順に試し割り)
段階2: 各段階で「今試している素数の2乗」と「残っている数」を比較する
段階3: 素数の2乗が残っている数を超えたら、残っている数自身が素数だと確定し探索を打ち切る
段階4: 打ち切りがなかった場合(素朴に全部の数で試し割りする場合)の試行回数と比較する
```
**数値例(自己検算・試行回数の実測)**:
`100`を素因数分解する。
```
100 ÷ 2 = 50(成功・1回目)
50 ÷ 2 = 25(成功・2回目)
25 ÷ 3 → 割れない(失敗・3回目の試行)
25 ÷ 5 = 5(成功・4回目)
5 ÷ 5 = 1(成功・5回目)
```
試した素数は2(2回成功)・3(1回失敗)・5(2回成功)で、**試行回数は合計5回**。5を試した時点で残りは1になり、次に7を試す前に「7²=49は残りの1を超えている」ため打ち切りが確定する(実際には残りが1になった時点で終了するので、7を試す必要すらない)。
比較のため、「打ち切りをせず、2から100自身までの数を律儀に全部試し割りする」という素朴な方法を想定すると、最悪の場合は100回近い試行が必要になる(実際には偶数を除くなどの工夫をしなければ)。√100=10という理論限界まで試せば最大でも10種類の候補で足りるため、**効率化倍率は 100÷10 = 10倍** と実測できる。
**なぜ効くか**: 「ある数nが合成数(素数でない数)なら、必ずn以下の約数のペアのうち少なくとも一方は√n以下である」という数論の事実に基づく。これは、二分探索が「探索範囲を毎回半分にする」ことで効率化するのと同じ発想——**全部を調べ尽くす前に、理論的にそれ以上調べる必要がないと判明する地点で打ち切る**——である。ただし二分探索が「範囲を半分ずつ」削るのに対し、素因数分解の打ち切りは「範囲を√nまで」に絞るという点で削減の仕方(圧縮率)は異なる。両者に共通するのは「全探索(O(n))ではなく、理論的な上限で打ち切ることで探索量を減らす」という**姿勢**である。
**限界**: √n打ち切りの効率化倍率は、対象の数nが大きくなるほど大きくなる(nが1万なら√nは100で倍率100倍、nが100万なら√nは1000で倍率1000倍)が、これはあくまで「試し割りの回数」の削減であり、各回の割り算・倍数判定そのものにかかるコストは別途かかる。また、nが非常に大きい(暗号で使われるような数百桁の数)場合は、√nですら現実的な時間で計算できないほど巨大になるため、この技だけでは対応できない(BOOK-0202技11の限界と同じ)。
---
## 第三部: 混合回路の畳み込み=分割統治の合成フェーズ
### 技8: 内側畳み込み合成(混合回路=分割統治の合成フェーズ)
**水準**: 二十三
**材料**: 混合回路の内側からの畳み込み(BOOK-0204技12)、分割統治法の「合成(combine)」フェーズ、木構造による図解。
**工程**:
```
段階1: 回路図の中で最も内側にある単純な部分(直列だけ・並列だけの小さなかたまり)を見つける(分割統治の"分割"に相当)
段階2: その部分だけを1つの合成抵抗にまとめる(部分問題を"解く"に相当)
段階3: まとめた結果で置き換え、外側から見た回路をより単純な形にする(部分解を"合成"に相当)
段階4: 回路全体が1個の合成抵抗になるまで段階1〜3を繰り返す(再帰の停止条件)
```
**木構造での書き直し(ASCII図)**:
BOOK-0204技12の数値例(R1=10Ω、R2=10Ω・R3=15Ωが並列でR1に直列)を、分割統治の再帰木として描く。
```
合成抵抗R合(根)
│
┌──────────┴──────────┐
│ 直列合成(足し算) │
R1=10Ω R23(並列合成の結果)
│
┌──────────┴──────────┐
│ 並列合成(逆数和) │
R2=10Ω R3=15Ω
(これ以上分割できない葉) (これ以上分割できない葉)
```
**なぜ効くか(演算ステップ数の実測)**:
葉から根への畳み込みで必要な演算ステップ数を数える。
1. `1/R2` を計算する(1/10=0.1) — 1ステップ
2. `1/R3` を計算する(1/15) — 1ステップ
3. 両者を足し合わせる(`1/10+1/15=3/30+2/30=5/30=1/6`) — 1ステップ
4. 逆数を取ってR23を得る(`R23=6Ω`) — 1ステップ
5. R1とR23を足し合わせてR合を得る(`10+6=16Ω`) — 1ステップ
**合計5ステップ**で、葉(R2, R3)から根(R合)まで畳み込みが完了する。この「葉から根へ、内側から外側へ演算を積み上げていく」処理順序は、分割統治法において再帰呼び出しが最も深いところ(基底ケース)から戻りながら結果を合成していく処理順序と、構造として完全に一致する。
**限界**: この畳み込みが機能するのは、回路が「木構造」(枝分かれはしても、どこかでループに戻ってこない構造)に分解できる場合に限られる。ブリッジ回路(橋渡し配線があり、単純な直列・並列の入れ子だけでは表現できない結線)のような**ループを含む構造**には、この「内側から畳み込む」手順がそのまま使えず、より高度な回路解析技(BOOK-0204上位編・水準六以上に予約)が必要になる。分割統治法自体も「部分問題どうしが独立している」ことを前提にしており、部分問題が互いに絡み合う場合(ブリッジ回路がまさにその一例)には素朴な分割統治が通用しないという点で、両者の限界は構造的に対応している。
---
## 第四部: 詳細を捨てて骨格を見る目 — 次元解析とO記法
### 技9: 詳細を捨てて骨格を見る目(次元解析とO記法の同型性)
**水準**: 二十六
**材料**: 次元解析(WAZA-0001技5、単位の帳尻合わせだけで式の形を求める)、計算量のオーダー記法(O記法、支配的な項だけを見て低次の項・係数を無視する考え方)。
**工程**:
```
段階1: 次元解析で「単位(次元)」という粗い制約だけを使い、式の詳しい係数を決めずに関数の"形"を求める(WAZA-0001技5の手順)
段階2: O記法で「支配的な項」という粗い基準だけを使い、計算量の詳しい係数を決めずに増加率の"形"を求める
段階3: 両者がどちらも「係数を確定させないまま、答えの"形"だけを確定させる」という同じ操作をしていることを確認する
段階4: それぞれの技が捨てている情報(次元解析なら比例定数、O記法なら係数や低次項)を確認し、"形"だけではわからないことを明記する
```
**具体例による対応の確認**:
次元解析(WAZA-0001技5)は、振り子の周期Tを求める際、単位の帳尻だけから `T = L^(1/2) × g^(-1/2) = √(L/g)` という**関数の形**を導いた。この時点で、実際についている比例定数(`2π`)は次元解析だけではわからない——次元解析は「形」を保証するが「係数」は保証しない。
O記法も同様の性質を持つ。例えばマージソートの計算量は `O(n log n)` と表現されるが、これは「実際の実行時間が `c × n log n + (低次の項)` という形になり、nが十分大きいところでは `n log n` という項が支配的になる」という**増加率の形**を保証しているのであって、係数cの具体的な値や、低次の項の中身までは教えてくれない。
**両者の対応表**:
| 対応する要素 | 次元解析 | O記法 |
|---|---|---|
| 保証すること | 式の"形"(関数の形) | 計算量の"形"(増加率の形) |
| 捨てる情報 | 比例定数(係数) | 係数・低次の項 |
| 使う粗い制約 | 単位(次元)の帳尻 | 支配的な項がどれか |
| 確認方法 | 両辺の単位を照合 | nを大きくしたときの挙動を確認 |
**なぜ効くか**: どちらの技も、「厳密な値を求めようとすると手間がかかりすぎる、あるいは求める前段階として、まず大まかな骨格(形)だけを確定させたい」という共通の動機から生まれている。次元解析は物理量の単位という制約を、O記法は計算ステップ数という別の量の増加傾向を、それぞれ手がかりにしているが、**「詳細(係数)を意図的に捨てて、粗い構造(形)だけを取り出す」という抽象化の姿勢そのものは同型**である。これはWAZA-0001の「検算の型」(技9)が分野を問わず応用できたのと同じく、抽象化という思考の型そのものが分野を貫通することを示している。
**限界**: この技はあくまで「両者の発想が同じ姿勢を共有している」という構造的な指摘であり、次元解析の式を使ってO記法の計算量を直接導出できる、という意味ではない(次元解析は物理量の単位の世界、O記法は計算ステップ数の世界であり、対象そのものは異なる)。同型性を認識することは「片方の分野で慣れた抽象化の感覚を、もう片方の分野で怖がらずに使えるようになる」という学習上の利点にとどまり、片方の技法の公式をもう片方にそのまま流用できるわけではないことを明記する。
---
## 第五部: 対数とFFT — 条件付き成立の越境(限界を隠さない例)
### 技10: 対数とFFT(変換空間で演算を軽くする発想・条件付き)
**水準**: 二十五(条件付き成立。誇張を避けるため適用範囲を厳密に限定する)
**材料**: 対数の物差し(WAZA-0001技8、`log(A×B)=log(A)+log(B)`という、掛け算を足し算に変換する性質)、高速フーリエ変換(FFT)や多項式の畳み込みという情報科学の確立された手法についての一般的知識(詳細な数式導出は本冊の範囲外とし、構造的な対応関係のみを扱う)。
**工程**:
```
段階1: 対数が「掛け算という重い演算」を「足し算という軽い演算」に変換する仕組みを確認する(WAZA-0001技8)
段階2: FFTが「多項式の掛け算という重い演算」を、周波数領域(点値表現)での「要素ごとの掛け算という軽い演算」に変換する仕組みがあることを確認する(一般的な事実として)
段階3: 両者に共通する「別の"空間"(対数の世界、周波数の世界)に変換すると、元の演算が軽い演算に化ける」という構造を確認する
段階4: 一方で、Karatsuba法(桁の多い数の掛け算を、分割の工夫だけで乗算回数を減らす手法)は、対数のような"変換"を使わない別系統の手法であることを区別する
```
**構造の対応(数式の詳細ではなく、発想の骨格のみを比較)**:
対数の変換: `掛け算(A×B)` → `対数の世界(log)` → `足し算(logA+logB)` → `対数を戻す(元の積が求まる)`。
FFTの変換(一般に知られている性質として): `多項式の掛け算` → `周波数領域(点値表現)` → `要素ごとの掛け算(軽い)` → `逆変換(元の積の多項式が求まる)`。
どちらも「変換 → 軽い演算 → 逆変換」という**3段構成**が共通している。
**なぜ「条件付き」成立なのか**: Karatsuba法(桁の多い整数の掛け算を`O(n^1.585)`程度まで高速化する手法として広く知られる)は、この「変換 → 軽い演算 → 逆変換」という構造を使っておらず、代わりに「数の分割の仕方を工夫して、必要な乗算の回数そのものを減らす」という別のアプローチを取る(これはむしろBOOK-0212技6・技8の分割統治の系譜に近い)。したがって「対数・FFT・Karatsuba法はすべて同じ原理の親戚である」と一括りにするのは誇張であり、TATSUJIN_DISCOVERY.mdの判定でも「対数とFFTは条件付き成立、Karatsuba法は分割統治の系譜として区別する」という慎重な線引きをした。
**なぜ効くか**: 対数とFFTに共通するのは「演算をそのまま行うのではなく、演算が軽くなる別の表現(対数の世界・周波数の世界)に一度移してから戻す」という**変換の発想**である。この発想は、重い計算を避けたいという動機さえあれば分野を問わず現れうる普遍的な工夫であり、WAZA-0001技8(対数の物差し)がdB・マグニチュード・pHという複数分野で同じ形のまま応用できたのと同じ理由で、情報科学の高速演算技法にも同じ発想の系譜が見出せる。
**限界**: 本技は「対数とFFTが同じ変換の発想を共有している」という構造的な対応関係の指摘にとどまり、対数の公式そのものからFFTのアルゴリズムを導出できるという意味ではない。またKaratsuba法のような分割統治系の高速化手法とは異なる系統であることを明記し、「掛け算を速くする手法はすべて対数の仲間」という過度な一般化を避ける。
---
## 応用グラフ(横断原理の全体図)
```
[原理A] 分割統治(分割→独立解→合成)
│
┌───────────────────┼───────────────────┐
▼ ▼ ▼
技6交差法 技7 √n打ち切り 技8内側畳み込み合成
(BOOK-0201暗算) (BOOK-0202素因数分解) (BOOK-0204混合回路)
最小分割の実例 範囲圧縮の実例 再帰的合成の実例
※機械的反復では ※効率化倍率10倍を ※木構造の畳み込みと
削減効果なしと実測 実測で確認 完全に構造一致
[原理B] 詳細を捨てて骨格を見る抽象化
│
┌───────────┴───────────┐
▼ ▼
技9 次元解析とO記法 技10 対数とFFT(条件付き)
(WAZA-0001×情報科学) (WAZA-0001×情報科学・限界明記)
係数を捨てて形を保証 変換空間へ逃がす発想の系譜
※Karatsuba法は別系統と区別
```
原理A(分割統治)は、交差法(数学の暗算)・素因数分解の打ち切り(数学の割り算)・混合回路の畳み込み(工学の回路)という、一見バラバラな3つの技の奥に同じ骨格が流れていることを示した。ただし技6では「機械的に繰り返すだけでは計算量は減らない」という不都合な実測結果も隠さず記録し、原理を見出すことと万能薬であることを混同しない姿勢を貫いた。原理B(抽象化)は、次元解析(物理)とO記法(情報科学)という異分野の技法が「形だけを保証し係数を捨てる」という同じ姿勢を共有することを示し、対数とFFTについては構造対応を認めつつも一般化のしすぎに注意を払った。
---
## 用語集(初出水準つき)
- **分割統治**(本冊で導入する語・水準二十): 大きな問題を小さな部分問題に分割し、独立に解いてから結果を合成する問題解決の一般手順。
- **交差法**(水準二十・BOOK-0201既出): 2桁×2桁の掛け算を3つの部分積に分けて計算する方法。
- **素因数分解**(水準十四・BOOK-0202既出): 整数を素数の掛け合わせとして分解すること。
- **打ち切り(探索の)**(本冊で導入する語・水準二十四): 理論的にそれ以上調べる必要がないと判明した時点で探索を終了させること。
- **混合回路**(水準三・BOOK-0204既出): 直列部分と並列部分が組み合わさった回路。
- **次元解析**(水準六・WAZA-0001既出): 単位の帳尻合わせだけで式の形を求める技法。
- **O記法**(本冊で導入する語・水準二十六): 計算量の支配的な項だけを見て、係数や低次の項を無視して増加率を表す記法。
- **対数**(水準七・WAZA-0001既出): 掛け算を足し算に変換する性質を持つ数学的操作。
- **Karatsuba法**(本冊で導入する語・水準二十五): 桁の多い整数の掛け算を、分割の工夫によって乗算回数そのものを減らす高速化手法(対数型の変換とは異なる分割統治系の手法として区別する)。
---
## quiz_public(検定問題・12問・易4/中4/難4)
### quiz_public
1. (易) 分割統治法の一般的な手順として正しい順序はどれか。 A.合成→分割→独立に解く B.独立に解く→合成→分割 C.合成のみで完結する D.分割→独立に解く→合成
2. (易) 100を素因数分解するときの試行回数を打ち切りありで数えると何回か。 A.3回 B.5回 C.7回 D.10回
3. (易) 混合回路の畳み込み(R2=10Ω・R3=15Ωの並列、R1=10Ωと直列)の演算ステップ数は何ステップか。 A.3ステップ B.4ステップ C.5ステップ D.6ステップ
4. (易) 次元解析とO記法に共通する姿勢として正しいものはどれか。 A.係数まで厳密に確定する B.両方とも計算量の話である C.両方とも物理量の話である D.詳細を捨てて骨格(形)だけを確定する
5. (中) 4桁×4桁の掛け算に交差法を機械的に2段階適用した場合の1桁乗算の回数の実測結果はどれか。 A.8回(削減効果あり) B.12回(削減効果あり) C.16回(素朴な筆算と同じ) D.20回(悪化)
6. (中) √n打ち切り探索で、100を素因数分解する場合の効率化倍率(打ち切りなしの最大100回相当との比較)はどれか。 A.2倍 B.5倍 C.10倍 D.50倍
7. (中) 混合回路の畳み込みが使えない場合として正しいものはどれか。 A.単純な直列回路 B.単純な並列回路 C.ブリッジ回路のようなループ構造 D.抵抗が2個だけの回路
8. (中) 対数とFFTに共通する3段構成として正しいものはどれか。 A.分割→独立解→合成 B.変換→軽い演算→逆変換 C.打ち切り→確定→終了 D.畳み込み→展開→検算
9. (難) 本冊が「Karatsuba法は対数の仲間ではない」と明記した理由はどれか。 A.Karatsuba法は分割の工夫で乗算回数を減らす別系統の手法だから B.Karatsuba法は現実に存在しないから C.Karatsuba法は対数より計算が遅いから D.Karatsuba法は掛け算に使えないから
10. (難) 技6(交差法=最小分割統治)の限界として本冊が明記した内容はどれか。 A.交差法は3桁以上では使えない B.交差法は分割統治法とは無関係である C.交差法は回路には応用できない D.交差法を機械的に繰り返すだけでは計算量削減にならず、部分積の共有などの工夫が別途必要
11. (難) 次元解析とO記法が「捨てている情報」としてそれぞれ正しい組み合わせはどれか。 A.次元解析は単位、O記法は増加率 B.次元解析は形、O記法は係数のみ C.両方とも何も捨てていない D.次元解析は比例定数、O記法は係数・低次の項
12. (難) 技8(内側畳み込み合成)が分割統治法の再帰と構造的に一致する理由はどれか。 A.回路図には数式が登場しないから B.回路には並列がないから C.分割統治法は回路の話でしか使えないから D.葉から根へ演算を積み上げる処理順序が、再帰呼び出しが基底ケースから戻りながら結果を合成する順序と一致するから
### answers
| 問番号 | 正解 | 根拠 |
|---|---|---|
| 1 | D | 「段階1: …分割する…段階2: …独立に計算する…段階3: …合成する」 |
| 2 | B | 「試行回数は合計5回」 |
| 3 | C | 「合計5ステップで、葉(R2, R3)から根(R合)まで畳み込みが完了する」 |
| 4 | D | 「両者がどちらも「係数を確定させないまま、答えの"形"だけを確定させる」という同じ操作」 |
| 5 | C | 「素朴な筆算…16回…この実測比較では…16回のまま変わらなかった」 |
| 6 | C | 「効率化倍率は 100÷10 = 10倍」 |
| 7 | C | 「ブリッジ回路…のような**ループを含む構造**には、この「内側から畳み込む」手順がそのまま使えず」 |
| 8 | B | 「変換 → 軽い演算 → 逆変換」という**3段構成**が共通している」 |
| 9 | A | 「Karatsuba法は…「数の分割の仕方を工夫して、必要な乗算の回数そのものを減らす」という別のアプローチを取る」 |
| 10 | D | 「交差法の分割の仕方をそのまま桁数の多い場合に機械的に繰り返しても…部分積の一部を「共有」して再利用する工夫…が必要」 |
| 11 | D | 「次元解析なら比例定数、O記法なら係数や低次項」 |
| 12 | D | 「「葉から根へ、内側から外側へ演算を積み上げていく」処理順序は…再帰呼び出しが最も深いところ…から戻りながら結果を合成していく処理順序と、構造として完全に一致する」 |
---
## 出典・系譜(§16.5準拠)
本冊で扱った横断原理(分割統治法・次元解析とO記法の同型性・対数とFFTの構造対応)は、いずれも確立された数学・情報科学の標準的な考え方(分配法則の展開・算術の基本定理・単位の次元解析・計算量のオーダー記法・対数の性質)から自分の言葉で再構成したものであり、特定の書籍・サイトの文章を転載していない。分割統治法・O記法・FFT・Karatsuba法は情報科学において広く確立された標準的な概念であり特定の原著作権を持たない。数値例・ステップ数はすべて本文中で実際に計算・カウントし自己検算済みである。誇張を避けるため、成立しなかった候補(平方完成とDP/メモ化の対応)はTATSUJIN_DISCOVERY.mdに不成立として明記し、本冊には収録していない。
---
## 改訂履歴
- 2026-07-04 v1.0 初版執筆(Sonnet 5・達人術発見リード班・BOOK-0212予約枠)。技6〜10(交差法=分割統治・√n打ち切り・内側畳み込み・次元解析とO記法・対数とFFT)・quiz12問(易4中4難4)を収録。発見の全過程はTATSUJIN_DISCOVERY.mdを参照。
# BOOK-0212 達人術その2 — 横断アルゴリズム(総当たり発見)