ボーナスドリンク問題の解答

こちらの記事を見てみて、面白そうな問題がいくつかあったので、プログラミング初心者ではないですが解きました。

blog.jnito.com

ボーナスドリンク問題

「ある駄菓子屋で飲み物を買うと、空き瓶3本で新しい飲み物を1本プレゼントしてくれる。最初に100本購入した場合、トータルで何本飲めるか」

解答

コード

class BonusDrink
  def self.total_count_for(amount)
    return 0 if amount.zero?

    last_amount = (amount - 1) % 2 + 1
    (3 * amount - last_amount) / 2
  end
end

テストコードはこちら。

require 'rspec'
require File.expand_path(File.dirname(__FILE__) + '/../bonus_drink')

describe BonusDrink do
  specify { expect(BonusDrink.total_count_for(0)).to eq 0 }
  specify { expect(BonusDrink.total_count_for(1)).to eq 1 }
  specify { expect(BonusDrink.total_count_for(2)).to eq 2 }
  specify { expect(BonusDrink.total_count_for(3)).to eq 4 }
  specify { expect(BonusDrink.total_count_for(11)).to eq 16 }
end

解説

最初にN本買ってきたときに、最終的に飲める本数をf(N)とします。

f(1) = 1
f(2) = 2
f(3) = 4
f(11) = 16

です。

例として問題にある通り、今回はN=100の場合を考えます。

f(100) = 最初に100本買ってきたときに最終的に飲める本数

まず、100本の中身が入っているジュースがあります。

3本飲んでください。

さっそく3本だけ取り替えに行きましょう。1本もらいました。

手元にあるジュースの本数を確認しましょう。 残ってる97本と取り替えた1本で98本ですね。 98本で飲める量はf(98)で表されるのでした。

すでに3本のジュースを飲んでいるので、 100本のジュースで飲める量は、

f(100) = 3 + f(98)

で表すことができます。

同様に98本のうち3本を飲んで新しいジュース1本と交換します。

手元には96本のジュースがあります。すでに6本のジュースを飲んでいるので100本で最終的に飲める本数は以下の式で表すことができます。

f(100) = 3 + 3 + f(96)

お気付きのように、ジュースを3本飲むごとに手持ちのジュースが2本減ります。

繰り返していきましょう。

f(100) = 3 + 3 + 3 + f(94)
f(100) = 3 + 3 + 3 + 3 + f(92)
f(100) = 3 + 3 + 3 + 3 + 3 + f(90)
# 中略
f(100) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + f(6)
f(100) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + f(4)
f(100) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + 3 + f(2)

ここで手持ちのジュースが2本になってしまいました。 最後にこれを飲みましょう。

f(100) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + 3 + 2

では、上の式で3を何個足したか数えましょう。 100から2まで、2ずつ引いていったので、

(100 - 2) / 2 = 49

49個の3を足しています。

なので、上記の式は以下のように書き換えられます。

f(100) = 3 * 49 + 2
       = 149

最初に100本買った場合に最終的に飲める本数は149本であることがわかりました。(プログラムで算出するはずなのに、算数的に解いてしまった)

本数がNの時は上記と同様に

f(N) = 3 * (N-2)/2 + 2

となります。しかし、2本ずつ引いていって最後に2本になるのは偶数の時のみです。 奇数の場合を考えてみましょう。例として97本の場合を考えます。

考え方は同様で、3本飲むと、2本手持ちが減ります。これを数式にしていきます。

f(97) = 3 + f(95)
f(97) = 3 + 3 + f(91)
f(97) = 3 + 3 + 3 + f(89)
f(97) = 3 + 3 + 3 + 3 + f(87)
# 中略
f(97) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + f(5)
f(97) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + f(3)
f(97) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + 3 + f(1)

このようになり、最後に手持ちの1本を飲んで終わりです。

f(97) = 3 + 3 + 3 + 3 + 3 + ... + 3 + 3 + 3 + 3 + 3 + 1

97から1まで2ずつ引いたので、足した3の数は、

(97 - 1)/2 = 48

48個の3を足したので、

f(97) = 3 * 48 + 1
      = 145

最初に97本買った場合に最終的に飲める本数は145本であることがわかりました。

本数がNかつNが奇数の時、最終的に飲めるジュースの本数は

f(N) = 3 * (N-1)/2 + 1

になります。

ここまでをまとめると、

f(N) = 3 * (N-2)/2 + 2 (Nが偶数のとき)
       3 * (N-1)/2 + 1 (Nが奇数のとき)

です。

コードにしてみましょう。メソッドの最初にamountが0の時に0を返す処理を書いています。 amount % 2はamountを2で割ったときの余りという意味です。

class BonusDrink
  def self.total_count_for(amount)
    return 0 if amount.zero?

    case amount % 2
    when 0
      3 * (amount - 2) / 2 + 2
    when 1
      3 * (amount - 1) / 2 + 1
    end
  end
end

2つの式は似ているので、工夫すればまとめられそうです。 2つの式の違いは、amountから引いている数と最後に足している数です。この数は最後に手元に残る瓶の本数でした。

奇数と偶数で値が異なるので、

last_amount = amount % 2 === 0 ? 2 : 1
3 * (amount - last_amount) / 2 + last_amount

のようなコードを書きたくなりますが、あまりよい方法とは言えません。"3本で1本プレゼント"が"4本で1本プレゼント"になったときに対応できなくなってしまいます。

基本的には剰余(割り算の余り)を考えればよいのですが、割り切れる時には2にします。

last_amount = amount % 2 === 0 ? 2 : amount % 2
3 * (amount - last_amount) / 2 + last_amount

3項演算子を使わなくても、一旦1を引いて剰余を求めてから1を足すと同様の結果が得られます。

last_amount = (amount - 1 ) % 2 + 1
3 * (amount - last_amount) / 2 + last_amount

式を整理して、最終的にこちらのコードになります。

class BonusDrink
  def self.total_count_for(amount)
    return 0 if amount.zero?

    last_amount = (amount - 1 ) % 2 + 1
    (3 * amount - last_amount) / 2
  end
end

完成です！

あとがき

最初に再帰のアルゴリズムを思いついたのですが、最終的に四則演算と剰余だけで求めることができました。 試行錯誤できて楽しい問題でした。

ちなみに5本で1本交換の場合は、以下のようになります。

class BonusDrink
  def self.total_count_for(amount)
    return 0 if amount.zero?

    last_amount = (amount - 1 ) % 4 + 1
    (5 * amount - last_amount) / 4
  end
end

算数としてはこれで答えは出るのですが、プログラミングとしては整除を使用すればもう少し短く書けるかもと思いました。

こちらもどうぞ

yucatio.hatenablog.com

面白くて眠れなくなる数学 （PHP文庫） [ 桜井進 ] 価格：691円（税込、送料無料) (2019/2/8時点) 楽天で購入