裏 RjpWiki

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

素数で作る天秤ばかり

2016年09月20日 | ブログラミング

素数で作る天秤ばかり

2016/09/20 10:00 AM なので,その 1 分後に投稿されるように予約

【問題】
天秤ばかりを使って重さを量りたいと考えています。
ただし、使えるおもりは重さが素数のものしかありませんでした。

m, n をともに正の整数とし、m 以下の素数すべてがおもりの重さとして1つずつ用意されているとき、n グラムの計り方が何通りあるかを求めてください。

例えば、m = 10, n = 2のとき、2, 3, 5, 7 のおもりが一つずつありますので、左右に以下のおもりを使った4通りがあります。
(量るものを左側に置いたとします。)

左側         右側
なし         「2」
「3」         「5」
「5」         「7」
「2」、「3」     「7」

標準入力から m と n がスペースで区切って与えられるとき、n グラムの計り方が何通りあるかを標準出力に出力してください。
(ただし、 m < 50 とします。)

【入出力サンプル】
標準入力
10 2

標準出力
4


==========

bin を毎回呼び出すとそのオーバーヘッドがあるので,結果をリスト bin.list に保存しておき,関数呼び出しをリストの参照に換えることで,実行時間は速くなる

bin = function(p) {
    retval = matrix(0L, nrow = 2^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0L, (2^p/2^n)), rep(1L, (2^p/2^n))), length = 2^p)
    }

    retval
}

f = function(m, n) {
    bin.list = sapply(1:14, bin)
    count = 0
    prime = c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
    prime = prime[m >= prime]
    left.use = bin.list[[length(prime)]] # bin(length(prime))
    left = left.use %*% prime + n
    for (i in 1:(nrow(left.use) - 1)) {
        rest = prime[!left.use[i, ]]
        if (sum(rest) >= left[i]) {
            right.use = bin.list[[length(rest)]] # bin(length(rest))
            right = right.use %*% rest
            count = count + sum((left[i] == right))
        }
    }
    cat(count)
}


f(10, 2)  # 4
f(20, 10) # 90
f(30, 50) # 286
f(40, 30) # 3217
f(46, 3)  # 24946

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

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

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