プログラミングのお題スレ Part13

[過去ﾛｸﾞ] プログラミングのお題スレ Part13 (1002ﾚｽ)
上下前次1-新
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

13(2): 2019/02/03(日)21:40 ID:v4AFDwkt(1/2)調 AAS
浮動小数経由する実装だと整数部が53bit超えると判定出来ない(つまり64bit整数以上だと不適切)
だから自前で浮動小数を経由せずに平方根の整数部分を求めることを考えるわけだけどナイーブにやると計算量が線型になるから二分探索やNewton(-Raphson)法で計算量減らすことを考えるわけだ

14(4): 2019/02/03(日)22:02 ID:I0qputsI(4/4)調 AAS
>>13

>>7で64ビット以上の数も判定出来てるけど。。。
(0が偶数ならTrue、奇数ならFalse)
小数点以下が0か(n.0かn.41421356みたいな形か)どうか見てるだけだし。
この辺はsqrt関数の性能に依存するだろうけど。

n = 100000000000000000000
m = 10000000000000000000

print(isSqr(n))
print(isSqr(m))

出力

True
False

19(1): 2019/02/03(日)23:57 ID:Hf9VDUPT(2/2)調 AAS
>>13 それもわかる。だったら解き方の最初にこういう目的で解いたとか書かないとね。
だから、解ける最大数値も書いたら良いと書いたんだが。

ちなみに、>>1 の1億までの数字は、iPhoneで28秒だった。

>>15 False になるよ。iphone のpythonista

また、言われたようにバイナリサーチ法や、巨大数のバイナリー検索も試してみたが、単純検索よりずっと時間がかかった。ま、これは言語にもよると思うから何とも言えないが。スクリプト系はステップ数が短い方が効率は良さそうだな。

>>18 だからさ、どこまでやるか条件を出せよ。そしてサンプルを示してみたら？実行時間も入れて。

プログラムと言うのは、使う現場で目的が違うんだから目的がわからなければ良い悪いなんて言えないだろ。

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.039s