再帰木のノード数計算機
分割統治法の再帰木のノードを、レベルごとに数えます。16から半分の大きさの部分問題を2つずつ作ると、5つのレベルに1、2、4、8、16個のノードが並び、合計31個のうち16個が葉です。木を描かずに課題を確かめられます。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- 分岐係数
- 2
- 縮小率
- 2
- 入力サイズ
- 16
- レベル数
- 5
- 木の高さ
- 4
- ノードの合計
- 31
- 葉ノード
- 16
分割統治の再帰式 T(n) = a T(n/b) + 非再帰作業は、マージソートや二分空間分割、多方向再帰を木として描くアルゴリズム授業で必ず登場します。学習者は各レベルに何ノードあるか、基底ケースに達するまで木がどこまで深くなるかを信頼できる形で数えたいと考えます。この再帰木ノード数計算機は分岐因子 a、縮小比 b、根の入力サイズ n を受け取り、部分問題サイズが 1 以下になるまで木を辿り、レベル数・木の高さ・総ノードと葉の数・レベル別ノード列・部分問題サイズ・2 種類の作業配分比率を返します。一方はノード単位の単位コスト、もう一方は部分問題サイズに比例する作業を仮定し、各完全レベルが n に対して線形の仕事を行うマージソート型の図と一致します。
再帰木が数えるものとレベルの定義
再帰木は、実行時間が T(n) = a T(n/b) + f(n) を満たす分割統治アルゴリズムが生むすべての部分問題の図です。根はサイズ n の元のインスタンスを表します。各内部ノードはちょうど a 個の子を持ち、各子は親のサイズを b で割ったサイズの問題を解きます。
レベルは根を 0 として番号付けします。レベル i には a の i 乗個のノードがあり、各ノードの部分問題サイズは n を b の i 乗で割った値です(サイズが実数かつ正である限り)。走査は現在のサイズが 1 より厳密に大きい間続き、サイズが 1 以下となる最初のレベルを基底ケースの葉レベルとして残して停止します。
この慣習は定数サイズ入力を直接解く教科書の停止条件と一致します。木の高さはレベル数から 1 を引いた値、すなわち根から葉へのパス上の辺の数です。葉ノードはサイズがちょうど冪の境界で 1 に達するとき高さの a 乗に等しく、一般には最後に記録したレベルのノード数に等しくなります。
内部ノードは総ノードから葉を引いたものです。分岐因子が 1 のとき木はサイズが 1 以下になるまでの連続分割回数に等しい長さの一本の背骨になります。
再帰木のノードを数えると役立つ場面
アルゴリズムの授業やチュータリング基盤は、任意の a・b・n について深さと幅を手描きせずに確認できる再帰木ノード数計算機を使います。試験ジェネレータは、あいまいな漸近的推測ではなく、主張された葉数やレベル数を誤答と判定する決定的オラクルを必要とします。
面接対策ツールや計算量ビジュアライザはレベル別配列をチャートと組み合わせ、a が b に等しいとき均衡分割統治が各レベルで同じ作業を使う理由を候補者に示します。多方向スプリッタや並列タスクグラフを試作するエンジニアリングノートは、本番スケジューラを書く前にファンアウトを検証できます。検証失敗は残高を消費しません。
活用例
アルゴリズムの宿題とチュータリング
学生に T(n)=a T(n/b)+f(n) の a・b・n を提出させ、レベル数・葉ノード・幾何的ノード列を教科書の図と照合させます。
試験と LMS の自動採点
漸近的な手計算を厳密解として受け入れる代わりに、総ノードと高さの決定的オラクルで再帰木問題を採点します。
よくある質問
マージソートの再帰木にはノードがいくつありますか?
大きさ16の入力を毎回2つに半分ずつ分けると、5つのレベルに1、2、4、8、16個のノードがあります。合計31個で、そのうち葉が16個、内部ノードが15個です。
再帰木はどこで成長を止めますか?
部分問題の大きさが初めて1以下になったレベルで止まります。そのレベルが基本となる場合の集まりです。高さはレベル数から1を引いた値なので、5レベルなら高さは4です。
2つの作業量の配分は何を表していますか?
一方は各ノードの手間を同じとみなすので、作業の多くが葉に集まります。もう一方は手間が問題の大きさに比例するとみなし、マージソートのように5つの各レベルが全体の5分の1ずつを受け持ちます。
各呼び出しが部分問題を1つしか作らない場合は?
木は1本の鎖になり、その長さは大きさを1まで下げるのに必要な割り算の回数と同じです。縮小の比率は必ず1より大きくする必要があり、そうでないと部分問題が小さくなりません。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/dev/recursion-tree-nodes \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"branching_factor":2,"shrink_ratio":2,"input_size":16}'const res = await fetch("https://api.kit.forhosting.com/dev/recursion-tree-nodes", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/recursion-tree-nodes",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/recursion-tree-nodes", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"branching_factor":2,"shrink_ratio":2,"input_size":16}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"branching_factor":2,"shrink_ratio":2,"input_size":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/recursion-tree-nodes", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"branching_factor": 2,
"shrink_ratio": 2,
"input_size": 16
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.recursion_tree_nodes",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
再帰木が数えるものとレベルの定義
分岐因子が 1 より大きいとき L レベルにわたる総ノードの閉形式は a の L 乗マイナス 1 を a マイナス 1 で割ったものであり、本エンドポイントは幾何級数を加算して再計算し、分数サイズや早期の基底ケースも走査と整合させます。
入力契約・応答フィールド・作業配分の見方
数値文字列も受け付けます。recurrence 文字列は a と b で T(n) を再掲し、formula はレベル規則と総ノードの閉形式を要約します。安全なレベルまたはノード上限を超える病理的な組合せは明確なメッセージで拒否し、クライアントが爆発する木で停止しないようにします。例:分岐因子 2、縮小比 2、入力サイズ 16 は、ノード数が 1・2・4・8・16 の 5 レベル、総 31 ノード、葉 16 を与え、2 の冪長配列上のマージソートの古典的な完全二分再帰木になります。必須の有限数 3 つを含む JSON 本体を POST してください。branching_factor は 1 以上の整数、shrink_ratio は部分問題が縮むよう 1 より厳密に大きい有限数、input_size は根用に 1 以上の有限数です。欠落フィールド、非有限値、非整数または 1 未満の分岐因子、1 以下の縮小比、1 未満の根サイズは invalid_input で失敗し課金されません。成功時は 3 入力をエコーし、level_count、tree_height、total_nodes、leaf_nodes、internal_nodes を報告します。nodes_per_level 配列は根から下への各レベルのノード数です。subproblem_size_per_level 配列はそのレベル全ノードが共有するサイズで、ランタイム横断の安定比較のため小数 12 桁に丸めます。合計 1 になる 2 本の比率配列があり、node_fraction_per_level は各レベルノード数を総数で割り再帰呼び出しごとの単位作業をモデル化し、size_work_fraction_per_level はノード数×部分問題サイズで各レベルを重み付けし、そのノードでのサイズ比例の非再帰作業をモデル化します。
再帰木ノード API が役立つ場面
実装は pure parse の tier A のため、成功した各呼び出しはモデルトークンも外向きネットワークもなく公開の基本料金 $0.002 です。
連携の活用例
計算量ビジュアライザと面接対策
nodes_per_level と size_work_fraction_per_level をチャートに渡し、マージソート型の木で作業がレベル間にどう広がるかを候補者に見せます。
技術的な質問
分割統治の再帰木でノードをどう数えますか?
整数の branching_factor a ≥ 1、shrink_ratio b > 1、input_size n ≥ 1 を送ってください。API は size ≤ 1 まで a^i ノード・サイズ n/b^i のレベルを辿り、合計とレベル別配列を返します。
level_count と tree_height の違いは何ですか?
level_count は根を含むレベル数(少なくとも 1)です。tree_height は level_count から 1 を引いた値で、根から葉へのパス上の辺の数です。
作業配分はどう計算されますか?
node_fraction_per_level は各レベルのノード数を total_nodes で割った値です。size_work_fraction_per_level はノード数×部分問題サイズで重み付けし、呼び出しあたり Θ(size) の非再帰作業に対応します。
計算機はいつ入力を拒否しますか?
欠落または非有限のフィールド、非整数または 1 未満の branching_factor、shrink_ratio ≤ 1、input_size < 1、安全なレベル/ノード上限を超える木は invalid_input で失敗し課金されません。
再帰木ノード数計算機の料金は?
ブラウザツールは無料です。API 要求は成功した呼び出しごとに前払い KIT 残高から $0.002 です。無効な入力は課金されません。