2022年法雷序列总结报告 .pdf

《2022年法雷序列总结报告 .pdf》由会员分享，可在线阅读，更多相关《2022年法雷序列总结报告 .pdf（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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-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/1 cout _a / _b; _a = 1; _b = n; / 整个序列第二个分

4、数1/n cout _a / _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 / 若不能，则指针向后移动，判断后

5、面的位置是否还能插入新的分数p = p-link; 如上所述即可求出所有分数组成的链表，最后输出就可以了，但是如果数据过多，则有存不下的危险， 而实际在插入过程中，上面的指针一旦往后移动了，前面链表中的内容对后面的计算毫无作用，这是我们可以输出前面分数，并释放前面链表的空间，于是可以改为：struct ListNode int deno, nume; / deno, nume分别表示分母，分子ListNode* link; ; 设链表中已插入0/1, 1/1, 链表头 first 指向 0/1 所在节点。ListNode*p = first; while (p-link != NULL) if

6、 (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 / 若不能，则指针向后移动，判断后面的位置是否还能插入新的分数 cout nume / deno; ListNode *q = p; p = p-link; delete(q); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 -

7、- - - - - - - - 将前面的空间释放后，我们可以保证在同一时刻，链表中节点个数最多+1 个。因为每插入一个分数其分母比其后面的分数的分母大，所以构成一个递减的序列，但是分母最多只有，所以链表中节点最多+1 个(包括所指向的位置)，空间应该能承受。在方法二的实现时，我使用的是STL, 因为其跌代子操作比较复杂，所以算法效率不够高。方法三：方法三是基于方法二的栈的实现，仔细分析上面过程发现，上面结点的插入和删除和栈的入栈出栈极其类似。最开始时栈中元素为0/1, 1/1，首先我们取出栈顶元素0/1，存入 out 中，再如下执行：a)如 果out的 分 母 与 栈 顶 元 素 ( 设 为

8、) 分 母 相 加 不 大 于 ， 则 压 入 新 分 数(out.nume+x.nume)/(out.deno+x.deno) ，不断重复此过程，直到不满足情况，执行b） 。b)输出 temp, 弹出栈顶元素，存入out, 若栈非空，继续a); 否则，输出out,程序结束。以 n=5 为例：限于篇幅栈中分数为执行完一次a)步骤后的结果， out 的取值的序列就是法雷序列上面省略了 /1 的弹出过程，应该不会影响理解。同样我们设置栈的大小可以为，因为栈中元素分母明显递增。而栈的实现也颇简单：1 / 1 1 / 2 1 / 3 1 / 4 1 / 5 out : 0/1 1 / 1 1 / 2

9、1 / 3 1 / 4 out : 1/5 1 / 1 1 / 2 1 / 3 out : 1/4 1 / 1 1 / 2 2 / 5 out : 1/3 1 / 1 1 / 2 out : 2/5 1 / 1 2 / 3 3 / 5 out : 1/2 1 / 1 2 / 3 out : 3/5 1 / 1 3 / 4 out : 2/3 1 / 1 4 / 5 out : 3/4 1 / 1 out : 4/5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页

10、 - - - - - - - - - struct fraction int deno, nume; stack S; fraction out, temp; /设栈中已加入 1/1, 0/1 out = 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.p

11、op(); cout out; 以上三个方法的时间复杂度是同一个量级的，和法雷序列长度有关，但是第一个方法的空间复杂度基本为0，方法二，三的空间复杂度应该是O(N)的，而方法二采用了STL，在指针的运算上比较耗时，所以明显比方法三慢得多，而方法三虽用了一定的空间，但是其操作只涉及加法，所以实际效率上比方法一要好。【小结】总的来说， 法雷序列的做法简直是数不胜数，我是基于不同的性质，以及采用不同的数据结构而给出不同的方法，应该说三个方法都已经是最好的了，只不过是实现效率因客观条件而有所差别。 我这样采用不同方法的真正目的，不过是想将同一道问题用已有的数据结构知识用不同实现方法实现，以通过比较得到

12、练习和提高。【附录】我程序程序实现时将所有输入，运行输出封装到一个类中class fareySequence private: int n；/ 输入的数据规模int readin() ； / 读入数据void run() ；/ 根据 n,计算并输出相应的法雷序列，/ 根据方法不同，我共写了三个run 函数，分别加以实现void start() ；/ 循环读入和运行，直到用户叫停public: fareySequence() start() ; / 构造函数，其动总程序 方法一的程序实现：farey1.cpp名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

13、 - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - / / 我真诚地保证：/ 我自己独立地完成了整个程序从分析、设计到编码的所有工作。/ 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中/ 详细地列举我所遇到的问题，以及别人给我的提示。/ 在此，我感谢XXX, , XXX 对我的启发和帮助。下面的报告中，我还会具体地提到/ 他们在各个方法对我的帮助。/ 我的程序里中凡是引用到其他程序或文档之处，/ 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段, / 我都已经在程序的注释里很清楚地注

14、明了引用的出处。/ 我从未没抄袭过别人的程序，也没有盗用别人的程序，/ 不管是修改式的抄袭还是原封不动的抄袭。/ 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。/ 饶向荣/* 文件名称：fareySequence 项目名称：法雷序列创建者：饶向荣创建时间：9/23/2004 最后修改时间：9/?/2004 功能：对输入的 N,输出相应的法雷序列文件中的函数名称和简单功能描述：int isNumber(char* str) 判断 str 是否为正整数, 并且大小不超过MAXV , 如果是，则返回数的值，否则，返回 -1. int readIn() 从键盘读入一个数，并显示相

15、应提示文件中定义的全局变量和简单功能描述：常量 MAXV , 限制输入数据的大小. 文件中用到的他处定义的全局变量及其出处：无与其他文件的依赖关系：无*/ #include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - const int MAXV = 100000; #define OUTPUTMSG / 控制是否输出序列，若只要测试计算速度，可以不输出using namespace std; /* 类名

16、称：fareySequence 定义该类的目的：能完成数据的输入和输出相应的法雷序列的全过程. 类属性：类中函数及功能：int isNumber(const char* str); 判断一个串是否为正整数, 并且大小不超过MAXV 满足判断条件，则返回字符串包含的数字，否则返回 -1 int readIn(); 提示用户输入一个不大于MAXV的非负数，返回一个满足条件的输入void run(); 根据输入的N, 输出相应的法雷序列void start(); 重复数据的输入和序列的输出，直到用户示意退出,用户输入0 退出与其他类的关系（调用/被调用哪类对象中的什么函数）：无*/ class fa

17、reySequence int n; / 要计算的序列的规模int isNumber(const char* str); /* 函数名称： isNumber 函数功能描述：判断一个串是否为正整数, 并且大小不超过MAXV 函数调用之前的预备条件：输入字符串返回值（如果有的话）: 满足判断条件，则返回字符串包含的数字，否则返回-1 函数的输入参数：一个字符串指针*/ int readIn(); /* 函数名称： readIn 函数功能描述：提示用户输入一个不大于MAXV的非负数，返回一个合理的输入返回值（如果有的话）: 返回合理的输入,即输入 N */ void run(); /* 函数名称：

18、run 函数功能描述: 根据得到的N, 输出相应的法雷序列, 本过程通过递推实现，由已知的前两数,可直接推出下一数,直到输出完所有数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 18 页 - - - - - - - - - 函数调用之前的预备条件：readIn 完成 N 的读入返回值（如果有的话）: 返回合理的输入,即输入 N */ void start(); /* 函数名称： start 函数功能描述：重复数据的输入，和序列的输出，直到用户示意退出*/ public:

19、 fareySequence() / 构造函数，启动输入输出 start(); ; int fareySequence:isNumber(const char* str) int i = 0, len = strlen(str), temp = 0; / i 循环变量，len 纪录字符串长度，temp 纪录得到的数值if (len = 0) return -1; / str 为 空串 ,则返回 -1 while (stri = ) i+; / 不计字符串前面的空白for (; i len & stri != ; i+) / 从前向后扫描直到遇到空白或者字符串结束if (stri 9) retu

20、rn -1; / 字符串中有非数字，返回-1 else temp = temp * 10 + stri - 0; / 更新数值if (temp MAXV) return -1; / 如果数值大于MAXV ，返回 -1 return temp; / 返回字符串包含的数字串的值 int fareySequence:readIn() const MAXN = 1000; / 用户输入的最大长度char inStrMAXN+1; / 输入存在此字符串中int temp; / temp 临时变量/ 提示信息cerr a positive number(less than 100001) you want

21、 to calculate: endl; cerr 0 stands for quit = 0) / 如果输出合理，则返回得到的输入数值return temp; else / 否则，重新输入 cerr A positive NUMBER less than 100001, sir! endl; void fareySequence:run() int _a, _b, _a, _b, a, b, quot; / _a, _b 表示第一个分数的分母和分子/ _a, _b 表示第二个分数的分母和分子/ a, b 当前要计算分数的分子分母/ quot 记录第二个分数分子分母放大的倍数int count

22、; _a = 0; _b = 1; / 整个序列第一个分数0/1 #if defined OUTPUTMSG cout _a / _b; #endif _a = 1; _b = n; / 整个序列第二个分数1/n #if defined OUTPUTMSG cout _a / _b; #endif count = 2; while (_b != 1) / 若 1/1 已生成，则跳出循环 / 根据前两个分数，算出下一个分数quot = (_b + n) / _b; a = quot * _a - _a; b = quot * _b - _b; +count; #if defined OUTPUT

23、MSG cout a / b; #endif / 递推，滚动存储，准备继续计算下一个分数_a = _a; _b = _b; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - - - - _a = a; _b = b; #if defined OUTPUTMSG cout endl; #endif cout the number of fractions: count endl; void fareySequence:start() whil

24、e (n = readIn() != 0) / 不断重复输入输出，直到用户输入0 run(); cerr work done! endl; void main() fareySequence tempVar; 方法二的程序实现：farey2.cpp/ 我真诚地保证：/ 我自己独立地完成了整个程序从分析、设计到编码的所有工作。/ 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中/ 详细地列举我所遇到的问题，以及别人给我的提示。/ 在此，我感谢XXX, , XXX 对我的启发和帮助。下面的报告中，我还会具体地提到/ 他们在各个方法对我的帮助。/ 我的程序里中凡是引用到其他程

25、序或文档之处，/ 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段, / 我都已经在程序的注释里很清楚地注明了引用的出处。/ 我从未没抄袭过别人的程序，也没有盗用别人的程序，/ 不管是修改式的抄袭还是原封不动的抄袭。/ 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。/ 饶向荣/* 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - 文件名称：fareySequence 项目名称：法雷序列创建者：饶向荣

26、创建时间：9/23/2004 最后修改时间：9/?/2004 功能：对输入的 N,输出相应的法雷序列文件中的函数名称和简单功能描述：int isNumber(char* str) 判断 str 是否为正整数, 并且大小不超过MAXV , 如果是，则返回数的值，否则，返回 -1. int readIn() 从键盘读入一个数，并显示相应提示文件中定义的全局变量和简单功能描述：常量 MAXV , 限制输入数据的大小. 文件中用到的他处定义的全局变量及其出处：无与其他文件的依赖关系：无*/ #include #include #include const int MAXV = 100000; / 输入

27、的最大数值#define OUTPUTMSG / 控制是否输出序列，若只要测试计算速度，可以不输出using namespace std; /* 类名称：fareySequence 定义该类的目的：能完成数据的输入和输出相应的法雷序列的全过程. 类属性：类中函数及功能：int isNumber(const char* str); 判断一个串是否为正整数, 并且大小不超过MAXV 满足判断条件，则返回字符串包含的数字，否则返回 -1 int readIn(); 提示用户输入一个不大于MAXV的非负数，返回一个满足条件的输入void run(); 根据输入的N, 输出相应的法雷序列void sta

28、rt(); 重复数据的输入和序列的输出，直到用户示意退出,用户输入0 退出与其他类的关系（调用/被调用哪类对象中的什么函数）：无*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - class fareySequence struct fraction / 分数的分子和分母的记录 int deno, nume; / deno, nume 分别表示分母，分子; int n; / 要计算的序列的规模int isNumber(co

29、nst char* str); /* 函数名称： isNumber 函数功能描述：判断一个串是否为正整数, 并且大小不超过MAXV 函数调用之前的预备条件：输入字符串返回值（如果有的话）: 满足判断条件，则返回字符串包含的数字，否则返回-1 函数的输入参数：一个字符串指针*/ int readIn(); /* 函数名称： readIn 函数功能描述：提示用户输入一个不大于MAXV的非负数，返回一个合理的输入返回值（如果有的话）: 返回合理的输入,即输入 N */ void run(); /* 函数名称： run 函数功能描述: 根据得到的N, 输出相应的法雷序列, 本过程通过递推实现，由已知的

30、前两数,可直接推出下一数,直到输出完所有数函数调用之前的预备条件：readIn 完成 N 的读入返回值（如果有的话）: 返回合理的输入,即输入 N */ void start(); /* 函数名称： start 函数功能描述：重复数据的输入，和序列的输出，直到用户示意退出*/ public: fareySequence() / 构造函数，启动输入输出 start(); ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 18 页 - - - - - - - - - in

31、t fareySequence:isNumber(const char* str) int i = 0, len = strlen(str), temp = 0; / i 循环变量，len 纪录字符串长度，temp 纪录得到的数值if (len = 0) return -1; / str 为 空串 ,则返回 -1 while (stri = ) i+; / 不计字符串前面的空白for (; i len & stri != ; i+) / 从前向后扫描直到遇到空白或者字符串结束if (stri 9) return -1; / 字符串中有非数字，返回-1 else temp = temp * 10

32、 + stri - 0; / 更新数值if (temp MAXV) return -1; / 如果数值大于MAXV ，返回 -1 return temp; / 返回字符串包含的数字串的值 int fareySequence:readIn() const MAXN = 1000; / 用户输入的最大长度char inStrMAXN+1; / 输入存在此字符串中int temp; / temp 临时变量/ 提示信息cerr a positive number(less than 100001) you want to calculate: endl; cerr 0 stands for quit

33、= 0) / 如果输出合理，则返回得到的输入数值return temp; else / 否则，重新输入 cerr A positive NUMBER less than 100001, sir! endl; void fareySequence:run() / 根据说明文档中第二种方法编写 list sflist; / 定义法雷序列链表fraction temp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - - - - - - - - - int co

34、unt; temp.deno = 1; temp.nume = 0; / 序列第一个分数sflist.push_back(temp); temp.deno = 1; temp.nume = 1; / 序列的最后一个分数sflist.push_back(temp); list:iterator pointer, _pointer; / 跌代子 pointer 为扫描指针， _pointer 计录 pointer 下一位置pointer = sflist.begin(); count = 0; while (pointer-deno != 1 | pointer-nume != 1) / 没有到链

35、表尾部 +(_pointer = pointer); / 给_pointer 赋值为 pointer 下一位置if (pointer-deno + _pointer-deno deno + _pointer-deno; temp.nume = pointer-nume + _pointer-nume; sflist.insert(_pointer, temp); / 在 _pointer 位置插入这个新的分数 else / 若不能再插入新的分数，则pointer 向后移动 #if defined OUTPUTMSG cout nume / deno ; / 输出 pointer 所在位置的分数

36、#endif +count; +pointer; / 移动 pointer sflist.pop_front(); / pointer之前的元素已经无用, 可以删除以节省空间 #if defined OUTPUTMSG cout nume / deno endl; #endif cout the number of fractions : +count endl; sflist.clear(); void fareySequence:start() while (n = readIn() != 0) / 不断重复输入输出，直到用户输入0 run(); 名师资料总结 - - -精品资料欢迎下载

37、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - cerr work done! endl; void main() fareySequence tempVar; 方法三的程序实现：farey3.cpp/ 我真诚地保证：/ 我自己独立地完成了整个程序从分析、设计到编码的所有工作。/ 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中/ 详细地列举我所遇到的问题，以及别人给我的提示。/ 在此，我感谢XXX, , XXX 对我的启发和帮助。下面的报告

38、中，我还会具体地提到/ 他们在各个方法对我的帮助。/ 我的程序里中凡是引用到其他程序或文档之处，/ 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段, / 我都已经在程序的注释里很清楚地注明了引用的出处。/ 我从未没抄袭过别人的程序，也没有盗用别人的程序，/ 不管是修改式的抄袭还是原封不动的抄袭。/ 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。/ 饶向荣/* 文件名称：fareySequence 项目名称：法雷序列创建者：饶向荣创建时间：9/23/2004 最后修改时间：9/?/2004 功能：对输入的 N,输出相应的法雷序列文件中的函数名称和简单功能描述：in

39、t isNumber(char* str) 判断 str 是否为正整数, 并且大小不超过MAXV , 如果是，则返回数的值，否则，返回 -1. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - int readIn() 从键盘读入一个数，并显示相应提示文件中定义的全局变量和简单功能描述：常量 MAXV , 限制输入数据的大小. 文件中用到的他处定义的全局变量及其出处：无与其他文件的依赖关系：无*/ #include #incl

40、ude #include const int MAXV = 100000; / 输入的最大数值#define OUTPUTMSG / 控制是否输出序列，若只要测试计算速度，可以不输出using namespace std; /* 类名称：fareySequence 定义该类的目的：能完成数据的输入和输出相应的法雷序列的全过程. 类属性：类中函数及功能：int isNumber(const char* str); 判断一个串是否为正整数, 并且大小不超过MAXV 满足判断条件，则返回字符串包含的数字，否则返回 -1 int readIn(); 提示用户输入一个不大于MAXV的非负数，返回一个满足

41、条件的输入void run(); 根据输入的N, 输出相应的法雷序列void start(); 重复数据的输入和序列的输出，直到用户示意退出,用户输入0 退出与其他类的关系（调用/被调用哪类对象中的什么函数）：无*/ class fareySequence struct fraction / 分数的分子和分母的记录 int deno, nume; / deno, nume 分别表示分母，分子; int n; / 要计算的序列的规模int isNumber(const char* str); /* 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

42、- - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - 函数名称： isNumber 函数功能描述：判断一个串是否为正整数, 并且大小不超过MAXV 函数调用之前的预备条件：输入字符串返回值（如果有的话）: 满足判断条件，则返回字符串包含的数字，否则返回-1 函数的输入参数：一个字符串指针*/ int readIn(); /* 函数名称： readIn 函数功能描述：提示用户输入一个不大于MAXV的非负数，返回一个合理的输入返回值（如果有的话）: 返回合理的输入,即输入 N */ void run(); /* 函数名称： run

43、 函数功能描述: 根据得到的N, 输出相应的法雷序列, 本过程通过递推实现，由已知的前两数,可直接推出下一数,直到输出完所有数函数调用之前的预备条件：readIn 完成 N 的读入返回值（如果有的话）: 返回合理的输入,即输入 N */ void start(); /* 函数名称： start 函数功能描述：重复数据的输入，和序列的输出，直到用户示意退出*/ public: fareySequence() / 构造函数，启动输入输出 start(); ; int fareySequence:isNumber(const char* str) int i = 0, len = strlen(st

44、r), temp = 0; / i 循环变量，len 纪录字符串长度，temp 纪录得到的数值if (len = 0) return -1; / str 为 空串 ,则返回 -1 while (stri = ) i+; / 不计字符串前面的空白for (; i len & stri != ; i+) / 从前向后扫描直到遇到空白或者字符串结束if (stri 9) return -1; / 字符串中有非数字，返回-1 else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页

45、，共 18 页 - - - - - - - - - temp = temp * 10 + stri - 0; / 更新数值if (temp MAXV) return -1; / 如果数值大于MAXV ，返回 -1 return temp; / 返回字符串包含的数字串的值 int fareySequence:readIn() const MAXN = 1000; / 用户输入的最大长度char inStrMAXN+1; / 输入存在此字符串中int temp; / temp 临时变量/ 提示信息cerr a positive number(less than 100001) you want t

46、o calculate: endl; cerr 0 stands for quit = 0) / 如果输出合理，则返回得到的输入数值return temp; else / 否则，重新输入 cerr A positive NUMBER less than 100001, sir! = 0) / 若栈非空 ,执行新元素的插入 if (out.deno + Stacktop.deno = n) / 判断是否插入新的分数入栈名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18

47、页 - - - - - - - - - temp.deno = out.deno + Stacktop.deno; temp.nume = out.nume + Stacktop.nume; Stack+top = temp; else / 若不能再插入新的分数，则弹出栈顶元素到out count+; #if defined OUTPUTMSG cout out.nume / out.deno ; #endif out = Stacktop-; #if defined OUTPUTMSG cout out.nume / out.deno endl; #endif cout the number of fractions: +count endl; void fareySequence:start() while (n = readIn() != 0) / 不断重复输入输出，直到用户输入0 run(); cerr work done! endl; void main() fareySequence tempVar; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -