我想到的是睿智和慷慨约翰D 'Errico作为一个计算机慈善家。在柯达(Kodak)做了很长时间的数字分析师后，他退休了，对外界可能是一种自满的冷漠。但约翰·迪里科不是那种人。他想贡献自己的时间，让其他人在计算事业中更加熟练。我们在MATLAB中心很幸运，有一个人的才华和动机作为常驻学者和教练。在和科迪玩了一段时间后，约翰给我们寄来了这张纸条，在他的允许下，我很高兴在这里发表。

跟在专家后面是很有趣的，因为即使是一个看似简单的问题，比如连续整数的和，也总是比你最初意识到的要复杂得多。总有一种你从未考虑过的解决问题的新方法。

谢谢你约翰!

内德。

关于科迪的一些想法

John D 'Errico

作为一个偶尔解决了几百个欧拉项目的求解者(其中只有一个是用MATLAB解决的，唯一一个是我手工完成的)，科迪引起了我的兴趣。我昨天和科迪待了一会儿。这是我的一些想法，也许你可以告诉我。

实际上，我主要关注的是一个问题，一个相当随意的问题。我选择189题看。问题是计算从1到2^n的整数之和。

很明显，简单的解，实际上，有人可能会说经典的MATLAB解很简单

Y = sum(1:2^n);

当然，这是快速计算，易于阅读，并且非常明显的代码的功能。这是我通常会选择的解，除非n很大。例如，如果n = 25会怎样?100年?在宇宙死于热死之前，上面的经典解将无法返回n=100的结果，因为2^100是一个如此巨大的数字，任何现代计算机都不会终止计算。简单地尝试生成一个长度为2^100的向量将超过我们所能想象的任何计算机的RAM。所以经典的解决方案失败了，对于SOME n。在我的机器上，我得到以下时间:

>时间>(@()和(1:2 ^ 5)ans = 1.2278 e-06 >时间>(@()和(1:2 ^ 10))ans = 4.911 e-06 >时间>(@()和(1:2 ^ 15))ans = 7.7062 e-05 >时间>(@()和(1:2 ^ 20))ans = 0.002765 >时间>(@()和(1:2 ^ 25))ans = 0.1736

正如你所看到的，当n开始变得足够大，使得向量变得非常大时，时间也变得非常重要，而且变化得很快。如果n=30，我就懒得试了。关键是经典的解决方案失败了，因为它使用的算法是O(2^n)。当然，受到这种指数增长影响的算法是有问题的。只要n不大于15-20，这个就没问题。但是指数运行时间很快就会撞上计算的墙。

解决办法可能是选择更仔细地观察问题。有没有一种数学方法可以减少所需的时间?显然，必要的和很容易计算，如果我们认识到对于任何正整数n，可以将集合[1:2^n]中的整数写成:

[1:2^(n-1)， 2^(n-1) + 1:2^(n-1)]

这仅仅反映了这些数的二进制展开。但是它也给了我们一种很好的递归方式来写期望的和。也就是说，我们可以把解写成:

Sum_int (n) = Sum_int (n-1) + (2^(n-1))²

所以一个更好的编码，至少对于纯非负整数n来说，可能是这样的:

对于非负整数输入x，计算整数的和为1:2^x，如果x == 0 %特殊情况下结束递归y = 1;Else y = 2*sum_int(x - 1) + 2^(2*x-2);结束

因此，我们可以看到上面写的sum_int实际上运行得更快，即使n小到5，而且时间似乎是n的线性。正如人们应该认识到的，sum_int确实是上面写的O(n)算法。

>> timeit(@() sum_int(5)) ans = 7.5692e-07 >> timeit(@() sum_int(10)) ans = 1.7227e-06 >> timeit(@() sum_int(15)) ans = 2.6715e-06 >> timeit(@() sum_int(20)) ans = 3.7462e-06 >> timeit(@() sum_int(25)) ans = 4.6515e-06 >> timeit(@() sum_int(100)) ans = 1.772e-05

事实上，甚至可以使用sum_int来计算sym输入的确切值。当然，sym会降低速度，但即使这样也只需要1/2秒的计算时间。

>> timeit(@() sum_int(sym(100)) ans = 0.54818 >> sum_int(sym(100)) ans = 803469022129495137770981046171215126561215611592144769253376 >> sum_int(sym(1000)) ans =57406534763712726211641660058884099201115885104434760023882136841288313069618515692832974315825313495922298231949373138672355948043152766571296567808332659269564994572656140000344389574120022435714463495031743122390807731823194181973658513020233176985452498279081199404472314802811655824768082110985171698215120385828833994926435042413009836474525915918251720110295164670516628746730606637774712420949241272862285974797636825655630482650144583914557794004353013244164891007287546556882572164179254268468766736029354798734808092593495610026430676423398598185956607671495251600324809039074511028408549376

一个有趣的问题是n是否应该是整数。当n不是整数时，代码是否会产生错误?或者它应该只产生任何非负浮点数的结果?我的观点是，错误检查是好代码的重要组成部分，就像在所有情况下指示代码行为的好的文档一样。所以当n等于2.5，或者pi，或者任何非整数时，sum_int就会失败。

其次，一些递归方案的一个严重问题是它们本身会受到指数增长的影响。例如，使用递归来计算第n个斐波那契数是一种典型的糟糕的解决问题的方法。一个简单的循环(因此O(n))足以计算相当小的斐波那契数，尽管对于巨大的n，有更好的方案来计算复杂度仅为O(log2(n))的斐波那契数。无论如何，可以使用for循环重写sum_int函数，尽管代码的递归性质并不是这个问题的真正问题。

对于非负整数输入x，计算整数的和为1:2^x y = 1;当k = 1时:x y = 2*y + 2^(2*k-2);结束

这种更简单的非递归代码与递归代码一样易于阅读，而且运行速度更快，因为它没有递归函数调用开销。但是，它不会为sym输入产生正确的结果。人们也可以通过一些努力来解决这个问题。

好吧，这样的讨论就到此为止了吗?当然不是。我们可以回到高斯的著名解，它承认了问题的自然对称性。因此，如果我们写出整数的和

0 1 2 2^n-2 2^n-1 2^n

然后我们可以把它们按不同的顺序相加来压缩和。

(0 + 2²)+(1 + 2²-1)+(2 + 2²-2)+…

所以，从0到k的整数和的著名公式(归因于高斯)可以写成

k * (k + 1) / 2

因此，我们可以编写这段代码的一个更简单的版本:

Sum_int3 = @(n) 2^n*(2^n+1)/2;

这是因为整数0:k的和与整数1:k的和相同。当然，它会产生正确的结果，而且相当快。同样，它也适用于支持必要算术运算的任何类型的输入。金宝app

>> sum_int3(sym(100)) ans = 803469022129495137770981046171215126561215611592144769253376 >> timeit(@() sum_int3(sym(100))) ans = 0.0031585

因此，任何对这个问题的深入讨论都应该解释这样的问题。我认为Cody的几乎所有问题都可以从这样的讨论中受益，在这里读者可以学习如何识别一个简单的算法，当它对某些输入很好时，可能仍然会对其他输入失败。

科迪是否应该为专家解决问题提供一些机制来解释这样的问题?我想这取决于你的决定，但我认为一个认真的学生可以从这样的讨论中学到很多东西。

总而言之，我意识到我的评论中的教训是相当经典的:

在编写代码时，最初的目标应该是找到一个至少可行的解决方案。首先让它工作起来。如果存在时间或内存等问题，只有在这种情况下才考虑优化代码。程序员(包括我)经常会花太多时间优化那些根本不需要优化的代码。

程序员时间通常比cpu时间更有价值。因此，避免对代码进行预先优化。

在寻找代码优化时，有许多方法可以解决任何问题。有时矢量化的解是正确的。有时，循环解决方案更好。有时寻求数学洞察力来找到一个完全不同的解决方案是正确的。

约翰