farey2.cpp

法雷序列是非常经典的序列

// 我真诚地保证：
    
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。

// 在此，我感谢 XXX, …, XXX对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// 饶向荣

/*
	文件名称：	fareySequence
	项目名称：	法雷序列
	创建者：	饶向荣
	创建时间：	9/23/2004
	最后修改时间：9/?/2004
	功能：		对输入的N,输出相应的法雷序列

	文件中的函数名称和简单功能描述：
		int isNumber(char* str) 判断str是否为正整数, 并且大小不超过MAXV, 如果是，则返回数的值，
								否则，返回-1.
		int readIn()			从键盘读入一个数，并显示相应提示

	文件中定义的全局变量和简单功能描述：
		常量MAXV, 限制输入数据的大小.

	文件中用到的他处定义的全局变量及其出处：无
	与其他文件的依赖关系：无
*/

#include <iostream>
#include <string>
#include <list>
const int MAXV = 100000; // 输入的最大数值

#define OUTPUTMSG		// 控制是否输出序列，若只要测试计算速度，可以不输出

using namespace std;

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

	与其他类的关系（调用/被调用哪类对象中的什么函数）：无
*/
class fareySequence
{
	struct fraction  // 分数的分子和分母的记录
	{
		int deno, nume; // deno, nume分别表示分母，分子
	};

	int n; // 要计算的序列的规模

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

public:
	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 (str[i] == ' ') i++;	// 不计字符串前面的空白
	for (; i < len && str[i] != ' '; i++) // 从前向后扫描直到遇到空白或者字符串结束
		if (str[i] < '0' || str[i] > '9') return -1; // 字符串中有非数字，返回-1
			else 
			{
				temp = temp * 10 + str[i] - '0';  // 更新数值
				if (temp > MAXV) return -1; // 如果数值大于MAXV，返回-1
			}
	return temp;	// 返回字符串包含的数字串的值
}

int fareySequence::readIn()
{
	const MAXN = 1000; // 用户输入的最大长度
	char inStr[MAXN+1]; // 输入存在此字符串中
	int temp; // temp临时变量
	
	// 提示信息
	cerr << "a positive number(less than 100001) you want to calculate: " << endl;
	cerr << "			0 stands for quit " << endl;

	while (true) // 不断提示用户输入，直到得到合理输入
	{
		cin.getline(inStr, MAXN);
		temp = isNumber(inStr);
		if (temp >= 0)	// 如果输出合理，则返回得到的输入数值
			return temp;
		else			// 否则，重新输入
		{
			cerr << "A positive NUMBER less than 100001, sir! " << endl;
		}
	}
}

void fareySequence::run() // 根据说明文档中第二种方法编写
{
	list<fraction> sflist; // 定义法雷序列链表
	fraction temp;
	int count;

	temp.deno = 1; temp.nume = 0; // 序列第一个分数
	sflist.push_back(temp);
	temp.deno = 1; temp.nume = 1; // 序列的最后一个分数
	sflist.push_back(temp);
	
	list<fraction>::iterator pointer, _pointer;		
	// 跌代子pointer为扫描指针，_pointer计录pointer下一位置
	pointer = sflist.begin();
	count = 0;
	while (pointer->deno != 1 || pointer->nume != 1) // 没有到链表尾部
	{
		++(_pointer = pointer);	// 给_pointer赋值为pointer下一位置
		if (pointer->deno + _pointer->deno <= n)  // 如果pointer, _pointer之间可以插另外一分数
		{
			temp.deno = pointer->deno + _pointer->deno;
			temp.nume = pointer->nume + _pointer->nume;
			sflist.insert(_pointer, temp); // 在_pointer位置插入这个新的分数
		}
		else // 若不能再插入新的分数，则pointer向后移动
		{
			#if defined OUTPUTMSG
				cout << pointer->nume << "/" << pointer->deno << " ";  // 输出pointer所在位置的分数
			#endif
			++count;
			++pointer; // 移动pointer
			sflist.pop_front(); // pointer之前的元素已经无用, 可以删除以节省空间
		}
	}
	#if defined OUTPUTMSG
		cout << pointer->nume << "/" << pointer->deno << endl;
	#endif
	cout << "the number of fractions : " << ++count << endl;
	sflist.clear();
}

void fareySequence::start()
{
	while ((n = readIn()) != 0)	// 不断重复输入输出，直到用户输入0
	{
		run();
		cerr << "work done!" << endl;
	}
}

void main()
{
	fareySequence tempVar; 
}