加上一只羊减去一只羊

Question

很久很久以前。当还没有钱或股票的时候，人们就在交易羊。即使在“算盘”发明之前，沃伦·巴菲特的曾祖父就认为很难追踪羊的踪迹。他想收拾好所有的东西，还清所有的债务，这样他就可以投资买一台新的计票机，他听说他的朋友，比尔盖茨的曾祖父正在用棍子和珠子建造。他所有的交易都是原子性的，也就是说，他要么只给某人一只羊，要么只买一只羊。当然，自助餐爷爷有更多的羊，然后再给。实际上，他有749只羊要收集，他欠250只羊，所以他有499只羊。正因为如此，他事先为499只羊建造了一个谷仓。然后他给999个人打了电话，让他们排队。第一个人想要他的羊，但谷仓里还没有羊。他不喜欢这个订单，希望每个人都能重新排序，但首先是施舍者，然后是现在的收藏家。在500人的时候，谷仓里没有放新羊的地方，但在开始捐羊之前，仍有250只羊要收集。他把所有收集到的羊还给他，让他们再次排队，然后去盖茨爷爷那里帮他点菜。他们不知怎么搞清楚了，在499只羊的帮助下，他们建造了大量的算盘，从此过上了幸福的生活。

几年后，昨天比尔·盖茨和沃伦·巴菲特在一次捐赠誓言会议上相遇。他们讲了这个故事，笑了很多。然后盖茨对巴菲特说：“你知道吗，我不知道我的曾祖父是怎么订购了999个人的，但我知道有很多种方式。事实上，如果你让我这样做，我可以告诉你多少人……”然后，他回到自己的房间，写了一个代码来计算可能的订单数量，这些订单总是保证谷仓里总是有羊或空位，直到队列空了为止。他这样做了，但作为比尔盖茨，他写了一个递归函数，它正确但缓慢地解决了这个问题。所以每个人都在等待他的答案。自助餐无聊了，你能写一个更好更快的功能吗？

p = 749
n = 250
orderings(p,n) = ?

最短的代码获胜，但它必须在几分钟内完成，而不是几小时或几天。

Answer 1

Pyth，33字节

M?+&<HGgtGH&+-499GHgGtHH1g749 250

在网上试试：Pyth编译器/执行器。在我的笔记本电脑上大约需要3秒。在线编译器的速度有点慢，但也会在15秒内计算出答案。

答案是：

160547283350099323317963999889002394629262478407796913030854915361460989263675794524349914992326520887556329626280682363011590724268659750627030457440692447081328860242720905181098211539560301455338502543318855115593179999323115473879753632000

解释：

首先是递归函数的伪码.这很容易写。

function g(p, n):
   if (p > 0 and n > 0):
      count = 0
      if (occupied_places_in_barn < 499):
         count += g(p-1, n)
      if (occupied_places_in_barn > 0):
         count += g(p, n-1)
      return count
   else:
      return 1 # only one way possible

而毕思的译文：

M                                  def g(G,H): return _
    <HG                               H < G
   &   gtGH                                 and g(G-1,H)
            +-499GH                   499-G+H
           &       gGtH                       and g(G,H-1)
  +                                   return sum of these two numbers
 ?                     H1             if H else 1
                         g749 250  call g(749,250) and print

为什么这个递归代码这么快？函数g不是迭代了所有1.6*10^199的可能性吗？

不，没有。这里的关键是动态规划。当我们再次用相同的参数调用函数时，我们将已知的结果存储在缓存中并查找结果。Python的一个非常酷的特性是@lru_cache装饰器，它为您完成了所有的工作。不需要手动生成这样的缓存并处理像查找、存储结果、.在Pyth中，它甚至更简单，因为每个函数都自动使用这样的缓存。因此，函数g总共只执行125499次。少于1.6*10^199倍。