プログラミングのお題スレ Part18
■ このスレッドは過去ログ倉庫に格納されています
>>553 Ruby $><<gets.sub(/\d+(?=\D+$)/, &:succ) # => IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoim M3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOn xhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfP sQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuu UBGLGuFToYptzqjkfdAoxAqqmeQO8PVcUS >>553 Perl コマンドラインで以下のように入力後に標準入力から文字列を読ませると標準出力に出力される。 perl -pe 's/(\d+)(\D+)$/($1+1).$2/ge' あるいはファイルに内容を入れておいてそのファイルを指定する。 js window.prompt().replace(/\d(?=\D+$)/,i=>i*1+1) >>556 行末が数字のときに対応できない perl -pe 's/(\d+)(\D*)$/($1+1).$2/e' のほうがよくないかな >>511 その場合の良いアルゴリズムって 「素因数分解を早く解くアルゴリズム」 よね。 それがもし思いついたらフィールズ賞ものではw >>553 haskell theStr = "B0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO7PVcUS" f x = let (a,b) = span (\x-> (x<'0') || (x>'9')) $ reverse x c = show $ (+1) $ read $ return $ head b in reverse $ a++c++(tail b) main = do print $ f theStr >>558 そうだった。 + じゃなくて * だったな。 >>559 素因数分解まで行かない。 素でなくてもいいので因数のうちイチバン大きいもの。 なんかいい解法見つけられないか、考えているけどいまのところ見出せていない いや、違うな… 因数のうちイチバン大きいものでは、ダメだわ 初出題 数学板の問題より 5つのサイコロの1〜6の面がそれぞれ赤白黄青緑にそれぞれ ["byrbwg", "yrgwbb", "gbrwwy", "gyrbww", "gbrybw"] と塗り分けられている この状態では1-6を天地の軸として2〜5の側面にはそれぞれ ["yrbyb","rgrrr","bwwby","wbwwb"] となっている それぞれのサイコロを適当に回転させて全ての側面にrwybgがちょうど一回ずつとなるようにしたい そのような回転の組み合わせは何通りか 本質的に同じものを重複して数えるのを避けるために最初のサイコロの回転は ・動かさない ・1→2,2→3,3→1,4→6,5→4,6→5 ・1→3,2→1,3→2,4→5,5→6,6→4 の3つのうちどれかのみを許すとする (出力) ["yrbgbw","gbybrw","bgwryw","bygwwr","bwrygb"] ["yrbgbw","gbybrw","wywrgb","rwgwyb","bgrywb"] ["rbywgb","gyrbbw","wwgyrb","ygbrww","brwgyb"] ["rbywgb","wybrbg","wwgyrb","wgrbwy","brwgyb"] >>568 君が何を言わんとしているのかが全くわからない。 >>509 Perl5、>>567 にヒントを貰った通り√を使ってnaiveに書くと… use POSIX 'ceil'; for $n (81, 87, 91) { $r = ceil sqrt $n; for ($r..$n) { $i = $_; last until $n % $_; } print "$n => $i\n" } 実行結果 ~ $ perl 18_509_99_naive.pl 81 => 9 87 => 29 91 => 13 計算量の少ないもう少しカッチョイイ方法を見出せればなぁ… >>568 です やはりちょっと伝わらないですね >>568 は取り下げます >>572 計算量減らすなら√n以下の最大の約数d求めてn/dを出力すれば計算量は減るな イヤnが素数の場合に√nから上むきに探索すると計算量はnになるけど下向きなら√nになる √n以上の約数と√n以下の約数は同数だけど整数そのものは下側には√nしかなく、上にはn-√nあるので下向きに探していった方が速い ポラード・ロー法使えばもっと計算量は減る 素数判定と組み合わせればモンテカルロ法ではなくラスベガス法になるから、正当性も担保される 素因数分解利用するなら素因数分解そのものが手早くできてもダメでしょ? それを何個か使って最も√nに近いもの探すのはかなり難しいんじゃなかったっけ? つまり素因数分解n=Πpi^eiが与えられたとして、つぎは 0≦xi≦eiを動かすときΣxi log(pi) が1/2 log(n)に最も近くなるものを決定しなければならない コレなんか名前ついてる問題で指数オーダーのアルゴリズムしか見つかってないんじゃなかったっけ? 素因子の数はlog(n)のオーダーで増えていくから、結局exp(c log(n)) のオーダーになって、cがどれくらいに収められるか、そもそも指数オーダー必要なのかも未解決なんじゃなかったっけ? >>579 √n以上の最小の約数をdとして上むき探索に必要な時間はすうがく/d-√n\、下向き探索のそれは\√n-n/d/ (/〜\と\〜/はfloorとceiling) 差は/d-√n\-\√n-n/d/ =\d+n/d-2√n/はam≧gmと\〜/の広義単調性から0以上で上むき探索は素数であるか否かに限らず常に計算量は同じかそれ以上 素数であるか予備検査しても結局上向きに探索したら計算量は同じ以上かかる あ、間違えた 上向き探索の探索量はd-/√n\+1=/d-√n+1\で/~\はceiling 下向き探索の探索量は\√n/-n/d+1=\√n-n/d+1/で\~/はfloor まぁ常に上向きの方が計算量は増える まぁもちろんnをまともに素因数分解して>>578 みたいな方法で√nオーダーより真に早いのがあるなら上向きも下向きもないけど、もうそこまで行ったら研究者レベルの話でしかない気がする >>550-551 短いこの間でダークサイドに堕ちてて草 >>582 お詫び→弁解→言い訳→逆ギレ 冷静に書いてたつもりが書いてくうちに興奮して見事なコンボを決めたようだ 気分を変えてまた数学板より 自然数nに対して格子点の集合{(a,b) | a,bは1〜nの整数}の中の相異なる4点の組みで同一円周上に並ぶものの個数を数え上げよ n:1〜8では [0,1,14,194,826,2491,6364,14564] のハズ >>585 ちなみにn=3の場合の14個は 1×1の正方形:4個 2×2の正方形:1個 √2×√2の正方形:1個 2×1の長方形:4個 4辺が1,1,√2,2√2の等脚台形:4個 の14個 >>585 https://ideone.com/L3IoWm {0,1,14,184,762,2257,5704,13040}と出たんだが どっちが合ってる? 一直線上にある4点の組を余分に数えたところ >>585 の解と一致した https://ideone.com/GUZoZL [0,1,14,184,762,2257,5704,13040] が正解ですね https://ideone.com/YULQQ4 >>591 n=3だと ●●◯ ◯●● ◯◯◯ ◯◯◯ ●●◯ ◯●● ●●◯ ◯●● ◯◯◯ ◯◯◯ ●●◯ ◯●● ●◯● ◯◯◯ ●●◯ ◯●● ●◯● ●◯● ◯◯◯ ◯◯◯ ◯◯◯ ●◯● ●●◯ ◯●● ●●◯ ◯●● ◯◯● ●◯◯ ◯◯● ●◯◯ ◯◯● ●◯◯ ◯◯● ●◯◯ ●●◯ ◯●● ●◯● ◯●◯ ◯◯◯ ●◯● ●◯● ◯●◯ の14通り >>585 のお題は、 平面上に4点を選んだとき、その4点をすべて含む円周が存在する場合としない場合がある xy平面上に、x,yの各座標が1〜nの整数であるような、互いに異なる点を4つ選んだとき、4点すべてを含む円周が存在するものがいくつあるか? n=1〜8についてそれぞれ数え上げよ (註:n=1のときは異なる4点を選べないので、解は0でよい) ってことでいいかな? >>594 正解だと思う おそらくn=9までは [0,1,14,184,762,2257,5704,13040,25996] 今作ってるのはC[n^2,4]を全数検査してるのでO(n^8)で計算量増えるので二桁以上はしんどいorz 対象性を考慮する以外の計算量の削減手段はないのかねこの手の問題は 解決すべき課題は計算量の削減ばかりではないだろうけれどさ まぁ何に重きを置くかですな 数学板でこの手のプログラムが必要になるのは誰も答え持ってなくて、一応答えは出てるけど確認したいときとか その時は速度より“確実に正しい”事の方が重要になる この場合も対称性やら、明らかに無駄な可能性を排除すれば速度は上がるけど“確実に正しい”のかは怪しくなってしまう 実務でプログラム使う人もその辺のtpoは意識してるのでは?、 コード汚くても高速な奴も募集中 >>594 に挙げられている184通りのうち、その3/4にあたる138通りが、直径が√10のものである そのうち、円の中心が図の中央にあるものは、候補となる点が8個あるので、8C4 = 70 通りある。 図の中央から(±1,0)または(0,±1)ずれたものは、候補となる点が6個なので4×(6C4)=60通り 図の中央から(±2,0)または(0,±2)ずれたものが、候補となる点が4個なので4×(4C4)=4通り 図の中央から(±1,±1)ずれたものが、候補となる点が4個なので4×(4C4)=4通り 合わせて 70+60+4+4=138 通りと数え上げることができる 図の中央を基準にすることができるものばかりとは限らないところには注意が必要だが 総当たりよりは効率化が見込めると思われる。 >>509 Python3, >>576 を参考に計算量を√nに減らした解法 import math for n in [81, 87, 91, 13]: s = math.sqrt(n) f = n for i in reversed(range(2, 1 + math.floor(s))): q, m = divmod(n, i) if m == 0: f = q; break print(n, '=>', f) 実行結果 ~ $ python 18_509_99_rootn.py 81 => 9 87 => 29 91 => 13 13 => 13 もっとスマートな解法を考えていると双曲線を意識した解法を意識してしまうが、 簡単には解けない数学の問題に突き当たると思う >>600 × 意識した解法を意識してしまうが、 ○ 意識した解法を思い浮かべてしまうが、 お題: アッカーマン関数の引数が与えられるので、計算過程を1ステップずつ出力してください 入力: 2 1 出力: A(2, 1) A(1, A(2, 0)) A(1, A(1, 1)) A(1, A(0, A(1, 0))) A(1, A(0, A(0, 1))) A(1, A(0, 2)) A(1, 3) A(0, A(1, 2)) A(0, A(0, A(1, 1))) A(0, A(0, A(0, A(1, 0)))) A(0, A(0, A(0, A(0, 1)))) A(0, A(0, A(0, 2))) A(0, A(0, 3)) A(0, 4) 5 >>605 Haskell astr m n = "A(" ++ m ++ "," ++ n ++ ")" ack' 0 n = (n+1, [astr (show 0) (show n), (show $ n+1)]) ack' m 0 = let (val, ss) = ack' (m-1) 1 in (val, (astr (show m) (show 0)) : ss) ack' m n = let (val1, ss1) = ack' m (n-1) (val2, ss2) = ack' (m-1) val1 ss = [astr (show $ m-1) s | s <-ss1] ++ (tail ss2) in (val2, (astr (show m) (show n)):ss) ack m n = map (++"\n") $ snd $ ack' m n main = do [x,y]<-(return.(map read).words)=<<getLine mapM_ putStr $ ack x y >>607 いや、上手な人ならもっと上手くやるはず アホほどライブラリがあってそれ使えば楽々のハズだけど修行中の身ではこんなもんorz >>606 ちょっとチューンナップ 達人なら***とか>>>とか意味わからん演算子使ってもっとスッキリ書くんだろうけどアホほどあって使いこなせんorz haskell ---- astr m s = "A(" ++ (show m) ++ "," ++ s ++ ")" ack 0 n = [astr 0 $ show n, show $ n+1] ack m 0 = (astr m $ show 0) : ack (m-1) 1 ack m n = let ss1 = ack m (n-1) in [astr m $ show n] ++ (map (astr (m-1)) ss1) ++ (tail $ ack (m-1) (read $ last ss1)) main = do [x,y]<-(return.(map read).words)=<<getLine mapM_ ((putStr).(++"\n")) $ ack x y お題: 野球のボールの動きを物理シミュレートして、ピッチャーの投げてきたボールをより遠くにかっ飛ばすバッターAIを開発せよ。 >>610 ─┼─┐─┼─ / ,. `゙''‐、_\ | / / │ │─┼─/| _,.イ,,.ィ' ─────‐‐‐ * ←>>蟻人間 │ |ツ │ | | | イン /´⌒`ヽ // | \ {, リ) / ./ | \ __ /}从、 リ( / / | ,. ,. -‐===‐- `つ/ ,.イ ’^ソハノリ / ∵|:・. 〃〃〃〃 //ミノ__ /´ /∴・|∵’ ヽ_I__I__I__I__I_I __ノ_/ / ヽミ、、 .∵.;|∵’:; ー{____,,二二二ニ) ノΘ(__ ) ゙ 、∵.;|∵’, /I I I I I I .^^^' \ !  ̄フ ゙ 、 |∴ ソ / ` ノ⌒ヽ') / ノ/ / /\/ ∧/ / ', / / ノ./ ./ ', ノ/ ヘ__、 ./ / ̄ ̄ ̄ヽ .', ヘ_'_, / \ / ', / \/ ', ゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙ ゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙゙ >>605 Perl5 use feature qw{signatures say}; no warnings 'experimental'; sub A($m, $n, $l, $r) { say "${l}A($m, $n)$r"; $m ? $n ? A($m-1, A($m, $n-1, "${l}A(".($m-1).', ', ")$r"), "${l}A(".$m.', ', ")$r") : A($m-1, 1, "${l}A(".($m-1).', ', ")$r") : $n + 1; } say A(2, 1, '', ''); 実行結果 ~ $ perl 18_605_Ackermann_func.pl A(2, 1) A(1, A(2, 0)) A(1, A(1, A(1, 1))) A(1, A(1, A(0, A(1, 0)))) A(1, A(1, A(0, A(0, A(0, 1))))) A(1, A(1, A(1, A(0, 2)))) A(2, A(1, 3)) A(2, A(0, A(1, 2))) A(2, A(0, A(0, A(1, 1)))) A(2, A(0, A(0, A(0, A(1, 0))))) A(2, A(0, A(0, A(0, A(0, A(0, 1)))))) A(2, A(0, A(0, A(1, A(0, 2))))) A(2, A(0, A(1, A(0, 3)))) A(2, A(1, A(0, 4))) 5 そうなのよね 入力もらって表示→ワンステップだけ展開して戻る の繰り返しが1番楽なんだけどなぁ >>605 Perl5、>>615 を修正。 >>617 あら正規表現で書けちゃうのかイナ… use feature qw{signatures say}; no warnings 'experimental'; sub A($m, $n) { $m ? $n ? do{ my ($m2, $n2) = ($m-1, $n-1); push @$l, "A($m2, "; push @$r, ')'; say @$l, "A($m, $n2)", @$r; A($m2, A($m, $n2)) } : do{ my ($m2, $n2) = ($m-1, 1); say @$l, "A($m2, $n2)", @$r; A($m2, $n2)} : do{ my $s = $n + 1; say @$l, $s, @$r; pop @$l; pop @$r; $s }; } ($m, $n) = (2, 1); say "A($m, $n)"; A($m, $n); 実行結果 $ perl 18_605_Ackermann_func.pl A(2, 1) A(1, A(2, 0)) A(1, A(1, 1)) A(1, A(0, A(1, 0))) A(1, A(0, A(0, 1))) A(1, A(0, 2)) A(1, 3) A(0, A(1, 2)) A(0, A(0, A(1, 1))) A(0, A(0, A(0, A(1, 0)))) A(0, A(0, A(0, A(0, 1)))) A(0, A(0, A(0, 2))) A(0, A(0, 3)) A(0, 4) 5 >>605 ocaml https://ideone.com/dqTO60 let (>>) f g x = g (f x) let rec a m n p = let () = p (Printf.sprintf "A(%d, %d)" m n) in if m = 0 then n + 1 else if n = 0 then a (m - 1) 1 p else a (m - 1) (a m (n - 1) (Printf.sprintf "A(%d, %s)" (m - 1) >> p)) p let () = print_int (a 2 1 print_endline) ↓ A(2, 1) A(1, A(2, 0)) A(1, A(1, 1)) A(1, A(0, A(1, 0))) A(1, A(0, A(0, 1))) A(1, A(0, 2)) A(1, 3) A(0, A(1, 2)) A(0, A(0, A(1, 1))) A(0, A(0, A(0, A(1, 0)))) A(0, A(0, A(0, A(0, 1)))) A(0, A(0, A(0, 2))) A(0, A(0, 3)) A(0, 4) 5 >>605 octave https://ideone.com/50i12U function c = a(m, n, p) p(sprintf('A(%d, %d)', m, n)); if m == 0 c = n + 1; elseif n == 0 c = a(m - 1, 1, p); else c = a(m - 1, a(m, n - 1, @(s) p(sprintf('A(%d, %s)', m - 1, s))), p); end end disp(a(2, 1, @disp)); お題: ax**2+b*x+c==0という形の二次方程式を解き、全ての実数解と実数解の個数を表示する。 実数解はルートを含んだ形でいいのか? あるいは小数点以下何桁まで正確に求めるのか? >>624 ∧_∧ / ̄ ̄ ̄ ̄ ̄ ( ´∀`)< オマエモナー ( ) \_____ | | | (__)_) お題:計算ができる文章テンプレートを実装し、つるかめ算を自動生成せよ。 文章テンプレートの例: 「ツルとカメが合わせて{$(ツルの数)+$(カメの数)}います。 足の合計本数が{$(ツルの数)*2+$(カメの数)*4}本です。 カメは何匹いますか。」 変数は「$(変数名)」のように表し、その具体的な値は入力として与えられる。 計算式は{ }で囲って表す。 計算式は変数や定数、加減乗除の演算子、または丸カッコを含むことができる。 入力の例:「ツルの数=3, カメの数=4」 >>625 js function quadraticWithCount(a, b, c) { const inSqrt = b ** 2 - 4 * a * c if (inSqrt < 0) return [[], 0] const l = - b / (a * 2) if (inSqrt === 0) return [[l], 1] const r = Math.sqrt(inSqrt) / (a * 2) return [[l - r, l + r], 2] } console.log(quadraticWithCount(3, -2, -1)) console.log(quadraticWithCount(3, 6, 3)) console.log(quadraticWithCount(1, 2, 3)) // [ [ -0.3333333333333333, 1 ], 2 ] // [ [ -1 ], 1 ] // [ [], 0 ] >>629 追記: パーサーを作れない人はevalを用いても構わない。 >>625 js 改善 function quadratic(a, b, c) { const rt = Math.sqrt(b ** 2 - 4 * a * c) return [(-b + rt) / (2 * a), (-b - rt) / (2 * a)] } function quadraticReal(...abc) { const ans = quadratic(...abc) const [a1, a2] = ans if (isNaN(a1)) return [] if (a1 === a2) return [a1] return ans } const quadraticRealWithCount = (...abc) => addCount(quadraticReal(...abc)) const addCount = a => [a, a.length] console.log(quadraticRealWithCount(3, -2, -1)) // [ [ 1, -0.3333333333333333 ], 2 ] console.log(quadraticRealWithCount(3, 6, 3)) // [ [ -1 ], 1 ] console.log(quadraticRealWithCount(1, 2, 3)) // [ [], 0 ] >>629 Ruby ツルの数 = 3 カメの数 = 4 Template =<<_EOT_ 「ツルとカメが合わせて{$(ツルの数)+$(カメの数)}います。 足の合計本数が{$(ツルの数)*2+$(カメの数)*4}本です。 カメは何匹いますか。」 _EOT_ puts Template.gsub( /\{(.*?)\}/ ){ eval $1.gsub( /\$\((.*?)\)/ ){ $1 } } >>629 Perl5 use utf8; no warnings 'utf8'; $ツルの数 = 3; $カメの数 = 4; print <<EOF 「ツルとカメが合わせて@{[${ツルの数}+${カメの数}]}います。 足の合計本数が@{[${ツルの数}*2+${カメの数}*4]}本です。 カメは何匹いますか。」 EOF 実行結果 ~ $ perl 18_633_ツルの数+カメの数.pl 「ツルとカメが合わせて7います。 足の合計本数が22本です。 カメは何匹いますか。」 お題: 2つのRGBカラーが#RRGGBB形式で与えられる(RRGGBBは六桁の十六進数とする)。 2つの中間色を#RRGGBB形式で出力せよ。 可能ならばこれら3つの色をカラーバーとして表示せよ。 >>635 入力例1: #112233, #99AAFF 入力例2: #AD03ff, #a39e75 >>635 ,636 自明な入力例だけを示しても、出力例も出さないと意味ないだろう。 2色の中間色ってのが曖昧じゃね? 単にR,G,Bそれぞれの平均を取るだけなのか、赤と紫の中間が赤紫になるように循環する色相で中間をとるのかとか。 >>634 >変数は「$(変数名)」のように表し、 お題: 20201010と出力してください。ただしコードに使っていい数字は1のみです。 >>640 python a=1;b=a+a;c=a-a print(b,c,b,c,a,c,a,c,sep='') #出力20201010 >>640 自分で js const t = ` `.charCodeAt() console.log(t + t + "" + (t + t) + t + t) const m = "ϲ".charCodeAt() console.log(m + m + "" + m) >>640 js本日限定 new Date().toLocaleDateString().split(/-|\//).join`` //=> "20201010" >>647 Windowsでもそのままでいけるのか? haskell import Data.Maybe main = print $ product $ map ((fromJust).(flip lookup (zip ['\t'..] [1..]))) "&myC" >>649 js var ctx = new window.AudioContext var osc = ctx.createOscillator() osc.type = 'sine' osc.frequency.value = 1000 osc.connect(ctx.destination) osc.start() osc.stop(1) >>640 haskell 改良 unicode = length . tail . (enumFromTo minBound) main = print $ product $ map unicode "ാᝇ" ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる