プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
>>123 平面上に3点P1、P2、P3を配置して三角形を作る時、正三角形を含む二等辺三角形でなければならない これ以外の配置のやり方をすると辺の長さが3種類となって前提に反する 上記のように配置した3点3点P1、P2、P3に4点目P4を配置するとき、 A) 二等辺三角形P1P2P3と底辺を共有し、長さが等しい辺と同じ長さの2辺をもつ2等辺三角形となるようにP4を配置する (底辺を共有するように二等辺三角形二つを配置する) または B) 三角形P1P2P3が正三角形のとき、外接円の中心と一致するようにP4を配置する の二通りの配置の仕方がある。逆に言えば、この条件に従うように座標を決定すれば無限の配置の仕方が可能 って、>>123 よく読んだら>>130 じゃダメだ! orz 失敬 撤回しますわ お題:ある数 n が与えられたとして、n の原始根の位数を求めよ 条件:原始根については https://ja.wikisource.org/wiki/%E5%88%9D%E7%AD%89%E6%95%B4%E6%95%B0%E8%AB%96%E8%AC%9B%E7%BE%A9/%E7%AC%AC1%E7%AB%A0/%E5%8E%9F%E5%A7%8B%E6%A0%B9%EF%BC%8C%E6%8C%87%E6%95%B0 を参照せよ、ただし、このテキストでは n が素数であることを前提にしているが、原始根は n が素数でなくても存在する。n が素数でない場合にも対応せよ。 原始根を、小さい数から順次位数を力技で求める方法は認めない。 n の原始根が存在しない場合にアルゴリズムが停止する必要は要請しない。 C言語スレよりロンダリング x面体のサイコロy個を振って得られる出目のヒストグラムを出力するプログラムを作ろう dice.exe 6 3 (6面体のサイコロ3個) の出力例 出目 出現回数 出現率 ---- -------- ------ 3 1 0.46 4 3 1.39 5 6 2.78 6 10 4.63 7 15 6.94 8 21 9.72 9 25 11.57 10 27 12.50 11 27 12.50 12 25 11.57 13 21 9.72 14 15 6.94 15 10 4.63 16 6 2.78 17 3 1.39 18 1 0.46 厳密解を出す場合なら動的計画法で素朴にやるとO(x^2y^2) この問題のポイントはサイコロを正N面体に限定してないところだな それと3面体なんていう指定をされたらどうするとかな >>136 やるなあ パスカルの三角形のもう一段階上みたいな感じか お題: ハート・ダイヤ・クラブ・スペードを各13枚ずつもつ52枚のカードから13枚のカードが配られます. Q1. 配られたカードの種類がもっとも均質でない(13・0・0・0)確率P1と, もっとも均質である(4・3・3・3)確率P2を求めてください. Q2. 確率P1よりも低い確率の組み合わせが存在する場合, その組み合わせと確率を求めてください. Q3. 確率P2よりも高い確率の組み合わせが存在する場合, その組み合わせと確率を求めてください. >>134 Emacs Lisp (require 'cl-lib) (defun dice (x y) (let ((b '(0))) (dotimes (i y) (setq b (reduce (lambda (a b) (append a b)) (loop for n in (loop for i from 1 to x collect i) collect (loop for m in b collect (+ n m)))))) (pp (loop for n in (remove-duplicates b) collect (list n (count n b) (/ (float (count n b)) (length b))))))) (dice 6 3) ((3 1 0.004629629629629629) (4 3 0.013888888888888888) (5 6 0.027777777777777776) (6 10 0.046296296296296294) (7 15 0.06944444444444445) (8 21 0.09722222222222222) (9 25 0.11574074074074074) (10 27 0.125) (11 27 0.125) (12 25 0.11574074074074074) (13 21 0.09722222222222222) (14 15 0.06944444444444445) (15 10 0.046296296296296294) (16 6 0.027777777777777776) (17 3 0.013888888888888888) (18 1 0.004629629629629629)) >>134 Squeak/Pharo Smalltalk | dice | dice := [:x :y | | bag | bag := Bag new. (1 to: x) asDigitsToPower: y do: [:ary | bag add: ary sum]. bag sortedElements collect: [:kv | {kv key. kv value. kv value / bag size * 100s2}] ]. dice value: 6 value: 3 "=> { {3 . 1 . 0.46s2}. {4 . 3 . 1.38s2}. {5 . 6 . 2.77s2}. {6 . 10 . 4.62s2}. {7 . 15 . 6.94s2}. {8 . 21 . 9.72s2}. {9 . 25 . 11.57s2}. {10 27 12.50s2}. {11 27 12.50s2}. {12 . 25 . 11.57s2}. {13 . 21 . 9.72s2}. {14 . 15 . 6.94s2}. {15 . 10 . 4.62s2}. {16 . 6 . 2.77s2}. {17 . 3 . 1.38s2}. {18 . 1 . 0.46s2} } " >>144 プログラミングする意味のあるお題作ってくれよ いや>>134 は10面体10個を10秒以内で計算するとかの条件付けるとプログラミングの意味あるぞ >>136 はよく出来てるとオモタ >>144 そんなこといわずに >>132 を解いてくれよぅ 原始根の存在定理を素数以外に拡張していいのかどうか、いまいち確信がもてないんだ… 乱数を使用して10億回試行してみたところ,4・3・3・3の出現回数は105357474 (10.5%), 13・0・0・0は0(12・1・0・0は3)でした. 4・3・3・3よりも出現回数の多い組み合わせは以下の4通りでした. 4・4・3・2 215505541回 (21.6%) 5・3・3・2 155167267回 (15.5%) 5・4・3・1 129327030回 (12.9%) 5・4・2・2 105786216回 (10.6%) このお題はHAKMEM MIT AI Memo 239 ITEM 46 (Schroeppel)を参考にしました. http://www.inwap.com/pdp10/hbaker/hakmem/number.html#item46 A+B+C+D+E+F+G+H+I+J+K=170 A-B=−2 A>B>C>D>E>F>G>H>I>J>K A>0のとき この式を満たすA〜Kを全て求めよ A-B=−2 A>B この二つを同時に満たせません 修正がA>B>C...→A<B<C...じゃなくてA-B=-2→A-B=2だと無数に求められるから全て求めるのは無理じゃないかな? 例えばこんなん int A=68,B=66,C=8,D=7,E=6,F=5,G=4,H=3,I=2,J=1,K=0; while(true) { A++; B++; K-=2; } こういうお題を書きたいのなら制約条件を良く考えないと A+B+C+D+E+F+G+H+I+J+K=170 A>B>C>D>E>F>G>H>I>J>K A〜Kは全て自然数とする こういうのとかな >>150 http://ideone.com/ZXck7T C++。ちょっと自信ないけど、一応できた。 頑張って最適化した。 https://www.hackerrank.com/sinapusu2002-1 ハッカーランクという競技プログラミングサイトで出題中の問題。 オリジナル問題6問。 ハッカーランクに登録して解いてくれ。 スレ違いだろうか? 2つの三角形の共有面積はかなりマゾいのでお勧め。 一応競技プログラミング界の重鎮で東大で数学してる人にも解いてもらったりはしたけど。 挑戦者数が増えないのが悩みの種。 ただいま次回コンテストに向けて3/6問作成済み、3問作成予定。 挑戦者数が増えないのは問題が悪いからだろ。 良問をだしてれば自然と挑戦者は増えるはず。 宣伝してズルした時点でお前の人間性の低さがわかるんだよ >>160 東大生に解いてもらっても屑な問題はクズだ。 そんなもので東大のブランド志向に思ってる奴を釣ろうとしている お前も同じ穴の貉だよ。 俺はそいういうやつは軽蔑するな。 お題:格子点を1個だけ含む面積4の凸多角形を求める >>167 斜めってる正方形とか、無限にできるんでないの? >>167 xが0.9未満なら (0,0)(x,0)(0.1,4/x)(0.1+x,4/x) の平行四辺形でいいよね >>167 (0,0)-(0.8,0)-(9.8,10) [1] 授業単元:線形代数 [2] 問題文 与えられたn字正方行列の逆行列を求めよ。 求めた行列は、与えられた行列を掛けて n 次単位行列となることを確認せよ。 以下のCプログラムを元に実装されていない部分を補完せよ。C 以外の言語で記述する場合は、この C プラグラムの対応する部分も記述すること。 https://ideone.com/k996I1 逆行列が存在しない場合は適切に処理してよい。 [3] 環境 [3.1] OS: 問わない [3.2] コンパイラ名とバージョン: 問わない [3.3] 言語: C または任意の言語 [4] 期限: ([2017年4月15日23:59まで] [5] その他の制限:お題です。 お題: 辺の長さが100より小さい既約のピタゴラス三角形をすべて求めう。 出力の順序は問わない。 >>171 これ、宿題の解答にならないようなプログラムにするのは結構難問かも。 >>174 Ruby N=100 (1..N).step(2){|a|(a+2..N/a).step(2){|b|c=b*b-a*a>>1 ;a.gcd(b)<2&&c<N&&p([a*b,c,c+a*a])}} お題: トランプの札のリストが文字列で与えられるので 同じマークor同じ数字のペアが最大何組できるか求めよ D:ダイヤ、H:ハート、S:スペード、C:クラブ、 A:エース、2〜9:数字の2〜9、T:10、J:ジャック、Q:クイーン、K:キング 例: "DAD2HAH3" -> 2 "DAD3D8D9DJH5H8HKSASKCAC5C8CK" -> 7 "SAS2S3S4S5S6S7S8S9C2C3C4C5C6C7C8C9CT" -> 9 >>180 知らんけどNP完全とかそういうやつ? 違ったらスマソ >>180 http://ideone.com/UgHgtz C++。多分間違ってる。数字も合わないしな。 i7-6700でリリースビルドで40秒くらいかかる。 見てる感じ塩基配列だよなこれ。 >>180 c++ http://ideone.com/WK9LQi 問題文には明記なかったが、ユニークな52枚(4*13)1セットだけだとして解いた。 計算量は 1問 14^4*6 くらいになるのだろう。 (最初は14^5*6でやったが、ひとつ計算量落とした。 この数値じゃ、意味なかったけど) >>171 人気がないね…ループの知識だけあればOKでループの構成を考える腕力が多少あればそれなりに楽しめるお題と思ったんだけれども 新規性がないのが弱点なのかな? 次のお題を考えることにしようか http://ideone.com/Et54St 意味ないけど最適化したら現実的な時間で終わるようになった。 今暇なので、いい暇つぶしになったなぁ。意味ないけど。 >>186 >DAD2HAH3:4,2 >DAD3D8D9DJH5H8HKSASKCAC5C8CK:394,38 >SAS2S3S4S5S6S7S8S9C2C3C4C5C6C7C8C9CT:1972800,16 どういうこと??? 組み合わせの数がカードの枚数すら超えてるの??? そいつのコード見てないから分からんが多分、最初の例なら 1)DAHA 2)DAD2 3)HAH3 4)DAD2,HAH3 みたいにカウントされちゃってるんじゃないか? >>180 最後のは9じゃなくて8組だろ 同じマーク S:4組、C:4組、合計8組 同じ数字 2,3,4,5,6,7,8,9の各ペアで合計8組 最大組数は8組 俺も間違ってたので修正した http://ideone.com/vD1JHy 答えは2組,6組,8組じゃないの? >>189 反例 数字で(S2=C2)で1ペア、 残り8枚ずつで同スートのペアを8つくる 合計 9ペア 数字で(S2=C2, S3=C3, S4=C4) 3ペア 残りは6枚ずつになるので、6ペアできる 合計9ペア その他 数字のペアを奇数個つくれれば、9を作れる 8bitの整数を一つ引数として与え、 上位4bitと下位4bit を符号なし整数として掛け算した結果の8bitを返す関数を 論理演算子のみで実装したもののうち、 もっとも実行時間が短いものを挙げよ。 論理演算は全て1命令1サイクルとする。 最も実行時間が短いかどうかの判定ってNP完全っぽそう http://ideone.com/QNbwWa C++。えーん終わらないよ〜。 デバッグ覗いたら早い段階で答え出てるんだけど打ち切り方がわからない。 >>186 などは題意を把握してなかった。 ふえぇーん。1時間半回してもおわらないよー。 動的計画法すごい。 お題 これ http://www.mext.go.jp/programin/ に相当するアプリケーションを 非Web環境でも使えるような仕様で 単一の言語でコーディングしろ こういうのに瞬時に回答できるようになるまでどのくらいの時間がかかるものなの? >>212 時代は3Dか・・・。 ロートルにはできん芸当だ。GJ。 すみません。何言ってるかわからないだろうけど、 12桁の数字が並ぶ羅列は何を表しているのでしょうか??? /021/000/000/000 とか 最初の3つが市外局番 次が区番号 残りが個人識別子だよ 12桁くらいの数字を使う規格ってそれなりにありそうだけどな。 >>218 ギブアップ。うぃきぺ見ても意味わかんない。頭爆発しそう。 数字の入ったヤング盤じゃなくて、図形だけでいいの? nのヤング図形を全部求めるってこと? >>221 は1行目が「× Yaund」「○ Young」という恥ずかしい間違いから始まり N <= 0の時のチェック漏れやら 長方形のパターン(N=10の時の[5,5]や[2,2,2,2,2])が抜けてるなど ミスしまくってました orz てことで、修正します >>218 Nim https://wandbox.org/permlink/RUf5B0SVg0MozD25 なーんだそれでいいのか。 それならなんとか組めるかも。 問題の想定解と合ってるのかな? 出題者のコメントが欲しいところ お題:以下を出力 857142 714285 571428 428571 285714 142857 >>227 法則性がわからん 文字列じゃなくあくまで数値で? ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる