プログラミングのお題スレ Part15
■ このスレッドは過去ログ倉庫に格納されています
https://ideone.com/geZ4qP >>5 が不安だったので、出力変えてみたけど、最大値で500近くになるんだな。 何かビビった。 サイコロの偏りをもっと明確にしたいなら、乱数エンジンを複数持つか、ランダムデバイスそのもので実行する。 ランダムデバイスは遅いことになってるのでMTに投げるんだけど。 一様乱数のサイコロは、現実では職人が作ったサイコロですなあ。 お題: 炭素原子C, 酸素原子O, 水素原子Hという三種類の原子をそれぞれいくつか組み合わせて、非イオンの分子を作る。C, O, Hの結合の手の本数は、それぞれ四本、二本、一本である。 ゼロ以上の整数p,q,rが与えられ、Cがp個、Oがq個、Hがr個あると仮定するとき、原子を余らせず、また、結合の手を余らせずに一つの連結された分子を作りたい。 C, O, Hをこの順でp+q+r個、並べたリストLについて、m番目の原子L[m]とn番目の原子L[n]の結合の個数をA[m,n]と書くとき、A[m,n]によってなる行列Aを一つ求めなさい。不可能な場合は「None.」と表示しなさい。 例) (p, q, r)=(0, 2, 0) → A=((0, 2), (2, 0)). (p, q, r)=(1, 2, 0) → A=((0, 2, 2), (2, 0, 0), (2, 0, 0)). (p, q, r)=(0, 1, 2) → A=((0, 1, 1), (1, 0, 0), (1, 0, 0)). 出題者は自分で解けることを確認してからお題にしてるのかね? 自明でない不可能な場合の例とか出してこないし怪しいもんだ 慣れない言語の勉強に使うのに丁度いいね 出題者が答えも貼っといてくれるとありがたい(´・ω・`) 良いプログラムは良い数式がないと作れないのでこのスレは過疎化する。 久々にこの板きたけど、宿題スレってなくなったんだね 解空間は、サイズ(p+q+r)×(p+q+r)の整数行列の集合になる。 結合の手の個数は有限だから、解行列の成分は上限がある。 よって行列の各成分についてしらみつぶし探索が可能。 自分自身とは結合しないので、A[k,k]=0(つまり、行列の対角成分はゼロ)。 ある行の和は、行番号に対応する原子の結合の手の個数になる。 ある列の和は、列番号に対応する原子の結合の手の個数になる。 連結条件のチェックが必要。 お題: xのn次式を簡潔に表現できる関数を書け(rationalじゃなくてもOK) a+bx+cx^2+dx^3+... を f x a b c d ... のように表現する (可変引数を処理する) 例えば (defun f (x &rest as) (reduce #'+ (loop for a in as for i from 0 collect (* a (expt x i))))) (loop for x from -5 to 5 do (print (f x 0 -1 0 1/3))) -110/3 -52/3 -6 -2/3 2/3 0 -2/3 2/3 6 52/3 110/3 >>13 良い数式が立てられないのでモンテカルロに酔っているオレ・・・。 >>9 複雑すぎます 非環状アルカン(CnH2n+2)の構造異性体を列挙せよ、という簡略化したお題を提案します >>14 存在することはするのですが、誰も近寄らなくなりました、キチガイが一匹しつこく居候しているので お題: 1 + 1 を計算させて 3 と出力させなさい >>23 Perl5 $a = 1 + 1; print ~$a%10; 実行結果 $ perl 15_23.pl 3 ※64bit整数版で実行してね >>23 perl5 print ("1", "+", "1") 1+1 print $_ =()= ("1", "+", "1") 3 >>23 perl 1+1; print "3\n" >>23 ruby class Fixnum alias :add :+ def +(val) if self == 1 && val == 1 puts 3 2 else self.add(val) end end end 1 + 1 #=> "3\n" 1 + 1 + 1 #=> "3\n" 1 + 1 + 1 + 1 #=> "3\n" 1 + 1 - 1 + 1 #=> "3\n3\n" >>23 perl5 print qw(1 + 1) 1+1 print eval q(1 + 1) 2 print $_ =()= qw(1 + 1) 3 お題、東大入試 a^2 - a が、10,000 で割り切れるような奇数a を求めよ。 ただし、3 <= a <= 9,999 ヒント a^2 - a = a(a - 1) で、aは奇数、a-1 は偶数。 10,000 = 10^4 = 2^4 * 5^4 答え、625 東京大【整数マスターに俺はなる!#31】 https://www.youtube.com/watch?v=-LdnNZVftmw >>29 common lisp (loop for n from 3 to 10000 when (and (equal (mod n 2) 1) (equal 0 (mod (- (expt n 2) n) 10000))) collect n) (625) ・女体限定で、3次元の写真から3Dポリゴンモデルデータを自動作成 ・そのデータから胴体部の着衣部分を、裸モデルに修正 ・水着でついた脇乳の段差も修正 ・元写真の地肌色を使い、女体テンプレのテクスチャを作成 ・完成したモデルから胴体部だけ精密レンダリング ・元の写真に貼り付けて完成 プログラミングのお題スレ Part14 https://mevius.5ch.net/test/read.cgi/tech/1558168409/981-986 漏れは、前スレの981 ではないですが、この問題の応用で、 括弧のネストの深さの最大値を求めよ 括弧の対応が取れていない場合は、-1 を出力せよ。 2種類の括弧が順序通りに、閉じていないものも、-1 です ヒント : stack を使うと良いかも "" => 0 "( )" => 1 "{ ( { ( ) } ( ) ) } ( )" => 4 "} {" => -1 "( { ) }" => -1 自分でスタックするか再起にして自動で積ませるか、といったところか。 ideone バグっているのか? STDIN の1行目空だと ちゃんと標準入力としてプログラムに伝わっているけど リンク先の stdin 枠の中だと省略されているように見える stdout の 0 はその空を受け取ったもの twitterやっていたようなので そこにバグフィックス要請とテストケース画像貼っておいた たぶんそのうち直るでしょう >>38 大分前に作ったけど、コード紛失した。 アルゴリズムも忘れた。 ガーン。 年収n円の人が生活費と交遊費2種類だけで1年間の収入のすべてを消費するとして 税率がt1からt2に上がった時 税抜き価格ベースでの生活費が変動しないものと考えると 税抜き価格ベースでの交遊費の減少額はいくらになるか? (端数は切り上げとする) ex) 年収n=5,000,000 税率t1=8% 税率t2=10% 税抜き価格ベースでの生活費a 税抜き価格ベースでの交遊費x, y 5000000 = ( a + x ) * 1.08 5000000 = ( a + y ) * 1.10 上記の方程式を解いて x-y ≒ 84,176 >>42 wolfram Simplify[ x-y, {5000000 == (a+x)*1.08,5000000 == (a+y)*1.1} ] 84175.1 切り上げか Ceiling[ Simplify[ x-y, {5000000 ==(a+x)*1.08 == (a+y)*1.1} ] ] 84176 何も考えずにceiling(n/1.08-n/1.1)でいいんとちゃうけ? >>32 Ruby f = -> str {s = +str.delete(?\ ); (0..).each{|i| s.gsub!(/{}|\(\)/, '') || (break s.size.zero? ? i : -1)}} ['', '( )', '{ ( { ( ) } ( ) ) } ( )', '} {', '( { ) }'].each{|e| puts '%p => %d' % [e, f[e]]} # => "" => 0 "( )" => 1 "{ ( { ( ) } ( ) ) } ( )" => 4 "} {" => -1 "( { ) }" => -1 >>45 ちょっと考えたらceiling(n/59.4)だったw お題: 数字が与えられるので、その数字を元の数より大きくなるように再構築せよ 大きくできなければ元の数字をそのまま出力せよ 例: in < 123 out > 231, 213, 321, 312 in < 921 out > 921 123を入力したときに132が出力されないのはなぜ? >>48 https://ideone.com/fyfMQH C++。ご期待通り(?)にパーミテーション回してみたよ。 重いお。 https://ideone.com/pgG7pT from itertools import permutations #string = "123" string = "5672391" n = int(string) print filter(lambda m: m>n, map(lambda x: int("".join(x)), list(permutations(string, len(string))))) 「大きくできなければ元の数字をそのまま出力せよ」という条件が ことごとく無視されててワロタ あと、「133」みたいに同じ数字が複数含まれる場合はどうなるべきなんだろう >>48 Perl5 sub next_permutation { defined $_[1] and (next_permutation(@_[1..$#_]) or ($_[0] lt $_[1]) and do { for (1..$#_) {$_[0] lt $_[$_] ? $i = $_ : last} @_[0, $i] = @_[$i, 0]; @_[1..$#_] = reverse @_[1..$#_]; 1 }) } #$v = '123'; $v = '5672391'; @a = sort split '', $v; do { $n = join '', @a; print "$n " if $n > $v; } while next_permutation @a; 実行結果 https://ideone.com/qeSGDm CPANなどにあるPermutation計算モジュールを使用しても良いけど、 言語処理系に標準で含まれるモジュールではなく別途インストールが必要なので、 昔書いたnext_permutation iteratorを使ってみた >>57 ごめんなさい print "$n " if $n > $v; ↓ print "$n " if $n >= $v; じゃないと「大きくできなければ元の数字をそのまま出力せよ」を満たさなかった…orz >>58 そうすると逆に 「元の数「より大きくなる」ように再構築せよ」 については、元の数値が余計に出力されるな…ゴメンねもう一工夫要るわ それにiteratorである必要ないわ >>48 Perl5、iteratorじゃなくpermutationを列挙する方法で書いてみた。これなら題意に合うはず。 sub permu { my ($l, $p, @r) = @_; defined $p ? map {[$p, @$_]} permu([], @$l, @r) : ([]) , @r ? permu([@$l, $p], @r) : () } #$v = '123'; #$v = '321'; $v = '5672391'; @a = split '', $v; @b = grep {$_ > $v} map{join('', @$_)} permu [], @a; print (@b ? "@b" : $v); 実行結果 https://ideone.com/1Lft75 少しメモリを食ってるだろうけど0.04sで解けた >>48 Squeak/Pharo Smalltalk | fn res | fn := [:input | (Array streamContents: [:ss | input permutationsDo: [:perm | perm > input ifTrue: [ss nextPut: perm copy]]] ) ifEmpty: [input] ]. fn value: '123'. "=> #('132' '213' '231' '321' '312') " fn value: '921'. "=> '921' " {#ms -> [res := fn value: '5672391'] timeToRun. #size -> res size}. "=> {#ms->6 . #size->2438} " >>56 で指摘したのに誰も反応してくれないので自分で書く >>54 は、「133」と入れると[313,331,313,331]みたいに結果がダブる >>62 C++のnext_permutationは、辞書順で次に来る順列が返るので、 最初の並びにnext_permutationを繰り返し適用すれば題意を満たす数列が得られる。 あと、自前で桁分割するより他言語のように文字列を使った方が楽だと思う。 >>48 @Mathematica rebuildLargerN[n_]:=n// IntegerDigits// Permutations// Map[FromDigits,#]&// Select[#,#>n&]&// If[#!={},#,{n}]&; In[1] := rebuildLargerN[123] Out[1] = {132, 213, 231, 312, 321} In[2] := rebuildLargerN[921] Out[2] = {921} >>63 オレのPerl5の>>60 も桁に重複があると出力はダブるよ。 ダブった出力で良いかあるいは1つに削減して出力するか 仕様は不定なので、ダブる可能性があってもそのまま出した。 ダブらせず1つだけ出力すにはsortしてuniqすればいいんだけど。 @b = grep {$_ > $v} map{join '', @$_} permu [], @a; ↓ %h = map{$_ => 1} sort grep {$_ > $v} map{join '', @$_} permu [], @a; @b = keys %h; https://ideone.com/mBo1rR C++. >>63 のダブって表示はならないですね。 文字列だと、自分はいいけど、数字に限定するのが面倒なので、大きな数で処理してます。 文字を許容するんであればお題で書いておけばそのようになるんじゃないですかね?? あ、そうだった。文字列だと自分より大きいを表現するのがめんどくさいのでした。 >>48 https://ideone.com/1mtrVl C++。暇だったので、文字列版作った。 でかい数のデバッグが大変だから手抜きだ。 ご査収ください。。。 お題@閑話休題。 https://ja.wikipedia.org/wiki/AKS 素数判定法 AKSの実装。Prime is in P. 自分は挫折しました。数学解らない。 残骸:https://ideone.com/9e7Tyn >>70 そういえば、ソートする必要ないね。 書いてるときは保証できなかったから思いつきもしなかった。 >>73 seq 300|sort -R | perl -ne ' if ($. == 1){print ; $hold = $_} elsif ($_ > $hold) { print ; $hold = $_}' 140 145 231 246 248 270 272 281 298 299 300 >>73 要素粛清しながら見た目がそろっているというギャグかいな。 https://ideone.com/hhy72i C++。よく生き残った我が精鋭たちよ。 ところで・・・。 >>73 Squeak/Pharo Smalltalk | fn | fn := [:array | | memo | memo := array first. array reject: [:x | x < memo flag: (memo := x max: memo)] ]. fn value: (1 to: 300) asArray shuffled. "=> #(65 116 195 235 276 280 293 299 300) " >>73 しばらくお題がないとおちつかないな seq 300|sort -R | perl -ne ' if ($. == 1 or $_ > $hold) { print ; $hold = $_}' >>73 ss = -> a {a.reduce([]){|r, e| r.first.nil? ? [e] : r.last < e ? r + [e] : r}} p ss[[3,1,4,1,5,9,26,53,58,97,93,238]] # => [3, 4, 5, 9, 26, 53, 58, 97, 238] >>73 Perl5 use List::Util 'max'; @a = qw{3 1 4 1 5 9 26 53 58 97 93 238}; @b = grep {$n < $_ and $n = max($n, $_)} @a; print "@b\n"; 実行結果 ~ $ perl 15_73.pl 3 4 5 9 26 53 58 97 238 お題: 太陽系の各天体の位置を物理シミュレーションし、64日後の地球の位置を求めよ。 俺たちって計算能力でコペルニクスを超えられると思う? NASAのデータがあるから昔よりも楽だと思うけど。 >>73 Perl5、 >>80 よりこっちの方が若干スマート $n = -inf; @a = qw{0 3 1 4 1 5 9 26 53 58 97 93 238}; @b = grep {$n < $_ and ($n = $_), 1} @a; print "@b\n"; 実行結果 ~ $ perl 15_73.pl 0 3 4 5 9 26 53 58 97 238 >64 地球の位置といってもいろいろあります。 地球の赤道を天球上に投影した、「赤経、赤緯」、太陽の天球上の 通り道を天球上に投影した「黄経、黄緯」がありますし、それも、地球の中心を 原点とした、「地心赤経、赤緯」、「地心黄経、黄緯」および、観測地点を原点とした 「地表赤経、赤緯」、「地表黄経、黄緯」もありますので、どれにするかによって 計算式が違ってきます。 なお、JPLでは、太陽と月、および冥王星までの精密位置計算用のプログラムを 発表しています。 期間がながいものは、−4000(B.C.4001)〜4000(A.D.)まで、計算できるものが あります。 計算用のデータと、テスト用のFortranプログラムも附属しています。 Perlって読みにくいんだな {とか@とか$とか使いまくる言語ってマジ苦手 grep 内のboolian から最後の , 1 を取り除いたら 最初の0を拾わない 何というカオス @b = grep {$n < $_ and {$n = $_}} @a; こうやりゃいいんだよ この方がいいだろ @b = grep {$n < $_ and ($n = $_, 1)} @a; お題: 与えられた数列の要素の中で他と被っていない最小のものを求めよ 被っていない要素が存在しないときは-1を出力すること 例: 1,1,1,1,2,2,2,3,3,4 -> 4 1,2,3,4,5,5,4,3,2,1 -> -1 3,1,4,1,5,9,2,6,5,3,5 -> 2 >>91 Perl5 use feature say; use List::Util min; for ([1,1,1,1,2,2,2,3,3,4], [1,2,3,4,5,5,4,3,2,1], [3,1,4,1,5,9,2,6,5,3,5]) { my %h; $h{$_}++ for @$_; @s = grep{1 == $h{$_}} keys %h; $" = ','; say "@$_ -> ", @s ? min @s : -1; } 実行例 ~ $ perl 15_91.pl 1,1,1,1,2,2,2,3,3,4 -> 4 1,2,3,4,5,5,4,3,2,1 -> -1 3,1,4,1,5,9,2,6,5,3,5 -> 2 >>91 Ruby f = -> a {a.sort.group_by{|e| a.count(e)}[1]&.min || -1} [ [1,1,1,1,2,2,2,3,3,4], [1,2,3,4,5,5,4,3,2,1], [3,1,4,1,5,9,2,6,5,3,5] ].each{|a| puts '%p => %s' % [a, f[a]]} # => [1, 1, 1, 1, 2, 2, 2, 3, 3, 4] => 4 [1, 2, 3, 4, 5, 5, 4, 3, 2, 1] => -1 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] => 2 typo f = -> a {a.uniq.group_by{|e| a.count(e)}[1]&.min || -1} >>91 ruby [ [1,1,1,1,2,2,2,3,3,4], [1,2,3,4,5,5,4,3,2,1], [3,1,4,1,5,9,2,6,5,3,5] ].each{|ar| print ar.join(','), " -> " while (m = ar.min) && ar.count( m ) != 1 ar.delete( m ) end puts m || -1 } 1,1,1,1,2,2,2,3,3,4 -> 4 1,2,3,4,5,5,4,3,2,1 -> -1 3,1,4,1,5,9,2,6,5,3,5 -> 2 >>91 Perl5 >>92 よりもう少しシンプルに use List::Util min; for ('1,1,1,1,2,2,2,3,3,4', '1,2,3,4,5,5,4,3,2,1', '3,1,4,1,5,9,2,6,5,3,5') { my %h; $h{$_}++ for split ','; $s = min grep{1 == $h{$_}} keys %h; $s //= -1; print "$_ -> $s\n"; } 実行結果 ~ $ perl 15_91.pl 1,1,1,1,2,2,2,3,3,4 -> 4 1,2,3,4,5,5,4,3,2,1 -> -1 3,1,4,1,5,9,2,6,5,3,5 -> 2 昔々Cで数独解くやつ普通に作ったことあるけど普通に作っても人間の感覚では一瞬にして答えが出ちゃうんだよな。ほとんどEnterキー押したらすぐ出る感じ。 そしてこれといって他にアルゴリズムは思い浮かばない。(誰もが思い付くであろう再起でマスに入れられる数を順番に入れてく方式ね)。 これ以上に「素早く」やる方法なんてあるんだろうか? >>91 https://ideone.com/oSQNZM C++。これでどうじゃ。 バケットソートでいいじゃないか。プンプン。 #include <map> template<class Container> std::int64_t MakeHoge(const Container& D) { std::map < Container::value_type, std::uint64_t> M; for (auto& o : D) { M[o]++; } for (auto& o : M) { if (o.second == 1) { return o.first; } } return -1; } 詰めまくってみた。C++。 #include <map> template<class Container> std::intmax_t MakeHoge3(const Container& D) { std::map < Container::value_type, std::uintmax_t> M; for (auto& o : D) { M[o]++; } for (auto& o : M) { if (o.second == 1) { return o.first; } } return -1; } しつこいけど、これ以上は無理ってくらい詰めた。 どうでもいいのですけど、MITライセンス。知ってますね。 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.4 2024/05/19 Walang Kapalit ★ | Donguri System Team 5ちゃんねる