プログラミングのお題スレ Part13
■ このスレッドは過去ログ倉庫に格納されています
お題1: 現在地の緯度、経度を出せ 緯度:、、、、 経度:、、、、 お題2: 東京都新宿区西新宿2丁目8-1 の緯度、経度を出せ 緯度:、、、 経度:、、、 お題3: お題2で求めた緯度経度から住所を出せ 郵便番号:、、、 住所:東京都、、、、 >>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号 平方数の判定は、たとえば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 >>4 平方根求められる関数と、少数を整数にする関数があれ 途中で送っちゃった。。。 あれば簡単。 def isSqr(x): if sqrt(x) - int(sqrt(x)) == 0: return True else: return False def sqrt(x): return (x ** 0.5) >>7 ならば a=12345.678*12345.678 print('答え',a == (a**0.5) **2) #結果 True たとえば1000桁のを1000回、判定するとかsqrtでは時間かかるやつの高速化だろ >>8 なにが「ならば」か分からんけど。。。 引く必要なかったし、ifの中身をそのまま返せば良かった。 def isSqr(x): return (sqrt(x) == int(sqrt(x))) >>9 だったらそういう問題の出し方にしないと。 例えば、1から1億までの間の数字で平方根数は何個あるか。 かかった時間と、PC 環境を示せ また、処理できる最大に近い数字を示せ。 とかかな。 浮動小数経由する実装だと整数部が53bit超えると判定出来ない(つまり64bit整数以上だと不適切) だから自前で浮動小数を経由せずに平方根の整数部分を求めることを考えるわけだけどナイーブにやると計算量が線型になるから二分探索やNewton(-Raphson)法で計算量減らすことを考えるわけだ >>13 >>7 で64ビット以上の数も判定出来てるけど。。。 (0が偶数ならTrue、奇数ならFalse) 小数点以下が0か(n.0かn.41421356みたいな形か)どうか見てるだけだし。 この辺はsqrt関数の性能に依存するだろうけど。 n = 100000000000000000000 m = 10000000000000000000 print(isSqr(n)) print(isSqr(m)) 出力 True False >>14 100000000000000000001がtrueになったりはしない? >>14 無能 たまたま判定出来るケースだけ抽出してるだけじゃねぇか >>13 それもわかる。 だったら解き方の最初にこういう目的で解いたとか書かないとね。 だから、解ける最大数値も書いたら良いと書いたんだが。 ちなみに、>>1 の1億までの数字は、iPhoneで28秒だった。 >>15 False になるよ。iphone のpythonista また、言われたようにバイナリサーチ法や、巨大数のバイナリー検索も試してみたが、単純検索よりずっと時間がかかった。 ま、これは言語にもよると思うから何とも言えないが。 スクリプト系はステップ数が短い方が効率は良さそうだな。 >>18 だからさ、どこまでやるか条件を出せよ。 そしてサンプルを示してみたら? 実行時間も入れて。 プログラムと言うのは、使う現場で目的が違うんだから目的がわからなければ良い悪いなんて言えないだろ。 アホ過ぎて話になんねー 線型探索と二分探索のどっちが速いかが言語によるとか頭腐ってんのか 線型探索: ttps://ideone.com/De3SOQ 二分探索: ttps://ideone.com/v9Twjx >>19 寝てる間にフォローありがとう。 >>15 こっちはiPhoneのモバイルC内蔵のPythonだが、trueなった。 Haskellは63ビットだからかもう少し早い段階でなる。 ただ、>>19 の言う通り実用上問題無いのでは。 (階乗と違って入力より巨大な数が帰るわけじゃないし、Cとかだと十分実用かと) 64ビットまでの数では効率的なバージョンと、それ以上の数も対応するバージョンという感じではどうか。 sqrtも、n乗根は似た作りになるし。 # n√x def sqrtn(n,x): return (x ** (1/n)) どちらかと言うと**演算子(Cで言うpower関数)の実装に興味あるな。 CRC 16bit 左送り 初期値 0x0000 生成多項式0x11021 テーブル使用せず演算でなるべくスマートに 平方数 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 >>26 同じ条件でバイナリサーチをやってみると若干だけ早かったが、誤差の範囲 #結果 5.770102000000406 秒 count= 525 #範囲 99999999999990000000 100000000000010000000 >>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) いや、intにしてないからそれを調べてるってわけじゃないのか >>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型に最大値はない(上限なし)からどんな数でも扱える。 >>30 これ(count=49151)って99999999999999975424から100000000000000024575 (64bit浮動小数点数の16進表記で0x4415AF1D78B58C3Fから0x4415AF1D78B58C41)の平方根が、 10000000000 (64bit浮動小数点数の16進表記で0x4202A05F20000000)になって全部Trueになってるってことだろ 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符号なし整数にしか対応してません」っつうなら分かるがまともに判定出来てないのに「判定出来てる」主張する無能 やれ前提書けだの環境書けだの時間書けだのクソみてぇな御託並べる前に自分の頭の悪さを自覚しろ >>34 申し訳ない。 2〜3日前にpython をiPhoneに入れて使い始めてただただ練習のためにお題を使わせてもらってた。 整数と、浮動小数の最大値にまで頭が回らなかった。 今日初めてWindowsにpythonを入れた状態で本当に気が回らなかった。 本当に申し訳ない。 バイナリサーチの方は1個と出るが、時間が膨大にかかる。 自然数の割り算関数mydivと余り関数mymodを作れ。 >>36 これでいいの?javascript const myDiv = (a, b) => ~~(a / b) const myMod = (a, b) => a % b modをみる nが平方数なら、n=x^2 だが、n=x^2 (mod m)でもある 逆にmod で平方数でなければ、元々も平方数ではない mod 3だと0 1 は平方数だが、2はちがう。3i + 2 は平方数にはならない >>38 元は小学生にプログラミングを通じて、割り算への理解を深めてもらえないかと考えたんで、単純に演算子を置き換えて欲しくないかも。。。 小学生の時テストで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 >>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 掛け算は簡単だけど除算は結構面倒 ttps://ideone.com/EheeYM >>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 >>45 同じ条件で2分探索法でやると 5.5秒かかった。 Wikipediaに Integer square root https://en.wikipedia.org/wiki/Integer_square_root があり、その中の 2.1 Using bitwise operations の二つを試してみたが、 最初のrecursive call を使った方が 1.65秒 次の方が 2.05秒 早いことは早いが、>>42 >>45 のビットシフト法の方がかなり早い。 0.22秒 gmpのisqrt は早そうだが Pythonistaでは使えないので試していない。 >>4 そう言う記述を度々見るんだが、具体的なプログラムを提示してくれない? なんでも放題にすればいい お題 平方数は 256で割るとあまりの パターンが44種類になるという。 この44種類を求める。 python {(x**2) % 256 for x in range(0,256)} Ruby p 0x100.times.map{|i| i*i&0xFF}.uniq.sort # => [0, 1, 4, [...], 233, 241, 249] javascript [...new Set(function*(){for(let i=0;i<256;i++)yield i*i%256}())].sort((a,b)=>a-b) >>50 その44種(mod256)の中に x%256 が一致するか python mod256=sorted({(i**2)%256 for i in range(256)}) x=123*123 print(x%256 in mod256) # True これでmod の話が理解できた。 要は完全な平方数じゃないのは平方根の計算をしないと言う話ね。 >>50 Perl5 %a = map{$_=>1} map{$_*$_%256} 0..256; @a = keys %a; print "@a\n"; 実行結果 ~ $ perl 13_50.pl | wc -w 44 $ perl 13_50.pl 137 89 161 57 1 4 100 17 36 49 121 64 68 144 201 177 65 185 16 9 193 169 129 105 196 132 25 73 249 209 33 233 225 97 41 81 241 164 145 228 217 0 153 113 >>50 Perl5 その2 use List::MoreUtils 'uniq'; @a = uniq map{$_*$_%256} 0..255; print "@a\n"; >>49 有難う。 python だが、 # 256, 9, 5, 7, 13, 17 97 のmodであらかじめカットしたら、5倍くらい早くなった。 因みに >>50 のお題で mod256=sorted({(i**2)%256 for i in range(256)}) と modn = lambda n:set((i**2)%n for i in range(n)) mod256 = modn(256) では下のsetを使った方が3割くらいスピードが速かった。 >>59 # 256, 9, 5, 7, 13, 17 97 なんて順番ははおかしいんじゃねと思って、 大きい順にカットしたら、更に2割以上早くなった。 >>50 J 64個の平方数を調べれば44種類のパターンはそろうようだ。 /:~ ~. 256| *: i. 64 お題 ある数 n とする。 下位から24bit区切りの数を足し合わせてからmod 2^24-1 した数が、元の数nのmod 2^24-1 と一致することを確認しなさい。 >>62 任意の n に対してある自然数 N, 自然数列{a_k} が存在して n = Σ_{k = 0}^{N} a_k * 2^(24 * k) と書けるので mod 2^24 - 1 として n = Σ_{k = 0}^{N} a_k * 1^k = Σ_{k = 0}^{N} a_k ■ >>59 ,60 256はmodじゃなくて&255を取る 確率的には大きい順じゃなくて9,97,17,13,7,5が良いのでは? 9,97,17,13,7,5でmodを取る場合、大きい数からそのままmodを取るのではなく2^48-1でmodを取った数値に対してmod これで速度どうなる? mod 255にしたら遅くなるんじゃねーの 0 < n mod 255 < 254 だぞ 0 <= n mod 255 <= 254 だった >>62 python # n%(2**24-1) を求める def mod224get(n): bn=(n.bit_length()+7)//8 #byte長 bb=n.to_bytes(bn,'little') s= sum([int.from_bytes(bb[i:i+3],'little') for i in range(0,bn,3) ]) #24bit毎の合計 return s%(2**24-1) v0=12345678901234567890 #v0=0 n=v0**2 loop = 100000 print('テスト範囲は ',n,'〜',n+loop-1,'loop回数=',loop) start =time.process_time() for i in range(n,n+loop): if mod224get(n) != n%(2**24-1) :print('間違い見っけ',n) end =time.process_time() print('全問正解 かかった時間は、',end-start,'秒') # ―― 結果 テスト範囲は 152415787532388367501905199875019052100 〜 152415787532388367501905199875019152099 loop回数= 100000 全問正解 かかった時間は、 0.2963889999999765 秒 >>64 アドバイスありがとう。 それは思ったんだけど、現代の言語がそんなところで手抜きはしていないだろうと信じてテストしていなかった。 今、&255 に変えてテストしてみたけど、スピードの差はなかった。 そう言う発想は昔は非常に重要だったけど、今は言語の中で吸収してるみたいだね。 その下のアドバイスに対しては、何故ご自分では試されないのですか? あまりやるつもりはないのは、mod 2**24-1 と言うのが理解できていないからです。 これで早くなるのなら色々試してみたいんですが、このリストを作るだけでもかなりの時間がかかりめげてます。 >>70 剰余の順番に関しては確率がこんなんだからやで 3 / 5 = 0.600000 4 / 7 = 0.571429 4 / 9 = 0.444444 7 / 13 = 0.538462 9 / 17 = 0.529412 49 / 97 = 0.505155 テーブルは9, 97, 17, 13, 7, 5の物で良いんやで? 多倍長整数の剰余より32bit整数/64bit整数の剰余のほうが計算量が少ないから、 (32bitの場合) 2^24-1で剰余を取ったものに対して9, 17, 13, 7, 5の剰余で平方数かどうかを調べる (64bitの場合) 2^48-1で剰余を取ったものに対して9, 97, 17, 13, 7, 5の剰余で平方数かどうかを調べる なしてこんなことができるかってーと、 2^24-1(=16777215)の因数に5, 7, 9, 13, 17が、2^48-1(=281474976710655)の因数に5, 7, 9, 13, 17, 97含まれているからやで >>71 あまり深入りするつもりはないけど、mod 2**24-1 でチェックしたら、 mod 9, 97, 17, 13, 7, 5 でチェックする必要はないと言う事? ま、数学を解いてるつもりは全くなく、プログラムの練習だからいかに沢山の人が素晴らしいプログラムを見せてくれるかにしか興味はない。 プログラムを書かない人は自分にとってはなんの意味もない。 >>72 ちゃうねん mod 2**24-1をした数値に対してmod 9, 17, 13, 7, 5 でチェックするねん もしくはmod 2**48-1をした数値に対してmod 9, 97, 17, 13, 7, 5 でチェックするねん >> 73 2重に剰余を取るのはGMPみたく多倍長なら意味があるけど, 32/64bit固定長ならあまり意味はない 複数回剰余を確認する必要があるから多倍長から固定長(32/64bit)にしていて, 更に因数を使えば剰余を求めるための除算の代わりに乗算が使えるから因数の多い2^24 - 1や2^48 - 1を採用してる >>62 ガウス少年が見出したように Σ1,2,…,n-2,n-1=n *(n +1) /2 なので、 n の mod 2^24-1 と Σ1,2,…,n-2,n-1 =n *(n +1) /2 の mod 2^24-1 が等しいのは自明だと思うけど、 そういう、ちょっとした数学を使わず Σ1,2,…,n-2,n-1 をloopで和を算出し mod 2^24-1 して比較する n の mod 2^24-1 と比較する プログラムを作れという題なんだろうか… >>75 「比較する」を二度書いちゃった、訂正 Σ1,2,…,n-2,n-1 の和をloopで算出し mod 2^24-1 して n の mod 2^24-1 と比較する >>75 お題をよく読んだら? 24bit = 3バイト毎に取り出してその合計に対して 2**24-1 をしなさいと言う問題だよ。 数学なんて関係ない。 ただ出されたお題をプログラムで解いてくれ。 >>75 ごめん Σ1,2,…,n-2,n-1=n *(n +1) /2 は間違えた。こうだ Σ1,2,…,n-2,n-1=n *(n -1) /2 ある数nのビット表記方法によって一致する/しないを答えればいいのかな >>62 Perl5 use bignum (l=>GMP); use feature say; sub sum24 { my $v = $_[0]; if ($v > 0) { my $d = int($v / 2**24); my $m = $v % 2**24; # $v - $d * $f6; $m + sum24($d); } else { 0; } } $n = 12345678901234567890; say $n % (2**24 -1); say sum24($n) % (2**24 -1); 実行結果 ~ $ perl 13_62.pl 13189905 13189905 >>81 8行目後半の#から右 # $v - $d * $f6; は削除し忘れたcommentです スマソ >>83 自明もへったくれもない。 プログラムが正しいかどうかの確認だよ。 プログラムも書かないで能書きだけ垂れてもなんの足しにもならない。 ここはプログラムのお題スレだよ。 >>62 のお題は前スレのGMP の整数平方根の説明の文章の中から取り出したもの。 つまり、ここまでできると、次は n**2%(2**24-1) のリストを作れと言うお題になるんだろうけど、時間がかかりすぎるからお題にするのはやめた。 このリストができないと実際の平方数の高速チェックが出来ないじゃん。 しかしここまで複雑な処理をして本当に早くなるのかどうか疑問だけどな。 mod 2**24-1 って結構時間がかかりそうな気がする。 >>85 一番能書き垂れてんのお前だろ クソみたいな御託並べる前に自分のことを考えろっつったろうが GMPが一体どこで > n**2%(2**24-1) のリスト なんか使ってんだ?91で割った場合のテーブルでさえ12byte必要だってのにどうやってそんな巨大なテーブル用意するんだ? GMPの中身なんか数学の成果の塊だぞ?お前が数学したくないだか出来ないだか知らんがアルゴリズム考えるようなスレでクソみたいなこと喋ってんじゃねぇよ お前はコードを書いても価値がない 単なるbitmaskで済まない様な場合 あるいは除算して剰余を求めるなら さんざ研究されていると思うから自力で1から考える前に 先人の業績を知れってことだろ アバヨ ノシ お題:ポーカーダイス 通常のサイコロを5個振って出た目をポーカーの役になぞってそれぞれの出現確率を求める。 役は、5カード、4カード、ストレート、フルハウス、3カード、2ペア、1ペア、ブタ(ノーペア) 例えば出た目が 1,1,3,1,4 ならスリーカード。2,5,4,6,3 ならストレート。 5カードは6/(6^5)、4カードは(5*5*6)/(6^5)というように数学的に 求めても難しくはないのですが、ここはプログラミングのスレなので 全通り力技でチェックして求めてみてください。 解答例:C言語 https://ideone.com/4X62Am 6^5総当りせよってか… native compiler系言語で力技か python3 https://ideone.com/k6Ea4j 最後の出力部分はpython 3.6以降だと for k,v in hand.items(): print("{} :\n {} / 7776 ({} %)".format(k,v, round(100*v/7776,2))) でいけるけど実行環境が3.5なのでやむなく なんか数学でもできる力技お題増えてきたな もっとプログラミングじゃないとできないような良いお題無いんだろうか 確率の問題でも特定の疑似乱数と種を使った偏りを求めるとかは数学では難しい お題: 日本語文字とカッコ { } とスラッシュ(/)で構成された入力文字列Sが与えられる。{ }で囲まれ、かつ スラッシュで区切られた部分文字列について、それぞれ場合分けを行って、複数の文字列のリストに展開して改行区切りで出力せよ。 カッコの対応が間違っている場合はERRORを出力せよ。 (例1) {ひまわり/あさがお}は{植物/花}です。 (出力結果) ひまわりは植物です。 あさがおは植物です。 ひまわりは花です。 あさがおは花です。 なお、展開の順序については問わない。カッコがなくなるまで繰り返し展開せよ。 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる