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

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

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

1(5): 2019/02/03(日)11:21 ID:72eosYJ+(1/3)調 AAS
プログラミングのお題スレです。

【出題と回答例】
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/

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

※前スレ
2chｽﾚ:tech

2(1): 2019/02/03(日)11:24 ID:72eosYJ+(2/3)調 AAS
お題1: 現在地の緯度、経度を出せ
緯度:、、、、
経度:、、、、
お題2: 東京都新宿区西新宿2丁目8-1 の緯度、経度を出せ
緯度:、、、
経度:、、、
お題3: お題2で求めた緯度経度から住所を出せ
郵便番号:、、、
住所:東京都、、、、

3: 2019/02/03(日)11:36 ID:72eosYJ+(3/3)調 AAS
>>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号

4(3): 2019/02/03(日)13:16 ID:jFMT64Yy(1/2)調 AAS
平方数の判定は、たとえば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

5: 2019/02/03(日)17:42 ID:oUppVF8S(1)調 AAS
>>1
乙

6: 2019/02/03(日)18:09 ID:I0qputsI(1/4)調 AAS
>>4
平方根求められる関数と、少数を整数にする関数があれ

7(2): 2019/02/03(日)18:10 ID:I0qputsI(2/4)調 AAS
途中で送っちゃった。。。

あれば簡単。

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

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

8(1): 2019/02/03(日)19:44 ID:t6DUu8Hq(1)調 AAS
>>7 ならば
a=12345.678*12345.678
print('答え',a == (a**0.5) **2)
#結果 True

9(1): 2019/02/03(日)20:21 ID:jFMT64Yy(2/2)調 AAS
たとえば1000桁のを1000回、判定するとかsqrtでは時間かかるやつの高速化だろ

10(1): 2019/02/03(日)20:45 ID:I0qputsI(3/4)調 AAS
>>8
なにが「ならば」か分からんけど。。。

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

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

11: 2019/02/03(日)21:02 ID:Hf9VDUPT(1/2)調 AAS
>>9 だったらそういう問題の出し方にしないと。

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

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

とかかな。

12: 2019/02/03(日)21:37 ID:MY6f7I+S(1)調 AAS
なんか変なのいるね

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

15(2): 2019/02/03(日)23:09 ID:CD+d7Abc(1/2)調 AAS
>>14
100000000000000000001がtrueになったりはしない？

16: 2019/02/03(日)23:21 ID:CD+d7Abc(2/2)調 AAS
>>14
https://ideone.com/IntAcn

17: 2019/02/03(日)23:32 ID:J7OBWIJA(1)調 AAS
>>14
何言ってんのおまえ

18(1): 2019/02/03(日)23:38 ID:v4AFDwkt(2/2)調 AAS
>>14
無能
たまたま判定出来るケースだけ抽出してるだけじゃねぇか

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

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

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

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

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

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

20: 2019/02/04(月)01:09 ID:tmXRmKR0(1)調 AAS
このお客さんはどこから来たんだ

21: 2019/02/04(月)01:42 ID:8qZo3rbs(1/2)調 AAS
アホ過ぎて話になんねー
線型探索と二分探索のどっちが速いかが言語によるとか頭腐ってんのか

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

22: 2019/02/04(月)06:56 ID:eX/1kX5o(1/3)調 AAS
>>19
寝てる間にフォローありがとう。

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

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

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

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

23: 2019/02/04(月)07:03 ID:eX/1kX5o(2/3)調 AAS
どちらかと言うと**演算子(Cで言うpower関数)の実装に興味あるな。

24: 2019/02/04(月)07:23 ID:958Z8DnZ(1)調 AAS
CRC 16bit 左送り初期値 0x0000 生成多項式0x11021
テーブル使用せず演算でなるべくスマートに

25: 2019/02/04(月)08:07 ID:jp+X9sqK(1)調 AAS
指数関数，正弦関数，余弦関数のベキ級数展開（マクローリン展開）

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

http://www.synchronature.com/Science/Euler.html

26(2): 2019/02/04(月)10:14 ID:AyF9PYpz(1/2)調 AAS
平方数 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

27(1): 2019/02/04(月)10:28 ID:AyF9PYpz(2/2)調 AAS
>>26 同じ条件でバイナリサーチをやってみると若干だけ早かったが、誤差の範囲

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

28(1): 2019/02/04(月)11:40 ID:GcH+yasd(1/4)調 AAS
>>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)

29: 2019/02/04(月)11:43 ID:GcH+yasd(2/4)調 AAS
いや、intにしてないからそれを調べてるってわけじゃないのか

30(2): 2019/02/04(月)14:12 ID:NdPuZxEw(1)調 AAS
>>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型に最大値はない（上限なし）からどんな数でも扱える。

31: 2019/02/04(月)14:13 ID:fIIhQCXR(1)調 AAS
もういいからお前

32: 2019/02/04(月)14:20 ID:GcH+yasd(3/4)調 AAS
>>30
いや、誤差出てるやん

33: 2019/02/04(月)14:55 ID:GcH+yasd(4/4)調 AAS
>>30
これ(count=49151)って99999999999999975424から100000000000000024575 (64bit浮動小数点数の16進表記で0x4415AF1D78B58C3Fから0x4415AF1D78B58C41)の平方根が、
10000000000 (64bit浮動小数点数の16進表記で0x4202A05F20000000)になって全部Trueになってるってことだろ

34(1): 2019/02/04(月)15:39 ID:8qZo3rbs(2/2)調 AAS
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符号なし整数にしか対応してません」っつうなら分かるがまともに判定出来てないのに「判定出来てる」主張する無能
やれ前提書けだの環境書けだの時間書けだのクソみてぇな御託並べる前に自分の頭の悪さを自覚しろ

35(1): 2019/02/04(月)18:19 ID:TMO26aZK(1)調 AAS
>>34 申し訳ない。 2〜3日前にpython をiPhoneに入れて使い始めてただただ練習のためにお題を使わせてもらってた。
整数と、浮動小数の最大値にまで頭が回らなかった。
今日初めてWindowsにpythonを入れた状態で本当に気が回らなかった。
本当に申し訳ない。

バイナリサーチの方は1個と出るが、時間が膨大にかかる。

36(2): 2019/02/04(月)20:37 ID:WZY4HG/d(1)調 AAS
自然数の割り算関数mydivと余り関数mymodを作れ。

37: ◆QZaw55cn4c 2019/02/04(月)20:41 ID:CLpqTC7n(1)調 AAS
>>36
C++ 多桁長演算（加減乗除）の一環として、mpz_class との互換を目指していました
2chｽﾚ:tech

38(1): 2019/02/04(月)20:50 ID:Ly7rB5Pz(1)調 AAS
>>36
これでいいの？javascript
const myDiv = (a, b) => ~~(a / b)
const myMod = (a, b) => a % b

39: 2019/02/04(月)21:00 ID:mK0I6q3a(1)調 AAS
modをみる
nが平方数なら、n=x^2 だが、n=x^2 (mod m)でもある
逆にmod で平方数でなければ、元々も平方数ではない

mod　3だと0　1　は平方数だが、2はちがう。3i + 2　は平方数にはならない

40: 2019/02/04(月)22:02 ID:eX/1kX5o(3/3)調 AAS
>>38
元は小学生にプログラミングを通じて、割り算への理解を深めてもらえないかと考えたんで、単純に演算子を置き換えて欲しくないかも。。。

41(1): 2019/02/05(火)10:18 ID:ij/1zyvC(1)調 AAS
小学生の時テストで0点をもらった間違った割り算の
やり方をプログラムにしてみた。
--Lua
function myDivMod(a, b)
local r = 0
while a > 0 do
a = a - b
r = r + 1
end
return r, -a
end
print(myDivMod(10,3))
実行結果
4 2

42(2): 2019/02/05(火)12:28 ID:aE6b0ZPr(1)調 AAS
>>35 結局　整数のsqrt を作って、範囲の中に納まる最小最大の整数のsqrt を取り出し、その差（+1）がその範囲の中にある平方数の個数と言う作りにした。
ポイントとなった整数のsqrt が秀逸だったのでここに書いておく。　どんなに巨大な数字でも数回のシフト操作だけで終わるから極端にスピードが速い。
ソースは、gist.github.com/bnlucas/5879594

# integer square root
def isqrt_2(n):
　if n < 0:
　　raise ValueError('Square root is not defined for negative numbers.')
　x = int(n)
　if x == 0:
　　return 0
　a, b = divmod(x.bit_length(), 2)
#divmod(a, b)は(a // b, a % b)のタプルを返す。
#平方数は半分のビット数以下だからそれを最大値で計算開始
　n = 2 ** (a + b)
　while True:
　　y = (n + x // n) >> 1 #1bit右にシフト
　　if y >= n:
　　　return n
　　n = y

-----------------
#結果 0.0 秒 count= 1000000000
#範囲　　 999999999000000000000000000000000000 1000000001000000000000000000000000000
#入力bit_length()=120　入力bit_length()=120
平方数範囲 999999999500000000 1000000000499999999
上の二乗　 999999999000000000250000000000000000 1000000000999999998249999999000000001

43: 2019/02/05(火)12:33 ID:NCwCR2JI(1)調 AAS
>>41
おしいなw

44: 2019/02/05(火)13:45 ID:jFne2R1T(1)調 AAS
掛け算は簡単だけど除算は結構面倒
https://ideone.com/EheeYM

45(2): 2019/02/05(火)18:45 ID:63VtM8MC(1)調 AAS
>>42 の isqrt_2 を使ったパフォーマンステスト。
次のようなのを継ぎ足してテストした。例によってインデント部は全角空白に変換してるから、逆変換しないと動かない。

def isSqrt(n):
　return n == isqrt_2(n)**2

v0 = 12345678901234567890
v = v0**2 # 整数平方される対象の数値
loopc = 100000 # をこの回数繰り返す。

isqr=0
start =time.process_time()
for i in range(loopc): isqr=isqrt_2(v)
end =time.process_time()

print('#整数平方(v)の結果',end-start,'秒')
print(' 繰返し数の回数',loopc),print(),print('#v0　　　',v0)
print('#v=v0**2=',v),
print('#isqrt(v)',isqr)
print('#上の**2',isqr**2)
print('対象数vのビット数',v.bit_length(),'bit')
print('vが平方数かどうかの判定',isSqrt(v))
-----
#整数平方(v)の結果 0.22398700000002236 秒
繰返し数の回数 100000

#v0　　　 12345678901234567890
#v=v0**2= 152415787532388367501905199875019052100
#isqrt(v) 12345678901234567890
#上の**2 152415787532388367501905199875019052100
対象数vのビット数 127 bit
vが平方数かどうかの判定 True

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

あと 957 ﾚｽあります
ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.068s