2

そのため、私たちのクラスには、10 進数を 8 進数表現に変換する割り当てが与えられました。機能するまでなんとかいじくり回しましたが、なぜ機能するのか理解できません。より単純な方法で再帰を説明する可能性はありますか? ありがとう。

(define octify
 (lambda (n)
  (cond
   ((zero? n) 0)
   ((zero? (quotient n 8)) n)
   (else  (+ (* 10 (octify (quotient n 8))) (remainder n 8))))))
4

3 に答える 3

3

まず、「数値」は 10 進数でも 8 進数でもありません。「数」は数学的概念であり、一連のビットを含む何らかの形式でコンピューターに保存されます。10 進数と 8 進数は、数値の異なる文字列表現を参照します。つまり、「10 進数」や「8 進数」などは文字列について話す場合にのみ意味があり、特定の数値は 10 進数や 8 進数などの文字列に変換できます。

整数の 8 進数 (またはその他の基数) の文字列表現を生成することは、プログラミングの一般的な基本タスクです。あなたが基本的に理解したアルゴリズム: 基数で数値の剰余を取って最後の桁を取得し、基数で数値の商を再帰して、数値の残り (最後の桁を除くすべて) を取得します。

あなたがしていることについて奇妙なのは、このタスクで通常行うように、文字列を生成していないことです。代わりに、結果の数値の 10 進数表現が元の数値の 8 進数表現と同じように見えるように、それを数値にパックしようとしています。(8 進表現は何らかの数値の有効な 10 進表現でもあるため、これはたまたま可能です。たとえば、16 進数では不可能です。) 言い換えると、数値を 8 進文字列表現に変換してから、その文字列を 10 進表現であるかのように数値に変換します。たとえば、10 進数表現が文字列 "42" で、8 進数表現が文字列 "52" である数値 42 を取り上げます。

これをインタープリターに入力しているため、混乱する可能性があります。数値を計算または出力すると、10 進数表現が出力されます。ただし、数値は文字列とはまったく異なることを理解することが重要です。(インタプリタで文字列を計算した場合、おそらく引用符か何かで囲みます。) プログラムが、印刷されたときにそのように見える数値ではなく、8 進表現の文字列を出力した場合に最も意味があります。

于 2012-01-30T02:17:47.970 に答える
1

一世を風靡した数の主流表現は位置表記です。これは、商と剰余演算の概念と密接に結びついた表現であり、再帰関数の定義から多少見られます。何故ですか？

簡単に脇に置いておきましょう: 位置表記法は、数値の唯一の実行可能な表現ではありません。頻繁に出てくる方法の 1 つは、数値が 0 または数値よりも 1 大きい集計アプローチです。スティックを使用できます。プログラムについて話しているので、data-typeを使用しましょう。

Number :== Zero
         | Successor(n) where n is a number

これを「数値はゼロか、別の数値の後継である」と読みます。または、構造化表現 (Racket など) をサポートするスキームでコード化するには、次のように記述できます。

(define-struct Zero ())
(define-struct Successor (n))

たとえば、この表記法で3 つ(Successor (Successor (Successor (Zero)))を表すと、 になります。(私の記憶が正しければ、この表現はペアノと呼ばれます。)

この種の構造化されたデータ型を扱う関数は、多くの場合、データ型自体と同じ形をしています。つまり、ペアノの表現で機能する関数は次のようになります。

 ;; a peano-eating-function-template: peano-number -> ???
(define (a-peano-eating-function-template a-num)
   (cond [(Zero? a-num)
          ...]
         [(Successor? a-num)
          ...
          (a-peano-eating-function-template (Successor-n a-num)) 
          ...]

は、...ペアノ数で解決しようとしている特定の問題に固有のものになります。作業中のデータの構造に従う関数の問題です。Peano を食べる関数の具体例として、ピアノを星の束に変える関数を次に示します。

;; peano->stars: peano-number -> string
;; Turn a peano in a string of stars.  We are all made of stars.
(define (peano->stars a-num)
  (cond [(Zero? a-num)
         ""]
        [(Successor? a-num)
         (string-append "*"
                        (peano->stars (Successor-n a-num)))]))

とにかく、データ型は自然に特定の形状の関数につながります。これにより、位置表記法に戻ります。位置表記をデータ型としてキャプチャできますか?

できることがわかりました！10 進表記などの位置表記は、ペアノ数の記述と同様の方法で記述できます。この表現をBase10と呼びましょう。ここでは次のようになります。

Base10 :== Zero
         | NonZero(q, r) where q is a Base10, and r is a digit.

Digit :== ZeroD | OneD | TwoD | ... | NineD

そして、構造を持つ言語でのプログラミングに関して具体的に理解したい場合は、

(define-struct Zero ())
(define-struct NonZero(q r))

(define-struct ZeroD ())
(define-struct OneD ())
(define-struct TwoD ())
(define-struct ThreeD ())
(define-struct FourD ())
;; ...

たとえば、数値42は Base10 で次のように表すことができます。

(NonZero (NonZero (Zero) (FourD)) (TwoD))

うわぁ。それは少し...非常識に見えます。しかし、これにもう少し頼りましょう。以前と同様に、Base10 を扱う関数は、多くの場合、Base10 の構造と一致する形状を持ちます。

;; a-number-eating-function-template: Base10 -> ??? 
(define (a-number-eating-function-template a-num)
  (cond
    [(Zero? a-num)
     ...]
    [(NonZero? a-num)
     ... (a-number-eating-function-template (NonZero-q a-num))
     ... (NonZero-r a-num)]))

つまり、Base10 自体の構造に従うだけで、Base10 で動作する再帰関数の形をほぼ無料で取得できます。

... しかし、これは数字を扱うクレイジーな方法ですよね? ええと... forty-two の風変わりな表現を思い出してください:

(NonZero (NonZero (Zero) (FourD)) (TwoD))

同じ数を表す別の方法を次に示します。

((0 * 10 + 4) * 10 + 2)

ほぼ同じ考えです。ここで、さらにいくつかの括弧を削除しましょう。次の表記法で42を表すことができます。

42

私たちのプログラミング言語は、この数字の表記法を扱う方法を知るためにハードコーディングされています。

ゼロをチェックするのに相当するものは何ですか? 私たちはそれを知っています。

(= n 0)   ;; or (zero? n)

NonZero のチェックに相当するものは何ですか? 簡単！

(> n 0)

NonZero-q と NonZero-r に相当するものは何ですか?

(quotient n 10)
(remainder n 10)

次に、ほとんどプラグアンドプレイで、数値入力を位置的に処理する再帰関数の形状を取得できます。

(define (a-decimal-eating-function-template n)
  (cond [(= n 0)
         ...]
        [(> n 0)
         ... (a-decimal-eating-function-template (quotient n 10))
         ... (remainder n 10)]))

見覚えがあります？:)

詳細については、How to Design Programsなどの教科書を参照してください。

于 2012-01-31T02:54:37.223 に答える
0

明らかに、(octify 0)は 0 であり(octify n)、0 < n < 8 が n であるような n の場合です。次の条件は複雑なものです。最初の質問は「何を(octify (quotient n 8))返すか」です。10 進数の場合、10 で割ると右端の桁が削除されます - 145/10=14 (整数除算を想定)。基数 8 の数値の場合、8 で割ると同様に機能します。したがって、(octify (quotient n 8))n の最後の桁を除くすべての数値を返しますが、それoctifyが正しく定義されていると仮定します (これを想定する必要があります)。ここで、この数値を 1 桁左に「プッシュ」する必要があります。プリンターは base-10 で印刷するため、これに 10 を掛けます。 (remainder n 8)n の最後の桁を取得します。これで、最初の数桁 (最後の桁はゼロ) と最後の桁ができたので、それらを追加して組み合わせることができます。この時点で、関数は実行され、正しい値が返されます。

于 2012-02-02T04:54:38.747 に答える