2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

データ構造とアルゴリズム総合

1 :デフォルトの名無しさん:2012/03/21(水) 06:40:59.10
データ構造とアルゴリズムに関する総合スレ。

【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
<集大成>アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/

2 :デフォルトの名無しさん:2012/03/21(水) 06:41:18.28
【参考サイト】
アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html

3 :京霊研 ー アイ :2012/03/21(水) 14:45:38.92
アンチエイリアスつきのブレゼンハム線を教えれ

4 :デフォルトの名無しさん:2012/03/21(水) 14:57:53.56
ブレゼンハムってサブピクセルレンダに応用してうまみなんてないだろ

5 :デフォルトの名無しさん:2012/03/21(水) 17:53:02.61
純粋関数型言語のためのデータ構造

Purely Functional Data Structures
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Purely Functional Data Structures
http://www.amazon.co.jp/dp/0521663504

Purely Functional Data Structures読書会議事録
http://wiki.haskell.jp/Workshop/ReadPFDS/
20分でわかる Purely Functional Data Structures
http://www.kmonos.net/pub/Presen/PFDS.pdf

6 :デフォルトの名無しさん:2012/03/22(木) 12:24:18.53
角Aから角Bに時計まわりに方向転換するとき途中で角Cを向くか真偽値を返すkaku(A,B,C)をくれ
(ラジアンで指定 一周以上はしない kaku(π*30, -π*20+3, 4)ならfalse)

7 :デフォルトの名無しさん:2012/03/22(木) 13:50:20.27
こいつなんで偉そうなの

8 :片山博文MZボット ◆0lBZNi.Q7evd :2012/03/22(木) 15:29:46.99
bool kaku(double a, double b, double c)
{ return b <= c && c <= a; }

「kaku(π*30, -π*20+3, 4)ならfalse」は論理エラー。

9 :デフォルトの名無しさん:2012/03/22(木) 19:10:36.30
>>8
2πnラジアン=0ラジアン(nは整数)である事を利用して
a-bとa-cを0以上2π未満に正規化し、a-bの方が大きければtrueです。
ちなみにkaku(π*30, -π*20+3, 4)=kaku(0, 3, 4)はtrueです。

10 :デフォルトの名無しさん:2012/03/22(木) 21:35:58.78
falseじゃね?

11 :デフォルトの名無しさん:2012/03/23(金) 07:39:23.91
>>10
0ラジアンを右とするとπ/2ラジアンは上、πラジアンは左、3π/2ラジアンは下です。
kaku(0, 3,4)は、0ラジアン(右)から時計回りに3ラジアン(左より少し上)まで方向転換し、
途中で4ラジアン(左下)を向くからtrueです。

kaku(0, 3,4)=kaku(2π, 3,4)だから、
|aからbへの時計まわりの移動量|=|bからaへの反時計回りの移動量|=a-b=2π-3
|aからcへの時計まわりの移動量|=|cからaへの反時計回りの移動量|=a-c=2π-4
2π-3>2π-4なのでtrueです。

12 :デフォルトの名無しさん:2012/03/23(金) 07:54:41.82
>>11
×  a-b=2π-3、 a-c=2π-4
○ a-b≡2π-3 (mod 2π)、 a-c≡2π-4 (mod 2π)

13 :デフォルトの名無しさん:2012/03/23(金) 08:04:59.36
ム板民と数学人間でY軸方向の符号が違うから差が出るな

14 :デフォルトの名無しさん:2012/03/24(土) 00:03:59.97
だいたいの感じでコーディングしてみた。
動くかは知らん。

bool kaku (double a, double b, double c)
{
  double na = fmod(a, PI*2.0);  if (na < 0.0) na += PI * 2.0;
  double nb = fmod(b, PI*2.0);  if (nb < 0.0) nb += PI * 2.0;
  double nc = fmod(c, PI*2.0);  if (nc < 0.0) nc += PI * 2.0;

  // 時計まわりの方向がプラス回転
  if (nb < na) nb += PI * 2.0;
  if (nc < na) nc += PI * 2.0;

  return (nc <= nb);
}


15 :京都大 :2012/03/24(土) 12:34:28.90

□□□□□□□□□ ・右の図の□を■にしてすべての■をつなげたい
□■□■□■□■□ ・毎回違う結果にしたい
□□□□□□□□□ ・無駄がないようにしたい
□■□■□■□■□ ・輪にならないようにしたい
□□□□□□□□□ ・よろしこ
□■□■□■□■□
□□□□□□□□□
□■□■□■□■□
□□□□□□□□□

16 :デフォルトの名無しさん:2012/03/24(土) 13:08:20.62
□□□□□□□□□
□■□■□■□■□
□□■□■□■□□
□■□■□■□■□
□□■□□□□□□ ・これはありか
□■□■□■□■□
□□■□■□■□□
□■□■□■□■□
□□□□□□□□□

17 :デフォルトの名無しさん:2012/03/24(土) 13:37:09.87
つ ローグライクのダンジョン生成参考

18 :デフォルトの名無しさん:2012/03/24(土) 15:08:07.10
何というか・・・宿題スレでやれ


19 :デフォルトの名無しさん:2012/03/24(土) 15:19:59.08
ジオロケーションのアルゴリズムで相談をお願いします。

データレコード
struct
{
float  x;
float  y;
String buffer;
};
が数千件あるテーブルがあるとします。

その中からユーザーの座標(float ux. float ,uy)の半径 R(float)以内にある
データレコードのbufferを取り出すにはどうすれば一番効率が良くなるでしょうか?

テスト段階での条件では
範囲としては関東全域
Rの値は最大 100m
サーバー側のクロックは
CPUクロック:3GB
使用可能メモリ:6GB〜10GB
レコードの平均使用容量:112byte

クライアント側はAndroidを利用してサーバーからへ座標を渡して、情報をリクエスト、
また新しい情報をポストするのみになります。
送受信にはUDPパケットの使用を考えています。

また挿入や削除がしやすいというのが第一の条件となっています。
なのでデータはすべてメモリ上におき、テキストエディタみたくギャップバッファと地域の細分化、リンクドリストを
複合的に持ち合わせて、定期的にDBへのアップデートを行っていこうと考えております。
以上を踏まえてどなたかアドバイスなどをいただけないでしょうか?

20 :デフォルトの名無しさん:2012/03/24(土) 15:57:37.84
>>19
素人なりに考えた。
全データを100m四方のグリッドで分割しといて(ハッシュででも)、
ユーザ座標含めた隣接9グリッドについてのみ計算する。
件数も少ないし計算も複雑でないから、複雑な枝刈りはあんま意味ないとおもう。
てか数千件ならふつうに総当りでもいけそう。

じぶんがつくるなら、サーバは起動時とユーザシグナル受信時にDBから読むだけで
データ管理とは分離させる。

21 :デフォルトの名無しさん:2012/03/24(土) 16:17:15.72
>>20
なるほど
参考になります。
ではデータはグリッドごとということして挿入、削除をすればいいということですね
ありがとうございます。

22 :デフォルトの名無しさん:2012/03/24(土) 16:24:15.02
>>19
kd-treeがいいんじゃないかな。
フォトンマッピングでぐぐると、近傍のフォトン探索とかの使用方法が出てくると思う。

23 :デフォルトの名無しさん:2012/03/24(土) 16:31:57.56
>>22
フォトンマッピングですね
調べてきます。
ありがとうございます。

24 :15:2012/03/25(日) 10:16:52.24
>>16

なしだぜ

25 :デフォルトの名無しさん:2012/03/25(日) 10:50:24.50
>>15はアイちゃん

26 :デフォルトの名無しさん:2012/03/25(日) 12:25:26.16
>>15
>無駄がないようにしたい
下記のように■同士を最短距離でつなげたいという意味ですか?

□□□□□□□□□ ・右の図の○を■にしてすべての■をつなげたい
□■○■○■○■□ ・毎回違う結果にしたい
□○□○□○□○□ ・輪にならないようにしたい
□■○■○■○■□
□○□○□○□○□
□■○■○■○■□
□○□○□○□○□
□■○■○■○■□
□□□□□□□□□

これで全ての■がつながるなら24個の○のうち最低15個が■ですね。
15個の■と9個の□で全ての■をつなげた時は輪はありません。
以下の手順で全ての組み合わせが求まります。

1 24個の○のうち15個を■、9個を□にした順列を順番に走査する。
2 今調べている順列に上下左右が□の■があればボツ。

順列を再帰呼び出しで作り、
1〜9個目の□の位置を決めるごとにその上下左右の■を調べ、
■の上下左右が全て□だったらその枝の走査を打ちきると効率的です。

27 :デフォルトの名無しさん:2012/03/26(月) 02:12:37.52
面白そうな問題なんだが、
>>26の言うように「無駄がないように」の意味があいまいなんだよね。
>>26のような解釈でOKなのか、それとも探索に無駄がないようにという意味なのか。

28 :京霊研:2012/03/26(月) 08:55:15.92
>>26
そうその○の位置だけ変えるって意味だぜ
探索はどうやってもいいぜ
それだと2組に分かれる可能性があるぜ
あと15個以下でも全部繋げられるから輪になるかもだぜ

29 :デフォルトの名無しさん:2012/03/26(月) 11:03:44.25

■ ・これが孤立しているケース


30 :デフォルトの名無しさん:2012/03/26(月) 11:14:18.36
>>28
>それだと2組に分かれる可能性があるぜ
確かにボツにする条件が不十分ですね。
それに15個を○から●にして2組以上になったら必ず輪ができます。
最後に全部つながったか確認する必要があります。

□□□□□□□□□
□■●■●■●■□
□●□●□○□○□
□■●■●■●■□
□●□○□○□○□
□■●■●■●■□
□○□○□○□○□
□■●■●■●■□
□□□□□□□□□

>あと15個以下でも全部繋げられるから輪になるかもだぜ
左上の■に残りの15個の■を●でつなげていくと考えてください。
1個の○を●にした時に左上に新たにつながる■は高々1個だけです。
だから全部の■をつなげるには最低15個の●が必要です。
1個の○を●にした時に輪ができたら新たにつながる■はありません。
だから15個の●だけで全部つながったら輪はありません。

31 :デフォルトの名無しさん:2012/03/26(月) 23:50:53.03
・開始点の■を決める

A
■B■   
C

・次に繋がる点をリストアップ  
・繋がる先がすでに別な方向から繋がってたら除外
・リストから一点選ぶ
■□■
.A  B
■■■E■  
.C  D
■□■
・次に繋がる点をリストアップ  
・繋がる先がすでに別な方向から繋がってたら除外
・リストから一点選ぶ
・再帰

32 :デフォルトの名無しさん:2012/03/27(火) 15:34:05.65
勤務表作成アルゴリズム募集。

ExcelVBAで勤務表を作ろう
http://toro.2ch.net/test/read.cgi/tech/1329803312/

33 :デフォルトの名無しさん:2012/03/27(火) 18:31:43.60
勤怠表はアルゴリズムってより
対象者向けインターフェースの推敲が難しいからな
ライン工相手に出勤退勤毎にキーボード叩けなシステムとかアホ過ぎるし

34 :デフォルトの名無しさん:2012/03/27(火) 19:08:39.50
タイムカードをがっちゃんがっちゃん押したらUSBでPC等につながって自動管理、とかの機械ありそう

35 :デフォルトの名無しさん:2012/03/28(水) 02:17:12.79
あながち馬鹿に出来ない

押し忘れとか、日付が変わってから退社とか、
3交替の夜勤とか

下手なものを作ると出勤か?退勤か?すら後で分からなくなるw

36 :デフォルトの名無しさん:2012/03/28(水) 08:50:46.61
>>31
エクセルで作ったぜ〜

http://www42.atwiki.jp/syugyou?cmd=upload&act=open&pageid=250&file=mei.xls

37 :デフォルトの名無しさん:2012/03/28(水) 10:21:13.89
>>34
うちのは無線LANで飛ばしてるお


38 :営利利用に関するLR審議中@詳細は自治スレへ:2012/03/29(木) 00:04:51.11
うん

39 :営利利用に関するLR審議中@詳細は自治スレへ:2012/03/29(木) 08:31:17.45
タンピンリャンペーコーを判別せよ


40 :営利利用に関するLR審議中@詳細は自治スレへ:2012/03/29(木) 14:11:37.90
まず雀頭1と順子4つになっているか確認
その後19字牌がないがチェック ない場合成立
二杯口は順子をグループ化してふたつどういつかチェックすればいいんでね
平和だけどタンヤオって時点で役牌じゃない&二杯口も前提条件だから
両方が成立したとき自動的に成立

タンピンリャンペーコーを判定する専用ならこういうやり方でいいんでね



41 :営利利用に関するLR審議中@詳細は自治スレへ:2012/03/29(木) 15:50:35.74
>>39-40
君らみたいなのが宇宙麻雀作るんだろうな(´・ω・`)

>>40
待ちは?

42 :営利利用に関するLR審議中@詳細は自治スレへ:2012/03/29(木) 18:18:29.52
> 風牌や三元牌で順子可能
> ドラのみ和了
> 立直後明槓
> メンタンピン一盃口が役満
> 白があっても清一色可能
> 一気通貫が役でない

これはひどい

43 :営利利用に関するLR審議中@詳細は自治スレへ:2012/03/30(金) 10:19:59.32
宇宙麻雀ググッたけど
設定ミスで>>42とかプログラマー神すぎるだろ

44 :営利利用に関するLR審議中@詳細は自治スレへ:2012/03/31(土) 21:02:41.36
閉路を沢山含んだインバースキネマティクスって
どうやればいいの?

もう既に有名なアルゴリズムとかあるの?


45 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/01(日) 05:42:22.57
2-正則な閉路だけ考えた場合、移動した頂点から交互に重複するまで解決していくだけだし
そこから伸びた枝は普通に解決出来ないか?

46 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/01(日) 13:39:02.37
>>45
注意してもらいたいのは、要件は「閉路を含んだ」ではなく
「閉路を沢山含んだ」になっている点です。

例えば、以下のような格子状の関節(5*5)をもっている場合、
リアルタイムで計算させるのは結構難しいかと。

┌┬┬┬┐
├┼┼┼┤
├┼┼┼┤
├┼┼┼┤
└┴┴┴┘

もうすでに誰か偉い人がアルゴリズムを考えていたりしないかな、と。


47 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/01(日) 21:37:29.89
一度通った道を再び通らないようにすることだけ考えりゃいいんだから
結局は同じじゃねえの

48 : ◆QZaw55cn4c :2012/04/01(日) 21:54:11.78
「薔薇の名前」のアルゴリズムは使えないか?

49 : ◆QZaw55cn4c :2012/04/01(日) 22:27:20.12
>>15
http://toro.2ch.net/test/read.cgi/tech/1313183984/187

50 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/02(月) 06:58:39.00
>>47
もし簡単ならば、そのアルゴリズムを教えてほしい。
そしてその計算量の見積もりも。

でも、それが簡単じゃないからこそ今のIKは
軒並み「ループ無し縛り」を課している訳で。


51 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/02(月) 07:54:20.67
なんでQZがいんの

52 :15:2012/04/02(月) 14:36:11.40
>>49
ありがたまきんΩ

53 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/02(月) 18:42:03.65
さめがめの最適解を求めるアルゴリズムを
作ろうとしています。

□□●●□□●□●
○■●■●■●■□
○●●●□○□○●
□■●■●■●■□
■●□○□○□○●
□■●■●■●■●
■○□○□○□■□
□■●○●■●■□
■□□○□■□■■

ルール:
 隣り合う2つ以上の連続した同じ種類の記号は消去できる。
 重力あり。消えたら下に詰める。
 連続で消せたら高得点

この仕様で、連続して消せる最大の回数を求めるのと、
完全に消去するという二つをそれぞれで考えたいのですが、
総当りだとものすごい時間がかかりそうなので、何か
数学的な理論や手法などはないでしょうか。

1)消せるブロックの集合を探す
2)ブロックを消す
3)消えたブロックの上のマスを落とす
4)1)に戻る

特に1)の部分の隣り合う2つ以上の連続した同じ種類の記号を
探すのが結構時間がかかりそうなので時間短縮する方法が
あれば教えてください。

54 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/02(月) 19:42:44.37
さめがめってNP完全でしょ。

> 総当りだとものすごい時間がかかりそう

試してはいないんだな。

55 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/02(月) 20:03:33.82
発散しそうもないし、先ずは試してみたらいいんじゃね。

56 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/03(火) 10:14:52.66
消せるブロックの集合が崩れてない時に
その情報を次のターンに持ち越せば少しは軽くなるな

57 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/08(日) 22:28:30.73
さめがめってよくフラッシュとかでもゲームあるけど、
ブロック消すところはなぜあんなに早いの?

思い浮かんだロジックだと、>>53を例にすると、

1)9x9のテーブルを2種類作る(Aテーブル、Bテーブル)
2)Aテーブルに記号別にフラグ(たとえば1〜5)を埋め込む
3)たとえば左上を基点に上下左右に同じ種類の記号が
  あるか調べる
4)あったらBテーブルに消せる場所に種類のフラグを埋め込む
5)基点から3)と4)を実行して全部調べる
6)Bテーブルに消せるマスがあれば、同じ位置のAテーブルのマスを空白にする
7)Aテーブルの空白のマスを消去し、上にマスが残ってたら下に下ろす

ここまでを一瞬でやってるわけですよね?
もっと簡単にできる方法があるのかな。

58 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 00:26:59.90
1GHzのCPUで、一マスの処理が1000命令かかるとすると、秒間100万マスの処理が可能。
81マスの処理なんて余裕すぎる。

59 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 00:52:48.40
なんで >>58 は、1クロック1命令だと思ったんだろう


60 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 01:03:57.34
ベンチでFLOPS計測するしかないってか。

61 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 09:21:58.82
え、でも計算量って1マス検査するのに、残りの80マスをチェックしないと
いけないから、9x9のマスのチェックをするのに、

81×(81−1)×・・・ってなるんじゃないの?

62 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 09:38:20.91
隣り合ってるマスだけでいいだろ。

63 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 20:26:34.18
1クロック1命令、っておおざっぱな見積りでは普通に使うだろうが

64 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 21:03:02.17
>>63
いいからあなたはPentiumだけ使っててください。

65 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 22:10:30.77
大昔のBASICでは、PAINT文で塗りつぶしを行うと
塗りつぶして行く様子が目で見えてたなぁ

66 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 22:54:13.98
>>64
1クロック1命令の方がCPUとして少数派だと思うが・・・
2,3クロック1命令で見たほうが良くないか?


67 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 22:55:03.93
ごめ・・・
>>66>>63向け


68 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 23:33:16.52
クロック周波数で性能は比較できない

69 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/09(月) 23:36:06.57
総括すると>>63でオーダとしては妥当ってことじゃないの?

70 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 00:16:07.22
スレ違いだし、とっとと収束させるべきなんだろうけど…
>>69
>総括すると
頭おかしいのか?

71 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 00:20:24.86
オーダーは変わらない。
1命令が1クロックだろうが、100クロックだろうが変わらない。

72 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 00:30:55.57
話がかみ合ってなくてワロスwww

73 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 00:40:56.01
1GHzのCPUで、一マスの処理が1000クロックかかるとすると、秒間100万マスの処理が可能。
81マスの処理なんて余裕すぎる。

これでおk。

74 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 06:50:43.40
>>68 IPC(CPI)が同じなら、クロックが倍のコンピュータなら、
周辺による遅れがなければ、倍の性能だろうが。バカか?

75 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 11:26:00.65
アルゴリズムの文脈で、計算量ってどう見積もるのか知らない奴がこのスレにいるとは

76 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 11:47:24.19
定数倍が重要なことも時にはあるだろうが
最初のレスがゲームについてなんだし

77 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 13:45:31.87
>>74
ふつー、バス速度は絶対に倍にはならないですよね…

78 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 18:16:05.89
>>62
そっか。
となれば、最大81×4回(上下左右)チェックすればいいだけか。
さらに端っこのますは片側は壁だからもっと少ない計算量で
済むんだな。


79 :営利利用に関するLR審議中@詳細は自治スレへ:2012/04/10(火) 23:10:48.23
>>75
見積もりといえばKKD法だよな。


80 :デフォルトの名無しさん:2012/04/14(土) 19:53:09.94
スケープゴート木って、サイズ計算に時間食い過ぎるな。
かと言ってノードにサイズ情報埋め込むのは本末転倒な気がするし。

81 :デフォルトの名無しさん:2012/04/14(土) 20:57:57.57
俺さ、ハッシュマップってのを思いついたんだが

82 :デフォルトの名無しさん:2012/04/14(土) 20:58:49.31
車輪

83 :デフォルトの名無しさん:2012/04/14(土) 21:05:42.14
八種抹粉

84 :デフォルトの名無しさん:2012/04/14(土) 21:09:24.55
いらなーい

85 :デフォルトの名無しさん:2012/04/16(月) 05:22:45.95
一度車輪をやらないと上を行くアルゴリズム作るのは無理

86 :デフォルトの名無しさん:2012/04/16(月) 08:19:00.54
さめがめ:連続で消せたら高得点
てナニ?

87 :デフォルトの名無しさん:2012/04/19(木) 11:06:37.63
イナズマの描画法をおしえれ

88 :デフォルトの名無しさん:2012/04/19(木) 17:11:02.18


89 :デフォルトの名無しさん:2012/04/19(木) 17:13:32.69
Piローダーだっけ、イナズマローダーって

90 :デフォルトの名無しさん:2012/04/19(木) 17:24:40.05
>>88
Z じゃね?

91 :デフォルトの名無しさん:2012/04/19(木) 17:36:25.65
picとかだね

92 :デフォルトの名無しさん:2012/04/19(木) 22:52:28.58
CADで言うところのフィレット

2つの線分があり、端点の一つを共有している状態で
半径5のフィレットを行いたい

つまり、点P1(x1,y1) 点P2(x2,y2),点P1(x3,x3) で 点P2の部分をフィレットしたい

お分かりなる方がいたらおしえてください

93 :デフォルトの名無しさん:2012/04/19(木) 23:14:56.11
内角に辺5のひし形作って対角を中心とした円

94 :デフォルトの名無しさん:2012/04/20(金) 03:22:59.96
>>92
点と直線の距離の公式を使って垂線の長さ5の方程式を二つ立てる。
これを連立方程式として解くと円の原点候補が二つ求まる。
点P2→点P1と点2→原点候補の内積が正になる方が円の原点である。
原点を中心とした半径5の扇を描く。

>>93
菱形の辺の長さが5なら内角が直角の時以外は円の半径は5より小さくなります。

95 :デフォルトの名無しさん:2012/04/20(金) 09:28:57.75
ArcTo関数か
俺なら自前でBezier2Dするねキリッ

96 :デフォルトの名無しさん:2012/04/21(土) 07:11:47.54
test

97 :デフォルトの名無しさん:2012/04/21(土) 07:13:42.88
2と3だけを複数回かけてある数Aにもっとも近い数を作りたーい

98 :デフォルトの名無しさん:2012/04/21(土) 11:16:24.54
総当り

99 :デフォルトの名無しさん:2012/04/21(土) 23:17:10.93
宿題か

100 :デフォルトの名無しさん:2012/04/22(日) 21:33:27.78
文字列が正しくデコードされてるか試験する、という目的の下、文字列の尤度を求めるために、
文字コードの範囲を確率変数として教師信号を用意(様々なファイルから読み込んだ文字列による)したのですが、
いまいち良い信号になりません。(正規分布に従わない)

ラテン文字帯が凄まじい数になり、ラテン文字を含めば全部尤度高い、という結果になってしまいます。
文字化けしたと思われる値(教師信号分布0の文字帯)の信号値を、より低い値にしたい(コストを大にしたい)のですが、
こういう場合、どういう風に信号を改善していけばいいでしょうか・・。

101 :デフォルトの名無しさん:2012/05/11(金) 13:57:17.81
a, b, c, d, e, zの昇順ソートされた整数配列があります。
それぞれ、1000万要素程度あり、mallocで領域を確保してあります。

a〜eの配列のそれぞれの要素から、zに含まれている要素を抜いてから、
全て結合してソートして出力したいです。
どういった方法が一番早いでしょうか?

それぞれの配列で
aとz
bとz
cとzと順番に、それぞれでa[0]とz[0]から逐一比較していって、
一致しない要素をメモリに持っておき、
最後に結合して、ソート
というのを考えましたがこれが最良なのかどうか…朝からずっと悩んでいます。




102 :デフォルトの名無しさん:2012/05/11(金) 14:08:02.26
整数かつソートされていると保証されているなら
各配列にポインターをつけて
ポインター群でいちばん小さいものをresult配列に追加してポインターをインクリメント

でいいんじゃね

103 : ◆QZaw55cn4c :2012/05/12(土) 01:57:40.79
>>101
マージソートの応用でいけそうだ。
a, b, c, d, e の先頭なかから一番小さいものをとりだし result に書き出す。
ただし、それが z の先頭と等しかったら捨てる。
a〜e + z のなかで z が一番小さかったら、z の先頭を捨てる。


104 :デフォルトの名無しさん:2012/05/12(土) 02:53:22.74
なるほど

105 :デフォルトの名無しさん:2012/05/12(土) 11:59:03.22
ありがとうございます。
コーディングしてみます

106 :デフォルトの名無しさん:2012/05/14(月) 11:25:53.96
うーん…それぞれの配列がユニークじゃない時はむりか。。
すみません、全配列で要素が重複してる可能性があり、
同配列で値が重複した要素もそれぞれ一要素として扱いたい

例えば、
a={0,1,3,3,4,5,5,7}
b={3,4,5,5,5,6}

z={1,3,5,5,10}

の場合は
a'= {0,3,4,7}
b'= {4,5,6}
として、
result={0,34,4,5,6,7}
としたい・・・
やっぱ一つ一つ出して、resultに格納、最後にソートかなぁ・・・
103みたいになんとかソートを省けないか、もう少し考えてみます

107 :デフォルトの名無しさん:2012/05/14(月) 12:10:41.04
>>106
どうとでもできるとおもうけど
考えてるとおりにaからa'を出力するイテレータ(ジェネレータ)書けばいいんちゃう?

元の配列がソートされてるのにそれを利用しない手はない。

108 :デフォルトの名無しさん:2012/05/14(月) 12:24:59.78
>>106
103の「先頭なかから一番小さいものをとりだし result に書き出す。 」時に、
一番小さい数をある分だけ result に追加すれば良いだけだろ。
少しは考えれば分かるだろうけど。

109 :デフォルトの名無しさん:2012/05/14(月) 12:43:05.75
はい、今回はメモリもある程度限られた状況で
なんと言っても速度重視なので、
何パターンか考えて模索してみます。

110 :デフォルトの名無しさん:2012/05/24(木) 20:24:10.54
http://www.i.u-tokyo.ac.jp/edu/course/cs/pdf/2006computer.pdf

これの専門科目II-1 (4)がわからないんですが
方針だけでもいいので教えていただけないでしょうか?

111 :110の問題:2012/05/24(木) 20:27:06.66
問題 1(100 点).
負の枝長の枝は存在するが,負の経路長のサイクルは持たない強連結な有向グラフ G = (V, E) を
考える.ここで,l(u, v) は枝 (u, v) ∈ E の長さ,d(v, w) は点 v ∈ V から点 w ∈ V への最短路長を
表すものとする.以下の問いに答えよ.
(1) グラフ G において,任意の点 v ∈ V 及び任意の枝 (u, w) ∈ E に対し,
l(u, w) + d(v, u) − d(v, w) ≥ 0 が成り立つことを証明せよ.

(2) グラフ G において,V のすべての点 v に対して数値 s(v)が与えられているとする.さらに,
すべての枝 (u, v) ∈ E についてその長さを l(u, v) + s(u) − s(v) に変換したグラフ G を考え
る.この時,G 上において任意の 2 点 w, x 間の最短路であるパスは,G においても同じく
w, x 間の最短路であることを証明せよ.

(3) グラフ G において,v ∈ V を始点とする最短路木を求めるアルゴリズムを記述し,その計算
量を述べよ.

(4) グラフ G において,v ∈ V を始点とする最短路木が与えられている時に,別の点 w ∈ V を
始点とする最短路木を求めるアルゴリズムを記述し,その計算量を述べよ.

112 :デフォルトの名無しさん:2012/05/25(金) 07:27:26.01
手ダイクストラ法を逐次やって、既存の木と合流したら、最短経路の再計算で手が抜けるのでは?

113 :デフォルトの名無しさん:2012/05/25(金) 17:00:13.49
深さ優先探索の空間計算量って
木の最大深さm, 最大分岐数 b として O(bm) ってありますが、
一つのノードで分岐どうし順序がデータ構造のなかに定義されている、または自明であれば
O(m) になりますよね?

114 :デフォルトの名無しさん:2012/05/28(月) 17:28:58.85
ビー玉云々が何を言ってるのかよくわかりません。この例えは何か原典があるのでしょうか?

http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95

115 :デフォルトの名無しさん:2012/05/28(月) 17:44:51.94
ググり直した出典はありました読んでみます

116 :デフォルトの名無しさん:2012/06/05(火) 00:17:18.82
diffの動作原理を知る〜どのようにして差分を導き出すのか|gihyo.jp … 技術評論社
ttp://gihyo.jp/dev/column/01/prog/2011/diff_sd200906

これ全然理解できない・・・

117 :デフォルトの名無しさん:2012/06/05(火) 09:26:36.11
>>116
「編集距離」で検索すれば分かりやすいページがたくさん
10年位前にOCRの認識率を計測するために色々とインプリメントしたな〜


118 :デフォルトの名無しさん:2012/06/05(火) 09:35:41.80
単純なアルゴリズム(長さMとNの文字列に対して計算量MNになるアルゴリズム)の
解説をすっとばして、実用的なアルゴリズムの解説になってるなぁ。

理解するためにはまず単純なアルゴリズムの解説を探すといいと思う。

119 :デフォルトの名無しさん:2012/06/05(火) 11:11:01.86
>>116
技術評論社のサイト初めて見たけど、中々興味深い記事があるな。

120 :デフォルトの名無しさん:2012/06/05(火) 11:41:07.31

【問1】
ある点が三角形abcの中にあるかどうかを判定する簡潔な方法を俺に教えよ

121 :デフォルトの名無しさん:2012/06/05(火) 11:56:58.65
ぼくのかんがえたさいきょうの(ry

ある点をdとすると、
abc=abd+acd+bcd(面積)

どうやって実装するのかはシラネ

122 :デフォルトの名無しさん:2012/06/05(火) 11:58:14.51
・重心とその点を結んで各辺と交わるかどうか調べる

123 :デフォルトの名無しさん:2012/06/05(火) 12:10:29.02
いや結ぶのは三角形の一点でいっか

124 :デフォルトの名無しさん:2012/06/05(火) 12:14:58.41
0 < ↑ab・↑ap かつ 0 > ↑ab・↑bp かつ
0 < ↑bc・↑bp かつ 0 > ↑bc・↑cp かつ
0 < ↑ca・↑cp かつ 0 > ↑ca・↑ap ならば、点pは△abcの中。

なお、計算に無駄がある。

125 :デフォルトの名無しさん:2012/06/05(火) 12:17:49.79
ごめん、嘘。でもベクトルの内積の符号を調べる方法で良かったはず。

126 :デフォルトの名無しさん:2012/06/05(火) 12:38:23.40
0 > (↑ab・↑ap)(↑ac・↑ap) かつ
0 > (↑bc・↑bp)(↑ba・↑bp) かつ
0 > (↑ca・↑cp)(↑cb・↑cp)

127 :デフォルトの名無しさん:2012/06/05(火) 13:04:37.41
class Triangle
{
public Point PointA { get; set; }
public Point PointB { get; set; }
public Point PointC { get; set; }

public bool PointIsInsideOfThis(Point target)
{
return 宿題か(target);
}
}

128 :デフォルトの名無しさん:2012/06/05(火) 13:39:43.07
目視で確認が一番簡素

129 :デフォルトの名無しさん:2012/06/05(火) 13:49:07.51
>>121
これ?
http://upload.wikimedia.org/wikipedia/ja/math/3/2/f/32f967328ca04765e6804a07e6d1dbc7.png

130 :デフォルトの名無しさん:2012/06/05(火) 17:15:26.77
ヘロンの式だな

131 :デフォルトの名無しさん:2012/06/06(水) 10:50:47.34

A. ありがとうございました

132 :デフォルトの名無しさん:2012/06/06(水) 17:46:11.37
1. VRAMに三角形を描画して中を赤とかで塗る
2. 点に対応するアドレスの値を読み、背景色か赤か判定

BASICならたぶん2行で書ける

133 :デフォルトの名無しさん:2012/06/06(水) 17:49:59.95
えらい無駄が多いな

134 :デフォルトの名無しさん:2012/06/06(水) 19:49:12.59
□□
□ ・ □
  □  □□
  □
こういうコーナーができたときに、「・」の場所は塗り潰せないからアウトだな。

135 : ◆QZaw55cn4c :2012/06/06(水) 21:20:34.03
>>134
詰め碁か?
二眼確保で安泰型にみえてしまうのだが?

136 :デフォルトの名無しさん:2012/06/07(木) 04:44:03.28
一発なら>>126
もしくは2点から特定の角度範囲内

何度も判定するなら>>132みたくマップを作ったほうがいいな

>>134
塗りつぶしを自作すれば可能

137 :デフォルトの名無しさん:2012/06/07(木) 10:13:32.12
アンチエイリアスつきの塗りつぶし三角形を計算で出そうとすると

http://www42.atwiki.jp/syugyou?cmd=upload&act=open&pageid=250&file=ana.html

138 :片山博文MZボット ◆0lBZNi.Q7evd :2012/06/08(金) 11:57:52.99
>>137 これすげー。出版しろよ。

139 :デフォルトの名無しさん:2012/06/08(金) 13:37:48.75
wikiの内容とは何の関係もないんだな

140 :デフォルトの名無しさん:2012/06/08(金) 13:57:23.20
ただのアフィじゃねーか
死ねよ

141 :じゃがりきん:2012/06/09(土) 09:34:10.60
このコードじゃ出版できないぜ〜

142 :デフォルトの名無しさん:2012/06/09(土) 22:58:18.07
ワイルドだろぉ〜?

143 :デフォルトの名無しさん:2012/06/10(日) 00:39:33.38
ダイクストラ法のwikipediaでの説明が日本語と英語のページで全然違うんだけど
なぜ?

144 :デフォルトの名無しさん:2012/06/10(日) 00:43:39.84
公用語の違いかな

145 :デフォルトの名無しさん:2012/06/10(日) 19:25:30.28
書いた人が違うから

146 :デフォルトの名無しさん:2012/06/10(日) 19:31:34.41
不特定多数が編集するから
あまり信用ならない
悪意ある改変とかマイナーな記事なら修正される機会も少ないだろうし

147 :デフォルトの名無しさん:2012/06/10(日) 19:42:39.47
>>146
そういう思い込みを吹き込むのは如何なものか。

148 :デフォルトの名無しさん:2012/06/10(日) 19:59:55.31
「いくらなんでもwikipを書き換えるなんてことはしないだろう」という思い込み

149 :デフォルトの名無しさん:2012/06/10(日) 20:14:16.52
どこか1サイトの情報だけ見ようとするからダメなんだよ
個人サイトでもその人の勘違いや間違いで誤った事が書かれてることもあるし
wikipedia含めいくつかのサイトで情報見比べることが大事

150 :デフォルトの名無しさん:2012/06/10(日) 20:34:12.90
>>143
翻訳記事じゃないんだから構成が違っていて当然だが、何か問題でも?

151 :uy:2012/06/11(月) 04:31:24.08
Wikipediaとか
2chで信者とアンチが争ってるようなカテゴリーの記事だと改変されまくり
Wikipediaと、Wiki以外のサイトの最低2つは情報見ろよゴミカス死ねと思う


152 :デフォルトの名無しさん:2012/06/11(月) 05:42:43.76
基地外コテキター

153 :デフォルトの名無しさん:2012/06/12(火) 14:09:24.92
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1488984684
お願いします

154 :デフォルトの名無しさん:2012/06/12(火) 16:15:20.50
英語が読めないアホはどうぞインチキ情報に騙されてくださいねw

155 :デフォルトの名無しさん:2012/06/12(火) 21:12:15.06
概要の、まずビー玉と紐を用意し・・・
擬似コード

こんな説明でわかるやつ天才や

156 :デフォルトの名無しさん:2012/06/17(日) 05:10:41.60
trieすら自力実装できない自分の頭に悪さに絶望してます
死んだ方がいいですか?

157 :デフォルトの名無しさん:2012/06/17(日) 05:42:29.75
うん。

158 :デフォルトの名無しさん:2012/06/17(日) 05:47:14.55
プログラミングの才能がないと、いくら努力しても土方止まり
他の才能を持っている分野で頑張った方がいいよ

アルゴリズムの説明すると、すぐ理解する後輩がすげーと思ったら、
まわりの大半がそうだった。死にたい。

159 :デフォルトの名無しさん:2012/06/17(日) 09:01:12.14
培養菌の数をカウントするのってどうやるんだろう?
画像から直径と中心を判別するには?

160 :デフォルトの名無しさん:2012/06/21(木) 01:34:04.14
>>159

羊と狼を数えるアルゴリズム
http://www2c.comm.eng.osaka-u.ac.jp/~alcon2009/overview.php

161 :デフォルトの名無しさん:2012/06/21(木) 01:39:31.54
コロニーだから丸?
輪郭抽出→クロージング→オープニング→連続してるのを数える

162 :デフォルトの名無しさん:2012/06/21(木) 03:30:23.41
>>159
単純に色の違うピクセル数をカウントして1ピクセルあたりいくらってのをかけてやるんじゃダメ?

163 :デフォルトの名無しさん:2012/06/21(木) 09:27:55.64
大きさの異なる円が2つ以上重複していてもカウントできなくちゃダメだろ

164 :デフォルトの名無しさん:2012/06/22(金) 02:20:12.99
サメガメの判定で処理負荷が問題になる状況ってどんなだよ。しかも揚げ足取りで揉めてるし。

165 :デフォルトの名無しさん:2012/06/22(金) 07:32:19.63


166 :デフォルトの名無しさん:2012/06/22(金) 08:00:23.50
ほとんど重複だから
輪郭の一部である弧から直径と中心を拾うアルゴリズムかな・・・
で、どうやるの?

167 :デフォルトの名無しさん:2012/06/22(金) 08:36:03.17
OpenCV を使う。
というか画像処理スレの話題。

168 :じゃがりきん :2012/06/27(水) 13:58:41.44
>>137の一部がカラパイアに載ったぜ〜

169 :デフォルトの名無しさん:2012/06/27(水) 14:06:45.24
本人いたのかいな

170 :デフォルトの名無しさん:2012/06/28(木) 13:15:54.50
円の内部(円周上を含む)に点を指定した数だけ打ちたい
それぞれの点の距離を最大化するように打つにはどうすればいい?


171 :デフォルトの名無しさん:2012/06/28(木) 13:29:06.42
最適化問題むずかしす

172 :デフォルトの名無しさん:2012/06/28(木) 13:39:35.73
n=1 どこでも
n=2 2点を繋ぐ線分が円の中心を通るような円周上の2点
n=3〜6 円に内接する正n角形の頂点
n=7 円に内接する正6角形の頂点と円の中心
n>=8 これの求め方を教えてってこと

173 :デフォルトの名無しさん:2012/06/28(木) 13:42:50.29
予想としては
同心円の円周上に点を取っていくことになる

174 :デフォルトの名無しさん:2012/06/28(木) 13:43:23.14
なかなか面白い問題

175 :デフォルトの名無しさん:2012/06/28(木) 13:46:30.74
正三角形による円充填になりそう。

176 :デフォルトの名無しさん:2012/06/28(木) 13:54:51.33
1.円内にランダムに点をばらまく。
2.全ての点についてそれぞれ最近傍の点を見つける
3.その点から離れる方向に移動。移動量はXXX。
4.3の移動量の総和が閾値以下になるまで2へ戻って繰り返す。

みたいなのを考えたんだけど移動量はどうすればいいか

177 :デフォルトの名無しさん:2012/06/28(木) 13:55:12.35
充填問題の一種だろうな。
http://ja.wikipedia.org/wiki/%E7%90%83%E5%85%85%E5%A1%AB#.E5.86.86.E5.85.85.E5.A1.AB

1940年、マジャル人数学者 László Fejes Tóth は、六方格子が正規も非正規も含めたあらゆる円充填の中で最も高密度であることを証明した。
とあるが参考になるだろうか。

178 :デフォルトの名無しさん:2012/06/28(木) 14:02:08.92
>>176
1番目と2番目に近い点と自身で正三角形を作るように移動してはどうか
移動量と移動方向が決まる


179 :デフォルトの名無しさん:2012/06/28(木) 14:03:00.53
>>176
振動しまくって終わる予感。

180 :デフォルトの名無しさん:2012/06/28(木) 14:56:24.90
http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html

181 :デフォルトの名無しさん:2012/06/28(木) 15:29:41.61
球ならどうなんの?
4次元以上なら?

182 :デフォルトの名無しさん:2012/06/28(木) 16:17:59.04
>>176
単純に (距離)^-2 の斥力がはたらくようにしてみた
http://www.dotup.org/uploda/www.dotup.org3139871.png

円周部の密度が高くなってしまう

183 :デフォルトの名無しさん:2012/06/28(木) 16:20:30.94
>>182
それって再近傍の点からの斥力?
全ての点から r^-2 の斥力を受けたらどうなるかね。

184 :デフォルトの名無しさん:2012/06/28(木) 16:21:38.62
>>183
すまんこ
全ての点からの斥力にしてる

185 :デフォルトの名無しさん:2012/06/28(木) 16:27:49.50
毎ターン、各点の再近傍の点からの距離の平均を求め、その平均値との差の二乗に比例して引力/斥力を受けたらどうなるだろうか。

186 :デフォルトの名無しさん:2012/06/28(木) 16:32:57.36
>>182
円周部から中心方向に移動する力が働かないからかな

187 :デフォルトの名無しさん:2012/06/28(木) 16:43:40.74
点Aの座標 P(A)
点Aと点Bの2点間距離 D(A,B) = D(B,A)
点の集合 Z = {A,B,C, ....}

D(a,b) ≧ D(c,d) ∧ P(x)≠P(y) [x≠y; ∀x,y∈{a,b,c,d}; ∀a,b,c,d∈Z;]
を満たすZを求める


188 :デフォルトの名無しさん:2012/06/28(木) 17:24:25.85
>>182
円周部を端点じゃなくて無限にしてみたらどうだろう

189 :デフォルトの名無しさん:2012/06/28(木) 17:29:54.11
>>187
定式化がめちゃくちゃじゃないの?
例えば4点でそれを満たすユークリッド平面上の点の例があるの?

190 :デフォルトの名無しさん:2012/06/28(木) 18:00:35.89
>>188
無限に飛んでいくだけだな

191 :デフォルトの名無しさん:2012/06/28(木) 18:05:33.70
逆に考えるんだ。

http://mathnokai.seesaa.net/image/hex_circle.gif
こういう正三角形のメッシュを考えて、
ちょうど求める数の頂点が円内部に入るように、円の半径と中心を動かすんだ。

192 :デフォルトの名無しさん:2012/06/28(木) 18:48:26.53
>>191
点の数が多いときは圧倒的によさそう

193 :デフォルトの名無しさん:2012/06/28(木) 23:25:07.62
常に格子点に来るわけじゃないと思うけど

194 :デフォルトの名無しさん:2012/06/28(木) 23:30:50.22
何が?

195 :デフォルトの名無しさん:2012/06/28(木) 23:57:54.20
最適解が

196 :デフォルトの名無しさん:2012/06/29(金) 01:35:35.32
>>191
ちょうど数をとっても隙間ができる
その分まだ距離は広がれる


197 :デフォルトの名無しさん:2012/06/29(金) 03:44:55.03
いや、無理だろ

198 :デフォルトの名無しさん:2012/06/29(金) 03:54:38.76
>>191の場合、4,5,6のケースで>>172と違いがでてくる
8以上でも不都合があるかもしれん

199 :デフォルトの名無しさん:2012/06/29(金) 04:38:18.99
>>176で粒子法もどきでFA

200 :デフォルトの名無しさん:2012/06/29(金) 04:40:13.84
外縁部は円周上にへばりつかせて残りを内部にばらけさせるほうがいい

201 :デフォルトの名無しさん:2012/06/29(金) 08:30:00.42
>>190
いや
無限遠という意味ではなく
無限循環?的な意味だった

「無限だけど閉じた宇宙」
みたいな

専門用語知らんのですまそ


202 :デフォルトの名無しさん:2012/06/29(金) 10:50:05.35
>>196
無理。外周で幾つか点を動かせるかも知れんが、内部は動かせない。

203 :デフォルトの名無しさん:2012/06/29(金) 11:22:06.93
>>191
8個の場合円はどこにどの大きさで取るの?


204 :デフォルトの名無しさん:2012/06/29(金) 11:27:55.32
円に内接する、正六角形に正三角形を一つたした、↓の図形の頂点が解になるだろうな。
 ___
/ \/
\_/
これより頂点間距離が大きいのがあったら提示してくれ。

205 :デフォルトの名無しさん:2012/06/29(金) 12:11:49.17
隙間だらけじゃん
http://www.dotup.org/uploda/www.dotup.org3142869.png
例えばこれらの点をこう動かせばどの点との距離をとっても広がるか変わらないかだね
狭まる箇所は無いね


206 :デフォルトの名無しさん:2012/06/29(金) 12:15:14.96
存在しないファイル。

207 :デフォルトの名無しさん:2012/06/29(金) 12:21:33.24
すまんうpし直した
http://www.dotup.org/uploda/www.dotup.org3142891.png


208 :デフォルトの名無しさん:2012/06/29(金) 12:26:58.00
>>207
一番下の二つの頂点も動かさないと、距離変わらないぞ。

そして全部動かした後で、距離が広がってるかも確認してくれ。

209 :デフォルトの名無しさん:2012/06/29(金) 12:28:41.92
>>204
その図形を円に内接させた状態で、外周に近い一部の頂点は更に円周方向に移動できそうだよ。
要は>196か。

でもまぁ、>176で闇雲に求めるよりも>176の1で与えるべき初期値としてはいいのか。

210 :デフォルトの名無しさん:2012/06/29(金) 12:40:20.28
最小距離を最大化すればいいという考え方と
全ての点の組み合わせの距離の総和を最大化するという考え方の違いか


211 :デフォルトの名無しさん:2012/06/29(金) 12:45:37.56
帰ったら俺も作ってみるか

212 :デフォルトの名無しさん:2012/06/29(金) 14:59:49.66
>>208
下二つも広げられるよ

213 :デフォルトの名無しさん:2012/06/29(金) 15:26:31.30
>>204
正七角形の頂点+中心点


214 :デフォルトの名無しさん:2012/06/30(土) 00:07:19.12
>>170これは何に使うアルゴリズムなのかな

215 :デフォルトの名無しさん:2012/06/30(土) 00:10:50.60
サンプリングとか?

216 :デフォルトの名無しさん:2012/06/30(土) 00:25:55.72
どんなN角形も三角形に分割できるわけで2点の距離を同じにするなら近隣の3点を結ぶと正三角形になるような形が理想的だが
どんな2点でも等距離である必要はなく、すべての点の中で2点間距離が最小となる距離を円の範囲内で最大化するって問題だから
単純に正三角形の敷き詰めからの切り抜きでは実現できないってことか

ある正円Rがあり
Rの内側と円周上に合わせてN個の点が存在し
N個の点のうち任意の2点間の距離Dp [p=1,2,...,N*(N-1)/2]と定義したとき
Min(Dp)を最大にするN個の点の位置を求める

217 :デフォルトの名無しさん:2012/06/30(土) 00:34:11.07


218 :デフォルトの名無しさん:2012/06/30(土) 01:32:33.72
>>215
ずばり正解

219 :デフォルトの名無しさん:2012/06/30(土) 01:43:26.93
このスレにいる連中のレベルを調査か

220 :デフォルトの名無しさん:2012/06/30(土) 01:44:13.48
そして有望そうな奴はバシバシスカウト

221 :デフォルトの名無しさん:2012/06/30(土) 01:53:46.77
サンプリングなら >>191 でも正方格子でもいいんじゃないかと思った

222 :デフォルトの名無しさん:2012/06/30(土) 01:55:04.81
有望そうなのって居る?

223 :デフォルトの名無しさん:2012/06/30(土) 03:01:35.40
正三角形とか正方形メッシュで
中心と半径を探すアルゴリズムってどうやるの?


224 :デフォルトの名無しさん:2012/06/30(土) 03:14:52.14
点の重心求めて最遠点までを半径にすりゃいいんじゃね?

225 :デフォルトの名無しさん:2012/06/30(土) 03:23:51.65
最近距離の2点を見つける
その2点だけ自身を除くすべての点からの斥力方向へ移動(移動量は2番目に距離の短いものより1以上長くなるよう)
点が円の外側へ移動しようとするとき、円自体を移動させすべての点が円内に収まるようにする
でやってみたがダメだった

226 :デフォルトの名無しさん:2012/06/30(土) 04:12:00.84
>>223
もしかして >>159 なのか
つくづく問題を説明する気のない人だwww

シャーレ上の培養菌のコロニーの数と半径を求めよ
サンプル画像
http://www.dotup.org/uploda/www.dotup.org3146244.png
黒線がシャーレ
ピンクの部分が培養菌のコロニーである
コロニー同士は重なる場合もある

って感じじゃないの?

227 :デフォルトの名無しさん:2012/06/30(土) 04:14:41.54
>>224
点の重心って?


228 :デフォルトの名無しさん:2012/06/30(土) 04:16:10.16
>>226
いや全く別人
流れ見てて気になっただけ


229 :デフォルトの名無しさん:2012/06/30(土) 04:31:22.77
別人だったか

230 :デフォルトの名無しさん:2012/07/02(月) 16:30:54.01
すみません、質問です:
voronoi分割のクラスライブラリは、どこかにありますでしょうか?
色んな環境で動作させるために、Boost.Polygon.Voronoiは使えませんorz

231 :デフォルトの名無しさん:2012/07/02(月) 16:51:20.09
スレ違い

232 :230:2012/07/02(月) 17:04:55.20
エエエエェェェェ(略
しかし別スレに移動したら、マルチあっちいけと叩かれるだけ。
このスレでお願いしますOTL

233 :デフォルトの名無しさん:2012/07/02(月) 18:04:21.18
片山議員は参加者に囲まれながら、「民主党政権になってから、生活保護の不公平が見逃すことができないところに来ている。
外国人の不正受給に関しても、まずは日本人の、真面目に義務を果たしている人が優先。
今は特に、韓国なんてすごく豊かなんですから」と持論を展開し、

「私に対してもいろいろ嫌がらせがあったが、どこから来ているかはわかるんですよね。私たちの日本を愛するマグマの方が強いことを教えよう。
日本が正直者が報われる、本当に強い国にもう1度なれるように、私たちががんばりましょう」
と呼びかけると、参加者からは大きな拍手が起こった。

http://www.j-cast.com/2012/07/01137691.html?p=all
http://www.j-cast.com/images/2012/news137691_pho01.jpg
http://www.j-cast.com/images/2012/news137691_pho02.jpg


http://engawa.2ch.net/test/read.cgi/poverty/1341150152/
http://engawa.2ch.net/test/read.cgi/poverty/1341153256/

234 :デフォルトの名無しさん:2012/07/02(月) 18:16:36.16
>>230
> 色んな環境で動作させるために、Boost.Polygon.Voronoiは使えませんorz
なぜBoost.Polygon.Voronoiではダメなのか
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_main.htm を見てもわからない。
せめてBoost.Polygon.Voronoiが動作しない環境を挙げるべきでは。

235 :デフォルトの名無しさん:2012/07/02(月) 19:15:21.06
>>232
マルチした以上しかたない
2chで質問したいなら半年ROMれ

236 :デフォルトの名無しさん:2012/07/02(月) 22:33:24.51
>170

・中心(0,0)、半径1の単位円として一般性を失わない
・1点を (-1, 0)と決め打ちしても一般性を失わない

この条件下で、最近傍の点との距離を dist とした場合に n 点詰め込む処理を用意して、
dist に対して二分探索を行った。

詰め込む処理はある点を追加した時に、
1) その点を中心とした半径 dist の円と単位円の交点
2) その点を中心とした半径 dist の円と、今まで追加してきた各点を中心とする半径 dist の各円との交点
を次の候補として探索した。

n = 20 辺りから急激に遅くなる。
似た問題で http://en.wikipedia.org/wiki/Circle_packing_in_a_circle があってその結果と比べると大体合ってそうな感じ。

http://ideone.com/fOz4R

237 :236:2012/07/02(月) 22:40:36.62
勢い込んで書いてからあれだけど
>210
>最小距離を最大化すればいいという考え方と
>全ての点の組み合わせの距離の総和を最大化するという考え方の違いか
で、最小距離を最大化した場合(あるいは >216 の定式化の場合)で、総和が最大になるかは分かんないね。

238 :230:2012/07/03(火) 09:11:29.66
>>234
HEW。
テンプレート構文を対応していないので、STLも使えません。

>>235
マルチしていません。

239 :デフォルトの名無しさん:2012/07/03(火) 09:21:35.74
スレ違いつってんだろが
失せろゴミ

240 :デフォルトの名無しさん:2012/07/03(火) 09:52:51.30
Voronoiのデータ構造とアルゴリズムについてでそ。
脳に障害があるの?239はwww

241 :デフォルトの名無しさん:2012/07/03(火) 09:54:38.21
↑池沼

242 :デフォルトの名無しさん:2012/07/03(火) 11:24:00.28
回答が返って来ない所でうだうだとするより、他所に行った方が良くないか?

243 :デフォルトの名無しさん:2012/07/03(火) 11:30:59.47
↑オマのうだうだジャマ。てか、それがオマエの存在そのものwwwww

244 :デフォルトの名無しさん:2012/07/03(火) 12:06:27.06
クラスライブラリの場所を尋ねるスレだったのかここ

245 :デフォルトの名無しさん:2012/07/03(火) 12:07:08.76
>>238
スレ立てるまでもない質問はここで 120匹目
http://toro.2ch.net/test/read.cgi/tech/1341099441/

246 :デフォルトの名無しさん:2012/07/03(火) 12:13:40.25
と言うよりこのスレで質問することが妥当であることを示す一言でもあればよかったのにね
『特殊なアルゴリズムのためこのスレの方が一番詳しいんじゃないかとここで質問いたしました』とかさ

247 :230:2012/07/03(火) 12:19:40.11
意外や意外に妥当なvoronoiクラスライブラリが無かったので来ました。

・アルゴリズム事典に無かった
・Javaアプレットは小型のものがあったがC++やC言語が無い
・既存の演算やBoostで出来ちゃうから無い?

ネットにソースが散在してると思っていたんですが。。。

248 :デフォルトの名無しさん:2012/07/03(火) 12:28:02.45
>>247
アプレットがあるならそれをベースにすればいいだろ。
物乞いしたいのなら、スレ違いだってばさ。

249 :デフォルトの名無しさん:2012/07/03(火) 12:38:35.39
いろんな環境で動作させたいんなら環境依存の少ないJavaのそのライブラリ使えばええやん

250 :デフォルトの名無しさん:2012/07/03(火) 12:39:59.36
Javaの奴ってこれだろ?

Lee Byron ≫ Else ≫ Mesh ? A Processing Library
http://www.leebyron.com/else/mesh/

251 :デフォルトの名無しさん:2012/07/03(火) 12:43:12.80
Voronoi diagram - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Voronoi_diagram
外部リンクでも辿って探せや

252 :230:2012/07/03(火) 12:48:19.89
本当に物乞いするだけなら、スレじゃなくてググルするだけだし。
どちらかというと、検索結果があれ?となって、他の人がどういう対応なのか知りたかったのです。

>>248
それは不可能じゃないですが、だから、C++な人の通常の方針が知りたくて。

自分が見つけたリンクは、
Javaは ttp://www.ics.kagoshima-u.ac.jp/~fuchida/research/voronoi/normal/index.html
その他は ttp://gihyo.jp/dev/serial/01/geometry/0012
といった感じです。

が、上のレスに貼られたリンクに入ってみます。

253 :230:2012/07/03(火) 13:12:28.17
voronoiで、先ず、ある点の一番近くの点と結ぶのは、全部やる方法もありますし、工夫する方法も分かります。

その次の、あるドロネー辺の2等分垂直線同士の交点座標を取得方法も分かります。


が、しかしドロネー辺が無数にあると、計算時にどれ活かすか難しくないですか???

254 :230:2012/07/03(火) 13:31:00.88
それと、ある点に対して出来上がるvoronoiが何角形かも不明だし、
関係している線分と関係してない線分とか、線分で領域が閉じてるか、
とか、簡単に分かるのかなぁ?
実際の図を描けば分かっても、プログラムだと1次元的に見えますよねぇ。

255 :230:2012/07/03(火) 13:41:48.29
連投すみません(連投の最後):

ある点の一番近くの点と結ぶのは全部やる方法、じゃダメですよね。
余分に結ぶと余分に線分が出来て、余分に多角形化しちゃうし。

どうもvoronoiの認識が足りないので、そちらを勉強してみます。
もしくは、高度なポリゴンクラスライブラリを持っていれば簡単に解決なのか?_?
チラ裏となってきたので、一旦消滅します。レスはずーっと読み続けますが。

256 :デフォルトの名無しさん:2012/07/03(火) 14:16:40.53
まとめると、「自分で実装する気はないからライブラリ教えろや!」

257 :デフォルトの名無しさん:2012/07/03(火) 14:21:50.90
ライブラリが存在しないケース

・アルゴリズムの再現自体が不可能

・複雑なプログラムになり相応のコストがかかるため、無料提供が無いが有償提供ならある

・アルゴリズム自体の知名度や有用度が低いため手を付ける者が少なくライブラリ化してない

・あまりにも簡単で単純なアルゴリズムのため、わざわざライブラリにして提供するまでもない

258 :デフォルトの名無しさん:2012/07/03(火) 14:24:57.60


259 :230:2012/07/03(火) 14:26:39.02
どうも、いきなりボロノイを実装するのではなく、
>ボロノイ〜逐次添加法
>ボロノイ〜再帰二分法
といった手法が定石みたいでつね。

それらでググったら、多少ひっかかってきますたw
ttp://suuri.ics.kagoshima-u.ac.jp/lectures/easywin/docs/voronoi/Voronoi.h
ttp://www.ics.kagoshima-u.ac.jp/~fuchida/research/voronoi/index.html
ttp://i-health.u-aizu.ac.jp/CompuGeo/2011/exercises.html

理解して修正できるコンパクトなものにしたいでつ。

260 :デフォルトの名無しさん:2012/07/03(火) 14:27:20.48
さっきから日本語サイトばかり

261 :230:2012/07/03(火) 16:27:55.65
英語サイトもみっけ:
ttp://www.koders.com/c/fid17552685298283A6BFE8B1CBCC2D3E9A35C58C16.aspx
ttp://www.leebyron.com/else/mesh/
ttp://www.codeforge.com/s/0/alghorothm-for-voronoi

ttp://www.geocities.co.jp/SiliconValley-PaloAlto/4089/voronoi.html

262 :デフォルトの名無しさん:2012/07/03(火) 16:48:17.86
おまえなんでここにメモってんの?ここにメモる必要ないだろ

263 :デフォルトの名無しさん:2012/07/03(火) 16:56:47.24
おまえなんでここ監視して余計なこと言ってんの?ここで発言する必要ないだろ


264 :デフォルトの名無しさん:2012/07/03(火) 17:44:41.21
>>261>>263
失せろゴミ

265 :デフォルトの名無しさん:2012/07/03(火) 17:48:18.98
(笑)

266 :デフォルトの名無しさん:2012/07/03(火) 20:49:04.54
空間ってか直方体を8つごとに分けていって
8分木の形にしたデータ構造の,一部の葉だけが選択されていて,それらの葉の接続関係
を求めるってどうすればできますか?
葉に対応する直方体の面同士が接していれば接続しているとしたいのですが
階層がちがうのの扱いがよくわかりません。。。

267 :デフォルトの名無しさん:2012/07/03(火) 21:00:13.81


268 :デフォルトの名無しさん:2012/07/03(火) 21:04:32.27
点の絶対座標から、その点を含むノードのアドレスを出せるよう、ノードのアドレスを工夫する。
(ここで言うアドレスとは、root->node[0]->node[1]->node[4] における (0,1,4) のようなもの)

で、選択されたノードの中心座標 (x,y,z) から (x±dx, y±dy, z) (x±dx, y, z±dz) (x, y±dy, z±dz) (復号任意)を含むノードのアドレスを得る。


269 :デフォルトの名無しさん:2012/07/03(火) 21:19:16.93
>>268
どうもです^o^

270 :デフォルトの名無しさん:2012/07/03(火) 22:08:59.67
ミスった。

> (x±dx, y±dy, z) (x±dx, y, z±dz) (x, y±dy, z±dz)

ここ普通に (x±dx, y, z) (x, y±dy, z) (x, y, z±dz) だ。
dx, dy, dz はまあ、直方体のサイズとかでも。

271 :デフォルトの名無しさん:2012/07/03(火) 23:26:29.68
>>255
http://www.pi6.fernuni-hagen.de/publ/tr198.pdf

272 :デフォルトの名無しさん:2012/07/11(水) 03:06:25.48
質問させてください

C++スレから誘導してもらいました
スレチでしたら誘導頂けると幸いです。

O表記法についてなのですが、イマイチ理解できていません。
授業にて以下7つのルールを定義されたのですが
各々について具体的な数字の入った例をいただけませんでしょうか
#数学の勉強が足りないのかもしれませんが、具体的な数字があれば理解できると認識しています。
#宿題ではないのですが、以降のテストで以下ルールを適用しながらアルゴリズムの証明を行う問題が出題される予定です。

1). if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)) then f(n) ∈ O(h(n))
2). if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)) then f(n) + g(n) ∈ O(h(n))
3). an^k ∈ O(n^k)
4). n^k ∈ O(n^k+j) for any j
5). if f(n) = cg(n) then f(n) ∈ O(g(n))
6). loga n ∈ O(logb n) O(logn)
7). loge n ∈ O(loge n)

お手数ですがよろしくお願いします。

273 :デフォルトの名無しさん:2012/07/11(水) 10:26:48.61
いやです

274 :デフォルトの名無しさん:2012/07/11(水) 10:42:54.09
>>272
ggrks

275 :デフォルトの名無しさん:2012/07/11(水) 11:57:07.67
雑多な質問スレっていろいろあるのに
何故このスレに誘導されたのだろうか

276 :デフォルトの名無しさん:2012/07/11(水) 12:12:31.31
>>272

ランダウの記号 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7

277 :デフォルトの名無しさん:2012/07/12(木) 04:03:56.85
>>272
オーダー記号って普通は等号使ってn=O(n)とか書くんじゃないかな
それはともかく数字があれば理解できるって神だな。
関数の極限の話だし。

278 :デフォルトの名無しさん:2012/07/12(木) 07:19:45.35
ヒープソートでなぜ再帰?〜日本語版ウィキペディアの問題点と最強最速のヒープソート〜
http://www.dreamhope.net/soliloquies/HeapSort/


279 :デフォルトの名無しさん:2012/07/12(木) 08:54:36.87
>>278
この人頭悪いね

>同じコンピュータ環境で、Linux GCC環境では2,500,000件程度のデータを取り扱いできるのに対し、
>Windows BCC環境ではその10分の1の258,000件程度が最大です。
>LinuxがWindowsよりも10倍性能が良いのか、GCCがBCCより10倍性能が良いのかはわかりませんが、
>この性能差には驚きました。

そりゃ

int dat[DC+1]; //データ格納用配列

のようにスタックに巨大な配列を取ればそのうちスタックオーバーフローするって
更にスタックオーバーフローは都合の悪い事にエラーが出ずに結果だけおかしくなる事が多い

ちゃんとソートされているのか結果を見たのかな(ヒープ4だけは見ているようだけど)
Linuxはスタックが足りなくなると自動的に拡大してくれるので問題が出ない

ヒープに取れば同じ事
速度が4倍〜13倍も違うのはよく分からない
ちなみにEclipse CDT + gcc4.6.1でやってみたがbccやvcと速度的には大差なかった
スケジューリングの問題かな?

280 :デフォルトの名無しさん:2012/07/12(木) 10:12:28.23
スタックオーバーフローは最近はSEGVで落ちるんじゃね?

ウィキペディアの記事も微妙だが、そのウェブページもいろいろと頭悪いという
ことについては同意。

281 :デフォルトの名無しさん:2012/07/12(木) 10:21:47.95
>>280
Linuxは拡張しきれないスタックを要求した時はSEGVで落ちるけど
Windowsは黙って変な結果を出して終了するか、暴走するかどちらか

282 :デフォルトの名無しさん:2012/07/12(木) 12:08:48.86
ランダウの記号って名前があったのか
知らなかった

283 :デフォルトの名無しさん:2012/07/12(木) 12:51:41.81
Mac も
> 黙って変な結果を出して終了するか、暴走するか

284 :デフォルトの名無しさん:2012/07/12(木) 13:50:54.97
VCのデバッグならスタックオーバーフローを検出して止まるので
リンカのオプションからスタックサイズを改めて指定しなおす事になる
この時に一度ビルドをクリーンしないと単にリンクし直すだけでは
スタックオーバーフローエラーは止まらないようだ

285 :デフォルトの名無しさん:2012/07/12(木) 20:40:52.04
>そして、ウィキペディアを書き換えようかと思ったが、とても面倒なのでこちらにて問題提起することにした。

・・・ナゼ

286 :デフォルトの名無しさん:2012/07/12(木) 21:20:43.48
自己顕示欲の強そうな人だね
他の記事も読んだけど首を傾げすぎて首が疲れた
データベースは毎回自分で実装した方がいいらしいよ 目から鱗だわ

287 :デフォルトの名無しさん:2012/07/13(金) 16:46:26.64
最適化を語るのにオプションを明示しないとか、
データ量を語るのにオプションを明示しないとか、
処理速度を語るのに環境を明示しないとか、
10〜20年くらい前から知識が更新されていないんじゃないだろうか。

288 :デフォルトの名無しさん:2012/07/13(金) 16:47:09.23
>>285
批評に晒されたくないチキンハートなんでしょ。

289 :デフォルトの名無しさん:2012/07/13(金) 19:20:15.32
出回ってる書籍が古いものばかりだからね
図書館で借りようものなら10年〜20年昔の本だって当たり前のように陳列されてる

290 :デフォルトの名無しさん:2012/07/17(火) 20:23:27.35
@区間スケジューリング問題<=p 点カバー問題
A独立集合問題<=p 区間スケジューリング問題

この2つについて
(i)Yes (ii)No (iii)「これが解ければP=NP問題が解決できるので不明」
のいずれかで答え、その簡単な説明も与えよ。

という問題の答えを教えて下さい

291 :デフォルトの名無しさん:2012/07/18(水) 01:05:55.70
C/C++の宿題片付けます 158代目
http://toro.2ch.net/test/read.cgi/tech/1339338438/

292 :デフォルトの名無しさん:2012/07/18(水) 01:26:27.60
すっげえ宿題でるんだな
俺が通ってた大学での「データ構造とアルゴリズム」ってまんまの名前の授業あったけど
宿題に出たのがせいぜい一般的なソートアルゴリズムいくつかををjavascriptで書けとかそういうレベルだったよ

293 :デフォルトの名無しさん:2012/07/18(水) 04:41:54.35
なんでjavascriptなの?なんかその大学に興味があるんだけど
今時は大学でjavascriptでアルゴリズム書かせるのか

294 :デフォルトの名無しさん:2012/07/18(水) 10:28:38.16
schemeの代替

295 :デフォルトの名無しさん:2012/07/18(水) 11:29:46.28
web限定用語で教育するってのはちょっとナンセンスかと

296 :デフォルトの名無しさん:2012/07/18(水) 11:31:53.61
「web限定用語」ってすごい表現だなw

プログラミング言語を「用語」って言うのはどこのマヌケ業界だろう?

297 :デフォルトの名無しさん:2012/07/18(水) 11:39:08.99
web限定言語で教育するって凄い大学だな

298 :デフォルトの名無しさん:2012/07/18(水) 11:41:14.74
逆にCとかJavaみたいな一般のプログラマにとって中途半端に使えない、
実用的でない言語なんて教えたところで意味無いでしょ。

299 :デフォルトの名無しさん:2012/07/18(水) 11:49:22.80
じゃあpythonでいいだろ
少なくともアルゴリズムの授業でjavascriptってのは学生がかわいそうだ

300 :デフォルトの名無しさん:2012/07/18(水) 11:53:38.65
>>298
いや相手は情報系の学生だぞ?
CもJavaもダメな奴がどうやって情報科学を学ぶわけ

301 :デフォルトの名無しさん:2012/07/18(水) 11:54:58.55
>>298
世界が狭すぎ
あなたがどういうバックボーンなのか知りたいわ

302 :デフォルトの名無しさん:2012/07/18(水) 12:02:34.74
情報系っていうのはプログラマ養成施設じゃないよ。
専門学校か他の工学系と勘違いしてないか?

303 :デフォルトの名無しさん:2012/07/18(水) 12:15:03.55
情報系でCもJavaも教えない大学があるのか?
それまともな大学じゃないだろ
そんなカリキュラムが存在するならマジで教えて欲しい 聞いたこと無いから

プログラマ養成機関じゃないからこそCで本質に切り込むんじゃないの
専門学校みたいなプログラマ養成機関こそがPHPとかJavascriptを教えるんでしょ

まあそれはさておき、アルゴリズムの概念を教えるのにJavascriptを使う大学はおかしいよ絶対に
それも否定する?

304 :デフォルトの名無しさん:2012/07/18(水) 12:18:38.42
まともな大学生ならCは自習で既に学んでるから大学ではいちいち教えない

305 :デフォルトの名無しさん:2012/07/18(水) 12:27:09.76
アルゴリズムの本質は言語によって変わらない


306 :デフォルトの名無しさん:2012/07/18(水) 12:31:27.01
「アルゴリズムの本質は言語によって変わらない」
それはわかるけどさ、だからといって
「アルゴリズムの本質は言語によって変わらないからJavascriptで教えます」
はおかしいでしょう 普通の感覚じゃ考えられない

言語実装に関係のない本質を教えるんであれば、なおのこともっと汎用的な普遍的な言語でやるべきじゃない

307 :デフォルトの名無しさん:2012/07/18(水) 12:34:34.41
そうかい

308 :デフォルトの名無しさん:2012/07/18(水) 12:36:18.55
その感覚はわからなくもないが感覚じゃなく理屈で説明してくれ。

309 :デフォルトの名無しさん:2012/07/18(水) 12:42:09.35
アルゴリズムの授業だからJavascriptなんじゃなくて
別の理由で決まったんだろ

310 :デフォルトの名無しさん:2012/07/18(水) 12:44:52.14
10年前とは違うからな。javascriptを取り巻く環境は随分改善した。
ブラウザ間の互換性であるとかデバッグ環境はすでに十分な領域に達している。


311 :デフォルトの名無しさん:2012/07/18(水) 13:00:17.42
>>305
8-QueenをCOBOLで書くようにという宿題がでるらしいと聞いたら
その授業は取らない。

312 :デフォルトの名無しさん:2012/07/18(水) 13:32:43.00
そうかい

313 :デフォルトの名無しさん:2012/07/18(水) 14:07:00.66
8-Queenとアルゴリズム全般、COBOLとJavascriptじゃ違いすぎるな


314 :デフォルトの名無しさん:2012/07/18(水) 14:36:01.76
いい加減スレ違い

315 :デフォルトの名無しさん:2012/07/18(水) 14:41:23.22
そうかい

316 :デフォルトの名無しさん:2012/07/18(水) 14:59:25.90
JavaScriptをウェブ専用とか思ってるバカがプログラマのわけないだろw

317 :デフォルトの名無しさん:2012/07/18(水) 15:00:37.58
そうかい

318 :デフォルトの名無しさん:2012/07/18(水) 17:11:07.05
ECMAScript は Web 専用じゃないけど Javascript は Web 専用とか、そういう揚げ足取りなのかもね。

319 :デフォルトの名無しさん:2012/07/18(水) 17:44:37.90
言語は手段でしかない

320 :デフォルトの名無しさん:2012/07/18(水) 18:22:28.47
javascriptはクロージャを学ぶのに悪くない

321 :デフォルトの名無しさん:2012/07/18(水) 18:57:27.05
>>319
このスレの住人が口にすると迫力あるな。

322 :デフォルトの名無しさん:2012/07/18(水) 19:27:20.07
そうかい

323 :デフォルトの名無しさん:2012/07/18(水) 20:51:20.96
VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。

324 :292:2012/07/18(水) 20:56:44.84
誰のPCにでも入ってて使えるプログラム言語だからという理由でjavascriptを指定してたよ
別にHTMLファイルにするとかじゃなくて
アルゴリズムを再現したコードをメールに添付して送信するみたいな宿題だった
ちなみに情報が専門の学科は無い大学だったのでそういうことに

325 :292:2012/07/18(水) 21:04:23.79
ちなみな自分語りになるが
学科名的には電子情報工学科となってて情報系の授業を期待して入学したものの
(ちゃんと調べずに願書出した俺が悪いのだが)
情報とは名ばかりで情報系の授業はほとんど開講されず
電子系、特に半導体系の授業ばかりしかなかった
その大学わが母校はもう存在してないけどね

326 :デフォルトの名無しさん:2012/07/18(水) 21:13:34.30
本当ただの自分語りだな

327 :デフォルトの名無しさん:2012/07/18(水) 21:21:22.30
寂しい奴なんだろう。

328 :デフォルトの名無しさん:2012/07/18(水) 23:16:38.10
>その大学わが母校はもう存在してないけどね

津波で流されたのね

329 :デフォルトの名無しさん:2012/07/19(木) 01:35:32.86
つまり本格的な情報科学系の授業では無かったという事の証左だよな
まあ非情報系の学生だったらブラウザで誰でも実行環境が整うからあえてJavascriptでやるっていう意味もわかる気がする

330 :デフォルトの名無しさん:2012/07/19(木) 04:30:09.03
VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。

331 :デフォルトの名無しさん:2012/07/19(木) 07:32:51.17
なんでこんな頭の悪いのがこのスレにいるんだ?

332 :デフォルトの名無しさん:2012/07/19(木) 09:04:49.51
若者の 2ch 離れが進んでいるな

333 :デフォルトの名無しさん:2012/07/19(木) 19:06:58.62
2点が与えられたときその2点を結ぶ単純な経路(同じ頂点を通らない経路)
が2つ以上存在するかを判定するアルゴリズムと計算量を述べよ。

深さ優先探索とかでしょうか?

334 :デフォルトの名無しさん:2012/07/19(木) 19:12:15.02
宿題は宿題スレへ

335 :デフォルトの名無しさん:2012/07/19(木) 19:36:47.50
失礼しました

336 :デフォルトの名無しさん:2012/07/19(木) 21:33:34.33
>>331
どっちのこと?

337 :デフォルトの名無しさん:2012/07/19(木) 21:44:47.18
おそらく自問自答だろう

338 :デフォルトの名無しさん:2012/07/20(金) 16:42:44.97
二分探索木の平均高さが O(logN) の証明ってどういう風にやるんでしょうか?
アルゴリズムイントロダクションに書いてあるらしいのですが見当たりません。どのあたりでしょうか?

339 :デフォルトの名無しさん:2012/07/20(金) 16:53:14.03
>>338
2分探索の構造がわかれば少し考えればわかることだよ

340 :デフォルトの名無しさん:2012/07/20(金) 16:56:17.57
>>338
木 T が平衡なら、そのまま height(N) = 1 + height(N/2) で O(logN)でしょ。分割統治法

341 :デフォルトの名無しさん:2012/07/20(金) 17:29:31.19
手元の本にありましたのでもういいです。
お騒がせしました

342 :デフォルトの名無しさん:2012/07/20(金) 19:17:26.17
宿題は宿題スレへ

343 :デフォルトの名無しさん:2012/07/21(土) 03:01:26.56
3つのくっついてる円にこれまたくっついて囲まれてる円の半径を
求めるアルゴリズムってどうすればいい?

344 :デフォルトの名無しさん:2012/07/21(土) 03:14:49.30
3つの円はどういうくっつき方?
3つの円の半径はばらばら?

○○○

  ○
 ○○

345 :デフォルトの名無しさん:2012/07/21(土) 03:24:10.91
宿題は宿題スレへ
http://blogs.yahoo.co.jp/oka_yadokary/29892416.html

346 :デフォルトの名無しさん:2012/07/21(土) 03:24:54.06
343は外接・内接という言葉も知らなそうな雰囲気で困る。

347 :デフォルトの名無しさん:2012/07/21(土) 03:28:43.57
>>344
くっつき方は下の方
円の半径はバラバラ

348 :デフォルトの名無しさん:2012/07/21(土) 03:47:28.98
2本(3本)の双曲線の交点が共通接円の中心か

349 :デフォルトの名無しさん:2012/07/21(土) 14:31:42.96
互いに接する3つの円 に外接する円の半径の求め方?

350 :デフォルトの名無しさん:2012/07/21(土) 14:32:39.99
3つの円すべてと接する外接円は無理じゃね

351 :デフォルトの名無しさん:2012/07/21(土) 14:36:32.23
デカルトの円定理
http://aozoragakuen.sakura.ne.jp/taiwa/taiwaNch03/enteiri/node2.html

352 :デフォルトの名無しさん:2012/07/21(土) 14:36:40.22
にしてもスレチ。

353 :デフォルトの名無しさん:2012/07/21(土) 14:55:54.21
アルゴリズムでも何でもないなコレ

354 :デフォルトの名無しさん:2012/07/22(日) 10:15:52.04
プリムのアルゴリズムのヒープ版って
(E+V) log (E) ≒ Elog(E)ってあるけど (E+E) log (E) ≒Elog(E) が正しいと思う
挿入か削除のどっちも Elog(E) でしょ 最悪全枝を一回ずつ挿入と削除する必要があるんだから

355 :デフォルトの名無しさん:2012/07/25(水) 05:54:32.42
王様は王様でも頭が三つある王様はな〜んだ

356 :デフォルトの名無しさん:2012/07/25(水) 06:04:38.43
三頭王

357 :デフォルトの名無しさん:2012/07/25(水) 17:58:22.97
キングギドラ

358 : ◆VD2btbRbPs :2012/07/25(水) 21:41:00.81
大学の課題で二分探索木の高さを調べる実験とその結果を調べる実験が出たのですが
どうしたらいいですか

359 :デフォルトの名無しさん:2012/07/25(水) 21:54:46.35
そのようにプログラムを作って結果を表示すればいいのでは?

360 :デフォルトの名無しさん:2012/07/26(木) 16:24:57.70
宿題は宿題スレへ

361 :デフォルトの名無しさん:2012/07/26(木) 21:29:42.06
ほんとこういう質問するガキがムカつく
どうすればいいですか?って何だよ
そんな曖昧な質問で答えられると思ってんのかカスが
どこの底辺大学だか知らないが学費が無駄

362 :デフォルトの名無しさん:2012/07/26(木) 22:10:01.46
>>358
擬似乱数から最大の低周波成分を除くアルゴリズムを考案する。最大の低周波成分を除く操作を
繰り返すごとに2分探索木の高さが次第に平坦化することを実験・観察する。

363 :デフォルトの名無しさん:2012/07/26(木) 22:23:02.61
教授に不正してる奴がいたと報告しとく

364 :デフォルトの名無しさん:2012/07/26(木) 22:36:52.61
乱数が独立なら、Huffman木を作るといいよ!

365 :デフォルトの名無しさん:2012/07/27(金) 00:41:56.00
ハッシュのチェイン法の同一エントリのチェインの長さに制限があるやつはなんていうんだっけ?

366 :デフォルトの名無しさん:2012/07/27(金) 00:47:53.60
特にない

367 :デフォルトの名無しさん:2012/07/27(金) 01:03:18.89
半開きハッシュと名付けた

368 :デフォルトの名無しさん:2012/07/27(金) 01:38:15.37
こないだから宿題貼り付ける奴がちらほらいるが
そのどれも分からなかった俺は才能が無さ過ぎた

369 :デフォルトの名無しさん:2012/07/27(金) 08:00:24.64
>>361
黙れバカw
空気読んで答えやがれ


370 :デフォルトの名無しさん:2012/07/27(金) 08:13:45.67
↑お前が馬鹿

371 :デフォルトの名無しさん:2012/07/27(金) 09:41:12.30
馬鹿には無理

372 :デフォルトの名無しさん:2012/07/27(金) 10:18:48.93
>>370
>>371
バカはお前ら
お前らのパッパラパーなアルゴリズムでさっさと俺様を笑わせやがれ


373 :デフォルトの名無しさん:2012/07/27(金) 11:49:22.94
馬鹿には無理

374 :デフォルトの名無しさん:2012/07/27(金) 12:10:13.43
>>373
お前には無理と言うことかw

375 :デフォルトの名無しさん:2012/07/27(金) 19:08:10.29
>>374
お前が馬鹿

376 :デフォルトの名無しさん:2012/07/27(金) 19:54:35.27
     ____
    /∵∴∵∴\
   /∵∴∵∴∵∴\
  /∵∴∴,(・)(・)∴|
  |∵∵/   ○ \|
  |∵ /  三 | 三 |  / ̄ ̄ ̄ ̄ ̄
  |∵ |   __|__  | < うるせー馬鹿!
   \|   \_/ /  \_____
      \____/


377 :デフォルトの名無しさん:2012/07/27(金) 20:23:22.78
どーでもいい。

378 :記憶喪失した男 忍法帖【Lv=9,xxxP】 :2012/07/28(土) 07:59:18.69 ?2BP(3)
入力された内容は次のとおりです。
■件名: 日本のロボットトレーディングサイト「カブロボ」について
■ご意見・ご感想:
ロボットトレーディング、あるいはアルゴリズム取引トレーダーについて、少しは知識を得ました。その現状について知ったところ、やはり憂慮すべき事態だったため、意見申し上げます。

「カブロボ」というサイトを知りました。そのサイトについての意見です。政府として、このようなサイトを支援していただきたく思います。

アルゴリズム取引トレーダーとしては、株だけでなく、債券、為替取引にも当然対応するべきであります。
また、株、債券、為替取引は、現実に存在する二百か国以上の国や地域を網羅する必要があります。
それが賢いアルゴリズム取引トレーダーのするべきプログラムであり、
たった三百銘柄の仮想取引では、日本の投資家を育てるのに不適切だと思われます。海外銘柄を扱わないアルゴリズム取引トレーダーに魅力を感じません。

扱う銘柄を、全世界の株、債券、為替をすべて網羅する上級者向けのカブロボを立ち上げることを希望いたします。


379 :デフォルトの名無しさん:2012/07/28(土) 10:23:42.25
>>375
バカw


380 :デフォルトの名無しさん:2012/07/28(土) 11:39:47.47
>>324
その学科何年か前は違う名前じゃなかった?

381 :デフォルトの名無しさん:2012/07/28(土) 14:26:03.68
>>378
当事者が遊びで作ってるものに政府が金なんか出す訳ないだろ

382 :デフォルトの名無しさん:2012/07/28(土) 21:18:50.51
ぷよぷよのAIを作っているんですが窒息死します
どうすればいいですか

383 :デフォルトの名無しさん:2012/07/28(土) 22:12:51.40
ぷよぷよで強いAIってどうすんの?
http://toro.2ch.net/test/read.cgi/tech/1336825232/

384 :デフォルトの名無しさん:2012/07/29(日) 10:05:48.14
>>383
こんなスレあったんですか
ありです

385 :デフォルトの名無しさん:2012/07/31(火) 08:19:02.42
プッ

386 :デフォルトの名無しさん:2012/07/31(火) 09:24:11.53
ヨッ

387 :デフォルトの名無しさん:2012/07/31(火) 09:52:41.53
プッ

388 :デフォルトの名無しさん:2012/07/31(火) 21:35:14.84
ヨッ

389 : 【大吉】 :2012/08/01(水) 08:41:13.81
O(N)

390 :デフォルトの名無しさん:2012/08/02(木) 10:09:55.05
オナラプー

391 :デフォルトの名無しさん:2012/08/02(木) 20:47:04.14
ガベージ・イン/ガベージ・アウト:
善き人々が悪しきプログラムに手を染める時
http://practical-scheme.net/trans/gigo-1997-03-j.html

392 :デフォルトの名無しさん:2012/08/03(金) 20:45:11.38
ハッシュだけどチェイン法>開番地法なんだよね?でなければ溢れを気にする必要はないからね

ハッシュのチェインの長さに制限があるやつの削除、参照の計算量の解析ってどっかにない?

393 :デフォルトの名無しさん:2012/08/03(金) 20:56:13.76
「チェイン法>開番地法」
この意味は何?


394 :デフォルトの名無しさん:2012/08/03(金) 21:49:02.14
参照、追加、削除の計算量です

395 :デフォルトの名無しさん:2012/08/03(金) 22:12:44.83
A>B はAのほうが良い、ってことで

396 :デフォルトの名無しさん:2012/08/04(土) 18:35:46.31
>>392
> 長さに制限があるやつ
って何よ。
ハッシュ値が衝突した要素を格納するためのコンテナの計算量でいいんじゃないの?


397 :デフォルトの名無しさん:2012/08/05(日) 17:00:36.26
ハッシュ法って、均したらまともな実装ならO(1)にならにゃいかんのでは?

398 :1/4:2012/08/06(月) 18:50:54.98
アルゴリズム考えてもらえませんか。
恥ずかしながら、一応自分の考えたのも載せます。
ただ、絶対もっとスマートな解法があると思うのでよろしくお願いします。
ちなみに言語は PHP です(><)

【問題】
整数が二つ入った配列がいくつかあります。(配列の配列)
これは何らかの数列の範囲を表しています。

最初の数字が範囲の開始位置、二つ目の数字が範囲の長さ。

例えばこんな具合です。

$data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 2 ),
array( 4, 1 ),
array( 8, 2 ),
array( 10, 5 ),
array( 10, 6 )
);

------------- 長いので続きます --------------

399 :2/4:2012/08/06(月) 18:52:06.84
---続き---

抽象的に書くとこうなりますか。

$data = array(
array( a1, b1 ),
array( a2, b2 ),
--- 中略 ---
array( an, bn ),
);

a1からanは昇順にソート済みです。
同じ値の場合もあります。

b1からbnは1以上で不定です。

$data は、ある数列の 0番目から3スパン、2番目から1スパン、4番目から2スパン...という意味です。

ただし、この $data は範囲の重複の可能性があります。

実現したいアルゴリズムは、この $data が示す範囲を重複のない形で再定義することです。

400 :3/4:2012/08/06(月) 18:53:22.57
---続き---

例えばそれを実装した関数を linearize とした場合、

$newData = linearize( $data );

の結果は、

array(
array( 0, 3 ),
array( 4, 2 ),
array( 8, 8 )
);

でなくてはなりません。


401 :4/4:2012/08/06(月) 18:56:51.88
------続き------
こちらが自分が考えた関数です

function linearizedRange( $data ) {
$strage = array();
foreach( $data as $datum ) {
if( isset( $strage[$datum[0]] ) && $strage[$datum[0]] >= $datum[1] ) {
continue;
}
$strage[$datum[0]] = $datum[1];
}
foreach( $strage as $i => $v ) {
$strage[$i] = $v + $i;
}
$len = count( $strage );

if( $len > 1 ) {
$last = null;
foreach( $strage as $i => $v ) {
if( null === $last ) {
$last = $i;
continue;
}


402 :5/4:2012/08/06(月) 18:58:01.19
------続き------
すいません、予定より1レス多くなりました。
関数の続きです。これで最後です。

if( $strage[$last] >= $i ) {
if( $strage[$last] < $v ) {
$strage[$last] = $v;
}
unset( $strage[$i] );
} else {
$last = $i;
}
}
}

$data = array();
foreach( $strage as $i => $v ) {
$data[] = array( $i, $v - $i );
}
return $data;
}




403 :デフォルトの名無しさん:2012/08/06(月) 20:04:16.15
$data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 2 ),
array( 4, 1 ),
array( 8, 2 ),
array( 10, 5 ),
array( 10, 6 )
);



array(
array( 0, 3 ),
array( 4, 2 ),
array( 8, 8 )
);

404 :デフォルトの名無しさん:2012/08/06(月) 20:09:14.78
理屈がよくわからん

405 :デフォルトの名無しさん:2012/08/06(月) 20:14:28.31
できた!


function linearizedRange( $data ) {
$n = -1;
$result = array();
foreach( $data as $datum ) {
if ($dataum[0] > $n) {
$result[] = $dataum;
$n = $dataum[0] + $dataum[1];
}
}
return $result;
}

406 :デフォルトの名無しさん:2012/08/06(月) 20:15:48.26
でたらめを教える悪い例

407 :デフォルトの名無しさん:2012/08/06(月) 20:20:34.70
DPでいけそう
Viterbトレリスを作って一発

408 :デフォルトの名無しさん:2012/08/06(月) 20:23:59.40
ならばこうか!

function linearizedRange( $data ) {
$n = -1;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($dataum[0] > $n) {
if ($t !== null) {
$t[1] = $dataum[0] - $t[0];
$result[] = $t;
}
$t = $dataum;
$n = $dataum[0] + $dataum[1];
}
}
$p = array_pop($data);
$t[1] = $p[0] + $p[1] - $t[0];
$result[] = $t;
return $result;
}

409 :デフォルトの名無しさん:2012/08/06(月) 20:25:08.27
動かないコードなど無意味

410 :デフォルトの名無しさん:2012/08/06(月) 20:28:20.86
うおりゃ!スペルミス直したぞ!


function linearizedRange( $data ) {
$n = -1; $m = 0;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($datum[0] > $n) {
if ($t !== null) {
$t[1] = $datum[0] - $t[0];
$result[] = $t;
}
$t = $datum;
$n = $datum[0] + $datum[1];
}
if ($datum[0]+$datum[1]>$m) {
$m = $datum[0] +$datum[1];
}
}
}
$t[1] = $m - $t[0];
$result[] = $t;
return $result;
}

411 :デフォルトの名無しさん:2012/08/06(月) 20:30:11.37
動かないぞ

412 :デフォルトの名無しさん:2012/08/06(月) 20:31:20.11
括弧が一つ多かった!直したぞ!


function linearizedRange( $data ) {
$n = -1; $m = 0;
$t = null;
$result = array();
foreach( $data as $datum ) {
if ($datum[0] > $n) {
if ($t !== null) {
$t[1] = $datum[0] - $t[0];
$result[] = $t;
}
$t = $datum;
$n = $datum[0] + $datum[1];
}
if ($datum[0] + $datum[1] > $m) {
$m = $datum[0] +$datum[1];
}
}
$t[1] = $m - $t[0];
$result[] = $t;
return $result;
}

413 :5/4:2012/08/06(月) 22:54:42.75
>>412 さん、さっそくありがとうございますm(__)m
凄く短いコードなので感動しました(^-^)

が、どこか不具合がある模様です(-_-;)

例題の
$data = array(
array( 0, 3 ),
array( 2, 1 ),
array( 4, 5 ),
array( 5, 1 ),
array( 10, 2 ),
array( 12, 3 ),
array( 12, 4 )
);
の答えが

414 :398:2012/08/06(月) 22:55:22.08
Array
(
[0] => Array
(
[0] => 0
[1] => 4
)

[1] => Array
(
[0] => 4
[1] => 6
)

[2] => Array
(
[0] => 10
[1] => 6
)

)
になってしまいました(´・ω・`)

415 :398:2012/08/06(月) 22:56:52.95
Array
(
[0] => Array
(
[0] => 0
[1] => 4
)

[1] => Array
(
[0] => 4
[1] => 6
)

[2] => Array
(
[0] => 10
[1] => 6
)

)
になってしまいました(´・ω・`)

416 :398:2012/08/06(月) 23:11:31.65
別のデータを用いて模式図を書くとこうなります

( 0, 3 ) … データ1
( 2, 1 ) … データ2
( 4, 1 ) … データ3
( 5, 1 ) … データ4


01234567.... 数列
---------------------
***___________データ1
__*___________データ2
____*_________データ3
_____*________データ4

***_**________求める答え(V)

V1 = (0,3)
V2 = (4,2)

こうしてみるとOR演算ですね

417 :デフォルトの名無しさん:2012/08/06(月) 23:49:58.47
#PHPのことはわからんのに、適当に投げてみる
#どうせどっかでエラーが出る

function linearizedRange( $data ) {
$max = $min = $data[0][0];
$result = array();

foreach( $data as $datum ) {#----

if ( $datum[0] > $max ) {#====ギャップ感知
$result[] = array( $min, $max - $min );
$min = $datum[0];
}#====

if ( $datum[0] + $datum[1] > $max ) {#====
$max = $datum[0] + $datum[1];
}#====

}#----foreach

$result[] = array( $min, $max - $min );
return $result;
}

418 :398:2012/08/07(火) 00:47:35.30
>>417

m(__)m

もう、ほんとうに感謝感謝感謝です。
ありがとうございます。
しかもそのまんまコピペでOKでした。

>>417 さん以外の皆様もありがとうございました。
どこか別の場所で恩返しできるといいです。

419 :398:2012/08/07(火) 00:53:50.40
あぁ、そうかぁ、

$result に格納するタイミングは

datum[0] > $max

のときとループを抜けた最後だけでいいわけか・・・

すごくなるほど。

420 :398:2012/08/07(火) 01:03:25.12
あと、元のデータが ( 開始位置, 幅 ) だったので
それをループの中でいったん終了位置を $max として求めているのですね。

ということは、元のデータを ( 開始位置, 終了位置 ) として同じコストで作成できるとするならば、
それを採択した方がより良いアルゴリズムになるのですね。

元データの取得方法を再検討してみます。m(__)m

421 :デフォルトの名無しさん:2012/08/07(火) 02:43:10.51
宿題は宿題スレって約束忘れちゃったのかおまえら

422 :デフォルトの名無しさん:2012/08/09(木) 18:31:48.66
ヒープソート、書き換わってるなw

423 :デフォルトの名無しさん:2012/08/10(金) 07:22:34.38
ホントだ

424 :デフォルトの名無しさん:2012/08/14(火) 13:57:01.43
あらゆる状況や環境を無視して質問するんだけど
STXとETXで囲まれたバイト列を取得 というとき、

<STX>unko<STX>chinko<ETX>
というならびになっちゃってるときは chinko オンリーが正解か
unko<STX>chinko が正解か、どっちがセオリーかなぁ

425 :デフォルトの名無しさん:2012/08/14(火) 14:05:59.01
最長一致にするか最短一致にするかは
セオリーというより定義の問題だ

426 :デフォルトの名無しさん:2012/08/14(火) 14:06:25.67
後者。

/*foo/*bar*/ だってコメントアウトされるのは foo/*bar でしょう。

427 :デフォルトの名無しさん:2012/08/14(火) 14:20:48.63
>>426
そっちの方が作るのも楽なんだけどさ
なんでわざわざ囲ってんのか という根源的なとこを思うと
chinkoオンリーが正解な気がするんだよな

428 :デフォルトの名無しさん:2012/08/14(火) 15:07:33.07
>>427
プロトコル定義次第。
・<stx>で始まり、<etx>で終わるまで全てがデータ(unko<stx>chinko)
・<stx>で始まり、<etx>以外の制御コードを含まない区間がデータ(chinko)
・<stx>で始まり、<etx>以外の制御コードを無視した区間がデータ(unkochinko)
・<stx>で始まり、<etx>で終わるまでがデータだからネストを認め、内側から有効とする(chinko)(unkoはペンディング)
・<stx>で始まり、<etx>以外の制御コードが出現したらその後のデータは無効(データなし)
ちょっと考えただけでもこれだけバリエーションが作れる。
要は、エラーに対する強度の問題。

429 :デフォルトの名無しさん:2012/08/14(火) 15:10:09.72
>>427
<stx>が出現したら出力インデックスを初期化するだけだから、作る手間は殆ど変わらないだろ。

430 :デフォルトの名無しさん:2012/08/14(火) 15:32:23.36
>>428
STXとETXに挟まれたもの という定義なんか作った理由って
開始と終了を検知したいということなんだから、
STXまたはETXの見逃しを恐れるべきですね

ということは、STXのあとETXが来ないでSTXきちゃったのは
ETXを読み飛ばしちゃったと思った方がいいんだよな、きっと
つまり、とりあえずchinkoのみを採用すべきとすべきかなぁ

431 :デフォルトの名無しさん:2012/08/14(火) 16:03:01.12
>>430
再入可能かどうかが分からないとなんとも言えないだろ

432 :デフォルトの名無しさん:2012/08/14(火) 16:13:36.40
そうか。 再入可能かどうかがキモになるのか。

433 :デフォルトの名無しさん:2012/08/20(月) 12:52:16.26
AVL木の回転って適当すぎない?
別に回転じゃないじゃん。
ただ引き上げてるだけで、入れ替えたりしてる時点で
回転ではないだろ。


434 :デフォルトの名無しさん:2012/08/20(月) 17:32:15.47
死ねゴミ共がw

435 :デフォルトの名無しさん:2012/08/20(月) 20:27:00.20
>>433
subtreeのrotationじゃなくて、nodeのrotationなんで。
「入れ替え」くらいが適切な訳だったという感じでしょうかぁ↓

436 :デフォルトの名無しさん:2012/08/21(火) 09:13:13.56
バカばっかw

437 :デフォルトの名無しさん:2012/08/21(火) 09:44:31.25
>>435
いいね!

438 :デフォルトの名無しさん:2012/08/22(水) 00:06:18.81
お知恵をお貸しください。

xy平面上にランダムに配置された複数個の点があったとき、
それらを線で結ぶとして、結んだ結果が網の目のように見える
ようなアルゴリズムってありますでしょうか。

完全に見た目だけが目的なので自分でも要件が絞り込めて
いないのですが、網の目のように見えるための要件は
おそらく次のようなものでしょう。

・全ての点が2個以上の他の点と結ばれている
・線同士が交差しない
・近い点同士が結ばれていて、遠い点同士は結ばれない
・線で囲まれた図形は三角形ないし四角形を構成し、五角形以上にはならない

よろしくお願いいたします。

439 :デフォルトの名無しさん:2012/08/22(水) 00:11:11.92
ドロネー図でggr

440 :デフォルトの名無しさん:2012/08/22(水) 23:00:26.94
>439
ありがとうございます。

ttp://tercel-sakuragaoka.blogspot.jp/2011/06/processingdelaunay_3958.html
↑ここを参考にして実装を進めようと思うのですが、この方法だと、
一度完成したドロネー図から点を削除して線を引きなおすには、
再度(その点を除いた点群を入力として)ゼロから作図しなおす
しか無いのでしょうか?

441 :デフォルトの名無しさん:2012/08/30(木) 18:01:25.35
B木がよく分かりません。誰か簡単に説明してくれませんか?

442 :デフォルトの名無しさん:2012/08/30(木) 18:23:37.01
>>441
B木は多分岐の平衡木。
ノードは最大M個のサブノードとM-1個の値を保持する。
ノードの値がM-1個を超えるとノードの分割が行われる。

443 :デフォルトの名無しさん:2012/08/31(金) 00:00:52.49
2分平衡木の存在意義がゼロに

444 :デフォルトの名無しさん:2012/08/31(金) 20:16:21.92
ゼロどころではない。もはやマイナスだ。

445 :441:2012/08/31(金) 20:35:10.27
>442
ありがとうございます。

プログラム文がきわめて長いので、使いこなせません…。

446 :デフォルトの名無しさん:2012/09/01(土) 03:33:46.99
>>445
プログラム使うだけだったら実装の細部まで理解する必要ないっしょ。
Addメソッドを呼んだらが値を追加できてGetメソッドを呼んだら値を
取得できるというようなことさえわかってればじゅうぶんっしょ。

447 :445:2012/09/01(土) 23:51:43.84
>446
そうですかねえ。確かに文が400行以上あるので(コメントも含めて)、理解は無理っぽいですねえ。

二度目ですが、シェルソートが挿入ソートより速くなる理由を誰か教えて頂けませんか?

448 :デフォルトの名無しさん:2012/09/02(日) 00:27:54.32
ランダムに並んだデータを挿入していくと
比較回数の期待値が挿入1回に対しソート済みデータの半分になるけど

先頭に近そうなデータから挿入していけば
比較は後ろの方の1,2回だけとなることが期待できるってことでは

449 :デフォルトの名無しさん:2012/09/02(日) 00:28:30.47
1,2回だけ→ほとんどが1,2回くらい

450 :デフォルトの名無しさん:2012/09/02(日) 00:43:09.47
>>447
語尾が腹立つから教えてあげない

451 :447:2012/09/02(日) 01:05:24.33
>448-449
ありがとうございます。けれどやっぱり納得できないというか…。最終ソートの前で既に結構比較・交換にコストがかかってる気がして。

>450
何でですかあ?そんな事言わないで下さいよお。

452 :デフォルトの名無しさん:2012/09/02(日) 06:09:50.86
>>451
あんまりふざけたこといってるとぶちぎれるゾ(ゝω・)vキャピ

453 :451:2012/09/02(日) 23:53:28.52
>452
怒ったらダメですう。貴方に足りないのはCaですよお。(特に深い意味はない)

454 :デフォルトの名無しさん:2012/09/03(月) 05:10:27.93
つまんね

455 :デフォルトの名無しさん:2012/09/03(月) 06:29:18.19
例えば挿入ソートだと比較回数は期待値でだいたいこんな感じだろう
右から+の箇所で比較していって*に収まるイメージ(平均なので真ん中)
-----------------------------------*+++++++++++++++++++++++++++++++++++

でもシェルソートのごとく予め4つのグループに分けると比較回数がガクッと減らせる
-----------------------------------*---+---+---+---+---+---+---+---+---

さらに前段階で13のグループに分ければ比較回数が格段に減る
-----------------------------------*------------+------------+---------

いくら前段階というプロセス数が増えるとはいえ、比較や交換回数が小さいわりに
好位置へデータを移動させておくことができるから、全体としてみれば
効率が良くなるんだろう

456 :453:2012/09/06(木) 16:51:56.41
>455
しかし何故そうなるのかが分かりません。

今ヒープソートを勉強してますが、これはさらに分かりません。

457 :デフォルトの名無しさん:2012/09/06(木) 18:32:25.30
>>456
挿入ソートでは要素数が多くなると遠くまでテケテケと要素を1個ずつ移動せにゃならんから
超大変。シェルソートでは要素数が増えても離れた要素を交換することで遠くへ移動するときの
コストが減らせちゃうわけ。ゆえに要素数が増えるほどシェルソートが挿入ソートより
速くなるはずよ。

ヒープソートは2分木作っちゃうやつだろ、わかるだろ。

458 :デフォルトの名無しさん:2012/09/08(土) 19:22:54.12
基数ソートって分かりやすいしすばらしいですね。

459 :デフォルトの名無しさん:2012/09/10(月) 20:53:39.37
アルゴリズムとデータ構造の質問なんですけど、ここでいいですか?

   1.2次元以上で、無限に広がるユークリッド空間があります。
   2.空間上に、赤い砂粒と黒い砂粒を好きなだけ振りかけます。
   3.ここより先では、砂粒を追加しません。
   4.空間上の任意の座標を選びます。
   5.選んだ座標からユークリッド距離が最も小さい砂粒の、色は何色?

安定じゃなくてもokです。
こういう状況で、良い検索アルゴリズムってありませんか?

460 :デフォルトの名無しさん:2012/09/10(月) 21:04:04.91
> 安定じゃなくてもok

って、等距離に赤も黒もあった場合は、返す値は赤でも黒でも良いと言いたいのか?

461 :デフォルトの名無しさん:2012/09/10(月) 21:07:23.58
1ビットごとに次元を変えていくやり方なら地図サービスとかで使われている

462 :デフォルトの名無しさん:2012/09/10(月) 21:08:15.28
>>461
kwsk


463 :デフォルトの名無しさん:2012/09/10(月) 21:25:53.08
>>460
あ、その通りです。安定ソートっぽい意味でした。すみません。

等距離に、または同じ座標に、赤と黒があるときは、
答えは赤でも黒でも良い、検索のたびに答えが変わっても良い、
ってことです。

あと、例えば等距離に黒が複数ある場合、答えは「黒」と返すだけでokです。
アルゴリズムがどの座標の「黒」を指したのか、
それはアルゴリズム利用者に知らせる必要はないです。

>>461
1ビットごとに??
すみません、ちょっと想像がつきません…。
どんな仕組みなんでしょうか?

464 :デフォルトの名無しさん:2012/09/10(月) 22:52:42.26
>>463
1ビットずつ混ぜるんだよ。分かれよ。
x座標とy座標をそれぞれ32ビット整数値で表現するとして
x = { x31, x30, ... x1, x0 }
y = { y31, y30, ... y1, y0 }
だとするだろ。x31が上位ビットでx0が下位ビットな。
それを混ぜると、
z = { y31, x31, y30, x30, ..., y1, x1, y0, x0 }
という64ビット整数値になるわけだ。
地図系サービスはだいたいこんなのが多い。


465 :デフォルトの名無しさん:2012/09/10(月) 22:58:35.49
>>464
で? その64ビット整数値をどうする気だよ?

466 :デフォルトの名無しさん:2012/09/10(月) 23:01:13.24
砂粒座標データはどう整理された状況で提供されるのかが気になる
あるいは事前にデータを整えていいのか否かも

467 :デフォルトの名無しさん:2012/09/10(月) 23:06:48.73
>>465
ソートしておけば、upper_bound lower_boundである程度漠然とした領域が拾えるだろ。
全座標の重さが平等でないと使えないやり方だけどな。
そういう想定を置けないなら諦めてR-Tree書けだな。

468 :デフォルトの名無しさん:2012/09/10(月) 23:54:10.30
>>459
最近傍探索
http://ja.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E5%82%8D%E6%8E%A2%E7%B4%A2

2を一度だけ行い4を繰り返すのなら
3で同色の砂に囲まれている砂を取り除く方が効率が良いです。

469 :デフォルトの名無しさん:2012/09/11(火) 01:21:02.23
皆様ご回答ありがとうございます。

>>467
x,yそれぞれ2bitで図を書いてみたら、なんとなく解りました。
座標は実数を想定していたのですが(説明不足ですみません)、
固定小数点数に近似すれば使えるんでしょうか。ありがとうございます。
あと、R-Treeはちょっと気になってたので、Wikipediaあたりから読んでみます。

>>468
おっしゃるとおり1〜2は1回だけ実行、4以降は繰り返し実行です。
最近傍探索は今日は寝るので明日読みます、ごめんなさい…。

>>459 をもう1回整理して書きます。

   1.2次元以上で、無限に広がるユークリッド空間があります。
   2.空間上に、赤い砂粒と黒い砂粒を好きなだけ振りかけます。
      砂粒は実数の座標を持ちます。
      砂粒に大きさは無く、また同じ座標に複数の砂粒が重なることもあります。
   3.ここより先では、砂粒を追加しません。
      1〜3は1回しか実行しません。
      振りかけた数、各色ごとの数、n回目に振りかけた砂粒の情報(座標や色)はいつでもO(1)で調べることができます。
      ここまでは、砂粒のコピーをとってソートしたり、時間の掛かる計算もokです。
      1〜3で与えられたり生成した情報は、もし必要無ければこの段階までに破棄できます。
   4.空間上の任意の座標を選びます。
   5.選んだ座標からユークリッド距離が最も小さい砂粒の、色は何色か返します。
      ただし、等距離または同一座標のときは赤黒どちらを返しても良く、
      また、後で同一の検索をしたとき答えが変わっても良いです。
      赤黒どちらかを返すだけで、座標を返す必要はありません。
   6.4〜5を繰り返します。

なんかめんどくさそうですよね…。自分でも考えてみます。

470 :デフォルトの名無しさん:2012/09/24(月) 19:34:54.06
「Cによるアルゴリズムとデータ構造」(昭晃堂)って本いいですか?大学で教科書として使われてたんですが。

471 :デフォルトの名無しさん:2012/09/24(月) 19:47:47.61
その本今も持ってる
どっかにしまってあるわ
もう何年も前だから覚えてない

472 :デフォルトの名無しさん:2012/09/27(木) 23:34:39.11
平面上に複数の点があり、各点を中心とした円で塗り潰すとした場合に、
『塗られていない領域を最小』にするために、最適な相互に接する円の半径を
求めるアルゴリズムってありますか?

====以下、挫折した案====

近傍の2点間の中点を、仮りの半径の最小値として求めて順次他の点
との中点を求めいって半径の最小値を更新して、これを初期値とする。

この時点では、最小値を更新したことで、他と接することが無くなった
円が生じるので、この半径を再度増加させれば...

とか思ったのですが、局所的な部分しか見えていないし、そもそも
上で求めた最小値よりも、更に小さな半径とした方が適した場合も
ある様にも思います。

473 :デフォルトの名無しさん:2012/09/28(金) 00:06:32.99
>>472
こういうこと?
1.それぞれの円の半径はバラバラである
2.円と円が重なってはならない

474 :デフォルトの名無しさん:2012/09/28(金) 00:12:29.39
>>472
> 『塗られていない領域を最小』

つまり一辺の長さが l の正三角形の各頂点が与えられた場合、それぞれ半径 (l, 0, 0) の円が欲しいわけだな?

475 :デフォルトの名無しさん:2012/09/28(金) 00:20:03.90
凸計画問題として解いてしまうとか

476 :デフォルトの名無しさん:2012/09/28(金) 00:24:20.85
>>472
>>473 が条件であるとして
外周部にあたる点の半径を出来る限り大きくするのが有効に思える

他の点との距離の最小値が最大となる点で最大の円を描くようにすればよさげ

477 :デフォルトの名無しさん:2012/09/28(金) 00:47:33.75
あれか?水着の女の子の写真をうまい具合に水着部分だけ隠してあたかも裸に見えるっていうアレを作ろうとしてるのか?

478 :デフォルトの名無しさん:2012/09/28(金) 00:50:54.89
全然違うだろ・・・

479 :デフォルトの名無しさん:2012/09/28(金) 01:41:17.58
『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう! - YouTube
http://www.youtube.com/watch?v=Q4gTV4r0zRs&feature=youtu.be

で、肝心のアルゴリズムってなんなのよ

480 :デフォルトの名無しさん:2012/09/28(金) 01:43:49.54
点の集合をどこから持ってくるのかな
とおもってたら
>477


481 :デフォルトの名無しさん:2012/09/28(金) 01:48:30.30
>>479
お姉さんがやってるのは総当りじゃないかな
こんなん


C言語なら俺に聞け(入門編)Part 107
http://toro.2ch.net/test/read.cgi/tech/1347156509/187

187 名前:186[sage] 投稿日:2012/09/14(金) 22:16:01.89
>>186 に一番簡単な袋小路の判定を追加してさらに倍速

http://codepad.org/k9Dw2VA5

482 :デフォルトの名無しさん:2012/09/28(金) 01:49:43.41
>>481
お、そっちのスレで盛り上がってたのか。dクス

483 :デフォルトの名無しさん:2012/09/28(金) 01:57:35.54
>479
その高速アルゴリズムが正しいかどうか
検証するのに6年掛かるんですね判ります


484 :デフォルトの名無しさん:2012/09/28(金) 02:12:14.36
9x9までは正しい解が出せたとしても10x10でも果たして正しい解が出せたかどうかは

485 :デフォルトの名無しさん:2012/10/04(木) 21:23:52.08

任意の符号なし32bit値 Aに対して
下の関係を成り立たせる 32bit値を求めれるもの?

A = x + BitReverse(x)

BitReverseはビット逆順演算
31b ⇔ 0b
30b ⇔ 1b
   ・・・・
1b ⇔ 1b
0b ⇔ 31b


486 :デフォルトの名無しさん:2012/10/04(木) 21:30:03.12
よく意味が分からない

487 :デフォルトの名無しさん:2012/10/04(木) 21:32:58.97
xを0x00000000〜0xFFFFFFFFまでのAのリストを作ればいいんじゃね

488 :デフォルトの名無しさん:2012/10/04(木) 21:43:33.99
具体例で考えればいい
A=1のときのxを求める
A=2のときのxを求める

489 :デフォルトの名無しさん:2012/10/04(木) 21:44:05.80
>>486
分かりづらかったかも、すみません。

x + ビット反転(x)の結果が0x3476edc0のとき、
xの値を求めるには?

ビット反転は 10110010 → 01001101 のような感じの処理(この例は8ビットですけど)

490 :デフォルトの名無しさん:2012/10/04(木) 21:45:22.64
難しそうなアルゴリズムだ

491 :デフォルトの名無しさん:2012/10/04(木) 21:59:08.08
連投すみませんです。自分の説明に絶望した・・。

unsigned int A;
unsigned int x; // ?

A = x + reverse_bits(x);

if (A == 0x3476edc0) {
// この条件を満たすxを求めるには・・?任意のAについてどうやって計算すればいいか・・・
}

// 1101:0010 -> 0100:1011 ビット順序反転する関数
unsigned int reverse_bits(unsigned int v){
 v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
 v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
 v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
 v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
 v = ( v >> 16 ) | ( v << 16);
 return v;
}

492 :デフォルトの名無しさん:2012/10/04(木) 22:14:13.06
>>485
無理だな。
A と X は 2^32 通り、X + Rev(X) も 2^32 通り。
ただし、X + Rev(X) はオーバーフローする分、実際の数は少ない。
よって、任意の A に対して X を求めることは無理。

493 :デフォルトの名無しさん:2012/10/04(木) 22:15:25.15
訂正。
○ X + Rev(X) は 2^32 通り以下。

494 :デフォルトの名無しさん:2012/10/04(木) 22:15:49.33
Javaならオーバーフローしない!

495 :デフォルトの名無しさん:2012/10/04(木) 22:16:38.89
下位ビットが立ってたら上位ビットも立つ形になるんだし和で非対称になったとしても最下位ビットが

496 :デフォルトの名無しさん:2012/10/04(木) 22:17:39.08
更に訂正。
○ X + Rev(X) は 2^31 通り以下。

X + Rev(X) = Rev(X) + Rev(Rev(X)) だから。

497 :デフォルトの名無しさん:2012/10/04(木) 22:22:18.63
>>492
オーバーフロー分は切り捨てて良いのですが・・・無理でしょうか?
A = (unsigned int) ( x + reverse_bits(x) );

1元1次方程式に見えるので解があるような、
いやでも無いような・・・悶々としてます。

498 :デフォルトの名無しさん:2012/10/04(木) 22:22:59.96
A = 0xFFFF FFFF みたいな形が一番、式を満たす X の数多いようだな。

499 :デフォルトの名無しさん:2012/10/04(木) 22:23:25.14
496の対称性があるから無理じゃね

500 :デフォルトの名無しさん:2012/10/04(木) 22:24:25.45
さっさと487のいうように一覧にして全数字を網羅できるかチェックすれば早いのよ!(それじゃアルゴリズムじゃありませんが><)

501 :デフォルトの名無しさん:2012/10/04(木) 22:27:35.73
>>497
492,496を読んで、それでも一般には無理だと理解できない脳が怖い。

502 :デフォルトの名無しさん:2012/10/04(木) 22:31:08.08
496の言う対称性が分かればできる数字がほぼ半分しかないってことがわかる

503 :デフォルトの名無しさん:2012/10/04(木) 22:33:39.78
A=X+Rev(X)なら
Rev(X)=Yとすると
A=Y+Rev(Y)=X+Rev(X)が成り立つ
つまり同じ解を出すXが2通りあるってこと

504 :デフォルトの名無しさん:2012/10/04(木) 22:38:19.54
>>503
うーん そうですね。
xとAが1対多の関係がある時点でダメなのか・・・
皆さんありがとうです

505 :デフォルトの名無しさん:2012/10/05(金) 00:07:59.21
>>503
それは間違い

506 :デフォルトの名無しさん:2012/10/05(金) 00:58:37.93
簡単のため、2ビットの場合で考えてみる。

A = 00のときX = 00
A = 01のとき解なし
A = 10のときX = 11
A = 11のときX = 01,10

解があれば解を返し、なければ解なしと出力するアルゴリズムって総当たり探索になるのかな?
それとも代数的に解けるのだろうか?

507 :デフォルトの名無しさん:2012/10/05(金) 01:01:28.13
オーバーフロー切り捨てを考慮するとなるとかなり複雑になりそう

508 :デフォルトの名無しさん:2012/10/05(金) 01:08:57.90
A=000 X=000
A=001 X=011,110
A=010 X=101
A=011 X=
A=100 X=010
A=101 X=001,100
A=110 X=111
A=111 X=

509 :デフォルトの名無しさん:2012/10/05(金) 01:11:02.77
で、これ求めて何に使うわけ?

510 :デフォルトの名無しさん:2012/10/05(金) 01:14:16.72
0ビット目だけは下位ビットからの繰り上がりで1に出来ないことから
Aの0ビット目をみて

511 :デフォルトの名無しさん:2012/10/05(金) 01:15:22.75
>>509
FFT関係だと思います

512 :デフォルトの名無しさん:2012/10/05(金) 01:17:16.96
>>510
11は解があるよ

513 :デフォルトの名無しさん:2012/10/05(金) 01:21:21.45
A=0000 X=0000
A=0001 X=
A=0010 X=1001
A=0011 X=
A=0100 X=
A=0101 X=0111,1110
A=0110 X=0010,0100
A=0111 X=
A=1000 X=1011,1101
A=1001 X=0001,1000
A=1010 X=
A=1011 X=
A=1100 X=0110
A=1101 X=
A=1110 X=1111
A=1111 X=0011,1100,0101,1010

514 :デフォルトの名無しさん:2012/10/05(金) 01:22:28.99
フーリエ変換か

515 :デフォルトの名無しさん:2012/10/05(金) 01:27:14.69
nビット整数だとnが奇数でも偶数でも全ビットが1のものを除けば対称になってる

516 :デフォルトの名無しさん:2012/10/05(金) 01:28:20.19
その対称の端のXはオールビットが0か1

517 :デフォルトの名無しさん:2012/10/05(金) 01:31:36.52
>>513
これシンプルな計算で解の有無が判定できるのかね・・・不規則に見えるが

518 :デフォルトの名無しさん:2012/10/05(金) 03:45:27.52
^ をべき乗の記号として
2^((n+1)/2) 通りチェックする方法なら分かる

519 :デフォルトの名無しさん:2012/10/05(金) 03:49:10.90
A=1111 X=0011,1100,0101,1010,0110,1001,0111,1000,0001,1110,1101,0010,1011,0100,1111,0000

520 :デフォルトの名無しさん:2012/10/05(金) 03:54:10.07
>>519
反転じゃなくて逆順だよ?

521 :デフォルトの名無しさん:2012/10/05(金) 04:00:24.13
489 デフォルトの名無しさん [] 2012/10/04(木) 21:44:05.80 ID: Be:
    >>486
    分かりづらかったかも、すみません。

    x + ビット反転(x)の結果が0x3476edc0のとき、
    xの値を求めるには?

    ビット反転は 10110010 → 01001101 のような感じの処理(この例は8ビットですけど)

522 :デフォルトの名無しさん:2012/10/05(金) 04:16:49.17
質問者は反転と逆転の違いが

523 :デフォルトの名無しさん:2012/10/05(金) 04:19:19.69
例出すのも下手
わざとやってるだろ

524 :デフォルトの名無しさん:2012/10/05(金) 12:41:22.64
解いてみた
諸事情により 31 bit まで
#module
#defcfunc bitreverse int num, int bit, local rev
repeat bit
rev=(rev<<1)|((num>>cnt)&1)
loop
return rev

#deffunc solve array result, int num, int bit, local result_num, local u_, local l, local m, local n
dim result

n=1<<((bit+1)/2)
m=(1<<bit)-1
repeat n
l=cnt
u_=(num-l)&(n-1)
x=l|bitreverse(u_, bit)
if ((x+bitreverse(x, bit))&m)=num {
result.result_num=x
result_num++
}
loop
return result_num
#global

solve result, $ff, 8
repeat stat
mes strf("%x", result.cnt)
loop

525 :デフォルトの名無しさん:2012/10/05(金) 15:18:10.35
HSP?

526 :デフォルトの名無しさん:2012/10/05(金) 15:36:02.53
アルゴリズム記述用の抽象言語みたいなのってないのかな

527 :デフォルトの名無しさん:2012/10/05(金) 15:48:32.32
32bit全探索する気か

528 :デフォルトの名無しさん:2012/10/05(金) 15:50:40.72
8bitくらいまで>>513のように羅列していって何らかの傾向や法則性が無いか確かめられたらいいんだけどな

529 :デフォルトの名無しさん:2012/10/05(金) 16:50:50.02
しょうがねぇなぁ〜
http://codepad.org/Kkm8uPyR


530 :デフォルトの名無しさん:2012/10/05(金) 18:11:37.70
>>526
片言Algol知らんのか?

531 :デフォルトの名無しさん:2012/10/05(金) 20:26:48.63
"片言Algol"でググっても何なのか出てこないんですけどー"片言Algol"って何ですかー?

532 :デフォルトの名無しさん:2012/10/05(金) 20:54:44.01
片言のAlgol

533 :デフォルトの名無しさん:2012/10/05(金) 21:15:37.12
pidgin ALGOLも知らんとは!(怒

534 :デフォルトの名無しさん:2012/10/08(月) 00:42:46.73
pidgin ・・・ 混成語

他の言語と混ぜて使うってこと?よけい混乱しないか?

535 :デフォルトの名無しさん:2012/10/08(月) 07:19:41.75
>>534
ある言語の、外人 植民地人向けカタコトOKバージョン。

満州国を作ったあたりでpidgin日本語を作ってた。
語尾を「〜アル」で統一とか。

廃れてしまったがモノはちゃんと完成し、教育もされたようだ。
マンガの中国人が「〜アルよ」と言うのはその名残らしい。

536 :デフォルトの名無しさん:2012/10/08(月) 08:39:37.95
ゼンジー北京ってまだ生きてんの?

537 :デフォルトの名無しさん:2012/10/08(月) 19:17:57.21
http://codepad.org/dZ6OuG1e
ghc
f "101010" --2進
fx "12abcd"--16進
虫食い算を解く要領で1桁ずつ特定しています

538 :537:2012/10/09(火) 00:34:47.45
http://codepad.org/ETbL5UUF
32bitでエラーに成るのを修正
A=B+(reverse B)
rx B --> A
fx A --> B
rx "123456" -->"7c609e"
fx "7c609e" -->["7a3440","7a2c40","723450","722c50","6a3448","6a2c48","623458","622c58","5a3444
","5a2c44","523454","522c54","4a344c","4a2c4c","42345c","422c5c","3a3442","3a2c4
2","323452","322c52","2a344a","2a2c4a","22345a","222c5a","1a3446","1a2c46","1234
56","122c56","0a344e","0a2c4e","02345e","022c5e"]

539 :デフォルトの名無しさん:2012/10/14(日) 18:17:20.75
データ構造とアルゴリズムと設計パターンは、
ソフトウェア開発に必須の技術

540 :デフォルトの名無しさん:2012/10/14(日) 19:30:55.13
B木のようなプログラム文も、書けるようにならなければなりませんか?

541 :デフォルトの名無しさん:2012/10/14(日) 20:07:16.63
プログラム文という言葉は初めて見たかも

542 :デフォルトの名無しさん:2012/10/15(月) 00:01:49.62
ヒント翻訳ソフト

543 :デフォルトの名無しさん:2012/10/15(月) 01:18:47.48
>>542
翻訳ソフト使うと何が解決するの?

544 :デフォルトの名無しさん:2012/10/15(月) 17:34:20.97
というかダイクストラ法とクラスカル法の違いって何?
両方とも最小スパニング木を求める方法なのにお互い関係ないものなの?

ダイクストラで検索かけようとしても候補にクラスカルって出てこないし
逆もない。

クラスカルはプリムとセットで議論になるケースが多いけど。
誰か教えて。

545 :デフォルトの名無しさん:2012/10/18(木) 08:39:59.95
定義が違うし出力も違う。
そして、「同じものを求める二つのアルゴリズムなら関係があるはず」と言うのは思い込み。

546 :デフォルトの名無しさん:2012/10/23(火) 21:57:07.56
クラスカル、プリム・・・重み付きで、その重みが最小となる全域木を求めるAG

ダイクストラ・・・その経路までの最短キョリを求めるAG


クラスカルは全てのノードを繋ぐ
ダイクストラは最短ノードを選択





547 :デフォルトの名無しさん:2012/10/23(火) 22:46:30.76
線形探索も立派なアルゴリズム。

548 :デフォルトの名無しさん:2012/10/29(月) 21:42:14.08
AGってなんなん?

549 :デフォルトの名無しさん:2012/10/29(月) 21:46:33.53
GAなら知ってる

550 :デフォルトの名無しさん:2012/10/29(月) 23:57:14.35
GKなら乙

551 :デフォルトの名無しさん:2012/11/22(木) 18:39:52.58
線分で出来てるポリゴンで、
線分がクロスしているときにも正しい面積を出す方法はありますか?

イメージ的には、魚と魚のシッポがある場合に、魚の面積を得る方法。

552 :デフォルトの名無しさん:2012/11/22(木) 19:37:05.37
単純に2分の1になるんじゃないの?

553 :デフォルトの名無しさん:2012/11/22(木) 20:07:37.68
ポリゴンの共通部分体積を計算しなきゃな。

554 :デフォルトの名無しさん:2012/11/22(木) 21:22:43.29
クロスポイントで分割するしかないんじゃないの

555 :デフォルトの名無しさん:2012/11/22(木) 23:20:34.69
地震キター

556 :551:2012/11/26(月) 14:06:33.84
あらかじめクロスポイントが分かってないとできない、
座標を適当に入れるだけだと魚かシッポか判断できない、
ってことですね?

557 :デフォルトの名無しさん:2012/11/26(月) 14:23:38.70
塗りつぶすんならそれ用のアルゴリズムもあるけどね

558 :551:2012/11/26(月) 14:52:07.91
塗りつぶさずに処理したいです。

559 :デフォルトの名無しさん:2012/11/26(月) 21:09:10.39
半直線伸ばして線分と交差する回数の偶奇で判定できるかもしれない

560 :デフォルトの名無しさん:2012/11/27(火) 11:40:37.00
交点の座標を求めるのを厭わないなら、
交点も頂点の一つ(線分2本分なので二つ)に含めてしまえば、
普通に多角形の面積として求められるんじゃない?

561 :デフォルトの名無しさん:2012/11/27(火) 12:09:09.66
交点がちょうど頂点上だったり、線分が重複していたり、
まあ頑張ってくれ

562 :デフォルトの名無しさん:2012/11/27(火) 15:04:01.15
そこら辺の場合分けは地獄だな。

563 :デフォルトの名無しさん:2012/11/27(火) 15:15:10.54
面積求めるのにそんな例外事項は考慮する必要ない。
原点と、線分の両端点とで張る三角形の面積を、足したり引いたりするだけでしょ。
頂点どうしや頂点と交点が非常に接近してても問題ないし、
線分の全部や一部が重複してても問題ない。

564 :デフォルトの名無しさん:2012/11/27(火) 15:23:49.89
あぁ、すまん、これは「交点が求まったら」という前提な。
交点を求めることそのものは、工夫がいるね。

565 :デフォルトの名無しさん:2012/11/27(火) 16:54:57.32
二回ループ

566 :デフォルトの名無しさん:2012/12/05(水) 12:33:15.73
今あるn個の数値データの中から例えば1〜8個の数字を選んでx〜yの値にある組み合わせを作る
というアルゴリズムを考えているのですが、こういうアルゴリズムは何法とかで検索すればいいんでしょうか?
取りあえず総合で聞いてみたのですが、スレ違いなら誘導していただければ幸いです。

567 :デフォルトの名無しさん:2012/12/05(水) 12:33:45.43
あう・・・
age失礼しました。

568 :デフォルトの名無しさん:2012/12/05(水) 12:42:43.84
combination (あるいは permutation)

569 :デフォルトの名無しさん:2012/12/05(水) 13:24:52.20
>>568
ありがとうございます。
キーワードで調べてみます。

570 :デフォルトの名無しさん:2012/12/21(金) 10:45:15.05
ここで質問するべき事かわからないのですが、
適当な板もスレも見つからなかったのでお願いします。

Adobe illustratorでjavascriptを使って文字列の検索置換を行った時に
変更部分を目視で確認したいので置換した文字部分のみ色を変えたいのです。
正規表現を使って文字列置換するのは簡単なんですが、色を変えようとするとうまい方法が思いつきません。
100以上のパターンを検索置換しないといけません。
どんな考え方で作成したら良いのでしょうか?

571 :デフォルトの名無しさん:2012/12/21(金) 10:53:39.57
http://toro.2ch.net/test/read.cgi/tech/1355011916/

572 :デフォルトの名無しさん:2012/12/21(金) 10:59:58.44
>>570は誘導されたので移動します。

573 :デフォルトの名無しさん:2012/12/21(金) 13:05:37.93
領海

574 :デフォルトの名無しさん:2012/12/24(月) 11:36:38.88
バカは死ね

575 :デフォルトの名無しさん:2012/12/27(木) 22:10:58.26
ある整数の番号の範囲(例えば100〜999)があります。
要求によって番号を割り当てると、その番号は使用できなくなり
返却された番号はまた使えるようになります。
割り当て、返却を繰り返すと番号が断片化しますが
その場合でも安定した速度で未使用番号を検索できるアルゴリズムはないでしょうか?

576 :デフォルトの名無しさん:2012/12/27(木) 22:15:15.80
未使用番号の連結リスト
FATがやってるやつ

577 :デフォルトの名無しさん:2012/12/27(木) 22:17:11.78
膨大な数になったらどうするんです?

578 :デフォルトの名無しさん:2012/12/27(木) 22:40:50.83
膨大さと使えるメモリと許される時間による

579 :デフォルトの名無しさん:2012/12/27(木) 22:44:32.37
メモリやディスクブロックの割り当てに使われているような手法が応用できそう。
エクステントをツリーで管理するとか。

580 :デフォルトの名無しさん:2012/12/27(木) 22:44:41.80
例にしろ、100〜999って言っておいて、後から膨大とか後出しすぎ

581 :デフォルトの名無しさん:2012/12/27(木) 23:15:24.37
そこでblock符号ですよ!
圧縮にも使える便利なデータ構造でもある

582 :デフォルトの名無しさん:2012/12/27(木) 23:44:43.26
連続領域が必要ってわけでもなさそうだし、連結リストの何が不満なの?

583 :デフォルトの名無しさん:2012/12/28(金) 00:07:37.60
>>576でFA

584 : ◆QZaw55cn4c :2012/12/28(金) 01:09:30.09
>>576
FAT は未使用クラスタを連結リストにしていません。未使用マーク(0hとか)にするだけです。

585 :デフォルトの名無しさん:2012/12/28(金) 08:49:08.74
普通にリングバッファでキュー作ればいいだろ
何を難しく考えてるんだ

586 :デフォルトの名無しさん:2012/12/28(金) 09:00:25.38
>>576
FATって同じところに何度もアクセスしてディスク壊しやすいアルゴリズムだっけ?

587 :デフォルトの名無しさん:2012/12/28(金) 11:03:29.79
FATへの書き込みは大量に発生するね。

588 :デフォルトの名無しさん:2012/12/28(金) 11:46:18.52
HDDなら同じとこにいくらアクセスしても壊れんだろ
FDDだとFATのところがすりきれたりするけど

589 :デフォルトの名無しさん:2012/12/28(金) 13:23:44.02
安物のUSBフラッシュがデフォFATなのは、
適当に壊れて寿命と思って交換して欲しいから。

590 :デフォルトの名無しさん:2012/12/28(金) 13:41:02.59
テーブル2つもってるし
バッドセクタ機構もあるですしおすし

591 :デフォルトの名無しさん:2012/12/28(金) 22:33:22.79
>>589
mjd?

592 :デフォルトの名無しさん:2012/12/29(土) 00:34:52.59
FATは実装が容易で特許料のような余計なコストがかからず
いろんな機器の組み込みに使いやすいから

593 :デフォルトの名無しさん:2012/12/29(土) 00:55:36.80
特許使用料については微妙
ドイツでMSがモトローラに勝訴したとか

ロングファイルネームだけに対応するようにすれば大丈夫そうだけど
互換性に問題が出てくる

594 :デフォルトの名無しさん:2013/01/02(水) 23:38:19.70
NHK教育を見て40886倍賢くマターリ
http://hayabusa2.2ch.net/test/read.cgi/liveetv/1357124586/

595 :デフォルトの名無しさん:2013/01/04(金) 00:59:43.77
ヒープ作成の最大時間計算量の公式婆*2^k=(n-1)*2^(h+1)+2をどなたか証明できますでしょうか?
hは木の高さ、nをヒープの大きさとします。
nの場合からn-1の場合を引けばできるんですがみたいなんですが、、、

596 :デフォルトの名無しさん:2013/01/04(金) 02:21:04.43
最悪のケースで考えれば

597 :デフォルトの名無しさん:2013/01/09(水) 17:41:36.67
あと20分

岡野原大輔氏セミナー「ウェーブレット木の世界」 (番組ID:lv120540885)
ttp://live.nicovideo.jp/watch/lv120540885

【会場のご案内】
2013/01/09(水) 開場:17:57 開演:18:00

〜概略〜
機械学習・情報圧縮・高速文字列処理、それらを生かした起業などで
注目の若手、岡野原大輔氏(PFI取締役副社長)のセミナーを配信します。
ビッグデータ時代のシンボル的な方の講演ですが、そこは統数研チャンネル、ガチの
技術的・学術的内容、しかも最新でわかる人には胸ドキの内容で行きます。

「ウェーブレット木」は「ウェーブレット変換」と名前は似てますが、あまり関係はありません。
文字列、時系列、二次元グリッド、グラフなど様々な種類のデータに対し、これまで実現が難しかった
多くの操作を効率的にサポートしつつ、必要な作業領域量は
元のデータ表現よりと同じか小さいという、万能のデータ構造です。
この講演では、基礎的な仕組みから応用例,最新の研究成果まで解説します。

参考書:岡野原大輔「高速文字列解析の世界」(岩波書店)

598 :デフォルトの名無しさん:2013/01/10(木) 20:45:56.19
F欄大学のアルゴリズムの問題
授業もろくに出てないから全くわからん
問題の意味すら理解できないんだが
「egg]を文字コードに直して101でなんか計算すればいいの?


eggを m=101としてハッシュ → 解答 9
eeggを m=101としてハッシュ → 解答 9
eeggを m=128としてハッシュ → 解答103

アホな質問ですが、ほんとに困ってます

599 :デフォルトの名無しさん:2013/01/10(木) 21:01:33.23
ここじゃ宿題の相手はしてないよ
宿題スレに行けば親切なふりした誰かが学習機会をスポイルしてくれるかもね

600 :デフォルトの名無しさん:2013/01/10(木) 21:39:57.13
こっちで答えた方がお得
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13100051018

601 :桃白白:2013/01/10(木) 21:48:28.83
>>598
これでいんじゃね。

int hash(char* c, int m)
{
  int r = 0;
  while (*c)
  {
    r = r * 256 + *c;
    c++;
  }
  return r % m;
}

602 :デフォルトの名無しさん:2013/01/10(木) 21:54:36.12
それ静的解析かけてみろよ

603 :デフォルトの名無しさん:2013/01/10(木) 22:27:51.91
>>601
256ってどこからきたんですか?
この馬鹿にもっと詳しく教えて下さい

604 :デフォルトの名無しさん:2013/01/11(金) 00:20:29.77
>>601
*c >= 0x80
のとき、
> r = r * 256 + *c;
はどうなるのか

605 :デフォルトの名無しさん:2013/01/19(土) 10:43:24.87
あげ

606 :デフォルトの名無しさん:2013/01/19(土) 13:28:45.73
you tubeで「新唐人テレビ」を検索して見てください。
新唐人テレビは中国の民主化を望む中国人自身によるテレビ局で、海外に拠点をおき、
中国共産党の圧力に屈する情けない日本のマスゴミよりもよっぽどまともなテレビ局です。

日本では中国共産党の圧力により報道出来ないニュースが沢山取り上げられています。
新唐人テレビのような勇気ある報道機関を広める事で、中共の圧力に屈し、
真実を伝えない日本のマスゴミのへなちょこぶりを浮き彫りにする事にもなります。

新唐人テレビを日本や在日中国人の間に広めて、
中共が日本に戦争をしかけてくる前に中共を内部崩壊させましょう!

607 :デフォルトの名無しさん:2013/01/19(土) 13:43:23.76
直リン貼るとまずいことでもある?
http://www.youtube.com/user/NTDJapanese
http://www.ntdtv.jp/
http://ja.wikipedia.org/wiki/%E6%96%B0%E5%94%90%E4%BA%BA%E9%9B%BB%E8%A6%96%E5%8F%B0

608 :デフォルトの名無しさん:2013/01/19(土) 14:11:52.60
法輪功かよ。
要はカルトじゃねーか。

反政府カルトを「よっぽどまとも」とかいう奴の頭のほうがマスゴミより1000倍ゴミだわ。

609 :デフォルトの名無しさん:2013/01/22(火) 18:31:54.62
近交確認、リスト化て難しいな

610 :デフォルトの名無しさん:2013/02/02(土) 20:56:41.94
リスト内の要素をグループ化するアルゴリズムを考えてるんだけど、
単純にソートアルゴリズムを使うよりも少ない計算量でできる?

[入力] 少なくとも大小の比較ができる要素がランダムに並んだリスト
[出力] 同値な要素が必ず隣同士にあるリスト(入力と同じ要素数で、同じ要素を持つ)

出力のリストは上記の条件に合えば、どのような要素の並びでも構わない。

<例>
 入力 = [3, 5, 2, 3, 5, 2, 5, 2, 1, 5]
 出力例1 = [3, 3, 5, 5, 5, 5, 2, 2, 2, 1]
 出力例2 = [5, 5, 5, 5, 1, 3, 3, 2, 2, 2]

もちろんソートアルゴリズムを使えば O(n log n) でできるんだけど、
ソートより条件が緩いから、もっと早くできるかな、と。

611 :デフォルトの名無しさん:2013/02/02(土) 21:04:25.13
まとまってさえいれば、順番はどうなってもいいってことね
一旦ハッシュテーブルに突っ込んでから
また取り出せばいいんじゃない?

612 :610:2013/02/02(土) 21:33:02.28
>>611
この条件しかない入力リストの要素から上手くハッシュ値が計算できたら、
テーブルへの挿入も取り出しもそれぞれ O(n) でできるから、
たしかに全体の計算量も O(n) でできると思う。

ただ、俺がプログラムすると利点を台無しにしてしまいそうで怖い。
上手いハッシュ値の計算は要素のタイプによって全然違うだろうし。
ヘボ計算で変な値だとテーブルに使うメモリ量がバカでかくなりそうだし。

今のところ候補第1号ということで、
上手くハッシュ値を計算できるか考えてみるよ。


理想は、クイックソートみたいに入力と同じサイズのリストしか必要ない、
というアルゴリズムなんだけどね。
これでソート以外のアルゴリズムを考えたが、O(n^2) のものしか思いつかない。

613 :デフォルトの名無しさん:2013/02/02(土) 21:41:20.33
比較する値の範囲が小さければ
バケツソートすればいいよ

614 :デフォルトの名無しさん:2013/02/02(土) 21:42:47.87
と思ったが、バケツソートとハッシュテーブルは大して差が無いか

615 :デフォルトの名無しさん:2013/02/02(土) 21:54:04.64
実際扱う入力値の配列は長さいくつ?
何回実行する?

616 :610:2013/02/02(土) 21:59:44.83
もしかしたら誤解されているかもしれないけど、
入力リストの条件は「少なくとも大小の比較ができる要素を持つ」事しかないからね。

整数値とも浮動小数点値とも限らないよ。
(データのメモリアドレス値が取れるかどうかも、言語によるし)

比較する値の範囲、つまり何種類の要素があるかという情報は、
それこそハッシュテーブルを使うかして調べないと分からないからね。


>>615
ごめん、本当に実際に解決したかった問題はソートで解決した。
(その問題に限り、ソートを使うと、抱えていた他の問題も同時に解決できたから)

今は単に頭の体操で遊んでるだけ。

入力値の配列は長さと実行回数によってはソートより計算量は低くなる?

617 :デフォルトの名無しさん:2013/02/02(土) 22:31:12.24
クイックソートより効率を求めるならO(n)しか道は無いしなあ
ハッシュテーブルより効率よくするのは難しい気がする

618 :デフォルトの名無しさん:2013/02/03(日) 01:42:19.05
>>610
あんまり良く判らないが
同じ値が複数ある数値をPivotにしてQuickSortのアルゴリズムで
振り分けたら必ず同値は隣に並ぶんじゃね?
同値があるものを探すのに手間かかるけどね

619 :610:2013/02/03(日) 14:47:22.77
>>618
いや、だから、「ソートアルゴリズムを使えば O(n log n) でできる」と
>>610 に書いたんだが。

あと、結果のリストから同値があるものを探すのは今回は必要ないです。
あくまで目的(出力)は同値な要素が必ず隣同士にあるリスト。

>>617
たしかに O(n log n) よりもひとつ速いとなると O(n) しかないね。

ハッシュの方は試しに、要素の型を int に限定して、
std::unordered_set<int> を使ってやってみた。
残りのテンプレート引数はデフォルトで。
単純に、配列の要素を順に unordered_set に insert してから、
イテレータで順に取り出して元の配列に代入した。

配列の要素数は 10000000 個で、rand () % 3000 の値を入れた。
コンパイラは g++ (tdm64-1) 4.7.1 で、最適化オプションは O3。

qsort 関数は1秒で終わったが、ハッシュの方は15秒かかった。

話にならんかった。
やっぱ楽しないで、自分でハッシュ関数やアロケータを作って
テンプレート引数に入れるべきか・・・

俺の直感では単純なソートよりも条件は緩いはずなのに、
ソートと同程度のソートではないアルゴリズムが思いつかないのは意外だ。

620 :610:2013/02/03(日) 14:54:47.84
>>619
> qsort 関数は1秒で終わったが、ハッシュの方は15秒かかった。

もしかしてテーブルサイズの拡張に時間を食っているのではと思い、
std::unordered_set<int> のコンストラクタに配列の要素数を渡したところ、
3.5秒に短縮された。

まぁ、それでも qsort より 3倍以上かかってるから意味は無いが。

621 :デフォルトの名無しさん:2013/02/03(日) 15:55:52.48
ソートより条件厳しくないか?

622 :610:2013/02/03(日) 16:13:27.69
>>621
どの辺り?

623 :デフォルトの名無しさん:2013/02/03(日) 16:27:15.88
>>622
んー、ソートは大小比較だけが唯一の条件じゃん?
でも、>>610 って、移動位置も条件になってね?

624 :デフォルトの名無しさん:2013/02/03(日) 17:36:06.87
ハッシュがかなりぶつかってないのかなあ
デフォルトのハッシュってどんなもんなんだろ

625 :610:2013/02/03(日) 17:54:08.19
>>623
位置移動って、どういうこと?
ソートだって移動処理を伴うと思うが、そういうことではない?

同値な要素が隣同士にあれば、どのような順番でもいいけど。
ソートは小さい方から順に並べないといけなくない?

626 :デフォルトの名無しさん:2013/02/03(日) 18:05:42.28
>>625
順番かんけいないの?
であれば、個数をカウントするだけでいいな
多分O(n)で行ける

ってか、順番あってもカウントで行けるな

627 :デフォルトの名無しさん:2013/02/03(日) 18:06:50.81
あっ、そうすると結局ハッシュか

628 :デフォルトの名無しさん:2013/02/03(日) 18:07:56.28
>>625
ま、俺の勘違いっぽいので忘れて下さい
すまんです

629 :デフォルトの名無しさん:2013/02/03(日) 18:36:21.33
>>619
618なんだが、QuickSortを使うのではなくそのアルゴリズムを使うって話
QuickSortのアルゴリズムのキモの部分は、Pivotを決めてそれより大きいか小さいかでPivotの左右に振り分ける
それを改良して、Pivotを同値がある数値にし、Compareを=のみ真にして、真なら隣とスワップとする
同値が複数ある場合に備えて、1つスワップしたら、そのスワップする位置が内に1つずつズレていく
そのPivotを同値のある物にしなければならないから検索が必要になるってこと
要素に入っている数値全てに対して行なってもいいけど総当りになるから検索したほうがいいかなってこと

例えば、3, 5, 2, 3, 5, 2, 5, 2, 1なら
同値のある5を右端とスワップして、そのプログラムに通すと
3, 2, 3, 2, 1, 5, 5, 5ってなる
さらに3, 2, 3, 2, 1の部分を抜き出して左端に3を持っていきプログラムに通すと
2, 2, 1, 3, 3ってなる、2の場合も同じ
最終的に、1, 2, 2, 3, 3, 5, 5, 5ってなる、ソートされている状態だけど
3から始めたら、1, 2, 2, 5, 5, 5, 3, 3ってなる

QuickSortのアルゴリズム部分を改良したら行けるんじゃないか?って話

630 :デフォルトの名無しさん:2013/02/03(日) 18:37:24.80
要素のサイズが大きいとハッシュテーブルの方が有利になったりしないかな
あと、ハッシュテーブルのメモリ確保部分は工夫した方が良さそう

631 :デフォルトの名無しさん:2013/02/03(日) 18:59:07.38
検索なしでもいけるかも
フローを書くと

1)要素の最初の数値を左端に持っていきPivotとする
2)先頭から順番にPivotと比較して、=ならPivotの隣とスワップする
3)Pivot位置をそのスワップしたものに移動する
4)要素全て調べたらPivot位置を1つ左にズラして、1)に戻る

こんな感じかな

632 :デフォルトの名無しさん:2013/02/03(日) 19:06:26.24
連投すまん
単純に考えて最大O(n/2)で済むように思う
詳しい人あってる?
あ、書き忘れてた
Pivot位置が2番目に来たらループ抜ける

633 :デフォルトの名無しさん:2013/02/03(日) 19:12:36.63
ああ違うわ
O(n^2)だわ…
ソートしたほうが早いな…

634 :デフォルトの名無しさん:2013/02/03(日) 19:16:41.44
これでよくね?
ideone.com/XdtCMM

635 :デフォルトの名無しさん:2013/02/03(日) 19:18:28.48
バケツソートは既出だっつーの!

636 :デフォルトの名無しさん:2013/02/03(日) 19:30:12.09
ソートと違って、保存先へのポインタが必要だから、バケツより速くするのは無理な気がするぞ。

637 :デフォルトの名無しさん:2013/02/03(日) 19:31:16.34
バケツソートでなく
・データの1個目と同じデータの数を求め、配列()に保存
・その過程で検索したデータも削除して元データスリム化 (不要?)
・データエンドまで繰り返し
・あとは求めたデータと数の配列から順に書き起こして終わり

データの移動をせず、答えを改めて記述する点がキモ

638 :610:2013/02/03(日) 19:35:05.13
>>629 >>631-633
じつは俺も左に集めていく方法で速いのがないか色々試してた。
最初に提案されてからハッシュテーブルの実装をしばらく渋ってたのはそのせい。
でも、どう考えても O(n^2) のしかできなかった。

まぁ、久しぶりに脳をフル稼働した気分だし、
自分的には失敗しても得るものはあった。


ところで、ソートより速いハッシュテーブルでの実装が現実的に可能か謎だ。

データを木構造で持ってたら、要素ひとつの挿入に O(log n) かかって、
それが要素数分必要だから、結局 O(n log n) になる。

これより速くするなら木構造ではなく配列で持つ必要があるけど、
要素の型やグループ数などに汎用性を持たせようとすると、メモリ量が見積もれんな・・・

639 :デフォルトの名無しさん:2013/02/03(日) 19:35:16.19
あぁ
データエンドまででないな
重複をパスしてかつ求めた数の総量=元データ数になったら終わり

640 :デフォルトの名無しさん:2013/02/03(日) 19:36:45.82
>>637
>>634

641 :610:2013/02/03(日) 19:40:49.33
>>634
どういう意味かもう少し説明しほしいです。

ググってみたけど、今回のことにどう関係するのかよく分からなかった。

642 :デフォルトの名無しさん:2013/02/03(日) 19:46:10.70
>>641
どの数字がいくつあったか統計を取るということ。

643 :デフォルトの名無しさん:2013/02/03(日) 19:47:44.20
>>641
ハッシュでバケットを C++ 実装してるだけだよ
map 使ってるから、厳密にはハッシュじゃないけど

http://ideone.com/XdtCMM
見たんだよね?

644 :デフォルトの名無しさん:2013/02/03(日) 19:55:38.84
mapだとO(n log n)になってしまうぞい

645 :610:2013/02/03(日) 20:06:53.31
>>643
> 見たんだよね?
いや、ideone.com/XdtCMM でググっても何も出なくて、
ideone.com でググったら、どうもコード投稿サービスみたいな感じだから、
そこで XdtCMM を調べれば良いのかと思って [search] ボタンを探したが無くて、
諦めた。

>>634 の方法で時間を計ったら、qsort より 1.5 倍遅かった。

俺は >>619 で set(unordered_multiset)を使ってやったが、map の方が速かったのか。

あと今更すまん、>>619 は unordered_set って言ったけど unordered_multiset の間違い。

646 :610:2013/02/03(日) 20:16:14.46
>>613
map を inordered_map に換えてみたら、qsort より6倍以上速くなった!

あとは、要素の型にどうやって汎用性を持たせるかだ。
qsort は void* の要素と型のサイズを引数に取る汎用関数なんで。

qsort みたいに要素1個につき1バイトずつ while でコピーする方法でやっても、
なお qsort より速くできるか・・・やってみるわ。

647 :610:2013/02/03(日) 20:17:25.42
>>646
ごめん、アンカーミスった

>>643

648 :610:2013/02/03(日) 20:18:56.60
>>640
連投すまん

map を unordered_map に換えてみたら、です

ちょっと興奮を冷ますわ

649 :デフォルトの名無しさん:2013/02/03(日) 20:30:18.30
>>644
それはわかってるけど、考え方の具体例を示しただけだから
STL なんだからコンテナ変えるだけでhash_map (標準ではないかな)でもなんでも試せるじゃん?

>>648
おめ!
君の努力と探求心の賜物だね

650 :610:2013/02/03(日) 20:31:59.19
void* 使った汎用化は面倒なんで、関数テンプレートにしたわ。

>>611
正直ハッシュは本当にできるか疑ってたが、できてしまったな。
ごめんね。

しかし set と違って map クソ速いな。
どこで差が出るのかちょっと興味出てきた。

651 :デフォルトの名無しさん:2013/02/03(日) 20:45:47.82
unordered_multisetよりunordered_multimapが速いとかかなり衝撃的
何が違うんだ・・・

652 :デフォルトの名無しさん:2013/02/03(日) 20:52:21.18
>>651
コード晒した方が回答付きやすいぞ
コンテナに問題があるかもしれないが、使い方に問題がある場合が圧倒的だよ

653 :610:2013/02/03(日) 21:02:28.84
>>651
unordered_multiset と unordered_map の比較ね。

たぶん、multiset に挿入するのと map に挿入するのは同じだと思うんだ。
同じハッシュ関数や比較関数、アロケータを使ってるから。
違うのは、set に対して multi の機能を加えている部分ではないかと。

今ちょっと別のことやっててソースをまだ見てないから
間違ってるかもしれんが、multiset に「同じ値」を挿入すると、
そのタイミングで「同値要素格納用メモリ」がそのツリーノードに
確保されるのではないか。

というのも、コンストラクタでハッシュテーブルの
スロットの最低数は指定できるが、マルチ特有の設定項目がない。

あと、俺が >>619 でやったのは、ハッシュテーブルから取り出す値の数も、
最初の要素数と同じだ。

でも、>>634 のはヒストグラムだから、取り出す処理は
理論上はグループ数だけ。
(別の言い方をすればツリーのノードはグループ数だけ)
要素数に対してグループ数が少ないほど、こちらの方が速い。

>>626 の意味が今更分かったw


あとは、自分で unordered_multiset らのソースを眺めてみるよ。
みんな今までありがと。
たいへん勉強になったよ。

654 :610:2013/02/03(日) 21:13:13.45
俺、すげーバカだった。
ヒストグラム法じゃダメじゃん。

例えば要素の型が、

struct Himawari {
 int value;
 int id;
};

で、value でしか比較しない場合、グループ化後、
同じグループの要素の id が全て同じになってしまう。

要素がint型とかfloat型とか、そういう単純な値ならいいけど。

655 :デフォルトの名無しさん:2013/02/03(日) 21:46:02.02
>>654
実はそのケースもあると思ってた
でも、ちょびっと工夫するだけで結構楽にできると思うよ

656 :610:2013/02/03(日) 22:03:30.43
じゃあ、ちょびっと熟考してみる。

657 :デフォルトの名無しさん:2013/02/03(日) 22:30:08.32
バケツソートで数を数えるのではなく
テーブルに突っ込んでいけばいいのだが
ハッシュ=値そのものなハッシュテーブルと同じなのよねやってる事は

658 :デフォルトの名無しさん:2013/02/04(月) 16:22:01.97
要素数100万の配列をc++のstd::sortでソートすると
10秒ぐらいかかっちゃうんだけどこれって異常に遅いよね・・・
ちなみに要素の型はpair< long long, long long >なんだけど、
なにが問題なのか誰か分かる?

659 :デフォルトの名無しさん:2013/02/04(月) 16:26:09.16
コピー発生してる?

660 :デフォルトの名無しさん:2013/02/04(月) 16:35:04.67
比較関数が遅いとか。

661 :デフォルトの名無しさん:2013/02/04(月) 16:45:11.08
うーむむ・・ためしにint配列でやったら2秒ぐらいだった

というか、蟻本の巨大ナップサック(p148)をそのまま写して、
最大のn=40でやってみたら10秒以上かかったけどいいのかなー
どうやらソートに時間かかってんなーって感じなのよ

こればっかりは自分の処理系?だけじゃなんともいえんのか・・・

662 :デフォルトの名無しさん:2013/02/04(月) 18:41:17.92
環境も何もかかずにいったい何がしたいのか。

663 :デフォルトの名無しさん:2013/02/04(月) 20:11:22.72
コピーが遅いんだろ

664 :デフォルトの名無しさん:2013/02/04(月) 22:20:18.86
最適化有効にしてる?

665 :661:2013/02/04(月) 23:53:21.67
いやーすまぬ
Releaseにしてビルドしたらすごく速くなったわ
こんなに速度変わるとは

666 :デフォルトの名無しさん:2013/02/04(月) 23:57:54.34
・・・

667 :デフォルトの名無しさん:2013/02/05(火) 00:24:44.09
原因を解決したらもっと速くなりそうだな

668 :デフォルトの名無しさん:2013/02/05(火) 12:24:00.31
色々酷いな

669 :デフォルトの名無しさん:2013/02/06(水) 09:40:59.22
結果報告しただけでもマシ

670 :デフォルトの名無しさん:2013/02/06(水) 19:32:31.26
2のべき乗の和で、例えば7は1+2+4で構成されてますが、
7から1,2,4が使われてると判定する良い方法はありますか?

671 : ◆QZaw55cn4c :2013/02/06(水) 19:34:59.98
>>670
繰り返し 2 で割りまくって余りをみていくしかないのでは?

672 :デフォルトの名無しさん:2013/02/06(水) 19:38:43.95
>>670
16進数で論理演算したら?

673 :デフォルトの名無しさん:2013/02/06(水) 20:09:47.71
>>670
& で1ビットずつ判定していけば

674 :デフォルトの名無しさん:2013/02/06(水) 20:30:25.87
値がdoubleかも知れないし

675 :デフォルトの名無しさん:2013/02/06(水) 20:37:47.12
整数にキャストすればいいだけ

676 :デフォルトの名無しさん:2013/02/06(水) 20:38:52.35
判定した値を何に使うかで違ってくると思う
例えばforeachに突っ込むなら判定処理は先延ばしにした方がいいだろうし

677 :デフォルトの名無しさん:2013/02/06(水) 21:24:33.20
>>670
J言語だとこんなふう
(#2^i.@#)#:7
1 2 4
(#2^i.@#)#:1234
1 8 16 64 512

678 :デフォルトの名無しさん:2013/02/06(水) 22:04:58.56
J言語の書き込みなんて初めて見た

679 :670:2013/02/07(木) 03:55:23.45
ビット演算で
2の0乗&7、2の1乗&7...で判定できるのですが、この方法だと3の冪乗1 3 9 27...のときに同じ方式が使えないですよね。
どう考えれば良いのでしょうか。。

680 :デフォルトの名無しさん:2013/02/07(木) 04:04:00.14
>>679
>>671

681 :デフォルトの名無しさん:2013/02/07(木) 07:17:09.20
まさか10進数の表示を自前でできないってことはないよね?
3進数はその10を3に変えればいいだけ

682 :デフォルトの名無しさん:2013/02/07(木) 08:40:46.92
>>670 >>679
ここに 3 のベキ乗でも通用する良質の答えがある
http://toro.2ch.net/test/read.cgi/tech/1358572977/31-

683 :デフォルトの名無しさん:2013/02/07(木) 11:24:13.23
>>677 間違えました
2のべき乗のテーブルと2進数数の並びの対応が反対でした
(#2^i.@#)|.#:1234
2 16 64 128 1024

あれ?nのべき乗の話だったの?
f=:dyad def'(# x^i.@#)|.*x#.inv y'
3 f 1234
1 9 243 729

684 :デフォルトの名無しさん:2013/02/07(木) 13:23:59.05
何を間違えたのかすら解らないが、
J言語って奴がなんだか面白そうなことは解ったw

685 :デフォルトの名無しさん:2013/02/07(木) 19:45:22.01
J言語キモいw

686 :デフォルトの名無しさん:2013/02/07(木) 20:11:54.72
元々J言語に相当なキモさが内在しているのか、
それとも >>683 がキモい書き方しかできないヘボなのか

687 :デフォルトの名無しさん:2013/02/07(木) 20:36:39.22
言語を広めるのに見た目が大事だってことがよく分かった

688 :デフォルトの名無しさん:2013/02/07(木) 22:25:54.29
Cマガジンの連載で紹介されてたな。>J言語
SIMD(Single Instruction Multiple Data)な言語だ、みたいな紹介だった気がする。

689 :デフォルトの名無しさん:2013/02/07(木) 23:16:07.19
FortranはSIMDなの?

690 :デフォルトの名無しさん:2013/02/10(日) 04:08:54.61
ぜんぜん
ただ、自動SIMD化とかのコンパイラの最適化を適用する上で
性質がいろいろ良い

691 :デフォルトの名無しさん:2013/02/11(月) 02:19:38.21
プログラミング言語のデータ型の名称として使われる"char"、
これを「キャラ」と呼ぶ人が非常に多いですが、
ネイティブの方々は母音の関係でキャラとは発音できないはずです。
おそらく「チャア(チャー)」か「シャア(シャー)」と呼ぶのが正しいと思われます。

692 :デフォルトの名無しさん:2013/02/11(月) 02:37:32.40
カーとかチャーとか発音してるらしい

693 :デフォルトの名無しさん:2013/02/11(月) 03:32:12.27
まあ、characterのcharなんだからキャラって読んでもいいと思うけどね
英単語にchar(木炭、イワナなど)ってのがあるからその読みで読むんだろうね
オレは何も知らない時からチャーって読んでいた

694 :デフォルトの名無しさん:2013/02/11(月) 04:20:04.76
過去に一人だけ「きゃる」って言う人がいた。

695 :デフォルトの名無しさん:2013/02/11(月) 07:43:58.37
まあ赤い水星の彼もcharだしね

696 :デフォルトの名無しさん:2013/02/11(月) 07:44:29.09
>>695
彗星だなorz

697 :デフォルトの名無しさん:2013/02/11(月) 09:41:24.50
チャー大佐

698 :デフォルトの名無しさん:2013/02/11(月) 09:42:39.64
で、何でスレ違いの発音の話題が

699 :デフォルトの名無しさん:2013/02/11(月) 19:48:25.35
「データ型」ってことらしいぞ。>>691

700 :デフォルトの名無しさん:2013/02/11(月) 19:57:35.43
データ構造のスレですけど

701 :デフォルトの名無しさん:2013/02/18(月) 16:04:09.80
>>700
黙れキチガイ

702 :デフォルトの名無しさん:2013/02/18(月) 16:16:24.31
>>701
死ねゴミ

703 :デフォルトの名無しさん:2013/02/19(火) 21:00:29.46
バーカ

704 :デフォルトの名無しさん:2013/02/20(水) 07:10:16.02
>>702
死ねクズw

705 :デフォルトの名無しさん:2013/02/20(水) 09:39:29.80
>>670に似ていますがOpenOfficeCalcでセルの
A1に"a"
B1に"b"
C1に"c"
D1に"d"
E1に…と入っている時に

A2に43を入れたら、A3に"abdf"と表示(32+8+2+1)
B2に22を入れたら、B3に"bce"と表示(16+4+2)

させたいのですが、マクロを定義せずにA3やB3の数式だけで可能でしょうか

706 :デフォルトの名無しさん:2013/02/20(水) 11:18:08.25
>>704
死ねゴミ

707 :デフォルトの名無しさん:2013/02/20(水) 14:25:27.05
>>700-704,706
お前ら仲良いな

708 :デフォルトの名無しさん:2013/02/20(水) 16:09:36.79
>>706
黙れガキw
さっさと死ねwwww

709 :デフォルトの名無しさん:2013/02/20(水) 23:33:37.52
>>708
死ねゴミ

710 :デフォルトの名無しさん:2013/02/21(木) 08:09:50.40
>>709
消えろやゴミクズw

711 :デフォルトの名無しさん:2013/02/21(木) 09:12:56.32
>>710
死ねゴミ

712 :デフォルトの名無しさん:2013/02/21(木) 18:06:48.57
>>711
死ねゴミしか言えねえクズwwwwww

713 :デフォルトの名無しさん:2013/02/21(木) 18:27:30.59
これがリンク構造か

714 :デフォルトの名無しさん:2013/02/21(木) 18:28:44.17
>>713
線形のな。

715 :デフォルトの名無しさん:2013/02/21(木) 20:30:20.52
しねしね祭り開催中と聞いて

716 :デフォルトの名無しさん:2013/02/21(木) 21:36:51.32
最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイドという本の迷路づくり名人の例3ってResults間違ってませんか?
どう頑張っても6になります

同じ書籍持っている方いましたら教えてください

717 :デフォルトの名無しさん:2013/02/21(木) 22:22:53.01
>>712
死ねゴミ

718 :デフォルトの名無しさん:2013/02/21(木) 22:45:12.93
アルゴリズマーって...
タイトルからして読むような本じゃないな。

719 :デフォルトの名無しさん:2013/02/21(木) 22:54:09.49
http://www.itmedia.co.jp/keywords/algorithmer.html
これの書籍版かな

>>718
書籍は知らんが、記事の内容はいたってまともに見える

720 :デフォルトの名無しさん:2013/02/21(木) 22:54:11.57
アルゴリズミストって言って欲しいよな。

721 :デフォルトの名無しさん:2013/02/21(木) 23:00:02.40
http://www.algorithmist.com/index.php/Main_Page

722 :デフォルトの名無しさん:2013/02/21(木) 23:05:53.11
-erはゲルマン的だから、ラテン的な-orが良いと思う。(語源はアラブ由来だけど)

723 :デフォルトの名無しさん:2013/02/21(木) 23:11:29.83
algorithm player でいいじゃん

724 :デフォルトの名無しさん:2013/02/22(金) 08:46:41.86
>>717
死ねゴミクズwwwwwwwwww
バーカw

725 :デフォルトの名無しさん:2013/02/22(金) 09:48:52.55
>>724
死ねゴミ

726 :デフォルトの名無しさん:2013/02/22(金) 10:23:01.99
>>725
プッwバカめww
キモいんだよ死ねゴミクズwwwwwwwww

727 :デフォルトの名無しさん:2013/02/22(金) 10:49:15.35
>>726
死ねゴミ

728 :デフォルトの名無しさん:2013/02/22(金) 16:42:45.44
ム板のスレッドの一般的な流れだな

729 :デフォルトの名無しさん:2013/02/22(金) 17:13:05.48
こんな幸せがいつまでも続くと思ってた・・・

730 :デフォルトの名無しさん:2013/02/22(金) 18:38:39.56
>>727
まだ生きてやがんのかw
死ねゴミクズw

731 :デフォルトの名無しさん:2013/02/23(土) 02:09:25.34
>>730
死ねゴミ

732 :デフォルトの名無しさん:2013/02/23(土) 18:31:01.96
>>731
バーカw
死ぬのはお前じゃw

733 :デフォルトの名無しさん:2013/02/23(土) 22:19:34.60
>>732
死ねゴミ

734 :デフォルトの名無しさん:2013/02/23(土) 23:53:25.45
そろそろ面白くなくなってきた

735 :デフォルトの名無しさん:2013/02/24(日) 05:09:57.21
ム板のスレッドの一般的な流れだな

736 :デフォルトの名無しさん:2013/02/24(日) 05:41:52.28
>>733
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ
死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ死ねゴミ

737 :デフォルトの名無しさん:2013/02/24(日) 08:50:04.02
おまえら、よく飽きないな…

738 :片山博文MZパンク ◆0lBZNi.Q7evd :2013/02/24(日) 22:57:48.16
伝説のぼよ〜ん、ぼよ〜ん。

739 :デフォルトの名無しさん:2013/02/24(日) 23:35:56.78
しねしね祭りに嘘つき片山まで参戦して阿鼻叫喚の地獄絵図

740 :片山博文MZパンク ◆0lBZNi.Q7evd :2013/02/24(日) 23:42:37.60
データ構造の話に戻ります。

XMLを別のXMLに変換する方法にはどんなものがありますか

741 :デフォルトの名無しさん:2013/02/25(月) 00:00:16.39
>>740
XMLパーサーでも使えば?

742 :デフォルトの名無しさん:2013/02/25(月) 00:24:31.71
XSLT

743 :デフォルトの名無しさん:2013/02/25(月) 00:25:48.38
アルゴリズム+データ構造=プログラム

744 :デフォルトの名無しさん:2013/02/25(月) 12:53:05.92
qqqqqq

745 :デフォルトの名無しさん:2013/02/25(月) 23:26:12.86





746 :デフォルトの名無しさん:2013/02/27(水) 02:14:51.58
>>736
死ねゴミ

747 :デフォルトの名無しさん:2013/02/28(木) 11:44:09.51
>>746
死ぬのはお前じゃw
死ねやゴミクズw

748 :デフォルトの名無しさん:2013/02/28(木) 11:49:45.77
>>747
死ねゴミ

749 :デフォルトの名無しさん:2013/02/28(木) 21:31:59.17
ケンカ両成敗

仲良くしようぜ

750 :デフォルトの名無しさん:2013/03/01(金) 07:28:09.81
>>748
死ねゴミロボットはこの世にいらんwwww

751 :デフォルトの名無しさん:2013/03/01(金) 08:37:31.97
>>750
死ねゴミ

752 :デフォルトの名無しさん:2013/03/01(金) 20:30:56.34
ユーロファイターもスホーイも所詮は相打ちの戦闘機
確実に相手を殺し自分は生き残る最強無敵の戦闘機
それはF-35ライトニングII !

その恐るべき能力の数々!

DASシステム機能解説 ノースロップ・グラマン公式ビデオ(日本語版)
http://www.youtube.com/watch?feature=player_embedded&v=BMqVkeyGnD8

AESA(エーイーサ) レーダー解説ノースロップグラマン公式ビデオ(日本語版)
http://www.youtube.com/watch?v=_sKEOtvAukE

2012 F-35 Highlights
http://www.youtube.com/watch?v=WPx1A5Rsg10

753 :デフォルトの名無しさん:2013/03/02(土) 07:48:15.82
>>751
死ねゴミクズwwwwww
qqq

754 :デフォルトの名無しさん:2013/03/02(土) 11:26:01.87
>>753
死ねゴミ

755 :デフォルトの名無しさん:2013/03/03(日) 10:20:50.59
>>754
死ねゴミロボット涙拭けwwwwwwwww

756 :デフォルトの名無しさん:2013/03/03(日) 11:35:14.54
>>755
死ねゴミ

757 :デフォルトの名無しさん:2013/03/03(日) 12:06:42.44
>>756
死ねゴミw

758 :デフォルトの名無しさん:2013/03/03(日) 17:21:56.13
>>757
死ねゴミ

759 :デフォルトの名無しさん:2013/03/03(日) 17:31:53.31
環境に依存しない連想配列で、一番メモリ効率or速度効率が良いのって何かね。
B木?ってのが高効率らしいけど、環境依存なんでしょ?

760 :デフォルトの名無しさん:2013/03/03(日) 18:03:12.21
効率関係なく基本的なデータ構造だからB木ぐらい勉強しとけば?

761 :デフォルトの名無しさん:2013/03/03(日) 18:09:24.96
>>760
何で上から目線なのこのボンクラ

762 :デフォルトの名無しさん:2013/03/03(日) 18:25:19.96
>>759
くだらない事言ってる暇あったら勉強しろ

763 :デフォルトの名無しさん:2013/03/03(日) 18:33:32.78
>>760
知識としては、B木の名前と簡単な特徴はなんとなく覚えてる。
でも木構造の操作って直感で理解しにくくない?

勉強のためにスプレー木を実装したことがあるんだけど、
正しく動くものの、木の回転がいまいちピンと来なかった。

764 :デフォルトの名無しさん:2013/03/03(日) 18:39:51.68
>>761
貴様かageバカ。イラネ

765 :デフォルトの名無しさん:2013/03/03(日) 18:44:10.75
今どきagesage気にしてる池沼っているんだなw
妙なところに拘る奴にはアスペが多い

766 :デフォルトの名無しさん:2013/03/03(日) 18:47:39.54
>>764
減らず口叩いてる暇があったらアルゴリズムの勉強でもしてろゴミ

767 :デフォルトの名無しさん:2013/03/03(日) 18:56:40.93
>>763
同じデータ使って、回転させると木の高さがどうなるか調べてみたら。
特にほぼ整列しているデータを突っ込んだ時。
セジウィック本とかにちゃんと説明してあるよ。

768 :デフォルトの名無しさん:2013/03/03(日) 19:00:02.85
いい感じになってきたなw
どんどん罵りあえやバカ共がw

>>758
クズうるせえw
死ねキチガイw

769 :デフォルトの名無しさん:2013/03/03(日) 19:05:23.90
バカが殺伐とさせて喜んでるなあ...

770 :デフォルトの名無しさん:2013/03/03(日) 19:27:15.39
>>768
死ねゴミ

771 :デフォルトの名無しさん:2013/03/03(日) 19:29:24.26
そろそろコミュニティの一生だと人が離れていく時期か

772 :デフォルトの名無しさん:2013/03/03(日) 23:19:06.62
でどちらに移っていくのだろう?今話題になっているオニオンなんとかってやつ?

773 :デフォルトの名無しさん:2013/03/04(月) 06:53:18.05
>>769
じゃあお前死ねw
バカだからw

774 :デフォルトの名無しさん:2013/03/04(月) 07:38:16.94
>>767
出力しながら書いてみるわ。
あと本はググったけど、中古でプレミア価格になってた…。

775 :デフォルトの名無しさん:2013/03/04(月) 11:05:38.52
>>770
死ねゴミクズw

776 :デフォルトの名無しさん:2013/03/04(月) 11:27:35.95
http://digital.cs.usu.edu/~allan/DS/Notes/Ch22.pdf
この辺の絵を見るだけでも少し分かるんじゃないか。
いずれにせよ統計的な性質が重要。

ほぼ同じコストで最悪の時のオーダーがもっとよいアルゴリズムがあるけど、
スプレー木の様に特別な戦略がなくても、
回転すればある程度の改善ができることを知ることは重要。
回転もしない素の二分木はもっと悪いわけなので。

777 :デフォルトの名無しさん:2013/03/04(月) 12:16:21.31
>>775
死ねゴミ

778 :デフォルトの名無しさん:2013/03/04(月) 17:05:19.94
ちょっとした回転的な操作を入れれば
二分木でもだいたい何とかなると語ってたのはKnuth先生だっけ?

779 :デフォルトの名無しさん:2013/03/04(月) 17:17:23.00
たいていの平衡2分木は、2分木にちょっとした回転的な操作を入れたものだけど、
実装はどれも、微妙な操作を正確にやる必要があってなかなか難しい。

780 :デフォルトの名無しさん:2013/03/04(月) 17:28:42.19
具体例も示せない能書きはその辺りにしておけよゴ\ミ共

781 :デフォルトの名無しさん:2013/03/04(月) 20:27:54.71
なんでもかんでもベースはニ分木、異論は認めん

って言い切った方が逆にいろいろ可能性広がりそうだな

782 :デフォルトの名無しさん:2013/03/05(火) 07:49:59.60
>>777
線形野郎さっさと死ねw
ゴミクズがw

783 :デフォルトの名無しさん:2013/03/05(火) 11:46:09.41
>>779
セジウィックの本読めや
二重回転さえ理解出来ればそんなに難しくない

784 :デフォルトの名無しさん:2013/03/05(火) 11:50:32.90
>>782
死ねゴミ

785 :デフォルトの名無しさん:2013/03/05(火) 22:23:28.70
>>782>>784
うざい、シネコン

786 :デフォルトの名無しさん:2013/03/06(水) 08:41:23.59
>>784
黙れやキチガイw

>>785
死ねゴミw

787 :デフォルトの名無しさん:2013/03/06(水) 08:56:11.48
>>786
死ねゴミ

788 :デフォルトの名無しさん:2013/03/07(木) 01:09:48.11
ちょっと質問です。
「すべての順序に対して処理を行う」 いい方法はないでしょうか?

例えば要素数が 3 のとき、a[0]〜a[2] に対して、
・a[0] == 0 && a[1] == 1 && a[2] == 2 の場合
・a[0] == 0 && a[1] == 2 && a[2] == 1 の場合
・a[0] == 1 && a[1] == 0 && a[2] == 2 の場合
・a[0] == 1 && a[1] == 2 && a[2] == 0 の場合
・a[0] == 2 && a[1] == 0 && a[2] == 1 の場合
・a[0] == 2 && a[1] == 1 && a[2] == 0 の場合
に対してある処理を行いたいです。

要素数が x のとき、x! 回の処理を行うことになります。
オーバーフローに関してはとりあえず考えないことにします。

使い方として、例えば虫食い算などで、□に1〜9の数字を1つずつ入れて等式を完成させよという問題に対して、
総当りで解を探すのに使います。

よろしくお願い致します。

789 :デフォルトの名無しさん:2013/03/07(木) 01:39:46.48
「いい方法」って具体的には何を知りたいのよ?

順序から順序番号を取り出してジャンプテーブル使えばいいんじゃね、とでも言って欲しいのかね。

順序→順序番号変換は、
http://oku.edu.mie-u.ac.jp/~okumura/algo/ に置いてある permfac.c の encode 関数で
要素Nの順序→N-1桁の階乗進数へと変換できるので、
あとは
int val = 0;
for (int i = 1; i < N; i++) {
val += k[i] * a[i];
}
するだけ。ここで k[] = {0,1!,2!,...,(N-1)!}

790 :デフォルトの名無しさん:2013/03/07(木) 04:10:43.36
>>788
if(((1<<a[0])|(1<<a[1])|(1<<a[2]))==7) 何か処理;
みたいにできる

けど最初から重複しているものを処理対象にしないほうが効率的
>>789 の言うとおりにすりゃおk

791 :デフォルトの名無しさん:2013/03/07(木) 10:03:33.09
>>788
連立方程式を解くって意味なら、掃き出し法が簡単だなw
ググればソースも見つかると思うよ。

792 :デフォルトの名無しさん:2013/03/07(木) 11:17:55.75
>>788
C++ なら next_permutation()

793 :デフォルトの名無しさん:2013/03/07(木) 21:02:42.14
>>789-792
ありがとうございます! permfac.c の nextperm がまさに欲しいものでした。
やりたかったことが組めました!

>>792
…boost ならまだしも、まさか STL にあるとは思いもよりませんでした…。
調べてさえいませんでした。ありがとうございます!
色々使ってみて比べて行きたいと思います!

794 :デフォルトの名無しさん:2013/03/08(金) 16:59:45.37
>>787
死ねゴミクズw

795 :デフォルトの名無しさん:2013/03/08(金) 18:24:17.40
>>794
死ねゴミ

796 :デフォルトの名無しさん:2013/03/11(月) 04:55:21.80
>>795
だからてめえが死ねやゴミクズw

797 :デフォルトの名無しさん:2013/03/11(月) 11:31:32.65
ム板の一般的なスレッドの流れ

798 :デフォルトの名無しさん:2013/03/11(月) 11:57:17.98
>>796
死ねゴミ

799 :デフォルトの名無しさん:2013/03/12(火) 17:53:55.14
>>798
死ねゴミキチガイバカ丸出しw
死ねゴミクズw

800 :デフォルトの名無しさん:2013/03/12(火) 18:58:25.76
>>799
死ねゴミ

801 :デフォルトの名無しさん:2013/03/13(水) 23:17:05.07
ゴミゴミwww

802 :デフォルトの名無しさん:2013/03/13(水) 23:19:34.57
本で勉強しろよ馬鹿どもwww

803 :デフォルトの名無しさん:2013/03/13(水) 23:22:55.65
本を教えてくれよ

804 :デフォルトの名無しさん:2013/03/13(水) 23:23:31.53
クイックソート最高!他は糞!

805 :デフォルトの名無しさん:2013/03/13(水) 23:24:19.76
単方向リストと双方向リストどちらが優れていますか?

806 :デフォルトの名無しさん:2013/03/13(水) 23:34:54.21
>>805
シチュエーション次第

807 :デフォルトの名無しさん:2013/03/14(木) 00:05:35.21
コードが欲しけりゃ金だしな

808 :デフォルトの名無しさん:2013/03/14(木) 00:07:18.15
金が欲しけりゃコード出せ

809 :デフォルトの名無しさん:2013/03/14(木) 00:13:59.94
それは自己顕示欲の強いQZに言いな

810 :デフォルトの名無しさん:2013/03/14(木) 00:16:47.72
ゴミは要らないです

811 :デフォルトの名無しさん:2013/03/14(木) 01:58:33.57
>>804
シェルソートやコムソートも捨てがたい

812 :デフォルトの名無しさん:2013/03/14(木) 11:39:30.43
>>800
死ねゴミロボット涙拭けwwwwww
>>801
死ねゴミクズw

813 :デフォルトの名無しさん:2013/03/14(木) 12:43:53.33
>>812
お前がゴミクズwww

814 :デフォルトの名無しさん:2013/03/14(木) 13:08:36.71
ブサヨ同士発狂してるな

815 :デフォルトの名無しさん:2013/03/14(木) 13:33:47.14
ν速+に帰れプラス民

816 :デフォルトの名無しさん:2013/03/14(木) 13:46:12.91
そこでつっかかってるくってことは
お前もしかして在日朝鮮人?

817 :デフォルトの名無しさん:2013/03/14(木) 13:57:56.13
もしかしなくてもネトウヨうざい。
一生在日在日言ってろ。

818 :デフォルトの名無しさん:2013/03/14(木) 14:37:54.14
>>813
死にやがれバーカw

819 :デフォルトの名無しさん:2013/03/14(木) 16:40:17.51
>>818
お前が馬鹿のクズのアホ間抜けだwww

820 :デフォルトの名無しさん:2013/03/14(木) 16:50:43.80
>>817
はいネトウヨ言った
ネトウヨ言うのは在日しかいません、よってお前は在日

821 :デフォルトの名無しさん:2013/03/14(木) 17:23:02.97
在日連呼するのはバカウヨの証拠。
よってお前はバカウヨ。

822 :デフォルトの名無しさん:2013/03/14(木) 17:26:04.73
ネトウヨなんてありもしないのにネトウヨネトウヨレッテル貼り連呼して楽しい?在日

823 :デフォルトの名無しさん:2013/03/14(木) 17:40:22.15
在日在日連呼して何がうれしいの?

824 :デフォルトの名無しさん:2013/03/14(木) 17:46:18.38
そうやっていつも監視してるんですよねぇ?在日工作員さん

825 :デフォルトの名無しさん:2013/03/14(木) 17:46:27.91
スレ違い荒らしはなぜ通報されないの?

826 :デフォルトの名無しさん:2013/03/14(木) 17:48:45.39
>>824
大久保で外国人は殺せとかおまえの同類が喚いてるから、
今後おまえらを嫌う奴はどんどん増えるぞ。

827 :デフォルトの名無しさん:2013/03/14(木) 17:54:39.02
健全な日本人は在日を擁護するようなまねはしないからな
まずそこを理解して

828 :デフォルトの名無しさん:2013/03/14(木) 17:58:09.21
健全な日本人は大久保で「殺せ」とかデモをするバカを「健全な日本人」だと、
擁護するようなまねはしないからな。

まずそこを理解して。

829 :デフォルトの名無しさん:2013/03/14(木) 18:28:01.24
た〜たきだせー

830 :デフォルトの名無しさん:2013/03/14(木) 18:30:48.90
日本のために闘ってデモしてる人たちにそれはないわ

831 :デフォルトの名無しさん:2013/03/14(木) 19:43:43.05
>>814-828 をた〜たきだせー

832 :デフォルトの名無しさん:2013/03/14(木) 19:45:01.82
たたきだすべきは不法入国してる在日朝鮮人ども

833 :デフォルトの名無しさん:2013/03/14(木) 20:30:50.22
>>830
あいつらはお行儀が悪すぎるのでむしろ日本の恥

834 :デフォルトの名無しさん:2013/03/14(木) 21:50:05.25
在日利権くって反日活動してる在日のほうがよほど恥

835 :デフォルトの名無しさん:2013/03/14(木) 22:32:17.01
両方とも恥

836 :デフォルトの名無しさん:2013/03/14(木) 22:34:42.15
行動する右翼とかの連中
最初は上手く演出してたのに
最近は二言目には「腹を斬れ」と叫ぶようになって
支持者激減中
おそらく右翼を陥れようとする在日が沢山混ざってきてる

837 :デフォルトの名無しさん:2013/03/14(木) 22:56:45.59
街宣右翼と同じ方法だね

838 :デフォルトの名無しさん:2013/03/14(木) 22:59:33.48
在特会は在日、とか本気で言ってるんだもんなぁ。
頭、ほんとに大丈夫?

839 :デフォルトの名無しさん:2013/03/14(木) 23:01:00.13
保守の印象を悪くしているのも反日マスコミだしな

840 :デフォルトの名無しさん:2013/03/14(木) 23:01:55.97
>>819
死ねゴミクズw

841 :デフォルトの名無しさん:2013/03/15(金) 01:20:50.77
おまえら・・・いい加減にしろ。
スレ違いというか板違いだろ。

在日のこと話すにしろ、せめてデータ構造とアルゴリズムに関連付けて
話してくれ

842 :デフォルトの名無しさん:2013/03/15(金) 01:34:41.76
>>841
自治厨ウゼぇんだよゴミがでしゃばるな

843 :デフォルトの名無しさん:2013/03/15(金) 01:50:23.13
>>842
反抗期の小学生みたいなこと言うな

844 :デフォルトの名無しさん:2013/03/15(金) 01:54:48.70
>>843
自己顕示欲を満たしたいだけのゴミ自治厨がでかい口叩くな

845 :デフォルトの名無しさん:2013/03/15(金) 02:00:27.15
吠えるだけの内容しかない人は馬鹿にしか見えないんだけど
それ本人は分かってないの?

846 :デフォルトの名無しさん:2013/03/15(金) 02:02:21.94
端から見ると馬鹿にしか見えないけど、本人は格好良く暴れてるつもり
この病気の名前はなーんだ?

847 :デフォルトの名無しさん:2013/03/15(金) 02:04:29.01
>>844
IDのない匿名掲示板で「自己顕示欲」を持ち出すのは無理があるんじゃないっすか?

848 :デフォルトの名無しさん:2013/03/15(金) 02:34:30.32
>>847
自己顕示欲を満たすのに複数回書き込む必要あんの?
馬鹿かお前

849 :デフォルトの名無しさん:2013/03/15(金) 03:59:23.92
自己顕示欲を満たしたい奴が2chなんか来るわけないだろ

850 :デフォルトの名無しさん:2013/03/15(金) 11:46:08.97
匿名だから自己顕示欲を満たせるんだろ

851 :デフォルトの名無しさん:2013/03/15(金) 11:51:59.71
ボンバーマンの爆弾のアルゴリズムを教えてください

悩んでいるのは
@火力nで、プレイヤーと壁までの距離がnより小さかった場合、描画される火花はnより小さくなるがそれをどのように書くべきか
A火花は4方向に伸びていくがどのように書くべきか
B引火する処理はどのように書けばいいか

あたりのことです

852 :デフォルトの名無しさん:2013/03/15(金) 12:04:34.29
>>851
お前普通の2D描画レベルで躓いてるだろ

853 :デフォルトの名無しさん:2013/03/15(金) 12:18:09.66
はい

854 :デフォルトの名無しさん:2013/03/15(金) 12:19:21.35
はいじゃないが

855 :デフォルトの名無しさん:2013/03/15(金) 12:20:26.57
??

856 :デフォルトの名無しさん:2013/03/15(金) 12:20:26.82
偉そうに質問してんじゃねーぞコラ

857 :デフォルトの名無しさん:2013/03/15(金) 12:24:01.76
在日が偉そうに政治を語ってるんじゃねーよ

858 :デフォルトの名無しさん:2013/03/15(金) 12:26:42.63
自分の技量もわきまえずに質問するからこうなる

859 :デフォルトの名無しさん:2013/03/15(金) 12:28:18.58
今日本は大日本帝国時代の日本人の誇り高き精神を取り戻すべき

860 :デフォルトの名無しさん:2013/03/15(金) 12:29:30.14
ここ、ボンの質問禁止ですかね・・・。
ボンバーマンが作りたいのですが、爆弾のアルゴリズムが初心者のわてには難しすぎるのです
引火も考えないといけないし爆発リミットも考えないといけない
特に、過去に置いた爆弾の爆発が後から置いた爆弾に影響するところが難しく感じます

861 :デフォルトの名無しさん:2013/03/15(金) 12:33:25.88
差別や偏見なく国民各々が一心となって国力を上げる努力をすべき

862 :デフォルトの名無しさん:2013/03/15(金) 12:38:28.42
>>860
爆弾をスタックに詰んで全爆弾の判定すれば済む話じゃん。
お前アルゴリズム言いたいだけでコード全く書いてないだろ。

863 :デフォルトの名無しさん:2013/03/15(金) 12:39:41.83
ちゃらんぽらんに横から頭突っ込んで考えてみる
クラス 爆炎の先端{
  変数:現在位置、方向、残り走行距離;
  フレームごとの処理{
    現在位置に不動爆炎を設置;
    方向を用いて現在位置更新;
    爆弾やプレイヤーなど何かに重なった時の処理;
    残り走行距離を減らす;
    残り走行距離がなくなったら不動爆炎先端タイプに変化;
  }

クラス 不動爆炎{
  変数:現在位置、残り時間、絵のタイプ;
  フレームごとの処理{
    残り時間を減らす;
    絵を変化させる;
    残り時間がなくなったら消滅;
#    衝突判定はこのクラスではなく相手のクラスで行ったほうがよさげ;
  }

クラス 爆弾{
  変数:いろいろ;
  爆発したら{
    爆炎の先端を上下左右の4つ作る;
  }

なんて、こんないい加減な設計で上手く行ったら苦労はせんわな

864 :デフォルトの名無しさん:2013/03/15(金) 12:47:30.90
コードで書けよ在日

865 :デフォルトの名無しさん:2013/03/15(金) 12:50:48.74
バカウヨには擬似コードという概念もないらしい

866 :デフォルトの名無しさん:2013/03/15(金) 12:52:01.66
>>860
それは、アルゴリズムよりも、つまり計算手順(計算手続き)よりも
もう少し抽象度の高いゲームプログラムのレベルで躓いている感じがします。

「ゲームプログラムなら俺に聞け」のスレで質問されてはどうでしょうか。

あちらで質問して方針を定め、その方針を計算手順に落とし込む段階で躓いたら、
まちこちらで質問されるのが良いと思います。

あと、質問からあなたが作ろうとしているゲームの仕様があまり想像できないのですが、
再度質問される際は、仕様をはっきりと明記してくださいね。

例えばボンバーマンというゲームから私が想像するに、火力と関係があるのは、
プレイヤーと壁までの距離ではなく、置かれた爆弾と壁までの距離ではないかと思います。
爆弾を置いてから爆発するまでの間もプレイヤーは動きますから(でなきゃ死ぬ)。

867 :デフォルトの名無しさん:2013/03/15(金) 12:54:18.15
現代日本はこのような自分で考えることもできない糞を生み出した

868 :デフォルトの名無しさん:2013/03/15(金) 13:01:45.64
悪しき自己顕示欲を抑制することも出来ない馬鹿日本人を多く生み出した2ch

869 :デフォルトの名無しさん:2013/03/15(金) 13:21:23.75
私初心者だから抽象度とか言われてもわけわかんないバロス

870 :デフォルトの名無しさん:2013/03/15(金) 13:26:21.40
>>851
セルオートマトン的な発想でよくね

871 :デフォルトの名無しさん:2013/03/15(金) 13:28:04.14
在日朝鮮人こそが堕落した日本人の象徴である!

872 :851:2013/03/15(金) 13:30:38.25
すみません途中まで作ったのをupします
http://www.dotup.org/uploda/www.dotup.org4040527.zip.html
bombermanjava.classがメインクラスです
十字キーで操作、Fキーで爆弾設置、Eキーで情報表示、ESCキーで終了です

ここまでは作ってみたのですがこの設計だとちょっと無理な気がしてきて1から作り直そうと思ってます
一応自分で考えてみてはいるのですが頭が足りず上手くいかないので質問しました
アドバイスください

873 :デフォルトの名無しさん:2013/03/15(金) 13:41:01.74
javaかよ!javaでかいてんじゃねーぞ糞が

874 :デフォルトの名無しさん:2013/03/15(金) 13:43:03.44
>>872
謝罪と賠償を要求する!

875 :デフォルトの名無しさん:2013/03/15(金) 13:46:58.04
>>872
こんなものもオブジェクト指向でしか書けないジャバザハットが参上w

876 :851:2013/03/15(金) 13:46:59.14
>>863
>残り走行距離を減らす;

「残り走行距離を減らす」というのはどういうことですか?
もしかして、時間測って爆発させるのではないってこと?

877 :851:2013/03/15(金) 13:53:24.56
オブジェクト指向じゃない書き方って何ですか?
Javaしかやったことないプログラミング初心者&オブジェクト指向が何か知らないというレベルなので。。。
色んなサイト見ながらとにかく動くことを目指して作ったのでハチャメチャだと思います・・・

878 :デフォルトの名無しさん:2013/03/15(金) 13:54:12.26
Bombにも火元・延焼・類焼があるからな

879 :デフォルトの名無しさん:2013/03/15(金) 13:55:57.80
>>876
うん?もしかして爆弾と爆炎(爆風や火花といったほうがよかったか?)を勘違いされているのでは?

880 :デフォルトの名無しさん:2013/03/15(金) 14:07:50.31
ほら見て自己顕示欲を満たしたいだけの馬鹿が集まってきてるよw

881 :デフォルトの名無しさん:2013/03/15(金) 14:20:55.78
>>880 を筆頭にな

882 :デフォルトの名無しさん:2013/03/15(金) 14:26:04.76
と、自らの悪行を他人になすりつけるw

883 :デフォルトの名無しさん:2013/03/15(金) 14:36:02.48
自分のことは棚上げで謝罪賠償要求するチョンと気質が同じだな

884 :デフォルトの名無しさん:2013/03/15(金) 14:54:58.34
>>870
> セルオートマトン的な発想でよくね

もしかしてボンバーマンって、
チューリング完全だったりするのかな?

885 :デフォルトの名無しさん:2013/03/15(金) 15:07:25.91
>>883
日本語でどうぞ
棚上げの意味を知らないとかマジでチョン?

886 :デフォルトの名無しさん:2013/03/15(金) 15:38:03.53
あーあー見えない聞こえないw
またチョン病が発症かw

887 :デフォルトの名無しさん:2013/03/15(金) 17:02:09.28
888-1

888 :デフォルトの名無しさん:2013/03/15(金) 17:02:55.80
887+1

889 :デフォルトの名無しさん:2013/03/15(金) 19:05:23.25
ゲームについてはここじゃなくて「ゲーム製作技術」板で質問しろ

890 :デフォルトの名無しさん:2013/03/15(金) 19:14:13.96
ここでやっと正論が出た

891 :デフォルトの名無しさん:2013/03/16(土) 15:40:46.74
>>872
ちょっと見たけど読みにくい
コメントも全然ないし他人に読ませる気ないでしょ
未来の自分も他人だから後で困るよ

892 :デフォルトの名無しさん:2013/03/16(土) 15:46:51.17
で?

893 :デフォルトの名無しさん:2013/03/16(土) 15:54:42.84
ははははははははwwwwwww

894 :デフォルトの名無しさん:2013/03/16(土) 15:55:23.04
未来の自分が他人なら遠慮する必要は無いな

895 :デフォルトの名無しさん:2013/03/16(土) 16:22:00.07
じゃあ、未来の自分が自分なら遠慮するするのか

訳分からんな

896 :デフォルトの名無しさん:2013/03/16(土) 16:25:18.69
日本語大丈夫?在日朝鮮人

897 :デフォルトの名無しさん:2013/03/16(土) 16:31:23.38
ごめん、憶えたてでちょっとやばいかも知れん

勉強し直してくるわ

898 :デフォルトの名無しさん:2013/03/16(土) 16:42:58.14
>>872
Githubに登録しようず

そしたら見てやんよ
Java使ったことないけど

899 :デフォルトの名無しさん:2013/03/17(日) 01:31:13.20
むしろよくこのスレの流れで質問しようとするな
もうこのスレ終了してるから他行ったほうがいいよ

900 :デフォルトの名無しさん:2013/03/17(日) 03:50:46.96
いくら糞レスで埋めようがにぎわってねえからな
勘違いすんじゃねえぞ

901 :デフォルトの名無しさん:2013/03/17(日) 06:57:28.84
>>900
うるせえ死ねキチガイw

902 :デフォルトの名無しさん:2013/03/17(日) 10:59:19.58
アルゴリズムに正解なんてないからな
自分で考えろやゴミ

903 :デフォルトの名無しさん:2013/03/17(日) 13:58:07.67
>>902
死ねゴミクズw

904 :デフォルトの名無しさん:2013/03/17(日) 14:23:52.27
>>903
お前がゴミゴミンwww

905 :デフォルトの名無しさん:2013/03/17(日) 15:05:09.86
33 11 25 12

906 :デフォルトの名無しさん:2013/03/17(日) 15:06:43.28
馬鹿の書き込み時刻表

907 :デフォルトの名無しさん:2013/03/17(日) 15:35:41.91
>>904
黙れゴミゴミンw

>>906
お前の書き込み時刻表だなw
なっ、バカw

908 :デフォルトの名無しさん:2013/03/18(月) 07:35:36.62
スレ汚し大成功w
スレタイ通りに話するバカは死ねw

909 :デフォルトの名無しさん:2013/03/20(水) 09:45:00.72
バカは死ねw

910 :デフォルトの名無しさん:2013/03/21(木) 06:38:01.51
計算量について基本的なことなんですが教えてください。
このページに
http://imoz.jp/algorithms/imos_method.html
>記録には O(C) が,シミュレートには O(T) がかかるので,全体としての計算量は O(C+T) となります
と書いてありますが、ループを並べる場合ってO(max(C, T))ではなくてO(C+T)のように足し算してもいいんでしょうか?

911 :デフォルトの名無しさん:2013/03/21(木) 06:41:57.78
yes

912 :910:2013/03/21(木) 07:12:56.70
ありがとうございました。

913 :デフォルトの名無しさん:2013/03/21(木) 15:53:28.37
no

914 :デフォルトの名無しさん:2013/03/21(木) 18:03:50.12
>>911
ダウト
O(定数+定数)=O(定数)

915 :デフォルトの名無しさん:2013/03/21(木) 18:09:22.17
全部読んでないけど、この問題に出てくる C は定数の C じゃなくて、お客さんの数らしいんだよね。で、C も T も入力時に与えられる変数で定数じゃないみたい。

916 :デフォルトの名無しさん:2013/03/21(木) 18:33:19.53
スレチっぽいのでこちらへ誘導
http://toro.2ch.net/test/read.cgi/tech/1363854937/

917 :デフォルトの名無しさん:2013/03/21(木) 19:35:14.38
蟻本見たらループ回数が変数のループを並べる場合の計算量はO(N+M)みたいな足し算になってたよ

918 :デフォルトの名無しさん:2013/03/21(木) 20:02:39.94
そりゃそう書く事に意味があるからね

919 :デフォルトの名無しさん:2013/03/21(木) 20:59:34.15
しかしO記法は・・・

920 :デフォルトの名無しさん:2013/03/21(木) 21:19:03.77
死ねバカ共がw

921 :デフォルトの名無しさん:2013/03/21(木) 21:21:27.04
うるさい朝鮮人!

922 :デフォルトの名無しさん:2013/03/21(木) 21:24:14.50
O(C+T)でなくてO(N)でよい

923 :デフォルトの名無しさん:2013/03/21(木) 21:27:04.00
うるさいゴミグラマ!

924 :デフォルトの名無しさん:2013/03/21(木) 22:20:47.27
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7

==> [多変数の場合]

925 :デフォルトの名無しさん:2013/03/21(木) 22:26:46.93
うるさい自己顕示欲!

926 :デフォルトの名無しさん:2013/03/21(木) 22:49:12.83
>>919
しかしじゃねーよ
O記法勉強し直せ

927 :デフォルトの名無しさん:2013/03/21(木) 22:54:06.07
無学は罪

928 :デフォルトの名無しさん:2013/03/21(木) 23:55:33.93
関連の無い2つの変数があるなら
それは1つにはまとめられないよ

929 :デフォルトの名無しさん:2013/03/22(金) 05:29:51.69
それも違う

930 :デフォルトの名無しさん:2013/03/22(金) 07:28:48.49
O(M+N)でM側が常にゴミ同然ならO(N)でいいだろうが
MとNのどちらが支配的になるかがMとNの大きさによるのであれば
O(M+N)と書くべき

931 :デフォルトの名無しさん:2013/03/22(金) 07:54:43.83
最高時速を馬力で語るみたいなもんか

932 :デフォルトの名無しさん:2013/03/22(金) 08:46:26.65
>>928 >>930 は正しい。
グラフ探索で頂点の数がM、辺の数がNの時に探索のオーダーをO(M+N)と表すのが有名な例。

933 :デフォルトの名無しさん:2013/03/22(金) 09:20:04.90
↑アホ

934 :デフォルトの名無しさん:2013/03/22(金) 09:34:07.59
O(M+N)って例えばO( m^2 + n )や O( m + log(n) )という書き方できるの?

MとNが常に同じ次元なら別々に書く意味はそれ程ないと思うけど、別のものを使えるなら、
分けて書かないと意味が違ってくるような気がする。

935 :デフォルトの名無しさん:2013/03/22(金) 09:40:59.02
O( m^2 + n ) → O( m^2 )

O( m + log(n) → O( m )

936 :デフォルトの名無しさん:2013/03/22(金) 10:04:15.82
スレタイに沿って書きこんでるバカ死ねw

937 :デフォルトの名無しさん:2013/03/22(金) 10:14:13.87
>>934
できるよ。例えば
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

938 :デフォルトの名無しさん:2013/03/22(金) 10:18:27.83
なぜ項が消えるのか或いは消えないのかわかってない奴多すぎ

939 :デフォルトの名無しさん:2013/03/22(金) 11:33:32.61
解説頼む

940 :デフォルトの名無しさん:2013/03/22(金) 11:38:08.85
数が大きくなったときに影響力のでかい項はどれかって話じゃね

941 :デフォルトの名無しさん:2013/03/22(金) 11:39:19.96
解脱求む

942 :デフォルトの名無しさん:2013/03/22(金) 12:12:16.63
高校数学の極限辺りを勉強

943 :デフォルトの名無しさん:2013/03/23(土) 13:47:16.60
プッw

944 :デフォルトの名無しさん:2013/03/24(日) 06:32:32.23
死ねゴミ

945 :デフォルトの名無しさん:2013/03/24(日) 17:37:20.35
もう疲れたよパトラッシュ

946 :デフォルトの名無しさん:2013/03/24(日) 19:41:14.56
>>945
じゃあ死ねゴミラッシュw

947 :デフォルトの名無しさん:2013/03/24(日) 19:48:44.93
黙らっしゅ

948 :デフォルトの名無しさん:2013/03/25(月) 05:28:50.79
>>947
そんなお前が黙ラッシュw
死んじまえ糞ゴミw

949 :デフォルトの名無しさん:2013/03/26(火) 17:05:31.31
バーカバーカバカラッシュw

950 :デフォルトの名無しさん:2013/03/26(火) 17:08:42.13
超絶ゴミスレ

951 :デフォルトの名無しさん:2013/03/26(火) 17:48:27.34
そうか?
ム板の一般的なスレッドじゃん

952 :デフォルトの名無しさん:2013/03/27(水) 10:47:47.92
グーグルの予測検索って検索候補出すのめっちゃ早いけど
どうやってるかわかる奴いる?
あれってDBに問い合わせてあの応答速度なんかね
むかし予測検索と似たようなことやらされてクソミソだったからふと気になった

953 :デフォルトの名無しさん:2013/03/27(水) 12:51:00.48
在日工作員がよー!てめーが在日工作員なんだろーが!!!

954 :デフォルトの名無しさん:2013/03/27(水) 12:55:12.78
お前みたいな在日工作員が日本にはびこるから!!
日本がおかしくなるんだろーが!!!!!!!!

955 :デフォルトの名無しさん:2013/03/27(水) 13:23:48.85
俺はお前みたいな在日工作員が嫌いなんだよ

956 :デフォルトの名無しさん:2013/03/27(水) 13:42:07.72
次スレきぼんぬ

957 :デフォルトの名無しさん:2013/03/27(水) 13:51:53.85
わかったらとっとと本国に帰れよ!

958 :デフォルトの名無しさん:2013/03/27(水) 19:04:25.32
>>952
Googleを支える技術
http://www.amazon.co.jp/dp/4774134325/
に載ってるかも。

あるいは、きっと参考論文リストが載ってるだろうから、
そこから辿るとか。

959 :デフォルトの名無しさん:2013/03/27(水) 19:14:17.32
GOOGLEもできないチョン国人は半島に帰れ

960 :デフォルトの名無しさん:2013/03/27(水) 19:36:47.24
>>952 >>958
「Google を支える技術」持ってるけど載ってないな。

http://stackoverflow.com/questions/3670831/how-does-google-instant-work

を見ながら自分でも Firebug 実行してみたけど、キーワードを1文字入力するごとにクエリーして、たとえば "を" と入れると

window.google.ac.h(["を",[["ヲタみん",0,[4]],["ヲタル",0,[4]],["ヲタケン",0,[4]],["ヲタみん 顔",0,[4]],["ヲタク",0,[4]],["wowow",0,[4]]..

みたいなのが返ってくるね。
Google にログインしても、してなくても、結果が同じだから、毎回DBにアクセスするんじゃなくて、候補の入ったオブジェクトをキャッシュしておいて毎回それを返しているんだと思う。

961 :デフォルトの名無しさん:2013/03/27(水) 19:38:14.12
肺キター自己顕示欲満載の在日チョンの自演がキターw

962 :デフォルトの名無しさん:2013/03/27(水) 19:39:02.49
最高の頭脳はこんなところで油を売ってる暇はないし
暇があったとしてもとっくに他のコミュニティに移動してる

こんな匿名の叩き煽りが日常茶飯事で自分にメリットが薄いようなところは
最高の頭脳でなくともまともな人間でもさっさと去るよ

他にコミュニティがない10年前なら最高の頭脳もいたかも知れないが、
いつの間にかいなくなって今ではその幻想だけが残ってる

最高の頭脳持ってる奴は他のコミュニティに行っても入っていけるから困らなかっただろう
そしてそういったコミュニティで相手にされない奴が集まってるのが2ch

963 :デフォルトの名無しさん:2013/03/28(木) 06:59:04.64
700超えたあたりから良スレになったな
最高だよ!
それまではバカ共が知識ぶって騒ぐだけのクソスレw

964 :デフォルトの名無しさん:2013/03/28(木) 13:53:33.30
>>958
そっちじゃなくて、たぶん
『日本語入力を支える技術』の方だと思う
ローマ字やひらがなの入力から漢字の候補をサジェストしたりするから
多分ほとんど同じ技術を使ってる

965 :デフォルトの名無しさん:2013/03/28(木) 14:26:59.91
>>964
バカ共が知識ぶって騒ぐだけ

966 :デフォルトの名無しさん:2013/03/28(木) 15:04:25.92
>>952
Googleが予めマップリデュース使ってweb上の日本語の文章200億から計算したngramのデータがあるんだよ。
これはGoogleからDVDで買える。
iPhoneにもngram.datてGoogleのデータ入っててこれに問合せてるだけ。
予め膨大な単語毎にngramを計算済みだから速い。
俺iPhoneの日本語入力ハッキングするスレに
iPhone3G発売当初に常駐しとってiPhoneがSONYの増井の入力からGoogle工藤拓のmecabとngram.datに変更したの発見したんだわ。
最初Googleのデータ使ってるぞ!とかレスしたら嘘つき扱いされたんだけど、
工藤拓自ら講演会とかブログで宣伝するようになった。
ただ工藤拓がAppleにブチ切れて今は宣伝辞めてしまった。
iOS6もこないだJBしてみたら相変わらずmecabとngram.dat使っとるわ。

967 :デフォルトの名無しさん:2013/03/28(木) 16:03:37.69
>ただ工藤拓がAppleにブチ切れて

kwsk

968 :デフォルトの名無しさん:2013/03/28(木) 16:05:14.38
>>967
ggrks
http://www.chasen.org/~taku/blog/

969 :デフォルトの名無しさん:2013/03/28(木) 17:24:19.29
サジェストの動作的には
エッジを検索語と出現頻度にしたトライ木に見えるけどなあ
本当にn-gram?

970 :デフォルトの名無しさん:2013/03/28(木) 17:47:26.07
死ねゴミw

971 :デフォルトの名無しさん:2013/03/28(木) 23:46:20.34
ぅ座ゴミw

972 :デフォルトの名無しさん:2013/03/29(金) 07:04:01.92
>>970
うるせえ死ねゴミクズw

973 :デフォルトの名無しさん:2013/03/29(金) 10:57:13.99
>>972
ゴミは黙ってろwwwww

974 :デフォルトの名無しさん:2013/03/29(金) 16:51:21.82
>>973
ゴミはお前ださっさと死ねw

975 :デフォルトの名無しさん:2013/03/29(金) 16:54:22.18
こいつらまとめてマーク&スイープされちまえば良いのに

976 :デフォルトの名無しさん:2013/03/29(金) 20:19:10.18
とはいえム板の一般的なスレッドだしな
このレベルで規制してたらほとんどのスレ、つーか板ごと機能しなくなる

977 :デフォルトの名無しさん:2013/03/30(土) 08:53:09.57
>>975
ばかじゃねえのお前w
死んでしまえw

>>976
スレタイ通り話してるのがバカなだけじゃw

978 :デフォルトの名無しさん:2013/03/30(土) 09:07:06.40
>>976
まあ、2chも終わりということだな。

979 :デフォルトの名無しさん:2013/03/30(土) 09:45:28.90
>>976 >>978
2chはもう死んでいる

980 :デフォルトの名無しさん:2013/03/30(土) 11:29:16.65
久々にマ板のスレ見てるけどなんで死ね連呼してる基地外いるんだよ
どっかの頭イカれた学生かな

981 :デフォルトの名無しさん:2013/03/30(土) 11:45:47.96
自己紹介乙

982 :デフォルトの名無しさん:2013/03/30(土) 11:54:35.13
>>980=どっかの頭イカれた学生

983 :デフォルトの名無しさん:2013/03/30(土) 12:08:33.01
>>980
頭イカれた学生のくせにスレを素晴らしくしてる人たちをキチガイとか言ってんじゃねえよw
死ねゴミクズw

984 :デフォルトの名無しさん:2013/03/30(土) 12:15:10.41
春休みだなあ

985 :デフォルトの名無しさん:2013/03/30(土) 12:51:38.98
お前は年中春休みだろゴミw

986 :デフォルトの名無しさん:2013/03/30(土) 14:53:55.49
馬鹿ゴミ

987 :デフォルトの名無しさん:2013/03/30(土) 14:59:44.67
ちんこ

988 :デフォルトの名無しさん:2013/03/30(土) 21:36:38.05
>>985
進研模試の偏差値でいうと2ちゃんねるのニュース速報がおよそ45、民放地上波の報道ステーションが約40、
ニュース速報+は35程度の読者を想定しています。

989 :デフォルトの名無しさん:2013/03/30(土) 21:45:02.03
意味不

990 :デフォルトの名無しさん:2013/03/30(土) 23:05:30.99
>>988
それに似た話を見たことがあるな。

NHK地上波は、高卒50歳の主婦
民放地上波は、小学3年生
が視聴者だと仮定して番組作るって。

大卒はNHK-BSプレミアムを観ればいいとか。

991 :デフォルトの名無しさん:2013/03/31(日) 03:20:47.87
ぅメmass

992 :デフォルトの名無しさん:2013/03/31(日) 03:23:29.94
CHOYAゥメッシュ

993 :デフォルトの名無しさん:2013/03/31(日) 03:24:29.75
漱ゥ

994 :デフォルトの名無しさん:2013/03/31(日) 03:44:35.47
>>980
学生に見えるだろ?ところがこいつ結構歳いってるぽいんだよ

995 :デフォルトの名無しさん:2013/03/31(日) 04:21:41.84
このスレの終了と同時にム板の終焉が始まる

996 :デフォルトの名無しさん:2013/03/31(日) 04:23:33.66
次スレ

データ構造,アルゴリズム,デザインパターン総合スレ 2
http://toro.2ch.net/test/read.cgi/tech/1362301811/

997 :デフォルトの名無しさん:2013/03/31(日) 06:56:19.60
ざまあみやがれバカ共がw
そして死ねゴミクズw
次スレも素晴らしくなるだろうw

998 :デフォルトの名無しさん:2013/03/31(日) 09:08:34.03
ume

999 :デフォルトの名無しさん:2013/03/31(日) 09:35:01.30
999

1000 :デフォルトの名無しさん:2013/03/31(日) 09:36:27.81
1000げっと

1001 :1001:Over 1000 Thread
このスレッドは1000を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。

207 KB
★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)