阿男的小窝

View the Project on GitHub

卖酒的算法题解

基友发来一道算法题:

大概的意思就是:一共有六桶酒,白酒数量为5,上午卖了2,下午还剩3。因此下午三桶的升数之和应该是上午的两倍:

找到这样的关系以后,那么最后剩下那桶就是红酒了。大概想了下,一个比较直接的思路就是,可以把它当成是一个排列组合的任务:上午卖两桶,就是从5个元素里面任意取两个元素;下午卖三桶,就是在剩下的四桶里面任意取3。然后在这样的排列组合当中,找到下午的数字之和是上午的二分之一的组合,然后最后剩下的那个元素就是红酒了。这个任务可以用ruby代码来做做看。rubyarraypermutation的能力,我们可以用用看:

可以看到permutation把数组里元素所有可能的顺序组合都列出来了。这个permutation方法还支持定制选取元素的数量进行排列:

irb(main):005:0> arr.permutation(2).to_a
=> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

有了这个方法,我们就可以列出所有酒桶的排列方式了。首先是定义酒桶的数组:

irb(main):006:0> buckets = [30, 32, 36, 38, 40, 62]
=> [30, 32, 36, 38, 40, 62]

然后是取其中两个元素,列出所有的可能性,相当于上午取两桶酒的所有可能:

上面这个排列组合里面,数组的元素是有顺序的,因为是permutation,而不是combinationruby除了『排列』,也提供了『组合』的功能。下面是combination(...)方法:

irb(main):012:0> buckets.combination(2).to_a
=> [[30, 32], [30, 36], [30, 38], [30, 40], [30, 62], [32, 36], [32, 38], [32, 40], [32, 62], [36, 38], [36, 40], [36, 62], [38, 40], [38, 62], [40, 62]]

从上面的结果可以看到顺序不同,元素一样的数组不存在了,只剩下元素不同的数组。上面这个数组代表了『上午卖出的两桶酒』的所有可能。因此,我们针对每一个可能,刨去上面的元素,再从剩下的4个元素里面取3,并列出所有的组合。从一个数组中刨去某些元素的代码如下:

可以看到,使用减号就可以了,剩下的元素是刨去了上午售出的酒。此时在这个数组当中再用combination(...)方法,取出三个元素,列出所有组合。然后把三个元素的值相加,如果是上午的两个元素相加的值的两倍,那么剩下的那个元素就是最后剩下的红酒了。因此,两个for循环就可以完成上面所讲的逻辑了。完整的代码如下:

buckets = [30, 32, 36, 38, 40, 62]
sold_at_morning = buckets.combination(2).to_a

arr = []
for x in sold_at_morning
  left = buckets - x
  sold_at_afternoon = left.combination(3).to_a
  sum_morning = x.inject(0) { |sum, _x| sum + _x }
  for y in sold_at_afternoon
    sum_afternoon = y.inject(0) { |sum, _y| sum + _y }
    if sum_afternoon.to_f / sum_morning == 2
      puts "morning: #{x} / afternoon: #{y} / red wine: #{buckets - x - y}"
      exit
    end
  end
end

上面的代码就是前面讲的思路的实现,具体用到的一些之前没讲到的技巧包括:

sum_morning = x.inject(0) { |sum, _x| sum + _x }

上面这个block会计算数组的元素之和。

sum_afternoon.to_f / sum_morning == 2

上面的to_f,把sum_afternoon的数值类型从int转化成float,这样保证我们计算所得是被整除的。因为两个int型数据相除是会取整的,这样结果为2的时候不一定是被整除为2。运行上面的代码,结果如下:

morning: [30, 36] / afternoon: [32, 38, 62] / red wine: [40]

得到结果是红酒为40升的这桶,并给出了上午和下午卖出酒桶的升数。以上是对解题思路的一个记录。