// 我真誠地保證：
    
// 我自己獨(dú)立地完成了整個(gè)程序從分析、設(shè)計(jì)到編碼的所有工作。
// 如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序?qū)嵙?xí)報(bào)告中
// 詳細(xì)地列舉我所遇到的問題，以及別人給我的提示。

// 在此，我感謝 XXX, …, XXX對(duì)我的啟發(fā)和幫助。下面的報(bào)告中，我還會(huì)具體地提到
// 他們?cè)诟鱾€(gè)方法對(duì)我的幫助。
 
// 我的程序里中凡是引用到其他程序或文檔之處，
// 例如教材、課堂筆記、網(wǎng)上的源代碼以及其他參考書上的代碼段,
// 我都已經(jīng)在程序的注釋里很清楚地注明了引用的出處。

// 我從未沒抄襲過別人的程序，也沒有盜用別人的程序，
// 不管是修改式的抄襲還是原封不動(dòng)的抄襲。

// 我編寫這個(gè)程序，從來沒有想過要去破壞或妨礙其他計(jì)算機(jī)系統(tǒng)的正常運(yùn)轉(zhuǎn)。
    
// 饒向榮

/*
	文件名稱：	fareySequence
	項(xiàng)目名稱：	法雷序列
	創(chuàng)建者：	饒向榮
	創(chuàng)建時(shí)間：	9/23/2004
	最后修改時(shí)間：9/?/2004
	功能：		對(duì)輸入的N,輸出相應(yīng)的法雷序列

	文件中的函數(shù)名稱和簡單功能描述：
		int isNumber(char* str) 判斷str是否為正整數(shù), 并且大小不超過MAXV, 如果是，則返回?cái)?shù)的值，
								否則，返回-1.
		int readIn()			從鍵盤讀入一個(gè)數(shù)，并顯示相應(yīng)提示

	文件中定義的全局變量和簡單功能描述：
		常量MAXV, 限制輸入數(shù)據(jù)的大小.

	文件中用到的他處定義的全局變量及其出處：無
	與其他文件的依賴關(guān)系：無
*/

#include <iostream>
#include <string>
#include <list>
const int MAXV = 100000; // 輸入的最大數(shù)值

#define OUTPUTMSG		// 控制是否輸出序列，若只要測(cè)試計(jì)算速度，可以不輸出

using namespace std;

/*
	類名稱：		fareySequence
	定義該類的目的：能完成數(shù)據(jù)的輸入和輸出相應(yīng)的法雷序列的全過程.
	類屬性：
	類中函數(shù)及功能：
		int isNumber(const char* str); 判斷一個(gè)串是否為正整數(shù), 并且大小不超過MAXV
									   滿足判斷條件，則返回字符串包含的數(shù)字，否則返回-1
		int readIn();  提示用戶輸入一個(gè)不大于MAXV的非負(fù)數(shù)，返回一個(gè)滿足條件的輸入
		void run(); 根據(jù)輸入的N, 輸出相應(yīng)的法雷序列
		void start(); 重復(fù)數(shù)據(jù)的輸入和序列的輸出，直到用戶示意退出,用戶輸入0退出

	與其他類的關(guān)系（調(diào)用/被調(diào)用哪類對(duì)象中的什么函數(shù)）：無
*/
class fareySequence
{
	struct fraction  // 分?jǐn)?shù)的分子和分母的記錄
	{
		int deno, nume; // deno, nume分別表示分母，分子
	};

	int n; // 要計(jì)算的序列的規(guī)模

	int isNumber(const char* str);
/*
	函數(shù)名稱：isNumber
	函數(shù)功能描述：判斷一個(gè)串是否為正整數(shù), 并且大小不超過MAXV
	函數(shù)調(diào)用之前的預(yù)備條件：輸入字符串
	返回值（如果有的話）: 滿足判斷條件，則返回字符串包含的數(shù)字，否則返回-1
	函數(shù)的輸入?yún)?shù)：一個(gè)字符串指針
*/
	int readIn();
/*
	函數(shù)名稱：readIn
	函數(shù)功能描述：提示用戶輸入一個(gè)不大于MAXV的非負(fù)數(shù)，返回一個(gè)合理的輸入
	返回值（如果有的話）: 返回合理的輸入,即輸入N
*/
	void run();
/*
	函數(shù)名稱：run
	函數(shù)功能描述: 根據(jù)得到的N, 輸出相應(yīng)的法雷序列, 本過程通過遞推實(shí)現(xiàn)，
				  由已知的前兩數(shù),可直接推出下一數(shù),直到輸出完所有數(shù)
	函數(shù)調(diào)用之前的預(yù)備條件：readIn完成N的讀入
	返回值（如果有的話）: 返回合理的輸入,即輸入N
*/
	void start();
/*
	函數(shù)名稱：start
	函數(shù)功能描述：重復(fù)數(shù)據(jù)的輸入，和序列的輸出，直到用戶示意退出
*/

public:
	fareySequence()		// 構(gòu)造函數(shù)，啟動(dòng)輸入輸出
	{
		start();
	}
};

int fareySequence::isNumber(const char* str)
{
	int i = 0, len = strlen(str), temp = 0; 
	// i 循環(huán)變量， len紀(jì)錄字符串長度，temp紀(jì)錄得到的數(shù)值

	if (len == 0) return -1;	// str為]空串,則返回-1
	while (str[i] == ' ') i++;	// 不計(jì)字符串前面的空白
	for (; i < len && str[i] != ' '; i++) // 從前向后掃描直到遇到空白或者字符串結(jié)束
		if (str[i] < '0' || str[i] > '9') return -1; // 字符串中有非數(shù)字，返回-1
			else 
			{
				temp = temp * 10 + str[i] - '0';  // 更新數(shù)值
				if (temp > MAXV) return -1; // 如果數(shù)值大于MAXV，返回-1
			}
	return temp;	// 返回字符串包含的數(shù)字串的值
}

int fareySequence::readIn()
{
	const MAXN = 1000; // 用戶輸入的最大長度
	char inStr[MAXN+1]; // 輸入存在此字符串中
	int temp; // temp臨時(shí)變量
	
	// 提示信息
	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)	// 如果輸出合理，則返回得到的輸入數(shù)值
			return temp;
		else			// 否則，重新輸入
		{
			cerr << "A positive NUMBER less than 100001, sir! " << endl;
		}
	}
}

void fareySequence::run() // 根據(jù)說明文檔中第二種方法編寫
{
	fraction Stack[MAXV]; // 用一個(gè)數(shù)組來模擬堆棧
	fraction temp, out; // temp為臨時(shí)變量,out保存剛彈出棧的分?jǐn)?shù)
	int top, count; // top指示棧頂位置

	temp.deno = 1; temp.nume = 1; // 1/1入棧
	Stack[0] = temp;
	temp.deno = 1; temp.nume = 0; // 0/1入棧
	Stack[1] = temp;
	
	top = 0; out = Stack[1]; count = 0; // 彈0/1出棧,存入out
	while (top >= 0) // 若棧非空,執(zhí)行新元素的插入
	{
		if (out.deno + Stack[top].deno <= n)  // 判斷是否插入新的分?jǐn)?shù)入棧
		{
			temp.deno = out.deno + Stack[top].deno;
			temp.nume = out.nume + Stack[top].nume;
			Stack[++top] = temp;
		}
		else // 若不能再插入新的分?jǐn)?shù)，則彈出棧頂元素到out
		{
			count++;
			#if defined OUTPUTMSG
				cout << out.nume << "/" << out.deno << " ";
			#endif
			out = Stack[top--];
		}
	}
	#if defined OUTPUTMSG
		cout << out.nume << "/" << out.deno << endl;
	#endif
	cout << "the number of fractions: " << ++count << endl;
}

void fareySequence::start()
{
	while ((n = readIn()) != 0)	// 不斷重復(fù)輸入輸出，直到用戶輸入0
	{
		run();
		cerr << "work done!" << endl;
	}
}

void main()
{
	fareySequence tempVar; 
}