質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

2回答

409閲覧

AtCoder Beginner Contest 131 C - Anti-Division

consomme

総合スコア11

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

1グッド

1クリップ

投稿2019/06/22 14:07

前提・実現したいこと

プログラミング初心者です。
AtCoder Beginner Contest 131 C - Anti-Division が不正解となるの理由がわかりません。

不正解となるコード

Python3

1import fractions 2 3a,b,c,d=map(int, input().split()) 4 5def lcm(x, y): 6 return (x * y) // fractions.gcd(x, y) 7 8x =int(b/c)-int(((a-1)/c)) 9y =int(b/d)-int(((a-1)/d)) 10n =lcm(c,d) 11xy=int(b/n)-int(((a-1)/n)) 12 13ans = (b-a+1) - (x+y-xy) 14print(ans) 15

正解となるコード

Python3

1import fractions 2 3a,b,c,d=map(int, input().split()) 4 5def lcm(x, y): 6 return (x * y) // fractions.gcd(x, y) 7 8x =(b//c)-(((a-1)//c)) 9y =(b//d)-(((a-1)//d)) 10n =lcm(c,d) 11xy=(b//n)-(((a-1)//n)) 12 13ans = (b-a+1) - (x+y-xy) 14print(ans)

質問項目

違いは商の小数を切り捨てる際に、intを使うか//を使うかです。
この2つの方法で行う計算は何が異なりますか?

LouiS0616👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

hayataka2049

2019/06/22 15:07

BA頂いて申し訳ないのですが、LouiS0616さんの回答の方が良さそうなので、そちらに付け直していただけないでしょうか?
guest

回答2

0

ベストアンサー

int(a / b) と a // b が等しく無いのは、確かに直感に反しますね。
興味深い質問です。

小数点以下の丸め方は同じか?

双方は小数点以下の丸め方が異なります。

//負の無限大に向かって丸める
int()0に向かって丸める

商が負の数になったとき、丸め方が異なることになります。
しかしリンク先の制約を見る限り、負の数が与えられることは無さそうです。

この推測はハズレです。

それでは、全く同じと言って良いか?

ダメです。

c = int(a / b) は、実際には次のように解釈されています。

Python

1f = a / b 2c = int(f)

このときfは整数型ではなく浮動小数型です。
int(a/b) と a//b は同じに見えても、前者は浮動小数を経由しているのです。

この差異に原因が隠れていそうです。

浮動小数点数の誤差

Pythonを含み多くのプログラミング言語では、浮動小数をIEEE形式に基いて表現しています。
この方式は軽量に広いケタの数を表現できるのですが、巨大な数を扱う際は誤差が出得ます。

例えば、このように。

Python

1>>> n = 9007199254740993 2>>> n 39007199254740993 4>>> float(n) 59007199254740992.0

結論

割り算の結果が浮動小数表現で表せない巨大な数の場合、a//b と int(a/b) の値は変わり得る。

投稿2019/06/22 15:06

LouiS0616

総合スコア35658

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

hayataka2049

2019/06/22 15:08

ああ、有効桁数の絡みですか。10^18だから確かに引っかかりますね。
guest

0

intについて

浮動小数点数については、これは 0 に近い側へ切り捨てます。
https://docs.python.org/ja/3/library/functions.html#int

//について

/ (除算: division) および // (切り捨て除算: floor division) は、引数同士の商を与えます。数値引数はまず共通の型に変換されます。整数の除算結果は浮動小数点になりますが、整数の切り捨て除算結果は整数になります; この場合、結果は数学的な除算に 'floor' 関数 を適用したものになります。
https://docs.python.org/ja/3/reference/expressions.html#binary-arithmetic-operations

とりあえず一つ確実に思いつく違いを挙げておくと、演算結果が負値のときは違う挙動になるでしょう。

python

1>>> int(-10/3) 2-3 3>>> -10//3 4-4 5

でも問題の制約で負にはならないですね。なので、この理由ではなさそうです。

本当の理由については検討中。

LouiS0616さんの回答にある通り、floatの有効桁数の絡みのはずです。

pythonのfloatは内部的には64bit浮動小数点数型で、10進数としての有効桁数は15桁です。ですから、10^18なんて桁数の数字は正確には表せません。

一方整数型は任意精度演算をサポートしますので、問題の扱うレンジの数字を正確に表現でき、演算結果も正確なものが得られるのだと思います。

投稿2019/06/22 15:04

編集2019/06/22 15:12
hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問