12

与えられた一連の正の数についてフロベニウス数を計算する最短のプログラムを作成します。フロベニウス数は、セット内の数の正の倍数の合計として記述できない最大の数です。

例: Chicken McNugget TMサイズのセット [6,9,20] の場合、式 a*6 + b*9 + c*20 = 43 (a,b ,c >= 0) であり、43 はこのプロパティの最大値です。

与えられた集合に対してフロベニウス数が存在すると仮定できます。そうでない場合 ([2,4] など)、特定の動作は予想されません。

参考文献:

[編集] GolfScript バージョンを受け入れることにしました。MATHEMATICA のバージョンは「技術的には正しい」と考えられるかもしれませんが、明らかに競技会の楽しみを奪ってしまいます。そうは言っても、他のソリューション、特に Ruby (汎用言語としては非常に短かった) にも感銘を受けました。

4

9 に答える 9

9

Mathematica 0文字（またはinvokeコマンドを数えて19文字）

で呼び出す

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

例

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

レコードですか？:)

于 2010-08-12T18:09:34.193 に答える
6

ルビー 100 8680文字

(改行は必要ありません) で呼び出す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 ソリューションと同じように機能します (ただし、より優れています:)。 $*コマンドライン文字列の配列です。aints と同じ配列で、作成可能なすべての数値を収集するために使用されます。eval(a*"*")製品、チェックする最大数です。

Ruby 1.9 では、 に置き換えることで を 1 文字追加でき"*"ます?*。

編集:Symbol#to_proc inを使用して 86 に短縮し、配列を折りたたむことで計算を$*.mapインライン化し、短縮します。編集 2:に置き換え、と交換。m
.times.map.to_a;i

于 2010-08-12T22:26:09.027 に答える
5

Mathematica プログラム - 28 文字

まあ、これは本当の（不要な）プログラムです。他の Mathematica エントリが明確に示しているように、プログラムを書かなくても答えを計算できます...しかし、ここにあります

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

で呼び出す

f[6, 9, 20]

43
于 2010-08-13T00:20:29.650 に答える
4

GolfScript47 /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
于 2010-08-12T09:42:02.127 に答える
3

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 これは私の最初のコード ゴルフ提出なので、入力の処理方法がわかりません。ルールは何ですか?

于 2010-08-12T08:37:40.033 に答える
2

Perl105107110119122127152158文字_ _ _ _ _ _ _ _

最新の編集：複合代入はあなたにぴったりです！

$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から：までの各番号について：入力番号の1つである場合は、ハッシュ$tを使用してマークを付けます。%hそれ以外の場合、さらに後ろからマークされたエントリがある場合（入力に違いがある場合）、このエントリにマークを付けます。マークされたすべてのエントリは、フロベニウス番号の候補ではありません。

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

マークされていないすべてのエントリを抽出します。これらはフロベニウス候補です...

print pop @b, "\n"

...そしてこれらの最後の、最も高いのは、フロベニウスの数です。

于 2010-08-12T18:24:22.957 に答える
2

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# ソリューションがあると確信していますが、これが私が思いついたものです。

これは、値をコマンド ライン パラメータとして受け取り、結果を画面に出力する完全なプログラムです。

于 2010-08-13T23:11:03.203 に答える
1

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]ます。

于 2010-08-12T09:20:56.520 に答える
-4

FrobeniusScript 5 文字

solve

残念ながら、この言語用のコンパイラ/インタプリタはまだ存在しません。

パラメータはありません。インタプリタはそれを処理します:

$ echo solve > myProgram  
$ frobeniusScript myProgram
6
9
20
^D
Your answer is: 43
$ exit
于 2010-08-13T00:25:32.477 に答える