[過去ﾛｸﾞ]
プログラミングのお題スレ Part13 (1002ﾚｽ)
プログラミングのお題スレ Part13 http://mevius.5ch.net/test/read.cgi/tech/1549160513/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
62: デフォルトの名無しさん [sage] 2019/02/10(日) 12:16:48 ID:8pY6FeJB お題 ある数 n とする。 下位から24bit区切りの数を足し合わせてからmod 2^24-1 した数が、元の数nのmod 2^24-1 と一致することを確認しなさい。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/62
63: デフォルトの名無しさん [sage] 2019/02/10(日) 12:27:09 ID:Mq5me4ef >>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 ■ http://mevius.5ch.net/test/read.cgi/tech/1549160513/63
69: デフォルトの名無しさん [sage] 2019/02/10(日) 15:12:41 ID:95x0uvij >>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 秒 http://mevius.5ch.net/test/read.cgi/tech/1549160513/69
75: デフォルトの名無しさん [sage] 2019/02/11(月) 00:35:41 ID:8Hdd2FlG >>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 と比較する プログラムを作れという題なんだろうか… http://mevius.5ch.net/test/read.cgi/tech/1549160513/75
81: デフォルトの名無しさん [sage] 2019/02/11(月) 01:42:54 ID:8Hdd2FlG >>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 http://mevius.5ch.net/test/read.cgi/tech/1549160513/81
85: デフォルトの名無しさん [sage] 2019/02/11(月) 02:15:34 ID:HnU/OI7o >>83 自明もへったくれもない。 プログラムが正しいかどうかの確認だよ。 プログラムも書かないで能書きだけ垂れてもなんの足しにもならない。 ここはプログラムのお題スレだよ。 >>62 のお題は前スレのGMP の整数平方根の説明の文章の中から取り出したもの。 つまり、ここまでできると、次は n**2%(2**24-1) のリストを作れと言うお題になるんだろうけど、時間がかかりすぎるからお題にするのはやめた。 このリストができないと実際の平方数の高速チェックが出来ないじゃん。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/85
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.046s