- 1 名前：デフォルトの名無しさん mailto:sage [2019/11/17(日) 09:00:22.10 ID:xqEdXdr6.net]
- プログラミングのお題スレです。
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
結果がある場合はそれも
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
codepad.org/
compileonline.com/
rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
melpon.org/wandbox
https://paiza.io/
宿題は宿題スレがあるのでそちらへ。
※前スレ
プログラミングのお題スレ Part15
mevius.5ch.net/test/read.cgi/tech/1564310397/
- 610 名前：デフォルトの名無しさん mailto:sage [2020/01/11(土) 13:10:43.10 ID:JM9/51Sk.net]
- >>544 Perl4
use feature qw{say signatures};
sub rev($s) {
$s ne '' and substr ($s, -1, 1, '') . rev($s)
}
say rev('string
- 611 名前：');
てす [] - [ここ壊れてます]
- 612 名前：デフォルトの名無しさん mailto:sage [2020/01/11(土) 13:14:26.71 ID:JM9/51Sk.net]
- >>594 Perl5 だった…orz
しかし、このソースの「substr (」のrと(の間のスペース文字を省くと
スレへの書き込みで
HTTP/1.1 403 Forbidden
が起きて書き込めなかったのは謎…
- 613 名前：デフォルトの名無しさん mailto:sage [2020/01/11(土) 14:01:21.01 ID:M68szGrA.net]
- >>592
echo 5
- 614 名前：デフォルトの名無しさん [2020/01/11(土) 20:08:39.02 ID:go77StkR.net]
- お題
20200111の階乗を素因数分解したとき、すべての因数の積は20200111の階乗だが、
すべての因数の和は何か。
- 615 名前：デフォルトの名無しさん [2020/01/11(土) 20:55:04.41 ID:r5wulSj/.net]
- ナベアツ理論か。
- 616 名前：デフォルトの名無しさん mailto:sage [2020/01/12(日) 00:39:46.42 ID:PW2KE/yt.net]
- >>595
書き込めないコマンドは、一杯ある。
「ｌｓ −ｌ」とか
5ch は、特定の命令によって、表示の見た目を変えることができるから、
単に、表示する文字列に変換するだけじゃなくて、
投稿されたテキストから、命令を抽出したりしているから、
バグりそうなテキストを排除しているのだろう
- 617 名前：デフォルトの名無しさん mailto:sage [2020/01/12(日) 10:30:24.93 ID:Cuf7XVQy.net]
- >>597
C++
https://ideone.com/30RQZF
- 618 名前：デフォルトの名無しさん mailto:sage [2020/01/12(日) 16:28:53.41 ID:Svv4a/Ag.net]
- お題: バイナリ―サーチを実装せよ（自分の記憶だけで書かなければならない）
- 619 名前：デフォルトの名無しさん [2020/01/12(日) 16:52:57.01 ID:qRMFtMw7.net]
- >>601
Java
https://paiza.io/projects/y4RxMakkRM6x88qm5GGMvA
- 620 名前：デフォルトの名無しさん mailto:sage [2020/01/12(日) 17:33:54.06 ID:kqg5PnqA.net]
- >>601 Ruby
def bs(ary, &cond)
return ary[0] && cond.call(ary[0]) ? ary[0] : ary[1] && cond.call(ary[1]) ? ary[1] : nil if ary.size < 3
mid = ary.size / 2
bs(ary[cond.call(ary[mid]) ? 0..mid : mid + 1..-1], &cond)
end
p bs([1,3,5,7,9]){|i| i > 0} # => 1
p bs([1,3,5,7,9]){|i| i > 3} # => 5
p bs([1,3,5,7,9]){|i| i > 9} # => nil
- 621 名前： mailto:sage [2020/01/12(日) 17:39:35.02 ID:ZvwnN6DP.net]
- >>601
C++
https://mevius.5ch.net/test/read.cgi/tech/1434079972/33
std::set<int> の再実装にて、内部にバイナリーサーチを含んでいます
- 622 名前： mailto:sage [2020/01/12(日) 17:41:03.57 ID:ZvwnN6DP.net]
- >>601
＞（自分の記憶だけで書かなければならない）
これは重要かつ役に立つ訓練のしかたですね、この前は pthread の mutex と cond が理解できているかどうかを、この縛りのもとにコードを書いて試みました
- 623 名前：デフォルトの名無しさん mailto:sage [2020/01/12(日) 18:20:53.87 ID:Xff8C4Cf.net]
- >（自分の記憶だけで書かなければならない）
お題は全てそういうものだと思ってたが
みんなカンニングして回答してるの？
- 624 名前：デフォルトの名無しさん [2020/01/12(日) 19:59:45.88 ID:qRMFtMw7.net]
- お題1
10ビットの乱数を10個作成して
2進数に変換して出力してください
10ビットに満たない数は0埋めしてください
例)
1101101110
1000100011
0100111001
1110000001
1001001100
0010001111
1111001000
1010110111
1100001001
0100110111
お題2
縦方向、または、横方向に1が連続しているところを調べて
最も1が連続しているところの1の数を出力してください
ビット数や乱数の数が増えてもちょっぱやで処理できるとなお良いです
- 625 名前：デフォルトの名無しさん [2020/01/12(日) 20:38:11.83 ID:xWFTg64o.net]
- >>600
正解。あなたには簡単すぎただろうが。
Rで書いた解答例はPCでは2秒台で実行できたのに、ideoneでは制限時間5秒以内に
終わらなかったので、C++で書いた方を貼る。https://ideone.com/DFDdtr
>>600とほぼ同じだが、掛け算が減る分だけ速いな。
- 626 名前：デフォルトの名無しさん [2020/01/12(日) 21:27:08.47 ID:xWFTg64o.net]
- >>607
R
https://ideone.com/iTihQo
- 627 名前：デフォルトの名無しさん [2020/01/12(日) 21:44:57.86 ID:qRMFtMw7.net]
- >>609
ありがとうございます、そして申し訳ないです
11
11
こうなってたら4と出力してほしくて
連続じゃないですね、隣接といえばよかったかもしれません
縦方向、横方向に1が隣接してる領域のうち最大の領域の1の数を出力して欲しいのです
- 628 名前：デフォルトの名無しさん [2020/01/12(日) 21:45:02.91 ID:xWFTg64o.net]
- >>607
ビット数と乱数の数を別々に指定できるように訂正
https://ideone.com/cYMlMO
- 629 名前：デフォルトの名無しさん [2020/01/12(日) 21:48:51.97 ID:qRMFtMw7.net]
- すみません・・・平にご容赦いただきたく
- 630 名前：デフォルトの名無しさん [2020/01/12(日) 21:48:57.49 ID:xWFTg64o.net]
- >>610
隣接している領域は矩形でなければいけないのか、そうでなくても良いのか。例えば、
1110
0110
0111
は前者なら6個で、後者なら8個になる。
- 631 名前：デフォルトの名無しさん [2020/01/12(日) 21:52:58.77 ID:qRMFtMw7.net]
- >>613
矩形じゃなくていいです8個パターンです！
- 632 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 04:22:53 ID:5GjUS2iX.net]
- 質問なら質問スレに
宿題なら宿題スレに
回答を用意してない出題は禁止
- 633 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 04:47:28.11 ID:5GjUS2iX.net]
- 昔ながらのPAINTアルゴリズム
検索すれば色々と出てくるよ
- 634 名前：デフォルトの名無しさん [2020/01/13(月) 05:51:52.90 ID:9cAJpR6a.net]
- >>589 J
smoutput 10 10 $ p: <: p: i.100
実行結果
3 5 11 17 31 41 59 67 83 109
127 157 179 191 211 241 277 283 331 353
367 401 431 461 509 547 563 587 599 617
709 739 773 797 859 877 919 967 991 1031
1063 1087 1153 1171 1201 1217 1297 1409 1433 1447
1471 1499 1523 1597 1621 1669 1723 1741 1787 1823
1847 1913 2027 2063 2081 2099 2221 2269 2341 2351
2381 2417 2477 2549 2609 2647 2683 2719 2749 2803
2897 2909 3001 3019 3067 3109 3169 3229 3259 3299
3319 3407 3469 3517 3559 3593 3637 3733 3761 3911
- 635 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 09:11:38.57 ID:a0NWv3WS.net]
- >>607はAOJにあった島の数の問題じゃないの
そうじゃなくてもぷよぷよは大抵コレでしょ
- 636 名前：デフォルトの名無しさん [2020/01/13(月) 12:20:35.97 ID:AM9JqLhx.net]
- >>607
>>615だそうだが、既にほぼ書いてしまっていたから、完成させたのを載せる。
R
https://ideone.com/eECxW1
- 637 名前：デフォルトの名無しさん [2020/01/13(月) 14:02:08.92 ID:7B3b+WrT.net]
- >>607
Java
https://paiza.io/projects/qWcc4EhNNSHq8Jono0wgNg
回答は一応用意してました
みんなUnionFind大好きだと思ったんだけど
- 638 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 18:55:55.99 ID:7n+Qr/32.net]
- >>566
>>569
8087は、第3の実数フォーマット、一時実数を許している点でユニークである。
このフォーマットは、(符号が1ビット)、指数が15ビットで、有効数字が64ビットである。
このフォーマットで格納されている数値は、拡張精度数と言われている。
単精度および倍精度実数と異なり、一時実数は入力および出力値を表わすことを意図していない。
････(中略)･････
それでは、何故80ビットではなく4倍精度すなわち128ビットを一時実数に使わなかったのか。
1つの理由は、4倍精度は少なくとも性能(速度)が半分になることである。
他の理由は、4倍精度を基本フォーマットとして用いると、中間結果のためにより長いフォーマットが必要となることである。
(後略)
・出典
J.F.パーマー・S.P.モース(著)「8087入門」啓学出版 (1985/Feb) 御牧 義 (訳)
- 639 名前：2900円
第2章 データフォーマット、p.19-20 [] - [ここ壊れてます]
- 640 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 19:02:27.52 ID:7n+Qr/32.net]
- John F. Palmer, Ph.D. は8087の設計者、
Stephen P. Morse, Ph.D. は8086の設計者だそうな。
- 641 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 19:38:23.04 ID:cBNIohlK.net]
- x87で遊んでた頃は
将来は4倍精度とか8倍精度とかが当たり前になると思ってたけど
まさか単精度や半精度の時代になるとは
- 642 名前：デフォルトの名無しさん mailto:sage [2020/01/14(火) 21:06:38.50 ID:vjAz2zAO.net]
- >>581
AVX2 & FMA で作ってみました
https://ideone.com/j44H0T
範囲チェックはしてません
- 643 名前：デフォルトの名無しさん mailto:sage [2020/01/14(火) 21:13:25.69 ID:vjAz2zAO.net]
- 20命令で4個のdoubleのexpm1の計算が出来ます
8パラにしてレイテンシを隠蔽すれば
1個あたり2.5クロックくらい
- 644 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 12:05:09.83 ID:z1LU+PP1.net]
- 将来、行列演算もFPU化されると、逆行列の桁落ちが問題になるだろうな････
それを見越して、入出力は64bitのまま内部演算だけ80bitにしたんぢゃね？
- 645 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 13:12:03.91 ID:BnAK3ul/.net]
- 思想がどんなに優れてても使われなきゃしょうがない
レジスタが8個しか無いから内部だけ80bitでもほとんど精度改善にならないし
メモリに80bit保存するのも使いにくい
互換性の問題もあって
コンパイラや最適化で値がかわってしまうのも都合が悪い
だから演算にx87命令を使ったとしても内部64bit精度がデフォ
x87全盛期に作られたSuperPIも64bit精度の演算を使ってる
80bit精度で計算すれば速度アップ出来るにも関わらず
- 646 名前：デフォルトの名無しさん [2020/01/15(水) 17:38:16 ID:xp2qVCg5.net]
- >>589 Ruby
require 'prime'
a=Prime.take(100)
p ([0]+Prime.take(a.last)).values_at(*a)
- 647 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 21:04:20.76 ID:/kpg6gtq.net]
- お題:
9つの物がある。
重さが20以下で価値の合計が最大になる組み合わせを求めなさい。
(Part7から再出)
[重さ, 価値]
[
[3, 5],
[5, 6],
[6, 3],
[3, 5],
[5, 9],
[2, 1],
[7, 5],
[4, 6],
[8, 3],
]
- 648 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 21:18:06.99 ID:1ZW9vAE3.net]
- ナップサック問題か
- 649 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 21:27:46 ID:woCrNz65.net]
- 重さ < 価値
となる物を集めると丁度重さが20だから
これが解
- 650 名前：デフォルトの名無しさん [2020/01/16(Thu) 21:02:25 ID:ZS18thyn.net]
- 【お題】以下の31個の数の下6桁を求めよ。
20200101の1, 2, 3, ..., 20200101乗の総和
20200102の1, 2, 3, ..., 20200102乗の総和
20200103の1, 2, 3, ..., 20200103乗の総和
:
20200131の1, 2, 3, ..., 20200131乗の総和
- 651 名前：デフォルトの名無しさん mailto:sage [2020/01/17(金) 06:54:23.06 ID:bFwt3c1k.net]
- >>626
逆行列の計算は避けた方がいいってえらいひとがゆってた
ttps://www.kyoritsu-pub.co.jp/bookdetail/9784320013438
- 652 名前：デフォルトの名無しさん [2020/01/17(金) 12:14:19.25 ID:onsz9c/m.net]
- >>629
16, 7: 0 0 1 0 0 1 0 0 1
17, 9: 0 0 0 0 0 1 1 0 1
18, 26: 1 1 0 1 1 1 0 0 0
19, 27: 1 1 0 0 1 1 0 1 0
20, 31: 1 1 0 1 1 0 0 1 0
- 653 名前：デフォルトの名無しさん mailto:sage [2020/01/17(金) 18:26:22.50 ID:KcAYJrW8.net]
- >>632
C++
https://ideone.com/A0BeSs
- 654 名前：デフォルトの名無しさん [2020/01/17(金) 20:33:32 ID:VgNyCBhj.net]
- >>635
正解。
Rによる2種類の解答例
(1) https://ideone.com/7B7IhY
(2) https://ideone.com/Y8jx8o
(1)は等比数列の総和の公式を利用しているので分かりやすいが、途中計算の最大値が
(20200130 * 1000000 - 1) ^ 2 ≒ 2 ^ 88.4 になるかも知れず、64ビット整数の
範囲に収まらないため、Cでは手軽に書けない。Rでは多倍長整数パッケージgmpを
使って書ける。
(2)は部分和をちまちま足していく方式で、途中計算の最大値が (1000000 - 1) ^ 2
≒ 2 ^ 39.9 で済むため、Cでも64ビット整数で計算できる。Rでも多倍長計算が必要な
(1)より速い (正味の実行時間が(1)は0.016秒、(2)は0.004秒)。
- 655 名前：デフォルトの名無しさん mailto:sage [2020/01/17(金) 21:12:46 ID:KcAYJrW8.net]
- お題
f(n) = n^1 + n^2 + ... + n^n の時
f^20200117 (20200117) の下9桁を求めよ
※ f^n (x) = f(f(f(....f(x)))...) 【fがn個】
- 656 名前：デフォルトの名無しさん [2020/01/18(土) 00:45:25.84 ID:meR2Lc88.net]
- >>629
Java
https://paiza.io/projects/Qbx2Q0ZIlXetvF51BwoF_w
- 657 名前：デフォルトの名無しさん [2020/01/18(土) 05:21:08 ID:et7QELfi.net]
- >>589 octave
a=primes(5000);
a(a(1:100))
- 658 名前：デフォルトの名無しさん [2020/01/18(土) 22:25:47 ID:uIn7pF9I.net]
- >>637
https://ideone.com/WvoPeq
Rでは時間が掛かりすぎるのでコンパイラ言語を使うが、C/C++だと出題者と同じで
つまらないから、Fortranで書いてみた。nが奇数の場合にしか求められないし、
合っているかどうか分からない。
- 659 名前：デフォルトの名無しさん mailto:sage [2020/01/18(土) 23:02:35 ID:/9q/+LXn.net]
- >>640
正解
C++
https://ideone.com/09pUlf
312500はどうやって求めました？
- 660 名前：デフォルトの名無しさん mailto:sage [2020/01/18(土) 23:12:37.20 ID:/9q/+LXn.net]
- >>641だと偶数でもOKです
- 661 名前：デフォルトの名無しさん [2020/01/18(土) 23:31:05.83 ID:uIn7pF9I.net]
- >>641
時間は掛かるがRで下9桁の値を順々にいくつか求めて配列rに記録してから、
プロンプトで any(duplicated(r)) や which(duplicated(r)) と入力して
周期性を見つけただけ。理論的な根拠はない。
- 662 名前：デフォルトの名無しさん mailto:sage [2020/01/18(土) 23:34:38.18 ID:/9q/+LXn.net]
- thx
周期が既知なら
mod(20200117, 312500) 回だけで済むのでは？
- 663 名前：デフォルトの名無しさん [2020/01/18(土) 23:45:49 ID:uIn7pF9I.net]
- >>644
まあそうだが、それではあまりにもマジックナンバーすぎるので、周期が本当に
312500であるかチェックするコードを31行目に念のため入れた。周期性が
確認できなければ、STOP Errorと表示してプログラムを中断する。
- 664 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 00:38:02.65 ID:msO9WicL.net]
- 【お題】
無向グラフGが入力として与えられ、Gがサイクルを持てば、
Gの中の最小サイクルの経路とそのコストを出力するプログラムをかけ
＊条件
・グラフサイズ(頂点数)は10頂点程度(任意でよい)
・各辺の重みはランダムとする
・入力は隣接行列表現とする
- 665 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 08:33:00.83 ID:r8dbXOf2.net]
- お題: 文字列aの真ん中に文字列bを挿入する関数chopを定義しなさい
- 666 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 08:40:19 ID:dOSa/ZjO.net]
- >>647 Ruby
def chop(str); str.tap{|s| s[s.size / 2, 0] = ?b}; end
puts chop('hogefuga') # => hogebfuga
- 667 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 08:42:44 ID:dOSa/ZjO.net]
- 問題誤読してた
def chop(a, b)
a.tap{|s| s[s.size / 2, 0] = b}
end
puts chop('hogehoge', 'HOGE') # => hogeHOGEhoge
- 668 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 10:33:55 ID:9NcxNk8h.net]
- お題 (>>346)
1〜1000 の整数の内、3の倍数または5の倍数であるものだけを選んで、その合計を求めよ。
- 669 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 10:37:40 ID:9NcxNk8h.net]
- 3の倍数
[1000/3] = 333個
S(3) = 3+6+9+････+999 = 333 * (3+999)/2 = 166833,
5の倍数
[1000/5] = 200個
S(5) = 5+10+15+････+1000 = 200 * (5+1000)/2 = 100500,
3の倍数かつ5の倍数 （15の倍数）
[1000/15] = 66個
S(15) = 15+30+45+････+990 = 66
- 670 名前： * (15+990)/2 = 33165,
∴ S(3) ＋ S(5) - S(15) = 100500 + 166833 - 33165 = 234168. [] - [ここ壊れてます]
- 671 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 13:04:07.51 ID:CR4NZ4aH.net]
- 15の倍数含めないんじゃないの？
https://paiza.io/projects/EeMOFbswluii2y-uytbeqA
- 672 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 18:23:22 ID:t01ujcAX.net]
- >>629 Perl5
use List::Util qw{max};
$W = 20;
$n = @wv = ([3, 5],[5, 6],[6, 3],[3, 5],[5, 9],[2, 1],[7, 5],[4, 6],[8, 3]);
@w = map{$$_[0]} @wv;
@v = map{$$_[1]} @wv;
$wt[$n][$_] = 0 for 0..$W;
for ($i = $n - 1; $i >= 0; $i--) {
for $j (0..$W) {
$ws = $wt[$i + 1][$j];
$ws = max($wt[$i + 1][$j - $w[$i]] + $v[$i], $ws) if $j >= $w[$i];
$wt[$i][$j] = $ws;
}
}
print "価値合計最大: $wt[0][$W]\n";
$j = $W;
for $i (0..$n-1) {
$ws = $wt[$i][$j];
if ($wt[$i + 1][$j] != $ws) {
print "[$w[$i], $v[$i]] ";
$ws -= $v[$i];
for (; 0 <= $j; $j--) { last if $wt[$i + 1][$j] == $ws; }
}
}
$ perl 16_629_nsp_dp.pl
価値合計最大: 31
[3, 5]
[5, 6]
[3, 5]
[5, 9]
[4, 6]
- 673 名前：デフォルトの名無しさん [2020/01/19(日) 20:22:32 ID:MJwntUeD.net]
- >>652
PowerShellには論理XOR演算子があるので簡潔に書けるな。
(1..1000 |? {$_ % 3 -xor $_ % 5} | measure -sum).sum
-- 実行結果 --
201003
- 674 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 21:28:24 ID:RfLx+x9F.net]
- >>652
なぜそう思った？
- 675 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 21:32:35 ID:CR4NZ4aH.net]
- >>655
だけ と強調してたから15を含めない意図があったのかと思った
- 676 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 21:35:30 ID:RrNuywTU.net]
- 「3の倍数または5の倍数であるものだけ」という文言をそう理解するのは宇宙でお前だけだと思う
- 677 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 22:24:05 ID:RfLx+x9F.net]
- 妊娠してるか体が不自由な人だけ使ってください
- 678 名前：デフォルトの名無しさん mailto:sage [2020/01/19(日) 23:13:47.04 ID:xkwic4JQ.net]
- >>658
妊娠してる障害者はすわれないやんけ！
- 679 名前：デフォルトの名無しさん [2020/01/20(月) 07:26:08 ID:MadDRkAO.net]
- 日本語の選択が排他的かどうかは状況しだいだから難しいところだと思うけどね
レストランで「コーヒーか紅茶が付きます」と言えばどちらか一方でしょ
ケースバイケース
こう解釈したらこういうプログラムになるというふうに思考を広げることはできるっしょ
- 680 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 08:18:28 ID:ItoFGwWk.net]
- それは選ぶ条件ではなく、選ぶ個数の問題
>>346は全て選ぶのが暗黙の了解
>>660は選ぶのが1個であるのが暗黙の了解
>>346も全てとは書いてないから
1個選ぶのか、任意の個数選ぶのか、全ての選び方の場合を求めるのか、などが考えられるのかも
誤解の可能性があるなら｢全て選ぶ｣と書かないとね
- 681 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 10:07:25.78 ID:DzK/Jy6Q.net]
- ０個選んで答えは０
コンピュータ言語読み書きしてたらこういう
発想が自然に感じられるが
日常言語の世界ではナンセンス杉
- 682 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 14:10:00.56 ID:gT/yNp+O.net]
- >651 のようにした
common lisp
(loop for i from 1 to 1000 when (= (* (mod i 3) (mod i 5)) 0) sum i)
234168
- 683 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 15:41:16.18 ID:/G9h8LiI.net]
- >>651 Ruby
def si(n,m); n.step(m,n).inject(:+); end
p n3 = si( 3, 1000 ) #=> 166833
p n5 = si( 5, 1000 ) #=> 100500
p n15 = si( 15, 1000 ) #=> 33165
p n3 + n5 - 2 * n15 #=> 201003
- 684 名前：デフォルトの名無しさん [2020/01/20(月) 21:4
]
- [ここ壊れてます]
- 685 名前：6:25.06 ID:eV9B9Eib.net mailto: >>629
Rで全探索
https://ideone.com/XDwD7C
物が9個しかないので512通りの組み合わせを全探索してもすぐ終わるし、
上のプログラムの2番目の問題のように、合計価値が最大となる組み合わせが
複数ある場合でもすべて挙げられるし、重さが小数や大きな整数の場合でも
同様に解けるから、全探索が時間的に可能なら全探索の方が良いんじゃないか? [] - [ここ壊れてます]
- 686 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 22:42:22 ID:vyZs8dgX.net]
- >>665
問題の条件によって適した解法が変わる。
たとえば個数が高々十数個程度であっても、
個々の重さや価値の範囲が広く、詰め込める荷物のキャパが大きいとか、
整数でない場合は、動的計画法だと解けないが、ナイーブな解法なら解ける。
逆に個数が大きくて、個々の重さや価値、キャパがそれほど大きくない整数だと、
ナイーブな解法では時間がかかりすぎて解けないが、
動的計画法だと短時間で解ける。
条件によって適した解法を選択する。
>>653 は動的計画法の復習と最適解に至る経路を逆にたどる復習のつもりで書いのよん。
- 687 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 23:01:52 ID:kEPXORSp.net]
- 問題に適した解法なら>>631が最強
- 688 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 23:10:30 ID:vyZs8dgX.net]
- (´･ω･`)「・・・・・」
- 689 名前：デフォルトの名無しさん [2020/01/21(火) 14:48:52 ID:/dftakVp.net]
- >>650
Kotlin script
KotlinもBooleanのxor使えたよ。こういう場合は優先順位の問題で括弧が必要になるけどね。
println((1..1000).filter { (it % 3 == 0) xor (it % 5 == 0) }.sum())
- 690 名前：デフォルトの名無しさん mailto:age [2020/01/21(火) 16:44:59 ID:TMO7rdDn.net]
- !=でいんじゃ、、、
- 691 名前：デフォルトの名無しさん mailto:sage [2020/01/21(火) 21:56:37.25 ID:q8k+mYw1.net]
- ["A -> B" , "A -> D", "B -> E", "D -> E"]
を
A
B
E
D
E
このようにツリー状に表現する際に計算量が少ない書き出し方ってどうなりますか。言語問いません。
- 692 名前：デフォルトの名無しさん mailto:sage [2020/01/21(火) 21:57:01.85 ID:q8k+mYw1.net]
- スペースきえた…
- 693 名前：デフォルトの名無しさん mailto:sage [2020/01/21(火) 21:58:36.68 ID:5H3OckH4.net]
- D -> B のようなループできるかもね
- 694 名前：デフォルトの名無しさん [2020/01/22(水) 03:28:09 ID:HNO/xGn/.net]
- >>670
それを言っちゃあおしめえよ
- 695 名前：デフォルトの名無しさん mailto:sage [2020/01/22(水) 10:29:09 ID:Oj6zQLXh.net]
- >>671
データ構造がツリーじゃないのにツリー形式で表示するのは効率悪くない？
同じデータを何度も表示しちゃう
- 696 名前：デフォルトの名無しさん [2020/01/22(水) 11:00:25 ID:8VKZzbv1.net]
- >>671
dot
- 697 名前：デフォルトの名無しさん mailto:sage [2020/01/22(水) 19:16:47 ID:0ayd3B3Q.net]
- お題
>>671 において
入力文字列が20個以内で出力の行数が最大となる
入力文字列(を1個)を求めよ
- 698 名前：デフォルトの名無しさん mailto:sage [2020/01/22(水) 19:50:15 ID:k+w34kNu.net]
- ["A -> B" , "B -> A]
これで循環参照のチェックいれるコードがない再帰っぽい感じなら無限に出力だ
- 699 名前：デフォルトの名無しさん mailto:sage [2020/01/22(水) 19:55:17 ID:F1N+c+gr.net]
- 閉路と多重辺は無しで
辺の無い点も表現出来ないので無し
- 700 名前：デフォルトの名無しさん [2020/01/22(水) 20:19:19 ID:3jquT0bn.net]
- >>677
20個ならループしない限りは内容が何だろうが20行にしかならないのでは？
- 701 名前：デフォルトの名無しさん mailto:sage [2020/01/22(水) 20:23:02 ID:1i745hKi.net]
- 最大は21行だよ
- 702 名前：デフォルトの名無しさん [2020/01/22(水) 20:40:06 ID:3jquT0bn.net]
- あー。そうか。21だね。
- 703 名前：デフォルトの名無しさん mailto:sage [2020/01/22(水) 20:43:02 ID:F1N+c+gr.net]
- >>671に "E -> C" を加えると？
- 704 名前：デフォルトの名無しさん [2020/01/22(水) 21:13:37 ID:pXdYyKNl.net]
- >>671
Java
https://paiza.io/projects/zVLPWkZWdFIgv8aDQjIn0Q
- 705 名前：デフォルトの名無しさん [2020/01/23(Thu) 01:12:44 ID:LqZxq9h8.net]
- >>683
分岐か。そうすれば増えるね。
- 706 名前：デフォルトの名無しさん mailto:sage [2020/01/23(Thu) 18:13:14 ID:AdSJ3UeH.net]
- [] 0行
["A -> B"] 2行
["A -> C", "B -> C"] 4行
["A -> D", "B -> D", "C -> D"] 6行
["A -> D", "B -> D", "C -> D", "D -> E"] 9行
- 707 名前：デフォルトの名無しさん mailto:sage [2020/01/23(Thu) 18:45:00 ID:AdSJ3UeH.net]
- n≧12 の時、以下を四捨五入した行数になるかな
偶数
4 * exp(n*0.24060591252980172375)
奇数
4.0137530980362538594 * exp(n*0.24060591252980172375)
- 708 名前：デフォルトの名無しさん mailto:sage [2020/01/24(金) 23:55:14 ID:qxZ+oily.net]
- >>671 Perl5 (goto 関数を使っていますが、perl5ではこれはcontinuationです)
use feature qw{current_sub signatures};
no warnings 'experimental::signatures';
@sx = (A => B, A => D, B => E, D => E);
sub {
if (@_) {
($a, $b) = (shift, shift);
push @lx, $a unless $h{$a};
push @{$h{$a}}, $b;
$r{$b}{$a} = 1;
goto __SUB__;
}
}->(@sx);
@ax = grep{! $r{$_}} @lx;
sub ($a, $d) {
print "$d$a\n";
__SUB__->($b, "_$d") while $b = shift @{$h{$a}};
}->($_, '') for @ax;
実行結果
$ perl 16_671.pl
A
_B
__E
_D
__E
- 709 名前：デフォルトの名無しさん mailto:sage [2020/01/25(土) 02:34:16 ID:XZtTnZKV.net]
- >>646
サンプルデータも考えて、回答も作れと言われると
めんどくさすぎてスルーされるんじゃまいか
- 710 名前：デフォルトの名無しさん mailto:sage [2020/01/25(土) 02:36:37 ID:XZtTnZKV.net]
- つか、無向グラフの最小サイクル検出って
いいｱﾙｺﾞﾘｽﾞﾑあったっけ
|
 |
