くだらないアルゴリズムを考えるスレ

1デフォルトの名無しさん2009/06/19(金) 23:03:59
居眠りをチェックするアルゴリズム

キーボードからの入力値が急に"ddddddddddddddddddddddd"とかになったら居眠り

271デフォルトの名無しさん2015/10/25(日) 20:07:17.57ID:IGihUR6P
Min・Maxは、最小値・最大値のどちらかしかわからない

同じ理屈で、中央値しかわからないものも作れるだろう。
常に前の値が、最小値・最大値から何個目かを記憶すれば?

272デフォルトの名無しさん2015/10/25(日) 21:49:41.45ID:UpnA5iMK
いやまじでソートいらないだろ?

273デフォルトの名無しさん2015/10/26(月) 11:38:20.35ID:SLPNlhiK
>>270
選択アルゴリズムで検索

274デフォルトの名無しさん2015/10/26(月) 16:45:31.83ID:7G3hAEBt
混雑している駐車場でどのくらいの速度で何周すれば入り口により近い場所に駐めることができるかを求めるアルゴリズム

275 ◆QZaw55cn4c 2015/10/27(火) 08:39:10.52ID:5zN18SUc
>>271
それはない。
最小から2番目の値は、最小値が判明したのちに始めてわかること

276デフォルトの名無しさん2015/10/29(木) 17:17:51.25ID:U/OAmJvP
>>270
ソートするより時間がかかりそうな方法だけど
適当に数字を拾って、そいつと他の数字を比べて
「大きい」判定と「小さい」判定がちょうど同じになればそいつが中央値だと判定できるぞ
もちろん1回の試行ではまず見つからないだろうが
「1回目に試行した数より大きい(or小さい)数は中央値ではない」という絞り込みが可能だから
案外早めに中央値が見つかる可能性はある

277デフォルトの名無しさん2015/10/29(木) 21:17:24.72ID:U/OAmJvP
小さい範囲でソートを使うけど高速に中央値を見つける方法を思いついた

(1)データ全体から100個ランダムに選んでそれをソートして45位と55位の値をサンプルとして設定する(A、Bと呼ぶ)

(2)AとBをそれぞれデータ全体と比較してAとBの正確な順位を割り出す
 このときAとBが中央値より上位と下位でなかった場合は(1)のサンプルの幅を広げてやり直す

(3)AとBの間の値をすべてピックアップしてソートすれば中央値を見つけられる

「概ね中央値」が見つけられれば満足なら
(1)の50位を「概ね中央値」ということにしてしまうという手もある

278デフォルトの名無しさん2015/10/30(金) 00:25:26.40ID:b1AWcwGp
>>277
時間かかるね

クイックソートのアルゴリズムを使ったらええんよ
基準値を任意に選択して、それ以下グループとそれより大きいグループに分ける
中央値のインデックスは要素サイズ/2の位置だから
基準値のインデックスと比べて中央値がどちらのグループに含まれているか判断する
該当するグループを再帰的に同じ処理をする

279デフォルトの名無しさん2015/10/30(金) 09:20:32.78ID:vEVizsPP
>>277を改善してみた

(1)データ全体から100個ランダムに選んでそれをソートして50位の値をサンプルAとして設定する

(2)Aより大きい数字と小さい数字のグループに分ける。Aの正確な順位が判明する

(3)Aが全体の上位50%未満だったなら、(1)の51位をサンプルBとして(2)のAより大きかったグループと比較。Bより大きい・小さいグループを作る
 Bの正確な順位が判明する

(4)Bが全体の上位50%オーバーだったならBより小さいグループをソートすれば中央値が見つかる
 Bが全体の上位50%未満だったなら、(1)の52位をサンプルにしてやり直し

280デフォルトの名無しさん2015/10/30(金) 12:31:25.64ID:vEVizsPP
(1)の暫定中央値を決める方法としてこんなのを思いついた
データを81個取って、3個ずつ比較して、3個の中の中央値だけを残す
残った27個も同様にして9個、3個、1個と減らしていって、残った値を暫定中央値にする

最初はこの方法だけで中央値見つかるんじゃね?と思ったけど
数字の組み合わせによっては本当の中央値が消されてしまう模様

281デフォルトの名無しさん2015/12/31(木) 19:18:55.40ID:+ajUwyFG
どなたか、「アルゴリズムの定理」について教えていただけますでしょうか。
2ch.netの初期に流行ったらしいですが・・・
その人、最初に「全員氏ね」とか書いたらしいです

282片山博文MZ ◆T6xkBnTXz7B0 2016/01/21(木) 14:54:51.84ID:ypubXGFS
「{私,俺,僕}は{片山,伊藤}博文です。」
という文字列を展開して
「私は片山博文です。」
「私は伊藤博文です。」
「俺は片山博文です。」
「俺は伊藤博文です。」
「僕は片山博文です。」
「僕は伊藤博文です。」
という六通りの文字列を取得したい。

283デフォルトの名無しさん2016/03/03(木) 16:44:08.25ID:VYzcKEWT
ネトゲなんかでユーザー全体の使用頻度が高いキャラほど弱体化するようにしたら
運営があれこれいじらなくても勝手に最適なゲームバランスになったりしないかな

284デフォルトの名無しさん2016/03/05(土) 00:32:39.75ID:kDGbe/9t
>>283
どうだろうね
よくあるシステムで職業+選択型スキルってのがあるよね
職業に特徴づけしてスキルはその特徴を拡張するアタッチメント
このゲームシステムって特化の特化だから破綻しやすいって思うんだよね
複雑化した格ゲーがバランス取りにくいのに似ている

職業なしの調整可能なパラメータ型スキルだったら
自動的にバランスを取りやすいと思う
初期MMOのUOとか何度も調整が入ったけど
基軸のゲームシステムの完成度が高かったから、それほど破綻した感じじゃなかった

285デフォルトの名無しさん2016/03/07(月) 22:16:07.92ID:TykniRs6
>>283
ゲームバランスは保たれるかもしれないが、キャラ育成に魅力がなくなりそうだし、ユーザーが付かないんじゃね。

286デフォルトの名無しさん2016/03/23(水) 00:26:46.89ID:WABTO3x4
最近複雑というか色々増えて面倒なif分岐を分かりやすく取りまとめる方法として
分岐条件に2の2乗の連番を割り振ってそれ足せばどの分岐通ったかすぐ分かるというのを思い付いた

287デフォルトの名無しさん2016/04/01(金) 15:37:31.80ID:68T5b8iH
要は2進数の各ビットをそれぞれの番号に使うってこと?

288デフォルトの名無しさん2016/04/02(土) 15:20:47.12ID:DpBQG+77
日清焼きそばUFOを作るアルゴリズムを表記せよっていう宿題が出たんだけど
いったいどうしたらいいの?
(´・ω・`)

289片山博文MZ ◆T6xkBnTXz7B0 2016/04/02(土) 15:47:46.55ID:KB0q5q6i
>>288
1. 平らな場所にUFOを置く。
2. ふたを半分開ける。
(以下略、自分で考えろ)

290片山博文MZ ◆T6xkBnTXz7B0 2016/04/02(土) 18:45:46.82ID:k91t9LjX
UFOを上下逆さに置いたらまずい

291デフォルトの名無しさん2016/04/03(日) 02:56:26.78ID:MFbElsbn
>>288
まずは畑で小麦を作ります。
収穫した小麦で麺を打ちます。
打ち上がった麺を油で揚げます。
油で揚げた麺と袋に入ったソースと加薬をUFOの容器に入れ、蓋をします。

292デフォルトの名無しさん2016/04/03(日) 13:16:32.07ID:Leps+2Do
コンピューターでソートしろっていったらクイックかマージになると思うけど
見やすいように横並びにした1〜100の数字が書かれたシャッフルされたカードを人間に並び替えてもらう
この状況で人間はなんのアルゴリズム使うと思う?

293デフォルトの名無しさん2016/04/03(日) 21:38:07.74ID:pvdfhL1n
数字に偏りがないなら場所が決まってるのでn番目にnを置くを繰り返す

294デフォルトの名無しさん2016/04/03(日) 22:12:11.84ID:Leps+2Do
つまり・・・バケットソート?

295デフォルトの名無しさん2016/04/03(日) 22:39:41.90ID:cUaB0ZrS
それカードでやるとn番目に置くってのが正確にできなくて、
ここに2枚入れなきゃいけないけどはいらねえ…
とかなりそう

俺なら1-10,11-20..のように10束にまず分類して、10枚ずつ見ながら1から順番においていくかな

296デフォルトの名無しさん2016/04/04(月) 21:51:55.97ID:MTfOn2UF
>>295
コンピュータと同条件でやるならカードが束になっている前提がおかしい
カードの枚数分の箱を用意してそこに1枚ずつランダムで入っている状態でやらないと

全部のカードを一旦箱から取り出してしまったら
コンピュータが別にメモリを確保したのと同じになる
比較とスワップ回数、メモリ使用量を考慮したらクイックソートに落ち着くかもしれん

ただ、1~100のカードって前もって分かっているなら
一旦全部取り出してカード番号と同じインデックスの箱に入れていけばいいから
バケットソートになるな
これはコンピュータにやらせても同じだな
計算量はO(2n)になるのかな

297デフォルトの名無しさん2016/04/04(月) 22:03:36.71ID:MTfOn2UF
>>296
いや違った
箱の中の1つを取り出して
その数値と同じインデックスの持つ箱の中のカードとスワップ
これを箱の数だけ繰り返せばいいから
計算量はO(n)でいけるのか

298デフォルトの名無しさん2016/05/01(日) 09:54:08.01ID:q6XVMwpi
HDDとLTOのハイブリッドレコーダーというものを思いついた
HDDに番組冒頭5分を記録しておいて、ユーザーがその5分部分を見ている間にLTOから番組本編をロードすんの
HDDの利便性を維持しつつ、LTOの低コスト性も利用できるわけ

まぁ現行画質ならHDDだけで十分っぽいし、
4K時代にはテレビ放送が滅びてオンデマンドが主流になってそうだしで
たぶんこんなレコーダーは登場しないだろうけど

299デフォルトの名無しさん2016/05/27(金) 13:33:31.21ID:Jr0QFls7
step0
96 99 57 59 23 65 18 56 16 39 88 87 50 43 93 49

step1
96 99
57 59
23 65
18 56
16 39
87 88
43 50
49 93

step2
57 59 96 99
18 23 56 65
16 39 87 88
43 49 50 93

step3
18 23 56 57 59 65 96 99
16 39 43 49 50 87 88 93

step4
16 18 23 39 43 49 50 56 57 59 65 87 88 93 96 99


口で説明するのが面倒なんでソート結果でなんとなく理解してもらいたいんですけど
こういうソートって名前ついてたりしますかね?
あとクイックソートと比べて処理数はどうなんでしょうか

300デフォルトの名無しさん2016/05/27(金) 13:45:03.73ID:Jr0QFls7
自己解決
マージソートでした
速度は クイックソートと比べると、最悪計算量は少ない。ランダムなデータでは通常、クイックソートのほうが速い らしい

301デフォルトの名無しさん2016/05/28(土) 03:49:55.20ID:nOTqNgHh
>>300
いわゆる普通のクイックソートはPivotとなる値の選別如何によって最悪計算量になってしまう
実際、クイックソート殺しっていう数列が存在する
それを回避する手段、複数の値を取ってその中央値をPivotとする、がある

それぞれの良い特性を活かした複合型のソートアルゴリズムが安定していて良いね
イントロソートとか

302デフォルトの名無しさん2016/06/09(木) 23:28:57.50ID:T1E+kGV8
シャッフル・ソートを使わずにm個要素からn個の要素をランダムに取り出し小さい順に表示する方法

一巡のfor〜loop中に
n/mの確率で各数字をピックアップ
n個の要素をピックアップできた時点で終了
ピックアップが足りなかった場合はやり直し

おそらく何の意味もないアルゴリズムだけどリソースが限られる状況では使える可能性があるかも

303デフォルトの名無しさん2016/06/14(火) 00:28:17.23ID:5Fs2Kiny
言語が違う人同士がネットでやり取りする際に
あらかじめ用意されてる定型文を使えば確実な翻訳でやり取りできるわけだけど
この定型文を山ほど用意しておいてキーボードで自由な文章を入力させたあと、それに最も近い定型文を提示すれば
言語が違う人同士が完璧な翻訳でやり取りできるんじゃないだろうか

大量の定型文を用意するのに相当なコストがかかるだろうけど世界的IT企業ならなんとかできそうだし
すでにプロジェクトが始まってたりしないかな

304デフォルトの名無しさん2016/06/14(火) 01:11:29.09ID:l1XssgdC
>>303
在り来りなのは定型文としてデータベースに入っていると思うけど

翻訳のシステムってどういうのか詳しく知らないけど
多分木とかトライ木とか単語出現率とかで決定しているんじゃない?

305デフォルトの名無しさん2016/06/15(水) 09:50:10.67ID:zzAqDIgP
>>303
提示された定型文は明確に解釈できても、入力文と定型文の間に齟齬が発生する可能性があるから、普通の翻訳とあまり変わらないんじゃないか?
精度を上げるには、定型文を大量に用意して、入力文と定型文とのマッチを正確に行うことになると思う。

でも、マッチの精度を上げるってのは入力文の解析精度を上げるってことなわけで、
それが出来るなら直接翻訳しちゃえばいいじゃんてことになって、やっぱり普通の翻訳システムと同じ形に落ち着きそう…
定型文を持っておくには大きなリソースも必要だしね

306デフォルトの名無しさん2016/06/15(水) 23:15:00.29ID:/ngiWJwj
日本語を直接英語に翻訳してもユーザーにはそれが本当に伝えたい英文になっているかは判断できないけど
日本語の定型文を出してからそれの翻訳を表示するなら相手に何を伝えているか正確に知ることができるだろ
この差は結構大きいよ

あと、語弊力のない人にとっては自分の文章より定型文の方がいい文章である場合も多々あるはずだし
定型文を表示する意義はあるはずだよ

307デフォルトの名無しさん2016/06/21(火) 22:32:47.51ID:GMAXhxXB
あ、文章を入力すると自動で定型文になって相手に届くものと考えてた。

入力時に、入力と同じ言語の定型文を表示して、こういう意味の英語に変換しますよって事か。
単純に文章校正にも使えて便利そう。

ただ、将来的に普及し過ぎたら、文字による情報伝達は個性がなくつまらないものになりそうだなと思った。

308デフォルトの名無しさん2016/09/01(木) 09:59:39.50ID:pVMnIIR6
カードを使って買ったものを"ユーザー自身が"把握できるサービスがあったらヒットしそうな気がする
そもそもカードってのは個人が何を買ったか把握するためのシステムなのに
その効果を店側しか利用できないなんてもったいないじゃないか

必要な物全てをカードで買えば自動的に家計簿が出来上がるし
食品の場合は消費期限やカロリーなんかも出してくれれば相当便利だろう

309デフォルトの名無しさん2016/09/03(土) 17:48:50.12ID:1pX++2wa
不定形な面積内に2個のサイズ可変な正方形を最大面積で置くには
どんな探索手順がイイんだろう?

310デフォルトの名無しさん2016/09/04(日) 19:47:21.73ID:pCJy0LgL
>>308
>そもそもカードってのは個人が何を買ったか把握するためのシステムなのに

カードって何のカード?
ポイントカード?

311デフォルトの名無しさん2016/09/08(木) 00:11:51.95ID:ij6VDmav
>>308
au Wallet は?
au のスマホ持ってないと意味をなさないけど、一応実現できていると思うぞ。

312デフォルトの名無しさん2016/09/08(木) 00:12:59.41ID:ij6VDmav
あ、よく見たら消費期限やカロリーも?
そこまではないなあ。

313デフォルトの名無しさん2016/11/14(月) 14:22:12.97ID:IEgPgh3U
>>301
3個ほどの値の中央値ってのを求めるとかならソート数列がある程度大きければめちゃ使えそう

314デフォルトの名無しさん2016/12/14(水) 00:17:01.88ID:b/IcEtEF
バケットソートが好きだな

315デフォルトの名無しさん2016/12/19(月) 21:46:23.02ID:p8ZG7dfy
新しいソートアルゴリズムはもう出ないのかな

316デフォルトの名無しさん2016/12/20(火) 18:15:48.61ID:Ih9ndzia
既存のいいとこ取りみたいなのはまだまだ出るだろうけど、全く新しいのは厳しいだろうね

最初にデータ全体の半分をマージソートして
その結果を中央値にしたクイックソートをすれば速くなりそう

317デフォルトの名無しさん2016/12/21(水) 22:44:05.01ID:KgQ+mMVr
Qbitとかマルチスレッド前提のアルゴリズムとか

318デフォルトの名無しさん2017/01/24(火) 17:42:16.89ID:28f07hFv
うちの母親は人の話した単語で自分の話を始める癖があるんだけど
この癖をマネすればチューリングテストをパスできるプログラムが比較的簡単に作れるような気がする
名付けて「コンピューターお母ちゃん」だ

319デフォルトの名無しさん2017/12/16(土) 10:32:06.71ID:gY8Oz9or
「東京大改革」が聞いてあきれる。
都議会の「かがやけTokyo」「日本維新の会」「共産」「生活者ネット」の
4会派が共同提出した都議のボーナス増額を阻止する条例改正案を、
小池知事が特別顧問を務める最大会派「都民ファーストの会(都F)」が
突っぱねていたことが分かった。
14日、4会派が都庁で会見して都Fの“ご都合主義”を批判した。

https://news.nifty.com/article/domestic/government/12136-431863/

320猫娘+ ◆BotWa53rWA 2018/02/03(土) 19:34:15.42ID:UlYItUwa
11×11をこの調子で数えると、約290億年かかります。
(宇宙の年齢は推定137億年)

ところが、現在の最先端のアルゴリズム技術を使うと、
同じ問題を普通のパソコンでわずか数秒で数え上げることができます。

16×16の問題でも普通のパソコンにて、わずか2時間で終わってしまいます。

『フカシギの数え方』 お姉さんに教えてあげたい…。

321デフォルトの名無しさん2018/02/07(水) 12:42:43.08ID:oaI3SEA+
あの動画ももう結構古いし
今の最新アルゴリズムだとどうなんだろう

新着レスの表示
レスを投稿する