Lan*_*dei 12 language-agnostic code-golf rosetta-stone
编写计算给定正数集的Frobenius数的最短程序.Frobenius数是最大数,不能写为集合中数字的正倍数之和.
例如:对于该组中的鸡McNugget的TM尺寸[6,9,20]弗罗贝尼乌斯数为43,因为没有无解的方程*6 + B*9 + C*20 = 43(用A,B ,c> = 0),43是具有此属性的最大值.
可以假设给定集合存在Frobenius数.如果不是这种情况(例如对于[2,4]),则不会出现特定的行为.
参考文献:
[编辑]我决定接受GolfScript版本.虽然MATHEMATICA版本可能被认为是"技术上正确的",但它显然会带来竞争的乐趣.也就是说,我也对其他解决方案印象深刻,特别是Ruby(对于通用语言来说非常简短).
调用
FrobeniusNumber[{a,b,c,...}]
例
In[3]:= FrobeniusNumber[{6, 9, 20}]
Out[3]= 43
这是一个记录吗？:)
红宝石 100 86 80个字符
(不需要换行)调用 frob.rb 6 9 20
a=$*.map &:to_i;
p ((1..eval(a*"*")).map{|i|a<<i if(a&a.map{|v|i-v})[0];i}-a)[-1]
就像Perl解决方案一样工作(除了更好:). $*是一个命令行字符串数组; a与int相同的数组,然后用于收集可以生成的所有数字; eval(a*"*")是产品,要检查的最大数量.
在Ruby 1.9,可以通过更换保存一个额外的字符"*"用?*.
编辑:通过折叠数组,使用Symbol#to_procin $*.map,inline m和缩短计算缩短为86 .
编辑2:替换.times用.map,成交.to_a了;i.
嗯,这是一个真实的(不必要的)程序.正如另一个Mathematica条目清楚地表明的那样,你可以在不编写程序的情况下计算出答案......但在这里它是
f[x__]:=FrobeniusNumber[{x}]
调用
f[6, 9, 20]
43
GolfScript 47/42 个字符
更快的解决方案（47）。
~:+{0+{.1<{$}{1=}if|}/.!1):1\{:X}*+0=-X<}do];X(
缓慢的解决方案（42）。检查所有值直到集合中每个数字的乘积...
~:+{*}*{0+{.1<{$}{1=}if|}/1):1;}*]-1%.0?>,
输入/输出示例：
$ echo "[6 9 20]"|golfscript frobenius.gs
43
$ echo "[60 90 2011]"|golfscript frobenius.gs
58349