あたまの体操してますか？
以下は、 プログラマ脳を鍛える数学パズルを写経したときのメモです。回答例はRubyで記述したものです。もっとRubyのメソッドを活用すればきれいに書けるZE☆などあったら、コメントください。
Q1〜Q3まであります。前提条件の後に問題が表示されます。回答例を見る前にコーディングしてみると、あたまの体操になります。（たぶん）
Q1.カードを裏返したい
【前提】
1〜100までの番号が書かれた100枚のカードが1から順番に並んでいます。最初、すべてのカードは裏返しの状態になっています。ある人が2番目のカードから、1枚おきにカードを裏返していきます（２,4,6...100のカードが表を向く）。次に３番めのカードから２枚お気にカードを裏返していく。（表向きのカードは裏返され、裏向きのカードは表を向く）。このようにn番目のカードからn-1枚おきにカードを裏返す操作を、どのカードの向きも変わらなくなるまで続けたとします。
【問題】
カードの向きが変わらなくなったとき、裏向きになっているカードの番号をすべて求めてください。
【回答例】
# 100枚のカードを初期化
N = 100
cards = Array.new(N, false)
# 2〜Nまで裏返す
(2..N).each do |i|
j= i -1
while (j < cards.size ) do
cards[j] = !cards[j]
j += i
end
end
# 最後に裏向きのカードを出力する
N.times do |i|
puts i + 1 if !cards[i]
end
【考え方】
左から順番に処理していけばOK。
表向きを「true」, 裏向きを「false」とすることで、反転を表現できる。
Q2.棒を切り分けたい
【前提】
長さn[cm]の一本の棒を、1cm単位に切り分ける。一本の棒を一度に切ることができるのは、1人だけ。例えば、切り分けられた棒が3本あるとき、同時に3人で切ることができる。
最大m人の人間がいるとき、最短で何回切り分けられるかを求めてください。
【問題】
n=100, m=8のときの回数を求めよ。
# currentは現在の棒の数
def cutbar(m, n , current)
# 切り終えたとき
if current >= n then
0
# 切る人より、現在の棒の数が少ない時、切れる
elsif current < m then
# 切れたら現在の2倍になる
1 + cutbar(m, n, current * 2)
else
# 切る人の数だけ増加
1 + cutbar(m, n, current + m)
end
end
puts cutbar(8, 100, 1)
【考え方】
一本の棒を切れるのは1人だけ。棒を切れるときの条件を整理する。
（問題を逆に読み、1cmの棒をm人で繋いで、n[cm]の棒を作ることとも読み替えられる→別解を考えてみよう！）
Q3.どうしても現金で払いたい
【前提】
バスに設置されているような、両替機を想定してください。この機械では、10円、5０円、100円、500円の組み合わせで両替することができる。両替する際に、使われない硬貨があっても構いませんが、大量の小銭は持て余すので、最大で15枚となるように両替します。例えば、「50円玉、20枚」という両替はNG。
【問題】
1,000円札を入れた時の、硬貨の組み合わせは何通りになるか？
- 回答例[強引ver.]
count = 0
(0..2).each do |y500|
(0..10).each do |y100|
(0..15).each do |y50|
(0..15).each do |y10|
if y500 + y100 + y50 + y10 <= 15 then
if y500 * 500 + y100 * 100 + y50 * 50 + y10 * 10 == 1000 then
count +=1
end
end
end
end
end
end
puts count
- 回答例[メソッド活用ver.]
coins = [10, 50, 100, 500]
count = 0
(2..15).each do |i|
coins.repeated_combination(i).each do |coin_set|
count +=1 if coin_set.inject(:+) == 1000
end
end
puts count
おわりに
いかがでしたか？
今回は、ちょっとあたまの体操がしたいなという時に解いてみたいpuzzleをご紹介しました。
ぜひこの機会にあたまをやわらかくしてみてくださいね。（こちらの記事の情報は記事更新時点のものです。事前に最新のあたまの体操情報をご確認ください）
