裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

シフトと加算

2015年10月08日 | ブログラミング

装置がある。
装置にはディスプレイがあり,そこには最初 1 と表示されている。
ディスプレイの下には[+1]と[×2]という 2 つのボタンがある。
それぞれ,ディスプレイに表示されている数に 1 を加える,2 倍する,という機能だ。
ディスプレイある数を表示するために,最低何回ボタンを押さなければならないか求めよ。
たとえば,
10 を表示するためには ×2, ×2, +1, ×2 の 4 回
40 を表示するためには ×2, ×2, +1, ×2, ×2, ×2 の6 回
60 を表示するためには ×2, +1, ×2, +1, ×2, +1, ×2, ×2 の 8 回
65 を表示するためには ×2, ×2, ×2, ×2, ×2, ×2, +1 の 7 回

つまり,「全ての整数は,二進表示で,初期値 1 の左シフトと 1 の加算でできるということ。
左から順に 2 桁目以降が 0 なら左シフト 1 回,1 なら,左シフト 1 回と 1 の加算が必要。

func = function(n) {
  a = NULL
  repeat {
    a = c(n %% 2, a)
    if ((n = n %/% 2) == 0) break
  }
  a = a[-1]
  sum(a == 0) + sum(a == 1)*2
}

> func(10)
[1] 4

> func(40)
[1] 6

> func(60)
[1] 8

> func(65)
[1] 7

> func(10000000)
[1] 30

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

実数を分数で近似

2015年10月08日 | ブログラミング

実数 x,0.1 ≦ x ≦ 10 を,近似誤差が最も小さくなるような分数で表せ。
ただし,分子,分母共に 6 桁以内の整数とする。
たとえば,x = 1.618033963166706... の場合は,6765 / 4181 である。

変数名を長くしたので複雑そうに見えるが,実に簡単。for 文を使わず,ベクトル計算でやる。

func2 = function(x) {
  denominator = 1:999999
  numerator = as.integer(x*denominator)
  denominator = rep(denominator, 2)
  numerator = c(numerator, numerator +1)
  is.ok = 999999 >= numerator
  numerator = numerator[is.ok]
  denominator = denominator[is.ok]
  subscript = which.min(abs(x-numerator/denominator))
  cat(numerator[subscript], "/", denominator[subscript])
}

> func2(1.618033963166706)
6765 / 4181

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

PVアクセスランキング にほんブログ村

PVアクセスランキング にほんブログ村