浅谈程序设计中的一些非常规算法^_^

我们在做题的时候肯定会遇到一些不知道该怎么解决的问题，也许是因为算法还不会，也许是因为会了但是算法不知道该怎么对应的使用。所以，也许可以用一种比较奇怪的方法来解决一些问题。当然，在平时的练习当中，我们要练的是各种各样的常规算法，以下的一些不太常规的方法只适用于的确实不知道该如何解决问题或者是特殊情况下，仅仅为了以这几种解法来说明程序设计中需要我们更多地运用我们的大脑来思考出属于我们自己的算法，以及用数学的一些建模的思想来辅助程序设计。

总之，勤于思考是最重要滴。

例一

TJU1010数素数

Problem

素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。

Input

本题有多组数据，每组数据由两个正整数M,N组成。（0＜M＜N＜1000000＝

Output

输出一个整数，表示介于M,N之间（包括M,N）的素数的数量。

记得上个星期四罗小松讲解这道题的时候采用了空间压缩的方式，以及建立素数表的方式。后者既然已经讲了这里就只作总结：在编程序设计的时候要多多利用计算机本身的功能。比如：编一个比较慢的程序计算出结果,然后寻找规律；建立表；用计算机自带的计算器辅助；甚至在忘记带草稿纸的情况下用记事本演算……

总之，要合理的利用计算机

而对于这道题，如果纯用“筛选法”求出m~n之间的素数，显然会超空间，而如果采用枚举法，时间又会不够。除了“空间压缩”这种方法之外，是否还有一个可以把这道题AC的方法呢。

首先我们考虑枚举法超时的原因：对于一个很大的数，比如100000，需要从2尝试到1000，而如果M与N相差很大，那么就会出现超时的情况。

其次我们再考虑筛选法，原因是数据限制到了1000000所以超出了空间限制。

第三，我们仔细思考，不难想到素数的特点：

除了1和本身之外没有其他的约数。

在这个定义上，我们可以发现，这里的约数有2种情况：1、合数；2、素数。而我们判断一个数n是否是素数，其实并不用用枚举法找出从2~round(sqrt(n))中是否存在一个数是它的约数，我们只需要判断的是,是否有质数可以整除它即可——原因是任何一个合数均能由2个或2个以上的素数相乘得到，而任何一个素数必定没有素因数。比如17，它就不能被某个除它本身以外的素数整除，那么它肯定不会被某个素数的倍数整除。

所以说，对于一个很大的数，判断它是否是素数，只需要用2~round(sqrt(n))之间的所有素数尝试即可。

于是，我们想到了先用速度较快的筛子法筛选出某一段的素数，其他数的判断便使用前面求得的素数去枚举尝试。

下面是完整的算法：

1、首先用筛子法筛选除1~10000以内的素数。

2、把素数用a[1]存2,a[2]存3……的方式保存在数组中。

3、对于输入的M，N，For I:=m to n判断每一个I。对于I，首先判断其与10000的关系，小于10000则直接通过已经得出了10000以内素数表判定，是素数则计数器+1。当I大于10000的情况，则从a数组依次调用素数尝试，直到a[k]>=round(sqrt(i))，是素数则计数器+1；

通过这样先求一小段素数，再用素数尝试素数的枚举与筛选结合的方法，就成功的结合了筛子与枚举对于这道题各自的长处。

通过这道题，我们不难总结出：只要肯于思考，总会有比较不常规但却有实用的算法出现的。

例二

TJU1016求N！左边第二位的数字

Problem

请求N！左边第二位的数字

Input

第一行为一整数M.表示M组测试数据，每组测试数据仅一个整数N.4<=N<=100000

Output

输出N! 左边第二个数字

   刚拿到这道题，会有一种无从下手的感觉。然后，我们也许会对N进行特殊赋值来找规律。记得当时刚做这到题的时候，花了两三节课的时间来找规律，最终也以失败告终。

    其实，PASCAL语言里的所定义的各种类型，在某种特殊情况下都可以发挥他们各自的作用。这道题初看之下显然不会用到REAL类型，因为题目明确表示N是一个整数，这就麻痹了我们的思路。

    其实，如果使用REAL类型进行纯模拟，左边的第2位始终是精确值，这样，定义N为实型，用模拟的方式计算N！很快就会得到一个第2位精确的非常大的数，这样再把得到的数转换为整型再求其第2位的值即可。

    （本算法由胡遥高手提供。）

    通过这道题，我们可以感受到的是，PASCAL的数据类型是有很大的功用滴。

思考：《古土的兴趣》的数据类型。

例三 TJU1076

Problem

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. 给你A, B和n, 你要算出f(n)的值.

Input

每一组数据包含3个整数A, B 和 n 在同一行上 (1 <= A, B <= 1000, 1 <= n <= 100,000,000). 三个0在一行表示输入结束.

Output

对于每组数据，打印出f（n）的值.

当拿到这道题的时候，首先想到的是递推，即是说当输入N值时，采用题目原本给好的递推公式来进行模拟。但是，请大家注意，N可以达到100，000，000，这的确是个“小”数目。由此观之，纯递推模拟的算法貌似不可行。

对数学比较有兴趣的人自然会想到f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7与我们见过的某个数列很像，没错，就是非波垃圾数列。众所周知，非波垃圾数列可以用那个什么特征根法推出其通项，但是那个通项比较恐怖，根号都有好几个。显然，这里的这个公式还有个MOD 7，显然此法不可用（为证明此方法不可用，某星曾请教著名的亚波老师，他说不是所有的递推都可以转通项滴，由此可以证明原结论）

如果以上两种方法都不行，那么这道题到底该怎么办呢。

其实，这个“MOD 7”既是本题的难点，又是本题的突破口。不难发现，这里的模运算得到的结果必定是0~6之间的一个整数。我们现在已经知道了f(1)与f(2)的值,而无论A与B为多少，f(n)必定是一个0~6之间的整数。那么，如果从0~6这7个数中取2个数来排列，其可能的方式有：A(7,2)=7*6=42种即是说，在f（43）之前，必定存在2个连续的项f(k)和f(k+1)分别等于f(1)和f(2),而一旦出现这种情况，则f(k+2)必定等于f(3)，由此下去，我们发现了这个奇怪的数列其实一点都不奇怪，就是一个典型的周期数列！那么，一切都明了了。我们只需要算出一个周期内各项的数，然后用要求的N项这个N除以周期T取余便很容易求得f(n)了。

从这道题中，我们得到的信息是，对于有些看起来很奇怪的题，如果能够联系到我们熟悉的东西，并比较得出其中的不同点，这些不同点也许便会成为我们的突破口。

在这短短的时间内，水平有限，不能为大家介绍什么算法，况且关于算法的文章在各类书籍以及网上都数不胜数，在这里仅仅是给大家浅显地介绍了一些关于程序设计中的思路。重要的是希望大家在掌握了书本上的算法后，或者是在拿到题不知如何下手的情况下能够开动大脑，想出一些匪夷所思甚至可以说是莫名其妙但能解决问题的算法。