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

**デフォルトの名無しさん** · 2019/05/18(土) 17:33:29.45

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

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

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

※前スレ
https://mevius.5ch.net/test/read.cgi/tech/1549160513/

**デフォルトの名無しさん** · 2019/05/25(土) 19:01:54.73

>>124 取り敢えずこの問題を『凸包正方形』
とでも呼びますか。

**デフォルトの名無しさん** · 2019/05/25(土) 20:41:54.94

三角形に分解してみる?

**デフォルトの名無しさん** · 2019/05/25(土) 21:12:11.52

>>112
連続体濃度でかつ二番目に小さな値のある集合
{0, 1} ∪ (2, ∞)

**デフォルトの名無しさん** · 2019/05/25(土) 22:13:07.00

>>11
ポイントが(136,577), (110,927)の2つだけならどうなる?

**デフォルトの名無しさん** · 2019/05/25(土) 22:15:27.93

>>128
それ対角線の正方形しかないやろ

**デフォルトの名無しさん** · 2019/05/26(日) 01:40:13.82

以下はｵﾚなりに考えた仮説
1）2点で正方形の内側に接するのは何らかの平べったい形、対角にて頂点が接するので45°
2）3点で接するのは、細長い三角形あるいはそれに準じた形、角度の計算は…?不明
　または凸包の一辺が正方形の辺に接する形
3）4点で接するのは、細長い三角形あるいはそれに準じた形、角度の計算は…?不明
　または凸包の一辺が正方形の辺に接する形
4）5点以上で接する場合は、凸包の一辺が正方形の辺に接する

「対角にて頂点が接する形の角度は45°」
「凸包の一辺が正方形の辺に接する形は凸包の辺の角度」
これらは角度が分かるので回転変化･逆変換を使って
外側の最小の斜め正方形の候補を探索することは可能だが、
角度が良く分からない形の解法が、まだ見出せていない

**デフォルトの名無しさん** · 2019/05/26(日) 01:44:08.13

凸包の一辺が正方形の辺に接するおよび二点が対角に接する場合に限った解法
なら難しくないんだがな…

**デフォルトの名無しさん** · 2019/05/26(日) 01:59:58.39

>>129
それは正方形が(0,0)-(999,999)からはみでてまうな

**130** · 2019/05/26(日) 17:27:59.46

>>11 外側の正方形 Perl5、但し>>130>>131の「凸包の一辺が正方形の辺に接する」または「細い菱形のような形が
正方形の対角2点で接する」場合について求てみた。凸包を求める処理は略し、二点間の辺を総当りで計算している。
use List::Util qw{min max pairkeys pairvalues};
@s=qw{136 577 110 927 472 199 157 808 388 598 94 31 388 157 325 409 787 897 850 598};
@X = pairkeys @s; @Y = pairvalues @s;
sub sp {$_[0]*$_[2] + $_[1]*$_[3]}
sub rt {
　@e = (cos $th, -sin $th); @f = (sin $th, cos $th);
　my @x = map{sp @e, $X[$_], $Y[$_]} 0..$#X;
　my @y = map{sp @f, $X[$_], $Y[$_]} 0..$#Y;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　$h = (max $x[1] - $x[0], $y[1] - $y[0]) / 2;
　$cx = ($x[1] + $x[0]) / 2; $cy = ($y[1] + $y[0]) / 2;
　@x = ($cx - $h, $cx + $h); @y = ($cy - $h, $cy + $h);
　($e[1], $f[0]) = (-$e[1], -$f[0]);
　@x = map{sp @e, $x[$_], $y[$_]} 0..1;
　@y = map{sp @f, $x[$_], $y[$_]} 0..1;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　(\@x, \@y, 2*$h) }
for $i (0..@X-2) { for $j ($i+1..$#X) {
　($dx, $dy) = ($X[$j] - $X[$i], $Y[$j] - $Y[$i]);
　($dx, $dy) = (-$dx, -$dy) if $dx < 0;
　$l = sqrt($dx*$dx + $dy*$dy);
　$th = $dx > abs($dy) ? -atan2($dy, $dx) : atan2($dx, $dy);
　($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
　$th += 3.14159265358979/4; ($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
} }
@t = sort{$a->{w}<=>$b->{w}} grep{0<=$_->{X}[0]and$_->{X}[1]<=999 and 0<=$_->{Y}[0]and$_->{Y}[1]<=999} @t;
do {@x = @{$t[$_]->{X}}; @y = @{$t[$_]->{Y}};
　printf"%d: (%7.3f, %7.3f)-(%7.3f, %7.3f): w=%3.3f\n",$_+1,$x[0],$y[0],$x[1],$y[1],$t[$_]->{w}} for 0..5;

**デフォルトの名無しさん** · 2019/05/26(日) 17:29:47.07

>>133 の実行例

~ $ perl 14_11.pl
1: ( 48.607, 27.043)-(863.062, 983.177): w=891.576
2: ( 45.920, 20.484)-(869.713, 849.356): w=892.353
3: ( 32.627, 29.170)-(901.066, 949.457): w=895.142
4: ( 24.000, 31.000)-(920.000, 927.000): w=896.000
5: ( 24.000, 31.000)-(920.000, 927.000): w=896.000
6: ( 14.845, 32.823)-(931.567, 907.397): w=896.130

検算してないので、もしバグっていたらｺﾞﾒﾝﾁｬｲ、（ゝω・）ﾃﾍﾍﾟﾛ

**デフォルトの名無しさん** · 2019/05/26(日) 17:38:51.62

>>133 ｽﾏｿ、「正方形の4点の座標を示せ」と書かれていたので、出力処理を少し修正
use List::Util qw{min max pairkeys pairvalues};
@s=qw{136 577 110 927 472 199 157 808 388 598 94 31 388 157 325 409 787 897 850 598};
@X = pairkeys @s; @Y = pairvalues @s;
sub sp {$_[0]*$_[2] + $_[1]*$_[3]}
sub rt {
　@e = (cos $th, -sin $th); @f = (sin $th, cos $th);
　my @x = map{sp @e, $X[$_], $Y[$_]} 0..$#X;
　my @y = map{sp @f, $X[$_], $Y[$_]} 0..$#Y;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　$h = (max $x[1] - $x[0], $y[1] - $y[0]) / 2;
　$cx = ($x[1] + $x[0]) / 2; $cy = ($y[1] + $y[0]) / 2;
　@x = ($cx - $h, $cx + $h); @y = ($cy - $h, $cy + $h);
　($e[1], $f[0]) = (-$e[1], -$f[0]);
　@x = map{sp @e, $x[$_], $y[$_]} 0..1;
　@y = map{sp @f, $x[$_], $y[$_]} 0..1;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　(\@x, \@y, 2*$h) }
for $i (0..@X-2) { for $j ($i+1..$#X) {
　($dx, $dy) = ($X[$j] - $X[$i], $Y[$j] - $Y[$i]);
　($dx, $dy) = (-$dx, -$dy) if $dx < 0;
　$l = sqrt($dx*$dx + $dy*$dy);
　$th = $dx > abs($dy) ? -atan2($dy, $dx) : atan2($dx, $dy);
　($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
　$th += 3.14159265358979/4; ($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
} }
@t = sort{$a->{w}<=>$b->{w}} grep{0<=$_->{X}[0]and$_->{X}[1]<=999 and 0<=$_->{Y}[0]and$_->{Y}[1]<=999} @t;
do {@x = @{$t[$_]->{X}}; @y = @{$t[$_]->{Y}};
　printf"%d: (%6.3f, %6.3f), (%7.3f, %6.3f), (%6.3f, %7.3f), (%7.3f, %7.3f): w=%3.3f\n",
　　$_+1,$x[0],$y[0],$x[1],$y[0],$x[0],$y[1],$x[1],$y[1],$t[$_]->{w}} for 0..5;

**デフォルトの名無しさん** · 2019/05/26(日) 17:40:00.54

>>135 実行結果

~ $ perl 14_11.pl
1: (48.607, 27.043), (863.062, 27.043), (48.607, 983.177), (863.062, 983.177): w=891.576
2: (45.920, 20.484), (869.713, 20.484), (45.920, 849.356), (869.713, 849.356): w=892.353
3: (32.627, 29.170), (901.066, 29.170), (32.627, 949.457), (901.066, 949.457): w=895.142
4: (24.000, 31.000), (920.000, 31.000), (24.000, 927.000), (920.000, 927.000): w=896.000
5: (24.000, 31.000), (920.000, 31.000), (24.000, 927.000), (920.000, 927.000): w=896.000
6: (14.845, 32.823), (931.567, 32.823), (14.845, 907.397), (931.567, 907.397): w=896.130

検算してないので、もしバグっていたらｺﾞﾒﾝﾁｬｲ、（ゝω・）ﾃﾍﾍﾟﾛ

**デフォルトの名無しさん** · 2019/05/26(日) 17:44:33.42

>>136
なんか変、バグってるｽﾏｿ、直すことが出来たら書き込みます

**デフォルトの名無しさん** · 2019/05/26(日) 18:33:59.00

>>11 外側の正方形 Perl5 凸包の辺が正方形の辺に接するまたは対角二点で接する場合、>>135の露骨なﾊﾞｸﾞ一個修正
use List::Util qw{min max pairkeys pairvalues};
@s=qw{136 577 110 927 472 199 157 808 388 598 94 31 388 157 325 409 787 897 850 598};
@X = pairkeys @s; @Y = pairvalues @s;
sub sp {$_[0]*$_[2] + $_[1]*$_[3]}
sub rt {
　@e = (cos $th, -sin $th); @f = (sin $th, cos $th);
　my @x = map{sp @e, $X[$_], $Y[$_]} 0..$#X;
　my @y = map{sp @f, $X[$_], $Y[$_]} 0..$#Y;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　$h = (max $x[1] - $x[0], $y[1] - $y[0]) / 2;
　$cx = ($x[1] + $x[0]) / 2; $cy = ($y[1] + $y[0]) / 2;
　@x = ($cx - $h, $cx + $h, $cx - $h, $cx + $h);
　@y = ($cy - $h, $cy - $h, $cy + $h, $cy + $h);
　($e[1], $f[0]) = (-$e[1], -$f[0]);
　@x = map{sp @e, $x[$_], $y[$_]} 0..3;
　@y = map{sp @f, $x[$_], $y[$_]} 0..3;
　(\@x, \@y, 2*$h) }
for $i (0..@X-2) { for $j ($i+1..$#X) {
　($dx, $dy) = ($X[$j] - $X[$i], $Y[$j] - $Y[$i]);
　($dx, $dy) = (-$dx, -$dy) if $dx < 0;
　$l = sqrt($dx*$dx + $dy*$dy);
　$th = $dx > abs($dy) ? -atan2($dy, $dx) : atan2($dx, $dy);
　($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
　$th += 3.14159265358979/4; ($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
} }
@t = sort{$$a{w}<=>$$b{w}} grep{0<=min@{$_->{X}}and max@{$_->{X}}<=999 and 0<=min@{$_->{Y}}and max@{$_->{Y}}<=999} @t;
do {@x = @{$t[$_]{X}}; @y = @{$t[$_]{Y}};
　　printf"%d: (%7.3f,%7.3f), (%7.3f,%7.3f), (%7.3f,%7.3f), (%7.3f,%7.3f): w=%7.3f, th=%7.3f°\n",
　　　$_+1,$x[0],$y[0],$x[1],$y[1],$x[2],$y[2],$x[3],$y[3],$t[$_]{w},$t[$_]{th}*180/3.14159265358979} for 0..4;

**デフォルトの名無しさん** · 2019/05/26(日) 18:37:35.18

>>138 実行例

~ $ perl 14_11.pl
1: ( 32.627, 29.170), (927.382, 55.475), ( 6.310,923.152), (901.066,949.457): w=895.142, th= -1.685°
2: (920.000,927.000), ( 24.000,927.000), (920.000, 31.000), ( 24.000, 31.000): w=896.000, th=180.000°
3: ( 24.000, 31.000), (920.000, 31.000), ( 24.000,927.000), (920.000,927.000): w=896.000, th= 0.000°
4: ( 14.845, 32.823), (910.733, 11.994), ( 35.680,928.226), (931.567,907.397): w=896.130, th= 1.332°
5: ( 18.819, 32.332), (914.819, 16.335), ( 34.819,928.046), (930.819,912.049): w=896.143, th= 1.023°

ちゃんと検算してないので、もしまだバグがいたらｺﾞﾒﾝﾁｬｲ、（ゝω・）ﾃﾍﾍﾟﾛ

検算方法考えた方がいいのかも。ちなみにwは正方形の幅、thは回転各[deg]

>>11 の内側の正方形についてはまだ考えていない。

**デフォルトの名無しさん** · 2019/05/26(日) 20:05:21.06

>>11 おもろいな、初級問題だと文法の練習としてそれなりに勉強になる。
こう言うのはそれを超えていろんなパッケージ／ライブラリを駆使することになるから一皮剥けて勉強になる。

解けるか解けないか判らないけど楽しんでる。

勿論こう言うのは、言語の問題ではなく、ロジックの問題だと解っているんだが、ヒントとなる数字を出せるのは言語の力にもよるからそれはそれなりに面白い。

図形は直感的に推論が正しいかどうか判るから面白い。
https://i.imgur.com/cCazfFe.jpg
凸包の重心は使えなさそうだな。

>>139 なんとなく変に感じるんだが。
https://i.imgur.com/3ioZWjZ.jpg

この場合の正方形の一辺は、左側の凸包の線そのものになると思うんだけど。
つまり、左下端が、( 94,31 )、上端が(110,927) にならないかな？

**デフォルトの名無しさん** · 2019/05/26(日) 20:06:23.89

>>140 ごめん、同じ画像を二つ上げてしまった。

◆QZaw55cn4c · 2019/05/26(日) 20:24:38.79

>>11
まずは「斜めは考えない」 https://ideone.com/0ho1Fr
>>48
解が一致しました

◆QZaw55cn4c · 2019/05/26(日) 20:28:38.16

お題と回答
>>5 : 6 10 32 36 44
>>9 : 15 34 35 79
>>11 : 48 (78) 138-139
>>19 :
>>50, https://mevius.5ch.net/test/read.cgi/tech/1549160513/920 : 4 85 89
https://mevius.5ch.net/test/read.cgi/tech/1549160513/988 : 59 61
>>90 : 95 96
>>99 :

**138** · 2019/05/26(日) 21:07:57.74

>>140 図をありがとう

scriptを(94, 31) - (110, 927)の辺に傾けてこの角度における最小の正方形だけを計算するようなおして
計算したら
5: ( 18.819, 32.332), (914.819, 16.335), ( 34.819,928.046), (930.819,912.049): w=896.143, th= 1.023°
になりました。

**デフォルトの名無しさん** · 2019/05/27(月) 00:47:32.69

>>144 それはおかしい。直行正方形の辺の長さが896だから、896以下にならなければならない。

**デフォルトの名無しさん** · 2019/05/27(月) 03:33:47.20

>>11 1)のみやってみた。

図 https://codepen.io/dokokade/full/WBzgrZ

※ 途中で完全にJavaScriptのお遊びになってしまった。
　　(計算は別プログラムで、そのログを図にした)

一辺 = 890.70993168302
四点
x: [ 0.8027676391, 82.9114960624, 969.828819782, 887.7200913596]
y: [916.8907759982, 29.9734522778, 112.082180701, 998.9995044215]

**デフォルトの名無しさん** · 2019/05/27(月) 12:03:51.40

>>146 多分正解だね。　おめでとう。

**デフォルトの名無しさん** · 2019/05/27(月) 12:17:08.10

>>146 あ、でも　右上の頂点は　y = 998.9995044215　となってるけど、
正確には　y=999 とぶつからなければいけないよね。　少し誤差が大きすぎるような気がするけどこんなもの？

**デフォルトの名無しさん** · 2019/05/27(月) 23:46:29.70

>>140
この図の(388,157)は（388,598）の誤記?

**デフォルトの名無しさん** · 2019/05/27(月) 23:59:39.40

>>149 間違っていないでしょ。
両方あるよ。
xys [[136 577]
[110 927]
[472 199]
[157 808]
[388 598] ***
[ 94 31]
[388 157] ***
[325 409]
[787 897]
[850 598]]

https://i.imgur.com/9emHzzD.jpg

**デフォルトの名無しさん** · 2019/05/28(火) 00:07:34.28

>>145 凸包の一辺(94,31)-(110,927)のみに着目し、この辺が垂直となる様に座標を1.023°回転して
から点郡を囲む矩形領域を求め、その長方形を正方形になるように短い辺を伸ばす処理は省いて
長方形のまま元の座標系に逆変換し4頂点座標を見たところ、
use List::Util qw{min max};
use Math::Trig;
@X = qw{94 110}; # 787 850 472 388};
@Y = qw{31 927}; # 897 598 199 598};
sub sp {$_[0]*$_[2] + $_[1]*$_[3]}
for $i (0..@X-2) { for $j ($i+1..$#X) {
　($dx, $dy) = ($X[$j] - $X[$i], $Y[$j] - $Y[$i]);
　($dx, $dy) = (-$dx, -$dy) if $dx < 0;
　$th = $dx > abs($dy) ? -atan2($dy, $dx) : atan2($dx, $dy);
　@e = (cos $th, -sin $th); @f = (sin $th, cos $th);
　my @x = map{sp @e, $X[$_], $Y[$_]} 0..$#X;
　my @y = map{sp @f, $X[$_], $Y[$_]} 0..$#Y;
　@x = (min(@x), max @x); @y = (min(@y), max @y);
　$w = max($x[1] - $x[0], $y[1] - $y[0]);
　($e[1], $f[0]) = (-$e[1], -$f[0]);
　@x = map{sp @e, $x[$_], $y[$_]} 0,1,0,1;
　@y = map{sp @f, $x[$_], $y[$_]} 0,0,1,1;
　#next if min@x<0 or 999<max@x or min@y<0 or 999<max@y;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,th,$th,X,[@x],Y,[@y],w,$w} } }
@t = sort{$$a{w}<=>$$b{w}} @t;
do {@x = @{$_->{X}}; @y = @{$_->{Y}};
　printf"%d: (%7.3f,%7.3f), (%7.3f,%7.3f), (%7.3f,%7.3f), (%7.3f,%7.3f): w=%7.3f, th=%7.3f°\n",
　　++$k,$x[0],$y[0],$x[1],$y[1],$x[2],$y[2],$x[3],$y[3],$$_{w},rad2deg $$_{th}} for @t;
~ $ perl 14_11_2.pl
1: ( 94.000, 30.990), (110.000, 30.990), ( 94.000,926.704), (110.000,926.704): w=896.143, th= 1.023°
となったので、今のところ計算は合っていると思う。おかしく感じたのは長方形を正方形になるように短い辺を伸ばした座標の
シフトによるものだと思う。しかし、この長方形⇒正方形補正が曲者で、より小さい正方形であるにもかかわらず長方形の
短辺を両側に均等に伸ばすと頂点が0～999の範囲をこえてしまうものがあるらしく、不均等に伸ばすようにすれば
より小さい正方形を見出せるかもしれない。

**デフォルトの名無しさん** · 2019/05/28(火) 00:08:24.04

>>150
そうだね、ｺﾞﾒﾝ

**デフォルトの名無しさん** · 2019/05/28(火) 00:16:35.63

>>150 外接円を描いてみたけど、利用方法を見つけられなかった。
むしろ [ 94 31] [787 897] の対角を直径とする最小包含円からかな？

**デフォルトの名無しさん** · 2019/05/28(火) 00:27:46.22

以下は試作実験programと結果
①凸包の辺の角度にのみ傾ける(それ以外の角度は略)　②長方形⇒正方形補正は略 ③頂点座標が0～999の範囲外も出力
use List::Util qw{min max}; use Math::Trig;
@X = qw{94 110 787 850 472 388}; @Y = qw{31 927 897 598 199 157};
sub sp {$_[0]*$_[2] + $_[1]*$_[3]}
for $i (0..@X-2) { for $j ($i+1..$#X) {
　($dx, $dy) = ($X[$j] - $X[$i], $Y[$j] - $Y[$i]);
　($dx, $dy) = (-$dx, -$dy) if $dx < 0;
　$th = $dx > abs($dy) ? -atan2($dy, $dx) : atan2($dx, $dy);
　@e = (cos $th, -sin $th); @f = (sin $th, cos $th);
　my @x = map{sp @e, $X[$_], $Y[$_]} 0..$#X;
　my @y = map{sp @f, $X[$_], $Y[$_]} 0..$#Y;
　@x = (min(@x), max @x); @y = (min(@y), max @y);
　$w = max($x[1] - $x[0], $y[1] - $y[0]);
　($e[1], $f[0]) = (-$e[1], -$f[0]);
　@x = map{sp @e, $x[$_], $y[$_]} 0,1,0,1;
　@y = map{sp @f, $x[$_], $y[$_]} 0,0,1,1;
　#next if min@x<0 or 999<max@x or min@y<0 or 999<max@y;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,th,$th,X,[@x],Y,[@y],w,$w} } }
@t = sort{$$a{w}<=>$$b{w}} @t;
do {@x = @{$_->{X}}; @y = @{$_->{Y}};
　printf"%d: (%7.3f,%7.3f), (%7.3f,%7.3f), (%7.3f,%7.3f), (%7.3f,%7.3f): w=%7.3f, th=%7.3f°\n",
　　++$k,$x[0],$y[0],$x[1],$y[1],$x[2],$y[2],$x[3],$y[3],$$_{w},rad2deg $$_{th}} for @t[0..4];

1: (752.170,710.324), ( 94.000,710.324), (752.170, -8.662), ( 94.000, -8.662): w=873.451, th=168.102°
2: ( 70.342, 31.983), (863.100, 31.983), ( 70.342,891.839), (863.100,891.839): w=895.830, th= 2.537°
3: ( 94.000, 30.990), (855.637, 30.990), ( 94.000,913.391), (855.637,913.391): w=896.143, th= 1.023°
4: (699.348,547.478), ( 94.000,547.478), (699.348,-34.520), ( 94.000,-34.520): w=945.899, th=160.148°
5: ( 94.000, 29.184), (671.086, 29.184), ( 94.000,1007.681), (671.086,1007.681): w=978.102, th=-23.199°
真の極小解は中途半端な角度にあるのか…

**146** · 2019/05/28(火) 00:38:23.09

>>148

146は、ヒュースリックス解だから、まだ小さくなると思う。
でも、あと1くらいだと思う
( これが厳密解を求めるやる気が、無くなる原因)

少しずるして、この問題に過剰最適化させて、
890.7003209442369にした。
図 https://codepen.io/dokokade/full/WBzgrZ

**デフォルトの名無しさん** · 2019/05/28(火) 00:44:50.83

>>154
これ、凸包の辺の角度にのみ傾けてない、凸包の全頂点の組み合わせエッジの角度に傾けている。
まいいや、大差ない

**デフォルトの名無しさん** · 2019/05/28(火) 01:02:45.97

>>125 >>11 の問題1 に名前を与えるならさしずめ、最小包含正方形かな。

**デフォルトの名無しさん** · 2019/05/28(火) 01:18:31.05

>>155 無理を言ってごめん、答えの誤差をなくすために、最終座標は整数の xy 座標に出来るかな。中心からの距離を切り上げて整数にする感じになると思うけど。

**デフォルトの名無しさん** · 2019/05/28(火) 01:33:00.26

こういう問題って、極小・最小解にいたる連続的な解空間形成してなけりゃ収束計算もできないし
かといって解析的あるいはロジカルな求解法が見出せなけりゃ、最後はヒューリスティックあるいはランダムwalk
あるいはRISMみたいな外挿的に探索するしかないのだろうか…
ないんだろうなたぶん。そんなきがす

**デフォルトの名無しさん** · 2019/05/28(火) 01:41:09.17

>>159 現実の世界でも、求める解は整数にすることが多いと思う。
画面のドット精度、工作機械の精度など整数と考えた方が良い。
現実的には整数解が求められないと、角を切り落としたりしかねない。
(許容誤差を加えた範囲を求めるのでも良いけど)

整数解にした方が、試行錯誤の時間も少なくなると思うからより現実的だと思う。答えが一律に決まるし。

50 · 2019/05/28(火) 13:42:19.32

https://mevius.5ch.net/test/read.cgi/tech/1549160513/920

前スレの920の、ランク付けの問題で、

入力データ
-6 3 9 5 3 -7
出力・ランク
2 3 5 4 3 1

2 3 6 5 3 1

下のように、同値の場合は、同じランクにして、次のランクの間隔を空ける場合、
ランク3 が2つあるから、4が無くなって、次は、5に飛ぶ場合は、難しい！

**デフォルトの名無しさん** · 2019/05/28(火) 16:43:58.97

>>161
uniqしないだけ

**デフォルトの名無しさん** · 2019/05/28(火) 17:48:16.52

>>153 このケースの場合の最小包含円は外接円と一致するんだな。

**デフォルトの名無しさん** · 2019/05/29(水) 15:51:03.59

素因数分解する関数を作れ。
ただし2より小さい数は空のリスト(又は配列)を返す事とする。

例: factorization 150
＞[2,3,5,5]

**デフォルトの名無しさん** · 2019/05/29(水) 16:00:45.49

はい、次のお題どうぞ

◆QZaw55cn4c · 2019/05/29(水) 18:28:49.13

>>164
== https://mevius.5ch.net/test/read.cgi/tech/1549160513/988 == >>56 >>59 >>61

**デフォルトの名無しさん** · 2019/05/29(水) 21:59:41.60

>>164 Perl5、>>59 で書いたroutineを流用しています。

sub prime {
　$h = int $n/2;
　for ($i=2; $i<=$h; $i++) {
　　$s[$i] = 1 unless exists $s[$i];
　　do {$s[$i*$_] = 0 for 2..int $h/$i} if $s[$i];
　}
　@p = grep{$s[$_]} 2..$h;
}
sub factorization {
　my $i = shift;
　my $h = int $i/2;
　for $j (grep{$_ <= $h} @p) {
　　return ($j, factorization($i/$j)) if 0 == $i % $j;
　}
　1 < $i ? $i : ();
}
$"=',';
for $n ((0, 1, 2, 150)) {
　prime;
　@f = factorization $n;
　print"$n => [@f]\n";
}

実行結果
~ $ perl 14_164.pl
0 => []
1 => []
2 => [2]
150 => [2,3,5,5]

**デフォルトの名無しさん** · 2019/05/30(木) 18:43:19.57

>>166
すでに既出だったとは。。。orz

**デフォルトの名無しさん** · 2019/05/30(木) 18:45:09.99

>>164
一応Haskell載せときます。

main = (print.factorization) 150

factorization n | n < 2 = []
factorization n = f n primes
where
f n (x:_) |n == x = [x]
f n (x:xs)|n `mod` x == 0 = x:f (n `div` x) (x:xs)
f n (_:xs) = f n xs

primes = sieve [2..]
where sieve (p:xs) = p:sieve [x | x <- xs, x `mod` p /= 0]

**デフォルトの名無しさん** · 2019/05/30(木) 18:49:02.33

既に既出
馬から落馬
歌を歌う
舞を舞う
ダンスをダンスる

**デフォルトの名無しさん** · 2019/05/30(木) 18:50:08.40

ヤフーでググる

**デフォルトの名無しさん** · 2019/05/30(木) 20:22:38.83

お題: sin, cos を用いてお題を作成せよ

**デフォルトの名無しさん** · 2019/05/30(木) 20:26:45.68

eをネイピア数とした時
e^(iθ) ≠ cosθ + i sinθ
となる事を証明せよ

**デフォルトの名無しさん** · 2019/05/30(木) 20:35:25.37

ん~、じゃあ
sin, cos を実装せよ

**デフォルトの名無しさん** · 2019/05/30(木) 22:02:46.02

>>173
オイラーの公式なめてんの？

**デフォルトの名無しさん** · 2019/05/30(木) 22:10:08.81

>>175
exp(iθ)=cosθ+isinθだけど(2.71828...)^(iθ)は多値関数だよ

**デフォルトの名無しさん** · 2019/05/30(木) 22:23:36.25

>>176
多値じゃなくて多価

**デフォルトの名無しさん** · 2019/05/30(木) 23:36:43.35

^はxorだからな。そりゃ違うさ。

**蟻人間** ◆T6xkBnTXz7B0 · 2019/05/30(木) 23:40:43.53

お題:テーブル方式でcos/sin関数をテキトーに自作ｾﾖ。

**デフォルトの名無しさん** · 2019/05/30(木) 23:54:33.59

>>179
cos := (1 0)(round abs fdivmod 2 * $a Math.PI) * (sgn $a);
sin := (0 1)(round abs fdivmod 2 * $a Math.PI) * (sgn $a);

**デフォルトの名無しさん** · 2019/05/31(金) 00:55:18.43

ああこりゃ多価関数の意味を知らないバカだな

**デフォルトの名無しさん** · 2019/05/31(金) 01:02:49.06

複素数の指数関数や対数関数は多価関数だろ
馬鹿はお前だ

**デフォルトの名無しさん** · 2019/05/31(金) 01:38:23.70

指数関数は多価じゃないよ、何言ってんの

**デフォルトの名無しさん** · 2019/05/31(金) 05:30:51.21

>>183
寝言はねえから言えよクズ
z^w := exp(w * log(z))
log(z) が多価関数なんだから一般にz^wも多価関数だっつーの
死ねよ雑魚が

https://en.wikipedia.org/wiki/Exponential_function
> We can then define a more general exponentiation:
>
> {\displaystyle z^{w}=e^{w\log z}} z^{w}=e^{w\log z}
> for all complex numbers z and w. This is also a MULTIVALUED function, even when z is real.

**デフォルトの名無しさん** · 2019/05/31(金) 05:49:38.41

>>184
出典がwikiとかありえねーよwww
wikiにそう書いてあるからってそれが正しいとは限んねえだろバーカ

**デフォルトの名無しさん** · 2019/05/31(金) 06:17:16.52

>>184
第一の意味での指数関数、つまり f′(z) = f(z), f(0)=1 を満たす f(z) = exp(z) は当然多価関数じゃない。

第二の意味での「指数関数」、つまり複素数の複素数乗 f(z, w) = z^w は、引用してくれたとおり exp の「逆関数」 log を使って f(z, w) = exp(w log z) と定義するけど、
log は主値を取るものとして(つまり定義域を制限した exp の真の意味での逆関数として)定義すれば log w も f(z, w) もちゃんとした関数になる。そうでなければどちらも多価関数になる。

多価関数って要は関数じゃない(写像ではない)から、少なくとも一般的な計算には使わないよね。多価の asin x や多価の √x なんて使わないでしょ?

**デフォルトの名無しさん** · 2019/05/31(金) 06:53:54.48

>>186
主値を取る場合はLogなりp.v. ｆなりきちんと明示するのが少なくとも解析屋の間ではルールだよ
他の分野の人は知らないけど

**デフォルトの名無しさん** · 2019/05/31(金) 07:16:05.79

>>170
> 歌を歌う
歌うには「歌を」と言う意味は含まれてないから歌を歌うと言うのは別におかしくないよ
> 舞を舞う
も同様

**デフォルトの名無しさん** · 2019/05/31(金) 07:32:11.07

>>164 Python sympy

from sympy import *
print(factorint(150))
#{2: 1, 3: 1, 5: 2} 2*3*5**2 を示す

**デフォルトの名無しさん** · 2019/05/31(金) 12:16:09.80

>>188
和語として語源同一なんだけど。
意外なものでは「くさい」と「くそ」「明かり」と「開ける」も同一語源。

**デフォルトの名無しさん** · 2019/05/31(金) 14:15:19.33

数学の問題なんて、センター入試問題でも解いてこいよ。手を抜きすぎだぞ。もっと面白くひねれよ。

**デフォルトの名無しさん** · 2019/05/31(金) 20:50:13.55

>>164
Haskellを元にPython。
素数じゃ無いと判定した時点でループ抜けるとかしたら、そこそこ速くなった。
https://ideone.com/3L1N23

**デフォルトの名無しさん** · 2019/05/31(金) 23:54:43.29

センターなんて数学じゃなくて算数でしょ

**デフォルトの名無しさん** · 2019/06/01(土) 05:45:08.23

面白いお題がないかと文句を言う前に
進んで面白いお題を書きましょう

**デフォルトの名無しさん** · 2019/06/02(日) 10:12:21.99

>>192 python sympy

from sympy import *
import time
time_sta = time.perf_counter()
ans=factorint(13999)
time_end = time.perf_counter()
print(ans,'{:.7f}ms'.format((time_end-time_sta)*1000))

#{13999: 1} 0.0283330ms

同じpython でも餅は餅屋なんだろうな。
因みに、13999**2 を求めると
#{13999: 2} 0.4635000ms

iPhone Xs Max Pythonista3.2 Python3.6.5 sympy 0.4.7.1

**デフォルトの名無しさん** · 2019/06/02(日) 15:03:12.02

>>192 は >>164向けの回答としては問題ない。

しかし、一般的な素因数分解としては問題が。
大きな素数が対象のとき、実行時間がひどい結果になっている。
たとえば有名な素数1000000007(10億7)をやると....
(前スレ988の制約範囲内くらい、普通にできる形が望ましい)

pythonで手を抜いた一般的な素因数分解でも
10^12くらいは1秒以内に出る。(10^12+39が近場の素数)

**195** · 2019/06/02(日) 18:27:22.13

>>196 python sympy
{1000000007: 1} 0.2255000ms

**195** · 2019/06/02(日) 18:41:56.81

>>196 同一環境での比較。

n= 13999 ans= {13999: 1} time=0.0135830ms
>>192 を実行
n= 13999 ans= [13999] time=152.4304170ms

**デフォルトの名無しさん** · 2019/06/03(月) 00:41:43.81

>>198
192の解が一般解としてはひどいすぎるってことでしょ。
10億7どころか、百万台の素数もキツイ。

**デフォルトの名無しさん** · 2019/06/03(月) 03:39:17.26

お題：↓の画像のようにコンソール画面に雨を降らせなさい
https://i.imgur.com/wR1mNu5.gif

**デフォルトの名無しさん** · 2019/06/03(月) 12:16:50.21

>>164 pythonわかってない俺がpythonで
https://ideone.com/7j8Gz8

**デフォルトの名無しさん** · 2019/06/03(月) 21:33:09.94

>>164
Kotlin
https://paiza.io/projects/65lAktSm6rjmcVdxSlaLSQ

ただループ回すだけじゃ芸がないと思って素数を返すイテレータのクラス作ってやってみた。
(素数をバッファリングもすればもっと無駄がなかったなとは思ったがそれはやってない)。

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

>>185
Wikiが正しいとは限らないからと言って、wikiが間違っている前提で反論するバカの見本

**195** · 2019/06/04(火) 07:17:53.03

>>201 jupyter で測ってみた。結構早い。

[1000000007]
CPU times: user 2.28 ms, sys: 0 ns, total: 2.28 ms
Wall time: 2.25 ms

[1000000000039]
CPU times: user 99.8 ms, sys: 0 ns, total: 99.8 ms
Wall time: 107 ms

[2, 3, 3, 5, 7, 11, 13, 17, 29]
CPU times: user 76 µs, sys: 0 ns, total: 76 µs
Wall time: 78.7 µs

[2, 3, 3, 5, 7, 11, 13, 17, 29, 1000000007]
CPU times: user 3.53 ms, sys: 0 ns, total: 3.53 ms
Wall time: 3.54 ms

**デフォルトの名無しさん** · 2019/06/04(火) 07:56:52.47

素数は、平方根までの素数で割って、割り切れなければ素数だろ

[2,3,5,7,11,13...] みたいに、素数表に追加していく途中で、
例えば、103 なら、11 までの素数で割って、割り切れなければ素数

13以降の素数で割る必要はない

もし13で割り切れるなら、13 * n = 103
となり、n は、√103 よりも、小さくなるから、既に割り切れているはず！

**デフォルトの名無しさん** · 2019/06/04(火) 08:11:49.19

>>205
例のRubyバカはこのスレにも出没するのか

**デフォルトの名無しさん** · 2019/06/04(火) 09:07:39.39

誰もRubyの話なんてしてないやろ

**デフォルトの名無しさん** · 2019/06/04(火) 09:27:19.41

日頃の行いがなぁ…

**デフォルトの名無しさん** · 2019/06/04(火) 10:23:22.04

>>185
間違いとも限らない。

書かれていることを鵜呑みにするのは間違いだが見もしないで頭ごなしに間違いと決めつけるのも間違い。

**202** · 2019/06/04(火) 10:27:05.50

>>205
なるほど。暇があったらそれも考慮しよう。

**デフォルトの名無しさん** · 2019/06/04(火) 11:04:03.94

【速報】金券五百円分とすかいらーく優侍券をすぐもらえる　　　　
https://pbs.twimg.com/media/D8I_lOtVUAE8t0O.jpg　　
　　
①　スマホでたいむばんくを入手　　　
②　会員登録を済ませる　　　
③　マイページへ移動する　　　　　
④　招待コード→招待コードを入力する [Rirz Tu]（スペース抜き）　　　　
　　　　　
今なら更に4日18時までの登録で2倍の600円の紹介金を入手　
クオカードとすかいらーく優待券を両方ゲットできます。　　
　　　　
かんたんに入手できますのでご利用下さい　　　　

**デフォルトの名無しさん** · 2019/06/04(火) 13:01:01.36

>>211
あとで一万円の請求が来るらしい

**デフォルトの名無しさん** · 2019/06/04(火) 13:24:26.77

>>211
バラまきキャンペーン乙。

**デフォルトの名無しさん** · 2019/06/05(水) 02:49:29.97

>>200 Ruby
# エスケープシーケンスが有効な環境
print "\e[1;1;H\e2" # "\ec"
while true
print 79.times.inject(''){|s| s += (rand(20) >= 19)? '|' : ' ' }, "\n\e[1T\eM"
sleep 0.1
end

**デフォルトの名無しさん** · 2019/06/05(水) 19:02:11.80

お題：2次元関数を図示したとき網目状になる関数を示せ。

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

網目状になったら普通それは関数とは言わないんですが

**デフォルトの名無しさん** · 2019/06/05(水) 20:21:05.87

>>200
https://light.dotup.org/uploda/light.dotup.org593450.gif

エスケープシーケンスのコードが行方不明だったので書き直した。
C++で書いたけど、ベターCですなぁ。

**デフォルトの名無しさん** · 2019/06/05(水) 20:26:27.13

>>215
それは数学のお題では？関数の方を求めるんでしょ？図を画面に出すとかではなく。

**214** · 2019/06/06(木) 05:58:02.66

>>200 Ruby
# 水はねを追加
require 'io/console'
Crow, Ccol = STDOUT.winsize
print "\e[0;0H"
lines = []
while true
line = ' ' * Ccol
rand(Ccol).div(8).times{ line[rand(Ccol)] = '|' }
lines << line
print "\e[0;0H#{line}\n\e[0;0H"
if lines.size >= Crow
line = lines.shift.tr('|','w')
print "\e[#{Crow};0H#{line}\e[0;0H"
end
sleep 0.1
print "\e[0;0H\eM"
end

**デフォルトの名無しさん** · 2019/06/06(木) 18:09:53.98

お題

1/x + 1/2y + 1/3z = 4/3
を満たす、整数( x, y, z )の組み合わせを求めろ

ただし、x, y, z の範囲は、1 <= x, y, z <= 4 とする

答え
[ 1, 2, 4 ], [ 1, 3, 2 ], [ 2, 1, 1 ]

**デフォルトの名無しさん** · 2019/06/06(木) 20:34:48.88

また数学か

**デフォルトの名無しさん** · 2019/06/06(木) 20:50:52.65

これは数学と言うより、コンピュータの問題じゃないかな。
IEEE754の理解が必要になると思う。

**220** · 2019/06/06(木) 22:57:28.49

有理数・Rational クラスを使えば？

式を6倍しても良いけど

**デフォルトの名無しさん** · 2019/06/06(木) 23:11:58.29

というか知的障害者でも64回回せば終わる問題だよな