高尔夫代码:弗罗贝尼厄斯编号 [英] Code Golf: Frobenius Number

问题描述

写出最短的程序，为给定的一组正数计算Frobenius数. Frobenius数是不能写为集合中数字正整数之和的最大数字.

Write the shortest program that calculates the Frobenius number for a given set of positive numbers. The Frobenius number is the largest number that cannot be written as a sum of positive multiples of the numbers in the set.

示例:对于大小为Chicken McNugget ^TM 的集合[6,9,20]，Frobenius数为43，因为方程a的无解 * 6 + b * 9 + c * 20 = 43(a，b，c> = 0)，并且43是具有此属性的最大值.

Example: For the set of the Chicken McNugget^TM sizes [6,9,20] the Frobenius number is 43, as there is no solution for the equation a*6 + b*9 + c*20 = 43 (with a,b,c >= 0), and 43 is the largest value with this property.

可以假定给定集合存在Frobenius数.如果不是这种情况(例如[2,4])，则不会有任何特定的行为.

It can be assumed that a Frobenius number exists for the given set. If this is not the case (e.g. for [2,4]) no particular behaviour is expected.

参考文献:

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

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

我决定接受GolfScript版本.虽然MATHEMATICA版本可能被认为是技术上正确的"，但显然可以从竞争中脱颖而出.话虽如此，其他解决方案也给我留下了深刻的印象，尤其是Ruby(对于通用语言而言，这是非常简短的).

I decided to accept the GolfScript version. While the MATHEMATICA version might be considered "technically correct", it would clearly take the fun out of the competition. That said, I'm also impressed by the other solutions, especially Ruby (which was very short for a general purpose language).

推荐答案

GolfScript 47/42个字符

更快的解决方案( 47 ).

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

慢速解决方案( 42 ).检查所有值，直到集合中每个数字的乘积...

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

~:+{*}*{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

这篇关于高尔夫代码:弗罗贝尼厄斯编号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！