搜索
法雷序列实习报告【前言】法雷序列是非常经典的序列，他有很多有趣的性质，因此在做法雷序列的时候，完全不要通过分数的排序就能够实现，且效率有很大的提高，而其性质又如此之多，以至于利用不同的性质能得到很多不同的算法，下面就将会简单比较一下几种不同的做法，并对各自性能稍作分析。【总体设计】一般总的程序应该分为读入和序列的计算和序列的输出三部分。但是如果序列的输出单独执行的话，需要保存在整个序列，对于较小的n的量级尚能胜任，但当n增大之后，空间将明显的不足，所以我在设计算法的时候，决定合并序列计算和输出这两个部分，边计算边输出，节省内存空间，下面介绍的主体算法都是直接或者优化成这种方法实现的。【主体算法设计】我想数据的输入就不用多说了，下面就落实到就给定一个数n，如何得出其法雷序列。先介绍方法一：法雷序列有个比较明显，基本上也是众所周知的性质，对于法雷序列中的任意三个连续的分数，设为p1/q1,p2/q2,p3/q3,应该有性质:p2/q2=(p1+p3)/(q1+q2)，其中p2,q2可能是经过约分得到的。如此我们希望通过已知的前两个数，直接能得到第三个数，然后依次类推，推出所有的数。实际上也是可以的，虽然从表面上看，知道p1,q1,p2,q2之后,p3,q3有多种情况，如(p2-p1)/(q2-q1),(p2*2-p1)/(q2*2-q1)…但是我们只需选择最小的一个，容易证明最小的p3/q3应该为(p2*x-p1)/(q2*x-q1)，其中x=max{k∣q2*k-q1≤n}，这点容易证明。而且此时(p2*x-p1)/(q2*x-q1)已经不能约分了，这点也好证明，这里就不赘述了。简要算法如下：int__a,__b,_a,_b,a,b,x;//__a,__b表示第一个分数的分母和分子；_a,_b表示第二个分数的分母和分子；//a,b当前要算分数分子分母//x第二个分数分子分母放大的倍数__a=0;__b=1;//整个序列第一个分数0/1cout__a/__b;_a=1;_b=n;//整个序列第二个分数1/ncout_a/_b;while(_b!=1)//若1/1已生成，则跳出循环{//根据前两个分数，算出下一个分数x=(__b+n)/_b;//!此处用到整除，算法效率的关键a=x*_a-__a;b=x*_b-__b;couta/b;//递推，滚动存储，准备继续计算下一个分数__a=_a;__b=_b;_a=a;_b=b;}如上所示，此算法实在是再简单不过了，边计算边输出，同时空间耗费基本上为0，而且复杂度为最低的量级了。不过上面用到了整除运算，对算法效率有一定的影响，但此算法已不好再优化了。方法二：法雷序列有另外一种构造方式：先在序列中放入头和尾两个分数，0/1,1/1,然后不断在此序列的基础上插入新的元素，元素插法为如果存在相邻两分数p1/q1,p2/q2，满足q1+q2≤n,则在p1/q1，p2/q2之间插入(p1+p2)/(q1+q2)，如此直到不能插入为止。具体插入过程如下简要描述：structListNode{intdeno,nume;//deno,nume分别表示分母，分子ListNode*link;};设链表中已插入0/1,1/1,链表头first指向0/1所在节点。ListNode*p=first;while(p-link!=NULL){if(p-deno+p-link-deno=n)//如果ｐ接点后能插入新的分数，则插入{ListNode*q=newListNode;q-deno=p-deno+p-link-deno;q-nume=p-nume+p-link-nume;q-link=p-link;p-link=q;}else//若不能，则指针向后移动，判断后面的位置是否还能插入新的分数p=p-link;}如上所述即可求出所有分数组成的链表，最后输出就可以了，但是如果数据过多，则有存不下的危险，而实际在插入过程中，上面的ｐ指针一旦往后移动了，前面链表中的内容对后面的计算毫无作用，这是我们可以输出前面分数，并释放前面链表的空间，于是可以改为：structListNode{intdeno,nume;//deno,nume分别表示分母，分子ListNode*link;};设链表中已插入0/1,1/1,链表头first指向0/1所在节点。ListNode*p=first;while(p-link!=NULL){if(p-deno+p-link-deno=n)//如果ｐ接点后能插入新的分数，则插入{ListNode*q=newListNode;q-deno=p-deno+p-link-deno;q-nume=p-nume+p-link-nume;q-link=p-link;p-link=q;}else//若不能，则指针向后移动，判断后面的位置是否还能插入新的分数{coutp-nume’/’p-deno;ListNode*q=p;p=p-link;delete(q);}}将前面的空间释放后，我们可以保证在同一时刻，链表中节点个数最多ｎ+1个。因为每插入一个分数其分母比其后面的分数的分母大，所以构成一个递减的序列，但是分母最多只有ｎ，所以链表中节点最多ｎ+1个(包括ｐ所指向的位置)，空间应该能承受。在方法二的实现时，我使用的是STL,因为其跌代子操作比较复杂，所以算法效率不够高。方法三：方法三是基于方法二的栈的实现，仔细分析上面过程发现，上面结点的插入和删除和栈的入栈出栈极其类似。最开始时栈中元素为0/1,1/1，首先我们取出栈顶元素0/1，存入out中，再如下执行：a)如果out的分母与栈顶元素(设为ｘ)分母相加不大于ｎ，则压入新分数(out.nume+x.nume)/(out.deno+x.deno)，不断重复此过程，直到不满足情况，执行b）。b)输出temp,弹出栈顶元素，存入out,若栈非空，继续a);否则，输出out,程序结束。以n=5为例：限于篇幅栈中分数为执行完一次a)步骤后的结果，out的取值的序列就是法雷序列上面省略了１/1的弹出过程，应该不会影响理解。同样我们设置栈的大小可以为ｎ，因为栈中元素分母明显递增。而栈的实现也颇简单：1/11/21/31/41/5out:0/11/11/21/31/4out:1/51/11/21/3out:1/41/11/22/5out:1/31/11/2out:2/51/12/33/5out:1/21/12/3out:3/51/13/4out:2/31/14/5out:3/41/1out:4/5structfraction{intdeno,nume;}stackfractionS;fractionout,temp;//设栈中已加入1/1,0/1out=S.pop();while(!S.empty){if(out.deno+S.GetTop().deno=n){temp.deno=out.deno+S.GetTop().deno;temp.nume=out.nume+S.GetTop().nume;S.push(temp);}else{coutout;//此处表示输出out表示的分数out=S.pop();}}coutout;以上三个方法的时间复杂度是同一个量级的，和法雷序列长度有关，但是第一个方法的空间复杂度基本为0，方法二，三的空间复杂度应该是O(N)的，而方法二采用了STL，在指针的运算上比较耗时，所以明显比方法三慢得多，而方法三虽用了一定的空间，但是其操作只涉及加法，所以实际效率上比方法一要好。【小结】总的来说，法雷序列的做法简直是数不胜数，我是基于不同的性质，以及采用不同的数据结构而给出不同的方法，应该说三个方法都已经是最好的了，只不过是实现效率因客观条件而有所差别。我这样采用不同方法的真正目的，不过是想将同一道问题用已有的数据结构知识用不同实现方法实现，以通过比较得到练习和提高。【附录】我程序程序实现时将所有输入，运行输出封装到一个类中classfareySequence{private:intn；//输入的数据规模intreadin()；//读入数据voidrun()；//根据n,计算并输出相应的法雷序列，//根据方法不同，我共写了三个run函数，分别加以实现voidstart()；//循环读入和运行，直到用户叫停public:fareySequence(){start()};//构造函数，其动总程序}方法一的程序实现：farey1.cpp方法二的程序实现：farey2.cpp方法三的程序实现：farey3.cpp