テール再帰で "n-rooks"を解く

Question

テイル再帰よりも速いので、n個のルーク問題を解決しようとしていますが、すべての作業を行う方法がわかりません。私は、この問題の背後にある理論を見上げると何かで与えられる解決策は、式で与えられる「電話番号」と呼ばれることがわかってきました：

T（1）= 1とT （2）= 2.

私はこの方程式を評価する再帰関数を作成しましたが、T（40）まではすぐにしか動作しません。現在のところ、推定値ではn> 1000を計算する必要があります計算の日数。

テール再帰は私の最善の選択肢だと思われますが、ここで誰かがテール再帰を使ってこの関係をプログラムする方法を知っていることを期待していました。

私はLISPで働いているが、

Answer 1

末尾再帰は、再帰のように表すだけループで末尾再帰をサポートしている任意の言語を使用してのオープンとなります。

「フォーク」という再帰的定義がある場合、素朴な実装はT（n）からT（n-1）、T（n-2）、T（n） 2）、T（n-3）、T（n-3）、T（n-4）である。

トリックは、T（1）とT（2）から構築するように計算を逆にしています。これは、各ステップで一定の時間を必要とするだけなので、全体的な計算は線形です。

(let ((n 2) 
     (t-n 2) 
     (t-n-1 1)) 
    …) 

とスタートのは、更新のためdoループを使用してみましょう：

(do ((n 2 (1+ n)) 
    (t-n 2 (+ t-n (* n t-n-1))) 
    (t-n-1 1 t-n)) 
    …) 

今、あなたはちょうどあなたがあなたの希望nに達したときに停止する必要があります。

(defun telephone-number (x) 
    (do ((n 2 (1+ n)) 
     (t-n 2 (+ t-n (* n t-n-1))) 
     (t-n-1 1 t-n)) 
     ((= n x) t-n))) 

であるために入力を確認してください：

(defun telephone-number (x) 
    (check-type x (integer 1)) 
    (if (< x 3) 
     x 
     (do ((n 2 (1+ n)) 
      (t-n 2 (+ t-n (* n t-n-1))) 
      (t-n-1 1 t-n)) 
      ((= n x) t-n)))) 

また、テストを作成し、これが何であり、どのように使用するのかのドキュメントを追加してください。これはまだテストされていません。このテール再帰を書くとき

、あなたは新しい値で再帰：末尾再帰が最適化されている場合

(defun telephone (x) 
    (labels ((tel-aux (n t-n t-n-1) 
      (if (= n x) 
       t-n 
       (tel-aux (1+ n) 
          (+ t-n (* n t-n-1)) 
          t-n)))) 
    (tel-aux 2 2 1))) 

、これはループのようにスケール（ただし、一定の係数は異なる場合があります）。 Common Lispはテールコールの最適化を要求していないことに注意してください。