代码高尔夫：弗罗贝尼乌斯数

Question

编写最短的程序来计算给定正数集的弗罗贝尼乌斯数。弗罗贝尼乌斯数是不能写成集合中数字的正倍数之和的最大数字。

示例：对于麦乐鸡^TM尺寸集 [6,9,20]，弗罗贝尼乌斯数为 43，因为方程 a*6 + 无解 b*9 + c*20 = 43（其中 a,b,c >= 0），并且 43 是具有此属性的最大值。

可以假设给定集合存在弗罗贝尼乌斯数。如果情况并非如此（例如[2,4]），则不会出现任何特定行为。

参考文献：

• http://en.wikipedia.org/wiki/Coin_problem
• http://mathworld.wolfram.com/FrobeniusNumber.html

[编辑] 我决定接受 GolfScript 版本。虽然 MATHEMATICA 版本可能被认为“技术上正确”，但它显然会剥夺比赛的乐趣。也就是说，其他解决方案也给我留下了深刻的印象，尤其是 Ruby（这是通用语言的缩写）。

Answer 1

Mathematica 0 个字符（或 19 个字符，计算调用命令）

Invoke withtih

FrobeniusNumber[{a,b,c,...}]

示例

In[3]:= FrobeniusNumber[{6, 9, 20}]
Out[3]= 43

它是一条记录吗？ :)

Answer 2

Ruby 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 中，您可以通过将 "*" 替换为 ?* 来保存一个额外的字符。

编辑：在 $*.map 中使用 Symbol#to_proc 缩短为 86，内联 m 并通过以下方式缩短其计算折叠数组。
编辑2：用.map替换.times，用.to_a交换;i >。

Answer 3

Mathematica 程序 - 28 个字符

嗯，这是一个真正的（不必要的）程序。正如其他 Mathematica 条目清楚地显示的那样，您可以在不编写程序的情况下计算答案......但这里是

f[x__]:=FrobeniusNumber[{x}]

Invoke with

f[6, 9, 20]

43

Answer 4

GolfScript 47/42 字符

更快的解决方案 (47)。

~:+{0+{.1<{$}{1=}if|}/.!1):1\{:X}*+0=-X<}do];X(

缓慢的解决方案（42）。检查所有值，直到集合中每个数字的乘积...

~:+{*}*{0+{.1<{$}{1=}if|}/1):1;}*]-1%.0?>,

示例 I/O：

$ echo "[6 9 20]"|golfscript frobenius.gs
43
$ echo "[60 90 2011]"|golfscript frobenius.gs
58349

Answer 5

Haskell 155 个字符
函数 f 完成这项工作并期望对列表进行排序。例如 f [6,9,20] = 43

b x n=sequence$replicate n[0..x]
f a=last$filter(not.(flip elem)(map(sum.zipWith(*)a)(b u(length a))))[1..u] where
    h=head a
    l=last a
    u=h*l-h-l

PS，因为这是我第一次提交高尔夫代码，所以我不确定如何处理输入，规则是什么？

Answer 6

C#，360 个字符

using System;using System.Linq;class a{static void Main(string[]b)
{var c=(b.Select(d=>int.Parse(d))).ToArray();int e=c[0]*c[1];a:--e;
var f=c.Length;var g=new int[f];g[f-1]=1;int h=1;for(;;){int i=0;for
(int j=0;j<f;j++)i+=c[j]*g[j];if(i==e){goto a;}if(i<e){g[f-1]++;h=1;}
else{if(h>=f){Console.Write(e);return;}for(int k=f-1;k>=f-h;k--)
g[k]=0;g[f-h-1]++;h++;}}}}

我确信有比这更短的 C# 解决方案，但这就是我想出的。

这是一个完整的程序，它将值作为命令行参数并将结果输出到屏幕。

Answer 7

Perl 105 107 110 119 122 127 < s>152 158 个字符

最新编辑：复合赋值对您有好处！

$h{0}=$t=1;$t*=$_ for@ARGV;for$x(1..$t){$h{$x}=grep$h{$x-$_},@ARGV}@b=grep!$h{$_},1..$t;print pop@b,"\n"

说明：

$t = 1;
$t *= $_ foreach(@ARGV);

将 $t 设置为所有输入数字的乘积。这是我们的上限。

foreach $x (1..$t)
{
  $h{$x} = grep {$_ == $x || $h{$x-$_} } @ARGV;
}

对于从 1 到 $t 的每个数字：如果它是输入数字之一，则使用 %h 哈希对其进行标记；否则，如果后面有一个标记条目（输入中存在任何差异），请标记该条目。所有标记的条目都不是弗罗贝尼乌斯数的候选数。

@b=grep{!$h{$_}}(1..$t);

提取所有未标记的条目。这些是弗罗贝尼乌斯候选数......

print pop @b, "\n"

最后一个，也是最高的，是我们的弗罗贝尼乌斯数。

Answer 8

Haskell 153 个字符

Haskell 解决方案的不同版本。我是 Haskell 的新手，所以如果不能缩短它，我会感到惊讶。

m(x:a)(y:b)
 |x==y=x:m a b
 |x<y=x:m(y:b)a
 |True=y:m(x:a)b
f d=l!!s-1where
 l=0:foldl1 m[map(n+)l|n<-d]
 g=minimum d
 s=until(\n->l!!(n+g)-l!!n==g)(+1)0

例如，使用 f [9,6,20] 来调用它。

Answer 9

FrobeniusScript 5 个字符

solve

遗憾的是，目前尚不存在这种语言的任何编译器/解释器。

没有参数，解释器将处理：

$ echo solve > myProgram  
$ frobeniusScript myProgram
6
9
20
^D
Your answer is: 43
$ exit