Termine Calkin–Wilf
Il termine 5 della successione di Calkin-Wilf è 3/2, raggiunto dalla radice 1/1 con un passo a sinistra e uno a destra. Inserisca una posizione da 1 a un miliardo e ottenga la frazione ridotta e il suo percorso. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- N
- 5
- Numeratore
- 3
- Denominatore
- 2
- Frazione
- 3/2
- Percorso
- LR
L'albero di Calkin–Wilf è un albero binario completo i cui nodi sono esattamente i numeri razionali positivi, ciascuno una sola volta e in forma ridotta. Percorrere l'albero livello per livello (o indicizzare i nodi nell'ordine naturale di heap binario che coincide con il percorso binario di un intero positivo n) produce una celebre enumerazione di Q+: la successione di Calkin–Wilf. L'indice uno è la frazione radice uno su uno; ogni indice successivo segue un unico percorso sinistra-destra codificato dalle cifre binarie di n dopo il bit uno iniziale. Studenti di combinatoria enumerativa, matematica discreta e ricostruzione razionale necessitano di un oracolo rapido che restituisca numeratore e denominatore per un indice sicuro arbitrario senza costruire l'intero albero. Questa capacità accetta un intero positivo n, percorre quel cammino con poche somme intere e restituisce la frazione ridotta a/b insieme a una stringa di percorso e a una breve formula.
Cos'è l'enumerazione di Calkin–Wilf e come si definisce la n-esima frazione
Neil Calkin e Herbert Wilf hanno reso popolare un albero binario notevolmente semplice di razionali positivi: la radice è uno su uno; il figlio sinistro di una frazione a su b è a su (a più b); il figlio destro è (a più b) su b. Ogni razionale positivo compare esattamente una volta, già in termini minimi, così l'albero è al tempo stesso un'enumerazione di Q+ e una forma canonica ridotta di ogni valore.
L'indice naturale n a base uno etichetta i nodi per posizione nell'ordine di heap binario completo: n uguale a uno è la radice, n uguale a due è il figlio sinistro della radice (un mezzo), n uguale a tre è il figlio destro (due su uno), n uguale a quattro è il nipote sinistra-sinistra (un terzo), e così via.
In modo equivalente, scriva n in binario, scarti il bit uno iniziale che segna sempre la radice e interpreti ogni bit rimanente dal più significativo al meno come uno spostamento: zero significa sinistra, uno significa destra. Dopo tali spostamenti ottiene l'unica frazione ridotta a/b in quel nodo. Un'identità classica collega questo percorso alla successione diatomica di Stern s: la frazione di Calkin–Wilf all'indice n è s(n) su s(n più uno).
Poiché ogni passo somma solo due interi positivi, l'algoritmo è deterministico, leggero in allocazione e privo di arrotondamento in virgola mobile: ideale per oracoli di compiti, plugin LMS e notebook di ricerca che necessitano di numeratori e denominatori esatti anziché decimali approssimati.
Contratto di ingresso, campi di risposta e comportamento in errore
I valori inferiori a uno — incluso zero e ogni indice negativo — falliscono con un messaggio chiaro che l'indice di Calkin–Wilf deve essere almeno uno; tali fallimenti di validazione non vengono fatturati.
In caso di successo il corpo restituisce n, fornisce numerator e denominator come interi positivi, fraction come stringa numeratore barra denominatore, formula come breve riaffermazione delle regole di radice e figli più la regola del percorso binario, e path come le lettere L e R dei movimenti dopo la radice (o la parola root quando n vale uno). Esempio: n uguale a uno produce frazione uno barra uno e path root.
Esempio: n uguale a cinque ha binario uno zero uno, bit di percorso zero poi uno, quindi sinistra poi destra da uno su uno dà tre su due, path LR. Esempio: n uguale a sette ha path RR e frazione tre su uno. I client che necessitano solo del razionale possono leggere fraction o la coppia di interi; i tutor possono mostrare path accanto alla risposta affinché gli studenti verifichino ogni passo.
Dove torna utile il termine di Calkin–Wilf
I notebook di ricerca che esplorano rappresentazioni iperbinarie, demo della funzione punto interrogativo di Minkowski o strategie di campionamento razionale spesso necessitano di un oracolo esatto e rapido della n-esima frazione di Calkin–Wilf mantenendo il risultato ridotto per costruzione. Gli strumenti di ingegneria e istruzione che generano razionali di test positivi unici per test basati su proprietà possono ottenere termini successivi per indice invece di inventare coppie casuali non ridotte che poi richiedono pulizia con gcd.
Mantenga le richieste piccole, documenti che n è un intero positivo che inizia da uno e tratti numerator, denominator e fraction come campi di risposta canonici per i controlli automatici.
Casi d'uso
Controlli in aula e compiti
Consenta agli studenti di inviare un indice positivo n e di verificare la frazione di Calkin–Wilf a/b rispetto alle regole di figlio sinistro e destro, con la stringa di percorso mostrata per credito parziale.
Valutazione automatica LMS ed esami
Valuti gli item di enumerazione di Calkin–Wilf con un oracolo deterministico che rifiuta n inferiore a uno e non inventa mai razionali non ridotti o duplicati.
Razionali di test positivi unici
Generi un flusso di razionali positivi ridotti e distinti per indice per test basati su proprietà senza chiamare gcd su coppie casuali.
Domande frequenti
Come si ottiene la n-esima frazione di Calkin–Wilf?
Invii un intero positivo n (n ≥ 1).
Cosa succede se n è zero o negativo?
L'indice di Calkin–Wilf usato qui è un intero positivo che inizia da uno; i valori inferiori a uno sono rifiutati e non fatturati.
La frazione restituita è sempre ridotta?
Sì. Ogni nodo dell'albero di Calkin–Wilf è già in termini minimi, quindi numerator e denominator sono coprimi per ogni n valido.
In che modo differisce dalla successione di Stern–Brocot?
La successione diatomica di Stern restituisce un solo intero s(n). Il termine di Calkin–Wilf è il razionale s(n)/s(n+1) (equivalente al percorso sull'albero sopra). Intento di ricerca e forma di uscita differiscono: frazione versus valore diatomico.
Che cosa significa il percorso con le lettere L e R?
Scriva n in binario e tolga l'1 iniziale: ogni 0 rimasto è un passo a sinistra e ogni 1 un passo a destra dalla radice. Per la posizione 5, il binario 101 lascia le cifre 0 e 1, quindi il percorso è LR e arriva a 3/2.
Strumenti correlati
Per sviluppatori — accesso via API
Tutto quello che vedi in questa pagina è disponibile anche via API. Questa sezione è per i team che vogliono integrarlo nei propri sistemi; chi non ne ha bisogno può semplicemente usare lo strumento qui sopra.
Endpoint
Autenticazione con Bearer token: un POST mette in coda l'attività e il risultato arriva via webhook o link firmato.
Chiamala dal tuo stack
curl -X POST https://api.kit.forhosting.com/numth/calkin-wilf-term \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":5}'const res = await fetch("https://api.kit.forhosting.com/numth/calkin-wilf-term", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 5
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/calkin-wilf-term",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 5
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/calkin-wilf-term", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":5}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":5}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/calkin-wilf-term", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Esempio di richiesta
{
"n": 5
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.calkin_wilf_term",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L'API è asincrona: ricevi subito un task_id e puoi fare polling fino a 1 richiesta al secondo.
Prezzi
Prezzo pubblicato, senza token né crediti. Se l'attività fallisce, non paghi.
Errori
| HTTP | Codice | Significato |
|---|---|---|
401 | unauthorized | Chiave API mancante o non valida: controlla l'header Authorization. |
402 | insufficient_balance | Credito esaurito: ricarica per continuare a eseguire attività. |
404 | unknown_type | Tipo di attività sconosciuto: controlla il campo type della richiesta. |
429 | rate_limited | Troppe richieste in poco tempo: rallenta e riprova tra qualche secondo. |
Note tecniche
Gli indici inferiori a uno sono rifiutati con invalid_input affinché correttori e script non trattino mai zero né posizioni negative come termini validi.
Cos'è l'enumerazione di Calkin–Wilf e come si definisce la n-esima frazione
Questo endpoint implementa il percorso diretto sull'albero anziché una tabella Stern separata, ma le risposte coincidono con tale identità per ogni n positivo.
Contratto di ingresso, campi di risposta e comportamento in errore
Invii un corpo JSON con un unico campo obbligatorio n: un intero positivo maggiore o uguale a uno, come numero JSON o come stringa di cifre decimali, al massimo un miliardo. Gli alias index e order sono accettati con lo stesso significato. n mancante, stringhe vuote, non interi, numeri non finiti e valori oltre il massimo falliscono con invalid_input indicando il problema. L'implementazione è parse pura di livello A: nessuna rete, nessun token di modello, nessun filesystem, e lo stesso modulo può eseguire nel percorso gratuito del browser e sul Worker di edge senza divergenze.
Dove un'API del termine di Calkin–Wilf conviene
I corsi di combinatoria enumerativa e matematica discreta usano l'albero di Calkin–Wilf per insegnare biiezioni tra interi positivi e razionali positivi, legami con le frazioni continue e confronti con l'albero di Stern–Brocot; una piccola API consente ai plugin LMS di verificare le risposte degli studenti per un n arbitrario senza distribuire un intero sistema di algebra computazionale. Poiché ogni chiamata riuscita costa il prezzo base pubblicato $0.002 senza token di modello né rete in uscita, la validazione fallita non consuma saldo e l'algoritmo è solo O(log n) somme intere, ottiene frazioni riproducibili per compiti, valutazione e worker di edge senza infrastruttura pesante di teoria dei numeri.
Domande tecniche
Quanto costa il calcolatore del termine di Calkin–Wilf?
Lo strumento nel browser è gratuito. Le richieste API usano il saldo KIT prepagato a $0.002 per chiamata riuscita; l'input non valido non viene fatturato.