プログラミングのお題スレ Part22 (882ﾚｽ)
上下前次1-新
254(2): 2024/02/18(日)18:14 ID:puttXdr1(2/4) AAS
>>243
しらみ潰しで失格
>>244
しらみ潰しで失格
>>245
しらみ潰しで失格
255(1): 2024/02/18(日)18:15 ID:puttXdr1(3/4) AAS
>>246
しらみ潰しで失格
>>247
しらみ潰しで失格
>>248
しらみ潰しで失格
256(1): 2024/02/18(日)18:16 ID:puttXdr1(4/4) AAS
>>250
しらみ潰しで失格
>>251
しらみ潰しで失格
257: 2024/02/18(日)18:26 ID:ovKjFpQ6(1) AAS
>>253-256 アスペで不合格ｗ
258: 2024/02/18(日)18:34 ID:rWy6ZYAH(1/2) AAS
>>234 ruby
外部ﾘﾝｸ:ideone.com
f = -> n {
(0..n).lazy.map {|i| [n - i, n + i].select {|x| x.to_s.reverse.to_i == x}}.find(&:any?).uniq
}
>>252
(｀･ω･´)ゞ
誤：a - 1, a + 1
正：a - 1, b + 1
259(1): 2024/02/18(日)19:41 ID:rWy6ZYAH(2/2) AAS
>>234 dart
外部ﾘﾝｸ:ideone.com
void main() {
var rev = (n) => int.parse(n.toString().split('').reversed.join());
var f = (n) => Iterable.generate(n + 1).map((i) => [n - i, n + i].where((x) => x == rev(x))).firstWhere((a) => a.isNotEmpty).toSet().toList();
print([0, 17, 100].map((n) => [n, f(n)]));
}
260: 2024/02/20(火)08:46 ID:8US2zplP(1) AAS
【㋮㋑㋣㋹㊀㋳】 チャールズ３世戴冠式に｀死神´
2chｽﾚ:kokusai
BEｱｲｺﾝ:22ja8.png
261: 17 2024/02/20(火)10:47 ID:YmH8jdAc(1) AAS
>>254
しらみ潰しって、どんなテストしたの？
262(2): 2024/02/20(火)12:59 ID:qzcGLGiS(1) AAS
しらみ潰しとは例えば1から順番に見つかるまで全てを試していく最悪な方法を指す
今回の場合だと与えた数から順番に見つかるまで±1を続けて全てを試していって探すプログラムが該当する
263: 9 2024/02/20(火)17:18 ID:X5uoFLgg(1) AAS
「どんなテストしたの？」
って質問だよ
264(1): ◆QZaw55cn4c 2024/02/20(火)20:48 ID:RtAsHDVN(1) AAS
>>262
私は >>248
だけれども、解法としてはそれしかないと思いますね
265: 2024/02/20(火)22:00 ID:e+y9lgSN(1) AAS
>>249 と >>238 は
しらみ潰しではなく
きちんとプログラミングして算出しているようにみえますね
266(3): 2024/02/21(水)13:54 ID:ve9Dz9D8(1) AAS
>>264
私は解答は提出していないが、ざっくりと自分が思いついた方法
まず、以下のような操作を考える
A. 1234という入力に対して1234321を返す
B. 1234という入力に対して12344321を返す
ここで、xという入力に対してA,Bが返す数をA(x),B(x)と表すことにする
次に、与えられた数の桁数で場合分け
(1)与えられた数字の桁数が奇数の場合
例として5桁の数字を考える
N=a*10000+b*1000+c*100+d*10+e*1 (a~eは1桁の自然数, aは0でない)
省17
267(1): 2024/02/21(水)16:02 ID:Sko4Sglv(1) AAS
>>266
N=17
のときは？
268: 259 2024/02/21(水)23:06 ID:DX/jvS2m(1) AAS
>>259
Iterable.generate(n).map(f)は単に
Iterable.generate(n, f)で良かったと判明
269(1): 2024/02/21(水)23:42 ID:bqTl0uQM(1) AAS
>>234
>>249をC++で書き換え（入力値は64ビット整数の範囲内限定）
外部ﾘﾝｸ:ideone.com
元々はCで書き、4行目はなし、15行目と24行目はstrrev(s + i);だったが、Windowsのgccでは
コンパイルできたのにideoneではできなかったので、仕方なくC++にしてstd::reverseで代用した。
270: 2024/02/22(木)00:34 ID:+mJgzEZf(1) AAS
>>234 lisp
>>266を参考に>>249(C#)を移植
外部ﾘﾝｸ:ideone.com
271: 2024/02/22(木)01:30 ID:9s07Ijs0(1) AAS
>>234
Rust
fn nearest_palindrome_numbers(n: usize) -> Vec<usize> {
let mut dd = DecimalDigits::new(n);
dd.palindrome_using_upper_half();
let n1 = dd.to_number();
match compare(n, n1) {
Equal => return vec![n],
Greater => dd.increment_upper_half(),
Less => dd.decrement_upper_half(),
省12
272: 266 2024/02/22(木)01:47 ID:c61GBvnr(1) AAS
>>267
N=17=1*10+7*1のとき、Nは2桁(偶数桁)でM=1*1=1
B(M)=B(1)=11はNより小さいのでB(M-1)は考えなくてよい
B(M+1)=B(2)=22なので11,22が答えの候補
11より22のほうが17に近いので22が答え
ちょっとNに対するMの説明が足りてなかったけど言葉で上手く言い表せないすみません（上位半分以上かつ最小の桁数を抜き出す、的な）
273(2): 2024/02/22(木)20:54 ID:+nyM4OV5(1/2) AAS
>>234 ruby
外部ﾘﾝｸ:ideone.com
・それっぽい三個の候補から選んでるだけ
274(1): 2024/02/22(木)21:04 ID:3p8Kt6H4(1) AAS
>>234
>>269の一部でC++の機能をどうせ使ってしまったので、この際、全部をC++流に変えたら
C流よりすっきり書けた。
外部ﾘﾝｸ:ideone.com
275: 273 2024/02/22(木)21:48 ID:+nyM4OV5(2/2) AAS
>>273
> [1000, [1001]]
誤：ps = [p.(s), p.(t.to_i.pred.abs.to_s + u), p.(t.succ + u)]
正：ps = [p.(s), p.(t.to_i.pred.abs.to_s + u), p.(t.succ + u), p.(s.to_i.pred.abs.to_s)]
とりあえず雑に修正してみたが？
(ﾉ∀`)ｱﾁｬｰ
276(1): 17 2024/02/23(金)18:10 ID:ZR6D6MGM(1/2) AAS
>>262
>>245のKotlinのプログラムは何も考えてなくて本当に馬鹿正直に±1して一つ一つ検査する方式で作ったんだけど、それでもあなたのテストではダメということになったの?
まあ Int (符号付32bit整数) 使ってるからその限界超えたらダメではあるんだけど、そういう問題ではなく?
277(1): 2024/02/23(金)18:58 ID:9Umf93zL(1) AAS
>>276
それはしらみつぶしと言われる駄目プログラミングだよ
例えば求める解法が存在する方程式を解くのに値を±1しながら順に代入して試していくのと同じ
278: 2024/02/23(金)21:39 ID:ZR6D6MGM(2/2) AAS
>>277
あー。プログラムにバグがあってまともに答えが出ないっていうことではなく何の捻りもないプログラムだからダメっていう感想ね。それならわかる。
こちらもアルゴリズム思い浮かばないけどとりあえず作ってみただけだし。ダメというほどではないが良いとも思えないプログラムなので。
279(1): 273 2024/02/23(金)23:06 ID:RzwC5Hr4(1) AAS
>>234 ruby
外部ﾘﾝｸ:ideone.com
・273の[1000, [1001]]バグ修正版
・275とは違う方法で修正してみたがやっつけ感大
>>234 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・いわゆる（？）ジェネレータ版
・「終端を持たない範囲オブジェクト」はRuby 2.6.0から
280: 2024/02/24(土)00:25 ID:f2xn4abB(1) AAS
>>234
Ruby
外部ﾘﾝｸ:paiza.io
281: 279 2024/02/24(土)13:21 ID:aSUCvHSH(1) AAS
>>234 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・ジェネレータ版ちょっとアレンジ
・to_sしてto_iするのをやめた
282(16): ◆QZaw55cn4c 2024/02/24(土)14:25 ID:NZEL8Kud(1) AAS
異なる自然数 a, b (a > b) における a^3 - b^3 を「a, b の三乗差」と呼ぶことにする。
異なる5通りの組(a, b) (c, d) ... (j, k) について三乗差がすべて相等しいとき
その組(a, b)...(j, k) および三乗差自体を求めよ
異なる6通りの組で三乗差が相等しい場合があるかも検討せよ
283(1): 2024/02/24(土)16:47 ID:KRWvIUHe(1) AAS
>>282
[(1134, 357), (1155, 504), (1246, 805), (2115, 2004), (4746, 4725)]
a^3 - b^3 == 1412774811
284: 17 2024/02/24(土)16:52 ID:Pf8MFN4C(1) AAS
数学、か・・・
285(1): 2024/02/24(土)18:16 ID:O6Cw1j13(1) AAS
>>282 ruby
外部ﾘﾝｸ:ideone.com
・そのまま版
・5秒じゃ?
286: 2024/02/24(土)20:03 ID:mNVJyIZh(1/2) AAS
>>234
>>274を巨大整数対応にした。
外部ﾘﾝｸ:ideone.com
287(1): 2024/02/24(土)22:30 ID:mNVJyIZh(2/2) AAS
>>282
aが5000以下限定で>>283の解はRで5秒以内に求められた。8〜9行目は下三角行列の要素番号から
行番号と列番号を求めているだけで、>>282を解く特別なアルゴリズムというわけではない。
外部ﾘﾝｸ:ideone.com
288(2): 285 2024/02/25(日)08:52 ID:M1xmyD2F(1) AAS
>>282 ruby 2.5.5
外部ﾘﾝｸ:ideone.com
・285の無駄なループ回数を削減
・でも5秒じゃ?
289(1): 2024/02/25(日)21:06 ID:CUQUyFSy(1) AAS
>>282
>>287は下三角行列の要素番号から列番号を求めるのに2次方程式を解くのが分かりにくかったから、
各列の最下行の要素番号を計算しておいてそれを二分探索するように変更した。
外部ﾘﾝｸ:ideone.com
n = 25000で実行してみても、n = 5000ときの解のa, bを両方とも2, 3, 4, 5倍した解しか別に
見つからなかった。
290(2): 2024/02/26(月)22:18 ID:CjcYgBx5(1) AAS
>>282
>>289と似た手順でC++
外部ﾘﾝｸ:ideone.com
Rではソートする前に重複値だけを抽出しているが、C++のunique関数はソート済みデータにしか
使えないので使っていない。
291(1): 288 2024/02/27(火)21:45 ID:nu8aoj+0(1) AAS
>>282 c
外部ﾘﾝｸ:ideone.com
・288の移植
292(1): 2024/02/27(火)22:30 ID:BJV11H6M(1) AAS
>>282
下三角行列の各列内の要素は昇順で既に並んでいるのに、>>290は下三角行列の全要素を
ソートして無駄なので、列のマージに変更（要するにマージソートを途中段階から開始）
したら少し速くなった。
外部ﾘﾝｸ:ideone.com
n = 10000でも5秒以内に終わった。
外部ﾘﾝｸ:ideone.com
293: 288 2024/02/28(水)22:00 ID:7ZY4TL6q(1) AAS
>>282 c++
外部ﾘﾝｸ:ideone.com
・288の移植
>>282 rust
外部ﾘﾝｸ:ideone.com
・288の移植
294(1): 2024/02/28(水)23:21 ID:FCtvUtiC(1) AAS
>>282
>>292とは別の方法で>>290を高速化
外部ﾘﾝｸ:ideone.com
1³, 2³, 3³, …, 5000³をD = 5001で割った余りはすべて異なる値になるから、d = a³ − b³を
Dで割った余りはどれか1つの値に偏ることなく均等に分布する。dをDで割った余りによりdを
区分すれば、各区分に入る個数はどれも多すぎないのでソートに時間が余りかからない。
Dの値はconstexpr関数によりコンパイラに計算させている。n = 10000, 15000のときは
それぞれD = 10002, 15009になる。
295: 291 2024/02/29(木)22:20 ID:HlaTo1dC(1) AAS
>>282 c
外部ﾘﾝｸ:ideone.com
・291から省メモリ化
旧：unsigned int values[10];
新：unsinged short values[4];
296(4): 2024/03/01(金)22:22 ID:6k2oCbjk(1/3) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>294はa, bの二重ループ内でa³ − b³をD = 5001で割った余りrにより区分していたが、
rのループ内でa, bを変化させるように変更したら、2次元配列がなくなってすっきりした。
その結果、メモリ使用量が激減し、nが大きい場合でも実行できるようになった。
297(1): 2024/03/01(金)22:23 ID:6k2oCbjk(2/3) AAS
>>296の続き
n = 1000000, m = 6で実行すると、12通りの解が見つかった。
[6つ組解]
424910390480793: (75978, 23919), (77385, 33768), (83482, 53935), (141705, 134268), (317982, 316575), (596001, 595602)
620174235433536: (86184, 27132), (87780, 38304), (90237, 48573), (94696, 61180), (160740, 152304), (360696, 359100)
1238805803151000: (107487, 14487), (108540, 34170), (110550, 48240), (119260, 77050), (454260, 452250), (851430, 850860)
1384074844012224: (112152, 29844), (125324, 83600), (130050, 93426), (159372, 138624), (224928, 215412), (357447, 353799)
1936290882196125: (127629, 52254), (133320, 75675), (149285, 111620), (228525, 215430), (246510, 235395), (290214, 282339)
4589726535576000: (170172, 69672), (177760, 100900), (185265, 120945), (304700, 287240), (328680, 313860), (386952, 376452)
4961393883468288: (172368, 54264), (175560, 76608), (180474, 97146), (189392, 122360), (321480, 304608), (721392, 718200)
省8
298(1): 2024/03/01(金)22:24 ID:6k2oCbjk(3/3) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>296のrのループ内でa³ − b³をD2 = 5003で割った余りr2により区分し、それぞれの区分ごとに
解を探すようにしたら速くなった。ただし、nが大きい場合にはかえって遅くなる。
299(1): ◆QZaw55cn4c 2024/03/03(日)19:08 ID:75HCbpT6(1) AAS
>>297
出題者です。
すごいです。ありがとうございます。私の手元ではまだ6通り解、7通り解のひとつも入手できていないので、参考になりました
私のアルゴリズムは効率が悪いようですね
300(1): 2024/03/03(日)22:19 ID:ZEDvt9uH(1) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>298でnを大きくするにつれ>>296に対する高速化効果が薄れていくのは、ABをvectorでなく
配列にしたらある程度改善された。n = 5000のときの実行時間は>>296の半分以下になった。
ただし、n = 1000000まで大きくすると、296よりやっぱり遅くなる。
>>299
どんなプログラムを書いたのか見せて。
301(3): 2024/03/06(水)22:35 ID:lIZep5aT(1) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>300の実行時間を分析すると、最も時間が掛かっているのは46〜と47行目だと判明した。
そこで配列ABの第1次元と第2次元を入れ替えてみると、n = 5000では変わらないが、
1万, 2万, 5万, 10万, 20万では35%前後高速になった。これは、改良前には第2次元の添字が
小さい要素に書き込みが集中しているため、改良後のように第1次元に入れ替えた方が
纏まったメモリ領域に書き込みが集中しキャッシュの効きが良くなるからだと考えられる。
一方、n = 100万で高速化しないのは、書き込み集中領域が大きすぎるからだろう。
外部ﾘﾝｸ:ideone.com
省5
302: 2024/03/08(金)19:02 ID:oHHhAfhn(1) AAS
>>301
ハズレが多いから2passは効果ある？
303: 2024/03/09(土)22:13 ID:C74EWG6S(1/2) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
関数mainのループで配列A, B, Pに書き込まずdにだけ書き込むようにし、関数FindDuplicatesで
dの添字Pではなくdそのものをソートするように変えて、n = 1000000の場合に>>301より10%高速化。
関数PrintSolutionでa, bをmainでと同じ方法で再計算するのは非効率だが、PrintSolutionは僅か12回しか
呼ばれないため、全体の実行時間への影響は無視できる。
304(6): 2024/03/09(土)22:47 ID:v99WCN19(1) AAS
お題
460円 580円 600円 の3種類の商品があります
これらを組み合わせて合計10個買ったら5360円になりました
組み合わせを求めるプログラムを書いてください
ちなみに答えの一つは
・600円×2
・580円×4
・460円×4
だそうです
2chｽﾚ:cigaret
305: 2024/03/09(土)23:59 ID:C74EWG6S(2/2) AAS
>>304
面倒なのでRで全探索
外部ﾘﾝｸ:ideone.com
306(1): 2024/03/10(日)01:20 ID:8NU5B5F+(1) AAS
>>304
面倒なので全て460円を引くと
A=0円 B=120円 C=140円
10個で760円という問題
面倒なのでさらに20で割ると
A=0円 B=6 C=7円
10個で38円という問題
つまり唯一奇数のCは偶数個が確定
Cが6個以上だと42円以上でオーバーしてNG
Cが4個だと28円で残り10円をA,Bで作れないからNG
省3
307: 2024/03/10(日)11:20 ID:Doj9A/yB(1) AAS
>>306
すごすぎるだろ、日本の未来を頼む
308: 2024/03/10(日)19:06 ID:qBLPZ6x8(1) AAS
>>304
Rで全探索でなくちゃんと解くと
外部ﾘﾝｸ:ideone.com
解が複数ある場合と全くない場合の例として、600円を540円と520円に変更したときの出力も載せた。
309(1): 2024/03/10(日)20:08 ID:6qxPF4Wx(1) AAS
2pass案は多少工夫したらかなり速い
n ␣␣m ␣296␣ ␣301-1 ␣301-2 ␣303␣ ␣2pass
5k␣␣5 ␣ 0.5s ␣ 0.1s ␣ 0.5s ␣ 0.4s ␣ 0.1s
25k ␣5 ␣12.7s ␣ 2.5s ␣13.9s ␣11.1s ␣ 1.7s
100k␣5 ␣3m52s ␣49.3s ␣4m13s ␣3m26s ␣38.9s
1M* ␣6 ␣8h23m ␣2h50m ␣8h51m ␣6h43m ␣1h11m
*n=100万は1万サンプルの部分ループ500k≦r＜510kから100倍
>>301の296と301-2の比較記述と違う傾向があるのはキャッシュ階層の違いだと思う
2passは301-1に近いけど1pass目でのランダムアクセスサイズを落としながらも
誤判定率を低く抑える(0.2%～2%)工夫をするのがお楽しみだと思う
310: 2024/03/14(木)14:43 ID:ZraPd1+Q(1) AAS
ｔ
311: 2024/03/27(水)23:42 ID:sRZ89+IF(1) AAS
>>304
a = (600, 580, 460)
m = min(a)
h = set()
def buy(b, yen):
if yen < m: return
for i in range(0, len(a)):
v = a[i]
if yen >= v:
b[i] += 1
省7
312: 2024/03/27(水)23:55 ID:qNf/D02g(1) AAS
>>304
Haskell
[(a, b, c) | a <- [0..20], b <- [0..20], c <- [0..20], a * 460 + b * 580 + c * 600 == 5360]
output: [(0,2,7),(4,4,2)]
313: 2024/03/28(木)00:00 ID:0Zoa9Vsx(1) AAS
合計10個という条件忘れてた。
[(a, b, c) | a <- [0..20], b <- [0..20], c <- [0..20], a + b + c == 10, a * 460 + b * 580 + c * 600 == 5360]
output: [(4,4,2)]
314: 2024/03/31(日)11:57 ID:enek7T1c(1/2) AAS
大幅に手直しした
特に前回数値が一部出てこない状態になっていたので色々と手動で最適化した
新しいアイディアを思いつかない限りはシングルスレッドでの限界に近いと思う
n m 301-1 303 2pass 2pass'
5k 5 0.1s 0.4s 0.1s 0.1s
25k 5 2.5s 11.1s 2.3s* 1.7s
100k 5 49.3s 3m26s 38.9s 27.7s
1M* 6 2h50m 6h43m 1h11m 48m10s
2M* 6 17h06m 28h27m 5h47m 3h13m
Max* 6 35h51m 51h23m 11h09m 5h47m
省11
315: 2024/03/31(日)11:58 ID:enek7T1c(2/2) AAS
n D1 D2 D3 = 25000 25003 25005 25006
false_positive = 171 / 25003 = 0.68%
total_t_pass1 = 1654.681 ms 2.647 ns/iter
total_t_pass2 = 1.407 ms 0.329 ns/iter
real 0m1.709s
false_positive = 2211 / 100005 = 2.21%
total_t_pass1 = 27338.298 ms 2.734 ns/iter
total_t_pass2 = 78.402 ms 0.355 ns/iter
real 0m27.692s
n D1 D2 D3 = 1000000 1000002 1000009 1000015
省14
316: 2024/03/31(日)22:30 ID:4FIGx2uN(1) AAS
>>304
ぶっちゃけ、他の言語の人と同じっぽくないので心配なんだが…。
自分なりにHaskellで全探索じゃないバージョン書いてみた。
Haskell
[(a, b, c) | a <- [0..10], b <- [0..10 - a], c <- [0..10 - (a + b)], a * 460 + b * 580 + c * 600 == 5360, a + b + c == 10]
答えは同じ[(4,4,2)]。
317: 2024/04/01(月)04:52 ID:iTC1bSa8(1) AAS
少し一般化して、N個の商品があり、i番目の商品はA_i円です
合計M個購入し、価格の合計がS円であるような購入の仕方を998244353で割った余りを求めてください
だとO(N M S)より小さい計算量で解けるのかな
318: 2024/04/01(月)16:50 ID:0Kkx57P3(1) AAS
2個、4個、8個…みたいにメモ化すればMはlogMにできるかもしれんね
空間がlogM倍されそうだが
319(2): 2024/04/13(土)11:43 ID:itq2kjOw(1) AAS
ヘロンの公式を実装せよ
使用言語：C
320: 17 2024/04/13(土)16:57 ID:SxW/5mRR(1) AAS
>>319
外部ﾘﾝｸ:paiza.io
Wikipedia でヘロンの公式を調べてそのまま実装しただけで、ほとんど何も考えてない。
321(3): 2024/04/13(土)23:01 ID:wFZkrOeZ(1) AAS
>>319
外部ﾘﾝｸ:ideone.com
ヘロンが作ったもう1つの式である平方根を加算と除算の繰り返しで求める式も使用。
sqrt関数を呼び出すより実行形式ファイルサイズがほんの少しだけ小さくなる。
322(1): 2024/04/14(日)00:59 ID:ujzJ2+0Y(1) AAS
>>321
無限ループにならない?
機械イプシロン(DBL_EPSILON)とか気になる
323: 2024/04/14(日)18:34 ID:MHeAinLP(1/2) AAS
解答例
#include <stdio.h>
#include <math.h>
void heron(double, double, double);
int main(void)
{
double a, b, c;
printf("３辺a, b, cを入力せよ ");
scanf("%lf,%lf,%lf", &a, &b, &c);
heron(a, b, c);
省9
324: 2024/04/14(日)18:36 ID:MHeAinLP(2/2) AAS
>>321 さすがですね
325(1): 2024/04/15(月)21:01 ID:dSNEYg5r(1) AAS
>>322
p < 0 のとき（= 三角形を作れない場合）は浮動小数点数の特性に関係なく無限ループになる。
sqrt(p) と同様にNANを返すには、if (p < 0) return 0 / (p - p); を追加すれば良い。
p > 0 のときは無限ループにならないはず。以下が検証プログラム。
外部ﾘﾝｸ:ideone.com
x = sqrt(p), y = p / x とすると、浮動小数点数の特性により x == y とならない場合は存在する。
このとき、xとyの仮数部を整数と見なした値（以降では「仮数整数」と呼ぶ）の差は1なので、
z = (x + y) / 2 はxとyのうち仮数整数が偶数の方に一致する。zを新たなxとして代入しyとzを
再計算すれば、今度はxの仮数整数が偶数なのでzはxに必ず一致し、>>321の収束判定条件が成立する。
具体例で見ると、p = 2 のときはxの仮数整数が奇数なので x != z となるが、zを新たなxとして代入し
省2
326: 2024/04/15(月)22:06 ID:MxMoolaJ(1) AAS
>>325
解説ありがとう
俺には理解できないレベルだと分かりましたｗ
俺なら収束の自信が無くてDBL_EPSILONを使った判定と
ループ回数上限を組み合わせて実装しそうだ
327(2): 2024/04/17(水)05:47 ID:F2fqxIYT(1/2) AAS
ヘロンの公式はそのままだと、数値計算での安定性が良くないらしいぞ
解決策は、Wikipediaの英語版の方に…
外部ﾘﾝｸ:en.wikipedia.org
328: 327 2024/04/17(水)05:52 ID:F2fqxIYT(2/2) AAS
そしてこんなとこでもカハンせんせーの名前がが
329: 2024/04/17(水)16:28 ID:7JRzlbtx(1) AAS
の長さ
この公式で計算される面積は、理論的には正しい値です。しかし、実際には、以下の理由で誤差が生じる可能性があります。
数値計算の誤差: 計算機で数値を扱う場合、有限桁しか扱えないため、丸め誤差が生じます。特に、辺の長さの値が大きく異なる三角形の場合、この誤差が顕著になります。
四捨五入誤差: 計算結果を小数点以下n桁まで表示する場合、n桁目以降の数字を切り捨てます。この四捨五入誤差も、面積の誤差に影響を与えます。
by Gemini
330: 2024/04/17(水)23:38 ID:k4k/eSae(1) AAS
>>327に載っている参考文献
William M. Kahan, ‘Miscalculating Area and Angles of a Needle-like Triangle’
外部ﾘﾝｸ[pdf]:www.cs.berkeley.edu
のTable 1の問題がパソコン等でのC++プログラムでも再現されるか試してみた。
外部ﾘﾝｸ:ideone.com
Table 1とは違い、Accurate Δが概ね正確な場合にHeron's Δ'が大きく懸け離れた不正確な値に
なってしまうことはなく、ほぼ同じ値になり差はごく僅かしかない。Table 1のような不安定性は
Table 1の計算に使われたプログラマブル関数電卓に特有の問題で、パソコン等のプログラムでは
再現されない。(パソコン等のdoubleの方が精度が高いので当然と言えば当然だが)
一方、(a, b, c) = (5278.64055, 94721.35941, 99999.99996)の場合は、逆にHeron's Δ' = 0が
省10
331(2): 2024/04/18(木)07:16 ID:8T8m8Yde(1) AAS
>(a, b, c) = (5278.64055, 94721.35941, 99999.99996)
>c - (a - b)が正確には0なのに3.63797880709171e-12と計算されてしまい
この例に限らず、たいていの場合a,b,cはdoubleでexactに格納されて無くて
この例では「c - (a - b)が正確には0」なのをチョイスしただけでは？
332: 2024/04/18(木)07:30 ID:PYBA8OB3(1/2) AAS
パソロジカルな三角形をパラメトライズして面積を積分する検証はどう？
数式計算での正確な値
Heronで面積計算した時の数値積分
Accurateで面積計算した時の数値積分
を比べるのがフェアかなぁと
333(1): 2024/04/18(木)07:34 ID:PYBA8OB3(2/2) AAS
> 200ビットで計算したほぼ正確な値3.27490470056059e-07
この例だけ見るとAccurate Δの方が優れているように見えるので
>>331の様なチェリーピックはどちらの計算式でも出来るので平均的に近似が近い方が精度的に優れているかと
334: 2024/04/18(木)22:41 ID:y7NBfn6/(1) AAS
>>331
その通り。そして、(a, b, c) = (10000.1, 10000.2, 20000.3)とすれば、正しい面積は0なのに
Heron's Δ' = 2.69745899635295とAccurate Δ = 1.34872949817647は両方とも大間違いになる。
この場合のようにHeron's Δ'での問題がAccurate Δで改善されないだけでなく、>>331の引用の
場合のようにHeron's Δ'では結果的に問題ないのにAccurate Δでは新たな問題が生じてしまうのは、
参考文献の11ページで述べられた
An algorithm stood convicted of numerical instability if it could be replaced by
a new algorithm at least about as fast and accurate as the old for all data,
and good for all data for which the old algorithm was bad.
すべてのデータに対して旧アルゴリズムと少なくとも同じくらい高速かつ正確であり、
省9
335: 2024/04/18(木)22:55 ID:n9UdHBZN(1) AAS
総合すると有効桁じゃなくて精度が2桁良いし実装上は大差ないから改良版を使う、と言う方が自然では？
336(1): 2024/05/01(水)12:56 ID:nIC3qyB/(1) AAS
スレ落ちそうなのであげ
337: 2024/05/01(水)15:39 ID:hqp8cDbc(1) AAS
>>336
嵐を呼び込むために・・・
338(1): 2024/05/01(水)22:59 ID:4hNncNW1(1) AAS
何でこんなに過疎化しちゃったのか。前に頻繁に出題していた人がいなくなったのか。
339: 2024/05/02(木)10:32 ID:ijoO2C2L(1) AAS
お題を出してみてください
340(1): 2024/05/02(木)16:59 ID:DPVqLIsI(1) AAS
>>338
お題が出尽くしたってことはあるんじゃないか？
過去のお題拾ってきてそれを投稿すればいいぐらいまでスレが成熟してしまったのでは？
341: 2024/05/02(木)17:21 ID:pg1ymc2D(1) AAS
PC買って、脱衣AIで遊びまくってる「
一日一回無料で使えるみたい「
2chｽﾚ:gymnastics
342: 17 2024/05/02(木)18:44 ID:LxBZq7I4(1) AAS
>>340
なるほど。それをやるか。
343(3): 17 2024/05/14(火)05:34 ID:ou5vbzLn(1) AAS
じゃあ10年前のこのお題(URLを書くとNGになるようなので書かない)。
プログラミングのお題スレ Part4
115 ：デフォルトの名無しさん：2014/06/21(土) 18:36:45.72 ID:/fMJIWig.net
お題：文字列Aを1回以上繰り返した文字列Bが与えられたとき
文字列Aを求める。ただしAの候補が複数ある場合は最短のものとする。
例
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa -> a
123412312341231234123123412312341231234123 -> 1234123
oxoxoxoxoxoxoxoxxoxoxoxoxoxoxoxoxx -> oxoxoxoxoxoxoxoxx
344: 2024/05/14(火)17:27 ID:AXiunB2g(1) AAS
外部ﾘﾝｸ:ideone.com
Z-algorithm を使って O(|B|) で解いてみた
345: 警備員[Lv.4][初] 2024/05/14(火)20:59 ID:xk+62xOP(1) AAS
>>343
R
外部ﾘﾝｸ:ideone.com
C
外部ﾘﾝｸ:ideone.com
346: 警備員[Lv.18] 2024/05/23(木)14:16 ID:zV267ZMC(1/2) AAS
あれ？どんぐりの都合か？URL書いてあると書けなくなったような？
347: 警備員[Lv.18] 2024/05/23(木)14:17 ID:zV267ZMC(2/2) AAS
URLの先頭のhを抜いて書いてみよう。
>>343
Kotlin
こちらは普通に自作したやつ。
外部ﾘﾝｸ:paiza.io
こちらは正規表現使ってとても小さくなったやつ。
外部ﾘﾝｸ:paiza.io
348(5): 2024/06/01(土)10:16 ID:hzaQXY32(1/2) AAS
お題: コロン区切りの時分秒の時刻が与えられるので時分秒をそれぞれ掛け算した結果を表示せよ
例:
04:05:06
120
349(4): 2024/06/01(土)11:08 ID:hzaQXY32(2/2) AAS
お題: バイト列が与えられる。先頭から解析した場合にバイトが1だったら次の4バイトを読み込んで整数として出力し、バイトが2だったら次のバイトを0が来るまで読み込んで文字列として出力せよ
入力
1 1 0 0 0 2 65 66 67 0 1 128 0 0 0
出力
1ABC128
350: 2024/06/01(土)12:57 ID:M5I0DyuF(1) AAS
知らんがな
351: 2024/06/01(土)23:31 ID:oEZc8FHN(1) AAS
>>348
R
外部ﾘﾝｸ:ideone.com
>>349
C (データ識別子は1か2しかないものとし、整数のエンディアンは実行環境依存とする)
外部ﾘﾝｸ:ideone.com
352: 警備員[Lv.19] 2024/06/02(日)04:45 ID:yi3OE76t(1/2) AAS
>>348
Perl
bash のコマンドラインから入力して実行(ワンライナー)
$ perl -ne 'if(/(\d+):(\d+):(\d+)/){print $1*$2*$3,"\n"}else{print"入力エラー\n"}'
1:2:3
6
3:4:5
60
04:05:06
120
省1
353: 警備員[Lv.20] 2024/06/02(日)05:19 ID:yi3OE76t(2/2) AAS
>>349
Kotlin
外部ﾘﾝｸ:paiza.io
上下前次1-新書関写板覧索設栞歴
あと 529 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.919s*