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

**デフォルトの名無しさん** · 2018/04/24(火) 20:45:14.49

プログラミングのお題スレです。

前スレ
プログラミングのお題スレ 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/

宿題は宿題スレがあるのでそちらへ。

**デフォルトの名無しさん** · 2018/07/12(木) 17:25:23.25

>>587だと灘の問題全て捨て問題になりそう

**デフォルトの名無しさん** · 2018/07/12(木) 18:14:20.08

>>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であると確定する

**デフォルトの名無しさん** · 2018/07/12(木) 19:16:30.21

えらい省略したねえ

**デフォルトの名無しさん** · 2018/07/13(金) 02:14:22.89

>>569
問1のみ
Kotlin
https://paiza.io/projects/rG4rKSs27X473v0qxyicHQ
何も考えずに全パターン調べているだけ。

**デフォルトの名無しさん** · 2018/07/13(金) 02:29:27.10

>>569
問2のみ
Kotlin
https://paiza.io/projects/RS3SPZeRhx0caTVXDHQmaw
こっちの方が簡単だったな。

**デフォルトの名無しさん** · 2018/07/13(金) 07:35:11.88

>>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

**デフォルトの名無しさん** · 2018/07/13(金) 08:03:43.23

>>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

**デフォルトの名無しさん** · 2018/07/13(金) 08:58:11.48

rubyならさくっとワンライナーで
p (10000-10000%-36).step(10**5,36).find{|i|(i.digits&[2,3,5])[2]}
#=> 13572

**569** · 2018/07/13(金) 16:26:20.44

>>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

**デフォルトの名無しさん** · 2018/07/14(土) 05:33:19.05

国際数学オリンピック
問３反パスカル的三角形
https://twitter.com/worapolketanond/status/1017612366840717312

**デフォルトの名無しさん** · 2018/07/14(土) 13:47:04.74

そろそろ新しいお題を。
既出なら申し訳ない。

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

追加お題：
上記のマージソート処理の際、作業領域を元のデータの半分の量しか確保せずにソートを実行するプログラムを作成しなさい。

**デフォルトの名無しさん** · 2018/07/14(土) 15:13:06.98

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

**デフォルトの名無しさん** · 2018/07/14(土) 15:22:22.12

>>598
残念ながら余り良い問題じゃない希ガス

**デフォルトの名無しさん** · 2018/07/14(土) 15:57:46.49

スタック不可だとスタック操作が隠蔽されてる高級言語はほぼ使用出来ない
無理やりCやC++でやるとしてもローカル変数や関数呼び出しを殆ど封印しなければならない
これを良い問題と見るか悪い問題と見るかは分からないが俺はやる気が出ない

**デフォルトの名無しさん** · 2018/07/14(土) 16:00:11.93

>>599
組み合わせか

北大の湊真一のZDD とか。
本も出てる

**デフォルトの名無しさん** · 2018/07/14(土) 17:25:12.68

お題：Hello, World!を出力せよ。ただし出力系の関数を使ってはならない。

**デフォルトの名無しさん** · 2018/07/14(土) 18:41:01.92

>>601

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

>>600
ご期待に添えず申し訳ない。他のお題を思いついたら、また出題させていただきます。

**デフォルトの名無しさん** · 2018/07/14(土) 20:04:39.81

お題: マップの広さと部屋の個数及び部屋間の繋がりが与えられた時、ダンジョンを作成せよ
・ダンジョンは部屋と通路からなる
・部屋は少なくとも3x4の大きさを持つ
・通路の幅は1
・部屋同士は接しない
・マップ外に部屋や通路は無い
一応、想定としては標準出力に'#'と'.'で表示を考えてる
生成方法は自由だからゲーム的面白さのあるマップ作っても良い

**デフォルトの名無しさん** · 2018/07/14(土) 20:21:35.37

解釈がいろいろあり過ぎて
コードに対して仕様の説明文が必要になるぞ

◆QZaw55cn4c · 2018/07/14(土) 21:29:48.92

>>604
>>598 の問題はおもしろいし、お題として成立していると思います
・再帰を使用しないマージソートを実装
・作業領域を元のデータの半分の量しか確保せずにソートを実行する
で考えているところです

**デフォルトの名無しさん** · 2018/07/14(土) 22:17:39.11

>>603
出力せよといいつつ、出力系は使うなとは、まるで一休さんのような

**デフォルトの名無しさん** · 2018/07/14(土) 22:31:41.56

まて、関数は、とある
つまりはシステムコールを直につかうんだ！

**デフォルトの名無しさん** · 2018/07/15(日) 00:13:47.62

>>603
じゃあC言語で。

#include <stdio.h>

int main()
{]

**デフォルトの名無しさん** · 2018/07/15(日) 00:14:11.69

ごめん途中で書き込みボタン押してしまった。

**デフォルトの名無しさん** · 2018/07/15(日) 00:15:38.60

>>603

#include <stdio.h>

int main()
{
　system("echo Hello, World!");
　return 0;
}

**デフォルトの名無しさん** · 2018/07/15(日) 00:16:57.24

>>609
システムコールの内部は関数
だったりして

**デフォルトの名無しさん** · 2018/07/15(日) 00:17:46.78

>>612
それ関数

**デフォルトの名無しさん** · 2018/07/15(日) 00:23:22.27

>>609
クラスもありかも知れない。クラスの中にはメソッドがある。メソッドはメソッドであって関数ではない。
あるいは procedure でも良いのかも知れない。procedure は手続きであって関数ではない。
サブルーチンもありかも知れない。
昔のマイコン用のBASICでVRAMに直接 POKE で値を書き込んだりするのもありかも知れない。

もはや一休さん並のトンチであり言葉遊びである。

**デフォルトの名無しさん** · 2018/07/15(日) 00:24:49.27

>>614
出力系の関数は一切使っていない。

**デフォルトの名無しさん** · 2018/07/15(日) 00:26:13.41

関数を使わないとなると
int 21
とかじゃないの？

**デフォルトの名無しさん** · 2018/07/15(日) 00:46:35.39

>>603
J
'Hello, World!'

REPL な処理系なら簡単

**デフォルトの名無しさん** · 2018/07/15(日) 01:18:12.57

>>599
とりあえず出来たけどもっと簡単に変換する方法があるような気がする
https://ideone.com/EnmoNU

**デフォルトの名無しさん** · 2018/07/15(日) 03:18:16.17

cat
Hello, World!

もはやプログラムですらない。

**デフォルトの名無しさん** · 2018/07/15(日) 08:10:13.37

>>599
100この中から4個を選ぶことだから完全最小ハッシュ関数が使える

**デフォルトの名無しさん** · 2018/07/15(日) 08:20:59.61

>>603
紙にペンでHello, World! と書く。

**デフォルトの名無しさん** · 2018/07/15(日) 08:21:04.86

>>603
紙にペンでHello, World! と書く。

**デフォルトの名無しさん** · 2018/07/15(日) 08:24:39.94

10 PRINT "Hello, World!"

**デフォルトの名無しさん** · 2018/07/15(日) 09:17:28.76

「何々禁止で何々を書け」って類いの問題で面白くなることはあんましないな

**デフォルトの名無しさん** · 2018/07/15(日) 09:35:01.35

>>599 Java
https://ideone.com/oI3bvA
完全最小ハッシュ関数でぐぐっちゃった

**デフォルトの名無しさん** · 2018/07/15(日) 12:21:14.41

>>621
>>626
考え方分かりました
ありがとうございました

**デフォルトの名無しさん** · 2018/07/15(日) 13:09:18.09

質問一回許すとなし崩しに宿題だらけになるぞ。警告はした。

**デフォルトの名無しさん** · 2018/07/15(日) 13:13:37.51

これ宿題じゃないですよ
ここに書く前にコードも書いてたしもっと効率いい方法ここの人達なら知ってそうだと思ったから

**デフォルトの名無しさん** · 2018/07/15(日) 13:15:21.60

>>599
1 2 3 4 -> 001002003004
97 98 99 100 -> 097098099100

**デフォルトの名無しさん** · 2018/07/15(日) 14:11:04.01

>>629
よし、そのコードを貼るのだ

**デフォルトの名無しさん** · 2018/07/15(日) 14:14:11.66

>>619のもっと効率悪い奴だよ
元は100C4じゃなくて28C4だったけど
int cc[4][32][32];
こんな二次元の配列使ってた

**デフォルトの名無しさん** · 2018/07/15(日) 14:19:01.22

いいから貼れ

**デフォルトの名無しさん** · 2018/07/15(日) 14:26:45.03

https://ideone.com/VFv36f
2年前に書いたやつで今は何やってるかよく分からないけど
>>619のは昨日元のこのコードを見ないで30分くらい考えて作った

**デフォルトの名無しさん** · 2018/07/15(日) 14:33:39.46

それの何が不満？
何をどう改善したいのかわからないと

テーブル作成の速度？
テーブル検索の速度？
コードサイズ？
バイナリサイズ？
コードの分かりやすさや移植性？

**デフォルトの名無しさん** · 2018/07/15(日) 14:35:44.41

何がってほぼ全てが不満だけど

**デフォルトの名無しさん** · 2018/07/15(日) 14:36:24.88

ああ、
速度とメモリって書いてあったね

**デフォルトの名無しさん** · 2018/07/15(日) 15:22:45.17

宿題スレでやれ

**デフォルトの名無しさん** · 2018/07/15(日) 21:44:41.62

605、出題しておいて何だがこれめっちゃ難しいな
マップの大きさの制約があると通路引くのが難しすぎる

**デフォルトの名無しさん** · 2018/07/15(日) 22:38:32.27

いちおう解けるのを自分で確認してから出してくれないと困る

**デフォルトの名無しさん** · 2018/07/15(日) 23:36:44.29

>>639
>>606

**デフォルトの名無しさん** · 2018/07/16(月) 00:30:52.75

入力と出力の例とかあると良いよね

**デフォルトの名無しさん** · 2018/07/16(月) 10:10:17.82

>>607
で、出来てる？

◆QZaw55cn4c · 2018/07/16(月) 11:53:01.88

>>643
一般に、再帰を非再帰に書き下すのは難しいのです…

**デフォルトの名無しさん** · 2018/07/16(月) 13:51:43.31

お題
ポーランド記法による計算機を実装せよ
演算子は加算(+)と乗算(*)をサポートすること

* + 1 5 + 2 3
=> 30

* * * * 2 3 4 5 6
=> 720

**デフォルトの名無しさん** · 2018/07/16(月) 13:53:41.91

ただし、スタックを使用してはならない

**デフォルトの名無しさん** · 2018/07/16(月) 13:56:53.16

さらに、分数と複素数をサポートすること

**デフォルトの名無しさん** · 2018/07/16(月) 14:01:43.77

まーた、～を使わないで、か。
宿題か何かかな

**デフォルトの名無しさん** · 2018/07/16(月) 14:36:11.63

>>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

**デフォルトの名無しさん** · 2018/07/18(水) 02:22:22.35

>>645
Kotlin で二つ作った。

Stack 使ったやつ。
https://paiza.io/projects/Qnrrux74abDRsr1kh77FNA

Stack 使わずに MutableList で計算記号、数、数のパターンを計算できなくなるまで繰り返し計算するやつ。
enumも使用。
https://paiza.io/projects/rHKDVtB2yjTvymuFLlBL7g

**デフォルトの名無しさん** · 2018/07/19(木) 21:45:59.55

お題

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

引き算はなし
a_n = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

**デフォルトの名無しさん** · 2018/07/19(木) 21:52:08.91

うんざり

**デフォルトの名無しさん** · 2018/07/24(火) 10:08:13.30

>>606
>>605のは要はローグライクの部屋を作れってことだろ

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

ttps://cdn-ak.f.st-hatena.com/images/fotolife/g/gaou2/20170905/20170905111314.png

**デフォルトの名無しさん** · 2018/07/24(火) 12:45:23.08

これ見た目では普通だけどかなり横に長い部屋なんだよな

**デフォルトの名無しさん** · 2018/07/24(火) 12:55:16.04

部屋と通路以外の場所も存在するのかよ

**デフォルトの名無しさん** · 2018/07/24(火) 13:01:35.53

>>654
今だと全角文字で作ればいいかな。絵文字もまじえて。

**デフォルトの名無しさん** · 2018/07/26(木) 00:47:20.34

>>597 Java
https://ideone.com/VUgSXO
1行～5行までしか答え出ないな

うちの環境で
9行を探索するのに4.6秒
10行を探索するのに61.6秒
2018行はあかんｗｗ

**デフォルトの名無しさん** · 2018/07/26(木) 01:28:14.71

いやさすがに数学板でやれや。
国際数学オリンピックて自分で言うてるやんけ

**デフォルトの名無しさん** · 2018/07/26(木) 02:06:08.36

数学とか使わずに総当たりでやってるのに数学板に行けとな

**デフォルトの名無しさん** · 2018/07/26(木) 03:14:46.46

いやこれは総当たりでは計算量的に無理だろ
コードは書けるだろうけど
存在することを帰納法で証明するしかないから数学板の問題だ

**デフォルトの名無しさん** · 2018/07/26(木) 09:13:59.71

まーた数学コンプレックスが暴れてるのか
数オリに出るくらいの賢さがないから計算機の力も借りて解くっていう方向性は別にスレチじゃないだろ

**デフォルトの名無しさん** · 2018/07/26(木) 09:22:17.32

ここでレスリングの話しだして苦言を呈されると「まーたレスリングコンプレックスが暴れてるのか」
極端に言うとこういうこと。
レスリング板、数学板があるだろ。
わざわざここでオナニーしたいのは専門以外の板でマウント取りたいのかな？
そんなひねくれた根性だから現実世界でミジメな生活なんだよ。

**デフォルトの名無しさん** · 2018/07/26(木) 09:30:59.20

早速暴れてて草
正攻法で数オリの問題を解く話を延々してたんならうざいけど
飽くまで計算機使って解いてみようぜって言ってる人にまでその理屈が当てはまるわけないだろ
それとも数学だけじゃなくて論理的思考もできないタイプか？それなら納得だわｗ

**デフォルトの名無しさん** · 2018/07/26(木) 10:44:43.72

数学で解ける問題をわざわざコンピューターでムダな解き方するの？？
突き詰めていくと数学で出した解法そのまま引き写すだけになるのが分かりきってるのに。

**デフォルトの名無しさん** · 2018/07/26(木) 10:51:14.48

だからわざわざ「数オリに出るくらいの賢さがないから」って言ってるだろ日本語読めねえのかよ
そりゃ灘の入試レベルならその通りだろうけど数オリで正解率1割切ってたような問題なんだから計算機使ったアプローチしてみるのもプログラミングのお題としては面白いだろ
それともなんだ、円周率の計算だってペンと紙でできるんだから無駄だっていうのか？ｗ
そんな極論言うレベルの頭だから数学もできないんだよｗ

**デフォルトの名無しさん** · 2018/07/26(木) 11:36:12.38

そういう無駄に一般化した話も結構だけど、
個別具体的な話として>>597は計算機を併用することに効果が無いから数学の問題だと言ってるんだよ。

2018を解けるほど効率化できるなら既に人力で解けているだろうからね。

**デフォルトの名無しさん** · 2018/07/26(木) 13:48:16.24

それは総当たり以外にうまい方法が思い浮かばないから言えるだけでしょうよ。
あと素数判定アルゴリズムなんか考えればわかるけど、効率化できることと人力で解けることに相関はないぞ。
少なくともスレチではないと思うよ。

**デフォルトの名無しさん** · 2018/07/26(木) 14:31:11.72

部外者だが

嫌なら回答しなきゃいいだけなのに
何文句言ってるの？
って感じ

**デフォルトの名無しさん** · 2018/07/26(木) 15:16:02.44

そんなことより野球のはなししようぜ！嫌なら無視すりゃいいだけ。

**デフォルトの名無しさん** · 2018/07/26(木) 15:40:53.67

さすがにそれはスレチ

**デフォルトの名無しさん** · 2018/07/26(木) 20:25:33.46

アプローチ以前に
>>597の問題って存在するの
それとも無いの

**デフォルトの名無しさん** · 2018/07/27(金) 00:30:20.41

作るのは無理な気がするがよーわからん

一番大きい数値 1+2+…2018 = 2037171 は差の絶対値で作れないので最下段確定
一番大きい数値を出来るだけ上段に伝搬させるために小さい数値(1~2017)と組み合わせていっても最上段に残るのは 2018
→ 2019 以上と組み合わせると 2017 未満の数値がダブる
最下段で 2037171 と 1 を組み合わせた場合、 2037169 も最下段に設置する必要がある
2037169 は 1~2018 の大部分と組み合わせられないので上のほうまで伝搬できずにアウト

**デフォルトの名無しさん** · 2018/07/27(金) 01:35:56.64

その長々とした理屈は2018が7でも6でも同様のことが言えるよね
そして7や6には解がある

**デフォルトの名無しさん** · 2018/07/27(金) 01:42:27.70

>>673
適当に作ったプログラム(>>657)じゃ5までしか見つかっとらんのだけど、6や7にも解あるんか

**デフォルトの名無しさん** · 2018/07/27(金) 02:06:17.44

ないのかごめん
でも5でも同じことは言えるような

**デフォルトの名無しさん** · 2018/07/27(金) 04:54:59.02

5以下の場合は数字が足りなくなる前に最大値からの流れに合流出来てるんじゃね？

**デフォルトの名無しさん** · 2018/07/27(金) 07:39:19.67

>>674
>>657じゃなくてCで書いたけど6～40までは解無し

**デフォルトの名無しさん** · 2018/07/27(金) 07:52:55.93

数オリ経験者、東大数学科卒だけど
今度挑戦してみるか

**デフォルトの名無しさん** · 2018/07/27(金) 18:20:03.99

お題
非負整数nが与えられるので、以下に示すような六角形状の螺旋を描画せよ
https://ideone.com/MmH3N6

**デフォルトの名無しさん** · 2018/07/27(金) 19:00:06.01

>>679

質問です。
n>99の場合はズレが生じてくると思いますが、その時はどうしますか？
それともn≦99で範囲を絞ってもよろしいんでしょうか？

まぁ、私が作れるかどうか分からないんですがorz

**デフォルトの名無しさん** · 2018/07/27(金) 19:20:13.92

ご自由にどうぞ

**デフォルトの名無しさん** · 2018/07/27(金) 20:32:22.83

難しそうだが良いお題だな
こういうお題を考えられるようになりたい

**デフォルトの名無しさん** · 2018/07/28(土) 12:28:46.99

まずは数学から入るか

中心つき六角数 - Wikipedia
ttps://ja.wikipedia.org/wiki/%E4%B8%AD%E5%BF%83%E3%81%A4%E3%81%8D%E5%85%AD%E8%A7%92%E6%95%B0

**デフォルトの名無しさん** · 2018/07/29(日) 08:56:47.82

>>680
nの大きさに合わせて-の数を決めれば、歪にならないと思うよ。

**597** · 2018/07/29(日) 11:00:51.11

こんな資料がありました
https://ja.scribd.com/document/383589785/toads-pdf
http://w3.math.sinica.edu.tw/bulletin/bulletin_old/d51/5120.pdf

**デフォルトの名無しさん** · 2018/07/29(日) 13:36:35.25

>>685
へ～やっぱ n = 5 までしかないんだな
後でちゃんと読んどくわ

**デフォルトの名無しさん** · 2018/07/29(日) 17:52:03.38

出題者は自分で書けるのを一度確認してから出題してほしいわ