Utiliser 'ash' dans LISP pour effectuer une recherche binaire?

Donc, je lis maintenant Land of Lisp, et Lisp s'avère être très différent des autres langages de programmation que j'ai vus.Utiliser 'ash' dans LISP pour effectuer une recherche binaire?

Quoi qu'il en soit, le livre fournit un code que nous sommes censés entrer dans le CLISP REPL:

(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))

Maintenant, l'objectif de base est de créer un jeu de devinettes numéro dans lequel l'utilisateur/joueur choisit un certain nombre , puis l'ordinateur essaie de deviner le numéro. Il effectue une "recherche binaire", pour trouver le numéro du joueur, en demandant au joueur de signaler si le nombre deviné par l'ordinateur est supérieur ou inférieur au nombre du joueur.

Je suis un peu confus au sujet de la fonction ash. Je crois comprendre que c'est essentiel à la recherche binaire, mais je ne sais pas trop pourquoi. Le livre explique un peu ce qu'il fait, mais c'est un peu confus.

Que fait la fonction ash? Pourquoi est-il passé les paramètres de *small* ajoutés à *big* et -1? Comment ça marche? A quoi sert la recherche binaire?

Source

2011-12-26 Bhaxy

Probablement un décalage arithmétique. – leppie

Voir l'entrée HyperSpec sur [** ASH **] (http://www.lispworks.com/documentation/HyperSpec/Body/f_ash.htm): "ash effectue l'opération de décalage arithmétique sur la représentation binaire d'entier, qui est traité comme s'il était binaire. " –

Google vous donne this page qui explique que ash est une opération de décalage arithmétique. Donc (ash x -1) décale x d'un bit vers la droite, donc donne sa moitié entière.

Source

2011-12-26 10:23:35

Donc, il trouve effectivement la moyenne de '* small *' et '* big *', mais il renvoie un nombre entier plutôt qu'un virgule flottante? – Bhaxy

Oui, et il faut que '* small *' et '* big *' soient des entiers. –

Il n'est en fait pas nécessaire d'utiliser 'ash' pour obtenir une division entière en Lisp, il y a aussi les fonctions' floor' et 'truncate'. Vous pouvez donc remplacer '(ash x -1)' par '(floor x 2)'. –

Merci à Basile Starynkevitch pour l'aide sur celui-ci ...

Quoiqu'il en soit, ash effectue une arithmetic shift operation.

Dans le cas de (ash x -1), il décale x d'un bit vers la droite, ce qui renvoie finalement la moitié entière. Par exemple, considérez le nombre binaire 1101

Par exemple, considérons le nombre binaire 1101. 1101 en binaire est équivalent à 13 en décimal, qui peut être calculée comme ceci:

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

8 + 4 + 0 + 1 = 13

course (ash 13 -1) ressemblerait à la représentation binaire de 13, et effectuer un décalage arithmétique de -1, décaler tous les bits de la à droite par 1. Cela produirait une sortie binaire de 110 (en coupant le 1 à la fin du numéro d'origine). 110 en binaire est équivalent à 6 en décimal, ce qui peut être calculé comme si:

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

4 + 2 + 0 = 6

Maintenant, 13 divisé par 2 n'est pas équivalent à 6, il est équivalent à 6,5, cependant, car il retournera le demi-entier , 6 est la réponse acceptable. Ceci est dû au fait que le binaire est la base 2.

Source

2011-12-26 10:46:20 Bhaxy

Utiliser 'ash' dans LISP pour effectuer une recherche binaire?

Répondre

Questions connexes