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

**デフォルトの名無しさん** · 2019/02/03(日) 11:21:53.20

プログラミングのお題スレです。

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文
　　結果がある場合はそれも

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

※前スレ
https://mevius.2ch.net/test/read.cgi/tech/1538096947/

**デフォルトの名無しさん** · 2019/02/03(日) 11:24:10.97

お題1: 現在地の緯度、経度を出せ
緯度:、、、、
経度:、、、、
お題2: 東京都新宿区西新宿2丁目8-1 の緯度、経度を出せ
緯度:、、、
経度:、、、
お題3: お題2で求めた緯度経度から住所を出せ
郵便番号:、、、
住所:東京都、、、、

**デフォルトの名無しさん** · 2019/02/03(日) 11:36:46.42

>>2 python (pythonista)
#お題1
import location
location.start_updates() # GPSデータ更新を開始
gps=location.get_location() # GPSデータを取得する
location.stop_updates()# GPSデータ更新を終了
print('お題1')
print('緯度:'+str(gps['latitude']))
print('経度:'+str(gps['longitude']))
#お題2
address_dict = {'Street': '西新宿2丁目8-1'}
gc = location.geocode(address_dict)[0]
print('お題2')
print('緯度:'+str(gc['latitude']))
print('経度:'+str(gc['longitude']))
#お題3
adr = location.reverse_geocode(gc)[0]
#print(adr)
print('お題3')
print('郵便番号:'+str(adr['ZIP']))
print('住所:'+str(adr['State'])+str(adr['City'])
+str(adr['Street']))
#結果
お題1
緯度:35.7----略
経度:139.6---略
お題2
緯度:35.689504
経度:139.6916833
お題3
郵便番号:160-0023
住所:東京都新宿区西新宿2丁目8番1号

**デフォルトの名無しさん** · 2019/02/03(日) 13:16:33.45

平方数の判定は、たとえばmod 10だと、
1と4と5と6と9に限るってのを利用すると、違う場合は判定が速いんだろ。
mod n で複数やる。

1=1^2
4=2^2
9=3^2
6=4^2
5=5^2
6=6^2
9=7^2
4=8^2
1=9^2

**デフォルトの名無しさん** · 2019/02/03(日) 17:42:03.97

>>1
乙

**デフォルトの名無しさん** · 2019/02/03(日) 18:09:22.12

>>4
平方根求められる関数と、少数を整数にする関数があれ

**デフォルトの名無しさん** · 2019/02/03(日) 18:10:24.69

途中で送っちゃった。。。

あれば簡単。

def isSqr(x):
if sqrt(x) - int(sqrt(x)) == 0:
return True
else:
return False

def sqrt(x):
return (x ** 0.5)

**デフォルトの名無しさん** · 2019/02/03(日) 19:44:56.44

>>7 ならば
a=12345.678*12345.678
print('答え',a == (a**0.5) **2)
#結果 True

**デフォルトの名無しさん** · 2019/02/03(日) 20:21:31.21

たとえば1000桁のを1000回、判定するとかsqrtでは時間かかるやつの高速化だろ

**デフォルトの名無しさん** · 2019/02/03(日) 20:45:32.58

>>8
なにが「ならば」か分からんけど。。。

引く必要なかったし、ifの中身をそのまま返せば良かった。

def isSqr(x):
return (sqrt(x) == int(sqrt(x)))

**デフォルトの名無しさん** · 2019/02/03(日) 21:02:27.70

>>9 だったらそういう問題の出し方にしないと。

例えば、1から1億までの間の数字で平方根数は何個あるか。かかった時間と、PC 環境を示せ

また、処理できる最大に近い数字を示せ。

とかかな。

**デフォルトの名無しさん** · 2019/02/03(日) 21:37:11.53

なんか変なのいるね

**デフォルトの名無しさん** · 2019/02/03(日) 21:40:28.27

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

**デフォルトの名無しさん** · 2019/02/03(日) 22:02:19.65

>>13

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

n = 100000000000000000000
m = 10000000000000000000

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

出力

True
False

**デフォルトの名無しさん** · 2019/02/03(日) 23:09:07.55

>>14
100000000000000000001がtrueになったりはしない？

**デフォルトの名無しさん** · 2019/02/03(日) 23:21:43.21

>>14
https://ideone.com/IntAcn

**デフォルトの名無しさん** · 2019/02/03(日) 23:32:49.30

>>14
何言ってんのおまえ

**デフォルトの名無しさん** · 2019/02/03(日) 23:38:52.32

>>14
無能
たまたま判定出来るケースだけ抽出してるだけじゃねぇか

**デフォルトの名無しさん** · 2019/02/03(日) 23:57:14.35

>>13 それもわかる。だったら解き方の最初にこういう目的で解いたとか書かないとね。
だから、解ける最大数値も書いたら良いと書いたんだが。

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

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

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

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

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

**デフォルトの名無しさん** · 2019/02/04(月) 01:09:58.80

このお客さんはどこから来たんだ

**デフォルトの名無しさん** · 2019/02/04(月) 01:42:54.31

アホ過ぎて話になんねー
線型探索と二分探索のどっちが速いかが言語によるとか頭腐ってんのか

線型探索: ttps://ideone.com/De3SOQ
二分探索: ttps://ideone.com/v9Twjx

**デフォルトの名無しさん** · 2019/02/04(月) 06:56:02.27

>>19
寝てる間にフォローありがとう。

>>15
こっちはiPhoneのモバイルC内蔵のPythonだが、trueなった。
Haskellは63ビットだからかもう少し早い段階でなる。
ただ、>>19 の言う通り実用上問題無いのでは。
(階乗と違って入力より巨大な数が帰るわけじゃないし、Cとかだと十分実用かと)

64ビットまでの数では効率的なバージョンと、それ以上の数も対応するバージョンという感じではどうか。

sqrtも、n乗根は似た作りになるし。

# n√x
def sqrtn(n,x):
return (x ** (1/n))

**デフォルトの名無しさん** · 2019/02/04(月) 07:03:50.35

どちらかと言うと**演算子(Cで言うpower関数)の実装に興味あるな。

**デフォルトの名無しさん** · 2019/02/04(月) 07:23:18.46

CRC 16bit 左送り初期値 0x0000 生成多項式0x11021
テーブル使用せず演算でなるべくスマートに

**デフォルトの名無しさん** · 2019/02/04(月) 08:07:18.20

指数関数，正弦関数，余弦関数のベキ級数展開（マクローリン展開）

http://www.synchronature.com/Science/Resources/e-s-c.jpg
http://www.synchronature.com/Science/Euler.html

**デフォルトの名無しさん** · 2019/02/04(月) 10:14:05.68

平方数 64ビット以上の巨大数
pythonista iPhone XS Max

def chk2(v1,v2):
　c = 0
　for i in range(v1, v2+1):
　　if i == (i**0.5) **2: c += 1
　return c

v = 100000000000000000000
r = 10000000
v1= v-r
v2= v+r

start_time=time.clock()
c = chk2(v1,v2)
end_time=time.clock()
print('#結果',end_time-start_time,'秒','count=',c)
print('#範囲 ',v1,v2)

#結果 5.777779999999893 秒 count= 525
#範囲 99999999999990000000 100000000000010000000

**デフォルトの名無しさん** · 2019/02/04(月) 10:28:47.91

>>26 同じ条件でバイナリサーチをやってみると若干だけ早かったが、誤差の範囲

#結果 5.770102000000406 秒 count= 525
#範囲 99999999999990000000 100000000000010000000

**デフォルトの名無しさん** · 2019/02/04(月) 11:40:45.86

>>26-27
99,999,999,999,990,000,000~100,000,000,000,010,000,000の範囲には10,000,000,000しかないんだからcount=525ってのは演算誤差が出てるってことだよな？

99,999,999,980,000,000,001 (9,999,999,999^2)
100,000,000,020,000,000,001 (10,000,000,001^2)

**デフォルトの名無しさん** · 2019/02/04(月) 11:43:01.09

いや、intにしてないからそれを調べてるってわけじゃないのか

**デフォルトの名無しさん** · 2019/02/04(月) 14:12:20.36

>>28 言われてみればフロートまでカウントするのはおかしいから判定を変えた。

　for i in range(v1, v2+1):
　　if (i**0.5).is_integer(): c += 1
　return c

Core i3 3.2GHz Windows10　python3.7
#結果 8.15625 秒 count= 49151
#範囲 99999999999990000000 100000000000010000000

iPhoneの方が倍くらい早いかな。
#結果 4.180858 秒 count= 49151

Core i7のマシンもあるが大して期待できなさそうだな。

検算の意味で、1から1000までをカウントして31だったから正しいだろう。
なお、Python3の整数int型に最大値はない（上限なし）からどんな数でも扱える。

**デフォルトの名無しさん** · 2019/02/04(月) 14:13:11.15

もういいからお前

**デフォルトの名無しさん** · 2019/02/04(月) 14:20:39.50

>>30
いや、誤差出てるやん

**デフォルトの名無しさん** · 2019/02/04(月) 14:55:46.83

>>30
これ(count=49151)って99999999999999975424から100000000000000024575 (64bit浮動小数点数の16進表記で0x4415AF1D78B58C3Fから0x4415AF1D78B58C41)の平方根が、
10000000000 (64bit浮動小数点数の16進表記で0x4202A05F20000000)になって全部Trueになってるってことだろ

**デフォルトの名無しさん** · 2019/02/04(月) 15:39:51.36

99,999,999,980,000,000,001 = 999,999,999^2
100,000,000,000,000,000,000 = 10,000,000,000^2
100,000,000,020,000,000,001 = 10,000,000,001^2
なんだから[99'999'999'999'990'000'000, 100'000'000'000'010'000'000]の区間に入る平方数はただ一つ100,000,000,000,000,000,000しかない

「32bit符号なし整数にしか対応してません」っつうなら分かるがまともに判定出来てないのに「判定出来てる」主張する無能
やれ前提書けだの環境書けだの時間書けだのクソみてぇな御託並べる前に自分の頭の悪さを自覚しろ