《北大数据结构与算法实习报告：法雷序列》由会员分享，可在线阅读，更多相关《北大数据结构与算法实习报告：法雷序列（5页珍藏版）》请在金锄头文库上搜索。
1、法雷序列实习报告【前言】法雷序列是非常经典的序列，他有很多有趣的性质，因此在做法雷序列的时候，完全不要通过分数的排序就能够实现，且效率有很大的提高，而其性质又如此之多，以至于利用不同的性质能得到很多不同的算法，下面就将会简单比较一下几种不同的做法，并对各自性能稍作分析。【总体设计】一般总的程序应该分为读入和序列的计算和序列的输出三部分。但是如果序列的输出单独执行的话，需要保存在整个序列，对于较小的n的量级尚能胜任，但当n增大之后，空间将明显的不足，所以我在设计算法的时候，决定合并序列计算和输出这两个部分，边计算边输出，节省内存空间，下面介绍的主体算法都是直接或者优化成这种方法实现的。【主体算法
2、设计】我想数据的输入就不用多说了，下面就落实到就给定一个数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)但是我们只需选择最小的一个，容易证明
3、最小的p3/q3应该为(p2*x-p1)/(q2*x-q1)，其中x=maxkq2*k-q1n，这点容易证明。而且此时(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 / _
4、b;while (_b != 1) / 若1/1已生成，则跳出循环/ 根据前两个分数，算出下一个分数x = (_b + n) / _b;/ ! 此处用到整除，算法效率的关键a = x * _a - _a;b = x * _b - _b;cout a / link != NULL)if (p-deno + p-link-deno deno = p-deno + p-link-deno;q-nume = p-nume + p-link-nume;q-link = p-link;p-link = q;else/ 若不能，则指针向后移动，判断后面的位置是否还能插入新的分数p = p-link;如上所述
5、即可求出所有分数组成的链表，最后输出就可以了，但是如果数据过多，则有存不下的危险，而实际在插入过程中，上面的指针一旦往后移动了，前面链表中的内容对后面的计算毫无作用，这是我们可以输出前面分数，并释放前面链表的空间，于是可以改为：struct ListNodeint deno, 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 deno = p-deno + p-l
6、ink-deno;q-nume = p-nume + p-link-nume;q-link = p-link;p-link = q;else/ 若不能，则指针向后移动，判断后面的位置是否还能插入新的分数cout nume / deno;ListNode *q = p;p = p-link;delete(q);将前面的空间释放后，我们可以保证在同一时刻，链表中节点个数最多+1个。因为每插入一个分数其分母比其后面的分数的分母大，所以构成一个递减的序列，但是分母最多只有，所以链表中节点最多+1个(包括所指向的位置)，空间应该能承受。在方法二的实现时，我使用的是STL, 因为其跌代子操作比较复杂，所以
7、算法效率不够高。方法三：方法三是基于方法二的栈的实现，仔细分析上面过程发现，上面结点的插入和删除和栈的入栈出栈极其类似。最开始时栈中元素为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 / 11 /
8、 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/5上面省略了/1的弹出过程，应该不会影响理解。同样我们设置栈的大小可以为，因为栈中元素分母明显递增。而栈的实现也颇简单：struct fractionint deno,
9、 nume;stack S;fraction out, 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 cout out;/ 此处表示输出out表示的分数out = S.pop();cout out;以上三个方法的时间复杂度是同一个量级的，和法雷序列长度有关，但是第一个方法的空间复杂度
10、基本为0，方法二，三的空间复杂度应该是O(N)的，而方法二采用了STL，在指针的运算上比较耗时，所以明显比方法三慢得多，而方法三虽用了一定的空间，但是其操作只涉及加法，所以实际效率上比方法一要好。【小结】总的来说，法雷序列的做法简直是数不胜数，我是基于不同的性质，以及采用不同的数据结构而给出不同的方法，应该说三个方法都已经是最好的了，只不过是实现效率因客观条件而有所差别。我这样采用不同方法的真正目的，不过是想将同一道问题用已有的数据结构知识用不同实现方法实现，以通过比较得到练习和提高。【附录】我程序程序实现时将所有输入，运行输出封装到一个类中class fareySequenceprivate:int n；/ 输入的数据规模int readin()； / 读入数据void run()； / 根据n,计算并输出相应的法雷序列，/ 根据方法不同，我共写了三个run函数，分别加以实现void start()；/ 循环读入和运行，直到用户叫停public:fareySequence() start() ; / 构造函数，其动总程序方法一的程序实现：farey1.cpp方法二的程序实现：farey2.cpp方法三的程序实现：farey3.cpp
