頭の整理

頭の中を整えるために,色々と書き綴ります

2^n 計算法

{ \displaystyle n } 人で { \displaystyle 2^n } を計算する方法を解説します.

 

人の列:{ \displaystyle h_1\ ,\ h_2\ ,\ h_3 \ , \ \ldots\ , \ h_{n-1} \ ,\ h_n }

 

(1){ \displaystyle n } 人を横一列に並べ,左端から順に { \displaystyle h_1\ , \ h_2 \ , \ h_3 \ ,\  \ldots\ , \ h_{n-1} \ , \ h_n } とします.

(2){ \displaystyle h_n } は紙とペンを持ちます.紙は白紙の状態です(紙に書かれた線の本数を { \displaystyle M } とすると,{ \displaystyle M=0 } .)

(3)始めは,{ \displaystyle n } 人全員が右手を下しています( { \displaystyle h_j=1 \ (j=1,\ 2,\ldots,\ n) })

(4){ \displaystyle h_n } が紙に線を1本引き, { \displaystyle h_1 } に合図を送ります.( { \displaystyle M }{ \displaystyle M+1 } を代入.)

(5){ \displaystyle h_1 }{ \displaystyle h_n } から合図を受けたら下している右手を挙げるか,挙げている右手を下します.( { \displaystyle h_1 }{ \displaystyle h_1 \times (-1) } を代入.)

(6){ \displaystyle h_j \ (n \geq j>1)} は,{ \displaystyle h_{j-1} } が右手を挙げた状態から下したときに,下している自分の右手を挙げるか,挙げている自分の右手を下します.( { \displaystyle h_{j-1} }{ \displaystyle -1 } から { \displaystyle 1 } に変った場合,{ \displaystyle h_j }{ \displaystyle h_j \times (-1) } を代入.)

(7)(6)の動作が完了した段階で全員が右手を挙げていなければ(4)の動作に戻ります.全員が右手を挙げていれば,その時に紙に書かれている線の本数が { \displaystyle 2^n } の値になります.( { \displaystyle \sum_{j=1}^{n} h_j=-n } ならば,{ \displaystyle 2^n=M } .)

 

 

情報処理の基礎問題集 ?2進数の世界?

情報処理の基礎問題集 ?2進数の世界?

 
「Amazon.co.jpアソシエイト」