当前位置：文江博客话题详情

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

发布于 2024-09-14 16:05:03 字数 678 浏览 7 评论 0原文

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

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

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

参考文献：

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

静若繁花 2024-09-21 16:05:03

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

Invoke withtih

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

示例

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

它是一条记录吗？ :)

Mathematica 0 chars (or 19 chars counting the invoke command)

Invoke wtih

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

Example

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

Is it a record? :)

回复收藏 0 原文

乱了心跳 2024-09-21 16:05:03

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 >。

Ruby ~~100 86~~ 80 chars

(newline not needed)
Invoke with 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]

Works just like the Perl solution (except better:). $* is an array of command line strings; a is the same array as ints, which is then used to collect all the numbers which can be made; eval(a*"*") is the product, the max number to check.

In Ruby 1.9, you can save one additional character in by replacing "*" with ?*.

Edit: Shortened to 86 using Symbol#to_proc in $*.map, inlining m and shortening its calculation by folding the array.
Edit 2: Replaced .times with .map, traded .to_a for ;i.

回复收藏 0 原文

以歌曲疗慰 2024-09-21 16:05:03

Mathematica 程序 - 28 个字符

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

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

Invoke with

f[6, 9, 20]

43

Mathematica PROGRAM - 28 chars

Well, this is a REAL (unnecessary) program. As the other Mathematica entry shows clearly, you can compute the answer without writing a program ... but here it is

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

Invoke with

f[6, 9, 20]

43

回复收藏 0 原文

就是爱搞怪 2024-09-21 16:05:03

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

GolfScript 47/42 chars

Faster solution (47).

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

Slow solution (42). Checks all values up to the product of every number in the set...

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

Sample I/O:

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

回复收藏 0 原文

乖乖兔^ω^ 2024-09-21 16:05:03

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，因为这是我第一次提交高尔夫代码，所以我不确定如何处理输入，规则是什么？

Haskell 155 chars
The function f does the work and expects the list to be sorted. For example 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

P.S. since that's my first code golf submission I'm not sure how to handle input, what are the rules?

回复收藏 0 原文

花桑 2024-09-21 16:05:03

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# 解决方案，但这就是我想出的。

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

C#, 360 characters

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++;}}}}

I'm sure there's a shorter C# solution than this, but this is what I came up with.

This is a complete program that takes the values as command-line parameters and outputs the result to the screen.

回复收藏 0 原文

娇纵 2024-09-21 16:05:03

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"

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

Perl 105 ~~107~~ ~~110~~ ~~119~~ ~~122~~ ~~127~~ ~~152~~ ~~158~~ characters

Latest edit: Compound assignment is good for you!

$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"

Explanation:

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

Set $t to the product of all of the input numbers. This is our upper limit.

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

For each number from 1 to $t: If it's one of the input numbers, mark it using the %h hash; otherwise, if there is a marked entry from further back (difference being anything in the input), mark this entry. All marked entries are non-candidates for Frobenius numbers.

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

Extract all UNMARKED entries. These are Frobenius candidates...

print pop @b, "\n"

...and the last of these, the highest, is our Frobenius number.

回复收藏 0 原文

瀞厅☆埖开 2024-09-21 16:05:03

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] 来调用它。

Haskell 153 chars

A different take on a Haskell solution. I'm a rank novice at Haskell, so I'd be surprised if this couldn't be shortened.

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

Call it with, e.g., f [9,6,20].

回复收藏 0 原文

嗳卜坏 2024-09-21 16:05:03

FrobeniusScript 5 个字符

solve

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

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

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

FrobeniusScript 5 characters

solve

Sadly there does not yet exist any compiler/interpreter for this language.

No params, the interpreter will handle that:

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

回复收藏 0 原文

~没有更多了~

关于作者

孤星

暂无简介

0 文章

0 评论

22 人气

关注发私信

友情链接

文江博客

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（9）

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

Mathematica 0 chars (or 19 chars counting the invoke command)

Mathematica 程序 - 28 个字符

Mathematica PROGRAM - 28 chars

关于作者

相关话题

热门标签

推荐作者

1CH1MKgiKxn9p

ゞ记忆︶ㄣ

JackDx

信远

yaoduoduo1995

霞映澄塘

友情链接

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（9）

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

Mathematica 0 chars (or 19 chars counting the invoke command)

Mathematica 程序 - 28 个字符

Mathematica PROGRAM - 28 chars

关于作者

相关话题

热门标签

推荐作者

1CH1MKgiKxn9p

ゞ记忆︶ㄣ

JackDx

信远

yaoduoduo1995

霞映澄塘

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。