1 円，2 円，10 円，52 円，82 円，280 円の切手を合計が 2007 円になるように買う方法を求めよ。ただし，買う枚数を最小にせよ。
素直に考えて，280 円切手を 7 枚，10 円切手を 4 枚，2 円切手を 3 枚，1 円切手を 1 枚，つまり，280*7 + 10*4 + 2*3 + 1*1 =2007 ということで，15 枚が取りあえずの候補。
280 円切手だけは 2007 %/% 280 = 7 枚までしか買えないがそのほかは，まあ他の制約はあるけど，15 枚以下でないと候補にはならない。そこで，効率なんかは考えずにプログラムをして，以下のプログラムを得る。
fee = 2007
for (i280 in 0:(fee %/% 280)) {
for(i82 in 0:15) {
for (i52 in 0:15) {
for (i10 in 0:15) {
for (i2 in 0:15) {
i1 = fee-(i280*280+i82*82+i52*52+i10*10+i2*2)
if (i1 < 0) break
if (sum(c(i1, i2, i10, i52, i82, i280)) <= 15) {
cat(i1, i2, i10, i52, i82, i280, "\n")
}
}
}
}
}
}
どれくらい計算時間が掛かるか分からないが（いや，たいしたことないことは分かる），実行して見ると，以下の結果が表示される。
1 0 1 2 6 5
1 3 0 3 2 6
1 3 4 0 0 7
つまり
1 円切手 1 枚，2 円切手 0 枚，10 円切手 1 枚，52 円切手 2 枚，82 円切手 6 枚，280 円切手 5 枚。計 15 枚で 2007円。
1 円切手 1 枚，2 円切手 3 枚，10 円切手 0 枚，52 円切手 3 枚，82 円切手 2 枚，280 円切手 6 枚。計 15 枚で 2007円。
1 円切手 1 枚，2 円切手 3 枚，10 円切手 4 枚，52 円切手 0 枚，82 円切手 0 枚，280 円切手 7 枚。計 15 枚で 2007円。
のいずれでもよい。
2 桁の整数のうち，2 進数表記と BCD 表記に含まれる 1 の個数が同じになる整数はいくつあるか。
馬鹿馬鹿しい問題だけど...
# 2 進数表記に含まれる 1 の個数
bin = function(n) {
count = 0
repeat {
count = count + n %% 2
n = n %/% 2
if (n == 0) return(count)
}
}
# 0～9 の BCD 表記に含まれる 1 の個数
count1 = numeric(10)
for (d in 0:9) count1[d+1] = bin(d)
# 2 桁の整数の 2 進数表記と BCD 表記に含まれる 1 の個数が同じかどうか
same = logical(99)
for (n in 11:99) {
same[n] = bin(n) == count1[n %/% 10+1] + count1[n %% 10+1]
}
sum(same) # 同じになる数の個数
(1:99)[same] # そのような数のリスト
実行結果
> sum(same) # 同じになる数の個数
[1] 20
> (1:99)[same] # そのような数のリスト
[1] 12 13 18 19 24 25 26 27 38 39 48 49 52 53 70 71 78 79 98 99
エネルギー最短経路の問題と同じ。ただ，対称行列であるところが違うが。
効率がよいか悪いか分からない新しい言語（？）を覚えるまでもない。
route = matrix(c(
0, 200, 200, 390, 160, 220,
200, 0, 160, 220, 220, 310,
200, 160, 0, 310, 220, 310,
390, 220, 310, 0, 470, 550,
160, 220, 220, 470, 0, 220,
220, 310, 310, 550, 220, 0), ncol=6, byrow=TRUE)
station = c("東京", "新宿", "渋谷", "三鷹", "錦糸町", "北千住")
dimnames(route) = list(station, station)
# 料金表
route
東京 新宿 渋谷 三鷹 錦糸町 北千住
東京 0 200 200 390 160 220
新宿 200 0 160 220 220 310
渋谷 200 160 0 310 220 310
三鷹 390 220 310 0 470 550
錦糸町 160 220 220 470 0 220
北千住 220 310 310 550 220 0
library(e1071)
# 東京から始まり東京で終わる場合
d = permutations(length(station))
d = d[d[,1] == 1,]
fee = apply(d, 1, function(from) sum(route[cbind(from, c(from[-1], from[1]))]))
p = which.min(fee)
fee[p]
apply(d[fee == fee[p],], 1, function(n) station[c(n, 1)])
# 東京から始まり錦糸町で終わる場合
d = permutations(length(station))
d = d[d[,1] == 1 & d[,6] == 5,]
fee = apply(d, 1, function(from) sum(route[cbind(from[-6], from[-1])]))
p = which.min(fee)
fee[p]
apply(d[fee == fee[p],], 1, function(n) station[n])
径路は列方向に見る
東京から始まり東京で終わる場合
> fee[p] # 料金
[1] 1390
> apply(d[fee == fee[p],], 1, function(n) station[c(n, 1)])
[,1] [,2] [,3] [,4]
[1,] "東京" "東京" "東京" "東京"
[2,] "渋谷" "新宿" "北千住" "北千住"
[3,] "三鷹" "三鷹" "錦糸町" "錦糸町"
[4,] "新宿" "渋谷" "渋谷" "新宿"
[5,] "錦糸町" "錦糸町" "三鷹" "三鷹"
[6,] "北千住" "北千住" "新宿" "渋谷"
[7,] "東京" "東京" "東京" "東京"
東京から始まり錦糸町で終わる場合
> fee[p] # 料金
[1] 1260
> apply(d[fee == fee[p],], 1, function(n) station[n])
[,1] [,2]
[1,] "東京" "東京"
[2,] "渋谷" "新宿"
[3,] "三鷹" "三鷹"
[4,] "新宿" "渋谷"
[5,] "北千住" "北千住"
[6,] "錦糸町" "錦糸町"
1～2014 までの数を 2 進数で表したときに，連続する 2 数の 1 の個数が同じであるようなペアは何組存在するか
連続する数のうち，(1, 2)，(5, 6), (9, 10), ...
のように, (4(i-1)+1, 4(i-1)+2)，i = 1, 2, ... の 2 数の 1 の個数が等しくなる。
よって，n までには ifelse((n-1)%%4, (n-1)%/%4+1, (n-1)%/%4) 組存在する
n = 2014 ならば，
> n = 2014
> ifelse((n-1)%%4, (n-1)%/%4+1, (n-1)%/%4)
[1] 504
504 組存在する
愚直なプログラムを書いて確かめるなら，
> func = function(n) {
+ count = 0
+ repeat {
+ count = count + n %% 2
+ n = n %/% 2
+ if (n == 0) return(count)
+ }
+ }
> sum(diff(sapply(1:n, func)) == 0)
[1] 504
20 分で答よということなので，できるだけ無精をすることにすると...
library(gmp)
p = 1
repeat {
p = nextprime(p)
if (p > 100) break
print(as.integer(p))
}
「パスカルの三角形」は「右上の数と左上の数の和」を配置するが，「和」ではなく「排他的論理和」を使う場合を考える。
2014番目の「0」が出力されるのは何段目になるか？
規則性もあるだろうが，たかが 2014 番目なので，多めに見積もって，馬鹿正直なプログラムを書く。
それでも，解を得るのに 0.06 程度しかかからないのだから，これ以上の策を弄するのは無駄というものだ。
system.time({
m = 100
a = matrix(0, m, m+1)
a[1, 2] = 1
for (i in 2:m) {
for (j in 2:(i+1)) {
a[i, j] = xor(a[i-1, j-1], a[i-1, j])
}
}
b = 1:m - rowSums(a)
p = which.min(2014 > cumsum(b))
print(p) # 解
print(sum(b[1:(p-1)])) # 念のための確認
print(sum(b[1:p])) # 念のための確認
})
[1] 75 # 75 段目
[1] 1980 # 74 段目の終わりまでに 1980 個
[1] 2047 # 75 段目の終わりまでに 2047 個
所要時間
ユーザ システム 経過
0.058 0.003 0.061
「どの桁にも 0, 3, 6, 9 が表れない」という条件を満たす正の整数を小さい順に並べて以下のような数列を作る。
1, 2, 4, 5, 7, 8, 11, 12, 14, 15, 17, 18, 21, 22, ...
この数列の 30 番目の項は 58 である。では，この数列の 10^7 番目の項を求めよ。
n 番目の項を手計算で求める。
0, 3, 6, 9 を含まない数だけを考えるということは，
要するに 1, 2, 4, 5, 7, 8 という記号で表される数を，0, 1, 2, 3, 4, 5 という 5 つの数字で表される 6 進数を考えるということ
出現する数字 6 進数字
1 0
2 1
4 2
5 3
7 4
8 5
6 進数字を使って表示すると
1 桁のものは 6 個 0，1, 2, 3, 4, 5
2 桁のものは 6^2 個 ただし，00, 01, ..., 55 であることに注意
3 桁のものは 6^3 個 ただし，000, 001, ..., 555 であることに注意
4 桁のものは 6^4 個 以下同様
5 桁のものは 6^5 個
6 桁のものは 6^6 個
7 桁のものは 6^7 個
8 桁のものは 6^8 個
ここまでで，累計 2015538 個の数（項）である（10 進数で）
目的の 10^7 番目は，9 桁の 6 進数 000000000 を 1 番目として，10^7-2015538 = 7984462 番目の数，数としては 007984461（10 進数）
7984462 の 6 進表示（9 桁）は 443045034
これを逆変換すると 775178157 になる。これが 10^7 番目の項
ということで，プログラム化
func = function(n) { # n 番目の数を求める
k = sum(n > cumsum(6^(1:8))) # k+1 桁の 6 進数の中にある
m = sum(6^(1:k)) # k 桁までの 6 進数の個数の総数
i = n - m - 1 # 求める数の k+1 桁の 6 進表記
num = numeric(k+1)
for (j in 1:(k+1)) {
num[j] = i %% 6
i = i %/% 6
if (i == 0) break
}
as.numeric(paste(c(1, 2, 4, 5, 7, 8)[rev(num)+1], collapse=""))
}
func(10^7) # 775178155
func(10^6) # 44244455
func(10^5) # 1858755
func(10^4) # 115155
func(10^3) # 5455
func(10^2) # 255
func(3333) # 24244
時間が掛かるが，真っ正直に計算して，正しいことを確かめるプログラム
func0 = function(n) {
count = 0
for (i in 1:1e7) {
a = unlist(strsplit(as.character(i), ""))
if (all(! (a %in% c(0, 3, 6, 9)))) {
# print(i)
count = count+1
if (count == n) break
}
}
print(i)
}
func0(3333) # 24244
func0(10^2) # 255
func0(10^3) # 5455
func0(10^4) # 115155
func0(10^5) # 1858755
PVアクセスランキング にほんブログ村
