データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
11: 2020/11/08(日)16:03 ID:hnEKBOnE(2/2) AAS
自明なので判定するまでもないが。
12: 2020/11/08(日)16:28 ID:BBDku6LQ(1) AAS
データ構造とアルゴリズムって人気ないの？
13(1): 2020/11/29(日)20:21 ID:rAnHdnpn(1) AAS
これの 9.3. Solution が何故これで正解が導き出せるのか理解できないんですが
もう少しどなたか詳細に解決して頂けないでしょうか。
外部ﾘﾝｸ[pdf]:codility.com
14(1): 2020/11/29(日)21:27 ID:exnO589A(1) AAS
dpテーブル作って考えたほうがわかりやすいと思います
外部ﾘﾝｸ[pdf]:www.nii.ac.jp
これの19ページとか
15: 2020/11/29(日)21:37 ID:M8xgBTYt(1/3) AAS
そのPDFファイルに書いてあることの繰り返しになりますが，以下が成り立つからです．
max_ending == インデックスがiで終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
であると仮定する．
max_ending = max(0, max_ending+a)
を実行した後，
max_ending == インデックスがi+1で終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
が成り立つ．
16(1): 2020/11/29(日)22:05 ID:M8xgBTYt(2/3) AAS
5, -7, 3, 5, -2, 4, -1
インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceは，3, 5, -2, 4です．
インデックスが6で終わるsliceまたは空のsliceのうち，その和が最大であるsliceをSとする．
Sは何になるか？
3 + 5 - 2 + 4 - 1 = 9 > 0なので，Sは空のsliceではありません．
Sは，例えば，5, -2, 4, -1ではありません．もし，Sが，5, -2, 4, -1であるとすると，
5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1
したがって，
5 - 2 + 4 > 3 + 5 - 2 + 4
となってしまい，インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceが，3, 5, -2, 4ではなく，
5, -2, 4であるということになってしまうからです．
Sは，例えば，-7, 3, 5, -2, 4, -1ではありません．もし，Sが，-7, 3, 5, -2, 4, -1であるとすると，
-7 + 3 + 5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1
したがって，
-7 + 3 + 5 - 2 + 4 > 3 + 5 - 2 + 4
となってしまい，インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceが，3, 5, -2, 4ではなく，
-7, 3, 5, -2, 4, -1であるということになってしまうからです．
17: 2020/11/29(日)23:01 ID:0fgKV2B3(1) AAS
>>13
これ最初から足していってマイナスになったらリセットしてまた足し始める
それまでの最大を超えたら最大値を更新するってだけじゃないの
マイナスになったらそれを足し続けても得しないって訳だから
18: 2020/11/29(日)23:10 ID:M8xgBTYt(3/3) AAS
そうですね．
足していってマイナスにならなければ，無いよりはましだから，捨てずにsliceに含め続けるということですね．
19: (u＿・y) 2020/11/30(月)17:46 ID:nGWGFXsH(1) AAS
そうですよ。マイナスでさえなければ、いないよりはマシだから、あなたも雇われ続けているんです。
さらに2 + 2は必ずしも4ではなく、2 +2 = 80にもなるんです。
20: 2020/12/03(木)18:30 ID:Fq1nYucp(1) AAS
>>14
分離定理初めて知った、しゅごい
まあ算術でとかループでとか、ジャンプと変数があればとか、λさえあれば…とか似たような定理は見掛けたけど、は低レベル過ぎて指針にならんからな
これらでできないかひとしきり考えてみることにする
(もちろんちゃんと使える演算子は使います)
21: 2020/12/22(火)15:07 ID:h5DFCbD/(1) AAS
近似アルゴリズムの本に
極大マッチングは，単に辺を一つずつ選んでいきながら，選んだ辺の両端点とそれらに接続するすべての辺を除いて辺がなくなるまで繰り返すことで得られる
とあり，nを頂点の数，mを辺の数としたとき，計算時間がO(n + m)と書いてあるのですが
nはどこから来たのでしょうか
両方に点が残っている辺を見ていけばいいのでO(m)でできると思うのですが
22: [age] 2020/12/31(木)21:02 ID:pjMyqahK(1) AAS
ArrayListって実装的にはただの可変長配列ですか？
23: 2021/01/01(金)06:52 ID:L8CQYPdE(1) AAS
>>16
これは、最大連続区間か？
24: 2021/02/27(土)15:27 ID:cGuo4IiQ(1/2) AAS
ウィキペディアの焼きなまし法
外部ﾘﾝｸ:ja.wikipedia.org
にある擬似コードの
if nextE < bestE then
の部分はもしかして間違ってたりします？
この評価だとnextEが悪化するたびbestが更新されるように見えますが
25: 2021/02/27(土)16:54 ID:Hg2wHc/X(1) AAS
小さい方が良いでしょ
26: 2021/02/27(土)16:54 ID:q6FQGtjh(1) AAS
値が小さい方が望ましい
27: 2021/02/27(土)17:10 ID:cGuo4IiQ(2/2) AAS
よく読んでなかったすまんかった
28: 2021/03/08(月)16:54 ID:H4OoIpXQ(1) AAS
焼きなましに例えるんだからEnergyのEだろうね
線形計画法が流行ってた時代はとりあえず目標関数は最大化するものとしてた風潮があった(LPでは双対問題と厳密に等価)
シュミレーション分野、最近の機械学習の流行りでとりあえずコスト関数を最小化する雰囲気
LPじゃないんで同じ点で極値を与える関数にも良し悪しがある点には気を付けねば
実数関数なら符号の反転と、並進に依らないアルゴリズムであれば並進を加えたもののみ等価
29(1): 2021/03/17(水)19:38 ID:DuV9YnX6(1) AAS
初歩的な質問かもしれず、恐縮ですがお願いいたします。
i Phoneを使って、端末が始点から終点まで移動した角度をx,y,z（オイラー角）で取得したいと考えています。
最初は、始点と終点の端末の位置をオイラー角で取得し、その差分を出してみたのですが、ジンバルロックによりpitchの値を正確に取得できませんでした。
ジンバルロックを回避するためクォータニオンを使うといいようなのですが、クォータニオンを使って目的の値を算出する方法が分からない状態です。
もし分かる方がおられましたら、ご助言いただると幸いです。
よろしくお願いします。
30: 2021/05/19(水)16:18 ID:7NWiu4qI(1) AAS
Minimum Mean Cycleでこのスライドを見ているのですが
3ページでmaxをとっているのに正しい答えがでる理由ってなんでですか？
外部ﾘﾝｸ[pdf]:www.columbia.edu
(d^n(v) - d^k(v)) / (n - k)はｖからスタートしたときのMean Cycleですよね
d^k(v)が無限の場合を避けるためにmaxをとっていると思うのですが，なぜ正しい答えになるのでしょうか
31: 2021/05/22(土)02:18 ID:/00w7bM8(1) AAS
>>29
取り敢えず理解はほっといて動けばいいのなら、ウィキペにでも公式載ってたと思うよ
32: 2021/10/03(日)17:59 ID:nkudyinT(1) AAS
幅優先探索の計算量がO(N)ではなくO(N + E)なのはなぜ？
Nは頂点の数、Eは辺の数です。
33: 2021/10/03(日)20:36 ID:KyHKDHW1(1) AAS
辺の数だけ処理が増えるから
頂点の数を同じにして辺の数が異なる2つのグラフを比較してみればわかる
34: 2021/10/03(日)22:55 ID:45cLxSS6(1) AAS
モートン順序によって当たり判定を一瞬で計算するというのがありました
あれ特定の境目の上にオブジェクトがあるとすべてのオブジェクトとの衝突判定が発生するんですが
世の中のゲームってそんなふうにやってるんですか
35: 2021/10/04(月)18:40 ID:N2yAdGNd(1) AAS
計算量がO(V + E)であるの定義は何ですか？
36: 2021/10/04(月)22:35 ID:qkBPKVDO(1) AAS
それは計算量の定義をきいているのか？
37(1): 2021/10/05(火)00:11 ID:wQtjKuKa(1/2) AAS
そのアルゴリズムの計算時間を f(n) とし、オーダーが O(g(n)) と表記される場合、定数cがあって、n がある程度大きくなれば常に f(n) <= c * g(n) が成り立つ。言い方を変えれば計算時間は最悪のケースでも c * g(n) を超えない
g(n) が N (Nの1次式) なら計算時間は c * N を超えないし
g(n) が N^2 (2次式) なら c * N^2 を超えない
c はマシンのスペックや環境で変わるので具体的な数値は追求しない
Nの入力サイズが10倍、100倍、...、1万倍となったときに計算時間がおおよそどのくらいのスピードで増えるか見積もれれば良い
O(N) なら10倍、100倍、...、1万倍
O(N^2) なら100倍、1万倍、...、1億倍..
詳しくはアルゴリズムの教科書か
外部ﾘﾝｸ:ja.wikipedia.orgランダウの記号
38(1): 2021/10/05(火)02:13 ID:3IOuHtiP(1/2) AAS
>>37
ありがとうございます。
ですが、O(V + E)の中に書かれている式であるV + Eは2変数の関数です。それでも1変数の場合と同じ定義でいいんですか？
39(1): 2021/10/05(火)03:31 ID:wQtjKuKa(2/2) AAS
>>38
定義は同じ
V個の頂点はそれぞれ1回キューに入れられて1回キューから取り出される
E本の辺はある頂点から隣接する次の頂点を見つけるのに1度処理されるだけ
合わせてc0 * E + c1 * V の手間がかかるが、c0, c1 の大きい方を c として c0 * E + c1 * V <= c (E+V)、これは最悪でも計算量は c (E+V) を超えないことを意味し、E+V の部分が g(E+V) となる
40: 2021/10/05(火)08:50 ID:3IOuHtiP(2/2) AAS
>>39
なるほど。ありがとうございました。
上下前次1-新書関写板覧索設栞歴
あと 65 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.019s