- 1 名前：デフォルトの名無しさん mailto:sage [2012/03/21(水) 06:40:59.10 ]
- データ構造とアルゴリズムに関する総合スレ。
【関連スレ】
3Dアルゴリズム全般
toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
toro.2ch.net/test/read.cgi/tech/1217773415/
- 33 名前：デフォルトの名無しさん mailto:sage [2012/03/27(火) 18:31:43.60 ]
- 勤怠表はアルゴリズムってより
対象者向けインターフェースの推敲が難しいからな
ライン工相手に出勤退勤毎にキーボード叩けなシステムとかアホ過ぎるし
- 34 名前：デフォルトの名無しさん mailto:sage [2012/03/27(火) 19:08:39.50 ]
- タイムカードをがっちゃんがっちゃん押したらUSBでPC等につながって自動管理、とかの機械ありそう
- 35 名前：デフォルトの名無しさん mailto:sage [2012/03/28(水) 02:17:12.79 ]
- あながち馬鹿に出来ない
押し忘れとか、日付が変わってから退社とか、
３交替の夜勤とか
下手なものを作ると出勤か？退勤か？すら後で分からなくなるｗ
- 36 名前：デフォルトの名無しさん [2012/03/28(水) 08:50:46.61 ]
- >>31
エクセルで作ったぜ〜
www42.atwiki.jp/syugyou?cmd=upload&act=open&pageid=250&file=mei.xls
- 37 名前：デフォルトの名無しさん mailto:sage [2012/03/28(水) 10:21:13.89 ]
- >>34
うちのは無線LANで飛ばしてるお
- 38 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/03/29(木) 00:04:51.11 ]
- うん
- 39 名前：営利利用に関するLR審議中＠詳細は自治スレへ [2012/03/29(木) 08:31:17.45 ]
- タンピンリャンペーコーを判別せよ
- 40 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/03/29(木) 14:11:37.90 ]
- まず雀頭１と順子４つになっているか確認
その後１９字牌がないがチェック ない場合成立
二杯口は順子をグループ化してふたつどういつかチェックすればいいんでね
平和だけどタンヤオって時点で役牌じゃない＆二杯口も前提条件だから
両方が成立したとき自動的に成立
タンピンリャンペーコーを判定する専用ならこういうやり方でいいんでね
- 41 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/03/29(木) 15:50:35.74 ]
- >>39-40
君らみたいなのが宇宙麻雀作るんだろうな(´･ω･`)
>>40
待ちは？
- 42 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/03/29(木) 18:18:29.52 ]
- > 風牌や三元牌で順子可能
> ドラのみ和了
> 立直後明槓
> メンタンピン一盃口が役満
> 白があっても清一色可能
> 一気通貫が役でない
これはひどい
- 43 名前：営利利用に関するLR審議中＠詳細は自治スレへ [2012/03/30(金) 10:19:59.32 ]
- 宇宙麻雀ググッたけど
設定ミスで>>42とかプログラマー神すぎるだろ
- 44 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/03/31(土) 21:02:41.36 ]
- 閉路を沢山含んだインバースキネマティクスって
どうやればいいの？
もう既に有名なアルゴリズムとかあるの？
- 45 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/01(日) 05:42:22.57 ]
- 2-正則な閉路だけ考えた場合、移動した頂点から交互に重複するまで解決していくだけだし
そこから伸びた枝は普通に解決出来ないか？
- 46 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/01(日) 13:39:02.37 ]
- >>45
注意してもらいたいのは、要件は「閉路を含んだ」ではなく
「閉路を沢山含んだ」になっている点です。
例えば、以下のような格子状の関節(5*5)をもっている場合、
リアルタイムで計算させるのは結構難しいかと。
┌┬┬┬┐
├┼┼┼┤
├┼┼┼┤
├┼┼┼┤
└┴┴┴┘
もうすでに誰か偉い人がアルゴリズムを考えていたりしないかな、と。
- 47 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/01(日) 21:37:29.89 ]
- 一度通った道を再び通らないようにすることだけ考えりゃいいんだから
結局は同じじゃねえの
- 48 名前： ◆QZaw55cn4c mailto:sage [2012/04/01(日) 21:54:11.78 ]
- 「薔薇の名前」のアルゴリズムは使えないか？
- 49 名前： ◆QZaw55cn4c mailto:sage [2012/04/01(日) 22:27:20.12 ]
- >>15
toro.2ch.net/test/read.cgi/tech/1313183984/187
- 50 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/02(月) 06:58:39.00 ]
- >>47
もし簡単ならば、そのアルゴリズムを教えてほしい。
そしてその計算量の見積もりも。
でも、それが簡単じゃないからこそ今のIKは
軒並み「ループ無し縛り」を課している訳で。
- 51 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/02(月) 07:54:20.67 ]
- なんでQZがいんの
- 52 名前：１５ mailto:sage [2012/04/02(月) 14:36:11.40 ]
- >>49
ありがたまきんΩ
- 53 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/02(月) 18:42:03.65 ]
- さめがめの最適解を求めるアルゴリズムを
作ろうとしています。
□□●●□□●□●
○■●■●■●■□
○●●●□○□○●
□■●■●■●■□
■●□○□○□○●
□■●■●■●■●
■○□○□○□■□
□■●○●■●■□
■□□○□■□■■
ルール：
隣り合う２つ以上の連続した同じ種類の記号は消去できる。
重力あり。消えたら下に詰める。
連続で消せたら高得点
この仕様で、連続して消せる最大の回数を求めるのと、
完全に消去するという二つをそれぞれで考えたいのですが、
総当りだとものすごい時間がかかりそうなので、何か
数学的な理論や手法などはないでしょうか。
１）消せるブロックの集合を探す
２）ブロックを消す
３）消えたブロックの上のマスを落とす
４）１）に戻る
特に１）の部分の隣り合う２つ以上の連続した同じ種類の記号を
探すのが結構時間がかかりそうなので時間短縮する方法が
あれば教えてください。
- 54 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/02(月) 19:42:44.37 ]
- さめがめってNP完全でしょ。
> 総当りだとものすごい時間がかかりそう
試してはいないんだな。
- 55 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/02(月) 20:03:33.82 ]
- 発散しそうもないし、先ずは試してみたらいいんじゃね。
- 56 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/03(火) 10:14:52.66 ]
- 消せるブロックの集合が崩れてない時に
その情報を次のターンに持ち越せば少しは軽くなるな
- 57 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/08(日) 22:28:30.73 ]
- さめがめってよくフラッシュとかでもゲームあるけど、
ブロック消すところはなぜあんなに早いの？
思い浮かんだロジックだと、>>53を例にすると、
１）9x9のテーブルを２種類作る（Ａテーブル、Ｂテーブル）
２）Ａテーブルに記号別にフラグ（たとえば１〜５）を埋め込む
３）たとえば左上を基点に上下左右に同じ種類の記号が
あるか調べる
４）あったらＢテーブルに消せる場所に種類のフラグを埋め込む
５）基点から３）と４）を実行して全部調べる
６）Ｂテーブルに消せるマスがあれば、同じ位置のＡテーブルのマスを空白にする
７）Ａテーブルの空白のマスを消去し、上にマスが残ってたら下に下ろす
ここまでを一瞬でやってるわけですよね？
もっと簡単にできる方法があるのかな。
- 58 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 00:26:59.90 ]
- 1GHzのCPUで、一マスの処理が１０００命令かかるとすると、秒間１００万マスの処理が可能。
８１マスの処理なんて余裕すぎる。
- 59 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 00:52:48.40 ]
- なんで >>58 は、1クロック1命令だと思ったんだろう
- 60 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 01:03:57.34 ]
- ベンチでFLOPS計測するしかないってか。
- 61 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 09:21:58.82 ]
- え、でも計算量って１マス検査するのに、残りの８０マスをチェックしないと
いけないから、９ｘ９のマスのチェックをするのに、
８１×（８１−１）×・・・ってなるんじゃないの？
- 62 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 09:38:20.91 ]
- 隣り合ってるマスだけでいいだろ。
- 63 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 20:26:34.18 ]
- 1クロック1命令、っておおざっぱな見積りでは普通に使うだろうが
- 64 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 21:03:02.17 ]
- >>63
いいからあなたはPentiumだけ使っててください。
- 65 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 22:10:30.77 ]
- 大昔のBASICでは、PAINT文で塗りつぶしを行うと
塗りつぶして行く様子が目で見えてたなぁ
- 66 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 22:54:13.98 ]
- >>64
１クロック１命令の方がCPUとして少数派だと思うが・・・
２，３クロック１命令で見たほうが良くないか？
- 67 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 22:55:03.93 ]
- ごめ・・・
>>66は>>63向け
- 68 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 23:33:16.52 ]
- クロック周波数で性能は比較できない
- 69 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/09(月) 23:36:06.57 ]
- 総括すると>>63でオーダとしては妥当ってことじゃないの？
- 70 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 00:16:07.22 ]
- ｽﾚ違いだし、とっとと収束させるべきなんだろうけど…
>>69
>総括すると
頭おかしいのか？
- 71 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 00:20:24.86 ]
- オーダーは変わらない。
1命令が1クロックだろうが、100クロックだろうが変わらない。
- 72 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 00:30:55.57 ]
- 話がかみ合ってなくてワロスｗｗｗ
- 73 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 00:40:56.01 ]
- 1GHzのCPUで、一マスの処理が１０００クロックかかるとすると、秒間１００万マスの処理が可能。
８１マスの処理なんて余裕すぎる。
これでおk。
- 74 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 06:50:43.40 ]
- >>68 IPC（CPI）が同じなら、クロックが倍のコンピュータなら、
周辺による遅れがなければ、倍の性能だろうが。バカか？
- 75 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 11:26:00.65 ]
- アルゴリズムの文脈で、計算量ってどう見積もるのか知らない奴がこのスレにいるとは
- 76 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 11:47:24.19 ]
- 定数倍が重要なことも時にはあるだろうが
最初のレスがゲームについてなんだし
- 77 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 13:45:31.87 ]
- >>74
ふつー、バス速度は絶対に倍にはならないですよね…
- 78 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 18:16:05.89 ]
- >>62
そっか。
となれば、最大８１×４回（上下左右）チェックすればいいだけか。
さらに端っこのますは片側は壁だからもっと少ない計算量で
済むんだな。
- 79 名前：営利利用に関するLR審議中＠詳細は自治スレへ mailto:sage [2012/04/10(火) 23:10:48.23 ]
- >>75
見積もりといえばKKD法だよな。
- 80 名前：デフォルトの名無しさん [2012/04/14(土) 19:53:09.94 ]
- スケープゴート木って、サイズ計算に時間食い過ぎるな。
かと言ってノードにサイズ情報埋め込むのは本末転倒な気がするし。
- 81 名前：デフォルトの名無しさん mailto:age [2012/04/14(土) 20:57:57.57 ]
- 俺さ、ハッシュマップってのを思いついたんだが
- 82 名前：デフォルトの名無しさん mailto:sage [2012/04/14(土) 20:58:49.31 ]
- 車輪
- 83 名前：デフォルトの名無しさん mailto:sage [2012/04/14(土) 21:05:42.14 ]
- 八種抹粉
- 84 名前：デフォルトの名無しさん mailto:sage [2012/04/14(土) 21:09:24.55 ]
- いらなーい
- 85 名前：デフォルトの名無しさん mailto:sage [2012/04/16(月) 05:22:45.95 ]
- 一度車輪をやらないと上を行くアルゴリズム作るのは無理
- 86 名前：デフォルトの名無しさん mailto:sage [2012/04/16(月) 08:19:00.54 ]
- さめがめ：連続で消せたら高得点
てナニ？
- 87 名前：デフォルトの名無しさん [2012/04/19(木) 11:06:37.63 ]
- イナズマの描画法をおしえれ
- 88 名前：デフォルトの名無しさん mailto:sage [2012/04/19(木) 17:11:02.18 ]
- Ｎ
- 89 名前：デフォルトの名無しさん mailto:sage [2012/04/19(木) 17:13:32.69 ]
- Piローダーだっけ、イナズマローダーって
- 90 名前：デフォルトの名無しさん mailto:sage [2012/04/19(木) 17:24:40.05 ]
- >>88
Z じゃね?
- 91 名前：デフォルトの名無しさん mailto:sage [2012/04/19(木) 17:36:25.65 ]
- picとかだね
- 92 名前：デフォルトの名無しさん mailto:sage [2012/04/19(木) 22:52:28.58 ]
- CADで言うところのフィレット
２つの線分があり、端点の一つを共有している状態で
半径５のフィレットを行いたい
つまり、点P1(x1,y1) 点P2(x2,y2),点P1(x3,x3) で 点P2の部分をフィレットしたい
お分かりなる方がいたらおしえてください
- 93 名前：デフォルトの名無しさん mailto:sage [2012/04/19(木) 23:14:56.11 ]
- 内角に辺5のひし形作って対角を中心とした円
- 94 名前：デフォルトの名無しさん mailto:sage [2012/04/20(金) 03:22:59.96 ]
- >>92
点と直線の距離の公式を使って垂線の長さ5の方程式を二つ立てる。
これを連立方程式として解くと円の原点候補が二つ求まる。
点P2→点P1と点2→原点候補の内積が正になる方が円の原点である。
原点を中心とした半径5の扇を描く。
>>93
菱形の辺の長さが5なら内角が直角の時以外は円の半径は5より小さくなります。
- 95 名前：デフォルトの名無しさん mailto:sage [2012/04/20(金) 09:28:57.75 ]
- ArcTo関数か
俺なら自前でBezier2Dするねｷﾘｯ
- 96 名前：デフォルトの名無しさん mailto:sage [2012/04/21(土) 07:11:47.54 ]
- test
- 97 名前：デフォルトの名無しさん [2012/04/21(土) 07:13:42.88 ]
- 2と3だけを複数回かけてある数Aにもっとも近い数を作りたーい
- 98 名前：デフォルトの名無しさん mailto:sage [2012/04/21(土) 11:16:24.54 ]
- 総当り
- 99 名前：デフォルトの名無しさん mailto:sage [2012/04/21(土) 23:17:10.93 ]
- 宿題か
- 100 名前：デフォルトの名無しさん [2012/04/22(日) 21:33:27.78 ]
- 文字列が正しくデコードされてるか試験する、という目的の下、文字列の尤度を求めるために、
文字コードの範囲を確率変数として教師信号を用意（様々なファイルから読み込んだ文字列による）したのですが、
いまいち良い信号になりません。（正規分布に従わない）
ラテン文字帯が凄まじい数になり、ラテン文字を含めば全部尤度高い、という結果になってしまいます。
文字化けしたと思われる値（教師信号分布0の文字帯）の信号値を、より低い値にしたい（コストを大にしたい）のですが、
こういう場合、どういう風に信号を改善していけばいいでしょうか・・。
- 101 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2012/05/11(金) 14:08:02.26 ]
- 整数かつソートされていると保証されているなら
各配列にポインターをつけて
ポインター群でいちばん小さいものをresult配列に追加してポインターをインクリメント
でいいんじゃね
- 103 名前： ◆QZaw55cn4c mailto:sage [2012/05/12(土) 01:57:40.79 ]
- >>101
マージソートの応用でいけそうだ。
a, b, c, d, e の先頭なかから一番小さいものをとりだし result に書き出す。
ただし、それが z の先頭と等しかったら捨てる。
a〜e + z のなかで z が一番小さかったら、z の先頭を捨てる。
- 104 名前：デフォルトの名無しさん mailto:sage [2012/05/12(土) 02:53:22.74 ]
- なるほど
- 105 名前：デフォルトの名無しさん mailto:sage [2012/05/12(土) 11:59:03.22 ]
- ありがとうございます。
コーディングしてみます
- 106 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2012/05/14(月) 12:10:41.04 ]
- >>106
どうとでもできるとおもうけど
考えてるとおりにaからa'を出力するイテレータ(ジェネレータ)書けばいいんちゃう？
元の配列がソートされてるのにそれを利用しない手はない。
- 108 名前：デフォルトの名無しさん mailto:sage [2012/05/14(月) 12:24:59.78 ]
- >>106
103の「先頭なかから一番小さいものをとりだし result に書き出す。 」時に、
一番小さい数をある分だけ result に追加すれば良いだけだろ。
少しは考えれば分かるだろうけど。
- 109 名前：デフォルトの名無しさん mailto:sage [2012/05/14(月) 12:43:05.75 ]
- はい、今回はメモリもある程度限られた状況で
なんと言っても速度重視なので、
何パターンか考えて模索してみます。
- 110 名前：デフォルトの名無しさん [2012/05/24(木) 20:24:10.54 ]
- www.i.u-tokyo.ac.jp/edu/course/cs/pdf/2006computer.pdf
これの専門科目II-1 (4)がわからないんですが
方針だけでもいいので教えていただけないでしょうか？
- 111 名前：110の問題 mailto:さげ [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 名前：デフォルトの名無しさん mailto:sage [2012/05/25(金) 07:27:26.01 ]
- 手ダイクストラ法を逐次やって、既存の木と合流したら、最短経路の再計算で手が抜けるのでは？
- 113 名前：デフォルトの名無しさん mailto:さげ [2012/05/25(金) 17:00:13.49 ]
- 深さ優先探索の空間計算量って
木の最大深さm, 最大分岐数 b として O(bm) ってありますが、
一つのノードで分岐どうし順序がデータ構造のなかに定義されている、または自明であれば
O(m) になりますよね？
- 114 名前：デフォルトの名無しさん mailto:sage [2012/05/28(月) 17:28:58.85 ]
- ビー玉云々が何を言ってるのかよくわかりません。この例えは何か原典があるのでしょうか？
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 名前：デフォルトの名無しさん mailto:sage [2012/05/28(月) 17:44:51.94 ]
- ググり直した出典はありました読んでみます
- 116 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 00:17:18.82 ]
- diffの動作原理を知る〜どのようにして差分を導き出すのか｜gihyo.jp … 技術評論社
ttp://gihyo.jp/dev/column/01/prog/2011/diff_sd200906
これ全然理解できない・・・
- 117 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 09:26:36.11 ]
- >>116
「編集距離」で検索すれば分かりやすいページがたくさん
10年位前にOCRの認識率を計測するために色々とインプリメントしたな〜
- 118 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 09:35:41.80 ]
- 単純なアルゴリズム（長さMとNの文字列に対して計算量MNになるアルゴリズム）の
解説をすっとばして、実用的なアルゴリズムの解説になってるなぁ。
理解するためにはまず単純なアルゴリズムの解説を探すといいと思う。
- 119 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 11:11:01.86 ]
- >>116
技術評論社のサイト初めて見たけど、中々興味深い記事があるな。
- 120 名前：デフォルトの名無しさん [2012/06/05(火) 11:41:07.31 ]
-
【問１】
ある点が三角形abcの中にあるかどうかを判定する簡潔な方法を俺に教えよ
- 121 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 11:56:58.65 ]
- ぼくのかんがえたさいきょうの(ry
ある点をdとすると、
abc＝abd+acd+bcd（面積）
どうやって実装するのかはシラネ
- 122 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 11:58:14.51 ]
- ・重心とその点を結んで各辺と交わるかどうか調べる
- 123 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 12:10:29.02 ]
- いや結ぶのは三角形の一点でいっか
- 124 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 12:17:49.79 ]
- ごめん、嘘。でもベクトルの内積の符号を調べる方法で良かったはず。
- 126 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 12:38:23.40 ]
- 0 > (↑ab・↑ap)(↑ac・↑ap) かつ
0 > (↑bc・↑bp)(↑ba・↑bp) かつ
0 > (↑ca・↑cp)(↑cb・↑cp)
- 127 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 13:39:43.07 ]
- 目視で確認が一番簡素
- 129 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 13:49:07.51 ]
- >>121
これ？
upload.wikimedia.org/wikipedia/ja/math/3/2/f/32f967328ca04765e6804a07e6d1dbc7.png
- 130 名前：デフォルトの名無しさん mailto:sage [2012/06/05(火) 17:15:26.77 ]
- ヘロンの式だな
- 131 名前：デフォルトの名無しさん mailto: １２０ [2012/06/06(水) 10:50:47.34 ]
-
A. ありがとうございました
- 132 名前：デフォルトの名無しさん mailto:sage [2012/06/06(水) 17:46:11.37 ]
- 1. VRAMに三角形を描画して中を赤とかで塗る
2. 点に対応するアドレスの値を読み、背景色か赤か判定
BASICならたぶん2行で書ける
- 133 名前：デフォルトの名無しさん mailto:sage [2012/06/06(水) 17:49:59.95 ]
- えらい無駄が多いな
|
 |
