X

プログラミングのお題スレ Part11

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
垢版 |
2018/04/24(火) 20:45:14.49ID:ZY7R7Sru
プログラミングのお題スレです。

前スレ
プログラミングのお題スレ Part10
https://mevius.5ch.net/test/read.cgi/tech/1514772904/

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。
0576デフォルトの名無しさん
垢版 |
2018/07/11(水) 23:18:42.60ID:83LTUfxJ
>>569 Squeak/Pharo Smalltalk

"問1"
((0 to: 9) copyWithoutAll: #(1 3 9)) detect: [:n |
| set |
set := Set new.
'139', n asString combinations: 3 atATimeDo: [:comb |
comb permutationsDo: [:perm |
perm first ~= $0 ifTrue: [set add: (perm as: String) asInteger]
]
].
set size = 24 and: [set average = 555]
] "=> 7 "

"問2"
((10000 roundTo: 36) to: 99999 by: 36) detect: [:n | n asString includesAllOf: '235'] "=> 13572 "
0577デフォルトの名無しさん
垢版 |
2018/07/12(木) 00:00:29.98ID:gpOSM7dO
このスレprologニキっていないの？
手続き型以外の解法見たい
あとJニキ最近見なくて寂しい
0578デフォルトの名無しさん
垢版 |
2018/07/12(木) 01:08:11.22ID:gc75XwOp
>>569
問１
4種の数字から作られる24個の数字の平均が555
→合計が1110になる12組の数字にまとめられる→どの桁も合計が10になる２組の数字の組合せで構成される
→1,3,9,xのうち1と9を除外した3と「足して10になる数」→x=7

問２
36の倍数→4の倍数かつ9の倍数
→5桁の数字は9の倍数なので各桁の数字の合計が9の倍数になる
→5桁の数字には「2,3,5」が少なくとも１つ以上含まれているので、この時点で各桁の数字の合計は10より多くなる。
→各桁の数字の合計は9ではないので、18とする。残り2桁の数字の合計は8。この中で一番小さな数が作れるのは1,7。
→「1,2,3,5,7」の組み合わせの内、下2桁が4の倍数で最も小さい数は13572となる。

かなり乱暴に書くとこんな感じで解けば良いのかな？
しかし、これをプログラムで表現しようとするのはかなり骨っぽい(数を1桁ずつ分解するのに余計な手間がかかりそう)。
それよりも総当たりで解いた方がコンピュータ的には手っ取り早い気がしますね。
0580578
垢版 |
2018/07/12(木) 07:07:01.02ID:gc75XwOp
>>579
作成される数字を順列とみなした時に
「ABCD ABDC ACBD ACDB ...」を逆順にした
「DCBA DCAB DBCA DBAC ...」という列を組み合わせたら…なんて考えてたんですが、後で見ると意味不明でした。申し訳ない。

問１について、それよりも単純な方法がありました。

xがどの桁で使用されてるかで場合分けし、それぞれを合計する
x不使用：139 193 319 391 913 931 ：2886
xが１の桁：13x 19x 31x 39x 91x 93x ：2860 + 6x
xが10の桁：1x3 1x9 3x1 3x9 9x1 9x3 ：2626 + 60x
xが100の桁：x13 x19 x31 x39 x91 x93 ：286 + 600x
上記をすべて合計：8658 + 666x
24個の数字の平均が555だから合計は 555*24=13320
8658+666x=13320
666x=4662 x=7

若干手続きはコンピュータ向けと言えなくもないですが、やはりプログラミングするには手間ですね。
0581デフォルトの名無しさん
垢版 |
2018/07/12(木) 07:41:52.96ID:KB59nVpm
問1
24=4! なので4個の数字はすべて異なる
24通りを並べると各桁1, 3, 9, x が同じ回数出現する
これらの平均が555なので
1, 3, 9, x の平均が5とわかる
1, 9の平均が5なので3, xの平均が5となる7が答え

問2
最小を求めるので10000の位が1になる数を考える
(考えて、なければ他を考える)
各桁の合計が9の倍数から1, 2, 3, 5, 7とわかる
この中で偶数は2だけなのでこれが1の位
1の位が4で割りきれないので10の位は奇数であれば4の倍数
つまり10の位が3, 5, 7のどれでも36の倍数になる
3, 5, 7を小さい順にならべて13572が答え
0583デフォルトの名無しさん
垢版 |
2018/07/12(木) 09:03:09.86ID:ax9CLQnp
問１
x = 111 * (24 * 5 - 6 * (1 + 3 + 9) ) / (6 * 111)
= 7
問２
5つの数を A, B, 2, 3, 5 とすると
A + B + (2 + 3 + 5) = 0 mod 9　<=> A + B + 1 = 0 mod 9
かつ末尾2桁が4の倍数になる
従って一番左の桁は1で確定し {A, B} = {1, 7}も確定
2が末尾に来ることは確定していてかつそのとき任意の並びで4の倍数になるため13572が題意を満たす数

以上が東大理学部物理学科卒の考え方
両方合わせて40秒くらい
0584デフォルトの名無しさん
垢版 |
2018/07/12(木) 09:17:45.00ID:kqFyQCjZ
やっぱ紙と鉛筆で解く問題だよね。
最初から解析的に解けない問題出して欲しい。
0585デフォルトの名無しさん
垢版 |
2018/07/12(木) 10:06:30.92ID:nIR9VMIg
>>580
小学生が解く場合に途中で 8658+666x=13320 のような数学的表現で考えるのはありなのか？
回答者個人にそれができるかできないかの問題ではなく小学校が教えている範囲にそれが含まれるのかの問題ね。
もし含まれていないとしたら他の方法で解く事が可能という事になる。
0587デフォルトの名無しさん
垢版 |
2018/07/12(木) 14:03:35.77ID:Jbx8ub/k
36の倍数は、4, 9 の倍数で、それらの特徴を利用できるかどうかだけ

捨て問題だろ。
考えたり解いたりすると、2問で10分使うから、落ちるだけ。
即座に無視しないといけない。
新パターンの問題は、時間を使わせるから無視しろっていう、受験テクニック

灘中高は、100%塾の生徒しか受からない。
灘用の受験技術だから、その授業を受けていないと受からない

文系が東大工学部に入る、受験技術のマンガ「ドラゴン桜」と同じ。
賢い者ではなく、塾代という貧富の格差で決まる

大型資格もそう。
TAC, 大原などに行ってないと受からない

貧富の格差、貧富の遺伝
0589デフォルトの名無しさん
垢版 |
2018/07/12(木) 18:14:20.08ID:ax9CLQnp
>>586
ものすごくかみ砕いて言うと
A + B + 1 = 0 mod 9 (A, B ∈ {0, 1, ..., 9}) を満たす A, B に関して
任意のAに対して対応するBが少なくとも１つは存在することは自明なので
A = 1 として 1XX32 という数を考えればこの数は36の倍数でありかつ 2, 3, 5 を各桁に含む
(XXには A = 1 に対応する B の値の内の1つと 5 が入る)
解は10000以上1XX32以下の整数なので左端の桁は1であると確定する
0593デフォルトの名無しさん
垢版 |
2018/07/13(金) 07:35:11.88ID:isSSIGbX
>>569
Rubyで問１。

def odai_11_569_1(a_ary, a_avg)
(a_ary.size + 1) * (a_avg / 111) - a_ary.inject(:+)
end

w_ary = [1, 3, 9]
w_avg = 555
p odai_11_569_1(w_ary, w_avg)

結果：7
0594デフォルトの名無しさん
垢版 |
2018/07/13(金) 08:03:43.23ID:isSSIGbX
>>569
Rubyで問２。

def odai_11_569_2(a_ary, a_base, a_col)
a_ary.map!(&:to_s)
w = 10**(a_col - 1)
w = w / a_base - (w % a_base > 0 ? 0 : 1)
w *= a_base
loop do
w += a_base
next if (a_ary - w.to_s.split('')) != []
return w
end
end

a_ary = [2, 3, 5]
a_base = 36
a_col = 5
p odai_11_569_2(a_ary, a_base, a_col)

# 結果：13572
0595デフォルトの名無しさん
垢版 |
2018/07/13(金) 08:58:11.48ID:IlVyAeDp
rubyならさくっとワンライナーで
p (10000-10000%-36).step(10**5,36).find{|i|(i.digits&[2,3,5])[2]}
#=> 13572
0596569
垢版 |
2018/07/13(金) 16:26:20.44ID:oo2UOY38
>>569
Rubyで、問2

str_ary = %w(2 3 5)

(10_000...100_000).select do |num|
next unless num % 36 == 0

# 2, 3, 5 をすべて含む
if str_ary.all? { |s| num.to_s.include? s }
puts num #=> 13,572
break
end
end
0598デフォルトの名無しさん
垢版 |
2018/07/14(土) 13:47:04.74ID:3J9Q4qmi
そろそろ新しいお題を。
既出なら申し訳ない。

お題：
再帰・スタックを使用しないマージソートを実装し、整数型のデータn個の配列をソートするプログラムを作成しなさい。
データの個数は不定とし、特定の条件を満たす個数の配列にのみ有効なプログラムは不可とします。
データの内容はランダムとします。乱数の生成法はお任せします。
出来ればソート完了後に配列（の一部）を表示する、正しくソート出来たかチェックする処理を追加してみて下さい。

追加お題：
上記のマージソート処理の際、作業領域を元のデータの半分の量しか確保せずにソートを実行するプログラムを作成しなさい。
0599デフォルトの名無しさん
垢版 |
2018/07/14(土) 15:13:06.98ID:QznZ4U7X
1から100までの数字から4つを取り出したそれぞれに番号を振る速い方法ありますか？
メモリもあまり使わずに

1 2 3 4 -> 1
1 2 3 5 -> 2
1 2 3 6 -> 3

96 97 98 99 -> 3921221
96 97 98 100 -> 3921222
96 97 99 100 -> 3921223
96 98 99 100 -> 3921224
97 98 99 100 -> 3921225
0601デフォルトの名無しさん
垢版 |
2018/07/14(土) 15:57:46.49ID:ETmmav0O
スタック不可だとスタック操作が隠蔽されてる高級言語はほぼ使用出来ない
無理やりCやC++でやるとしてもローカル変数や関数呼び出しを殆ど封印しなければならない
これを良い問題と見るか悪い問題と見るかは分からないが俺はやる気が出ない
0602デフォルトの名無しさん
垢版 |
2018/07/14(土) 16:00:11.93ID:4RxIMQwD
>>599
組み合わせか

北大の湊 真一のZDD とか。
本も出てる
0604デフォルトの名無しさん
垢版 |
2018/07/14(土) 18:41:01.92ID:3J9Q4qmi
>>601

すみません。>598の「スタック」はデータ構造としての利用のみを想定していて、他関数呼び出しの禁止などは意図してませんでした。
問題文が不明瞭ですみません。

>>600
ご期待に添えず申し訳ない。他のお題を思いついたら、また出題させていただきます。
0605デフォルトの名無しさん
垢版 |
2018/07/14(土) 20:04:39.81ID:wFLY+TGv
お題: マップの広さと部屋の個数及び部屋間の繋がりが与えられた時、ダンジョンを作成せよ
・ダンジョンは部屋と通路からなる
・部屋は少なくとも3x4の大きさを持つ
・通路の幅は1
・部屋同士は接しない
・マップ外に部屋や通路は無い
一応、想定としては標準出力に'#'と'.'で表示を考えてる
生成方法は自由だからゲーム的面白さのあるマップ作っても良い
0607 ◆QZaw55cn4c
垢版 |
2018/07/14(土) 21:29:48.92ID:CBXc6tpD
>>604
>>598 の問題はおもしろいし、お題として成立していると思います
・再帰を使用しないマージソートを実装
・作業領域を元のデータの半分の量しか確保せずにソートを実行する
で考えているところです
0615デフォルトの名無しさん
垢版 |
2018/07/15(日) 00:23:22.27ID:upVjqm6g
>>609
クラスもありかも知れない。クラスの中にはメソッドがある。メソッドはメソッドであって関数ではない。
あるいは procedure でも良いのかも知れない。procedure は手続きであって関数ではない。
サブルーチンもありかも知れない。
昔のマイコン用のBASICでVRAMに直接 POKE で値を書き込んだりするのもありかも知れない。

もはや一休さん並のトンチであり言葉遊びである。
0625デフォルトの名無しさん
垢版 |
2018/07/15(日) 09:17:28.76ID:rFf4w5JC
「何々禁止で何々を書け」って類いの問題で面白くなることはあんましないな
0629デフォルトの名無しさん
垢版 |
2018/07/15(日) 13:13:37.51ID:9lve5q3D
これ宿題じゃないですよ
ここに書く前にコードも書いてたしもっと効率いい方法ここの人達なら知ってそうだと思ったから
0630デフォルトの名無しさん
垢版 |
2018/07/15(日) 13:15:21.60ID:kiP00q0W
>>599
1 2 3 4 -> 001002003004
97 98 99 100 -> 097098099100
0632デフォルトの名無しさん
垢版 |
2018/07/15(日) 14:14:11.66ID:9lve5q3D
>>619のもっと効率悪い奴だよ
元は100C4じゃなくて28C4だったけど
int cc[4][32][32];
こんな二次元の配列使ってた
0635デフォルトの名無しさん
垢版 |
2018/07/15(日) 14:33:39.46ID:ugn7dRUi
それの何が不満？
何をどう改善したいのかわからないと

テーブル作成の速度？
テーブル検索の速度？
コードサイズ？
バイナリサイズ？
コードの分かりやすさや移植性？
0639デフォルトの名無しさん
垢版 |
2018/07/15(日) 21:44:41.62ID:WaX+Eind
605、出題しておいて何だがこれめっちゃ難しいな
マップの大きさの制約があると通路引くのが難しすぎる
0644 ◆QZaw55cn4c
垢版 |
2018/07/16(月) 11:53:01.88ID:PLRcL5uS
>>643
一般に、再帰を非再帰に書き下すのは難しいのです…
0645デフォルトの名無しさん
垢版 |
2018/07/16(月) 13:51:43.31ID:yJ4dWfp7
お題
ポーランド記法による計算機を実装せよ
演算子は加算(+)と乗算(*)をサポートすること

* + 1 5 + 2 3
=> 30

* * * * 2 3 4 5 6
=> 720
0649デフォルトの名無しさん
垢版 |
2018/07/16(月) 14:36:11.63ID:dBK+PWCu
>>645 Ruby 2.5.0
[
"* + 1 5 + 2 3",
"* * * * 2 3 4 5 6"
].each do |_exp|
exp = +-_exp
nil while exp.gsub!(/([^\d\s]+) +(\d+) +(\d+)/){$2.to_i.send($1, $3.to_i)}
puts '%s => %s' % [_exp, exp]
end
#=>
* + 1 5 + 2 3 => 30
* * * * 2 3 4 5 6 => 720
0651デフォルトの名無しさん
垢版 |
2018/07/19(木) 21:45:59.55ID:bv0mlJEL
お題

N個の整数(a_1, a_2, ..., a_n, ..., a_N)と*+/()を使った数式の値が、ある整数aにもっとも近い数式とその値(実数)を出力せよ

引き算はなし
a_n = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
0653デフォルトの名無しさん
垢版 |
2018/07/24(火) 10:08:13.30ID:Dnr6z2Ly
>>606
>>605のは要はローグライクの部屋を作れってことだろ

出題者の説明不足
画像の1枚でも張れば見て分かる

ttps://cdn-ak.f.st-hatena.com/images/fotolife/g/gaou2/20170905/20170905111314.png
0658デフォルトの名無しさん
垢版 |
2018/07/26(木) 01:28:14.71ID:NOsumJU/
いやさすがに数学板でやれや。
国際数学オリンピックて自分で言うてるやんけ
0660デフォルトの名無しさん
垢版 |
2018/07/26(木) 03:14:46.46ID:64IGnOgv
いやこれは総当たりでは計算量的に無理だろ
コードは書けるだろうけど
存在することを帰納法で証明するしかないから数学板の問題だ
0661デフォルトの名無しさん
垢版 |
2018/07/26(木) 09:13:59.71ID:1RynmuAu
まーた数学コンプレックスが暴れてるのか
数オリに出るくらいの賢さがないから計算機の力も借りて解くっていう方向性は別にスレチじゃないだろ
0662デフォルトの名無しさん
垢版 |
2018/07/26(木) 09:22:17.32ID:NOsumJU/
ここでレスリングの話しだして苦言を呈されると「まーたレスリングコンプレックスが暴れてるのか」
極端に言うとこういうこと。
レスリング板、数学板があるだろ。
わざわざここでオナニーしたいのは専門以外の板でマウント取りたいのかな？
そんなひねくれた根性だから現実世界でミジメな生活なんだよ。
0663デフォルトの名無しさん
垢版 |
2018/07/26(木) 09:30:59.20ID:1RynmuAu
早速暴れてて草
正攻法で数オリの問題を解く話を延々してたんならうざいけど
飽くまで計算機使って解いてみようぜって言ってる人にまでその理屈が当てはまるわけないだろ
それとも数学だけじゃなくて論理的思考もできないタイプか？それなら納得だわｗ
0664デフォルトの名無しさん
垢版 |
2018/07/26(木) 10:44:43.72ID:NOsumJU/
数学で解ける問題をわざわざコンピューターでムダな解き方するの？？
突き詰めていくと数学で出した解法そのまま引き写すだけになるのが分かりきってるのに。
0665デフォルトの名無しさん
垢版 |
2018/07/26(木) 10:51:14.48ID:1RynmuAu
だからわざわざ「数オリに出るくらいの賢さがないから」って言ってるだろ日本語読めねえのかよ
そりゃ灘の入試レベルならその通りだろうけど数オリで正解率1割切ってたような問題なんだから計算機使ったアプローチしてみるのもプログラミングのお題としては面白いだろ
それともなんだ、円周率の計算だってペンと紙でできるんだから無駄だっていうのか？ｗ
そんな極論言うレベルの頭だから数学もできないんだよｗ
0666デフォルトの名無しさん
垢版 |
2018/07/26(木) 11:36:12.38ID:64IGnOgv
そういう無駄に一般化した話も結構だけど、
個別具体的な話として>>597は計算機を併用することに効果が無いから数学の問題だと言ってるんだよ。

2018を解けるほど効率化できるなら既に人力で解けているだろうからね。
0667デフォルトの名無しさん
垢版 |
2018/07/26(木) 13:48:16.24ID:YvrMO5FL
それは総当たり以外にうまい方法が思い浮かばないから言えるだけでしょうよ。
あと素数判定アルゴリズムなんか考えればわかるけど、効率化できることと人力で解けることに相関はないぞ。
少なくともスレチではないと思うよ。
0668デフォルトの名無しさん
垢版 |
2018/07/26(木) 14:31:11.72ID:v+At+/4W
部外者だが

嫌なら回答しなきゃいいだけなのに
何文句言ってるの？
って感じ
0672デフォルトの名無しさん
垢版 |
2018/07/27(金) 00:30:20.41ID:1FlI+KkW
作るのは無理な気がするがよーわからん

一番大きい数値 1+2+…2018 = 2037171 は差の絶対値で作れないので最下段確定
一番大きい数値を出来るだけ上段に伝搬させるために小さい数値(1~2017)と組み合わせていっても最上段に残るのは 2018
→ 2019 以上と組み合わせると 2017 未満の数値がダブる
最下段で 2037171 と 1 を組み合わせた場合、 2037169 も最下段に設置する必要がある
2037169 は 1~2018 の大部分と組み合わせられないので上のほうまで伝搬できずにアウト
0673デフォルトの名無しさん
垢版 |
2018/07/27(金) 01:35:56.64ID:DQ/IIgai
その長々とした理屈は2018が7でも6でも同様のことが言えるよね
そして7や6には解がある
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況