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

**デフォルトの名無しさん** · 2019/07/28(日) 19:39:57.54

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

【出題と回答例】
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/

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

※前スレ
プログラミングのお題スレ Part14
http://mevius.5ch.net/test/read.cgi/tech/1558168409/

**デフォルトの名無しさん** · 2019/07/28(日) 21:03:19.25

宿題、チューリングの泥沼、条件不足等回避のため
出題者は自分で回答可能か確認してからお題を出すこと

**デフォルトの名無しさん** · 2019/07/28(日) 21:08:20.48

※QZは書き込み禁止

**デフォルトの名無しさん** · 2019/07/28(日) 21:32:12.69

お題
とあるゲームでは、10面ダイスによってスコアを次のように定める
1. x個のダイスを全部振る
2. 振ったダイスのうち、最大の出目をスコアとする
3. 出目がc以上のダイスが存在するなら、その全てのダイスを使って同じ試行を行い、スコアに加算する
例えばc=7の時、2個のダイスの結果が(10,7)→(8,3)→(2)ならスコアは10+8+2=20となる
最初に振るダイスの個数Nとc(≧2)が分かっている時、スコアの期待値を求めよ

**デフォルトの名無しさん** · 2019/07/29(月) 11:14:17.89

>>4
https://ideone.com/GgQh2t
C++,モンテカルロしてみた。
値がちょっと怖い値になったので、バグ報告歓迎。

**デフォルトの名無しさん** · 2019/07/29(月) 11:34:20.96

https://ideone.com/geZ4qP
>>5が不安だったので、出力変えてみたけど、最大値で500近くになるんだな。
何かビビった。

**デフォルトの名無しさん** · 2019/07/29(月) 11:49:50.47

サイコロの偏りをもっと明確にしたいなら、乱数エンジンを複数持つか、ランダムデバイスそのもので実行する。
ランダムデバイスは遅いことになってるのでMTに投げるんだけど。

**デフォルトの名無しさん** · 2019/07/29(月) 11:55:28.48

一様乱数のサイコロは、現実では職人が作ったサイコロですなあ。

**蟻人間** ◆T6xkBnTXz7B0 · 2019/07/30(火) 00:00:42.86

お題: 炭素原子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)).

**デフォルトの名無しさん** · 2019/07/30(火) 03:21:18.39

問題がわかりづらい。

**デフォルトの名無しさん** · 2019/07/30(火) 06:42:15.48

出題者は自分で解けることを確認してからお題にしてるのかね？
自明でない不可能な場合の例とか出してこないし怪しいもんだ

**デフォルトの名無しさん** · 2019/07/30(火) 10:22:50.80

慣れない言語の勉強に使うのに丁度いいね
出題者が答えも貼っといてくれるとありがたい(´・ω・｀)

**デフォルトの名無しさん** · 2019/07/30(火) 16:13:07.32

良いプログラムは良い数式がないと作れないのでこのスレは過疎化する。

**デフォルトの名無しさん** · 2019/07/30(火) 16:39:56.09

久々にこの板きたけど、宿題スレってなくなったんだね

**蟻人間** ◆T6xkBnTXz7B0 · 2019/07/30(火) 16:51:52.79

解空間は、サイズ(p+q+r)×(p+q+r)の整数行列の集合になる。
結合の手の個数は有限だから、解行列の成分は上限がある。
よって行列の各成分についてしらみつぶし探索が可能。

自分自身とは結合しないので、A[k,k]＝0（つまり、行列の対角成分はゼロ）。
ある行の和は、行番号に対応する原子の結合の手の個数になる。
ある列の和は、列番号に対応する原子の結合の手の個数になる。
連結条件のチェックが必要。

**デフォルトの名無しさん** · 2019/07/30(火) 17:04:44.75

お題: 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

**デフォルトの名無しさん** · 2019/07/30(火) 17:10:40.80

>>14
基地外粘着uyによって潰された

**デフォルトの名無しさん** · 2019/07/30(火) 19:44:50.09

>>13
良い数式が立てられないのでモンテカルロに酔っているオレ・・・。

◆QZaw55cn4c · 2019/07/30(火) 20:12:47.58

>>9
複雑すぎます
非環状アルカン（CnH2n+2）の構造異性体を列挙せよ、という簡略化したお題を提案します

◆QZaw55cn4c · 2019/07/30(火) 20:13:36.62

>>14
存在することはするのですが、誰も近寄らなくなりました、キチガイが一匹しつこく居候しているので

**デフォルトの名無しさん** · 2019/07/30(火) 21:52:06.20

>>20
つ鏡

**デフォルトの名無しさん** · 2019/07/30(火) 23:15:45.71

>>21
草生える

**デフォルトの名無しさん** · 2019/07/30(火) 23:24:02.31

お題: 1 + 1 を計算させて 3 と出力させなさい

**デフォルトの名無しさん** · 2019/07/30(火) 23:34:18.81

>>23 Perl5

$a = 1 + 1;
print ~$a%10;

実行結果
$ perl 15_23.pl
3

※64bit整数版で実行してね

**デフォルトの名無しさん** · 2019/07/31(水) 00:12:45.83

>>23
perl5

print ("1", "+", "1")
1+1
print $_ =()= ("1", "+", "1")
3

**デフォルトの名無しさん** · 2019/07/31(水) 04:39:05.16

>>23
perl

1+1;
print "3\n"

**デフォルトの名無しさん** · 2019/07/31(水) 05:06:41.43

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

**デフォルトの名無しさん** · 2019/07/31(水) 09:55:03.07

>>23
perl5

print qw(1 + 1)
1+1
print eval q(1 + 1)
2
print $_ =()= qw(1 + 1)
3

**デフォルトの名無しさん** · 2019/07/31(水) 14:18:08.83

お題、東大入試

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

**デフォルトの名無しさん** · 2019/07/31(水) 14:46:10.23

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

**デフォルトの名無しさん** · 2019/07/31(水) 15:57:49.04

・女体限定で、3次元の写真から3Dポリゴンモデルデータを自動作成
・そのデータから胴体部の着衣部分を、裸モデルに修正
・水着でついた脇乳の段差も修正
・元写真の地肌色を使い、女体テンプレのテクスチャを作成
・完成したモデルから胴体部だけ精密レンダリング
・元の写真に貼り付けて完成

**デフォルトの名無しさん** · 2019/07/31(水) 17:25:11.51

プログラミングのお題スレ Part14
https://mevius.5ch.net/test/read.cgi/tech/1558168409/981-986

漏れは、前スレの981 ではないですが、この問題の応用で、

括弧のネストの深さの最大値を求めよ

括弧の対応が取れていない場合は、-1 を出力せよ。
2種類の括弧が順序通りに、閉じていないものも、-1 です

ヒント : stack を使うと良いかも

"" => 0
"( )" => 1
"{ ( { ( ) } ( ) ) } ( )" => 4

"} {" => -1
"( { ) }" => -1

**デフォルトの名無しさん** · 2019/07/31(水) 20:22:09.77

自分でスタックするか再起にして自動で積ませるか、といったところか。

**デフォルトの名無しさん** · 2019/07/31(水) 21:44:23.62

>>32 Java
https://ideone.com/dIdH1J

**デフォルトの名無しさん** · 2019/07/31(水) 22:14:16.43

>>32
perl5
http://ideone.com/X5OIjN

**デフォルトの名無しさん** · 2019/07/31(水) 22:19:24.27

ideone バグっているのか？
STDIN の1行目空だと
ちゃんと標準入力としてプログラムに伝わっているけど
リンク先の stdin 枠の中だと省略されているように見える

stdout の 0 はその空を受け取ったもの

**デフォルトの名無しさん** · 2019/07/31(水) 22:42:26.48

twitterやっていたようなので
そこにバグフィックス要請とテストケース画像貼っておいた
たぶんそのうち直るでしょう

**デフォルトの名無しさん** · 2019/07/31(水) 23:32:10.18

問題
n桁のヒットアンドブローのソルバーを作る。

**デフォルトの名無しさん** · 2019/07/31(水) 23:34:51.48

君の言っていることの意味がよくわからない。

**デフォルトの名無しさん** · 2019/08/01(木) 00:15:32.73

>>37
GJ

**デフォルトの名無しさん** · 2019/08/01(木) 15:40:09.21

>>38
大分前に作ったけど、コード紛失した。
アルゴリズムも忘れた。

ガーン。

**デフォルトの名無しさん** · 2019/08/01(木) 15:47:29.97

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

**デフォルトの名無しさん** · 2019/08/01(木) 16:10:15.37

>>42
wolfram
Simplify[ x-y, {5000000 == (a+x)*1.08,5000000 == (a+y)*1.1} ]
84175.1

**デフォルトの名無しさん** · 2019/08/01(木) 16:16:06.40

切り上げか
Ceiling[ Simplify[ x-y, {5000000 ==(a+x)*1.08 == (a+y)*1.1} ] ]

84176

**デフォルトの名無しさん** · 2019/08/01(木) 16:17:25.45

何も考えずにceiling(n/1.08-n/1.1)でいいんとちゃうけ？

**デフォルトの名無しさん** · 2019/08/01(木) 19:07:52.51

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

**デフォルトの名無しさん** · 2019/08/01(木) 21:02:36.17

>>45
ちょっと考えたらceiling(n/59.4)だったｗ

**デフォルトの名無しさん** · 2019/08/02(金) 20:14:36.58

お題: 数字が与えられるので、その数字を元の数より大きくなるように再構築せよ
大きくできなければ元の数字をそのまま出力せよ

例:
in < 123
out > 231, 213, 321, 312

in < 921
out > 921

**デフォルトの名無しさん** · 2019/08/02(金) 20:54:30.15

123を入力したときに132が出力されないのはなぜ?

**デフォルトの名無しさん** · 2019/08/02(金) 21:09:12.36

パーミュテーション作って終わりじゃあないのコレ

**デフォルトの名無しさん** · 2019/08/02(金) 21:52:24.70

>>49
ミスだよぉ！

**デフォルトの名無しさん** · 2019/08/02(金) 22:45:44.46

そんなんばっかだなお前

**デフォルトの名無しさん** · 2019/08/03(土) 01:06:14.19

>>48
https://ideone.com/fyfMQH
C++。ご期待通り（？）にパーミテーション回してみたよ。
重いお。

**デフォルトの名無しさん** · 2019/08/03(土) 10:23:36.04

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

**デフォルトの名無しさん** · 2019/08/03(土) 10:27:27.22

なんて早いんだ

**デフォルトの名無しさん** · 2019/08/03(土) 11:19:47.14

「大きくできなければ元の数字をそのまま出力せよ」という条件が
ことごとく無視されててワロタ

あと、「133」みたいに同じ数字が複数含まれる場合はどうなるべきなんだろう

**デフォルトの名無しさん** · 2019/08/03(土) 11:39:39.93

>>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を使ってみた

**デフォルトの名無しさん** · 2019/08/03(土) 11:43:50.21

>>57 ごめんなさい
print "$n " if $n > $v;
↓
print "$n " if $n >= $v;

じゃないと「大きくできなければ元の数字をそのまま出力せよ」を満たさなかった…orz

**デフォルトの名無しさん** · 2019/08/03(土) 11:49:41.56

>>58 そうすると逆に
「元の数「より大きくなる」ように再構築せよ」
については、元の数値が余計に出力されるな…ｺﾞﾒﾝねもう一工夫要るわ
それにiteratorである必要ないわ

**デフォルトの名無しさん** · 2019/08/03(土) 12:09:48.13

>>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で解けた

**デフォルトの名無しさん** · 2019/08/03(土) 16:01:35.10

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

**デフォルトの名無しさん** · 2019/08/03(土) 19:53:41.57

>>48だけど、>>56の要件を見落としていたので入れてみたよ。
https://ideone.com/h2KrQu
C++。

**デフォルトの名無しさん** · 2019/08/04(日) 03:52:38.60

>>56で指摘したのに誰も反応してくれないので自分で書く
>>54は、「133」と入れると[313,331,313,331]みたいに結果がダブる

**デフォルトの名無しさん** · 2019/08/04(日) 04:17:02.39

>>62
C++のnext_permutationは、辞書順で次に来る順列が返るので、
最初の並びにnext_permutationを繰り返し適用すれば題意を満たす数列が得られる。
あと、自前で桁分割するより他言語のように文字列を使った方が楽だと思う。