VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
419(6): ピッコロ ◆YAZTByPXwc6o 2019/05/17(金)22:06 ID:0ADdj9iV(1)調 AAS
>>418
じゃあこれ解いて
プログラミングのお題スレ Part13
2chｽﾚ:tech
| 920+8 ：デフォルトの名無しさん [↓] ：2019/05/16(木) 20:28:13.91 ID:3sIrlJF4
| お題
| 整数の数列が与えられるので、各値の大小関係を変えないように値をなるべく小さくせよ
| ただし1番小さい要素は1にすること
| 入力
| -6 3 9 5 3 -7
| 出力
| 2 3 5 4 3 1
420(1): 2019/05/17(金)22:18 ID:5uXz4WgO(2/6)調 AAS
>>419
間接参照でソートしてゴニョゴニョしてみてね系の問題。ただそれだけ。
クレクレ君に答えはやらねーよ。
421: 2019/05/17(金)22:32 ID:5uXz4WgO(3/6)調 AAS
>>419
調べたらお前自身のお題ってアホか。
「ちゃんと最悪の場合を見てないけどO(n^2)でもいいなら高校生でも解けるし高校生なら許す」
「でも普通はO(n)でいいよね」
「ピッコロは高校生じゃないよね」
「宿題出すな」
はいおしまい。
422: 2019/05/17(金)22:39 ID:8HaYh50j(1)調 AAS
>>419
自分じゃ大したお題を思いついたつもりなんだろうけど、実際はただの↓なんだよな
この程度でよく他人様に授業を始めますとか言えたもんだよ
934 名前：デフォルトの名無しさん[sage] 投稿日：2019/05/17(金) 12:14:50.20 ID:8VLhbVxR
>>920
は、ランク付けの問題だろ
462(2): ピッコロ ◆YAZTByPXwc6o 2019/05/19(日)02:10 ID:iZGlVtrY(3/7)調 AAS
>>456
>>419の問題はソートがどうしようもないんだよね
ソートがあるから計算量の限界はn*log(n)になるかと
それはそれとして計算量はデータ量が増加したときに
計算資源の消費量がこういう比率で増加しますってものだから
あくまでもデータ量とセットで考えてこそ意味があるものだよ
一般的に計算量がよいアルゴリズムはデータ量が少ないときに時間がかかる傾向があって
たとえばクイックソートの平均計算量はn*log(n)で挿入ソートの計算量はn^2だけれども
件数が少ないときは挿入ソートの方が速い
各種標準ライブラリのソートでも要素数が少ないときは挿入ソートが使われてて
挿入ソートを使うときの閾値はライブラリによってまちまち
.NETは16以下
https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/ArraySortHelper.cs
Javaは46以下
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/DualPivotQuicksort.java
FreeBSDは6以下
挿入ソートじゃなくてノームソートになってるけどまあ似たようなものだしまあいっかということで
https://github.com/freebsd/freebsd/blob/master/lib/libc/stdlib/qsort.c
Rubyはソースをきちんと追えなくて不確かだけれども
FreeBSDのqsortを使ってるっぽい気がする
今回の問題の要素数は6なので挿入ソートが最適かと
計算量はn^2で良い
474(1): ピッコロ ◆YAZTByPXwc6o 2019/05/20(月)00:00 ID:9bk38djr(1)調 AAS
>>419の問題をn log nで解きたいんだということなら
それはそれで意味のあることだと思うし大事な考えだから
ぜひよろしくお願いいたします
ピッコロ待ってます
479(1): ピッコロ ◆YAZTByPXwc6o 2019/05/25(土)16:25 ID:BD9fwrcm(1)調 AAS
>>419
これ解けた人いますか？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.041s