ForHosting KIT · 数学

フィボナッチ符号化

正の整数をフィボナッチ符号に変換します。6は項1と5の和なので10011になります。どの符号も11で終わるため、連続した符号を長さの情報なしで区切れます。圧縮の課題や通信方式の設計に役立ちます。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

N: 6

結果

フィボナッチ符号: 10011
ビット長: 5
ゼッケンドルフ表現の項: 1, 5

フィボナッチ符号化は、すべての正の整数を、常に連続する二つの 1 で終わる一意のビット列へ写す万能二進符号です。構成はツェッケンドルフの定理に依拠します。すなわち、すべての正の整数は、1、2、3、5、8… と続くフィボナッチ数列のうち、隣り合わない項の和として表せます。各和の項には 1、F 二以降で使わない基底項には 0 を置き、最後に終端ビットを付けて符号が 11 で終わるようにします。情報理論の学習者、圧縮の課題、自己区切り整数符号化を必要とするプロトコル設計者が、手作業でフィボナッチ表を組み立てずに例を確認するために本コンバータを使います。

フィボナッチ符号化とは何か、なぜ末尾が 11 か

フィボナッチ符号化は正の整数向け万能符号の一族です。1 以上の各 n に二進語が割り当てられ、どの符号語も他の接頭辞にならないため、長さ接頭辞なしで符号の列を解析できます。中心となる数学的事実はツェッケンドルフの定理です。

F 二を 1、F 三を 2、F 四を 3、F 五を 5… と書いたフィボナッチ数列（通常列から最初の 1 の重複を除いたもの）を用いると、すべての正の整数は隣接しない項の和として一意に表せます。符号化は、F 二から現れる最大の和の項までの各基底値の下にビットを置きます。そのフィボナッチ数が使われるとき 1、そうでなければ 0 です。

ツェッケンドルフは基底ビットに連続する二つの 1 を許さないため、使われる最高位ビットは常に 1 で、基底内でその後に別の 1 は続きません。終端の 1 を一つ付けると、連続する二つの 1 という特徴的な末尾になります。このパターンが復号器の停止信号です。

11 が見えるまでビットを読み、最後の 1 を除き、ツェッケンドルフ和を復元します。古典的な小さい値でパターンが具体化します。1 は 11、2 は 011、3 は 0011、4 は 1011、5 は 00011、6 は 10011 と符号化されます。

より大きな n では、最大の Fk が n 以下になるまでフィボナッチ表を延ばし、上から貪欲選択を行い、同じ終端付き文字列を出します。符号長は n の底 phi の対数のオーダーで伸びるため、大きな安全整数でも短いビット列に収まり、デモ、テストベクトル、接頭辞なし整数符号の教材スライドに適します。

フィボナッチ符号化が役立つ場面

情報理論と圧縮の講義では、Elias のガンマ・デルタと並ぶ具体的な万能符号としてフィボナッチ符号化を使います。ライブのコンバータがあれば、毎回フィボナッチ表を作らずに任意の正の整数の宿題符号化を確認できます。

ツェッケンドルフ表現、フィボナッチ記数法、自己区切りストリームを扱う競技プログラミングやアルゴリズム解説には、ビット列と和の項の両方を返す決定論的オラクルがユニットテストに必要です。可変長整数符号化を検討するプロトコル設計者は、サンプル ID 列で固定幅や LEB128 系と符号長を比較してからワイヤ形式を決められます。検証失敗は残高を消費しません。

活用例

情報理論の宿題チェック

学習者がツェッケンドルフ表で正の整数を手符号化し、末尾が常に 11 の二進フィボナッチ符号を決定論的オラクルと照合します。

圧縮と万能符号のデモ

教材がサンプル整数でフィボナッチ符号長と Elias 符号を比較し、ストリームを接頭辞なしにする終端パターンを示します。

よくある質問

なぜすべてのフィボナッチ符号は 11 で終わるのですか？

ツェッケンドルフのビットは連続する二つの 1 で終わらず、最高位基底ビット（常に 1）の後に終端 1 を付けるため、一意復号用の特徴的な停止パターン 11 になります。

n が 0 または負のときは？

フィボナッチ符号化は正の整数（n ≥ 1）にのみ定義され、無効な要求は課金されません。

符号化器はどのフィボナッチ数列を使いますか？

貪欲選択により隣接項のない一意のツェッケンドルフ展開が得られます。

12のフィボナッチ符号は何ですか？

12は101011になります。ゼッケンドルフの項は1、3、8で合計12となり、最後に付け足す1が符号の終わりを示す11を作ります。

数をフィボナッチ符号に変換するにはどうしますか？

その数を超えない最大のフィボナッチ数から順に、隣り合わない項を選んで和を作ります。小さい項から順に、使う項は1、使わない項は0を並べ、最後に1を付けると11で終わる符号になります。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/numth/fibonacci-coding

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/numth/fibonacci-coding \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":6}'

const res = await fetch("https://api.kit.forhosting.com/numth/fibonacci-coding", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": 6
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/fibonacci-coding",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": 6
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/fibonacci-coding", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"n":6}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"n":6}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/fibonacci-coding", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "n": 6
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.fibonacci_coding",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

入力契約、応答フィールド、エラー挙動

n は 1 以上の正の整数です。5 と 1 の和が 6 で、F 二から F 五までの基底ビットは終端前に 1,0,0,1 だからです。例：n が 1 のとき最小符号 11 と単一のツェッケンドルフ項 1 になります。例：n が 12 のとき 101011 と和の項 1,3,8 になります。採点器やノートブックは符号と和の項の両方を検証し、手計算表のオフバイワンを検出できます。実装は純粋な parse の tier A です。必須フィールド n だけを含む JSON 本体を POST してください。値は安全整数範囲内の JSON 数値でも、同じ範囲に正規化される数字列でも構いません。n の欠落、空文字、非整数、非有限値、0、負数は invalid_input で失敗し、課金されません。成功時は n をエコーし、常に 11 で終わる二進文字列として fibonacci_code を返し、その文字長を bit_length として報告し、n に戻る昇順のフィボナッチ和の項を zeckendorf_terms に列挙し、答えの横に表示する短い公式文字列も含めます。例：n が 6 のとき fibonacci_code は 10011、bit_length は 5、zeckendorf_terms は 1 と 5 です。ビット列だけが必要なクライアントは教育用フィールドを無視できます。

フィボナッチ符号化 API が役立つ場面

成功した呼び出しは $0.002 の 1 件課金で、分析コストはその床より十分低いため、一括採点スクリプトやエッジワーカーにも安価です。公開された安全整数上限内に n を保ち、期待する fibonacci_code 文字列をテストに固定すれば、計算機代数スタックを立てず、各クライアント言語に脆い場当たりループを埋め込まずに、教育・ドキュメント用フィクスチャ・軽量プロトコル試作向けの再現可能な符号化が得られます。

連携の活用例

ツェッケンドルフ系ツールのテストベクトル

フィボナッチ記数や自己区切り ID を実装するスクリプトが、第二実装を埋め込まずに多くの n で fibonacci_code と zeckendorf_terms を固定できます。

技術的な質問

数をフィボナッチ符号に変換するには？

正の整数 n（n ≥ 1）を送ってください。API は末尾が 11 の二進文字列 fibonacci_code に加え、bit_length と n を復元するツェッケンドルフ和の項を返します。

フィボナッチ符号化コンバータの料金は？

ブラウザツールは無料です。API 要求は成功した呼び出しごとに $0.002 で前払い KIT 残高を使い、無効入力は課金されません。

KITの完全なドキュメントを見る →