CodeIQ：小数を分数q/pに近似しよう

問題の概要

問題を引用します。

• 標準入力から、小数（有効桁数が51、小数点以下桁数が50、0.1以上10未満）が与えられます。
• 与えられた小数を分数で、出来るだけ近似誤差が少なくなるよう近似します。
• ただし分子と分母とはいずれも自然数であり、6桁以下とします。
• 求めた分子と分母を、分子 分母の順に、スペース区切りで出力してください。

私のプログラム

C言語で解答しています。

#include <stdio.h>

/**
 *	連分数展開
 *	a[IN]	各段階の分数の分母のリスト
 *	count[IN]	何段階まで処理するか
 *	den[OUT]	分母
 *	num[OUT]	分子
 *	戻り値	0：aに処理するだけの値がない
 *			1：処理され、分母分子ともに6桁以内であった
 *			2：処理され、分母か分子が6桁以上であった
 */
int calcDenNum(unsigned int* a, int count, unsigned int* den, unsigned int* num){
	if(count < 1){
		return 0;
	}

	int i=0;
	unsigned int p=a[count];	// 分母
	unsigned int q=1;	// 分子

	for(i=count-1; i>0; i--){
		int np = a[i] * p + q;
		int nq = p;

		p = np;
		q = nq;
	}

	*num = a[0] * p + q;
	*den = p;

	// 7桁以上になった
	if((*den/1000000 >= 1) || (*num/1000000 >= 1)){
		return 2;
	}

	return 1;
}

/**
 *	少数を分数にする
 *	org[IN]	小数
 *	den[OUT]	分母
 *	num[OUT]	分子
 **/
void getRat(double org, unsigned int* den, unsigned int* num){
	unsigned int a[32];
	int i=0;
	unsigned int pow = 1;
	double b = org;

	// 整数部分
	a[0] = (unsigned int)org;

	// 連分数展開
	for(i=1; i<sizeof(a)/sizeof(int); i++){
		int ret = 0;	// 分母、分子の計算結果の妥当性
		unsigned int p,q;		// 現在の分母、分子
		b = 1/(b - (unsigned int)(b));
		a[i] = (unsigned int)b;

		if(a[i] == 0){
			break;
		}

		ret = calcDenNum(a, i, &p, &q);
		if(ret == 1){
			*den = p;
			*num = q;
		}
		else if(ret == 2){
			break;
		}

		// Debug
		// printf("%d: %lf %u, den=%u num=%u\n",i, b, a[i], *den, *num);

		pow *= 10;
	}

	return;
}

int main(int argc, char* argv[]){
	char str[64] = {0};

	while( fgets(str, sizeof(str), stdin) != NULL ){
		double org = 0;						// 入力されたの数
		sscanf(str, "%lf", &org);
		unsigned int n=0;
		unsigned int d=0;

		getRat(org, &d, &n);
		printf("%u %u", n, d);
	}

	return 0;
}

解説

この問題は少数を連分数を使って近似するという問題です。
実際、この手順をそのままコード化しています。getRat()が連分数展開を行い、calcDenNum()でその連分数をq/pの形に直します。
この問題は★★★ですが実際結構難しいと思います。

雑感

この問題のロジック自体は高校の数学でやったことなのですぐにイメージできました（やり方は忘れていたので調べましたが）。ただ、コードにするのは結構苦労しました。コードだけ考えていると頭が混乱してきます。こういう時は結局紙に書いて整理するのが一番早いと思います。