少数を入力して分数を求めるプログラムです。

picusicu · #1

問題
　小数が与えられた時に，それを値が最も近い分数で表現することを考える。例えば，小数として， 3.141592 が与えられた時，分母・分子に用いる数字を 3 桁以内に限定するとすると，それにもっとも値が近い分数は，355/113 となる。ただし，ここでは，与えられる小数は，0 以上 10 未満であるものとする。また，出力する分数は，既約分数に限るものとする。具体的には，a.b1b2b3.........bk という形式の小数(ここで，a, b1, b2, b3,..., bk は，それぞれ 1 桁の正の整数)が与えられた時に，これに最も近い分数 y/x を見つける。ただし，kが50以下, x と y が 6 桁以下となる場合にも対応できるプログラムであること。

処理(1): 整数 x と整数 y を引数として受け取り，小数 y/x を配列として返す関数
処理(2): 2 つの小数 f1 と f2 を配列として受け取り，その差の絶対値(型は，小数) を配列として返す関数
􏰀処理(3): 2 つの小数 f1 と f2 を配列として受け取り，f1 の方が大きい時，1 を返し，そうでない時，0 を返す関数。
􏰀処理(4): 配列としての 1 つの小数ともう一つの配列を受け取り，小数をもう一つの配列に代入する関数。

質問
　少数を入力して分数を求めるところまではできたんですが、int型配列に格納するのができないので、教えていただきたいです。

コード:

#include <stdio.h>
#include <math.h>
double shori1(int x,int y);
double shori2(double x,double y);
int shori3(double x,double y);
double shori4(double x,double y);

int main(void)
{
  int x,y,c,d,count=0;
  int rememx1,rememy1,rememx2,rememy2;
  double a,b,z;
  double hantei1=999.0,hantei2=999.0;
  double nyuryoku;
  scanf("%lf",&nyuryoku);
  
  if(nyuryoku>0) {
    for(x=1;x<=999;x++) {
      for(y=1;y<=999;y++) {
	a = shori1(x,y);
	b = shori2(a,nyuryoku);
	c = shori3(hantei1,b);
	if(c==1) {
	  hantei1 = shori4(b,hantei1);
	  rememx1 = x;
	  rememy1 = y;
	} else if(c==0) {
	  break;
	}
      }
      d = shori3(hantei2,hantei1);
      if(d==1) {
	hantei2 = shori4(hantei1,hantei2);
	rememx2 = rememx1;
	rememy2 = rememy1;
      } else if(d==0) {
	
      }
      hantei1=999.0;
    }
  }
  z = (double)rememy2/(double)rememx2;
  printf("%lfに最も近い分数は %d/%d \nそのときの近似値は %lf \n",nyuryoku,rememy2,rememx2,z);
  
  return 0;
}

double shori1(int x,int y)
{
  double a;
  
  a = (double)y/(double)x;
  
  return a;
}

double shori2(double x,double y)
{
  double b;
  
  if(x>y) {
    b = x - y;
  } else if(x<y) {
    b = y - x;
  }
  
  return b;
}

int shori3(double x,double y)
{
  int c;
  if(x>y) {
    c = 1;
  } else {
    c = 0;
  }
  
  return c;
}

double shori4(double x,double y)
{
  y = x;
  return y;
}

かずま · #2

小数の入力に double を使うと、小数点以下15桁程度しか取得できません。

小数を int の配列にするなら int b[51]; で、b[0] が a、b[k] が bkですね。

入力

コード:

#include <stdio.h>

#define K 51

int input(int *f)
{
	char s[1024];
	if (!fgets(s, sizeof s, stdin)) return 1;
	if (s[0] < '0' || s[0] > '9') return 1;
	f[0] = s[0] - '0';
	int i = 1;
	if (s[1] == '.')
		for (; i < K && s[i+1] >= '0' && s[i+1] <= '9'; i++)
			f[i] = s[i+1] - '0';
	while (i < K) f[i++] = 0;
	return 0;
}

void print(const int *f)
{
	int n;
	for (n = K; --n > 0 && f[n] == 0; ) ;
	putchar(f[0] + '0'), putchar('.');
	for (int i = 1; i <= n; i++) putchar(f[i] + '0');
	putchar('\n');
}

int main(void)
{
	int a[K];
	while (!input(a)) print(a);
}

処理1

コード:

#include <stdio.h>

#define K 51

void proc1(int x, int y, int *f)
{
	for (int i = 0; i < K; i++) f[i] = x / y, x = x % y * 10;
}

void print(const int *f)
{
	int n;
	for (n = K; --n > 0 && f[n] == 0; ) ;
	putchar(f[0] + '0'), putchar('.');
	for (int i = 1; i <= n; i++) putchar(f[i] + '0');
	putchar('\n');
}

int main(void)
{
	int a[K], b[K] = { 2, 7, 1 };
	proc1(355, 113, a);
	print(a);
	print(b);
}

処理2

コード:

#include <stdio.h>

#define K 51

void proc2(const int *f1, const int *f2, int *d)
{
	int b = 0;
	for (int i = K; --i >= 0; ) {
		d[i] = f1[i] - f2[i] - b;
		b = d[i] < 0;
		if (b) d[i] += 10;
	}
	if (b) {
		int c = 1;
		for (int i = K; --i >= 0; ) {
			d[i] = 9 - d[i] + c;
			c = d[i] > 9;
			if (c) d[i] -= 10;
		}
	}
}

void print(const int *f)
{
	int n;
	for (n = K; --n > 0 && f[n] == 0; ) ;
	putchar(f[0] + '0'), putchar('.');
	for (int i = 1; i <= n; i++) putchar(f[i] + '0');
	putchar('\n');
}

int main(void)
{
	int a[K] = { 3, 1 , 4 }, b[K] = { 2, 7, 1 }, d[K];
	proc2(a, b, d);
	print(d);
	proc2(b, a, d);
	print(d);
}

処理3、処理4 と、問題のプログラムは自分で考えてみてください。

かずま · #3

処理3 を使うと、処理2 はもっと簡単になりますね。

コード:

#include <stdio.h>

#define K 51

int proc3(const int *f1, const int *f2)
{
	int i;
	for (i = 0; i < K-1 && f1[i] == f2[i]; i++) ;
	return f1[i] > f2[i];
}

void proc2(const int *f1, const int *f2, int *d)
{
	const int *x = f1, *y = f2;
	if (proc3(y, x)) x = f2, y = f1;
	int b = 0;
	for (int i = K; --i >= 0; ) {
		d[i] = x[i] - y[i] - b;
		b = d[i] < 0;
		if (b) d[i] += 10;
	}
}

void print(const int *f)
{
	int n;
	for (n = K; --n > 0 && f[n] == 0; ) ;
	putchar(f[0] + '0'), putchar('.');
	for (int i = 1; i <= n; i++) putchar(f[i] + '0');
	putchar('\n');
}

int main(void)
{
	int a[K] = { 3, 1 , 4 }, b[K] = { 2, 7, 1 }, d[K];
	proc2(a, b, d);
	print(d);
	proc2(b, a, d);
	print(d);
}

picusicu · #4

ありがとうございます！
一つのプログラムにまとめるにはどうしたらいいですか？

かずま · #5

処理4 はどう書きますか？

コード:

#include <stdio.h>

#define K (1 + 50)

void print(const int *f)
{
	int n = K;
	while (--n > 0 && f[n] == 0) ;
	putchar(f[0] + '0'), putchar('.');
	for (int i = 1; i <= n; i++) putchar(f[i] + '0');
	putchar('\n');
}

int input(int *f)
{
	char s[1024];
	if (!fgets(s, sizeof s, stdin) || s[0] < '0' || s[0] > '9') return 1;
	f[0] = s[0] - '0';
	int i = 1;
	if (s[1] == '.')
		for (; i < K && s[i+1] >= '0' && s[i+1] <= '9'; i++)
			f[i] = s[i+1] - '0';
	while (i < K) f[i++] = 0;
	return 0;
}

void proc1(int x, int y, int *f)  // f = x / y
{
	for (int i = 0; i < K; i++) f[i] = x / y, x = x % y * 10;
}

int proc3(const int *f1, const int *f2)  // f1 > f2
{
	int i;
	for (i = 0; i < K-1 && f1[i] == f2[i]; i++) ;
	return f1[i] > f2[i];
}

void proc2(const int *f1, const int *f2, int *d)  // d = | f1 - f2 |
{
	const int *x = f1, *y = f2;
	if (proc3(y, x)) x = f2, y = f1;
	int b = 0;
	for (int i = K; --i >= 0; ) {
		d[i] = x[i] - y[i] - b;
		b = d[i] < 0;
		if (b) d[i] += 10;
	}
}

void proc4(const int *f1, int *f2)  // f2 = f1
{
	// proc4 の実装
}

int main(void)
{
	int a[K], b[K], d[K], d2[K] = { 9, 9, 9 }, x2 = 1, y2 = 1;
	if (input(a)) return 1;
	for (int x = 1; x <= 999; x++) {
		for (int y = 1; y <= 999; y++) {
			proc1(x, y, b);       // b = x / y
			proc2(a, b, d);       // d = | a - b |
			if (proc3(d2, d)) {   // if (d2 > d)
				x2 = x, y2 = y;
				proc4(d, d2);     // d2 = d
			}
		}
	}
	printf("%d / %d = ", x2, y2);
	print(a);
}

これは、あくまでも参考となるプログラムのつもりです。
もっと分かりやすい書き方とか変数名などを工夫してください。

また、既約分数であることが証明できますか？
x と y を 6桁にするにはどうしたらいいと思いますか？

かずま · #6

処理4 はまだ書けないのでしょうか？
書けない場合は、書けないと返事をもらえないと先に進めません。

ところで、問題には、
「与えられる小数は，0 以上 10 未満であるものとする。
また，出力する分数は，既約分数に限るものとする。
具体的には，a.b1b2b3.........bk という形式の小数
(ここで，a, b1, b2, b3,..., bk は，それぞれ 1 桁の正の整数)」
とありますが、a や bk が正の整数だとすると 0 はダメで、
与えられる小数も 0 にできないのではないでしょうか？

もし、a や bk が 0～9 でよくて、小数として 0.0 を与えてよいのなら、
for (int x = 0; x <= 999; x++) { のように
x は 0 から始めないといけないでしょう。

かずま · #7

二重の forループで 999回ずつ実行すれば、その回数は約100万回です。
3桁なら何とかなりますが、6桁で 999999回ずつ実行すれば、
その回数はほぼ 1兆になり、結果が出るのに何日もかかるでしょう。

分子と分母を 6桁の整数でもよいようにするにはアルゴリズムの変更が必要です。
例えば、次のようになります。

コード:

#include <stdio.h>

#define K (1 + 50)

void print(const int *f)
{
	int n = K;
	while (--n > 1 && f[n] == 0) ;
	printf("%d.%d", f[0], f[1]);
	for (int i = 2; i <= n; i++) putchar(f[i] + '0');
	putchar('\n');
}

int input(int *f)
{
	char s[1024], *p;
	if (!fgets(s, sizeof s, stdin)) return 1;
	f[0] = strtol(s, &p, 10);
	if (p == s) return 1;
	int i = 1;
	if (*p == '.')
		while (i < K && *++p >= '0' && *p <= '9')
			f[i++] = *p - '0';
	while (i < K) f[i++] = 0;
	return 0;
}

void proc1(int x, int y, int *f)  // f = x / y
{
	for (int i = 0; i < K; i++) f[i] = x / y, x = x % y * 10;
}

int proc3(const int *f1, const int *f2)  // f1 > f2
{
	int i;
	for (i = 0; i < K-1 && f1[i] == f2[i]; i++) ;
	return f1[i] > f2[i];
}

void proc2(const int *f1, const int *f2, int *d)  // d = | f1 - f2 |
{
	const int *x = f1, *y = f2;
	if (proc3(y, x)) x = f2, y = f1;
	int b = 0;
	for (int i = K; --i >= 0; ) {
		d[i] = x[i] - y[i] - b;
		b = d[i] < 0;
		if (b) d[i] += 10;
	}
}

void proc4(const int *f1, int *f2)  // f2 = f1
{
	for (int i = 0; i < K; i++) f2[i] = f1[i];
}

void mul(const int *f, int y, int *x)  // x = f * y
{
	int c = 0;
	for (int i = K; --i > 0; ) c += f[i] * y, x[i] = c % 10, c /= 10;
	x[0] = f[0] * y + c;
}

int main(void)
{
	int a[K], x[K], b[K], d[K], d2[K] = { 1 }, x2 = 1, y2 = 1;
	if (input(a)) return 1;
	for (int y = 1; y <= 999999; y++) {
		mul(a, y, x);               // x = a * y
		if (x[0] > 999999) break;
		for (int i = 0; i < 2; i++) {
			proc1(x[0] + i, y, b);  // b = x / y
			proc2(a, b, d);         // d = | a - b |
			if (proc3(d2, d)) {     // if (d2 > d)
				x2 = x[0] + i, y2 = y;
				proc4(d, d2);       // d2 = d
			}
		}
	}
	printf("%d / %d = ", x2, y2);
	proc1(x2, y2, b);               // b = x / y
	print(b);
}

		8月 2025
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

少数を入力して分数を求めるプログラムです。

少数を入力して分数を求めるプログラムです。

Re: 少数を入力して分数を求めるプログラムです。

Re: 少数を入力して分数を求めるプログラムです。

Re: 少数を入力して分数を求めるプログラムです。

Re: 少数を入力して分数を求めるプログラムです。

Re: 少数を入力して分数を求めるプログラムです。

Re: 少数を入力して分数を求めるプログラムです。