什么是算法？

一个算法是一系列明确、精确、无歧义且可机械执行的简单指令，通常旨在完成特定任务。例如，以下是一个用于演唱那首令人讨厌的歌曲《墙上99瓶啤酒》的算法，适用于任意数值的99：

\underline{\text{Bottles of Beer}(n)} \\ \quad\quad\quad \text{For } i \leftarrow n \text{ down to } 1 \\ \quad\quad\quad\quad\quad \text{Sing } “i \text{ bottles of beer on the wall, } i \text{ bottles of beer,”} \\ \quad\quad\quad\quad\quad \text{Sing } “Take one down, pass it around, } i - 1 \text{ bottles of beer on the wall.” \\ \quad\quad\quad\quad\quad \text{Sing } “No bottles of beer on the wall, no bottles of beer,” \\ \quad\quad\quad\quad\quad \text{Sing } “Go to the store, buy some more, } n \text{ bottles of beer on the wall.”

1public class BottlesOfBeer {
2    public static void main(String[] args) {
3        bottlesOfBeer(99);
4    }
5    
6    public static void bottlesOfBeer(int n) {
7        for (int i = n; i >= 1; i--) {
8            System.out.println(i + " bottles of beer on the wall, " + i + " bottles of beer,");
9            System.out.println("Take one down, pass it around, " + (i-1) + " bottles of beer on the wall.\n");
10        }
11        
12        System.out.println("No bottles of beer on the wall, no bottles of beer.");
13        System.out.println("Go to the store, buy some more, " + n + " bottles of beer on the wall.");
14    }
15}

说明

• 第1行：这一行开始定义一个名为 BottlesOfBeer 的新类。该类将包含运行程序的 main 方法。
• 第3行：这一行调用 bottlesOfBeer 方法，并传入参数 99。
• 第7行：这一行开始一个 for 循环，从 n 递减到 1。int i = n 将循环变量 i 初始化为 n 的值。只要 i 大于等于 1，循环就会继续执行。i-- 在每次迭代后将 i 减 1。
• 第8–9行：这两行打印歌曲的歌词。

“算法”一词的词源

“算法”一词并非如某些古典学者所猜测的那样源自希腊语词根 arithmos（意为“数字”）和 algos（意为“痛苦”）。实际上，这个词是9世纪波斯学者穆罕默德·花拉子米（Muhammad ibn Musa al-Khwarizmi）名字的讹变。花拉子米最著名的著作是《代数学简明书》（Al-Kitab al-mukhtasar fıhısab al-ğabr wa’l-muqabala），现代术语“代数”即由此而来。在另一部著作中，他描述了现代十进制记数法——特别是使用一个小圆圈或 sifr（意为“空位”）来表示缺失的数量——这种记数法早在几个世纪前就在印度发展起来。他在这部著作中描述的方法（无论是用书写数字还是用算珠）在英语中被称为 algorism（或 augrym），其数字则被称为 ciphers（数码）。

尽管位置记数法和花拉子米的著作早已被部分欧洲学者知晓，但印度—阿拉伯数字系统是在中世纪意大利数学家兼商人莱昂纳多·皮萨诺（Leonardo of Pisa），即更广为人知的斐波那契（Fibonacci）推广下才在欧洲流行开来。得益于他于1202年撰写的《计算之书》（Liber Abaci），书写数字逐渐取代了当时称为算盘的计数板和手指计算，成为13世纪欧洲主流的计算方式——这并非因为书写十进制数字更容易学习或使用，而是因为它们提供了可追溯的计算过程。数码在西欧普及，直到活字印刷术出现；而真正广泛普及，则是在19世纪初廉价纸张变得充足之后。

最终，词“algorism”通过民间词源演变，融合了希腊语“arithmos”（数字）的概念，甚至可能受到此前提到的“algos”（痛苦）的影响，演变为现代的“algorithm”。因此，直到最近，“算法”一词都特指使用阿拉伯数字进行位置值算术的机械方法。那些熟练掌握这些程序快速可靠执行的人被称为 algorists（算法师）、computators（计算者），或更简单地称为 computers（计算机）。