引子
有些人認為自己已經(jīng)厭倦了數學(xué)，因為人們需要靈活的大腦才能領(lǐng)會(huì )一些數學(xué)問(wèn)題。但對于每個(gè)人來(lái)說(shuō)，并不是數學(xué)的每個(gè)領(lǐng)域都是那么麻煩和令人厭倦的，即使對數學(xué)基礎不好的人也是如此。數學(xué)的其中一個(gè)領(lǐng)域――數論，對數學(xué)學(xué)的不多的普通人來(lái)說(shuō)，也許會(huì )有很大的吸引力。
數論是研究整數性質(zhì)的一個(gè)學(xué)科，這也許是數學(xué)中的最古老的學(xué)科，它被具有“數學(xué)王子”之稱(chēng)的數學(xué)家高斯稱(chēng)為“數學(xué)中的女王”，因為很多數學(xué)領(lǐng)域都是為了解決數論上的問(wèn)題而出現的。實(shí)際上，學(xué)習數論并不需要有專(zhuān)業(yè)的數學(xué)基礎。你可能會(huì )對數學(xué)的各個(gè)領(lǐng)域都比較了解，如果那樣的話(huà)，你會(huì )發(fā)現數論的精彩。數論被認為是“純粹的數學(xué)”，因為在過(guò)去的日子里，人們無(wú)法將數論應用在除數學(xué)之外的其它領(lǐng)域。但是在現在的實(shí)際生活中，我們可以看到對數論的很多應用，比如密碼的編解碼、隨機數產(chǎn)生器、錯誤檢查、信息安全等領(lǐng)域，我們都可以看到數論的影子。直至今日，數論仍然是一門(mén)令人著(zhù)迷的數學(xué)，因為在這個(gè)領(lǐng)域中有很多未解之迷等待著(zhù)人們的解決?；蛟S，即使隨著(zhù)數學(xué)理論研究的發(fā)展和相關(guān)技術(shù)的進(jìn)步，人們也無(wú)法找到這些未解之迷的答案。
對數論的所有研究都是為了漂亮地證明各種數學(xué)問(wèn)題，或者通過(guò)已知的基本定理解決更加復雜的問(wèn)題。有意思的是，即使在數論上你未能證明一個(gè)命題是正確的，你仍然可以在實(shí)際生活中去應用它。舉個(gè)例子，大家所熟知的RSA加密算法就是基于一個(gè)假設：如果一個(gè)數是兩個(gè)以上的大素數的乘積，那么我們很難將這個(gè)大數分解。
詳細內容
現在我們要用一個(gè)簡(jiǎn)單的方法來(lái)討論數論。這是關(guān)于一個(gè)有趣的問(wèn)題――克拉茲問(wèn)題（Collatz problem）的一番討論，在這其中我們會(huì )用到很多種編程技術(shù)?？死潌?wèn)題的特殊之處在于――盡管我們很容易將這個(gè)問(wèn)題講清楚，但直到今天我們仍不能保證這個(gè)問(wèn)題的算法對所有可能的輸入都管用。這個(gè)問(wèn)題也被叫做hailstone問(wèn)題、3n+1問(wèn)題、Hasse算法問(wèn)題、Kakutani算法問(wèn)題、Thwaites猜想或者Ulam問(wèn)題。這個(gè)問(wèn)題是由L. Collatz在1937年提出的。
一句話(huà)，這是一個(gè)非常簡(jiǎn)單的問(wèn)題。取一個(gè)數（譯者注：嚴格地說(shuō)，這個(gè)數是正整數）作為輸入，如果這個(gè)數是偶數，就將它除以2，否則就將它乘以3后再加1。（譯者注：這是一個(gè)數列計算問(wèn)題，用數學(xué)的語(yǔ)言就是，如果Xn是這個(gè)數列的第n項，而且Xn為偶數，那么這個(gè)數列的第n+1項Xn+1＝（Xn）/2，如果Xn為奇數，則Xn+1＝3（Xn）+1，其中n為不小于0的整數，數列的第一項X0可以取任意正整數）。這個(gè)猜想的命題是：無(wú)論你取哪一個(gè)（正整）數作為輸入，然后求這個(gè)數列后面的項，總會(huì )有某些項等于1（譯者注：確切的說(shuō)無(wú)論取哪一個(gè)正整數，總能使這個(gè)數列達成1－4－2的循環(huán)，即數列中有一項等于1之后，下一項就是4，然后下一項是2，然后又是1、4、2、……。當然在本文中，作者并沒(méi)有打算討論那么多）。時(shí)至今日，仍然沒(méi)有人能證明這個(gè)命題是正確的，盡管現在通過(guò)計算機，已經(jīng)用大量的數據檢查了這個(gè)命題，所有的這些數據都通過(guò)了這個(gè)命題的測試。而這個(gè)命題的證明對人們來(lái)說(shuō)確實(shí)是一個(gè)挑戰，而如果有人能證明這個(gè)問(wèn)題，那么他無(wú)疑將會(huì )受到整個(gè)數學(xué)界的青睞。
如果將正整數n作為數列的第一個(gè)元素，那么這個(gè)數列的元素總能達到1，而數列中元素的個(gè)數就是這個(gè)數列的周期。比如你輸入5的話(huà)，那么就有如下的序列：
5 16 8 4 2 1
那么這個(gè)數列的周期是6。這個(gè)序列被稱(chēng)為hailstone序列（或3n+1序列）。
用來(lái)產(chǎn)生這個(gè)數列的算法是非常簡(jiǎn)單的：
算法A (產(chǎn)生3n+1序列的算法)
A1. [輸入n]
A2. [算法結束條件] If n = 1 then exit
A3. [檢查n] If n is even then n := n / 2 else n := n * 3 + 1
A4. [得出序列中的下一個(gè)元素后] Go to A2.
很好，現在就開(kāi)始實(shí)現這個(gè)算法吧。在這里，我嘗試著(zhù)用多種編程方式來(lái)實(shí)現這個(gè)算法，以便使整個(gè)過(guò)程顯得有趣。
使用無(wú)結構編程的方法
這也許是在計算機上最基礎的編程方法了，因為不需要定義過(guò)程（譯者注：除了main之外）或是其它的什么東西。使用這種方式的問(wèn)題是，在對代碼的管理和重用方面會(huì )有所困難，因為用這種方法編出來(lái)的程序沒(méi)有抽象層，因此如果使用這種方法來(lái)進(jìn)行大規模編程會(huì )是十分困難的。
#include <iostream>
using std::cout;
using std::endl;
int main(int argc, char* argv[])
{
int iCount = 1;
int iNo = 22;
int iTemp = iNo;
while (iTemp != 1)
{
// 如果是偶數
if (iTemp % 2 == 0)
{
iTemp /= 2;
}
// 如果是奇數
else
{
iTemp = iTemp * 3 + 1;
}
++iCount;
}
cout << "Cycle length of " << iNo << " is " << iCount << endl;
return 0;
}
使用結構化編程的方法
將程序分為小的模塊（函數），會(huì )使代碼比無(wú)結構的程序代碼更易于管理和重用。在邏輯上，程序中的一個(gè)函數會(huì )完成算法中的一部分工作，但這種單元劃分可以有很強的主觀(guān)性。這種編程方法可以將問(wèn)題進(jìn)行抽象分層，以便于將一個(gè)復雜的問(wèn)題分為一些較小的部分，然后一一解決。
#include <iostream>
using std::cout;
using std::endl;
int NextTerm(int iNo)
{
// 如果是偶數
if (iNo % 2 == 0)
{
iNo /= 2;
}
// 如果是奇數
else
{
iNo = iNo * 3 + 1;
}
return iNo;
}
int CalculateCycle(int iNo)
{
int iCount = 1;
while (iNo != 1)
{
iNo = NextTerm(iNo);
++iCount;
}
return iCount;
}
int main(int argc, char* argv[])
{
const int iNo = 22;
cout << "Cycle length of " << iNo << " is " << CalculateCycle(iNo) << endl;
return 0;
}
使用遞歸的方法
你知道什么是GNU嗎？GNU就是“GNU‘s Not Unix”，這不是很奇怪嗎？這個(gè)名稱(chēng)的首字母就是這個(gè)名稱(chēng)本身的縮寫(xiě)，如果你將GNU這個(gè)名稱(chēng)展開(kāi)，那么GNU這個(gè)詞又會(huì )出現在展開(kāi)后的名稱(chēng)中（比如：GNU‘s Not Unix ‘s Not Unix）。這只是遞歸的一個(gè)簡(jiǎn)單例子。換句話(huà)說(shuō)，一個(gè)典型的定義是：遞歸是通過(guò)重復擴展自身的方法來(lái)描述一件事物的方法。對編程語(yǔ)言來(lái)說(shuō)，遞歸就是一個(gè)函數調用它自己。使用遞歸的典型例子是求階乘、求Fibonacci問(wèn)題、漢諾（Hanoi）塔問(wèn)題等等。
#include <iostream>
using std::cout;
using std::endl;
int CalculateCycle(int iNo, int iCount)
{
++iCount;
if (iNo == 1)
{
return iCount;
}
else
{
if (iNo % 2 == 0)
{
iNo /= 2;
iCount = CalculateCycle(iNo, iCount);
}
else
{
iNo = iNo * 3+ 1;
iCount = CalculateCycle(iNo, iCount);
}
}
return iCount;
}
int main(int argc, char* argv[])
{
const int iNo = 22;
cout << "Cycle length of " << iNo << " is = "
<< CalculateCycle(iNo, 0) << endl;
return 0;
}
使用面向對象編程的方法
面向對象編程是一種編程方法，在這種方法中，你可以建立類(lèi)并且建立這些類(lèi)的實(shí)例，我們也可以稱(chēng)這些實(shí)例為“對象”。在技術(shù)上，“類(lèi)”是在一個(gè)整體中定義變量和方法的原型。這個(gè)問(wèn)題很小，你并不能通過(guò)這個(gè)問(wèn)題看到面向對象編程所有的特點(diǎn)。下面這個(gè)程序并不是面向對象的，而是采用基于對象的技術(shù)。
#include <iostream>
using std::cout;
using std::endl;
class Collatz
{
private:
int m_iCycle;
int m_iNo;
int NextTerm(int p_iNo);
public:
Collatz(int p_iNo = 0);
void CalculateCycle();
int GetCycle() const;
};
Collatz::Collatz(int p_iNo) : m_iNo(p_iNo), m_iCycle(1)
{
if (m_iNo < 1)
throw std::out_of_range("No should be greater than 0");
}
int Collatz::NextTerm(int p_iNo)
{
// 如果是偶數
if (p_iNo % 2 == 0)
{
p_iNo /= 2;
}
// 如果是奇數
else
{
p_iNo = p_iNo * 3 + 1;
}
return p_iNo;
}
void Collatz::CalculateCycle()
{
while (m_iNo != 1)
{
m_iNo = NextTerm(m_iNo);
++m_iCycle;
}
}
int Collatz::GetCycle() const
{
return m_iCycle;
}
int main(int argc, char* argv[])
{
const int iNo = 22;
try
{
Collatz objCollatz(iNo);
objCollatz.CalculateCycle();
cout << "Cycle length of " << iNo << " is "
<< objCollatz.GetCycle() << endl;
}
catch(std::out_of_range& ex)
{
cout << ex.what() << endl;
}
return 0;
}
使用泛型編程的方法
“泛型的（Generic）”就是“概括的”、“通用的”。在技術(shù)上，泛型編程的意思是，以一種方式來(lái)編寫(xiě)程序，在這種方式下編出來(lái)的程序可以對各種不同的獨立的數據類(lèi)型都能正常的運行。泛型程序應該對所有的數據類(lèi)型都提供良好的支持，并能完成程序應該完成的功能。使用C++模板是一種泛型編程的途徑。
#include <iostream>
using std::cout;
using std::endl;
template <typename T>
class Collatz
{
private:
T m_iCycle;
T m_iNo;
int NextTerm(T p_iNo);
public:
Collatz(T p_iNo = 0);
void CalculateCycle();
T GetCycle() const;
};
template <typename T>
Collatz<T>::Collatz(T p_iNo) : m_iNo(p_iNo), m_iCycle(1)
{
if (m_iNo < 1)
throw std::out_of_range("No should be greater than 0");
}
template <typename T>
int Collatz<T>::NextTerm(T p_iNo)
{
// 如果是偶數
if (p_iNo % 2 == 0)
{
p_iNo /= 2;
}
// 如果是奇數
else
{
p_iNo = p_iNo * 3 + 1;
}
return p_iNo;
}
template <typename T>
void Collatz<T>::CalculateCycle()
{
while (m_iNo != 1)
{
m_iNo = NextTerm(m_iNo);
++m_iCycle;
}
}
template <typename T>
T Collatz<T>::GetCycle() const
{
return m_iCycle;
}
int main(int argc, char* argv[])
{
const int iNo = 22;
try
{
Collatz<int> objCollatz(iNo);
objCollatz.CalculateCycle();
cout << "Cycle length of " << iNo << " is " << objCollatz.GetCycle() << endl;
}
catch(std::out_of_range& ex)
{
cout << ex.what() << endl;
}
return 0;
}
使用模板元編程的方法
模板元編程（Template Meta Programming）是C++中最漂亮的編程技術(shù)。在這種方法中，你可以使用編譯器來(lái)做原本應該由程序本身完成的工作。也可以這樣說(shuō)，它看起來(lái)像是根據程序來(lái)寫(xiě)程序。在模板元編程中，你可以將C++編譯器當做解釋器，比如，編譯器可以將模板展開(kāi)并生成程序運行時(shí)運行的二進(jìn)制代碼，這樣，執行編譯后程序的速度會(huì )非?？?，因為一些數據已經(jīng)在編譯時(shí)由編譯器計算出來(lái)。如果沒(méi)有消耗資源的話(huà)就什么都算不出來(lái)，但這種方法可以消耗編譯時(shí)的資源（通過(guò)編譯器的計算能力）。編譯時(shí)耗費的時(shí)間會(huì )有所增加，這取決于使用這種方法時(shí)所用算法的特性。
#include <iostream>
using std::cout;
using std::endl;
template<int N>
class CalculateCycle
{
public:
enum { count = CalculateCycle<N % 2 ? (N * 3 + 1) : (N / 2) >::count + 1;};
};
template <>
class CalculateCycle<1>
{
public:
enum { count = 1 };
};
int main(int argc, char* argv[])
{
const int iNo = 22;
cout << "Cycle length of " << iNo << " is = "
<< CalculateCycle<iNo>::count << endl;
return 0;
}
譯者注：實(shí)際上，如果使用模板元編程的方法來(lái)解決問(wèn)題的話(huà)，代碼往往并不能通過(guò)編譯，因為編譯器會(huì )提示編譯出錯信息，比如上面的程序在Visual C++中的編譯出錯信息是：
--------------------Configuration: tmp_1 - Win32 Debug--------------------
Compiling...
tmp_1.cpp
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : error C2760: syntax error : expected ‘,‘ not ‘;‘
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<2>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<4>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<8>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<16>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<5>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<10>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<20>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<40>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<13>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<26>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<52>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<17>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<34>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(9) : see reference to class template instantiation ‘CalculateCycle<11>‘ being compiled
H:\Documents and Settings\seafrog\桌面\tmp\tmp_1.cpp(23) : see reference to class template instantiation ‘CalculateCycle<22>‘ being compiled
……
這就是模板元編程的運行結果，我們在CalculateCycle模板后的尖括號中可以看到這個(gè)序列中的所有元素：
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
而且，如果你把這一句
enum { count = CalculateCycle<N % 2 ? (N * 3 + 1) : (N / 2) >::count + 1;};
中第一個(gè)分號（；）改為逗號（，）的話(huà)，你會(huì )編譯成功，運行編譯后的可執行文件，從而得到這個(gè)序列的周期count：
Cycle length of 22 is = 16
模板元編程確實(shí)是一個(gè)漂亮的編程方法。但為什么我們可以從編譯器得到本該由我們的代碼算出的結果呢？大家可以參考《C++模板元編程》（機械工業(yè)出版社《軟件研發(fā)》2004年2月號48頁(yè)，榮耀著(zhù)）一文。同時(shí)，模板元編程并不一定總是管用，如果你使用其他的編譯器（比如Dev-C++），在編譯出錯信息中就有可能不會(huì )顯示出運行結果。
（完，2005年8月2日稿）
