// 我真誠地保證：
    
// 我自己獨立地完成了整個程序從分析、設計到編碼的所有工作。
// 如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序實習報告中
// 詳細地列舉我所遇到的問題，以及別人給我的提示。

// 在此，我感謝 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() // 根據說明文檔中第二種方法編寫
{
	fraction Stack[MAXV]; // 用一個數組來模擬堆棧
	fraction temp, out; // temp為臨時變量,out保存剛彈出棧的分數
	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) // 若棧非空,執行新元素的插入
	{
		if (out.deno + Stack[top].deno <= n)  // 判斷是否插入新的分數入棧
		{
			temp.deno = out.deno + Stack[top].deno;
			temp.nume = out.nume + Stack[top].nume;
			Stack[++top] = temp;
		}
		else // 若不能再插入新的分數，則彈出棧頂元素到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)	// 不斷重復輸入輸出，直到用戶輸入0
	{
		run();
		cerr << "work done!" << endl;
	}
}

void main()
{
	fareySequence tempVar; 
}