Ruby [更新问题] 把 n 个苹果放在 k 个篮子里,其中每个篮子都有一定容量,一个篮子放满了之后再放入下一个篮子,如何放置?

FarFar · 2012年11月30日 · 最后由 xranthoar 回复于 2012年12月03日 · 6524 次阅读

延续前面累加数组的问题,现在多一个限值变量 给定一个任意数组 a 和一个限值 n, 问题:在数组 a 的基础上得到一个数组 b,使得数组 b 的和为 n,具体看以下测试用例

/////////////////////////////////////////////////////////

之前的表述可能太抽象了,也太无聊了,我再具体形象一点,可以更能容易理解:

比如,现在有 k 个篮子 (每个篮子都有自己的数字编号),和 n 个苹果;

每个篮子只能放一定数量的苹果,a=[e_0, e_1, ..., e_k-1],那么现在要把这个 n 个苹果,按篮子的编号顺序,不断放入篮子中,而且一个篮子放满了之后再放入下一个篮子。

如果篮子都放满了,苹果还有剩余,则把剩余的苹果放在仓库里,假定仓库可以放无限多的苹果。

现在想要知道的是所有装苹果的篮子(可能有些篮子是空的)的苹果数量,以及仓库中的数量(可能篮子不够装)

假设这个方法叫 f(a, n),a 数组代表所有篮子的容量,n 是苹果数量 以下是各种情况的测试用例

/////////////////////////////////////////////////////////

# []表示没有篮子,所有苹果都得放在仓库里
f([], 2) #  => [2] 

# 第一个篮子就够放了
f([3,2,4,5], 2) #  => [2]

f([3,2,4,5], 6) #  => [3,2,1]
f([3,2,4,5], 10) #  => [3,2,4,1]

# 所有篮子都不够装,最后剩余2个苹果要放在仓库里
f([3,2,4,5], 16) #  => [3,2,4,5,2]

/////////////////////////////////////////////////////////

这个也不是什么面试题,只是我实际中遇到的动态分组问题。我写了一个比较丑陋的方法,虽然测试了下都没问题,但是还是觉得看着别扭,可能是我想的太复杂的,大家可以先参考下。我觉得应该有更简单明了的方法,有兴趣的同学可以想一下。

def f(a, n)
  #先求a的累加数组,也就是篮子的累积容量
  b = a.inject([]) { |sum,e| sum << e + (sum[-1] || 0) }

  #初始化output数组
  c=[]

  #确定需要多少个篮子以及是否需要放在仓库里
  m = (b.length==0) ? 1 : ((b.index{|e| e >= n } || b.length) + 1)

  m.times do |i|
    if m == 1
      c << n
    elsif i < m-1
      c << a[i]       
    else
      c << n - (b[i-1] || 0)
    end
  end
  c
end
1 楼 已删除
匿名 #2 2012年12月02日
def f(a, n)
   return [n] if a.count == 0 
   return [0] if n == 0

   sum, last_sum, i = 0, 0, 0
   while i < a.count
       last_sum = sum
       sum += a[i]
       break if sum >= n
       i += 1
   end

   return a[0..i] if sum == n
   return a[0...i]<< n-last_sum if sum > n
   Array.new(a) << n-sum
end

c style~ 😄

终于等到想要的了,对 ruby 还不是太熟,现在才知道有 take_while 这个方法,唉,太惭愧了,相形见拙 #3 楼 @luikore 非常感谢!!!

#4 楼 @FarFar

如果用过一些函数式语言如 Haskell , 里面是没有 breakcontinue 的,如果不能事先知道要遍历的 list 的长度,就只能用 find, takeWhile, dropWhile 之类的函数给条件,然后用多了还会觉得挺好用,想问题的方式都不一样了...

顺便一扯 Ruby 就算在这类函数里也能用 breaknext 的,而且 breaknext 后面还能加参数可以写出各种神奇的让人抓狂的代码...

#5 楼 @luikore 的确,我之前就是在钻牛角尖,思路比较局限,没打开,你的思路和方法很受用,激动...

其实我觉得 ruby 是适合做 dsl 的,因此出现各种封装都不稀奇,但是最底层的才是有价值的东西吧。比如楼主写的代码算不算是 takewhile 在这个问题下的实现?如果是的话,那没啥好激动地,因为写实现的更伟大

需要 登录 后方可回复, 如果你还没有账号请 注册新账号