プログラミングのお題スレ Part20
■ このスレッドは過去ログ倉庫に格納されています
>>465 惜しい >>468 IEEE754の倍精度(binary64)を整数演算で実装するのではありません。 binary64を二つ使って、上位53ビットと下位53ビットとで106ビットの浮動小数に見立てたものが double-double演算です。 Wikipediaの「四倍精度浮動小数点数」の項に少しだけ載ってますです。 > Wikipediaの「四倍精度浮動小数点数」の項に少しだけ載ってますです。 一般的な用語じゃないんだから初めからこれ書いとけよ 128ビットあるのに106ビットしか使わんの? もったいなくね? >>485 もったいなよ ただ、既存のdouble計算リソースが使えるという利点がある double-doubleはFMAがFMAとして役立つ数少ない用途だな 積和じゃなくて3個の和のfused命令も欲しくなる お題: 1つの整数から規則性のある複数の整数を生成せよ 生成される整数は再現性がなければならない >>489 function f: Integer -> Integer{ return 0; } >>489 Ruby def sequence( seed, number ) srand( seed ) Array.new( number ){ rand(100) } end p sequence( 123, 10 ) #=> [66, 92, 98, 17, 83, 57, 86, 97, 96, 47] p sequence( 123, 10 ) #=> [66, 92, 98, 17, 83, 57, 86, 97, 96, 47] >>486 ocaml https://ideone.com/NzF5f2 let f = let rec fib = function 0 -> 0 | 1 -> 1 | n -> fib (n - 1) + fib (n - 2) and aux acc = function -1 -> acc | m -> aux (fib m :: acc) (m - 1) in aux [] >>489 ocaml https://ideone.com/NzF5f2 let f = let rec fib = function 0 -> 0 | 1 -> 1 | n -> fib (n - 1) + fib (n - 2) and aux acc = function -1 -> acc | m -> aux (fib m :: acc) (m - 1) in aux [] >>488 Juliaのhypot()でもFMA使ってますです >>494 ただ積と和を1命令にして高速化しただけの積和 の効果だけじゃなくて 融合(fused)の効果が効く用途の話 [お題] 平均が2022な素数数列 5000以下のあい異なる素数で、加算平均がぴったり 2022 の数列を作る。 数列の項数(要素数)を最大化する、最大はいくつか。 最大数と数列を表示する。 ※解答例(もちろん4以上がある) 4 [1747, 2099, 2113, 2129] ※実行時間は素数生成を含めて、4秒以内 最大な数列は複数通りあると思うので、一例のみで 答えは595個? 計算機+理詰めで595個っぽいけど 「Log4j」2.17.0にもリモートコード実行の脆弱性 >>497 c++ https://ideone.com/UBbtWd "素数-2022"で適当に最大化DPすれば、合計0相当の所に答えが……。 個人的には他の復元方法を見たかった。 pythonは遅いのであきらめた(高速化方法を知らない) >>498 595個でした。手作業でできるレベルなら…… オレがやったのは p[n]をn番目の素数、 P[n]をn番目までの素数の集合、 s[n]をP[n]の和 a=2022として まず素数のn元集合で平均が1番小さくなるのはP[n]でその平均値s[n]/nは単調増加だからs[n]/n>aの時元数n以上の解はない s[596]/596>aは計算機で確認 なので595元集合で解があればそれが最大 s[595]/595<aなのでP[595]はダメ s[596]-595a = 1205525 - 1203090 = 2435は素数ではないのでP[597]から一個消すのはダメ s[597]-595a = 1209898 - 1203090 = 6808 はp597=4373以下の素数2459,4349の和で表すことができる よってP[597]\{2459,4349}の和は595aとなる 完全に全自動で探索するプログラムも作れそうだけど答え出たらもういいかなと手が止まってしまった 何個取り除いたら平均2022にできるか考えると 確か74個だったけな? JavaScriptで1秒もかかんなかったか 表示時間除いたら1秒かかってないな 探索はほぼ一回でボトムまで到達して 発見された 可能と不可能が極端に分かれている問題なので 事前のブランチカットだけが重要なヘンなお題w >>352 はまだ未解決 千葉興業銀行、4月から副業解禁 県内地銀初 南都銀行、4月から行員の副業制度導入 ウェブ制作など 荘内銀、行員の副業・兼業解禁 フィデアHD、副業・兼業制度を導入 横浜銀行、10月から従業員の副業・兼業解禁 鹿児島銀、副業解禁を検討 九州FGと肥後銀は10月導入 肥後銀行が副業制度導入へ 多様な働き方認める 10月から >>497 haskell https://ideone.com/GLMXRV >>501 のアルゴリズムを自動化してみた すげー簡単なところでどハマりして半日かかった まだ解なしの場合とかの動作チェックとかしてないけどもうどうでもいい ちなみに出力形式は (最大個数、最大素数の通し番号、最大素数までの間での素数で除外する素数のリスト) try 67%5 →(5,8,[2,3,5]) は最初の個数8個[2,3,5,7,11,13,17,19]から[2,3,5]を抜いた[7,11,13,17,19]の5個が平均が67/5になる素数のリストの一つ 長さ 6以上はない お題: xをゼロ以上の浮動小数点数として 2^floor(log2(x)) の計算。ただし、x == 0 の場合はゼロとする。 >>481 >binary64を二つ使って、上位53ビットと下位53ビットとで106ビットの浮動小数に見立てたものが >double-double演算です。 現在検討中ですが、binary64 中には仮数部に使用できるビット幅は 52 bits しかありません。つまりケチビット表現です 53+53 とのことですが、実際には 53 + 52 = 105 しか格納できないのではないでしょうか? >>510 上位の±1/2ulp相当が下位になります >>509 perlでワンライナー。入力は標準入力からする。 perl -MPOSIX -ne 'chomp;$n=$_?2**floor(log($_)/log(2)):0;print "$n\n"' でも、こんなので良いの?自分ではほとんど何も考えてないんだが。 (log2()がないからlog(n)/log(2)でやるって所ぐらいしか工夫がない) >>509 C++ 環境+コンパイルオプション依存 little endian, double = 64bit, long double = 128bit double fl2( double x ) { *( (uint64_t*) &x ) &= 0xFFF0000000000000LLU; return x; } long double fl2( long double x ) { *( (__uint128_t*) &x ) &= *( (__uint128_t*)"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xFF\xFF" ); return x; } 2進表記した時に先頭のビット以外を0にすればいいだけだがワンライナーで書ける気がしない 先頭のビットというより「(存在するなら)0じゃない一番位の大きいビット」だな ビットいじる方法だと、非正規化数が0に、NaNが無限大になる そういえば、無限大やNaNはどうすればいいのだろうか Python でかい値だとうまくいかないやつ def foo(x): _c = x * float(2 ** 52 + 1) _xh = c - (c - x) _if xh > x: return(xh * 0.5) _return(xh) >>516 深く考えてませんでしたw >>512 log2(n)をlog(n)/log(2)で近似した際の「誤差」 (ぴったり整数値になって欲しいのにそれよりも数ulp小さい値になったとか、 数ulp大きくて、ぎりぎりfloor()で切り捨てられる筈の値が1大きくなったとか) を補償するコードが欲しい。 そこは性能とトレードオフになるしかない気はする 例えばfloor( log 32 / log2 ) = 5が使用上の動作だけど log 32/log2 =4.9999999999978 × 10^0が返されて答えが4になってしまうのを避けるならおそらく大きすぎる場合は無視していいから res' = floor( log x / log2 ) if (2^res'* 1.5) < x // (1.5倍でも届かないなら不当な丸め誤差が出たと判断) then res = res' + 1 else res = res' とかちょっと汚い書き方するしかない希ガス なんか変なこと書いた res' = floor( log x / log2 ) if 2^res' < x then res = res' + 1 else res = res' やな res'の算出で丸め誤差は-1までと仮定して補正する しかしもちろんlog(x)とか2^nハード的にFPUとかで高速にやってくれてしかも整数演算は誤差なしでやってくれる前提 この辺は高級言語プログラマレベルの話でなんとかなるもんではない やるならアセンブリ言語レベルでやるしかない >>509 C https://ideone.com/5kDuzA 非正規化数、NaN、無限大とかはそのまま返すようにした やり方は>>513 と変わらない いまどきのコンパイラなら、frexp()やldexp()をいい塩梅に最適化してくれるのだろうか? from math import frexp, ldexp def foo(x): _m, e = frexp(x) _if m == 0: return 0.0 _return ldexp(0.5, e) >>509 またPerlでワンライナー。 perl -ne 'chomp;if($_<=0){print"0\n"}else{for(my$i=0;;$i++){if((1<<$i)>$_){print 1<<($i-1),"\n";last}}}' 今度は計算している内容から考えて結果が同じになるようにした。浮動小数点演算をしていない。 また整数値が何ビットであるかも考慮しておらず、Perlの整数が32bitだった場合は2^32以上の値を入力されたら多分うまく動かない。 当然64bitだったら2^64以上の値の入力で多分うまく動かない。 >>522 の修正 from math import frexp, ldexp def foo(x): return 0.0 if x == 0 else ldexp(0.5, frexp(x)[1]) >>509 またまたPerlでワンライナー。 perl -MPOSIX -ne 'chomp;if($_==0.0){print"0\n"}else{print ldexp(0.5,(frexp($_))[1]),"\n"}' これは>>524 の真似(ていうかやってること同じ)。 >>511 それは答えになっていないかと 質問を変えます。下位側の指数部も意味を持つようにインプリメントするべきでしょうか? >>526 先人の実装例だと、 上位 + 下位 = double doubleの数値 という事になってますね(上位側の指数が決まると、下位側の指数も決まる)。 tps://na-inet.jp/na/qd_ja.pdf 勿論、そう実装しないのもあり。 >>527 となると、 >>510 >binary64 中には仮数部に使用できるビット幅は 52 bits しかありません よって下位側指数部無視なら 53bit + 52 bit = 105bit の実装となりますが? 下位側指数部有意ならば、下位側にもケチビットを適用できますが、今度は仮数部が 106 ビットとはいいきれなくなりますね(数によって変わる) >>527 失礼 pdf が紹介されていることを見落としていました、精査します、紹介ありがとうございます お題: 1より小さい実数を1以上2より下にせよ < 0.123 > 1.23 < 0.0000123 > 1.23 お題: 質量0.2 kgの直方体の物体が摩擦のある水平な床の上にある。 物体の初速を右向きの0.5 [m/s]とすると、物体は転倒することなく底面が床に接したまま、約x秒後に自然停止した。xより垂直抗力F[N]と動摩擦係数kを求めよ。 重力加速度を 9.8 [m/s^2]とする。 お題(HTML/JavaScript): ユーザがGoogleから訪問した場合は、3秒間ブラウザを停止させるようにせよ。 お題: -1 < n < 1 の実数nを-10 < m < 10の実数m(ただし1桁目が0を除く)に桁上げせよ(>>530 の改良) < 0.123 > 1.23 < -0.00056 > -5.6 >>536 perl ワンライナー。以下はbashのコマンドラインから実行して試した。 入力は標準入力で一つづつ改行する。 perl -ne 'chomp;$n=$_;while(int(abs($n))<1){$n*=10}print "$n\n";' やってることは見ての通り殆ど何も考えず10倍し続けるだけ。 もうすぐ22日、今年は "22/2/22"といつもより多め [お題] 偶数ゾロ目 URLのページに都道府県別の人口が載っている。 URL: https://ideone.com/2w86hj 今回使用するのは、2020/10のデータ 同じ県は一回のみで、異なる県を 22 県選らぶ。 (単純な選び方は全部で NCR(47, 22) = 約14.8兆通り) 整数A,Bが与えられる(1<=A<=B<=1億) 選択した22県の人口合計が A以上B以下となるのは何通りか? 1) 44444444 44444444 --> 214209 2) 22222222 44444444 --> ? 3) 44444444 66666666 --> ? ※上の三問を全部で5秒程度で 想定解はあるが、もっとスマートな方法がありそう 「またか」と思った人、以前の問題とは想定解はかなり違う >>539 旬だと思って出題 https://ideone.com/2w86hj 下部に追加 半分全列挙 + 尺取り法 早い言語でしかできない解答例でした >>543 乙 時間取れなくてやれてないが季節感あるネタ好き お題: RustかGoでバイナリーサーチを実装してください お題: トライ木を使ってサジェスト機能を実装してください $ prog > w world would will wish 辞書は任意の大きさとする 入力は英語、または日本語とする >>545 なんかHaskellってGHCのオプションに-O2とか指定すれば結構早くなった記憶がある あとListじゃなくVector使うとか お題 バッタの大冒険 a(1),a(2),⋯,a(n) を相異なる正の整数とし、M を n-1個の正の整数からなる集合と する。また、M は s=a(1)+a(2)+⋯+a(n) を含まない。数直線の 0 の地点にいるバッタが 数直線の正の向きに n 回ジャンプする。 n 回のジャンプの距離は a(1),a(2),⋯,a(n) の並べ替えである。このとき並べ替えをうまく選べば、バッタがM の要素に対応するn-1点に一度も着地しないようにできることを証明せよ。 ↑数学オリンピックの問題 もちろん証明はどうでもよろしい お題は(ジャンプの幅のリスト、禁止点のリスト)から禁止点を交わしていく飛ぶ順を見つけるプログラムを実装せよです 入力 ([3,5,8],[5,10]) 出力 [8,5,3] #着地するのは8,13,16で禁止点5,10をかわしている 入力 ([5,6,8,10,13,15],[2,18,24,29,45]) 出力 [15,13,10,8,6,5] #着地するのは15,28,38,46,51で全ての禁止点をかわしている 入力 ([3,26,30,32,36,44,53,62,68,82],[36,40,59,79,92,126,178,233,394]) 出力 [82,68,62,53,44,36,32,30,26,3] #同文 2番目の例着地するのは 15,28,38,46,52,57 ですた >>549 は数学の問題としても面白いけどココはプログラムのお題スレなのでアルゴリズムそのもの考えるのは嫌な人のためにアルゴリズムひとつ紹介しておきます 以下の探索で線形オーダーで解を見つけられます 自分で考えたい人は無視してください 以下aを最大ジャンプとします a=a(n)としておく (A)一回目を最大ジャンプで飛んだとして最初の禁止点に届かないかギリギリ届くとき 一回目のジャンプが最大ジャンプしたと想定して残りのn-1回ジャンプで最初の禁止点を無視したn-2個の禁止点を交わしたジャンプ順b(1)...b(n-1)を作る この順番でとんて行って最初に最初の禁止点をi回目に超えたとする 解のジャンプとして b(1),b(2),...,b(i-1),a,b(i),...,b(n) とすると全ての禁止点をかわしている (B) 一回目を最大ジャンプで飛んだとすると最初の禁止点を超えて、しかも禁止点以外に着地できるとき 一回目のジャンプが最大ジャンプしたと想定して残りのn-1回ジャンプで最初の禁止点を無視したn-2個の禁止点を交わしたジャンプ順b(1)...b(n-1)を作る 解のジャンプとして a,b(1),...,b(n-1) とすると全ての禁止点をかわしている (C) 一回目を最大ジャンプで飛んだとすると最初の禁止点を超えるが別の禁止点に着地してしまうとき この状況だとa(1)〜a(n-1)のいずれかのジャンプa(i)でa(i)もa+a(i)のどちらも禁止点でないものが取れる( (∵) 全てのi:1〜n-1でa(i)かa+a(i)のどちらかが禁止点とするとこれだけでn-1個の禁止点全部尽くされてしまうけど、この中には最初の仮定である“一回目aで飛んだら禁止点”はこの中には出てこないので矛盾 ) それをa(n-1)としよう 最小の2回をa(n-1),a(n)と飛んだとしてこの時点で最初の禁止点と最初a(n)だと踏んでしまう禁止点の2点は超えているので残りの禁止点はn-3個以下しか残ってない そこでa(1)〜a(n-2)をうまく並べ替えれば全部かわすことができる 問題がよくわからなくて解く以前の所で停止。そしてやる気消滅。 説明不足で申し訳ない 問題文は数オリの紹介サイトからそのままコピペしてきたのでわかりにくかったかもしれない 1番最初の例 ([3,5,8],[5,10]) だとバッタは最初x=0の地点にいて+3,+5,+8のジャンプでx=16の地点に行こうとしている しかしx=5,x=10の地点は着地禁止地点で着地できない 飛び方は全部で6通りあるがその中から禁止地点に着地しないものを選んで下さいという問題 3回くらいなら総当たりで答え出せるけどジャンプ10回禁止地点9ヶ所だと全数検索すると10!通り必要になって実用にならない どうしますかというテーマだけどもちろん数学オリンピックの問題なので中々自分で答え出すのは難しい でここは数学板ではないので同じ数オリサイトにあった解答を転記して「こんなアルゴリズムが知られているけどアルゴリズムをインプリメントできますか」がお題です お題: C/C++でスレッドセーフなstrtok関数を作れ 設計は各自で考えること 高度IT人材、富士通は最大年収3500万円へ AI人材の獲得に超本気 NECが新人事制度を9人に適用、富士通は最大年収3500万円へ 【年収3500万円も】富士通、「ジョブ型」人事制度を導入 幹部社員から 高度IT人材 来年度から副業解禁 人材多様化へ―大同生命次期社長 第一生命HD、副業解禁 約1万5000人対象 第一生命HD、副業解禁 1万5000人対象―大手生保初 IHI、国内8000人の副業解禁 重厚長大企業も転機 IHI、社外兼業を解禁 社内副業もルール化 >>554 C言語 https://paiza.io/projects/xS5GP9DAU6KzhDsM6x7M6g strtok_r() を strtok_r2() の名前にして自分で実装した。 strsep() も paiza.io のCのライブラリには何故かなかったので strsep2() にして自分で実装した。 思い付きでお題考えてみた 検証してないんだけどどう? お題: ランダムな部屋を移動する最短距離を求める 行列がある 任意の横幅Wと高さHで表現される部屋がランダムに1 <= N <= 5個生成される この部屋を部屋内の座標からランダムに選択した別の部屋の部屋内の座標まで通路を作る 通路の要素は斜めには生成されず横と縦に生成される 通路はランダムに1つの部屋から0 <= R <= 3生成される 各部屋を各通路で繋げ任意の部屋Aと任意の部屋Bを選択する このときAからBまでの最短経路を求めよ さらに、閑古鳥をよびよせるか [お題] 多倍長では無理!? 整数 S, T が与えられる。(1 <= S <= T <= 400万) S以上T以下の(連続する)整数の最小公倍数(LCM)をもとめる 答えは, 1000000007(10億7)の余りで出力 1) 6 8 --> 168 6,7,8 の最小公倍数、LCM(6, 7)= 42 --> LCM(42, 8)= 168 2) 10 30 --> 89546497 剰余前は、2329089562800 3) 2567890 3456789 --> ? 4) 1 4000000 --> ? √T以下の素数列挙 各数を素因数分解して各素数の指数の最大を求める 10億7の剰余で上の乗算を行う >>562 https://ideone.com/O9PQbN 想定解としては、(他の人同様) 求める最小公倍数を素因数分解した形に作るイメージ 400万以下の"素数及び素数べき乗"は、高々28.3万件。 S以上T以下で、素数べき乗が割り切れるかどうかチェックしている。 (方法は T/素数べき乗 > (S-1)/素数べき乗 ならあると, O(1)判定) ボトルネックは素数を求める部分なので、手抜きしている。 余談) ・4)を多倍長で計算すると173万桁だった(一分程度ででた) ・10^9+7 ではなく、下9桁を出力だと、4)は 0になる(5^9が範囲にあるから) お題: 文字列が整数だったらINT, 実数だったらFLOATと出力するプログラムを作れ 変換できない場合はINVALIDと出力せよ 123 -> INT 1,234 -> INT 1.23 -> FLOAT a123 -> INVALID 12abc -> INVALID 1.23.435 -> INVALID >>570 Ruby f = -> s { case s when /\A(?:0|[1-9]\d*)\z|\A(?:[1-9]\d{0,2})(?:,\d{3})*\z/ :INT when /\A(?:0?|[1-9]\d*)\.\d+\z/ :FLOAT else :INVALID end } %w[123 1,234 1.23 a123 12abc 1.23.435 .142857 1. 0 01 1,234,567 1234,567].each{|s| puts '%s -> %s' % [s, f[s]] } # => 123 -> INT 1,234 -> INT 1.23 -> FLOAT a123 -> INVALID 12abc -> INVALID 1.23.435 -> INVALID .142857 -> FLOAT 1. -> INVALID 0 -> INT 01 -> INVALID 1,234,567 -> INT 1234,567 -> INVALID >>570 こう言うのは仕様をちゃんと提示してよ 123. 123.0 12,34 はどうなればいいのか そんな文句みたいな言い方するほどか? 他の問題に比べたらケースちゃんと提示してる方だし そういうのは想定してないってなんとなくわかるだろ 競プロならちゃんと定義必要だろうけど >>574 > そういうのは想定してないってなんとなくわかるだろ お題なんだから想定しろよ でないとそのケースはそうじゃなくてこうすべきとか言う奴が出てきて荒れる元だし ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.4 2024/05/19 Walang Kapalit ★ | Donguri System Team 5ちゃんねる