什么是算法？

一个算法是明确、精确、无歧义且可机械执行的基本指令序列，通常用于实现特定目的。例如，以下是一个适用于任意数值（而非仅限于99）的《墙上99瓶啤酒》歌曲演唱算法：

$\underline{Bottles\ of\ Beer(n)} \\ \space\space\space\space For\space i ←n\space down\space to\space 1\\ \hspace{1cm} Sing\space “i\space bottles\space of\space beer\space on\space the\space wall,\space i\space bottles\space of\space beer,” \\ \hspace{1cm} Sing\space “Take\space one\space down,\space pass\space it\space around,\space i − 1\space bottles\space of\space beer\space on\space the\space wall.” \\ \hspace{0.35cm} Sing\space “No\space bottles\space of\space beer\space on\space the\space wall,\space no\space bottles\space of\space beer,” \\ \hspace{0.35cm} Sing\space “Go\space to\space the\space store,\space buy\space some\space more,\space n\space bottles\space of\space beer\space on\space the\space wall.”$

1#include <iostream>
2using namespace std;
3
4void BottlesofBeer(int n)
5{
6	for (int i = n; i >= 1; i--)
7	{
8		cout << i << " bottles of beer on the wall, " << i << " bottles of beer," << endl;
9		cout << "Take one down, pass it around, " << i - 1 << " bottles of beer on the wall." << endl;
10		cout << endl;
11	}
12
13	cout << "No bottles of beer on the wall, no bottles of beer." << endl;
14	cout << "Go to the store, buy some more, " << n << " bottles of beer on the wall." << endl;
15}
16
17int main()
18{
19	BottlesofBeer(99);	// 从99瓶开始
20	return 0;
21}

说明

• 第4行： 定义函数 BottlesofBeer，接收一个整型参数 n。
• 第6行： 开始一个循环，从 n 递减至 1，i 为循环变量。
• 第8–10行： 输出当前 i 值对应的歌词内容，每段之间换行。
• 第13–14行： 输出歌曲最后两句，表示已无剩余酒瓶，并建议去商店购买更多。

“算法”一词的词源

“算法”（algorithm）一词并非如许多人猜测的那样，源自希腊语中表示“数”的 arithmos（$\acute{\alpha} \varrho \iota \theta \mu \acute{o}\varsigma$）和表示“痛苦”的 algos（$\overset{,}{\acute{\alpha}} \lambda \gamma o\varsigma$）。实际上，它是9世纪波斯学者穆罕默德·伊本·穆萨·花剌子米（Muhammad ibn Musa al-Khwarizmi）名字的拉丁化变体。花剌子米最著名的著作是《代数学》（Al-Kitab al-mukhtasar fi hisab al-ğabr wa’l-muqabala），现代英文单词“algebra”（代数）即由此而来。

在另一部著作中，花剌子米描述了当时已在印度发展数个世纪的十进制记数系统，特别是使用一个小圆圈或 $\underset{\cdot}{s}ifr$ 来表示空位的方法。这些方法通过书面数字或计算石进行运算，在英语中被称为 algorism 或 augrym，而其中的数字则被称为 ciphers（数码）。

尽管位值制记数法和花剌子米的著作早已被部分欧洲学者所知，但真正将“印度-阿拉伯”数字系统在欧洲推广开来的，是中世纪意大利数学家兼商人比萨的列奥纳多（Leonardo of Pisa），也就是更为人熟知的斐波那契（Fibonacci）。由于他在1202年出版的《算经》（Liber Abaci）的影响，书写数字逐渐取代了传统的计数板（即当时的“abacus”，算盘），手指计算成为13世纪欧洲主流的计算方式。这并不是因为十进制书写更易于学习或使用，而是因为它能留下可追溯的计算记录。

直到活字印刷术出现后，ciphers 才在西欧广泛普及；而其真正变得无处不在，则是在19世纪初廉价纸张大量供应之后。

最终，algorism 一词通过民间词源学的影响，结合希腊语 arithmos（数），并可能受到前述 algos（痛苦）一词的联想影响，演变为现代的 algorithm。因此，直到不久之前，“算法”一词专指使用阿拉伯数字进行位值算术的机械化技术。那些受过训练、能够快速准确执行这些操作的人，被称为 algorists 或 computators，更简单地说，就是 computers（计算机——原意为人）。