six slices of pie

15 届 Perl 每周挑战赛的第一项任务是找到甜点系列中的最佳位置。

这是对创造马车鞭子或牛仔电影或实体书店或碳基能源的旧难题的重新阐述:何时是选择不断增加的不断减少的馅饼的最佳时机?

在这项任务中,馅饼足够大,可容纳100人,但第一个人在线上获得的切片仅相当于其中的1%。第二个人获得剩余的2%,第三个人获得剩余的3%,等等,直到第一百人获得100%的任何面包屑在前九十九个之后留下的分享。换句话说,我们“让苹果派再次伟大!”

实际任务是确定哪一个是该行中的最佳位置。早点进入并获得一小块仍然很大的馅饼是否更好?或者等待并最终获得更大的剩余部分?让我们以六种不同的方式回答这个问题。

1.势在必行的切片

我作为C程序员开始了我的开发人员职业生涯,我仍然觉得在命令式模式下处理像这样的小问题是很自然的。所以我第一次尝试回答这个问题(仁慈地,在Perl 6而不是在C中)看起来像这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Start with a full pie, and no idea who gets the most...
my $pie = 1.00; # i.e. 100%
my $max-share = 0.00; # i.e. 0%
my $max-index;

# For everyone in line...
for 1..100 -> $N {

# Take N% of what’s left as the next share...
my $share = $pie * $N/100;
$pie -= $share;

# Remember it if it’s maximal...
if $share > $max-share {
($max-index, $max-share) = ($N, $share);
}
}

# Report the biggest share taken...
say "$max-index => $max-share";

它不漂亮,不简洁,也不简单,但它很快,它产生了答案:

1
10 => 0.06281565095552947

换句话说,最佳位置是第十位,这可以保证你只占原始馅饼的6¼%。

但是这个解决方案存在一些问题……而不仅仅是明显的笨拙,冗长和太多的移动部件。更深层次的问题是它做出了一个重要的无根据的假设(一个恰好是正确的,尽管这不是我当时不知道的借口)。

让我们着手改进解决方案。

我做出的无根据的假设是队列中确实有一个可选的位置。但如果有两个同样好的地方呢?还是三个?还是一个高原,之后所有的地方都同样好?上面的代码实际上只告诉我们,第十名的人是第一个获得最大份额的人。如果有其他人怎么办?

它也是一个红旗,我们通过在循环中创建它时检查每个新共享来“手动”识别第一个最大值。 Perl 6具有完美的内置最大功能,可以为我们做到这一点。当然,我们真正需要的是一个max函数,它返回找到最大值的所有位置,而不仅仅是第一个。嗯… Perl 6也有:maxpairs

代码中的另一个红旗是需要添加记录代表百分比的各种数字的注释。 (例如1.00和$ N / 100)。应该有一种让代码本身变得明显的方法。

这是我对必要解决方案的第二次尝试,包含所有这些改进:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Add a percentage operator...
sub postfix:<%> (Numeric $x) { $x / 100 }

# Start with 100% of the pie, and no shares yet...
my $pie = 100%;
my %share;

# For everyone in line...
for 1..100 -> $N {
# Remove a share for the Nth person from the pie...
$pie -= ( %share{$N} = $pie * $N% );
}

# Finally, report the share(s) with maximal values...
say %share.maxpairs;

令人惊讶的是,Perl没有内置“百分比”运算符。好吧,也许它并不令人惊讶,因为它已经使用%符号作为前缀符号,中缀运算符,中缀正则表达式元运算符和无名静态变量。为该单个字符添加永久的第五个含义可能不会大大提高整体代码清晰度。

除此之外,这里确实如此。这就是为什么Perl 6使得简单地将其数字参数除以100的后缀%运算符变得非常简单:

1
sub postfix:<%> (Numeric $x) { $x / 100 }

所以现在我们可以写:

1
$pie = 100%

1
%share{$N} = $pie * $N%

无需评论就可以解释它们的百分比。

并且因为我们将每个计算的共享存储在哈希表中,我们可以使用内置的.maxpairs方法来检索具有最大值的%share的所有条目的列表。打印出该列表,我们发现它只包含一对:

1
(10 => 0.06281565095552947)

……从而确认排在第十位的人是唯一一个达到最佳馅饼的人。