趣味数学和C++

javasogo

浏览: 1817135 次
性别:
来自: 北京

最近访客更多访客>>

zzbing

u012363178

lyflyy

123456lllppp

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1649)

社区版块

存档分类

C C++C#编程算法

趣味数学和C++
撰文/Zeeshan Amjad 翻译/周翔
原文链接：http://www.codeproject.com/cpp/CPPMathFun.asp

引子

有些人认为自己已经厌倦了数学，因为人们需要灵活的大脑才能领会一些数学问题。但对于每个人来说，并不是数学的每个领域都是那么麻烦和令人厌倦的，即使对数学基础不好的人也是如此。数学的其中一个领域――数论，对数学学的不多的普通人来说，也许会有很大的吸引力。

数论是研究整数性质的一个学科，这也许是数学中的最古老的学科，它被具有“数学王子”之称的数学家高斯称为“数学中的女王”，因为很多数学领域都是为了解决数论上的问题而出现的。实际上，学习数论并不需要有专业的数学基础。你可能会对数学的各个领域都比较了解，如果那样的话，你会发现数论的精彩。数论被认为是“纯粹的数学”，因为在过去的日子里，人们无法将数论应用在除数学之外的其它领域。但是在现在的实际生活中，我们可以看到对数论的很多应用，比如密码的编解码、随机数产生器、错误检查、信息安全等领域，我们都可以看到数论的影子。直至今日，数论仍然是一门令人着迷的数学，因为在这个领域中有很多未解之迷等待着人们的解决。或许，即使随着数学理论研究的发展和相关技术的进步，人们也无法找到这些未解之迷的答案。

对数论的所有研究都是为了漂亮地证明各种数学问题，或者通过已知的基本定理解决更加复杂的问题。有意思的是，即使在数论上你未能证明一个命题是正确的，你仍然可以在实际生活中去应用它。举个例子，大家所熟知的RSA加密算法就是基于一个假设：如果一个数是两个以上的大素数的乘积，那么我们很难将这个大数分解。

详细内容

现在我们要用一个简单的方法来讨论数论。这是关于一个有趣的问题――克拉兹问题（Collatz problem）的一番讨论，在这其中我们会用到很多种编程技术。克拉兹问题的特殊之处在于――尽管我们很容易将这个问题讲清楚，但直到今天我们仍不能保证这个问题的算法对所有可能的输入都管用。这个问题也被叫做hailstone问题、3n+1问题、Hasse算法问题、Kakutani算法问题、Thwaites猜想或者Ulam问题。这个问题是由L. Collatz在1937年提出的。

一句话，这是一个非常简单的问题。取一个数（译者注：严格地说，这个数是正整数）作为输入，如果这个数是偶数，就将它除以2，否则就将它乘以3后再加1。（译者注：这是一个数列计算问题，用数学的语言就是，如果Xn是这个数列的第n项，而且Xn为偶数，那么这个数列的第n+1项Xn+1＝（Xn）/2，如果Xn为奇数，则Xn+1＝3（Xn）+1，其中n为不小于0的整数，数列的第一项X0可以取任意正整数）。这个猜想的命题是：无论你取哪一个（正整）数作为输入，然后求这个数列后面的项，总会有某些项等于1（译者注：确切的说无论取哪一个正整数，总能使这个数列达成1－4－2的循环，即数列中有一项等于1之后，下一项就是4，然后下一项是2，然后又是1、4、2、……。当然在本文中，作者并没有打算讨论那么多）。时至今日，仍然没有人能证明这个命题是正确的，尽管现在通过计算机，已经用大量的数据检查了这个命题，所有的这些数据都通过了这个命题的测试。而这个命题的证明对人们来说确实是一个挑战，而如果有人能证明这个问题，那么他无疑将会受到整个数学界的青睐。

如果将正整数n作为数列的第一个元素，那么这个数列的元素总能达到1，而数列中元素的个数就是这个数列的周期。比如你输入5的话，那么就有如下的序列：
516 8 4 2 1

那么这个数列的周期是6。这个序列被称为hailstone序列（或3n+1序列）。
用来产生这个数列的算法是非常简单的：

算法A (产生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. [得出序列中的下一个元素后] Go to A2.

很好，现在就开始实现这个算法吧。在这里，我尝试着用多种编程方式来实现这个算法，以便使整个过程显得有趣。

使用无结构编程的方法

这也许是在计算机上最基础的编程方法了，因为不需要定义过程（译者注：除了main之外）或是其它的什么东西。使用这种方式的问题是，在对代码的管理和重用方面会有所困难，因为用这种方法编出来的程序没有抽象层，因此如果使用这种方法来进行大规模编程会是十分困难的。

#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;
}

使用结构化编程的方法

将程序分为小的模块（函数），会使代码比无结构的程序代码更易于管理和重用。在逻辑上，程序中的一个函数会完成算法中的一部分工作，但这种单元划分可以有很强的主观性。这种编程方法可以将问题进行抽象分层，以便于将一个复杂的问题分为一些较小的部分，然后一一解决。

#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”，这不是很奇怪吗？这个名称的首字母就是这个名称本身的缩写，如果你将GNU这个名称展开，那么GNU这个词又会出现在展开后的名称中（比如：GNU's Not Unix 's Not Unix）。这只是递归的一个简单例子。换句话说，一个典型的定义是：递归是通过重复扩展自身的方法来描述一件事物的方法。对编程语言来说，递归就是一个函数调用它自己。使用递归的典型例子是求阶乘、求Fibonacci问题、汉诺（Hanoi）塔问题等等。

#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;
}

使用面向对象编程的方法

面向对象编程是一种编程方法，在这种方法中，你可以建立类并且建立这些类的实例，我们也可以称这些实例为“对象”。在技术上，“类”是在一个整体中定义变量和方法的原型。这个问题很小，你并不能通过这个问题看到面向对象编程所有的特点。下面这个程序并不是面向对象的，而是采用基于对象的技术。

#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）”就是“概括的”、“通用的”。在技术上，泛型编程的意思是，以一种方式来编写程序，在这种方式下编出来的程序可以对各种不同的独立的数据类型都能正常的运行。泛型程序应该对所有的数据类型都提供良好的支持，并能完成程序应该完成的功能。使用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++中最漂亮的编程技术。在这种方法中，你可以使用编译器来做原本应该由程序本身完成的工作。也可以这样说，它看起来像是根据程序来写程序。在模板元编程中，你可以将C++编译器当做解释器，比如，编译器可以将模板展开并生成程序运行时运行的二进制代码，这样，执行编译后程序的速度会非常快，因为一些数据已经在编译时由编译器计算出来。如果没有消耗资源的话就什么都算不出来，但这种方法可以消耗编译时的资源（通过编译器的计算能力）。编译时耗费的时间会有所增加，这取决于使用这种方法时所用算法的特性。

#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;
}

译者注：实际上，如果使用模板元编程的方法来解决问题的话，代码往往并不能通过编译，因为编译器会提示编译出错信息，比如上面的程序在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模板后的尖括号中可以看到这个序列中的所有元素：
221134175226134020105168421

而且，如果你把这一句
enum { count = CalculateCycle<N % 2 ? (N * 3 + 1) : (N / 2) >::count + 1;};
中第一个分号（；）改为逗号（，）的话，你会编译成功，运行编译后的可执行文件，从而得到这个序列的周期count：

Cycle length of 22 is = 16

模板元编程确实是一个漂亮的编程方法。但为什么我们可以从编译器得到本该由我们的代码算出的结果呢？大家可以参考《C++模板元编程》（机械工业出版社《软件研发》2004年2月号48页，荣耀著）一文。同时，模板元编程并不一定总是管用，如果你使用其他的编译器（比如Dev-C++），在编译出错信息中就有可能不会显示出运行结果。

（完，2005年8月2日稿）

分享到：