19/05/27 23:59:39.40 WucVzOyp.net
>>149 間違っていないでしょ。
両方あるよ。
xys [[136 577]
[110 927]
[472 199]
[157 808]
[388 598] ***
[ 94 31]
[388 157] ***
[325 409]
[787 897]
[850 598]]
URLﾘﾝｸ(i.imgur.com)
151:デフォルトの名無しさん
19/05/28 00:07:34.28 A9u6a3RO.net
>>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の範囲をこえてしまうものがあるらしく、不均等に伸ばすようにすれば
より小さい正方形を見出せるかもしれない。
152:デフォルトの名無しさん
19/05/28 00:08:24.04 A9u6a3RO.net
>>150
そうだね、ｺﾞﾒﾝ
153:デフォルトの名無しさん
19/05/28 00:16:35.63 eILR4MCH.net
>>150 外接円を描いてみたけど、利用方法を見つけられなかった。
むしろ [ 94 31] [787 897] の対角を直径とする最小包含円 からかな？
154:デフォルトの名無しさん
19/05/28 00:27:46.22 A9u6a3RO.net
以下は試作実験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°
真の極小解は中途半端な角度にあるのか…
155:146
19/05/28 00:38:23.09 dFqOFikP.net
>>148
146は、ヒュースリックス解だから、まだ小さくなると思う。
でも、あと1くらいだと思う
( これが厳密解を求めるやる気が、無くなる原因)
少しずるして、この問題に過剰最適化させて、
890.7003209442369にした。
図 URLﾘﾝｸ(codepen.io)
156:デフォルトの名無しさん
19/05/28 00:44:50.83 A9u6a3RO.net
>>154
これ、凸包の辺の角度にのみ傾けてない、凸包の全頂点の組み合わせエッジの角度に傾けている。
まいいや、大差ない
157:デフォルトの名無しさん
19/05/28 01:02:45.97 eILR4MCH.net
>>125 >>11 の問題1 に名前を与えるならさしずめ、最小包含正方形 かな。
158:デフォルトの名無しさん
19/05/28 01:18:31.05 eILR4MCH.net
>>155 無理を言ってごめん、答えの誤差をなくすために、最終座標は整数の xy 座標に出来るかな。 中心からの距離を切り上げて整数にする感じになると思うけど。
159:デフォルトの名無しさん
19/05/28 01:33:00.26 A9u6a3RO.net
こういう問題って、極小・最小解にいたる連続的な解空間形成してなけりゃ収束計算もできないし
かといって解析的あるいはロジカルな求解法が見出せなけりゃ、最後はヒューリスティックあるいはランダムwalk
あるいはRISMみたいな外挿的に探索するしかないのだろうか…
ないんだろうなたぶん。そんなきがす
160:デフォルトの名無しさん
19/05/28 01:41:09.17 eILR4MCH.net
>>159 現実の世界でも、求める解は整数にすることが多いと思う。
画面のドット精度、工作機械の精度など整数と考えた方が良い。
現実的には整数解が求められないと、角を切り落としたりしかねない。
(許容誤差を加えた範囲を求めるのでも良いけど)
整数解にした方が、試行錯誤の時間も少なくなると思うからより現実的だと思う。 答えが一律に決まるし。
161:50
19/05/28 13:42:19.32 tpS8MDSU.net
ｽﾚﾘﾝｸ(tech板:920番)
前スレの920の、ランク付けの問題で、
入力データ
-6 3 9 5 3 -7
出力・ランク
2 3 5 4 3 1
2 3 6 5 3 1
下のように、同値の場合は、同じランクにして、次のランクの間隔を空ける場合、
ランク3 が2つあるから、4が無くなって、次は、5に飛ぶ場合は、難しい！
162:デフォルトの名無しさん
19/05/28 16:43:58.97 C7xxE9sL.net
>>161
uniqしないだけ
163:デフォルトの名無しさん
19/05/28 17:48:16.52 IzhB96hl.net
>>153 このケースの場合の最小包含円は外接円と一致するんだな。
164:デフォルトの名無しさん
19/05/29 15:51:03.59 PE9V8n6M.net
素因数分解する関数を作れ。
ただし2より小さい数は空のリスト(又は配列)を返す事とする。
例: factorization 150
＞[2,3,5,5]
165:デフォルトの名無しさん
19/05/29 16:00:45.49 bq8lopql.net
はい、次のお題どうぞ
166:
19/05/29 18:28:49.13 8RGCI467.net
>>164
== ｽﾚﾘﾝｸ(tech板:988番) == >>56 >>59 >>61
167:デフォルトの名無しさん
19/05/29 21:59:41.60 tGd6tVjg.net
>>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]
168:デフォルトの名無しさん
19/05/30 18:43:19.57 vFLUPPTs.net
>>166
すでに既出だったとは。。。orz
169:デフォルトの名無しさん
19/05/30 18:45:09.99 vFLUPPTs.net
>>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]
170:デフォルトの名無しさん
19/05/30 18:49:02.33 WCG+7mjF.net
既に既出
馬から落馬
歌を歌う
舞を舞う
ダンスをダンスる
171:デフォルトの名無しさん
19/05/30 18:50:08.40 WCG+7mjF.net
ヤフーでググる
172:デフォルトの名無しさん
19/05/30 20:22:38.83 JBeAmq0Y.net
お題: sin, cos を用いてお題を作成せよ
173:デフォルトの名無しさん
19/05/30 20:26:45.68 zjW7i8/A.net
eをネイピア数とした時
e^(iθ) ≠ cosθ + i sinθ
となる事を証明せよ
174:デフォルトの名無しさん
19/05/30 20:35:25.37 7cnHmzOq.net
ん~、じゃあ
sin, cos を実装せよ
175:デフォルトの名無しさん
19/05/30 22:02:46.02 8+NCnZcE.net
>>173
オイラーの公式なめてんの？
176:デフォルトの名無しさん
19/05/30 22:10:08.81 mWdPfVjS.net
>>175
exp(iθ)=cosθ+isinθだけど(2.71828...)^(iθ)は多値関数だよ
177:デフォルトの名無しさん
19/05/30 22:23:36.25 mWdPfVjS.net
>>176
多値じゃなくて多価
178:デフォルトの名無しさん
19/05/30 23:36:43.35 0JxSfYBl.net
^はxorだからな。そりゃ違うさ。
179:蟻人間
19/05/30 23:40:43.53 rhzd9E8p.net
お題:テーブル方式でcos/sin関数をテキトーに自作ｾﾖ。
180:デフォルトの名無しさん
19/05/30 23:54:33.59 J5ONVYE0.net
>>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);
181:デフォルトの名無しさん
19/05/31 00:55:18.43 t9s7pmzY.net
ああこりゃ多価関数の意味を知らないバカだな
182:デフォルトの名無しさん
19/05/31 01:02:49.06 6bzo9swJ.net
複素数の指数関数や対数関数は多価関数だろ
馬鹿はお前だ
183:デフォルトの名無しさん
19/05/31 01:38:23.70 4Atryqh8.net
指数関数は多価じゃないよ、何言ってんの
184:デフォルトの名無しさん
19/05/31 05:30:51.21 Rd2VdfQd.net
>>183
寝言はねえから言えよクズ
z^w := exp(w * log(z))
log(z) が多価関数なんだから一般にz^wも多価関数だっつーの
死ねよ雑魚が
URLﾘﾝｸ(en.wikipedia.org)
> 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.
185:デフォルトの名無しさん
19/05/31 05:49:38.41 C3HpXD20.net
>>184
出典がwikiとかありえねーよwww
wikiにそう書いてあるからってそれが正しいとは限んねえだろバーカ
186:デフォルトの名無しさん
19/05/31 06:17:16.52 4Atryqh8.net
>>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 なんて使わないでしょ?
187:デフォルトの名無しさん
19/05/31 06:53:54.48 BfGYI+kd.net
>>186
主値を取る場合はLogなりp.v. ｆなりきちんと明示するのが少なくとも解析屋の間ではルールだよ
他の分野の人は知らないけど
188:デフォルトの名無しさん
19/05/31 07:16:05.79 LXc8d8Er.net
>>170
> 歌を歌う
歌うには「歌を」と言う意味は含まれてないから歌を歌うと言うのは別におかしくないよ
> 舞を舞う
も同様
189:デフォルトの名無しさん
19/05/31 07:32:11.07 E12bWjgi.net
>>164 Python sympy
from sympy import *
print(factorint(150))
#{2: 1, 3: 1, 5: 2} 2*3*5**2 を示す
190:デフォルトの名無しさん
19/05/31 12:16:09.80 ihIFj/V/.net
>>188
和語として語源同一なんだけど。
意外なものでは「くさい」と「くそ」「明かり」と「開ける」も同一語源。
191:デフォルトの名無しさん
19/05/31 14:15:19.33 rnSTXr8b.net
数学の問題なんて、センター入試問題でも解いてこいよ。 手を抜きすぎだぞ。 もっと面白くひねれよ。
192:デフォルトの名無しさん
19/05/31 20:50:13.55 /Dlwa3kC.net
>>164
Haskellを元にPython。
素数じゃ無いと判定した時点でループ抜けるとかしたら、そこそこ速くなった。
URLﾘﾝｸ(ideone.com)
193:デフォルトの名無しさん
19/05/31 23:54:43.29 fDsN7sSa.net
センターなんて数学じゃなくて算数でしょ
194:デフォルトの名無しさん
19/06/01 05:45:08.23 uuPo6pHP.net
面白いお題がないかと文句を言う前に
進んで面白いお題を書きましょう
195:デフォルトの名無しさん
19/06/02 10:12:21.99 kAC27lYz.net
>>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
196:デフォルトの名無しさん
19/06/02 15:03:12.02 c9LZ9fJN.net
>>192 は >>164向けの回答としては問題ない。
しかし、一般的な素因数分解としては問題が。
大きな素数が対象のとき、実行時間がひどい結果になっている。
たとえば有名な素数1000000007(10億7)をやると....
(前スレ988の制約範囲内くらい、普通にできる形が望ましい)
pythonで手を抜いた一般的な素因数分解でも
10^12くらいは1秒以内に出る。(10^12+39が近場の素数)
197:195
19/06/02 18:27:22.13 Hxta4mKu.net
>>196 python sympy
{1000000007: 1} 0.2255000ms
198:195
19/06/02 18:41:56.81 Hxta4mKu.net
>>196 同一環境での比較。
n= 13999 ans= {13999: 1} time=0.0135830ms
>>192 を実行
n= 13999 ans= [13999] time=152.4304170ms
199:デフォルトの名無しさん
19/06/03 00:41:43.81 u5qwV1AY.net
>>198
192の解が一般解としてはひどいすぎるってことでしょ。
10億7どころか、百万台の素数もキツイ。
200:デフォルトの名無しさん
19/06/03 03:39:17.26 4uiCu3lL.net
お題：↓の画像のようにコンソール画面に雨を降らせなさい
URLﾘﾝｸ(i.imgur.com)
201:デフォルトの名無しさん
19/06/03 12:16:50.21 V0dR4GNy.net
>>164 pythonわかってない俺がpythonで
URLﾘﾝｸ(ideone.com)
202:デフォルトの名無しさん
19/06/03 21:33:09.94 CuEu7mic.net
>>164
Kotlin
URLﾘﾝｸ(paiza.io)
ただループ回すだけじゃ芸がないと思って素数を返すイテレータのクラス作ってやってみた。
(素数をバッファリングもすればもっと無駄がなかったなとは思ったがそれはやってない)。
203:デフォルトの名無しさん
19/06/04 06:42:47.26 7qxdZD6A.net
>>185
Wikiが正しいとは限らないからと言って、wikiが間違っている前提で反論するバカの見本
204:195
19/06/04 07:17:53.03 /ArpXH0n.net
>>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
205:デフォルトの名無しさん
19/06/04 07:56:52.47 //1XsOfQ.net
素数は、平方根までの素数で割って、割り切れなければ素数だろ
[2,3,5,7,11,13...] みたいに、素数表に追加していく途中で、
例えば、103 なら、11 までの素数で割って、割り切れなければ素数
13以降の素数で割る必要はない
もし13で割り切れるなら、13 * n = 103
となり、n は、√103 よりも、小さくなるから、既に割り切れているはず！
206:デフォルトの名無しさん
19/06/04 08:11:49.19 e9k+jtYr.net
>>205
例のRubyバカはこのスレにも出没するのか
207:デフォルトの名無しさん
19/06/04 09:07:39.39 QWQyVZWL.net
誰もRubyの話なんてしてないやろ
208:デフォルトの名無しさん
19/06/04 09:27:19.41 u+S7EiZ9.net
日頃の行いがなぁ…
209:デフォルトの名無しさん
19/06/04 10:23:22.04 prB+PlYz.net
>>185
間違いとも限らない。
書かれていることを鵜呑みにするのは間違いだが見もしないで頭ごなしに間違いと決めつけるのも間違い。
210:202
19/06/04 10:27:05.50 prB+PlYz.net
>>205
なるほど。暇があったらそれも考慮しよう。
211:デフォルトの名無しさん
19/06/04 11:04:03.94 Hzpqs43L.net
【速報】金券五百円分とすかいらーく優侍券をすぐもらえる
URLﾘﾝｸ(pbs.twimg.com)
① スマホでたいむばんくを入手
② 会員登録を済ませる
③ マイページへ移動する
④ 招待コード→招待コードを入力する [Rirz Tu]（スペース抜き）
今なら更に4日18時までの登録で2倍の600円の紹介金を入手
クオカードとすかいらーく優待券を両方ゲットできます。
かんたんに入手できますのでご利用下さい
212:デフォルトの名無しさん
19/06/04 13:01:01.36 XXr8i2SB.net
>>211
あとで一万円の請求が来るらしい
213:デフォルトの名無しさん
19/06/04 13:24:26.77 RxG/e7Cf.net
>>211
バラまきキャンペーン乙。
214:デフォルトの名無しさん
19/06/05 02:49:29.97 TK4G9YGK.net
>>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