アルゴリズムに関する質問、議論総合スレ

なんとなくフリーセルのクローンを作ろうかなと思い立ち、頭の中で妄想
してみたんですが、問題作成アルゴリズムの見当が全く付きません；

どなたかクローン作った事ある方いらしたら大まかでよろしいので
教えて頂けませんか。。。

>>933
Windowsのフリーセルで、ゲーム番号の指定で-1か-2と入れてみな。絶対に勝てないから。

？ -1・-2は遊びでしょう。
アレ以外は全部解ける様に作られてるわけで。

とけるような配置を作ることは出来るのは分かるけど、
ランダムに配置した場合にとけない場合があるかどうかって証明済？

>>936
例えば、 -1・-2
乱数でばらまいて出る事はまずあり得ないけど。

CSVファイルの中身を検索したい場合、
今は、全部の行を配列に読み込んで、
その配列内をループして検索してますが、
ファイルの行数が300〜500くらいあるので時間がかかります。

もっと早く検索する方法ってあるんでしょうか。

>>938
どんなレコード構造で、どんなデータを探したいのか書け

次のような課題が出ました．
----
データ(x_i, y_i) [i=(1,2,・・・,N)] を直線近似する．
直線とそれぞれの点との 距離r_i の距離の和
Σr_i
を最小にする直線を求める方法でプログラミングせよ．
----

直線（ ax + by + c = 0 ）と点 (x_i, y_i) との距離は
r_i = | a * x_i + b * y_i + c | / sqrt{a^2+b^2}
なので，距離の和は
Σr_i
であり，これが最小になる a, b, c を求めればいいことはわかりました．
しかし，この先がわかりません．
最小自乗法の式の導き方はわかったのですが，
今回のやり方では偏微分の式の中に絶対値が入ってしまっているので，
どうしたらいいかわかりません．
ヒントください．

>>940
マルチポスト非常にうざい。
氏ね。

>>940
ttp://pc2.2ch.net/test/read.cgi/tech/1053963794/933-

>>941もマルチポストな罠

>>943
許してくれよ

レコード構造は
登録日(yyyymmdd),姓,名,姓ふりがな,名ふりがな,性別,年齢,E-Mail,電話番号

検索というより、ソートと抽出です。
全行を姓ふりがな、名ふりがなの値を利用して、五十音順（文字コード順）にソート。
その後、
性別（男、女、すべて）
年齢（20歳以下、30歳以下、40歳以下、すべて）
の条件に合うデータを抽出したいと考えています。

C/C++の宿題 のスレッドに書き込みしましたが，
こっちのスレッドのほうが質問の内容に適していると思い，
こちらに書き込みさせていただきました．
すいません．

945は939に対する返信です。

>>943-944
ワラタ
最高だ

>>946
もう遅い。自分で解決するんだな

>>945
検索するキーごとについて予めソートしておく。
それぞれのキーについて二分法で探索し、得られた結果の共通部分をとる。

>>949
がんばってみます．すいませんでした．

941 名前：デフォルトの名無しさん ：03/06/06 23:57
>>940
マルチポスト非常にうざい。
氏ね。


942 名前：デフォルトの名無しさん ：03/06/06 23:58
>>940
ttp://pc2.2ch.net/test/read.cgi/tech/1053963794/933-


943 名前：デフォルトの名無しさん ：03/06/06 23:59
>>941もマルチポストな罠


944 名前：941 ：03/06/07 00:00
>>943
許してくれよ 　　　　　　　　　

>950

あらかじめ、インデックスを作成しておくということですね。

全部の行を読むのは仕方ないにしても、検索処理は早くなりそうですね。
データファイルの更新日付を見て、更新されていなければ現在のインデックスファイルを
利用して、更新されていればその場でインデックスを作り直すというのがいいんでしょうか。

>>953
インデックス再構成のスケジュールは用途に応じて決めるべし。
オンデマンドで再構成だと応答の遅延が実用的でないかもしれないし、
更新が頻繁だとロックする必要がある。

検索が定型ならインデックスのインデックスを更に作っておくと早い。
例えば年齢に関するインデックス(それはレコードへのポインタの配列だろう)の
何番目からがn歳以上なのかをインデックスしておくと、検索の必要がない。

ただし、この配列の共通部分の計算がボトルネックになる場合は、
ソートせずにビットマップで持っておく。
例えば age[10] は i 番目の人が10歳であるときに age[10][i] = 1 であり
そうでなければ age[10][i] = 0 であるようなビットマップ。
これらのビットマップを年齢や単語などの数だけ用意しておき、
合致するデータをマスクとの積によって計算しビットマップの束として得る。
最後にこの束についてビット積をとることで求めたい共通部分が出る。
ビットマップ演算を bitfield で出来るのでtune-upしやすい。
また、定型の検索についてはマスクとの積を予め行なっておくことで、
要求時には共通部分をとる操作だけで済む。
googleなどで使われているのはおそらくこの手の方法じゃなかろうか。

n個の異なる数の集合から正確に(n+1)/2番目の要素、つまり中央値を縮小法を使ってアルゴリズムを設計しなさい。
ってでました。助けて下さい。

>>955
意味がわからん

>>955
寡聞にして縮小法というのを知らないのだが、
Hoareのfindアルゴリズムがそれになっていないかな？

手の始点と終点の座標及び関節が曲がることのできる角度から
関節部の座標を求めるアルゴリズムってなんでしたっけ？
わかりづらくてすんません。

>>958
インバースキネマティクス

ありがとうヽ(`Д´)ﾉ

有る点が領域（直線のみでよい）内に有るかの判断
何かいい方法有りますか？

>>961
意味がわからん。
2次元空間で、その領域が直線のみで囲まれているということか？

>>961
もしかしてこんなものをお探しですか？
http://www.google.co.jp/search?q=Ray-Intersection+Method&lr=lang_ja

>>962
すみません。そのとうりです

http://homepage.mac.com/hiroyuki44/hankaku10.html

>>961
ありがとうございます。
でも、この方法だと半無限線の方向が問題になると思われます
仮に半無限線を＋の水平方向にした場合

********* 　　**********
* 　　 * 　　 * 　　 *
* 　 * 　　* 　　 *
* × ******** 　　　 *
* 　　　　　 *
* 　　　　　 *
* 　　　　　 *
*************************

***********
* *
* *
* × *******
* *
* *
* *
*****************

上は交点３、下は交点２ですが
どちらも領域内部です

すいません絵がめちゃくちゃですね

************　　　　**********
*　　　　　*　　　　*　　　　*
*　　　　　*　　　　*　　　　*
*　　×　　**********　　　　*
*　　　　　　　　　　　　　　*
*　　　　　　　　　　　　　　*
*　　　　　　　　　　　　　　*
******************************

************
*　　　　　*
*　　　　　*
*　　×　　*****
*　　　　　　　*
*　　　　　　　*
*　　　　　　　*
****************

半無限線が水平で作成した場合
上は交点３、下は交点２ですが
どちらも領域内部です

半無限線て何？

996>>無限線の端点が固定された直線の事です

↑969>>の間違いでした

絵がうまく描けませんが、上は凹、下はＬ字型です

無限線て何？

>>969
半分、無限の線

>>973
無限の線

「線」・「直線」は、無限長。
「半直線」・「半無限〜」は、片側が端点で、もう片方が無限。
「線分」が、両方に短点を持つもの。

>>975
短点　→　端点　でした。
端点って辞書に載ってないのね。専門用語だから？それとも誤用？

直線・半直線は知ってるが、無限線・半無限線なんて聞いたことない。
どっかの業界の隠語？

CADでは日常ちゃめしごとと思われますです

http://homepage.mac.com/hiroyuki44/hankaku10.html

>>966 検索した>>963の中に、
＞方式１ 交差回数法: 点qから直線を引き、多角形と何度交わるか
＞方式２ 巻付判定法: 多角形をゴムに換えたら点qに巻付くか？
＞ ＝点qから見て多角形の線分を順に追いかけてゆくと１回転以上するかどうか

とあって、サンプルコードまで付いてるじゃないか。よく見てみなさい。

＞方式１ 交差回数法:y軸と交わった時の符号が正ならインクリメント
＞ 線分が y軸と交わるかどうかは 線分の始点終点のx座標の符号が違うかどうか

でサンプルコードはこうだ
＞ if ((rx<0)and(nx>=0)) or ((rx>=0) and (nx<0)) then begin
　　この部分で水平線はひっからないだろ？　

980>>ありがとうございます。水平線はひっかからない？
これは、方式２のサンプルですよね。
良く解らないですが（頭悪いので）、サンプル手に入りました。みなさんありがとうございました

>>981
１も２も考え方は違うけどコードは殆ど同じになると書いてあるぞ