妙用数学原理巧解编程趣题
有这样一道有趣的题目：有编号为1--100的灯初始状态是全开着的，现进行如下操作：
A 编号是1的倍数灯拨一下开关，（开--关算一次拨操作；关--开算一次拨操作）；
B 是2的倍数灯再拨一下开关；
C 是3的倍数的灯再拨一下开关；
。。。。。。
如此直到100的倍数。
问：此时有哪些编号的灯是熄灭的？累积熄灭的灯的个数，并输出其编号。
初看此题并不难，思路很快出来：创建一个整型数组用来存储所有灯的状态，设初值为0，表示灯初始状态是全开着的。遍历数组，从1到100对每个编号进行倍数判断操作，对满足条件的灯进行一次拨操作。最后判断有哪些编号的灯是熄灭的，即判断数组中哪些元素的值为1。
具体代码如下：
例程1：
#include <iostream>
using namespace std;
int Shift(int light); //执行一次拨操作
int main()
{
const int N = 100;//灯的总数
int a[N] = {0}; //整型数组用来存储所有灯的状态，设初值为0，表示灯是全开着的
for (int i=0; i<N; i++)//遍历数组
for (int j=i+1; j>0; j--) //穷举所有不大于当前编号的数
{
if ((i+1)%j == 0) //如果j是当前编号i+1的约数，即i+1是j的倍数，则执行一次拨操作
a[i] = Shift(a[i]);//也可用a[i] = (a[i] == 0)? 1 : 0; 实现
}
int sum = 0; //用来累计熄灭的灯的个数
cout << "熄灭的灯的编号:" << endl;
for (int i=0; i<N; i++)//累积熄灭的灯的个数，并输出其编号
{
if (a[i] == 1)
{
cout << i+1 << "\t";
sum++;
}
}
cout << "熄灭的灯的个数是: " << sum << endl;
getchar();
return 0;
}
int Shift(int light)
{
if (light == 0)
return 1;
else
return 0;
}
代码是正确的，程序也可以正常编译运行并得到正确的结果，但每次进行倍数判断操作，对满足条件的灯进行一次拨操作时，都要调用一次Shift(int light)函数（也可用a[i] = (a[i] == 0)? 1 : 0; 实现），使得运行速度变慢，也增加了代码行数。观察拨操作的执行情况，发现对于一盏灯而言，若拨操作次数为奇数，则其最后的状态是熄灭的，否则是亮着的（因为灯的初试状态是亮着的）。所以不必每次都执行一次拨操作，而只要累计每一盏灯的拨操作次数，最后判断总的拨操作次数的奇偶性，就可以判断该盏灯的状态。
修改后的代码如下：
例程2：
#include <iostream>
using namespace std;
int main()
{
const int N = 100;//灯的总数
int a[N] = {0}; //整型数组用来存储所有灯的状态，设初值为0，表示灯是全开着的
for (int i=0; i<N; i++)//遍历数组
for (int j=i+1; j>0; j--) //穷举所有不大于当前编号的数
{
if ((i+1)%j == 0) //如果j是当前编号i+1的约数，即i+1是j的倍数
a[i] ++; //累计该盏灯的拨操作次数
}
int sum = 0; //用来累计熄灭的灯的个数
cout << "熄灭的灯的编号:" << endl;
for (int i=0; i<N; i++)//累积熄灭的灯的个数，并输出其编号
{
if (a[i] % 2 == 1)//如果总的拨操作次数为奇数，表示该盏灯处于熄灭状态
{
cout << i+1 << "\t";
sum++;
}
}
cout << "熄灭的灯的个数是: " << sum << endl;
getchar();
return 0;
}
这样是比原来有所进步了，但仍然处于对题目的表象认识上，没有分析它的数学意义。仔细分析，不难发觉：如果编号为i的灯的总拨操作次数为奇数，即表示i有奇数个约数。这样要求熄灭的灯（即总拨操作次数为奇数的灯）的编号，就是求有奇数个约数的编号的灯。所以可以进一步改进程序，既不用创建数组，也不用判断每盏灯的总拨操作次数，只要判断该盏灯的编号是否有奇数个约数就可以了。
修改后的代码如下：
例程3：
#include <iostream>
using namespace std;
int main()
{
const int N = 100;//灯的总数
int sum = 0; //用来累计熄灭的灯的个数
cout << "熄灭的灯的编号:" << endl;
for (int i=1; i<=N; i++)//累积熄灭的灯的个数，并输出其编号
{
int count = 0; //用来累计编号的约数的个数
for (int j=1; j<=i; j++) //穷举所有不大于当前编号的数
{
if (i%j == 0)
count++; //累计编号的约数的个数
}
if (count % 2 == 1)//如果该盏灯的编号有奇数个约数，表示该盏灯处于熄灭状态
{
cout << i << "\t";
sum++;
}
}
cout << "熄灭的灯的个数是: " << sum << endl;
getchar();
return 0;
}
这样看起来已经够好了，速度也比前面的程序要快的多（特别是在灯的数量比较大的时候），但如果进一步观察，就会发现具有奇数个约数的数具有以下特点：
假设判断一个数 p 的约数个数，先将p分解为如下形式: p=n *（ b1 ^ t1 * b2 ^ t2....）
则p的约数个数为 (t1+1)*(t2+1)*....*(tn+1)，这就要求所有的 ti 必须是偶数。如此看来，当且仅当 p是个完全平方数的时候，p的约数个数才会是奇数个。
所以要求熄灭的灯（即总拨操作次数为奇数的灯）的编号，就是求有奇数个约数的编号的灯。要判断该盏灯的编号是否有奇数个约数，只要判断该编号是否为完全平方数就可以了。
判断一个数是否为完全平方数有两种方法，一种不用调用库函数中的sqrt()函数，但速度稍慢，一种需要调用库函数中的sqrt()函数，但速度较快。
两种方法的代码分别如下：
1。不用调用库函数中的sqrt()函数
例程4：
#include <iostream>
using namespace std;
int main()
{
const int N = 100;//灯的总数
int sum = 0; //用来累计熄灭的灯的个数
cout << "熄灭的灯的编号:" << endl;
for (int i=1; i<=N; i++)//累积熄灭的灯的个数，并输出其编号
{
for (int j=1; j<=i; j++) //穷举所有不大于当前编号的数
{
if (j*j == i)//如果该盏灯的编号为完全平方数，则有奇数个约数，表示该盏灯处于熄灭状态
{
cout << i << "\t";
sum++;
break;
}
}
}
cout << "熄灭的灯的个数是: " << sum << endl;
getchar();
return 0;
}
2。需要调用库函数中的sqrt()函数
例程5：
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
const int N = 100;//灯的总数
int sum = 0; //用来累计熄灭的灯的个数
cout << "熄灭的灯的编号:" << endl;
for (int i=1; i<=N; i++)//累积熄灭的灯的个数，并输出其编号
{
if (sqrt(i)*sqrt(i) == i)//如果该盏灯的编号为完全平方数，则有奇数个约数，表示该盏灯处于熄灭状态
{
cout << i << "\t";
sum++;
}
}
cout << "熄灭的灯的个数是: " << sum << endl;
getchar();
return 0;
}
从例程1到例程5，代码越来越短，速度越来越快，充分说明了对实际问题进行数学抽象，分析其数学本质，可以大大增进程序的效率。希望各位编程爱好者在面对一个编程问题的时候不要刚看到问题的表象，就匆匆作答，急于编写代码；应该先运用数学工具进行数学抽象和建模，寻找适当的数据结构和算法，高效率地编程。只有这样才能提高自己的数学水平和编程能力。
评论