Codage de Fibonacci
Transformez tout entier positif en code de Fibonacci : 6 devient 10011, avec les termes 1 et 5. Chaque code finit par 11, donc une suite de codes se découpe sans indiquer de longueur, utile en compression et pour concevoir des protocoles. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- N
- 6
- Code de Fibonacci
- 10011
- Longueur en bits
- 5
- Termes de Zeckendorf
- 1, 5
Le codage de Fibonacci est un code binaire universel qui associe à chaque entier positif une chaîne de bits unique se terminant toujours par deux uns consécutifs. La construction s'appuie sur le théorème de Zeckendorf : tout entier positif est la somme de nombres de Fibonacci non consécutifs de la suite qui commence par un, deux, trois, cinq, huit, et ainsi de suite. Placez un un pour chaque terme de la somme, un zéro pour chaque terme de base omis à partir de F deux, puis ajoutez un bit terminateur final pour que le code se termine par onze. Les étudiants en théorie de l'information, les devoirs de compression et les concepteurs de protocoles qui ont besoin d'un encodage d'entiers auto-délimité utilisent ce convertisseur pour vérifier des exemples sans reconstruire à la main la table de Fibonacci.
Ce qu'est le codage de Fibonacci et pourquoi il finit par 11
Le codage de Fibonacci appartient à la famille des codes universels pour les entiers positifs : chaque n supérieur ou égal à un reçoit un mot binaire, et aucun mot de code n'est préfixe d'un autre, de sorte qu'un flux de codes peut être analysé sans préfixes de longueur. Le fait mathématique central est le théorème de Zeckendorf.
En utilisant la suite de Fibonacci écrite comme F deux égale un, F trois égale deux, F quatre égale trois, F cinq égale cinq, et ainsi de suite (la suite habituelle sans la première duplication du un), tout entier positif a une représentation unique comme somme de termes non consécutifs de cette suite. L'encodage place un bit sous chaque valeur de base de F deux jusqu'au plus grand terme de la somme qui apparaît : le bit vaut un lorsque ce nombre de Fibonacci est utilisé et zéro sinon.
Comme Zeckendorf interdit deux uns consécutifs dans les bits de base, le bit le plus haut utilisé vaut toujours un et n'est jamais suivi d'un autre un dans la base. L'ajout d'un unique un terminateur produit donc une fin distinctive de deux uns consécutifs. Ce motif est le signal d'arrêt du décodeur : lisez les bits jusqu'à voir onze, retirez le un final et récupérez la somme de Zeckendorf.
Les petites valeurs classiques rendent le motif concret. Un s'encode en onze, deux en zéro un un, trois en zéro zéro un un, quatre en un zéro un un, cinq en zéro zéro zéro un un et six en un zéro zéro un un. Un n plus grand prolonge simplement la table de Fibonacci jusqu'au plus grand Fk au plus égal à n, exécute la sélection gloutonne depuis le haut et émet la même chaîne terminée.
La longueur du code croît comme O du logarithme en base phi de n, de sorte que même de grands entiers sûrs restent de courtes chaînes de bits adaptées aux démonstrations, vecteurs de test et diapositives sur les codes d'entiers sans préfixe.
Contrat d'entrée, champs de réponse et erreurs
Exemple : n égal à un donne le code minimal onze avec un seul terme de Zeckendorf égal à un. Exemple : n égal à douze donne un zéro un zéro un un avec les termes un, trois et huit. Les clients qui n'ont besoin que de la chaîne de bits peuvent ignorer les champs pédagogiques ; correcteurs et carnets peuvent vérifier le code et les termes pour détecter les décalages dans la table manuelle de l'étudiant.
L'implémentation est pure parse de niveau A : pas de réseau sortant, pas d'aléa, pas de dépendance à l'horloge, de sorte que le même n produit toujours la même charge utile et peut être figé dans des tests d'or automatisés.
À quoi sert le codage de Fibonacci
Les cours de théorie de l'information et de compression utilisent le codage de Fibonacci comme code universel concret à côté d'Elias gamma et delta ; un convertisseur en direct permet aux étudiants de vérifier des encodages de devoir pour des entiers positifs arbitraires sans reconstruire un tableur de Fibonacci à chaque fois.
La programmation compétitive et les blogs d'algorithmes qui traitent des représentations de Zeckendorf, des systèmes de numération de Fibonacci ou des flux auto-délimités ont besoin d'un oracle déterministe qui renvoie la chaîne de bits et les termes pour des tests unitaires. Les concepteurs de protocoles qui évaluent des encodages d'entiers à longueur variable peuvent comparer les longueurs du code de Fibonacci à des schémas de largeur fixe et de type LEB128 sur des séquences d'ID d'échantillon avant de fixer un format filaire. Une validation échouée ne consomme pas le solde.
Cas d’usage
Vérification de devoirs en théorie de l'information
Les étudiants encodent à la main des entiers positifs avec des tables de Zeckendorf et vérifient le code binaire de Fibonacci (toujours terminé par 11) face à un oracle déterministe.
Démos de compression et codes universels
Les supports de cours comparent la longueur du codage de Fibonacci aux codes d'Elias sur des entiers d'échantillon et montrent le motif terminateur qui rend le flux sans préfixe.
Questions fréquentes
Comment convertir un nombre en code de Fibonacci ?
Envoyez un entier positif n (n ≥ 1).
Pourquoi tout code de Fibonacci se termine-t-il par 11 ?
Les bits de Zeckendorf ne se terminent jamais par deux uns consécutifs ; un terminateur 1 est ajouté après le bit de base le plus haut (toujours 1), produisant le motif d'arrêt 11 distinctif pour un décodage unique.
Que se passe-t-il si n est zéro ou négatif ?
Le codage de Fibonacci n'est défini que pour les entiers positifs (n ≥ 1), et les requêtes invalides ne sont pas facturées.
Quelle suite de Fibonacci l'encodeur utilise-t-il ?
La sélection gloutonne produit l'expansion de Zeckendorf unique sans termes consécutifs.
Quel est le code de Fibonacci de 12 ?
12 se code 101011. Ses termes de Zeckendorf sont 1, 3 et 8, dont la somme fait 12, et le 1 final ajouté forme le 11 de clôture qui signale la fin du code.
Outils associés
Pour les développeurs — accès API
Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.
Endpoint
Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.
Appeler depuis votre stack
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)Exemple de requête
{
"n": 6
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.fibonacci_coding",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.
Tarifs
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
Erreurs
| HTTP | Code | Signification |
|---|---|---|
401 | unauthorized | Clé API absente ou invalide : vérifiez l’en-tête Authorization. |
402 | insufficient_balance | Solde insuffisant : rechargez votre compte pour lancer cette tâche. |
404 | unknown_type | Type de tâche inconnu : vérifiez le champ type de votre requête. |
429 | rate_limited | Trop de requêtes : ralentissez la cadence, puis réessayez. |
Notes techniques
Le même algorithme pur alimente l'outil gratuit du navigateur et le chemin d'API payant, de sorte qu'un exemple d'or de cours coïncide octet par octet avec l'automatisation de production, sans modèle et sans réseau à l'intérieur du solveur.
Contrat d'entrée, champs de réponse et erreurs
Envoyez en POST un corps JSON avec un seul champ obligatoire n : un entier positif supérieur ou égal à un. La valeur peut arriver comme nombre JSON dans la plage des entiers sûrs ou comme chaîne de chiffres qui se normalise à la même plage. n manquant, chaînes vides, non-entiers, valeurs non finies, zéro et tout nombre négatif échouent avec invalid_input et ne sont pas facturés. En cas de succès, la réponse renvoie n, fibonacci_code comme la chaîne binaire qui se termine toujours par onze, bit_length comme la longueur en caractères de cette chaîne, zeckendorf_terms comme les termes de Fibonacci croissants qui reconstituent n, et une courte chaîne de formule qui reformule la construction à afficher à côté de la réponse. Exemple : n égal à six donne fibonacci_code un zéro zéro un un, bit_length cinq et zeckendorf_terms un et cinq, car cinq plus un égale six et les bits de base de F deux à F cinq sont un, zéro, zéro, un avant le terminateur.
Où une API de codage de Fibonacci trouve son utilité
Comme chaque appel réussi est un élément facturable à $0.002 avec un coût analytique bien en dessous de ce plancher, la capacité reste bon marché pour des scripts de correction par lots et des workers en périphérie.
Cas d'intégration
Vecteurs de test pour outils Zeckendorf
Les scripts qui implémentent une numération de Fibonacci ou des ID auto-délimités peuvent figer fibonacci_code et zeckendorf_terms pour de nombreux n sans embarquer une seconde implémentation.
Questions techniques
Combien coûte le convertisseur de codage de Fibonacci ?
L'outil navigateur est gratuit. Les requêtes API utilisent le solde KIT prépayé à $0.002 par appel réussi ; une entrée invalide n'est pas facturée.