X

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

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
垢版 |
2019/05/18(土) 17:33:29.45ID:BWmpW4IF
プログラミングのお題スレです。

【出題と回答例】
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/
0063デフォルトの名無しさん
垢版 |
2019/05/21(火) 23:09:46.41ID:Arl7g85c
あなたが解けない C/C++/Java/C#/JavaScript の問題を有償で片付けるスレッドです
0064デフォルトの名無しさん
垢版 |
2019/05/21(火) 23:10:51.22ID:Arl7g85c
有償で片付けるスレッドに貼り付けるのはよろしくないね
有償で片付けてほしくて出題してるわけじゃないでしょ
問題の窃盗だよ
0065デフォルトの名無しさん
垢版 |
2019/05/21(火) 23:21:22.29ID:GF2ZpO+x
>>59
Perlは配列に対するexistsやdefinedは呼び出せるが振る舞いは不明確で「強く」非推奨となっているので
この場合では問題なくとも@pはリストではなく代わりにハッシュ%pを使って実装するべきだった
0067デフォルトの名無しさん
垢版 |
2019/05/21(火) 23:56:06.27ID:Jac4P34c
>>64
バカチョンには何を言っても無駄だと思うよ
聞く耳持たない分からず屋の馬鹿だからバカチョンなんだから
0068デフォルトの名無しさん
垢版 |
2019/05/22(水) 00:03:24.91ID:qz4w5gXY
>>64
>>27に理由が書かれていたが、一ヶ所に纏めておくと便利だなんてのは個人の都合であって、他の人にはわざわざ間接参照を強いることになるのだから、ほんとに身勝手な奴だと思う。

>>27
纏めておくのは他所で勝手にやれ、このスレにはコードだけを貼れよ。お前の手間なぞ知ったことではない。
0071デフォルトの名無しさん
垢版 |
2019/05/22(水) 01:20:05.57ID:34FbFmyD
>>70
それは絶対にやらないんじゃね
奴は自分のことしか考えてないから
だから自己愛
永遠に人から煙たがられる存在
0072デフォルトの名無しさん
垢版 |
2019/05/22(水) 01:29:50.95ID:BQdyZ7fR
>>11 は、多角形の中のドットの内外判定問題と言うのが確立されてるみたいね。
色んな方法があるみたいだが、簡単なのは、
Crossing Number Algorithm
らしい、ググってみると結構コンパクトなコード。
他も見てみたが、問題は境界線上にある点は多角形外と判定する事。

だから、そのままのロジックに手を入れないとした場合、使う側としてどう解決したら良いんだろう。
直行正方形を1ドットずつ大きくしてから回転させる？

それとも、多角形の中の多角形問題の方が適してるのかな？

この問題は結構勉強になる。 問題のイメージを掴むために、図形表示までやり始めたよ。 表示するとより楽しくなる。
0073デフォルトの名無しさん
垢版 |
2019/05/22(水) 01:32:14.02ID:BQdyZ7fR
>>71 そこまで悪い人間では無さそうだけどな、おだてれば猿も木に登るタイプだとみた。
高い木に登ってもらおう。
0074デフォルトの名無しさん
垢版 |
2019/05/22(水) 01:33:07.52ID:57KmKoFr
ｸﾞｸﾞﾗないで考えようとしていたけど、
ヒントを目にしてしまった気分
いやべつにいいけどさ
0075デフォルトの名無しさん
垢版 |
2019/05/22(水) 01:34:42.74ID:7yGywXQG
Q. クソ問題とは何ですか？
A. 問題の解釈を巡って議論や煽り合いが10レス以上続く、バカが投稿した不備のある問題のことです。
0076デフォルトの名無しさん
垢版 |
2019/05/22(水) 04:38:05.31ID:qmHT8WH/
>>47 Ruby
("HELLO".."WORLD").each{|v| puts v}
0079デフォルトの名無しさん
垢版 |
2019/05/22(水) 10:43:49.16ID:qmHT8WH/
>>9 Ruby

def sumnum(n)
(0..4).map{|i| ("1"*n +"0"*i).to_i}
end
0080デフォルトの名無しさん
垢版 |
2019/05/22(水) 12:02:59.73ID:75T3S5z+
>>78 　
Windows じゃないと動かないようだけど見やすいようにideonに張ってみた。
https://ideone.com/gJVREH

凸包と言うんだね。

2次元の凸包を求めるアルゴリズムと応用について
https://matsu7874.hatenablog.com/entry/2018/12/17/025713
凸包(convex hull)とは，与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと.

--------
凸包が求められても難しいね。　凸包内の点を削除して計算時間を削減できる効果はあるかもしれないけど。
0081デフォルトの名無しさん
垢版 |
2019/05/22(水) 12:11:47.61ID:/472uU17
凸包が求められれば、頂点の並びも整列するので
形状を分割して余弦定理とかから導けないかなって思ったんだよね
0082デフォルトの名無しさん
垢版 |
2019/05/22(水) 12:13:57.61ID:pwChZnOT
>>47
画面の幅が足りなくて表示できません。
0083デフォルトの名無しさん
垢版 |
2019/05/22(水) 12:34:28.61ID:/472uU17
ちなみに、最小を求めるだけならある角度から見た凸包の一次元への投影と、直交する角度からの一次元への投影を１８０度回しながら調べれば出せると思うけど、分割の粒度の問題で、本当に最小が取れる保証はないね
0084デフォルトの名無しさん
垢版 |
2019/05/22(水) 13:45:45.60ID:pwChZnOT
>>76
試しに Perl でも 文字列 .. 文字列 をやってみたらできたよ。
こんなことできたとは。知らないまま20年以上使ってたよ。w
008550
垢版 |
2019/05/22(水) 19:14:59.08ID:1CosvZF6
>前スレの920
頭を使った。Ruby で、

str = "-6 3 9 5 3 -7"

original_ary = str.split.map!( &:to_i ) # 各要素は整数型
hash = original_ary.each_with_object( { } ) { | num, h | h[ num ] = true }

sorted_ary = hash.sort # キーでソートする
#=> [[-7, true], [-6, true], [3, true], [5, true], [9, true]]

# Enumerator#with_index(offset = 0)
sorted_hash = sorted_ary.each.with_index( 1 ) { | elem, idx | elem[ 1 ] = idx }.to_h

# p sorted_ary
#=> [[-7, 1], [-6, 2], [3, 3], [5, 4], [9, 5]]

# p sorted_hash
#=> {-7=>1, -6=>2, 3=>3, 5=>4, 9=>5}

results = original_ary.map{ | num | sorted_hash[ num ] }
puts results.join( " " ) #=> 2 3 5 4 3 1
0086 ◆QZaw55cn4c
垢版 |
2019/05/22(水) 19:16:47.93ID:Kujyr1dD
>>70-71
アンカーが多すぎると投稿できないのです、ただそれだけです
0087 ◆QZaw55cn4c
垢版 |
2019/05/22(水) 19:17:22.29ID:Kujyr1dD
>>73
＞おだてれば猿も木に登るタイプだとみた。
痛いところを突きますね…
008850
垢版 |
2019/05/22(水) 19:26:33.00ID:1CosvZF6
>2 3 5 4 3 1

これが、
2 3 6 5 3 1

みたいに、4 が無くなる・飛ばされるランキングだと、もっとややこしい！w
0089デフォルトの名無しさん
垢版 |
2019/05/23(木) 09:23:03.57ID:mvOL8yN3
前スレの920 Ruby



def f(a)
b={}
a .dup.sort.each{|v|b[v]=b.size+1 if not b.key v}
a.map{|v|b[v]}
end

p f([-6,3,9,5,3,-7])
[2, 3, 5, 4, 3, 1]
0090デフォルトの名無しさん
垢版 |
2019/05/23(木) 12:32:00.03ID:vYeVJ6FZ
>>34
>>79

一休さんみたいなトンチの効いた回答で、それはそれで楽しめました。

改めて問題を書き直します。

各桁を足し合わせたら引数で与えられた数になる数の集合全体から小さい順に(可能なら=0対策)5個返す関数を作れ。

例:
sumnum 12
> [39,48,57,66,75] <- 3 + 9 = 12, 4 + 8 = 12, 5 + 7 = 12, 6 + 6 = 12, 7 + 5 = 12
0091デフォルトの名無しさん
垢版 |
2019/05/23(木) 12:33:09.81ID:vYeVJ6FZ
>>34は>>15の間違い
0092デフォルトの名無しさん
垢版 |
2019/05/23(木) 13:50:07.86ID:qjdiTxTD
苗字で漢字の｢口｣を｢くち｣ではなく｢ぐち｣と読むのは
井口、矢口、田口の3つだけ
これマメな
0096デフォルトの名無しさん
垢版 |
2019/05/23(木) 18:37:52.11ID:TjazBdz3
>>90
Haskell

import Data.Char要らんかった。
take 5も問題と違うけど外に追い出した方が応用効きそう。

main = (print.take 5.sumnum) 12

sumnum 0 = [0]
sumnum n |n < 0 = error "Please n >= 0 number"
sumnum n = [x | x <- [1..], n == sum [read [a]| a <- show x]]


>>95
OCamlで無限リスト処理どうすんだろと疑問だったので、後で精読させて頂きますm(_ _)m
0098デフォルトの名無しさん
垢版 |
2019/05/23(木) 19:39:17.51ID:4YO7mLFH
>>97 もう相手にすんな。お題にするなら、

その9つの名前の読み仮名のあいうえお順に並べよ。

谷口・関口・合口・相口・藍口・青口・赤口・秋口・明口

読み仮名を持ってくるのが難しそうだけどな。
0099デフォルトの名無しさん
垢版 |
2019/05/23(木) 21:02:26.03ID:W0nkxFNY
aを要素の型がIntである長さNの配列、k、cを型がIntである変数とする。
{P}a[a[k]]=c;{a[a[k]]!=c}
Hoare tripleが成立するためのなるべく弱いPを示せ
0100 ◆QZaw55cn4c
垢版 |
2019/05/23(木) 21:06:01.11ID:QGT5qlDg
>>99
教えてください
P は何ですか？
{ } とは何を表しているのですか？

＞{P}a[a[k]]=c;{a[a[k]]!=c}
0102デフォルトの名無しさん
垢版 |
2019/05/23(木) 21:38:26.52ID:iqEot/XY
sumnum、引数に10000とか与えたら答え返ってこなさそう
引数に1億とかは文字列長が千万とかになるから無理でも仕方ないけど、1万位は対応したいね
0104デフォルトの名無しさん
垢版 |
2019/05/23(木) 23:45:44.19ID:iqEot/XY
>>103 知らない言語ばかりでよく読めてないんだが、今までの提出って1から順に試してね？
それだと当然結果が返ってこないが
違ったらすまん
0106デフォルトの名無しさん
垢版 |
2019/05/24(金) 00:38:02.83ID:3viueN7b
>>92は「必ずレスがもらえるレス」として有名な文らしいな
案の定わんさかレスの付いてること
0109デフォルトの名無しさん
垢版 |
2019/05/24(金) 02:55:43.78ID:/EuQv4hQ
>>108 この凸包図を眺めてると、正解の正方形は 左辺の一番長い線を1辺とした正方形になりそうだが、それをどうやって求めるのか。

How to find the minimum-area-rectangle (MAR) fitted on the given points?
https://gis.stackexchange.com/questions/22895/finding-minimum-area-rectangle-for-given-points

最初に書いた人は、凸包を求めて重心を中心として1度ずつ回転させるやり方を考えたらしいが、下の方で良い解法のコメントが付いてた。

https://i.stack.imgur.com/ExZl3.png

少しずつ回転させるのではなくて、長方形の1辺は必ず凸包の辺のどれかと重なってるはずだから、凸包の辺の角度だけをとって試せば良いとのこと。
これなら重心を求める必要もないし、時間はかからない。

長方形が求まったら、座標系の中に入る正方形にすれば良いがはみ出してたら、参考解かな。

このアルゴリズムは、
The algorithm you are looking for is known in polygon generalisation as "smallest surrounding rectangle".
凸包最小長方形の解法とでも言えば良いのかな。
0111デフォルトの名無しさん
垢版 |
2019/05/24(金) 09:32:40.58ID:0g5oPW7D
今回のアルゴリズムは、最小の正方形を求める方法だけじゃなくて、グラフの境界との交差判定もあるから
最小の求め方だけではなく、2番め以降についても正しく判定できないといけない上に、回答が一つに定まらない可能性もあるんだよね
0112デフォルトの名無しさん
垢版 |
2019/05/24(金) 09:46:10.43ID:SalRbGaI
与えられた点を全て含む凸包全体からなる集合の濃度は明らかに連続体濃度なんだから2番目なんて存在しないぞ
0115デフォルトの名無しさん
垢版 |
2019/05/24(金) 11:52:18.57ID:MR3FxfYE
>>111 1辺から正方形を作る場合は、その正方形が全ての凸包の頂点を全て含むような大きさでなければならない。
この場合6辺あるから、そのような６つの正方形を作ってその中の最小のものを求めることになる。

面倒なのはそれが座標系に入らないといけないから場合によっては辺に平行移動しないといけないかも知れない。
すると、>>112 の言うように正方形の位置は変わるかもしれないけど、辺の長さが合ってれば正解だろうね。
（この場合は座標系に入るだろうからとりあえずは平行移動は考えないでも良いかも）
0116デフォルトの名無しさん
垢版 |
2019/05/24(金) 12:12:24.29ID:MR3FxfYE
>>110 どんな凸包体でも求まるよ。　1辺の長さが凸包体の辺の長さと一致させるわけじゃないよ。

全ての頂点を含む直方体を作る。　この求め方も工夫が必要そう。
1辺を伸ばした直線上に全ての頂点から垂線を引いて、一番外の距離を直方体の1辺とするんだろうな。
同じように他辺も求める。
0117デフォルトの名無しさん
垢版 |
2019/05/24(金) 12:51:12.25ID:Nda2hmui
>>116
雑な書き殴りですまん
https://i.imgur.com/v8rWTSf.png

さらにややこしいのは、凸包の頂点が正方形の辺上に位置して、
頂点に存在しないことのほうが多いのも難くする要因の一つ
0119デフォルトの名無しさん
垢版 |
2019/05/24(金) 18:00:01.45ID:ZpEEE6+U
>>11 色々見たけど、画像認識の境界を探す為にある程度人気のある話題みたいだが、完全を求めるのではなく、だいたいで良いからスピードの速いのが良いとしてるみたいだね。 境界自体があやふやなものだし。

厳密にやるとしても、長方形と正方形ではかなり条件が違う。

全ての点が正方形に入るのなら、一つの候補は凸包の対角上の点が一番離れているところを正方形の対角とした正方形が一つの候補ではないだろうか。
直交正方形が最大だからそこまでを調べれば良いけど、それだけをしらみつぶしに調べてどれだけ時間がかかるかだな。
それをはみ出る点がある場合にどうゴニョゴニョするかだけど、条件が絞れればスピードは速くなる。

一般的にはポイント数は膨大な数だから、条件を絞り込む方法が重要になりそう。


しかし、こんな例題はどこにでもありそうで殆どサンプルがないのは時間がかかりすぎて簡単に試せないのかな、今回はポイント数が少ないからそれほどではないとは思うけど。
0120デフォルトの名無しさん
垢版 |
2019/05/24(金) 18:05:08.54ID:ZpEEE6+U
>>119 文章が変な順になっててごめん。

全ての点が正方形に入るのなら、一つの候補は凸包の対角上の点が一番離れているところを正方形の対角とした正方形が一つの候補ではないだろうか。

それをはみ出る点がある場合にどうゴニョゴニョするかだけど、条件が絞れればスピードは速くなる。

直交正方形が最大だからそこまでを調べれば良いけど、それだけをしらみつぶしに調べてどれだけ時間がかかるかだな。
0121デフォルトの名無しさん
垢版 |
2019/05/24(金) 18:27:30.58ID:ukAKIdqH
計算両を優先するなら、座標軸を基準にとって大雑把に取るべきじゃないのかな
これなら、ゲームのコリジョン検出で使われる方法そのままだし
0122デフォルトの名無しさん
垢版 |
2019/05/24(金) 18:52:18.42ID:U6fsa1pB
点の数は関係なくね？
任意の3点を選んでその内部にある点は無いものとして考えても同じなんだから
0123デフォルトの名無しさん
垢版 |
2019/05/24(金) 19:02:15.89ID:U6fsa1pB
いや、関係あるか
頂点のめちゃくちゃ多い凸多角形になったら計算量明らかに増えるもんな
0124デフォルトの名無しさん
垢版 |
2019/05/25(土) 18:51:08.08ID:CqCnLPQm
>>11 なんかかなりの難問に思えてきたな。 解法への足がかりが見えない。 凸包までは比較的簡単にたどり着いたけどそれからが闇の中。
凸包の重心が何か使えるだろうか？

最小包含円 という言葉もあるようだが、少なくとも 正方形の辺はこの円の直径以下。
0130デフォルトの名無しさん
垢版 |
2019/05/26(日) 01:40:13.82ID:y3Cc4Dz0
以下はｵﾚなりに考えた仮説
1）2点で正方形の内側に接するのは何らかの平べったい形、対角にて頂点が接するので45°
2）3点で接するのは、細長い三角形あるいはそれに準じた形、角度の計算は…?不明
　または凸包の一辺が正方形の辺に接する形
3）4点で接するのは、細長い三角形あるいはそれに準じた形、角度の計算は…?不明
　または凸包の一辺が正方形の辺に接する形
4）5点以上で接する場合は、凸包の一辺が正方形の辺に接する

「対角にて頂点が接する形の角度は45°」
「凸包の一辺が正方形の辺に接する形は凸包の辺の角度」
これらは角度が分かるので回転変化･逆変換を使って
外側の最小の斜め正方形の候補を探索することは可能だが、
角度が良く分からない形の解法が、まだ見出せていない
0131デフォルトの名無しさん
垢版 |
2019/05/26(日) 01:44:08.13ID:y3Cc4Dz0
凸包の一辺が正方形の辺に接するおよび二点が対角に接する場合に限った解法
なら難しくないんだがな…
0133130
垢版 |
2019/05/26(日) 17:27:59.46ID:XOxN6P/y
>>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;
0134デフォルトの名無しさん
垢版 |
2019/05/26(日) 17:29:47.07ID:XOxN6P/y
>>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


検算してないので、もしバグっていたらｺﾞﾒﾝﾁｬｲ、（ゝω・） ﾃﾍﾍﾟﾛ
0135デフォルトの名無しさん
垢版 |
2019/05/26(日) 17:38:51.62ID:XOxN6P/y
>>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;
0136デフォルトの名無しさん
垢版 |
2019/05/26(日) 17:40:00.54ID:XOxN6P/y
>>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

検算してないので、もしバグっていたらｺﾞﾒﾝﾁｬｲ、（ゝω・） ﾃﾍﾍﾟﾛ
0138デフォルトの名無しさん
垢版 |
2019/05/26(日) 18:33:59.00ID:XOxN6P/y
>>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;
0139デフォルトの名無しさん
垢版 |
2019/05/26(日) 18:37:35.18ID:XOxN6P/y
>>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 の内側の正方形についてはまだ考えていない。
0140デフォルトの名無しさん
垢版 |
2019/05/26(日) 20:05:21.06ID:MaF2nVvH
>>11 おもろいな、初級問題だと文法の練習としてそれなりに勉強になる。
こう言うのはそれを超えていろんなパッケージ／ライブラリを駆使することになるから一皮剥けて勉強になる。

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

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

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

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

この場合の正方形の一辺は、左側の凸包の線そのものになると思うんだけど。
つまり、左下端が、( 94,31 )、上端が(110,927) にならないかな？
0144138
垢版 |
2019/05/26(日) 21:07:57.74ID:GCxYDy5d
>>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°
になりました。
0146デフォルトの名無しさん
垢版 |
2019/05/27(月) 03:33:47.20ID:ZlNUfz2v
>>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]
0148デフォルトの名無しさん
垢版 |
2019/05/27(月) 12:17:08.10ID:g1o9JmK9
>>146 あ、でも　右上の頂点は　y = 998.9995044215　となってるけど、
正確には　y=999 とぶつからなければいけないよね。　少し誤差が大きすぎるような気がするけどこんなもの？
0151デフォルトの名無しさん
垢版 |
2019/05/28(火) 00:07:34.28ID:A9u6a3RO
>>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の範囲をこえてしまうものがあるらしく、不均等に伸ばすようにすれば
より小さい正方形を見出せるかもしれない。
0153デフォルトの名無しさん
垢版 |
2019/05/28(火) 00:16:35.63ID:eILR4MCH
>>150 外接円を描いてみたけど、利用方法を見つけられなかった。
むしろ [ 94 31] [787 897] の対角を直径とする最小包含円 からかな？
0154デフォルトの名無しさん
垢版 |
2019/05/28(火) 00:27:46.22ID:A9u6a3RO
以下は試作実験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°
真の極小解は中途半端な角度にあるのか…
0155146
垢版 |
2019/05/28(火) 00:38:23.09ID:dFqOFikP
>>148

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

少しずるして、この問題に過剰最適化させて、
890.7003209442369にした。
図 https://codepen.io/dokokade/full/WBzgrZ
0156デフォルトの名無しさん
垢版 |
2019/05/28(火) 00:44:50.83ID:A9u6a3RO
>>154
これ、凸包の辺の角度にのみ傾けてない、凸包の全頂点の組み合わせエッジの角度に傾けている。
まいいや、大差ない
0158デフォルトの名無しさん
垢版 |
2019/05/28(火) 01:18:31.05ID:eILR4MCH
>>155 無理を言ってごめん、答えの誤差をなくすために、最終座標は整数の xy 座標に出来るかな。 中心からの距離を切り上げて整数にする感じになると思うけど。
0159デフォルトの名無しさん
垢版 |
2019/05/28(火) 01:33:00.26ID:A9u6a3RO
こういう問題って、極小・最小解にいたる連続的な解空間形成してなけりゃ収束計算もできないし
かといって解析的あるいはロジカルな求解法が見出せなけりゃ、最後はヒューリスティックあるいはランダムwalk
あるいはRISMみたいな外挿的に探索するしかないのだろうか…
ないんだろうなたぶん。そんなきがす
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況