5

だから、私は今Land of Lispを読んでいて、Lispは私が見た他のプログラミング言語とはかなり異なっていることがわかった。

とにかく、この本は、CLISPREPLに入力することを意図したいくつかのコードを提供します。

(defparameter *small* 1)
(defparameter *big* 100)

(defun guess-my-number ()
    (ash (+ *small* *big*) -1))

(defun smaller ()
    (setf *big* (1- (guess-my-number)))
    (guess-my-number))

(defun bigger ()
    (setf *small* (1+ (guess-my-number)))
    (guess-my-number))

さて、基本的な目標は、ユーザー/プレーヤーが数字を選択し、コンピューターが数字を推測しようとする数字推測ゲームを作成することです。コンピュータが推測した数がプレーヤーの数よりも多いか少ないかをプレーヤーに報告させることにより、プレーヤーの数を見つけるために「二分探索」を実行します。

関数について少し混乱していashます。これは二分探索に不可欠であると私は理解していますが、その理由はよくわかりません。この本はそれが何をするのかをいくらか説明していますが、少し混乱しています。

関数は何をしashますか？*small*なぜaddedto*big*とのパラメータが渡されるの-1ですか？それはどのように機能しますか？二分探索にはどのような目的がありますか？

4

3 に答える 3

3

グーグルはあなたにそれが算術シフト操作であることを説明するこのページを与えます。ashしたがって、1ビット右に(ash x -1)シフトして、整数の半分を与えます。x

于 2011-12-26T10:23:35.623 に答える
3

これについて助けてくれたBasileStarynkevitchに感謝します...

とにかく、算術シフト演算ashを実行します。

この場合、右に1ビット(ash x -1)シフトし、最終的に整数の半分を返します。x

たとえば、2進数を考えてみましょう1101。11012進数は10進数と同等で13あり、次のように計算できます。

8 * 1 = 8
4 * 1 = 4
2 * 0 = 0
1 * 1 = 1

8 + 4 + 0 + 1 = 13

実行(ash 13 -1)すると、13のバイナリ表現が調べられ、-1の算術シフトが実行され、すべてのビットが1だけ右にシフトされます。これにより、 （元の数値の末尾でを110切り落とす）のバイナリ出力が生成されます。2進数は10進数と同等であり、次のように計算できます。11106

4 * 1 = 4
2 * 1 = 2
1 * 0 = 0

4 + 2 + 0 = 6

ここで、13を2で割った値は6に相当しませんが、6.5に相当しますが、整数の半分を返すため、6が許容できる答えです。

これは、バイナリが基数2であるためです。

于 2011-12-26T10:46:20.253 に答える
1

Q. ash関数は何をしますか？なぜそれはbigと-1に加えられたsmallのパラメータを渡されるのですか？それはどのように機能しますか？二分探索にはどのような目的がありますか？

それはビットをシフトする操作を行います、より正確にはLispの特定のケースのためにグラフィカルに説明/表現されるように算術シフト：

> (ash 51 1)
102

これを行うと、51の2進数が左側に 1ビットずつ(ash 51 1)シフトし、結果として10進数で102になります。（2進数から10進数への変換のプロセスは、この回答で説明されています）1100111100110

ここに画像の説明を入力してください

ここでは、空いている最も適切な場所（L east S ignificant B itと呼ばれます）を追加 します。0

> (ash 51 -1)
25

これを行う(ash 51 -1)と、51の2進数が右側に1100111ビットずつシフトし（負の値は反対方向を表します）、結果として10進数で102になります。11001

ここに画像の説明を入力してください

ここでは、冗長LSBを破棄します。

Land of Lispに示されている「guess-my-number」ゲームの特定の例では、範囲を半分にするか、平均化することに関心があります。したがって、(ash (+ *small* *big*) -1))100 + 1 =100/2の半分を実行して50になります。次のように確認できます。

> (defparameter *small* 1)
*SMALL*
> (defparameter *big* 100)
*BIG*
> 
(defun guess-my-number ()
    (ash (+ *small* *big*) -1))
GUESS-MY-NUMBER
> (guess-my-number)
50

注目すべき興味深い点は、整数の値を1ビット左シフトすることで2倍にし、（約）1ビット右シフトすることで半分にすることができることです。

于 2019-05-14T16:08:16.623 に答える