AIZU ONLINE JUDGE (AOJ) - 0021 について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
vow256
記事: 13
登録日時: 1年前
連絡を取る:

AIZU ONLINE JUDGE (AOJ) - 0021 について

#1

投稿記事 by vow256 » 1年前

AIZU ONLINE JUDGE (AOJ) の 0021 に関して質問です。
問題に対し、以下のようなコードを作成しました。

コード:

#include <iostream>
using namespace std;

#define m1 (y2 - y1) / (x2 - x1)
#define m2 (y4 - y3) / (x4 - x3)

int main() {
	int n;
	double x1, y1, x2, y2, x3, y3, x4, y4;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
		if (m1 == m2) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}
自動審判で誤答と判定されたため別の方の解き方などを参考にしてみたのですが、
"abs" や "1e-10" を多くの方が解答に使っておられました。
double 同士の計算で誤差が出ることはあるのでしょうか。
もし誤差がないとしたら何故 "abs" や "1e-10" が使われているのでしょうか。
このコードの改善点なども一緒に指摘していただきたいです。

かずま

Re: AIZU ONLINE JUDGE (AOJ) - 0021 について

#2

投稿記事 by かずま » 1年前

誤差はあります。

コード:

#include <iostream>
using std::cout;

int main()
{
	if ((0.3 - 0.0) / (0.1 - 0.0) == (0.13 - 0.1) / (0.11 - 0.1))
		cout << "YES\n";
	else
		cout << "NO\n";
	double a = (0.3 - 0.0) / (0.1 - 0.0);
	double b = (0.13 - 0.1) / (0.11 - 0.1);
	cout.precision(20);
	cout << a << "\n";
	cout << b << "\n";
	if (abs(a - b) < abs(a) * 1e-15)
		cout << "YES\n";
	else
		cout << "NO\n";
}
実行結果

コード:

NO
2.9999999999999995559
3.0000000000000013323
YES

アバター
vow256
記事: 13
登録日時: 1年前
連絡を取る:

Re: AIZU ONLINE JUDGE (AOJ) - 0021 について

#3

投稿記事 by vow256 » 1年前

なるほど。誤差は生じるものなのですね。
イマイチ誤差が生じる理由を掴めていないので、
もう少し勉強しなおしてきます。
ご丁寧にありがとうございました。

かずま

Re: AIZU ONLINE JUDGE (AOJ) - 0021 について

#4

投稿記事 by かずま » 1年前

誤差が生じるのは、小数の値を正確に表現できないからです。

8ビットのデータを整数だとすると、
次のように 256種類の値を誤差なく表現できます。

コード:

	00000000 = 0
	00000001 = 1
	00000010 = 2
	00000011 = 3
	  :
	11111110 = 254
	11111111 = 255
8ビットのデータを小数だとすると、
次のように 256種類の値を表現できます。

コード:

	0.00000000 =   0/256 = 0.00000000
	0.00000001 =   1/256 = 0.00390625
	0.00000010 =   2/256 = 0.00781250
	0.00000011 =   3/256 = 0.01171875
		:
	0.00011001 =  25/256 = 0.09765625
	0.00011010 =  26/256 = 0.10156250
		:
	0.11111110 = 254/256 = 0.99218750
	0.11111111 = 255/256 = 0.99609375
10進の 0.1 は 25.6/256 なので、表現できません。
仕方がないので、0.1 は 0.00011010 = 26/256 = 0.1015625000 で代用します。
0.0015625 の誤差があります。

実際には float は 24ビット、double は 53ビットの精度があるので、
次のような近似値で代用されます。

コード:

#include <stdio.h>

int main()
{
	printf("  float:  %g = %.20g\n", 0.1f, 0.1f);
	printf("  double: %g = %.20g\n", 0.1, 0.1);
}
実行結果
  float:  0.1 = 0.10000000149011611938
  double: 0.1 = 0.10000000000000000555

アバター
vow256
記事: 13
登録日時: 1年前
連絡を取る:

Re: AIZU ONLINE JUDGE (AOJ) - 0021 について

#5

投稿記事 by vow256 » 1年前

なるほど。そういうことだったんですね。
ご丁寧にありがとうございます。
誤差があるとなると今まで作ってきたプログラムの中にも
不備があったりするかもですね。
今一度確認してみます。

返信

“C言語何でも質問掲示板” へ戻る