farey1.cpp

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

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

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

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

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

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

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

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

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

#include <iostream>
#include <string>
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
{
	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()
{
	int __a, __b, _a, _b, a, b, quot;
	// __a, __b 表示第一个分数的分母和分子
	// _a, _b 表示第二个分数的分母和分子
	// a, b 当前要计算分数的分子分母
	// quot 记录第二个分数分子分母放大的倍数
	int count;

	__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 OUTPUTMSG
			cout << " " << a << "/" << b;
		#endif

		// 递推，滚动存储，准备继续计算下一个分数
		__a = _a; __b = _b;
		_a = a; _b = b;
	}
	#if defined OUTPUTMSG
		cout << 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; 
}