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

アルゴリズムの質問、議論ならなんでもよし。
類似スレが多くてどこに書きこめば分からないときは
とりあえずこちらにどうぞ。

ありそうで無かったスレ。

とりあえず
「直線や円の2ドット以上の太さを持つ描画アルゴリズム」
をどうしてるか聞きたい。

>>3
刺繍と同じ。

代表的推薦図書

コルメン、ライザーソン、リベスト共著「 アルゴリズムイントロダクション全３巻 」近代科学社
http://www.amazon.co.jp/exec/obidos/ASIN/4764902451/qid=1014573379/sr=1-2/ref=sr_1_2_2/250-1126511-6613045
# 定番中の定番

Donald Knuth, "The Art of Computer Programming Vol 1-3", Addison Wesley
# バイブル

セジウィック著「アルゴリズムC(1-3巻) 」近代科学社
http://www.amazon.co.jp/exec/obidos/ASIN/4764902559/ref%3Dsr%5Faps%5Fd%5F1%5F3/250-1126511-6613045
# プログラミング言語がC(ただしスタイル悪し)。Knuthの弟子。

Christopher J. Van Wyk著「データ構造とCプログラム」Addison-Wesley社
http://shopping.yahoo.co.jp/shop?d=jb&id=30489974
# ほぼ完全なプログラムが載っていて初学者におすすめ。

＞「直線や円の2ドット以上の太さを持つ描画アルゴリズム」
ウチの会社の筆記試験だYo!

＞「直線や円の2ドット以上の太さを持つ描画アルゴリズム」
デバイスの解像度、速度優先か見た目優先か、アンチエリアシングするか、とかによって違うから、
これだけじゃ答えようがない、が正解。

>>7
じゃ、デバイスはPCのモニタ、速度優先、アンチエリアなしで。

だったら、１論理pixelづつずらしながら、ｎ回描画する、でええやん。

アルゴリズムの本って初心者向きと謳ってるけど
数学できないヤツは全然理解できないですよね
ということで数学やり直し中。黄チャートまでやったら読めるようになるかな・・・・

まず斜めの線の太さを定義してください。

x1,y1からx2,y2への太さを持つ直線の作画には
直線作画を少しづつずらしながら太さのぶん連続で行う方法と
円作画を少しづつずらしながら長さのぶん連続で行う方法があります。
がんばってください。

まともなグラフィックツールだったら1ピクセルずつずらしながら
描くなんてことはしてないよ。

とりあえず今実装してるのが円ずらしなんですけど、
あくびが出るほど遅いんですよ。
リアルタイムでやる必要があるのであくびが出ちゃうと
まずいな、と。

>直線作画を少しづつずらしながら太さのぶん連続で行う方法と
これはいいかも。0.5ピクセルずつずらせば大丈夫かなあ。

ありがとうっす。

>>13
意見聞きたいっす。

>>14
円ずらしって最悪でも最速アルゴリズムの８倍程度の処理時間におさまるはずだ
実装がまずいんじゃないの？

直線なら長方形と考えたらいいんじゃないの？
　太さ２だとして４５度の線なら途中は３ピクセル分水平にドットを並べる

円の場合も同じで、直径の違う２円として、水平に輪切りして処理するとか

>>14
まさか、毎回円を１から描いてるんじゃないよね？
直径ｎの円のビットマップ作って、転送してるよね？

('-`)｡o○（今時、水平ラインの描画がうんと速いと思ってるひと、いないよね）

>>19 水平ラインは速いよ　ビットマップを作る場合は特に

>>19
アクセラレータが使えないドでかい画像処理なら今もそうだよ

>>19　独自に描画エンジンを作る場合は　水平ラインが基本でしょう　特にプリンタなんかは

>>16>>18
すんません、言うの忘れてたんですけどレタッチ的なものを作ってるので
アルファブレンドも考慮に入れないといけないんす。
なので、ビットマップの転送ってのは出来ないんです。自力で計算しないと。

>最速アルゴリズム
聞きたいです。

>>17
あ、これもいいですね。直線ずらしは別バッファに一度書きこんでおかないと
重ね書きしちゃう可能性があったんですけどいいっすね。
ちょっとアルファ値の計算が時間かかりそうだけど問題ないかな。

>>14
> >直線作画を少しづつずらしながら太さのぶん連続で行う方法と
> これはいいかも。0.5ピクセルずつずらせば大丈夫かなあ。

横方向もDDLで書いてみるとどうなのかな?
pixelに空きが出来ちゃうのかな?

あ、横じゃなくて太さの方向ね。直線方向の垂直方向。

('-`)｡o○（1pixel=１bitでブロック転送を使うような、話の流れと違う特殊な状況を持ってくるなよ…）

つか、アルファブレンドするなら、（アルファブレンドが、単にα値なのか、
マスク画像かによるけど）それの時間がかかってるっぽいね。
だったら、出来るだけ同じpixelの処理を何度もやらない方法が速いでしょう。
もしかしたら、図形をポリゴンにして、スキャンラインにしたほうが速いかも。

プロファイルとってみたら？

>>23
αﾌﾞﾚﾝﾃﾞｨﾝｸﾞしても同じです
ﾌﾞﾚﾝﾄﾞのコスとがデカイなら、別に形だけマスクとして作っといて
マスクのあるとこだけ計算すればいいんだから

>>26=>>19
円ずらしをしてたので、遅い原因は同じ座標を何度も計算しなおしてる
ところにあったんす。ですので直線描画のアルゴリズムを見直せば（同じ
座標を計算しないようなアルゴリズムならば)アルファブレンドに関係なく
速くなるかな、と思ったんすけど。すんません。

とりあえず教えてくれたもの全部試してみるっす。

332=333なんだろうな(フ?

ごめん

シミュレーションゲーム（四角いマス）のキャラごとの移動可能範囲の
最速計算アルゴリズムはどうやってるんですか？

Ａ＊

B*

MD5を使って、ファイルのダイジェスト値をつかって
ファイルが変更されたかどうかをチェックする場合、
1/2^(16*8*2)の確立で失敗するんでしょうか？

MD5の計算方法ってどんな感じですか？

rfc嫁よ…

何番ですか？

逝ってよし。
http://www.google.com/search?q=rfc+md5

わからないからって、調べろっていうのも短絡的だね・・・
じゃあ、ここはいったいどう利用するの？

わからないから調べろってわけじゃなく
一々説明するのが大変だから既存の文書を読めって話でしょ。

>>39
少なくとも、「誰が調べてもすぐ答えが一つに定まるような
質問に答えるコーナー」として利用するのはつまらんではないか。

大勢に訊いて議論に持ち込む余地があるよーな質問、なら面白いが。

>>36
英語読めません...

>>42
読めるようになってから来てください。

>>39
初心者歓迎質問スレに行けば教えてくれると思う。

rfc見ても確か効能とソースだけだった記憶があるけど
ところで 1/2^256　というのは、宇宙が生まれてから滅びるまでに一度あれば奇跡と考えてよいような
数字だよ

＞ 1/2^256
この256はどこから出てきた？

>>46
多分>>45は>>35へのレスだと思われ。

MD5は16バイト＝16*8ビット＝128ビットなのを>>35のレスに
引きずられて16進32桁＝32*8ビット（本当は*4）=256ビットと
勘違いしたんじゃない？

再帰を普通のループに置き換える一般論を
解説してるとこ無いでしょうか。

>>48
ページの心当たりはありませんが、かなり昔のLispコンパイラの最適化に
関する記事で見た覚えがあります

>>48
再起 除去 あたりのキーワードで検索すれ。

tail recursion
末尾再帰

MD5で衝突したらfile本体を比べろよ...

円描画の一番簡単なアルゴリズムと一番速いアルゴリズムが知りたい。

>>53 簡単なのも速い方法も DDA

>>53
正１２８角形でもかけや。

void MonaCircle(double x, double y, double radius)
{
　　for (int i = 0; i < 360; i ++) {
　　　　double r = i * PI2 / 360;
　　　　PSet(x + cos(i) * radius, y + sin(i) * radius);
　　}
}

>>56
ツッコミ所満載で、どこにツッコんだら良いのやら･･･

ていうかギャグのつもりだろう。

y=sqrt(r^2-x^2) ってのは？
rは半径ね。
円の1/8だけ演算して、あとは鏡像をコピー。

>59
sqrtが重い

>>60
ターゲットによるでしょ。
SSE2でも平方根は有るんだし。

1/√x は 1/xに毛が生えた程度の演算量 だから√ｘはその２倍でしかない

　y=√(r^2-x^2) を微分して y*dy = -x*dy を求めて45°までの略算形式にするのがDDA

他の方法としては、汎用のベジェ描画を作ってベジェ係数に変換してしまうのが一般的で楽かも
といえば、じゃベジェ描画はどうするのか疑問が出るんだろうけど

とりあえず>>32へのレス
議題：n方向に移動可能なマップ上でのユニットの移動可能範囲の特定(微妙に汎用化)
条件：ユニットの移動力は移動により増加しないものとする(重要)
　　　マップと同じだけの大きさの0で初期化された解答格納用テーブルmap2(真ならば移動可能を示す)、
　　　ユニットの機動力move、がすでに宣言されていて利用できるものとする

解法：n方向に再帰する。再帰関数内では以下の処理を行う
コツ：map2には前回検索時の機動力が入る。これで比較処理での無駄が少しだけ省けるはずだ

void moveable(前回から見た移動方向, ユニットの座標，その他必要なものは考えれ)
{
　　int i;

　　ユニット座標の移動処理;　　/* ここでのユニットってのは実物じゃない。検索用のもの */
　　move = move - この地点への移動コスト;　　/* これも実物のじゃないぞ */
　　/* すでに今回より機動力が多い状態での再帰検索がなされているなら再帰検索を打ち切る */
　　/* テーブルは0で初期化されているため、これで機動力が0以下の場合にも対応できる点に注意 */
　　if (map2>=move) {
　　　　return;
　　} else {
　　　　map2=move;　　/* 移動できたぞ、と */
　　}
　　for(i=0; i<n; ++i)moveable(i, ...);　　/* n方向の再帰関数の呼び出し */
}
こんなんでいいのか？

まあ、はじめの呼び出しをどうやればいいかは宿題だな。
テーブルの初期化を含めて、それも一つの関数にしておくと楽だな。

>>63
4方向のやつはこれか
http://game.2ch.net/test/read.cgi/gamedev/1005040025/220

迂回路のコストが低い場合を考えて全検索すると無駄が出るから、
パスを作って枝借りしたほうがいいかも、っつーことで、
A* 調べろに１票

PhotoShopとかで領域を線で選択するときのアルゴリズムってどーやってんの？

void Circle2ch(unsigned long x, unsigned long y, float n)
{
float tx, ty, fy = y;
long i = 0, j = 0;
fy = -fy;
while(i <= j){
tx = i+x; ty = j-fy;
Pset(tx, ty);
tx = j+x; ty = i-fy;
Pset(tx, ty);
tx = -i+x;ty = j-fy;
Pset(tx, ty);
tx = -i+x;ty = -j-fy;
Pset(tx, ty);
tx = i+x; ty = -j-fy;
Pset(tx, ty);
tx = -j+x;ty = i-fy;
Pset(tx, ty);
tx = -j+x;ty = -i-fy;
Pset(tx, ty);
tx = j+x; ty = -i-fy;
Pset(tx, ty);
i++;
if((i*i+j*j-n*n-n) > 0) j--;
}
}

これは古い。微分補間の方が速い。
でもsin、cosでやってる人にはイイ。

二つの線分が、交わるかどうかを調べるアルゴリズムを教えて下さい。

>>68
いやーそれは数学の教科書見たほうが早いよ。

>>68
ここで調べて
http://www.google.co.jp/search?q=%90%FC%95%AA+%8C%F0%8D%B7%94%BB%92%E8

判らなかったら、そこを質問してね

>>66
領域を線で選択　のイメージが判らないので答えられないのだと思います

フリーハンドで描画したら、内部が選択領域になる、ってやつ。
うう、言葉で説明するの難しい。

windowsアクセサリのペイントブラシだったけの左上にあるフリーハンド領域選択？のこと？

そうそう、それ。

自分で考えたのは一度フリーハンドを描画してから左右1ピクセルずつ
大きくして左上から塗りつぶしを行って反転させる、って方法なんだけど
もうちょっといい方法あるかな、と思って。

>>74　単純にフリーハンドの塗りつぶしと同じアルゴリズムで　２枚のビットマップに分けてるだけでは？

最新 アルゴリズム事典 奥村著
のマンデルブロートのパラメータ教えてください。

xmin,xmax,ymin,ymax,maxiterの初期値例が載ってたような気がします。
(いま本が手元にない)

http://pc.2ch.net/test/read.cgi/tech/1016275511/8
ちょっと頼む。

>>77
そこら中で公開されとる検索せれ

囲碁を作りたいのですが、
石が囲まれてるか､囲まれていないかの判定をする
最速のアルゴリズムを教えてください。

>>79
石は置いた時にグループ番号を振る。
グループにはダメの数を記録しておく。
置いた時に隣接に同じ色の石があったら、自分も同じグループにする。
隣接に違うグループ番号の石があったら、そのグループの番号も自分の番号にする。
グループのダメの数は、自分のぶんを引き、自分のダメの数を足す。

こうしておくと、囲まれてるかどうかは、グループのダメの数を見ただけでわかる。

>>77
MTだ。
７行スレにソースあったぞ

今日会社で仕事さぼって二分木の勉強しましたが、おもしろいですね。

>>82
いまさら２分木を勉強してるあなたは何者？

>>83
そんなことで得意げになっているあなたは何者？

VB の本を読んでいるのですが、線形探索を一通り読んで、今二分木のとこまできました。
コンピューター関係の勉強をしていて、ゲームよりも面白い、と最近感じることが多くなりました。
仕事をさぼって勉強している、というのがまた良いんですけどね。
いかにも給料泥棒してるぞーって感じで。

ボソッ
×マンデルブロート
○マンデルブロー

>仕事をさぼって勉強している、というのがまた良いんですけどね。
>いかにも給料泥棒してるぞーって感じで。

いや、業務時間内の勉強は必ずしも給料泥棒とはいいきれない
「ライブラリの勉強にはむしろ通常の倍支払っても良い」
なんて書いてある本もあったよ

河西 朝雄さんのCとJavaのアルゴリズムの本は
どちらか買ったほうが（・∀・）ｲｲ？

囲碁で、コンピューター側の思考ロジックで良いアイディアありますか？

>>87
同意。勉強はサービスなんて言ってたらやってられないよ。

最近のCPUで二分木検索が有意な速度差を持つためには、
リストが１万件以上必要。
しかし、その場合、ソートに時間がかかるから、あぼーん。

>>89
オミー・Ｃ・リオキ法で検索するとよい。

>>91
はあ? キーが何かも定義せずにいい加減なこと言ってんなよ！
keyが32bit固定とかの話をしてるのかい?

ソートに時間がかかるってなんだい? sorted treeじゃないの?
二分木検索って二分木探索のこと?

返事しなくていいぞ、スレが汚れるから。

最初に全てを計算してテーブル等に入れるのではなくて、
必要になるまで計算しない技法のことを何といいましたっけ？
遅延なんとか？

遅延評価、遅延実行、lazy evaluation, lazy execution辺りでどう?

>>87
>>90
いやー実は私はISPのヘルプデスクなんですよ。
本当はTCP/IPとかADSLの勉強をしなきゃいけないんですけどね。
それらってつきつめると、結局Cで書かれてるじゃないですか。
わかんないことあって質問しても、すぐ
「ソース読め」
って言われるしそれでプログラミングの勉強はじめたらこっちの方が面白くなってきちゃったんでもうネットワークなんかどうでもいいです給料泥棒まっしぐら

>>96
それが真剣であるならそれこそネットワークスペシャリストになって、会社にもっと貢献できるだろ。
まぁ、いつまでも二分木やソートやってたら無理だが

よし！ 遅延評価でいこう。

一般的なコード↓
for(;h>0;h/=3){
　　for(int outer=h;outer<list.length;outer++){
　　　　int inner = outer;
　　　　Sortable temp = list[outer];
　　　　while((inner -= h) >= 0 && list[inner].getKey() > temp.getKey()){
　　　　　　　list[inner+h] = list[inner];
　　　　}
　　　　list[inner+h] = temp;
　　}
}
↓こっちのほうが速かった。
for(;h>0;h/=3){
　　int end = 2 * h;
　　for(int outer2=h;outer2<end;outer2++){
　　　　for(int outer=outer2;outer<list.length;outer+=h){
　　　　　　int inner = outer;
　　　　　　Sortable temp = list[outer];
　　　　　　while((inner -= h) >= 0 && list[inner].getKey() > temp.getKey()){
　　　　　　　　list[inner+h] = list[inner];
　　　　　　}
　　　　　　list[inner+h] = temp;
　　　　}
　　}
}

二つの長方形が共通の領域があるかどうか調べるアルゴリズム
誰か教えてください

二次元座標系、長方形は回転して斜めになっている場合でも適用できるようなの

うんこアルゴリズム教えて

>>100
いずれかの頂点が他の長方形の域内にあるか、
または二つの長方形の辺が交差しているなら共通の領域が存在する。

>102
レスありがと

やっぱり二つ組み合わせないとだめか

>>100 >>102
辺が交差しているかどうかを調べるだけでよくないっすか？

>>104
完全に含まれちゃってる時は?

あ，なるほどー。それがあったっすね。
失礼しました。

>>93
91の言ってることがよくわかってないな。

>>105
いずれかの頂点が他の長方形の域内にあるか、

106は誰やねん。

あ、104に言ってるのか。

あげげ

矩形内に円を描画するアルゴリズムを教えて！

ブロックソーティングと、算術圧縮のアルゴリズムが知りたい。

>>111意味分からん

>>111
座標と大きさを間違えなければ描画できるだろ。

>>112
BOOL block_sort_e(const BYTE* src,BYTE* dst,size_t size,unsigned int* index)
{
　unsigned int i;
　unsigned int* offset = NULL;

　assert(size > 1);
　assert(src != dst);
　assert(src != NULL && dst != NULL);

　offset = (unsigned int*)calloc(65536, sizeof(unsigned int));

　if (offset == NULL)
　　return FALSE;
　
　for (i = 0; i < size - 1; i++) {
　　unsigned int index = src[i] << 8 | src[i + 1];
　　offset[index]++;
　}
　offset[src[size - 1] << 8 | src[0]]++;

　for (i = 1; i < 65536; i++)
　　offset[i] += offset[i - 1];

　dst[ --offset[src[size - 1] << 8 | src[0]] ] = src[size - 2];
　for (i = size - 2; i; i--) {
　　WORD idx = src[i] << 8 | src[i + 1];
　　dst[--offset[idx]] = src[i - 1];
　}
　*index = --offset[src[0] << 8 | src[1]];
　dst[*index] = src[size - 1];

　free(offset);

　return TRUE;
}

続き。
BOOL block_sort_d(const BYTE* src,BYTE* dst,size_t size,unsigned int index)
{
　unsigned int i;
　size_t sum, count[256];

　size_t* offset = NULL;

　assert(size > 1);
　assert(src != dst);
　assert(src != NULL && dst != NULL);

　offset = (size_t*)calloc(65536, sizeof(size_t));
　if (offset == NULL)
　　return FALSE;

　memset(count, 0, sizeof(count));
　for (i = 0; i < size; i++) count[src[i]]++;
　sum = 0;
　for (i = 0; i < 256; i++) {
　　memset(dst + sum, i, count[i]);
　　sum += count[i];
　}

　for (i = 0; i < size; i++)
　　offset[(src[i] << 8) + dst[i]]++;
　for (i = 1; i < 65536; i++)
　　offset[i] += offset[i - 1];

　dst[0] = dst[index];
　dst[size - 1] = src[index];
　dst[size - 2] = src[--offset[(dst[size - 1] << 8) + dst[0]]];
　for (i = size - 1; i > 2; i--) {
　　WORD idx = dst[i - 1] << 8 | dst[i];
　　dst[i - 2] = src[--offset[idx]];
　}

　free(offset);

　return TRUE;
}

先頭文字の限定ソート

先頭２文字の限定ソート、ね。

>>115-117
最悪

>>115
2文字じゃ効果無いでしょ？
もっときっちりソートした奴書いて

算術圧縮
数字0,1,2の３値しかない。 出現頻度を 0が7 1が2 2が1 とする

数直線上に対応を描くと
．０．１．２．３．４．５．６．７．８．９　
　０　０　０　０　０　０　０　１　１　２

この表を逆にひく、最初の数が0なら領域 は 0.0<=W<0.7 というように。

最初が0なら 0.0<=W0<0.7 １なら 0.7<=W1<0.9
これを組み合わせて
値01なら 領域を 0.7*0.7< W01 <= 0.7*0.9
値10なら 領域を (0.9-0.7) * 0.0 + 0.7 < W10 <=(0.9-0.7) * 0.7 + 0.7
こういうふうに領域を分割してゆけば、数直線上の点の範囲として全ての組み合わせを表現出来る

W01,W10は範囲を含んだ表現なので、その必要精度だけのビット数で表現しなおせば
圧縮して表現出来るという理屈

>>120
ちょっとわからないので、ソース出してください

>>121
　書いた事は原理であって、
　実際のコードは整数演算で　吐き出したMSB分だけ全体を2^N倍しな
　がから考える必要があります。

120の説明の例で１０進で考えると
最初に２が選ばれた場合は 0.9=W1<1
となり最初の桁が 9と確定します。
確定すれば１０倍して９を吐き出します。

コードがどうしても必要ですか？

以下の規則で変換させるにはCでどうやってｺｰﾃﾞｨﾝｸﾞすればいいでしょうか
if文の羅列はしたくないんで、ﾋﾞｯﾄ操作でできないでしょうか
0x80->0x01
0x40->0x02
0x20->0x03
0x10->0x04
0x08->0x05
0x04->0x06
0x02->0x07
0x01->0x08

>>123
それぐらいなら、swich() で書けばいいとおもうが...。

>>124
typo した、switch() だ。

>>123

結局入力をxとして (-1 XOR (x-1) )を２進で表現して1の数を数えたいという事ですよね？

トリッキースレ
http://pc.2ch.net/test/read.cgi/tech/983191866/
にビット数を数えるコードがあります

あ！　もしかして ビット操作でって

for(i=1;i<8;i++) if( ( 0x100>>i ) & x ) break;
return i;

みたいな意味？

127さんのみてたら
for(i=0;i<8;i++){
if( ( 0x10>>i ) & x ){
break;
}
}
でできそうな感じがしてきました

>>128
気のせいだ。もっとよく >>127 を見ろ。

ごめん C はあんまり触りたくないから pascalのコードで悪いけど

>>123 を満たす関数を分岐・ループ無しビット操作だけで

function func(x:Integer):Integer;
begin
x:= (not (x-1)) and $FF;
x:= (x and $55)+((x shr 1) and $55);
x:= (x and $33)+((x shr 2) and $33);
x:= (x and $0F)+((x shr 4) and $0F);
Result := x and $F;
end;

>122
算術圧縮は特許だらけだとかここ↓で見た。
http://www.tomozo.ne.jp/yamazaki/download/doc_basic_compression.htm
RangeCoderの方がﾖｻｹﾞ？

Rangecorderも変形算術圧縮じゃん

アルゴリズムの勉強をはじめたのですが、
本を読んでいると２分探索は
実行回数：long n
計算量：O(log n)
等、いきなりでてきて、何を基にこういう式が求まるのかが
良く分かりません。
分かりやすく説明されている本やサイト、
もしくはどなたか説明できる方がいれば教えてほしいです。

>>133
算数とか数学でいいんじゃないかな？

Bサーチだと、
木が平衡な場合の最悪のケースの場合の探索の時間が
logN(底は２だよ）なのはわかるよね？

個人的には
アルゴリズム設計者になるわけではないのなら、
厳密な計算量がわからなくてもいいと思うよ。

1回比較を行うたびに範囲が半分になっていくのダ

>134
＞logN(底は２だよ）なのはわかるよね
とありますが、そのあたりが今一つ分からないんです。
logとか底が２とかがどこからきてるのかが分からないです。
数学の勉強からやり直さないとだめですかね・・・

> 厳密な計算量がわからなくてもいいと思うよ。
性格上、気になって・・・
できればすっきりして勉強進めたいかなと思うので。

>>136
logの意味は分かってるんだよね？

log　x　Y = Z なら
xのZ乗 = Y (逆もまた真)

二分探索するデータの総数がNとする。
1回の比較で、探索する範囲は約N/2になる。
(厳密にはN/2または(N-1)/2になる。)
もう1回比較するとさらに半分のN/(2の2乗)になる。
もう1回比較するとさらに半分のN/(2の3乗)になる。
…
そして、いずれ探索する範囲が1になる。

k回比較して1になったとする。
すなわち、N/(2のk乗) ≦ 1
これはk ≦ log2　Nと同じこと。
つまり、比較回数は高々log2　N回。

n個ので〜たの探索回数をxとすると
>>135に書いてあるとおり1回の比較で探索範囲は半分になるのだから
n = 2^x
よって
x = log n

>>137-138
ありがとう。関係ないけどよく分かったよ。

>137-138
なるほど、良く分かりましたo(^o^)o
はじめはlog nの底がてっきり常用対数の
10かと思ったりして混乱してました。
親切にありがとうございます。
本よりも勉強になりました(^_^;
いやーインターネットって本当に凄いですね。
そして、なによりも、見ず知らずの無知な私に
丁寧にアドバイスしていただいた方々に感謝です。
それでは、また、分からないことがあったら
よろしくお願いいたしますm(_ _)m

>o(^o^)o
>(^_^;
>m(_ _)m
2chで見るとムカツク

>>141
かわいい子からのメールならカワイく思える罠。

>>140
アルゴリズムの優劣を比較するときは、定数倍の違いを無視するんだ
よ。

例えば「かけ算をx回する必要があるアルゴリズム」と「たし算をx回
する必要があるアルゴリズム」では、たぶんたし算の方が何倍か速い
だろうが、どちらも「たし算をx^2回する必要があるアルゴリズム」
と比べれば、xを十分大きくすれば必ず速くなる。

底が2の対数と常用対数では、定数倍の違いしかない。なぜなら、
log10 x = (log2 x) / (log2 10)
1/(log2 10)は定数だから。つまり、底が何であっても同じこと。

>>137
不等号の向きが途中で逆になってる。

2 ＜ N/(2^k) ≦ 1 をみたすkがあったとすると、
2^(k-1) ＜ N ≦ 2^k だから、
k-1 ＜ log N ≦ k

「比較回数はlog N回以上必要だが、(log N)+1回はいらない」
つまり「ちょうどlog N回」が正しい。

> 2 ＜ N/(2^k) ≦ 1 をみたすkがあったとすると、
> 2^(k-1) ＜ N ≦ 2^k だから、
> k-1 ＜ log N ≦ k

気が狂ってるな。
1 ≦ N/(2^k) ＜ 2 をみたすkがあったとすると、
2^k ≦ N ＜ 2^(k+1) だから、
k ≦ log N ＜ (k+1)

フェルマーテストは、O(log n)の増加なので、
1000000近くの素数をテストする時間を1000近くの
素数をテストする時間と比べどのくらいと予想するか。

って1000000近くのテストは1000近くのテストの1.5倍ですか？

ん？2倍だろ？

log10 1000 = 3
log10 1000000 = 6
よって、２倍でいいの？

>>147
まあそうだけど、底が10でなくても
(log　x　1000000)/(log　x　1000) = log　1000　1000000 = 2
だ。(1000や1000000が何進法でもOK。)

バケットソートとバケツソートと分布数えソートは全て同じ物ですか？
また、分布数えソートよりも逆写像ソートを使った方がいい場面というのはあるのですか？

違う

陰面処理のやり方って堂やんの

保守

さめがめの最適解を算出するアルゴリズムおしえれ

>>153
その前にお前が自力でさめがめを作れるかどうかをおしえれ

>>154
作れる

質問です。
二次元座標上に、円と線がある時、この線が円と交わる点(0ヶ所か、1ヶ所か、2ヶ所)
の座標を求めたいのですが、どのようにすれば求められるでしょうか？

数学ｻﾊﾟｰﾘなのですが、一応自分でも考えたのですが詰まってしまいました。
私が足りない頭で必死に考えた方法は、この線を直角三角形の斜辺として考えれば
良いのではないかと思ったのですが、その先が思い付きませんでした

よろしくお願いします。

>>156
円の中心とその線までの距離を求めて円の半径と比較

>>157
レスありがとうございます。

ちょっと質問が分かりづらかったのかもしれません。
交わっている点の数ではなくて、
交わっている座標を知りたいのです。

よろしくお願いします。

>>156
普通に線と円の方程式を連立して解いたらいかんの？

>>159
レスありがとうございます。

「普通に」と言われてしまうと悩むのですが、
そう言われても私には「線と円の方程式を連立して解く」という言葉の意味すら
理解できないのです。
「線 円 連立 方程式」で Googleってみましたが、
それらしいものが見つかりませんでした。

どういう事をすればよいのでしょう？
よろしくお願いします。

>>156
いま、線はどうやって表現しているの？2点を通る直線？

>>161
レスありがとうございます。

はい、２点を通る直線です。
この線と、その延長線上で、円と交わる点の座標を得たいのです。

よろしくお願いします。

とりあえず、2点の座標から直線の方程式を求める。
2点(Px,Py)(Qx,Qy)を通る直線の方程式は
(Qy-Py)(x-Px)-(Qx-Px)(y-Py)=0となる。
ここまでいいかい？

直線の式y=ax+bを円の式(x-c)^2+(y-d)^2=r^2
に代入して
その結果の式
(x-c)^2+(ax+b-d)^2-r^2=0
を公式で解く、というのが王道だと思う。
あとは「円の方程式」とか「二元方程式の公式」とかで適当に検索しる！

>163
スマソ、見てなかった・・・

>164
いいさ。

>>163-164
ありがとうございます。
ｻﾊﾟｰﾘ理解できませんが、公式と検索のヒントを教えて頂けたので
後はなんとか自力で頑張って理解したいと思います。

本当にありがとうございました。

>164
2元方程式？
2次方程式じゃないの？
変数がxしかないので1元では？

>>167
　もし見つからなかったら、直線をX軸に、円の中心をy軸にあわせると
単なる３角形になるから考え易くなると思うよ

うーん、コンピュータで計算できる公式に直す事ができないです。
「二元方程式」だけでググルって57件しかないので、
片っ端から見ても……？？？？？？う〜ん。

>>168
二次方程式なのでしょうか？
あらゆる二次方程式は解の公式に変形できると書いてあるサイトを見つけたのですが
↑もできるのでしょうか？

>>169
直線を X軸に合わせるというのはどういう事でしょうか？
円の中心を Y軸に合わせるというのはわかるのですが…。

>>170 = >>156
今何歳？

そう、二次方程式だ。書き間違えたよ。無駄な時間を取らせてスマソ＞156
鬱だ詩嚢。
あと、164の式中の ax というのは a*x のこと。
^2 はもちろん二乗のこと。
円の方程式は
円の中心の座標が(c,d)で、半径が r のときに164の式になる。
念のため。

>166
ありが�d！

>>171
大人ですよ(汗)

学生時代は数学の時間は寝るものだと決めていたので…。
今になって禿しく後悔しています。

実は円じゃなくて四角形で代用できるような問題の気がしてきました。
四角形なら線と線の交わる点だけでいいですね……。
四角形で片づけようかな…。

>>173
直線って、ひょっとして水平か垂直な直線だけなのか？

>>172
大丈夫です。表記は読めました。
ありがとうございます。

>>174
いえ、さすがにそれはないです。

いちおう展開してみたけど、これでいい？
もっと変数減らせるかは知らん。

D = 2ac(b-d) - r*r

D < 0 で０個

x = c - a(b - d) ± sqrt(D)
y = ax + b

a = (Qy - Py) / (Qx - Px)
b = a * Px - Py

>>176
全然違う。

>>176
ありがとうございます。
VBScript で計算してみたのですが、ちょっと答えが変です。
私、何か解釈し間違っているでしょうか…。
LargeD = 2 * a * c * (b - d) - r * r
If LargeD >= 0 Then
　x1 = c - a * (b - d) + sqr(LargeD)
　y1 = a * x1 + b

　x2 = c - a * (b - d) - sqr(LargeD)
　y2 = a * x2 + b

　MsgBox "ans1=(" & x1 & "," & y1 & ") ans2=" & x2 & "," & y2 & ")"
End If

コピペしまちがえました。
こっちです。
VBScript ですが、読めると思います。

Option Explicit
Dim a, b, c, d, r
Dim LargeD
Dim Qx, Qy
Dim Px, Py
Dim x1, y1, x2, y2

Qx = 1 : Qy = 0
Px = 0 : Py = 2
c = 1
d = 0
r = 1

a = (Qy - Py) / (Qx - Px)
b = a * Px - Py

LargeD = 2 * a * c * (b - d) - r * r
If LargeD >= 0 Then
　x1 = c - a * (b - d) + sqr(LargeD)
　y1 = a * x1 + b

　x2 = c - a * (b - d) - sqr(LargeD)
　y2 = a * x2 + b

　MsgBox "ans1=(" & x1 & "," & y1 & ") ans2=" & x2 & "," & y2 & ")"
End If

これかな？
もう自信ない。

k = (a*c + b - d) / (1 + a*a)
D = r*r - k*k

x = (c - a*b + a*d) / (1 + a*a) ± sqrt(D)

これでいい？

k = (a*c + b - d) / (1 + a*a)
D = r*r/(1 + a*a) - k*k

x = (c - a*b + a*d) / (1 + a*a) ± sqrt(D)

b = Py - a * Px

うわー！みなさんありがとうございます！！
それらしい値が出てきました！！
結局全部他力本願になってしまいましたが、皆さんのおかげで
なんとかなりそうです。本当にありがとうございます。

Option Explicit
Dim a, b, c, d, r
Dim LargeD
Dim Qx, Qy
Dim Px, Py
Dim x1, y1, x2, y2
Dim k

Qx = 1 : Qy = 0
Px = 0 : Py = 2
c = 1
d = 0
r = 1

a = (Qy - Py) / (Qx - Px)
b = Py - a * Px

k = (a * c + b - d) / (1 + a * a)
LargeD = r * r / (1 + a * a) - k * k
If LargeD >= 0 Then
x1 = (c - a * b + a * d) / (1 + a * a) + sqr(LargeD)
y1 = a * x1 + b

x2 = (c - a * b + a * d) / (1 + a * a) - sqr(LargeD)
y2 = a * x2 + b

MsgBox "ans1=(" & x1 & "," & y1 & ") ans2=" & x2 & "," & y2 & ")"
Else
MsgBox "No junction " & LargeD
End If

n個の行列M1,M2,M3....,Mnが与えられたときに、スカラー乗算の回数が
最小になるように行列積M1M2M3…Mnに括弧をつける問題に対する
アルゴリズムを、コードじゃなくて日本語で説明してください。

数学板に逝け。

板違いスマソ

動的計画法について教えてください。

動的計画法？
何の？
トポロジカルソーティングの事か？

順列生成のアルゴリズムで一番速いのって何ですか？
辞書順でなくてもいいです。

ダイクストラ教授が72歳で死去。

ttp://news.lycos.co.jp/comp/story.html?q=10impressi03&cat=14

http://www.cs.utexas.edu/users/UTCS/notices/dijkstra/ewdobit.html

正直、とっくに亡くなってると思ってた。。
（だって、「ダイクストラの亡霊」とか言うじゃん。いやうそいわないかも。。）

ボイヤ・ムーアでなぜ高速検索できるのかわかりません

検索しなくても良い部分をはしょっているから

>>192 ちゃんとした解説は市販本でも読んでいただくとして・・・

n文字テキストからm文字キーワードを探す場合、
キーワード末尾の比較を行って、一致しなければ、一気にm文字分比較したのと同じ効果が得られる。
すなわち、最小比較回数が n/m 回になる。そして、実際もかなり小さい。

他の方法（KMPとか）は、必ず n 回比較するので、BM法の方が速い。

BMって、素朴サーチと比べてオーダは小さそうだけど
定数部分がおっきい感じがする。


って言うか、多バイト文字とかBMで検索するのって
難しそうだし。

>>194
＞＞n文字テキストからm文字キーワードを探す場合、
＞＞キーワード末尾の比較を行って、一致しなければ、一気にm文字分比較したのと同じ効果が得られる。

まさにそこがわからんのです。
説明しずらいのですが、n文字列の先頭（厳密には先頭でないが）からキーワードの末尾との比較を行い、一致しなかったら次はキーワードの末尾の一個前（後ろから2番目）と
比較を行い、文字が一致すれば一文字文スキップする。一致しなければ、またキーワードの今比較した文字の一個前（キーワードの後ろから3番目）と比較して文字が一致すれば
2文字分スキップする。一致しなければ、同様にキーワードの後ろから4番目と比較する、、、、というふうにキーワードをスキップさせて行くんですよね？

これだと比較の回数はn／m回にはならないのですが、、どうでしょう？
何か私の説明は間違ってますか？

> ＞＞n文字テキストからm文字キーワードを探す場合、
> ＞＞キーワード末尾の比較を行って、一致しなければ、一気にm文字分比較したのと同じ効果が得られる。
> まさにそこがわからんのです。
テキスト側の一致しなかった文字を x としよう。
もし、x がパターン文字列に含まれていなければ、一気に m文字分
スキップできる。これは OK?
もし、x がパターン文字列に含まれているなら、その出現位置によって
スキップできる文字数が決まる。
実際には、マッチングに先立ち、パターン文字列をもとにして、この
「スキップできる文字数」のテーブルを使っておく。

× 使っておく
○ 作っておく

>>195
表を１つだけつかうならば、定数部分はそんなに大きくないよ。
演算数は、せいぜい2倍。

もちろん、パターンが１文字とか２文字とか、
アルファベットサイズが２とか１０くらいだと、単純法より遅くなるだろうけど。

多バイト文字は、まぁ、wchar_t とかJavaのcharとか、
あるいは自前で (unsigned) short int とか、使ってやってくれぃ。

>>195,>>199
ShiftJIS や EUC とかでも別に難しくはない。
普通にBMでマッチングかけた後、マッチした部分が1バイトずれた
ところでないかどうかをチェックすればよいだけ。

>>197
レスありがとうございます
>>もし、x がパターン文字列に含まれていなければ、一気に m文字分
>>スキップできる。これは OK?

これは理解できます

しかし
>>もし、x がパターン文字列に含まれているなら、その出現位置によって
>>スキップできる文字数が決まる。
この説明で、出現する位置まで一つ一つ比較を行っているとれば

>>194さんの説明の最小比較回数がn／mになることはありえないと思うのですが、

>>201
オーダーで考えればO(n/m+m-1)=O(n/m)だな。
あるいは、見つからなければn/mである。

教えてください

円周上におかれた、3点の座標から、その円の半径と、中心座標を
求めるプログラムを書きたいのですが・・・。

どっかに、アルゴリズムありませんか？・・（＾＾；

よろしくーです

>>203
３点でわかるの？
１２０度ずつの３点なら中心求めれば簡単だけど
０、１、２度の３点ではわからないのでは。

>>203
残念ながらその最適アルゴリズムは俺様が特許を持っています。

え？・・特許ですか？・

円の方程式から、連立方程式を立てて、解けばできると思うんですが・・。
やっぱり、ガウスジョルダンとか使わないとだめなのかな・・・

めんどくさいよー

引き続き、ご意見募集

>>203
高校数学の問題。「三角形の外心」で調べろ。

>>204, >>205 も中学からやり直し(w

>>205
残念ながらその発言方法はボクが特許を取っています。
月末に特許料の請求書を送りますので、間違いなく振り込んで下さい。

>>204
３点で解けないのは楕円だけだろ

ある５リズム
（ズンチャチャズンチャ）＾ｎ

>>207
外心の計算をする場合、２元２次連立方程式、あるいは、３元２次連立方程式の
解をもとめないと、いけないの思うのですが、
プログラム上で、連立方程式を行列で解くのが、手間なので質問してます（−−；

よろしくです。

google で検索すれば山のように見つかると思うが。

>>212
このスレの趣旨わかってないだろ

>>211
定規とコンパスを使って外心を求める方法は中学校で習わなかったか？

ありがとうございました。

なんか、数学の板に同じ質問をしていた人がいたので、
参考にさせてもらいました。

マルチに踊らされたな

>>215
　よかったね。　じゃ回答のあるリンクをひとつのせておくよ
http://www.infoeddy.ne.jp/~tensyo/prog/linealgo.htm

文章から単語を切り分けたいんだけど

英語？半角スペース？

>>218　英語の場合は　空白で区切る　行末が -ならつなぐ
日本語の場合は人工知能のまず開発をお願いします

>>220
日本語の場合は茶筅とか案山子使えばいいんでは？
英語の行末ハイフンは連結語のハイフンも兼ねている場合があるので、
単語辞書も持っていたほうがいいね。

日本語で
細かい文法的なことはあんまりきにしないで
漢字の単語だけ切り分けたい
茶筅　案山子　ってなんですか？

検索しようよ。その用途なら Kakasi 向き。
漢字コード決め打ちして、Perl などで正規表現使っても良いと思う。

ChaSen
http://chasen.aist-nara.ac.jp/
Kakasi
http://kakasi.namazu.org/

インタラクティブな万華鏡ソフトを作ろうとしています。ある図形から正三角形を切り出すところまで終わりました。
三角形の各辺の中点を軸に180度回転させながら、図形を形作ろうと考えてます。
もっと良いアルゴリズムがあったら教えてください。

>>224
　sageで聞いても皆が見てくれないよ。

とりあえずもっと良いアルゴリズムって言われてもなあ
bitmapをリージョンかけて切り出してそれをまた回転するくらいかなあ

多バイト文字は、まぁ、wchar_t とかJavaのcharとか、
あるいは自前で (unsigned) short int とか、使ってやってくれぃ。

k = (a*c + b - d) / (1 + a*a)
D = r*r/(1 + a*a) - k*k

x = (c - a*b + a*d) / (1 + a*a) ± sqrt(D)

X = x[1] ... x[n]とY = y[1] ... y[n]というサイズnの配列があって、
それぞれにソート済みのn個の実数が入っているとき、これら2n個の実数の
中央値を求める、オーダーがlognのアルゴリズムを探しているんですが、
何か良いアルゴリズムはありますでしょうか？

>>228
２分探索木じゃダメなの？

>>228
抽象的な割には、やけに汎用性の乏しい問題だな。。。
これが宿題でなく、実際に問題になっているのなら
まず先にデータ構造の方を考え直せ。

スミマセン。宿題です…。
二分探索木をどのように使えばいいんでしょうか？
空の二分探索木に2n個の数を入れると根の数が中央値になる…なんて性質
ありましたっけ？この操作ならO(logn)で出来ますが…。

>>229
木にする必要ないと思うんだが。

えーと、どういう風にすればいいんでしょうか…？

よくわからないんだよね〜僕には中央値が。
二つの配列の値を比較しながら、近づくように走査していくのかな？
このとき、それぞれの総和を求めて行った方が良いのか？とか
二つの配列のそれぞれ両端から色々比較したりするのであれば、
４つ場所を保持しておかなければいけないと思うのだけれど、
その辺もわからない。わからないだらけの第３者です。

うーん、とりあえず条件は計算量がO(logn)であることと、2n個の数の
中央値を求めるってだけなんで…。
宿題なので実行効率とかそういうのは考えなくていいと思います。
変数や配列などの記憶場所も好きに使って良いと思います。
わざわざ配列が二つあるってことはマージを利用するのかなーとか
いろいろ考えては見てるんですけど…。

宿題スレへ逝け

おまいらしっかりしてください。
値を2個ずつとってきて、
「現在の中央値」「新しい値（１）」「新しい値（２）」
の＜3つの中の中央値＞をとれば、
それが新しい中央値になるじゃないの。

まてよそれだと O(n) か？

問題(>>228)読んでなかった。。
思いっきりバイナリサーチ(二分探索)じゃねーかYO!!
初歩だ初歩。あと二分探索木とか逝ったやつ反省しる

>>237
おまえしっかりしてください。

low1 = low2 = 0;
high1 = high2 = n - 1;
do {
mid1 = mid2 = (low1 + high1) / 2;
median = x[mid1];
if (x[mid1] < y[mid2]) {
low1 = mid1;
high2 = mid2;
}
else if (x[mid1] > y[mid2]) {
high1 = mid1;
low2 = mid2;
}
else
break;
} while (low1 < high1 || low2 < high2);
ここに直書き。あってるかどうかまったくわからない。

>>228
（ちょっと怪しいけど）こんな感じでは？

double f(double x[],double y[],int l)
{
    double xp,yp,z;
    do {
        l>>=1;
        if((xp=x[l])==(yp=y[l]))
            return xp;
        z=(xp<yp)?(x+=l,yp):(y+=l,xp);
    } while(l);
    return z;
}
double xx[]={1,2,3,10,11,12,};
double yy[]={4,5,6,7,8,9,};
int main(void){f(xx,yy,6);return 0;}

答え合わせは？

中央値は、x[],y[]のそれぞれ両端から比較していかないと取れないって・・・

中央値。とりあえず文章で説明してみる。実装は自分でやってくれ。
中央値を求めるのではなく、集合を大きい方と小さいほうに二等分する問題と
考えてみる。たとえば
集合Ｘ｛1, 3, 6, 7, 10}
集合Ｙ {2, 4, 5, 8, 9}
としてみる。
まず、集合Ｘを二つに分けると、ある敷居を境に大きいグループと小さい
グループにわかれる。この敷居を動かしていくと考える。まずは真中近辺
からスタート。６と７の間に敷居があるとしよう。
Ｘ｛1, 3, 6 || 7, 10}
Ｘが小さい方に３つ、大きい方に２つに分けたのだから、
Ｙは小さい方に２つ、大きいほうに３つに分けることになる。だから
Ｙ {2, 4 || 5, 8, 9}
となる。このとき、６＞５だから、この分け方は正しくないことがわかる。
＃分け方が正しいか正しくないかを見分けるには、例の場合４＞７、６＜５
＃を確認すればいいので、o(1)で調べられる。
では、この敷居の位置が悪かったことがわかる・・・、あとはバイナリサーチ
よろしく敷居の位置を変えればいい。o(logn)回敷居の位置を変えれば、正しい
分け方が発見できる。そうすれば中央値も求まる。

#include <stdio.h>
#define N 5

void f(double x[], double y[]) {
  int l = 0, r = N-1;
  do {
    int m = (l+r)/2;
    (x[m+1] < y[N-(m+1)])? (l = m+1): (r = m);
  } while (l < r);
  ((x[l+1] == y[l]) || (x[l+1]-y[l] <= y[l+1]-x[l]))?
    printf("%f,%f\n",y[l],x[l+1]): printf("%f,%f\n",x[l],y[l+1]);
}

main() {
  double x[N]={2,3,3,7,9};
  double y[N]={1,6,6,7,11};/*1,2,3,3,6,6,7,7,9,11*/
  f(x,y);
}

失敗

平面グラフの頂点を，隣接する頂点を異なる色で塗るとき，
４色あれば十分なことが証明されてますが（いわゆる４色定理），
その塗り方を求めるアルゴリズムを教えて下さい．

>>248
Brute Force

でかい本屋いって探せよ〜〜といいたくなるようなものなのですが。>>248

>>248
>平面グラフの頂点を，隣接する頂点を異なる色で塗るとき，
>４色あれば十分なことが証明されてますが

一点から辺が５本以上出ている "頂点" は
４色では塗れませんが、何か？

>>251

真ん中を青で塗って、周りの五つを赤、緑、赤、緑、白とすればよい。

>>251
日本語をもっとしっかり読め。
>>248
mod4で２足したりとか順にしていけばけっこうできるんじゃ無いの？

>>248
つーか、今はどんな手法使っているのよ？
始めは>>249のように力任せでもいいと思うけどな。
頂点数が1000くらいまでなら、最近のコンピュータなら十分速い。

えっと，4色塗りのアルゴリズムそのものが欲しいんではなくて，
そのアルゴリズムを使って別のことをしようとしています．
（具体的に何をしようとしているかはかなりややこしいので書きません）
考えて頂いておいて申し訳ないのですが，時間がかかるかもしれないけど
解けるというような方法は，私の目的には使えそうにりません．
真面目に文献調査をすることにします．

>>254
再帰探索じゃダメ？

http://caramel.2ch.net/test/read.cgi/owarai/1034442703/l50

>>255
N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas, ``Efficiently
four-coloring planar graphs'', In Proc. 28th ACM Symp. Theory of
Computing, pp 571-575, 1996.

フィボナッチ探索ってどういうのか分かります？

>>255
一松信先生の「正多面体を解く」とか読むと良いかも。
三十ﾍﾟｰｼﾞ辺りだけでも。

情報ありがとうございます．
>>258
ご指摘の STOC の論文を入手し読みました．まだ理解できておりませんが，
４色問題の証明に基づくアルゴリズムということで，非常に面倒そうだという
ことだけ分かりました．逆に言うと，単純なアルゴリズムがあれば，４色問題の
単純な証明になる！ということですね．．．
>>260
調べてみます．

四色問題（ブルーバックス）

>>259
わかりません。

Perl は屑!

ハノイの塔おもしれーーーーー（゜∀゜）ーーーー！

番号の低い順にならべてください(１が一番上)。
番号の高い物は上に重ねられません。

１
３　　１
２３　２
────

３２
１３３
１２２１　
─────

迷路を解くプログラムを作って欲しい

ハノイの塔の板の枚数がnのときの移動回数をnの関数として求める
というのはアルゴリズム論のよくある試験問題かも

>>268
右手法

>>269
n^2-1
光速で導きだせましたが何か？

>>270
立体迷路で通用しません。

枝刈り法

>>272
平面でも壁の連結成分が2個以上になった時点でｱｳﾄ

>>268
交差点で進んだ方向を記録しる。
平面なら最高３回、立体なら最高５回（つーか、分岐数−１回）

>>268　入口から水を注入して、最後まで水流のあるルートが解です

矩形内に円を描画するアルゴリズムを教えて!

>>268
袋小路を見つけて、道を埋めていけ。

baranced kd-tree の日本語解説があるページ or 本ってありますか？

３次元のダンスが見られる韓国製のフリーソフトで「D-Player」ってのが
あるんだけど、すごくリアルなモーションのくせにモーションデータが
小さすぎ。２、３分のデータでなぜか数百バイトとかなんだけど……。
どういうアルゴリズムか少しでも知ってる人いませんか？

グレッグ・ブライトの迷路は、行き止まりがありません。

>>281
一度通った道を壁と考えるのだ。

Objective-C !!

>>282
ゴールへの道が塞がっちゃった

迷路
ttp://cathand.org/etc/patramaze.jpg
http://cathand.org/etc/toromaze.jpg

ゴールはゴールでフラグでも立てとけよ

美佳ﾀﾝﾊｧﾊｧ
ttp://www.e.yamagata-u.ac.jp/~sakai/HOME_PAGE/H9/Mika/index.html

↑
DQN大学っぽい卒論だと思ったらやはり山形かよ

>>285とてもすばらしいです

>>287
これ、卒論なんですか？

>>290
ドクター請求論文でつ。

age

>>287
おれはこの子の論文どうこうに興味はないが、この子がついている教授がどの程度のもんなのか
見てみたい。

>>293
http://www.e.yamagata-u.ac.jp/~sakai/HOME_PAGE/Sakai/sakai.html

>>294
学外活動
看護管理者（ファーストレベル）研修会

ナースいっぱい・・・ﾊｧﾊｧ

浮動小数をサポートしてない機種で、浮動小数を実装したいと思っています
数値を浮動小数化するのは難しくないのですが、
浮動小数同士の足し算掛け算などで詰まってしまいました。

計算方法を解説してるHPなどありませんでしょうか

>>296
足し算掛け算に詰まるのに、浮動少数化するのが難しくないとはどういうわけですか?
漏れには信じられん。

浮動小数の仕組みはあっちこっちにあるので、変換はうまくいきました。
ただ掛け算はともかくとして、
足し算引き算は指数の離れている同士だとどうしましょうといった感じです

> 足し算引き算は指数の離れている同士だとどうしましょうといった感じです
有効数字が被らなければ無視すれば？

足し算引き算は、指数の大きいほうに揃えるしかないだろう。
それで失われる情報が「桁落ち」というやつだよ。

しかし、掛け算も結構面倒なはずだがなー
たとえば、仮数どうしをかけた後で、もう一度正規化する必要があるとか…
(1/2*1/2は1/4になっちゃうから。)

もしや掛け算この方法間違ってるのかな…
色々情報ありがたいことです。さらに調べてみます

>>301
そういうときこそ Knuth の本を読むのがよいと思われ

固定小数点に関するお勧めのサイトありませんか？

多角形と線分の交差判定って
凸型の多角形を前提にしてるものばっかりに思えるんだけど
凹型でも問題なくて、プログラムしやすそうなアルゴリズムって
どんなのがありますか？

あとこの辺りの計算幾何学のオススメの本とかあったら知りたいですけど
こういう本ってやっぱ高いのはしょうがないんですかね？
ちょっと安めでいい本があったら知りたいです。

交差判定って　普通、線分同士でしょ？

>>304
とりあえずこれは買っとけ。
コンピュータ・ジオメトリ−−計算幾何学：アルゴリズムと応用−−
http://www.kindaikagaku.co.jp/bookdata/ISBN4-7649-0277-X.htm

or and xor notだけで足し算ルーチンは作れないものでしょうか

CPU内部ではそうやってるよ

なるほど。
WinAPIに、BitBltという画像転送があるのですが
主にそのままコピー、or合成, and合成, xor notができます

それらを組み合わせて上手く加算合成とかをつくれないかなと

>>307
シフトが無いと　配列として処理するしかないけど
1ビットのレジスタ A,B とキャリの演算
A+B+Cy -> Cy+X
0+0+0 -> 0 cy0
0+1+0 -> 1 cy0
0+0+1 -> 1 cy0
0+1+1 -> 0 cy1
1+0+0 -> 1 cy0
1+1+0 -> 0 cy1
1+0+1 -> 0 cy1
1+1+1 -> 1 cy1

この表から論理演算を作ればいい

>>301
http://www.aya.or.jp/%7Esanami/peace/memorial/code21-30.html

>>309
> WinAPIに、BitBltという画像転送があるのですが
下位からの繰り上げの処理が実装しにくいと思うので、Bit数に応じて同等数
以上のBitBltが必要になると思うんだけど、、、
間違っているかもしれないので、突っ込みよろしく。

素直に「リプルキャリー｣で1ビットハーフアダー(1ビット入力＊２、
1ビット出力＊１とキャリー出力）を作ると、
A+B=A or B, Cy=A and B
１ビットフルアダｰは（1ビット入力＊２、キャリー入力＊１、
1ビット出力＊１、キャリー出力）は、
A+B+Cy=A xor B xor Cy
Cy=(A and B) or (B and Cy) or (Cy and A)
=(A and (B or Cy)) or (B and Cy)
これをビット数だけ繰り返せばよいわけだが。

そうなんですよね。「２倍にして合成」とかあるかと思ったんですが、ありませんでした
ピクセルごとに処理する方法は別に簡単なのですが、BitBltはハードウェアサポートのおかげで
超高速です。
それこそ100回や200回描画したところでびくともしません

シフトがないので桁あがりが無理そうですね…

うわ、見事に同時書き込み。
じっくり読んで理解するよう勤めます

>>313
なるほど、

まず合成する画像の特定bit部分だけとりだすのは、andを使えば簡単ですね。
特定の色で塗りつぶした画像を作り、それとand合成すれば良いわけですから。

加算器の構造に関してもHPと併用して理解できました。

しかしやはり繰り上がりができませんね。
シフトができない以上ここで手詰まりでしょうか。

>>304
線分の始終点のどちらかあるいは両方が多角
形内部の場合は交差。

多角形が反時計周りか時計周りか調べておく。

後は、線分と多角形の辺との交差関係を順次
調べて、交点での外積値の比較によって線分
が多角形の内部に入り込んでいるかをチェッ
ク（反時計周りか時計周りかの情報も利用）。

てのはどうでしょう。

>>316
> シフトができない以上ここで手詰まりでしょうか。
Bitmapを一次元にするとxを1ビットずらしてクリッピングでOKでは？グラフィッ
クカードに演算させるもは面白そうなので頑張ってね。

選択ソートと、バブルソートって比較回数はバブルの方が少ないですか？
でも実際交換回数は、バブルの方がぜんぜん多いんですけど。

>>318
RGBデータ部を１バイトずつ読み、シフトして返すのは可能ですが今回の目的にはそぐわないです
RGBデータ部全体を1bitシフトするのは流石に無理な気がします

何故シフト演算合成つくらなかったんだﾏｲｸﾛｿﾌﾄ!!

>>319
なんで?
単純なインプリメントだと
選択ソートは(n-1)(n-2)/2回
バブルの場合は(n-1)^2回
だと思う。
バブルソートでも最後に交換のあった位置を覚えておけば減るけどな。

>>320
> RGBデータ部を１バイトずつ読み、
2値のBitmapじゃないんだ。じゃ大変そうですな。

ヒープソートがわからない・・・。

ヒープソートを、図を書かずに分かりやすく説明する自信がない。

ダウンヒープってさ、根に向かって値があがっていく感じなの？
みためは上に向かってるけど、木として考えたら根に向かってるから
ダウンだけど。

おめぇら何歳？
我17だ。
そこまで知識を得るのに何歳から勉強してんだ？
たのむおしえて

ﾏｼﾞﾚｽだけど幼稚園で競馬プログラムをﾊｯｷﾝﾊｯｷﾝしてますた
と言っても本当に簡単なものだけどね
1から作りはじめたのは小学校後半
0から作るようになったのは高校ぐらいだ
17だったら丁度2種とって喜んでた頃だな

１０年も前の話だけど取引先の総務部長が、
韓国人の総会屋に一歩も引かなかったんだけど、
高校生の娘がレイプされて陥落。
ピストルをあそこに突っ込んだ写真を送ってきたらしい。
ネガは返してもらったらしいが親にしたらたまったもんじゃないだろう。
,
帰ってきただけまだましかも・・・・・・。
同じような目にあって、薬漬けにしてパチンコ屋の店長に
ペットとして払い下げられた中学生を知ってます・・・・・・。


http://ex.2ch.net/test/read.cgi/korea/1035676130/
↑ レイプ、拉致、人身売買、バラバラ殺人、カルト、毒殺、暴力など

>>328
http://bbs3.sekkaku.net/bbs/poohpooh.html
韓国人が集まりそうな掲示板
ここにいって書いて来い

>>323>>324
樹構造に、重りをぶら下げて行くと、上の部分は総和になり重くなっていく。
そのような、順番に大小のある値が入っている。

>>330
別に総和じゃないけど...

>>325
ふつう根を上に書けば「ダウン」は下へ行くだろ。
まあ、本によって説明の仕方は違うかも知れんが。

根が最小値のとき、ヒープ(priority queueともpartially-ordered tree
とも言う)へ値を挿入するには、葉から根へ向かって適当な場所まで
シフトして行く。最小値を削除するときは、空いた根の位置に、
いちばん端の葉の値をまず入れ、葉に向かってシフトして行く。

>>326
適当なアルゴリズムの参考書を購入しる。
最初は分からなくてもいいから、同じものを全部を通して最低１０回は読む。
あら不思議、５回目くらいから書いてあることが頭にどんどん入ってくるYo!


...これ、ちゃんとした学習法でつよ？

>>331
> 根が最小値のとき、ヒープ(priority queueともpartially-ordered tree
> とも言う)へ値を挿入するには、葉から根へ向かって適当な場所まで
heapとpriority queueとは同じじゃないよ。priority queueを実装するのに
heapを使うことが良くあるだけ。つまりheapじゃなくてもpriority queueは実
装できる。partially-ordered treeってのはあまり(というかほとんど)耳にし
たことがない。

>>332
なんだかんだとそれが一番正しい勉強法だと思う。
私も同じ方法で勉強してましたｗ
どの分野にも言えるけどがむしゃらに手を出すよりは、
ひとつの本を何度も読んで理解した方が早いよね。
その上で、内容がものたりなかったり、どうしてもわかりにくいところがあれば、
別の本に手を出して、また読み返していれば良し。
ちゃんと理解もしていないのにどんどん本を変えると、
かえってわかりにくくなるときもあるよ。
書く人によっては言葉の定義が違ってたり、くせもあるから。

後は、やはり実践かな。

>>333
まあそうね。priority queueを実装するのには単にbinary partially-ordered
treeが標準的な手法というだけで、イコールではないね。

partially-ordered treeを聞いたことがないってのは…（笑
「ヒープ｣なんて呼ぶのはヒープソートの時だけだよ。ふつーの
文脈でヒープといったら別の意味だから。

http://www.cs.ucsb.edu/~cs20/yfwang/notes/heap.pdf

>>JPS
ねぇ、マージソートはできたの？

>>335
ヒープってデータ構造のことだろ。Cormen,Leiserson&Rivestでも読め。

>>338
ほかのヒープもあるからややこしいの。
ややこしく無いようにpotと呼んどけ。

posetは使われるけど，potってのはなぁ…

>>340
そりゃまたぜんぜん違う意味っス。
これだから知ったかは…（ｗ

hurry porter!
いよいよっすね！

>>342
ほんとのスペルミスかどうかわかりにくいボケはやめて…

posetとpotが同じ意味だなんてどこにも書いてないと思うけど…

ネタはもういいよ…

>>344
はいはい。わかったわかった。
ageずにおれないほど悔しかったのね、ボクチャン？

どうしてもpotがよく使われているということにしたいんでしょう。CLR程度さ
えまともに勉強してないのがバレバレなのに。

>>347
はいはい。ゼミで読んでうれしかったのね。
じゃ、君はPOTの替わりにずっとヒープと言ってなさい。
ちなみに俺のゼミではAho, Hopcroft, Ullmanだったよ。

RivestとAhoとHopcroftとUllmanは知ってるけど、あとの2人は何した人？

>>348
> ちなみに俺のゼミではAho, Hopcroft, Ullmanだったよ。
まだそんなひどいの使ってるのか…だいたいゼミってなんだよ。学部2年で終
わらせとくもんだろう、アルゴリズムの単位なんて…日本の大学ってやっぱレ
ベル低いな。

>>350
いや、18年前の話なんだが…
ま、いずれにせよ「ヒープ」といったらデータ構造のほかに
動的メモリ割り当てのための領域のことを指すことも多いから、
よりspecificにpartially-ordered-treeと言った方が安全。

Cormenはダートマス大、LeisersonはMITの先生。

>>352
フーン…
別にたいした人じゃないのね。

>>351
> >>350
> いや、18年前の話なんだが…
で、それっきり研究の進展を勉強してない、と。ひとりで通用しない
partially-ordered-treeって言い続けてろや。

>>353
> 別にたいした人じゃないのね。
そのとおり。こんな時にこんなところで書きこんでるあなたさまと比べたら。

>>351
たしかにそっちのheapの方がよく使うよね。

>>354
（フﾟ
partially-ordered-treeと言われると理解できないらしい。

>>354
まあ、あんたは「メモリ領域じゃないほうのヒープ」と言いつづけてろや（ｗ

CLR程度の初級教科書を読んで「研究」（禿藁

Wirthの「プラスイコール」ですが何か？

どうでもいいけどお前ら必死すぎ

>361
禿同

なにをこんな朝早くから議論してるかと思えば、アルゴリズムじゃなくて名前に
ついてかい…

>>359
> CLR程度の初級教科書を読んで「研究」（禿藁
CLRさえ読んでないのか。タイトルだけで入門書だと思ってる。

>>363
なにやら知らんが必死だな（藁

漏れはCormen, Leiserson, Rivest and Steinなら読んだが、
あれを読むと何か研究したことになるんか？

マタ〜リマタ〜リ

遺伝的アルゴリズムの入門者用の良いサイトあったら教えて下さい

>366
入門でいいならここでいいと思う。
ttp://kyu.pobox.ne.jp/softcomputing/ga/

>>367
サンクス
でも何か具体例がないから難しいですね

>367
具体例は分かりづらいかと思われるが>287にある。

>>287
考察、結論のない論文、初めて見た

・小さなファイル(500Byte程度)が6000個ある
・全てのファイル名はユニークで、一つのディレクトリ内に集めれている
・あるファイルと、中身の文字列が全く一緒であるファイルが最大20個程度
　ある可能性があります(内容ダブっているってこと。)

これらのファイルを、内容が重複するものを削除したいのです。
更に、A⊃B となるような(Aは、Bの内容になんらかの文字列を追加したもの)
ファイルもあるので、Bも無駄なので削除してしまいたいのです。

最速、いやせめて実用的な方法ってどうやればいいんでしょう。。

500Byteが6000個でしょ。全部メモリに入れちまえば。

>>371
これをDisAsm32に架ける
http://henachoko.homeip.net/uploader/updata/20021124044847.zip

ファイルの内容をキーにファイル名をソート。
比較時にA⊇Bであるようなペアを記憶しておく。

上の前提条件を改めれば劇的に速くなるだろうけど。
たとえばデータ構造やらファイルの命名規則やら
ファイル作成時にチェック入れるとか。

頭の悪い俺は、こんな風にやりました。perlで実装してます。

1)　ディレクトリのエントリからなるリストの上から順に
　　次のファイルとdiffで比較→同じなら削除
→違うなら更に次のファイルとdiff..(以下略

　　この馬鹿げた方法では、10時間経っても終わりませんでした(藁
　　少しは無い頭使ったところ、以下のようになりました。

2)　ディレクトリエントリのリストを使うのは一緒ですが、初めに
　　サイズ順にソートしておきました。ファイルサイズが一緒の
　　場合のみ、実際にdiffで比較。ファイルサイズが異なるファイル
　　に出会ったら、中身の文字列が完全に一致しないのは明らかなの
　　でスキップ。次以降のファイルも、サイズが違うのは明らかなの
　　で同様にスキップ。次のループへ...

　　これでやると、3分で終わりました。
　　しかし、A⊃Bの場合にBを削除する要求にはノータッチなのです。
　　なやんでるところ。

　　

>>371
>>373で終わったな。終了

>373は当然として俺まで無視かよ!!

ごめんちょ

皆さんありがとう
>>372
効率よい＆＆実装できそう な方法を使っても、それでも遅かったら
そうしてみようと思います。

>>373
早速、今日試してみます。出勤なので・・

>>374
その方法で検討中ｗちょっと楽しみ。
そもそもの背景が、3交代シフト勤務の現場で、勤務交代するときに
生成される引継ぎファイルの内容を全文検索可能にしようという企画です。
1件の引継ぎ項目ごとにファイルに分割し、それにユニークな名前を
つけて一箇所に集めているのです。

個々の引継ぎ事項ってのは全員に行き渡るまで消去されないので、
複数日の引継ぎファイルに残る　→　結果、重複する内容がある

データ構造かぁ。。問題ありあり、というかマークアップもなにも
ない、プレーンテキストだからなぁ。

>>373
しまつた！この仕組みは、Linuxで動いてます・・

500Byte6000個。

create table hikitugi (
hikitugi_cd char(10),
author_cd char(10),
naiyo varchar2(4000)
insert_date date,
);

SELECT * FROM HIKITUGI WHERE NAIYO LIKE '%もうね%'

112233334444555555556666をLz78符号化して
112020343440474059510510606136
という結果を得たとき、これを復号化する際
〜106
を10番目の語句＋6ではなく、1番目の語句＋0+6番目の語句＋…と解釈すると
1122333344445551203316612334となります。
辞書の番号が一桁なのか二桁なのかどう区別したらいいのでしょうか？

class Pair
　def initialize(name, contents)
　　@name = name
　　@contents = contents
　end
　def name
　　@name
　end
　def contents
　　@contents
　end
end
Dir.chdir(ARGV[0])
data = Dir.glob("[^.]*").collect { |file_name|
　f = File.open(file_name)
　begin
　 Pair.new(file_name, f.read)
　ensure
　 f.close
　end
}
data.sort{ |a, b| a.contents <=> b.contents }
i = 1;
while i < data.length do
　str = data[i - 1].contents
　if str == data[i].contents[0..(str.length - 1)] then
　　File.delete(data[i - 1].name)
　end
　i += 1
end

>>379
Rubyで書いてみた。
ruby ディレクトリ名
で実行せよ。ファイル名はピリオドで始まらないと仮定してる。

ruby スクリプト名 ディレクトリ名
のマチガイ。逝ってきます…

>>382
何故十進数で符号化するのか分からないんだけど・・・
固定長でも可変長でもいいから別の符号化法使うか、
そういうのがダメ（っていうのは無いと思うけど）ならセパレータを使ったら？

>>381,>>383
ありがとう！今日のオカズにします。

たびたびスマソ
sortじゃなくて
sort!ですた。

>370
論文ではなく、研究発表用の資料だろう。発表は短時間で概要を説明するのが
主眼だから、細かい証明や考察なんかはザックリ落とす。

フーリエ変換って周波数成分取り出してそれをどういった事に応用できるのでしょうか？

>>390
宿題？
　直接的にはシステムの応答特性を見たり
　畳み込みを高速に処理したり、
　それを応用して多倍長掛算を高速化したり

>>390
あと、lossyなデータ圧縮にも使う。

>>392
それはコサイン変換では？

>>393
DCTもFFTも似たようなもんでしょ。

まあでもそれを同じと言ってしまうと　フーリエ変換とラプラス変換も同じようなもんだって事に

FFTを使ったlossyなデータ変換は、実際にあるでしょ。

>>396
例えば？
DCTをFFTで実現するのは普通にあると思うけど

>>391
ふーん、よくわからんからやっぱいいです

>>397
Dragon Cuest Ten
Final Fantasy Ten
合併だってな・・・

Dragon Fantasy になるのかな？
それとも Final Quest になるのかな？

>>397
＞DCTをFFTで実現するのは普通にあると思うけど

そしたら、それは「FFTを使ったデータ圧縮」といって良いんとちゃうんかと…

DCTはFFTの変形版でつよん？
波形をコピーして、位相をずらしたFFTの特殊系をDCTと呼ぶのでつ。
その変形方法によってDCT I,II,III,IV の4種類がありまつ。
JPEGなどで使われているのはDCT-IIでつ。

FFT使ってもlossyとは限らないとは誰も突っ込まないのか?

>>403
まぁ普通のFFTが普通はlossyで、無歪みのFFTは特殊なFFTです。

2分木に関する質問です。
頂点数ｎの完全２分木の高さがlog nであることを証明しなければならないのですが、わかりません。
どうやって証明すればいいのですか？
教えてください。お願いします。

ファイナルファンタジータクティクス２がでるんだからいいかげん１に話はやめましょうよ。

高さがnのときちょう点数が2^nであることをいう．

>405
> 頂点数ｎの完全２分木の高さがlog n
高さ k の完全二分木に含まれる頂点数が 2^k - 1 ってのは証明できたか？
帰納法を使うなり何なりして導け。

あとは n = 2^k - 1 とおいて k について解けば良い。

>407
高さがnのときって頂点数は2^k-1って証明できたんですが、2^kでいいんですか？

>408
2^k - 1 ってのは証明できました。
でも、n = 2^k - 1 じゃなくてlog n は、n = 2^k じゃないとでないんですが。

釣りか

>409
> でも、n = 2^k - 1 じゃなくてlog n は、n = 2^k じゃないとでないんですが。
O(log n) だろ？　定数項は捨てられるやん

VB厨です。レベルの高い人にはついていけない人です。まぁガンガリますが。

質問
　統計です。データがN個あり、データの値で累積度数分布を作ります。
一応は正規分布するもの（分布のイメージね）、とでも思って下さい。
このときのX％値を素早く求めるアルゴリズムを教えて下さい。

　今は、単にソートして、例えば100個（ほんとは101個）あるとすると、
5％なら5個目を選んでます。

>411
あがとうございます。分かりました。
まだ勉強が始まったばかりなんで、また来るかもしれませんがそのときはお願いします。

>>412
その5%を密度関数に代入して出てくる値をインデックスにすればいいのでは？

ガンダムseedで使われているOSについて教えてくさい。

>>412
それでいいんじゃないの？
「ソートして、順位がx%になるデータの値を求める。」でOKだろ。
累積度数分布表ができれば、ソートはおわったも同然
（累積度数分布表は「値nから順位への表」とみなせるので）
だから。

>>414
実際のデータから密度関数をどうやって求める？
また、そこから求めた百分位点が、実際の標本の百分位とあってる
確率は低いと思うが。

>412
平均と標準偏差だけ求めて，後は標準正規分布表見てやるのかなあ．Nが大きくなきゃ別にそれでもいいと思うけど．

>>417
標準偏差ってなんですか？

>>417
なんで>>416じゃだめなのさ？

度数ソートならO(N)時間で（つまり平均や標準偏差の計算と同じオーダーで）
できるんだよ？

>>416
う〜ん、それしかありませんか、やっぱし。

今作っているのが、実は一組当たり3万〜4万個のデータがあって、
その一組ごとに％値を求め、それをいっぺんに数百回やらないと
いけないんです。これが結構時間がかかるので・・・

注）416さんの仰るとおり、％値は標本値と一致しないといけません。

>>420
だあか〜ら〜。
どうせ累積度数分布表つくってるんなら、それでソートが終わったも同然でしょ
ってば。つまり、それ以上は速くなりようがないんでしょ？

まさかqsortとか使ってるんじゃないでしょうね。

>>421
なんか誤解されてしまったようですね。わかりにくい質問ですみません。
質問の意図は「X％値を求めること」であって、累積度数分布は実際に
は作ってません。「累積度数分布のX％値を求める」です。

ん？度数分布表作った方が速いの？

>>422
それなら完全ソートしなくてもよいので、
よほど変なことをしない限りO(n)で求まると思います。

>>422
まずソートについて。

累積度数分布表が作れるようなデータ（つまり、０〜１００とかみたいに、
値の範囲が限られた整数になるデータ）では、累積度数分布表を作ってソート
するのがもっとも高速です。O(N)時間でソートできます。「度数ソート」
「分布数えソート」等で検索してください。

x%点について。累積度数がx%を超えるまで累積度数を計算し、その順位にある
データを見つければよいわけですが、
・度数分布…N回ループ
・累積度数…(xN/100)回ループ
・その順位のデータを見つける…(N/2)回ループ
で、まあ、何割か早くなるでしょうが、「度数ソートしてX番目」と
オーダーとしてはおんなじです。

>>424
分布数えソートがあるというのは知りませんでしたが、
昔考えたことはありました。値の範囲を決めないといけないので
汎用ルーチン化は難しいと思って、放棄。

うーむ、頭が固いのはだめですねぇ。クイックソートが一番速い
と思いこんでましたから。

結果、めちゃくちゃ速くなりました。ありがとうございました。

僕も分布ソート知りませんでした。
ひとつ賢くなれたよありがとう！

分布ソートってなんですか？

>>427
ごめん 分布数えソート のタイプミスです。

vectorとlistを比べたときシーケンシャルアクセスもランダムアクセスもvectorの方が早いですよね?
ただ挿入とか削除が遅いと。でもプログラム中ってアクセスのほうが多いから
時々挿入とか削除が起こるくらいならvectorの方がいいのでしょうか?

そうだね。

>>429
ベンチマークを取ってみたら？

>429
> でもプログラム中ってアクセスのほうが多いから
プログラムによる。

あと list は node 単位でメモリを確保・解放するのに対して、vector は
一括してメモリを処理するから、iterator を長時間に渡って保持してお
きたい場合には list の方が良い。

|　　２のべき乗じゃないんですけどフーリエ変換できますか？
　＼＿＿＿＿　 ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／
　　　　　／||ミ Ｖ　
　　＿／ ::::||＿＿＿＿_
　[ ／ . :::::::||＿＿＿＿　]
　　|:::::::::::::::||　 　 　 　 ||
　　|:::::::::::::::||│　／ 　 ||
　　|:::::::::::::::||￣＼　　 ｶﾞﾁｬｯ
　　|:::::::::::::::||ﾟ ∀ﾟ）─　||
　　|:::::::::::::::||＿／　 　 ||
　　|:::::::::::::::||│　＼ 　 ||
　　|::::::: C=||∧ ∧∩　||
　　|:::::::::::::::|| ﾟ∀ﾟ）/.　 ||
　　|:::::::::::::::||∧ ∧∩　||
　　|:::::::::::::::||　ﾟ∀ﾟ）/.� ||
　　|:::::::::::::::||　　　 〈. � ||
　　|:::::::::::::::||,,／＼」. � ||　　　
　 [＼ . :::::::||￣￣￣￣　 ]　　　　
　　￣＼ ::::||￣￣￣￣￣　　　　
　　　　　＼||　　　　　　　　

>>433
FFTなら、2のべき乗になるようにダミーのデータを足せ。

2のベキ乗じゃないDFTの高速化は
ttp://momonga.t.u-tokyo.ac.jp/~ooura/fftman/ftmn1_3.html

これで判らないなら
http://www.google.co.jp/search?q=Winograd+FFT

学習アルゴリズムって何ですか？

等高線図（平面）を書くアルゴリズムを教えて下さい。

座標はｘ、ｙを任意に与えられるものとします。格子状とは限りません。
（格子状ですらわからないｱﾌｫですので、格子状でもいいですが）

>>437
x, yが任意に与えられるだけだったら等高線なんか描けないが。
それともその等高線は同一高度に限られてて画面に一本だけか?

>>438
失礼。測点のｘ、ｙ座標というべきでしたかね。当然、その位置の
高度（ｚ座標）は与えられます。

>>434
ダミーのデータを足すってことは、ある画像に対して例えば200＊200Pixelならば
縦横56ずつ、何かの画像をプラスして256*256にするって事ですか？
そのとき足すデータはどういうものが良いのですか？

>>437
手順１、 与えられた座標点間を補間した関数 F(x,y) を求める
　　　補間は色々。フーリエ変換とかスプラインとか

手順２、F(x,y)-C=0 を解く
　　　数式上解けないならニュートン法を使う

>>441
あかん、素人にはようわからん。それなりに難しいのかなぁ、やぱし。
（フーリエ変換とかスプラインとか、知ってはおるが結びつかん）

本とかURLとか紹介して下さる人いないですか？

できれば、その逆に等高線図から（スキャンして）任意のX,Y点の高度とかも
求められたらなぁ、などとｱﾌｫが壮大な夢を見ているのだが。

等高線。
まずグリッド生成。これは三角格子が楽だと思う。
なるべく正三角形に近い三角形になるように、点を結んでいく。

次に、等高線をどの高度についてどれくらいの間隔で引くか決める。

すべての三角形の辺について、等高線が辺と交わる（辺の両端が、
片方は等高線より高く、他方は低い）なら、直線補間で交点を決める。

等高線は、
・三角形の１つの頂点だけを通る。
・三角形の１辺から入り、別の辺から出る。
・三角形の頂点から入り、対辺から出る。
のいずれか。

こうしてできた等高線の点の連なりを結んでいく。
その時にスプライン補間などを使ってなめらかな曲線にする。

仕事なら、
等高線書いてくれるソフト使った方が早いと思うなー
Mathematicaとか、gnuplotとか。

>>443
サンクス。
で、グリッドに測点を持ってこいってことですか？
・・・・とまれ、なんか分かりそうでわからんような、難しそうですな、なかなか。

>>444
てか、ああいうのがどうやっているのかを知りたいんでね。多くのソフトが
コンター図作れているわけで、何かセオリーみたいなのがあるのかなぁ、
と思った次第。ナントカ法によるコンター図とか。

>>440
200点なら まず素因数分解してみろ
200 = 2^3*5^2

な？　FFTが使えるだろ？

>>445
443さんの案を元にして、グリッド生成の代わりにドロネー図を使うってのも
良さそうな気がします。
http://www.sra.co.jp/people/aoki/Voronoi2dDiagram/

>>442
幾何的に等高線を生成するのはかなり面倒くさい。

任意展の高度を求めるのは近傍の測点から補完して高度を求めればよい。ので簡単だ。

等高線図にしても描くだけなら画面上の点すべてについて高度を求めて等高線の高度なら点を打てばよい。

>>447
( ﾟдﾟ)ﾎﾟｶｰﾝってな感じでした。ｱﾌｫですのですみません。せっかくご紹介
いただいたのでそのアドレスはお気に入りに入れときます。

>>448

>等高線図にしても描くだけなら画面上の点すべてについて高度を求めて等高線の高度なら点を打てばよい。

無茶いわないで下さい。実は測点の高度というのは、実際には「高度」ではなく
計算値（これが結構時間がかかるのです）なのです。従って、それではほぼ永遠
に終わりません。手で書いた方が速い（ｗ

> >等高線図にしても描くだけなら画面上の点すべてについて高度を求めて等高線の高度なら点を打てばよい。
>
> 無茶いわないで下さい。実は測点の高度というのは、実際には「高度」ではなく
> 計算値（これが結構時間がかかるのです）なのです。従って、それではほぼ永遠
> に終わりません。手で書いた方が速い（ｗ

等高線ってもしかして地形じゃなくてシミュレーションかなんかの可視化なのか?
そんな前提はしとらん。
本当の高度を求めるのは適当に決めた測点だけにして、その他の点は測点の値から補完すれ。

>>443 さんがマジレスしてるので

正方格子　つまり等間隔なら簡単

a--b 　今　高さ h の 等高線を描きたいとしたら
|　　|　
c--d　
　１、a〜b a〜c b〜d c〜d間に h　が入るかどうか
　２、入るなら a=10 b=30 h=20 としたら a〜b間の(20-10)/(30-10)の比率の位置に点を打つ
　３、同じように a〜c b〜d c〜d間 でも行う　時計回りに見る事にするといい
　４、この点を結ぶ線を登録（始点終点）　最大２本の線が引ける
　５、登録した線を結ぶ　（前にやった時はB木に登録し検索して繋ぎながら処理した）


まあでも、今のCPUパワーなら まともに>>441をやった方が簡単かもね

等高線は三角形で平面を埋め尽くせれば後は簡単なのだと思う。
問題はどの点同士をつないで三角形を作るか、なんだろうな。

手順はボロノイ図（2番目の例で蜂の巣になってる方）を作って『ボロノイ点』を求め、
その後、ドロネー三角形を作ってるのか。
２ステップ踏まなきゃ三角形で埋め尽くした図は作れないんだな。


ボロノイ図（蜂の巣の方）の作り方はこんな感じかな。

１）点Aのまわりの蜂の巣を作るには

for i=1 to n-1
　for j=i+1 to n
　　点Aと点iとで作る垂直二等分線と、
　　点Aと点jとで作る垂直二等分線の交点をもとめる。
　　これがボロノイ点の候補になる。
　　これがボロノイ点かどうかをチェックする−−−
　　　　すべての点と点Aとで作った垂直二等分線よりも外側にあったらアウツ！
　　　　このチェックにパスしたらこの点をボロノイ点として登録する。
　　　　登録する際にはどの3つの点で作ったかを記録しておく。
　　　　（この場合はA, i, j。）
　　−−−
　next
next

これで点Aのまわりのボロノイ点は求まる。

２）
この要領で総ての点に対してボロノイ点を求めていくが、どの3つの点で作ったか（A, i, jとか）の情報をもとに
重複を避けながら登録していく。

>>447のページを見ると、ボロノイ点のまわりの母点（測定点）を結べば
ドロネー三角形の図になるそうだが、
幸い、上のルーチン中では使用した3つの点の情報を既に記録してある。
だから三角形を作るには、この3点を使えば良いわけだ。

等高線は各ボロノイ点ごとに（それの作る三角形ごとに）処理していけばよさそうだね。

> 等高線は三角形で平面を埋め尽くせれば後は簡単なのだと思う。
> 問題はどの点同士をつないで三角形を作るか、なんだろうな。

それをメッシュ生成と呼ぶ。
なかなか難しい問題で、まだいろいろと研究されている。

最終的には3重ループになって重複チェックはいらなくなるね。
三角形を作る段で3点の情報（A, i, jとか）は必要になるんだが。


別な話だが、中学生の頃、気象図（等圧線）を作る宿題が全然できなかった。
（手順なんかは一切教わらず地図と各点での気圧のデータを渡されただけ）

出来た人（他のクラス）のを見た時は「なんだ、こんなの簡単じゃん」とか思ったんだが
実際やり始めたらどこから手をつけていいかさっぱり分からず
何本か線が引けただけで、どーにもならなかったな。

地球儀のような球面状だともう訳ワカメ

|　　今からここでFFTしたいんですけどいいですか？
　＼＿＿＿＿　 ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／
　　　　　／||ミ Ｖ　
　　＿／ ::::||＿＿＿＿_
　[ ／ . :::::::||＿＿＿＿　]
　　|:::::::::::::::||　 　 　 　 ||
　　|:::::::::::::::||│　／ 　 ||
　　|:::::::::::::::||￣＼　　 ｶﾞﾁｬｯ
　　|:::::::::::::::||ﾟ ∀ﾟ）─　||
　　|:::::::::::::::||＿／　 　 ||
　　|:::::::::::::::||│　＼ 　 ||
　　|::::::: C=||∧ ∧∩　||　　　
　　|:::::::::::::::|| ﾟ∀ﾟ）/.　 ||
　　|:::::::::::::::||∧ ∧∩　||
　　|:::::::::::::::||　ﾟ∀ﾟ）/.� ||
　　|:::::::::::::::||　　　 〈. � ||
　　|:::::::::::::::||,,／＼」. � ||　　　
　 [＼ . :::::::||￣￣￣￣　 ]　　　　
　　￣＼ ::::||￣￣￣￣￣　　　　
　　　　　＼||　　　　　　　　

>>453
> ２ステップ踏まなきゃ三角形で埋め尽くした図は作れないんだな。

そんなことないですよ。ボロノイ図を書かなくてもドロネー図を生成できます。

英語ですが、解説ページ見つけました。サンプルも色々そろってます。
http://astronomy.swin.edu.au/~pbourke/terrain/triangulate/

>>459
あ、なるほど、これが>>447のページで言われている
『母点を一つずつ付け加えていく逐次添加法(incremental insertion method)』
になるわけですか。
>>453のやり方だとnの4乗のオーダーの計算時間がかかりそうですから
こっちの方が全然速そうですね。

===　>>459のページの内容　===

アルゴリズムの概要は

既に存在する三角メッシュに点を1つずつ加えてメッシュを更新していく。
処理の最初には全ての点を内包する任意のスーパートライアングルを1つ作成する。
これに1点ずつ母点を加えていってメッシュを更新し、処理が終わったら
スーパートライアングル自身と、それと辺を共有する三角形を削除する。

点を付け加えていくプロセスは
Figure 2a.の様に、メッシュと新しい母点があった場合、
・新しい母点を内包する外接円を持つ三角形を全て選びだす。（Figure 2b.）
・それらの三角形をつなぎ合わせると母点を内包する多角形ができる。
・多角形内の三角形を削除し、多角形の辺と母点を結んで新しい三角形を作る。（Figure 2c.）

1bit/pixelのフォントイメージを、1byte/pixelのVRAMに
展開するのに速いアルゴリズムってあります？
今は
if (font & 0x80) *(vram + 0) = 色;
if (font & 0x40) *(vram + 1) = 色;
if (font & 0x20) *(vram + 2) = 色;
if (font & 0x10) *(vram + 3) = 色;
if (font & 0x08) *(vram + 4) = 色;
if (font & 0x04) *(vram + 5) = 色;
if (font & 0x02) *(vram + 6) = 色;
if (font & 0x01) *(vram + 7) = 色;
ってのをフォントの幅/8*高さ分やってるんだけど
べたすぎて、他にいい方法がないものかと

落下の計算式きぼん

vy += ay;
y += vy;

ay = m*g - y*u;
vy += ay;
y += vy;

F = ma

準ニュートン法を使いたくて、
http://save.k.u-tokyo.ac.jp/~mimura/ja/study/method/q_newton/node4.html
を見ました。
ここで、使われているx(k+1)は現在のxの値で
x(k)が一つ前のxの値ということでいいのでしょうか？

スレ違いだったら申し訳ありません。ここが一番近しいと思ったもので

RSA暗号をCで作りたいのですが、150桁くらの素数が必要になります
10,000,000くらいまでの素数表ならネットに転がっていたのですが、
到底安全と思える桁数ではありません。
何か大きめな素数を手に入れる方法はありませんでしょうか

STLのrotateを実現する最適アルゴリズムをお教えくださいm(ﾟ▽ﾟ)m

2chはバカだらけなので、その質問には答えられません

こいつら…知識なさ過ぎ！！（ププッ

「Aアルゴリズム or A*アルゴリズムを使って8クイーンを解け」
っていわれたのだけれど。そんなことできるの？

へぇ。やっぱりね。

>471
A* って基本的には「全探索」のアルゴリズムだから、できるんじゃない。

アルゴリズムの特許って、どうやって検証するの？
形式的な検証方法があるのかな？

フリーソフト／オープンソースでも、ネットワークでプログラムを
ばら撒いただけで特許権侵害になるんでしょ？

果てしない禅問答に巻き込まれる様な気がする…。

匿名で公開する。完璧。

>>474
特許権の及ばない国で公開する。
時間設定が間違っているサーバで公開する。

任意のサイズ、任意個数の長方形があって、この長方形の
すべてが収まるような長方形の最小サイズを求めたいのです。
調べてみたところこれはNP完全問題で、局所最適解を求める
しかないようなのですが、なにかいいアルゴリズムをご存じのかた
いらっしゃらないでしょうか？

プログラミングのレポートでアルゴリズムと考え方を書くのですがこの２つの違いが分かりません。
どうか教えて下さい。

>477
良いアルゴリズムといっても評価の基準は様々だけど、何を重視してるの？

>>477
もろにナップサック問題だね。厳密解を求める良いアルゴリズムは無い。
確率的アルゴリズムや、近似解を求める発見的手法ならあるかも。

>>479
計算論で「良いアルゴリズム」と言ったらクラスPに属するアルゴリズムを言う。

>479
ご回答ありがとうございます。
速度重視で探索したいと考えています。
それほど厳密な解は必要ないんです。

>480
ご回答ありがとうございます。
調査したんですが、どうも近似解を求める
方法はみつかりませんでした。
確率的アルゴリズムというのはGAとかの
ことでしょうか？

>480
> 計算論で「良いアルゴリズム」と言ったらクラスPに属するアルゴリズムを言う。
近似解を求めるアルゴリズムにしても基準が色々あるだろ、という話だと思うが。

最適解の定数倍オーダーの答えを出すが計算量 O(n^3) のアルゴリズムと、
最適解の二乗のオーダーの答えを出すが計算量 O(n^2) のアルゴリズムが
ある場合、どちらが良いかは用途による。

>>482
質問者は誤解して使っているのかも知れんが「良いアルゴリズム｣というのは
定義ずみの用語であり、その定義は「多項式オーダー｣ということ。

>>481
GAは確かに近似アルゴリズムとして動作するが、
うまく動くようにプログラムする技術が確立していない。
問題の種類によって異なるが、GAのほかに、
シミュレーティッドアニーリングとか、シミュレーティッドエボリューション、
などを検証するとよろし。

関数の極小探査をしたいのですが、
どんな物がありますか？
名前で検索しようと思ったのですが、
黄金分割法しか知らないのでできませんでした。
よかったら、極小探査アルゴリズムの名前を教えてください。

関数といっても１次元なのか多次元なのか知らないけど。
とりあえず「最小値問題」 でｸﾞｸﾞﾚば？

n個のブツをm(<n)個のグループにわける問題をGA(遺伝的アルゴリズム)で
解く時に、どう言った遺伝子にコーディングすればいいか悩んでます。
例えば話を簡単にするために、ABCDの４グループに分類する場合、n個の
配列を遺伝子として表現すると、同じグループ分けのことなる遺伝子表現
が出来てしまいます。これは、あまり収束が良くなさそうなのでアイディア
なんかないですか？
例）同じグループ分けなのに異なる遺伝子になってしまう例
AABBBADDCCABBC
BBCCCBAADDBCCD

最高のalgorithmを目指すと数学が必要になってきますか？

除算の基本アルゴリズムはどうなりますか？

>>487
こんな感じで遺伝子を変換してはどうでしょう。

'言語はVBです
'グループは1〜mの整数で表してます。
Dim g(1 To n) '遺伝子
Dim t(1 To m) '変換テーブル

j = 1
For i = 1 To n
If (t(g(i)) = 0) Then
t(g(i)) = j
j = j + 1
End If
g(i) = t(g(i))
Next

あんまりいい方法じゃないかも。
場合によっては、変換のコストが無視できないほど掛かりそうですし。

>>490
こんな事すると、よけい収束が遅くなりますね。
このレスは忘れてください。

今VBで画像処理プログラムを作ってるんですが処理速度がすごい遅いです
例を挙げると、たかだか512＊512pixelの画像の反転ですら3秒ほどかかります
Photoshopなら1秒もかからないのに、、
マシンは2ギガのペン４だからスペックが悪いわけじゃないし
アルゴリズムに問題があるのだと思います、でも
やってることは
x=読み込んだ画像の横サイズ
y=読み込んだ画像の縦サイズ

ループ0〜y
　ループ0〜x
　　一画素を取得するメソッドで得た値をにcolor代入
colorをシフトビットとAND演算でRed,Green,Blueの各値を得る
255-Red,255-Green,255-Blueで得た値をそれぞれ新しいRBG値とする
　　一画素を描画するメソッドで、新しいRGB値をセットする
　ループxの終わり
ループyの終わり

ってやってるんですけど
私のアルゴリズムが悪いのでしょうか？
それともVBだから遅いの？

>492
アルゴリズムというか、使ってる API が悪いんだと思うが。

VB は知らんが、Win32 API だとピクセル単位で画像データを処理するのは
SetPixel(), GetPixel() という API だが、これは GDI 汎用に作られてるために
ムチャクチャ遅い。

画像処理をやる場合には、ふつうは CreateDIBSection + BitBlt を使う。あと
画像反転程度なら、自前でコード組むまでもなく BitBlt の引数で指定できる
ぞ。

（続きは Win32 関係のスレに行った方が、詳しい人間が見つかると思われ）

>>493
ありがとう
やっぱアルゴリズムどうこうではないようですね
そっちのスレで聞いてみます

論理演算、ビットシフト等を使ったアルゴリズムで有用なものはありませんか？
あったらぜひ紹介して下さい。

>>495
アルゴリズムは手段であり、目的があってこそ発明され利用されるものだろ？
何を目的にするのかわからないのに、アルゴリズムを紹介できるか。

有効じゃなくて有名なって言ってくれれば

○ABS

○ビット単位ストア

○条件付交換

○２のベキ乗かどうか

○奇偶判定

○除算を使わずに剰余を求める

○ABS
○条件付交換
○奇偶判定
○除算を使わずに剰余を求める

横レスだがどんな処理してるの？
奇遇判定は最下位ビットを見てるのかなとおもったんだけど

>>496
とりあえず用途は限定していませんでした。

>>497-498
ありがとうございます、参考になりました。

変数の中身を入れ替えるswapアルゴリズムに関してなんですが
tmp変数を使わず実装することはできますか？

余ってるレジスタ使えば可

>>501
XOR や　+ - を使うやりかたの事？

トリッキーなコード その２　の前スレに詳しいよ。
http://pc3.2ch.net/test/read.cgi/tech/1038215563/

#include <stdio.h>

main(){
int a=2,b=5;
printf("a=%d b=%d\n",a,b);
a^=b;
b^=a;
a^=b;
printf("a=%d b=%d\n",a,b);
return 0;
}

>>501
技術評論社「Ｃ言語による最新アルゴリズム事典」買え。

>>502ｻｿ
あんがとうで御座いました

>>496
お前は見当違いのｳﾞｧｶ

>>506
おいおい。少なくとも>>496のいうことは>>501の質問だけを見ると半分正しいと思うが。
俺は>>497-498の回答を有用とは思っていないからね。

つうか、レス間違い？>>501の質問は目的がはっきりしているだろうに。

＞少なくとも>>496のいうことは>>501の質問だけを見ると半分正しいと思うが。
少なくとも>>496のいうことは>>495の発言だけを見ると半分正しいと思うが。

過去には目的があったからアルゴリズムは存在している。
歴史と同じ。>>496は歴史を学ぶことは不可能だと言うのか？

目的馬鹿は死んでいいよ。
吐き気がする。

スレ違いかもしれませんが、お願いします.
とあるボードをRT-Linuxで利用したいのですが、付属のドライバでうまく
使えなかったので、ボードに直接アクセスして利用しようと考えています。
幸い、ドライバのソースを手に入れることができたので、何とか理解して必要な部分を
利用ようとしているんですが、ソースの中のioremap(　)が良くわかりません。
引数が2つ在るんですが、それぞれ何と何を表しているのかご存知の方折られませんか？

>>511
うちんところでは、iomapのベースアドレスと、サイズのように思えるが。

>>512
レスありがとうございます。
ioremap()の引き数が意味するのは、ベースアドレスからサイズ分のメモリを確保
するという意味なのでしょうか？

man ioremap

manで出てこないんですよ･･･

manのデータなかったらでてけえへんわな

うちでは、
/usr/src/linux/Documentation/IO-mapping.txt
に説明があった。

IP記録実験
http://qb.2ch.net/test/read.cgi/accuse/1042013605/

1 名前：ひろゆき ◆3SHRUNYAXA ＠どうやら管理人 ★ 投稿日：03/01/08 17:13 ID:???
そんなわけで、qbサーバでIPの記録実験をはじめましたー。

27 名前：心得をよく読みましょう 投稿日：03/01/08 17:20 ID:yL/kYdMc
SETTING.TXT管轄でないということは全鯖導入を視野に、か？

38 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:22 ID:rLfxQ17l
>>27
鋭いです。

73 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:27 ID:rLfxQ17l
＞ところで、IPが抜かれて何か今までと変わることってあるのでしょうか？
・今までより、サーバが重くなる。
・裁判所や警察からの照会があった場合にはIPを提出することがある。

IPとってるのかぁ・・・
オマンコなんて書いたら捕まっちゃうかな（；´Д｀）ｺﾜﾋｺﾜﾋ

>>214
あっ？やんのかコラ！

最高裁への上告は認められなくなったから、これで事実上判決確定だよ。
逆転も何もないって。　　　　　　　　　　
勢いで上告なんかしても一発で上告却下(門前払い)だよ。
　　　
二審も一審を支持。これに対して上告しようにも、
刑事訴訟と同様、自由に上告できるってもんでもないのです。
民事訴訟法312条 （上告の理由） 1項
「上告は、判決に憲法の解釈の誤りがあること
その他憲法の違反があることを理由とするときに、することができる。」
http://www.m-net.ne.jp/~doba/goto/hon.htm

ようするに上告しても今の制度では100％無駄。 これで完全終了ってことか。

======2==C==H======================================================

　　　　　　　　　２ちゃんねるのお勧めな話題と
　　　　　ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数： 138720人　発行日：2003/1/9

年末年始ボケがそろそろ収まり始めた今日このごろのひろゆきです。

そんなわけで、年末に予告したIP記録ですが実験を開始しています。

「２ちゃんねる20030107」
こんな感じで各掲示板の最下部に日付が入ってるんですが、
20030107以降になってるところはログ記録実験中ですー。

んじゃ！

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

そうだね。

Abone

【ネットボランティア】余ったＣＰＵを・・・
　cell computingとは、ブロードバンドに接続された家庭内や
企業内のPCの余剰CPUパワーを統合し、
仮想的なスーパーコンピュータとしての利用を実現する
技術を用いたSI、ネットワークサービスです。
　バイオ、物理計算、設計、金融工学、CGレンダリングなどの
分野のお客様へ、安価に仮想スーパーコンピュータパワーを
提供することを目的としております。
　なお、将来的には収益にあわせてCPUパワーを提供してくださる
参加者へポイントシステムやデジタルコンテンツによる
利益還元を考えております。
http://www2.cellcomputing.jp/

２ちゃんねるのチーム作ってみました。
http://members.cellcomputing.jp/services/teams/team.htm?id=ABBE425B-CE11-4DA4-8591-C68DF67DA41A

Yahoo News

2chでIP記録実験が始まる
http://headlines.yahoo.co.jp/hl?a=20030109-00000021-zdn-sci

　ネット掲示板「2ちゃんねる」管理人のひろゆき氏は1月9日、掲示板に書き込んだ
ユーザーのIPを記録する実験を始めたことを明らかにした。

　ひろゆき氏が発行するメールマガジンで明らかにした。各掲示板の最下部の日付が
「2ちゃんねる20030107」以降のものはアクセスログの記録を実験しているという。

　ひろゆき氏は2002年末、都内の動物病院が同掲示板への発言の削除を求めた
裁判の控訴審で敗訴したのを受け、IP記録の開始を示唆していた。（ZDNet）

[1月9日19時47分更新]


ZDNet

2chでIP記録実験が始まる
http://www.zdnet.co.jp/news/0301/09/njbt_07.html

Yahoo News

2chでIP記録実験が始まる
http://headlines.yahoo.co.jp/hl?a=20030109-00000021-zdn-sci

　ネット掲示板「2ちゃんねる」管理人のひろゆき氏は1月9日、掲示板に書き込んだ
ユーザーのIPを記録する実験を始めたことを明らかにした。

　ひろゆき氏が発行するメールマガジンで明らかにした。各掲示板の最下部の日付が
「2ちゃんねる20030107」以降のものはアクセスログの記録を実験しているという。

　ひろゆき氏は2002年末、都内の動物病院が同掲示板への発言の削除を求めた
裁判の控訴審で敗訴したのを受け、IP記録の開始を示唆していた。（ZDNet）

[1月9日19時47分更新]


ZDNet

2chでIP記録実験が始まる
http://www.zdnet.co.jp/news/0301/09/njbt_07.html

>>47
日本語の分からない人だね。内容証明があったからといって
名誉毀損があったとは限らないって言ってるの。

その上で裁判所は訴状送達の翌日としたのは、その時点で
名誉毀損を「認識した」ではなくて、「認識しえた」からなの。
わかる？この違い。

>>397
そしてバレて逮捕されるわけだが・・・

405 名前：心得をよく読みましょう 投稿日：02/12/31 11:04 ID:ADTGAx9x
はぁぁぁ。あと、1週間以内で生理・・・。

何事にもむかついてたまらないっ！
生理前って、ブルーになったり、いらいらしたり。。。
ほんと勘弁してって感じ。

君たちの年収を教えたまえ。

１年を通じて勤務した給与所得者　　
男性2,834万人、女性1,675万人

男
100万円以下 　　　　　　　　　　　　６８万６０００人　　　　２．４％
100万円超　200万円以下　　　　１１７万８０００人　　　　４．１％
200万円超　300万円以下　　　　２３１万１０００人　　　　８．１％
300万円超　400万円以下　　　　４５０万４０００人　　　１５．１％
400万円超　500万円以下　　　　５１７万６０００人　　　１８．１％
500万円超　600万円以下　　　　４２５万３０００人　　　１４．９％
600万円超　700万円以下　　　　３０８万８０００人　　　１０．８％
700万円超　800万円以下　　　　２２９万１０００人　　　　９．０％
800万円超　900万円以下　　　　１５６万７０００人　　　　５．５％
900万円超1, 000万円以下　　　 １０４万９０００人　　　　３．７％
1,000万円超　1,500万円以下　　１９８万３０００人　　　　６．９％
1,500万円超　2,000万円以下　　　３７万６０００人　　　　１．３％
2,000万円超　　　　　　　　　　　　　１４万１０００人　　　　０．５％

平成１３年度　１年を通じて勤務した給与所得者 給与階級別分布　国税庁
http://www.nta.go.jp/category/toukei/tokei/menu/minkan/h13/04.htm

2chには２つの価値が今まであった、それは「匿名性」と「人数の多さ」
そして今そのうちの１つが無くなった、まあ「人数の多さ」だけでも人は集まるんだろうが
しかしこうなると「匿名性」と「人数の多さ」が合体して出来る"祭り"という物が、無くなっ
ていくんじゃないかなあ？祭り厨房としてはとてもそれが心配なんだが、、、

腐れの良い物件選びの講座開いてください

俺は火星人設立宇宙サーバーをとうしているので、
毛利宇宙飛行士でなければ追跡は不可能です。

肉体改造しろよ。ひろゆき。

87さんがんばってください。
応援だけはします！

試して駄目だったのならすみません。

でも、普通そんな風には思えませんが。

======2==C==H======================================================

　　　　　　　　　２ちゃんねるのお勧めな話題と
　　　　　ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数： 139038人　発行日：2003/1/10

なにやら、連日メルマガだしてるひろゆきです。

そんなわけで、ログ記録実験ですが、いちいちサーバ指定するのが面倒なので、
全部のサーバに入れてみました。

重くなって落ちたりしてもご愛嬌ってことで。。。

んじゃ！

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

どうぞ暴露してください

２ｃｈという不定形の巨大な組織に晒された個人も大変なわけです。

閑話休題；

Ａさんが、ある「特定の結果」を得られるアルゴリズムを作りました。
のちにＢさんが「同一の結果」を得られる別のアルゴリズムを作りました。
そしてＡさんが「Ｂはパクリだ訴えちゃる」と言い出した。さて筋は通る？

通例では「筋は通らん」「Ａにそこまで縛る権利はない」の筈だが…。

(　´db｀)ﾉ＜　実況にないと思ったら地味にスレタイに納得なのれす。

20030107aになってる板は全て？
半角とと芸能板もなってるけど。。

ネオむぎを超えるわけない
犯人が１７歳以下なら話は別だが

つーかトリップもキャップもついてないし。

600,000,002だった・・・(´･ω･`)

new clieに逝きそうなんですが・・・
でも、大きいのと、高そうなのが・・・ちょっと・・・
でも・・・

カミサンだまし作戦開始・・・

メルマガ転載きぼん

PTAって尽く冗談とか悪ふざけが存在しない世界で生きてるよな
ある意味なんかスゲェと思う
っつーか、ヴァカすぎる。

今まで2ちゃんで書かれた意味ない予告にイチイチ社会が振り回されて
たらどうなるっていうんだか。

ＤＨＣと

fusianasan

対応はともかく、確実に通知したという事実は残るよ。
メールや電話だと「届いていない」「読めなかった」「回線の調子が悪くて聞こえなかった」で抜けられるからね。

３つのしもべみたいなもんか。

（＾＾）

　　　　　　は　　低　　学　　歴


　　　　　　　　　　4　　n　　d　　！！


　
　　　　　　

（＾＾）

中央値は、x[],y[]のそれぞれ両端から比較していかないと取れないって・・・

.:*・:*・∵.☆:* ・∵.゜.☆.・∴.,★ :*・∵.:☆.。.:*・:* ・∵.+:*・∵.゜ ">*・.:.。.:*・:*・

∵.☆:*・∵.゜.☆.・∴.,★ :*・∵.:☆.。.:*・:* ・∵.+:*・∵.゜ ★
★http://www6.ocn.ne.jp/~endou/index2.html★
　　　　　　★こんなサイト見つけました★

4ndハリーポッターの本を4ndぁんだろ

教えて君ですいません、非常に基本的な操作に関してなんですが、
自分の稚拙な頭じゃ思いつかないので質問いたします。

長さ N×M の配列 A があり、これが N×M の行列を表しているとします
つまり、A[i*M + j] が行列 A の(i,j)成分であると考えます。
（i=0,1,…,N-1, j=0,1,…,M-1 とします）

この行列を
"動的なメモリの確保なしに" (つまりN,Mに依存する余分な記憶領域を使わず）
転置して、M×N行列にしたいのです。
(もちろんN != M の場合に関してです。）

すなわち、Aの(i,j)成分
A(i,j) = A[i*N + j]
を、転置行列A' （Aと同じ配列です）の (j,i)成分
A'(j,i) = A[j*M + i]
としたいのです。

O(NM)の計算量でこのような操作は可能でしょうか？

スワップ使えないの？

即レスサンクスです。
実装上の問題というよりも、純粋に数学的興味が重きを占めてます。
なんかうまい方法がないですかな…

クイズみたいで気になってねれないよう

>>560
i'=j;
j'=i;
じゃ駄目なの？

A(i,j) <=> A(j,i)として転置ができるのはM=Nの正方行列のときだけです。

例えば 4×8の行列の (2,6)成分は
2*8 + 6 = 22 だから A[22]ですよね

これを 8×4行列の (6,2)成分にするのだから
6*4 + 2 = 26 より A[26] に移動するわけです。

でも、もとの A[26] を A[22] と交換するのではだめなんです。
26 = 3 * 8 + 2 より A[26] = A(3,2) なわけですから、
これは転置後 A'(2,3) ＝ A[2*4+3]=A[11]にいれなきゃなりません

で、A[11] = A[1*8+3] = A(1,8)だから
A'(8,1) = A[8*4+1] = A[33] で
A[33] = …以下続く…

>>564
俺が言ってるのは、そういう事じゃなくて
わざわざ、メモリ上の値を入れ替えなくても
アクセス方法を入れ替えたんじゃ駄目なのって事

例えば4×8の行列の(2,6)成分は
2*8 + 6 = 22 だから A[22]
これを8×4の行列の(6,2)成分として読むには縦と横を入れ替えて
6 + 2*8 = 22 だから A[22] /* 当たり前だけど同じでしょ */

誤解すまんです。

各行を（横方向に）走査して変換するルーチンがありまして、
それを各列に対して縦方向にも適用したいのです。
もちろんルーチン内でのアクセス方法をおっしゃる
とおりに変えれば良いんですけど、それはそれで結構
面倒なんで（連続する2つの実数を一つの複素数の実部
と虚部として扱っている部分があり、複素演算ライブ
ラリでは当然実部と虚部のアドレスは連続しているもの
と仮定しているので、単純に添字を変えていくだけでは
うまくいかない）

最初は長さがNのテンポラリーな配列を動的に確保して
各々の行にたいして
一時配列にコピー → ルーチン適用 → もと配列に戻す
としていたんですけど、malloc するのはなんだかなって
思ったんで、なんかスマートな方法ないかなと。

きっかけはそれで、今や数学的興味のみです。

上げておきます、知ってるかたはヒントくだされ。

まちがえた、13行目、各々の"列"にたいして
の誤りです。
各行はルーチンに直接わたせます。
失礼しました。

>>566
http://pc3.2ch.net/test/read.cgi/tech/992671330/192
に関連しているのでは

もろにそれですね、ありがとうございます。

（＾＾）

sage

500Byteが6000個でしょ。全部メモリに入れちまえば。

空間座標変換について
例えばある点(X,Y,Z)がありますこれを空間上でRラジアン回転移動させたい場合
Z軸回転
X =X * Cos(R) + Y * -Sin(R) ;
Y =X * Sin(R) + Y * Cos(R) ;
Z =Z ;
X軸回転
X =X ;
Y =Y * Cos(X) - Z * Sin(R) ;
Z =Y * Sin(X) + Z * Cos(R) ;
Y軸回転
X =X * Cos(R) + Z * Sin(R) ;
Y =Y ;
Z =X * -Sin(R) + Z * Cos(R) ;
というところまで何とか分かりました。
次に(X,Y,Z)を原点を中心として(X,Y,Z)の通る球の大円を描くように回転させたいと思っているのですが学力不足でできません。どなたか分かる方教えて下さい；；
大円を描く回転の場合もう一つラジアン値を設定しないといけませんが…

　　　 　 　 ☆　チン　　〃　∧＿∧ 　　／￣￣￣￣￣￣￣￣￣￣￣￣
　 　 　 　 　　ヽ　＿＿_＼（＼・∀・）＜　赤黒木ってなによ？
　　 　 　 　 　 　 ＼＿／⊂　⊂＿)＿　＼＿＿＿＿＿＿＿＿＿＿＿＿
　　　　　 　 　 ／￣￣￣￣￣￣￣／|
　　　　　　　　l￣￣￣￣￣￣￣￣|　.|
　　　　　　　　|　　 　 　 　 　 　|／

バイナリ−サーチ？

>>573
日本語がおかしいのも学力不足だからですか？

がんばって解読すると「原点中心で点(X,Y,Z)を通る大円」を書きたいって
言っているように見えるんだけど、その条件では一意にならないし...

巡回セールスマン問題みたいに通る辺の値を最小(最大)にするような経路
で、かつ、通る辺の数をなるべく小さくしたいのですが、どんなアルゴリズムを
使えばいいですか？

深さ探索？

>>577
それだけじゃ仕様が曖昧だな。
・開始点と終了点は違っているのか、同じなのか
・すべての頂点を通らなければならないのか、最短パス上の頂点のみでよいのか

ダイクストラのアルゴリズムは検討した？
それで解けない問題なら、サラリーマン問題と同じくNP問題用アルゴリズムだな。

ごめんなさい
始点と終点が違うし全頂点を通るわけでもないのでTSPとは別物でした

グラフのある点からある点への経路を探したいのですが、
通る辺の値の和を最小にすることと通る辺の数をなるべく少なくするという
２つの目的があって、ダイクストラのアルゴリズムを応用できないかとも思う
のですが、いまいち思いつきません。
「なるべく」というのもはっきりしないので、質問の仕方が悪いかもしれませんが
この事例ににた問題など紹介していただければありがたいです。

トーナメント表でも作る感覚で良いんじゃ無い？

>>580
二つの条件を同時に満たす解が、必ずしも見つからないことは承知してる？
普通は、辺の重みを最小にする「最短経路問題」を使うわけだが。

通過する辺（頂点）の数も同時に最小にするのは、
辺の重みとどちらを重視するかの重み付けが、別に必要となる。

たとえば、距離が1でも重みが100の経路と、
距離が100で各辺の重みが1の経路がある場合（それら二つしかない場合）、
どちらを採用するの？

ttp://www.keim.cs.gunma-u.ac.jp/~siraisi/
「講義用スライド・人工知能特論第1」という中に、
いくつかのネットワーク問題を最小化する問題についての資料があるよ。

また、この人が訳者になっている
「組合せ最適化アルゴリズムの最新手法」丸善
は、良書なので買っておこう！

>>538
ありがとうございます

>>584
538＞なにやら、連日メルマガだしてるひろゆきです。

おまえはひろゆきに何を感謝しているんだ？

>>2/9
2chがあることに感謝してるんじゃ！
と明後日の方向にレス

すいません、ﾌﾟﾛｸﾞﾗﾑの考え方で詰まっている者です。
課題は下の画像ファイルを模したものから直線、斜線を切り出し、始まりの点と
終わりの点の座標をとってくるﾌﾟﾛｸﾞﾗﾑです。0が背景で、1が線の部分です。
どういうふうにﾌﾟﾛｸﾞﾗﾑを組めばいいのかわからず困っているのでお願いします…

000000000000000000000000000000000000000000000000
000000000000000000100000000000000010000000000000
000000000000000001000000000000000010000000000000
000000000000000010000000000010000010000000000000
000000000000000100000100000100000010000000000000
000000000000001000000010001000000010000000000000
000000000000010000000010010000000010000000000000
000000000000100000000001100000000010000000000000
000000000001000000000001000000000010000000000000
000000000010000000000010100000000010000000000000
000000000100000000000100010000000010000000000000
000000001000000000001000010000000010000000000000
000000010000000000010000001000000010000000000000
000000000000000000000000000000000010000000000000
000000000000000000000000000000000010000000000000
000000000111111111111111111111111111111111110000
000000000000000000000000000000000010000000000000
000000000000000000000000000000000000000000000000

細線化もしくはThinningでググれ

Ｃ＋＋のソースで/**/ と // が入ってるのをコメント部分だけ削除するのってどうやるんでしょう？
コメントが入り組んでるとわかりにくいんですけど…

>>589
man cpp

オセロや将棋などの二人零和有限確定完全情報ゲームではなく

運的要素が強い麻雀などを確率的に判断して、最強のアルゴリズムで
有名な研究などありますか？

>>591
ＴＤギャモンとかは？
でもあれは普通に評価関数使って打ってるだけだったかな。

おかまの質問にも答えてよ

誤爆

細線化でわかりやすいサイトが見つからない…
すいませんが、理解しやすいサイトがあったら教えてください

>595
とりあえず縦線横線だけ限定で考えれば？
それならできるっしょ
斜めは後で追加

おもしろそうな問題だな
自分で解けよ
マインスイーパーみたいな感じでできるじゃん
周辺の８方向をチェックする

自分ならどうするかな
　水平垂直なら596さんの通り、同じX座標に連続して点がある　って条件で取れる
　それと同じで４５度の線分も　x+a,y+b (a,bは±1) の４方向に連続してる条件で取れる

ってやると、45度以外の斜めの線が水平垂直線と斜め線にバラバラに分解されてしまう

だから、最後に、分解した線分の始点、終点を接続してみて、直線上に並ぶなら接続という感じの処理で接続してゆく

微妙な角度だと1つ飛びの可能性もあるから
将棋の桂馬飛びみたいにパターンが連続してるかチェックする

そういえば将棋のスレあったな

>>590
ぅぅ。cppのソースを読めってことでつか？めんどい。
がんばりまつ。

みんな凄すぎてよくわからない…

すいません、何か簡単でいいのでソースとかありますか？

何かと言われてもねぇ

Ｃ言語が全然わからないものでして...

全ての縦線と横線の始点と終点の座標を求めるサンプルﾌﾟﾛｸﾞﾗﾑをお願いします。
斜め線は…どうしよう　つД;)

麻雀の最強アルゴリズムおしえて

http://lovelove.rabi-en-rose.net/

自分が頭が良いと勘違いしているｷﾓｦﾀ君のサイト

2ちゃんねらよりかは、はるかにマシさ。

直線の検出といえばハフ変換

ハフ変換で始点や終点、また交点なんて検出できたっけ??

■□□□□□□□□□□□□□
□□□□□□□□□□□□□■

左と右の■を結ぶ直線

線の切り出しで相談した者です。

チェーンコードの考え方を使って縦横、斜めの線を切り出そうというﾌﾟﾛｸﾞﾗﾑをつくりました。
つまり、線の始点を見つけたら８連結内を時計周りに見て、他のドットと繋がっている部分を探して、そこに次々移動していくというものです
（ちょっとわかりにくい説明だな…）

縦横はいいんだけど、斜めがちょっとまだ不十分…

例えば
******
******
******
******

だと斜め線でなく横線４つと認識してしまう…
どうしよう…

>>611
基本的に区別つかないから　短い線分同士が接続してるかどうかチェックしてゆく作業は必要じゃないかな

長い線分から順に検索して、２つの線分A,Bの端点同士が一致していたら
1本の線に出来るかどうかチェックしていったら？

□□□　□□□　□□□　□□□
□■■　□■□　□■□　□■□
□□□　□■□　■□□　□□■

初めてここに書きます。

PDFを出力するプログラムを書いているのですが、円を描く所で躓いてしまいました。
PDFには円を書くというオペレータがなく、3次ベジェ曲線を書くオペレータがあります。
或る円をかいているPDFファイルをみると4つの3次ベジェ曲線で円を描いているようでした。

4つの3次ベジェのそれぞれが、円の1/4弧を描いているらしいことはわかったのですが、
制御点をどのように算出しているのかがわかりませんでした。
ご存知の方いましたらおしえてください。

>>614
斜め楕円の描画　で検索すると見つかりますよ

ポリゴンのテクスチャデータを効率よく格納したいと思いねぇ。

ある矩形領域に、大きさがまちまちな矩形領域を、はみ出さず、かつ
それぞれが重ならないようになるべくたくさん並べて置けるようにする
アルゴリズムってどういったものがあるのでしょうか？

データはあらかじめ配置するので探索に時間がかかってもokです。

高さ順にソートしておいて横に並べるとか。＜適当

確かに高さをあわせて、横に並べればよりナップザック問題に近くなりますね。

ほぼナップザック問題のような気がします。

バラバラで扱った方が効率良かったりして

以前、ここで斜めの線分の切り出しについて質問したものです。みなさんのおかげでなんとか斜めの線を切り出すことが出来ました。
下の図を、垂直水平、そして斜めに切り出すことができました！　そして各辺の始点と終点の座標を得ることができました。

000000000000000000000000000000
000000000000011000000000000000
000000000000100100000000000000
000000000001000010000000000000
000000000010000001000000000000
000000000100000000100000000000
000000001000010000010000000000
000000001000010000001000000000
000000010000011000000100000000
000000100000101000000010000000
000001000000101000000001000000
000010000001000100000000100000
000100000001000100000000010000
001111111111111111111111111000
000000000010000010000000000000
000000000010000010000000000000
000000000010000010000000000000　　(2,13),(26,13) //横線
000000000100000010000000000000　　(6,25),(19,25) //横線
000000000100000001000000000000　　(13,1),(2,13)　 //左ななめ
000000001000000001000000000000　　(13,8),(6,25) //左ななめ
000000001000000001000000000000　　(14,1),(26,13) //右ななめ
000000001000000000100000000000　　(13,7),(19,25) //右ななめ
000000010000000000100000000000
000000010000000000100000000000
000000100000000000010000000000
000000111111111111110000000000
000000000000000000000000000000

さて次のステージですが…
これを２つの三角形として認識させて、それぞれの三角形の頂点の座標を得るのにまた困っています
この場合だと、１つめの三角形は頂点(2,13),(26,13),(14,1)、２つめは(6,25),(19,25),(13,7)という具合に…
線と線の座標が重なる部分が１ドットずれてることがあるけど、それを許容範囲にして一つの頂点としてみなしたいと考えています
どういう風に頂点をみつけていけばいいでしょうか…　つД;)

>>620
せっかくだから完成したプログラム書いとけば？

>>621
普通に点と点の距離の数学的公式使ったら？
差の２乗を取って〜〜

こんなのを作りました

http://www.geocities.co.jp/AnimeComic/7356/temp0.bmp.zip

sen5-1.bmpは読み込む画像、temp0.bmp.txtは読み込んだ画像を背景を０、線を１にしてテキストファイルに書き込んだもの。
そして1.cには違うツールを使って、この画像からの線の切り出しで得られた座標をインプットしてあります。

vec(x1,y1,x2,y2)で線の始点と終点を入力させています。(x1,y1)は線の始点、(x2,y2)では線の終点という具合です。

このﾌﾟﾛｸﾞﾗﾑを実行すると、それぞれ四角形の場合の全ての頂点の座標、五角形の頂点の座標を別々に表示します。その頂点の表示のされ方も、反時計周りに辺の順番に表示されています。
線の切り出しの部分でまだバグがあるため、角数１というものが出ますが、今回は三角形以上の図形のみに着目したツールを作るつもりなので、角数１の場合はこの頂点を見つけるﾌﾟﾛｸﾞﾗﾑであらかじめ除いておこうと考えています。
これで一応頂点の座標を取るﾌﾟﾛｸﾞﾗﾑは完成としました　ﾐﾝﾅ(･∀･)ｻﾝｸｽ!

しかし…

バレンタイン企画！
http://homepage3.nifty.com/digikei/ten.html

たびたびすいません。線の切り出しで重大なバクを発見してしまいました…
まず前準備で�@白黒の画像を読み込み　�A１ピクセルごとにＲＧＢ値を調べる　�B背景である黒だったら０番、白である線の部分であったら１番を割り付け、画像の大きさと同じぶんの２次元配列gazou[y][x]に格納

線の切り出しですが、原点からｘ軸方向に順に走査していって、線の始まりを見つけます。
始めに横線だけを抜き出し、そしてまた原点に戻ってから縦線、次にまた原点に戻り左斜め、次にまた原点に戻り右斜め、といった具合に線の種類事に切り出しを行いました。
線の切り出しの方法ですが、
（続く）

（続き）
線の切り出しのﾌﾟﾛｸﾞﾗﾑ
http://www.geocities.co.jp/AnimeComic/7356/prog.zip

横線を調べるときは、ｘ軸（左から右へ）に1が繋がっている時はその長さを足していき、1が途切れたところを終点にします。
また、線を調べるたびに原点から走査しなおしているので、長さが５以上あった線には二度と調べた線を読み込ませないために、1の部分を2に変えたり3に変えたりしています。

次に縦線も同じでｙ軸方向（上から下へ）に走査していって、1が繋がっているかを調べます。あとは横線の時と同じです。

左斜めの線ですが、まず線の始まりを見つけます。そして

３４５
２＊６　（＊は現在注目している点）
１０７

で０番に１があるかどうか調べます。あったらそこに注目点をずらします。
もし０番になかったら１番をみます。あったらそこへ注目点をずらします。
もし０番にも１番にも無く、２番にあったら、先ほど横線や縦線で調べた時、白を表す１が変化していなかったら、その横方向に進みます。
これら以外の場合は終点とみなし、その座標を計算します。

右斜めの場合は、左斜めと反対で、まず０番を見ます。
そして７番、次に６番をみます。

しかし、この線の切り出しのﾌﾟﾛｸﾞﾗﾑでは
http://www.geocities.co.jp/AnimeComic/7356/kekka.gif
上の図のように、　左斜め→右斜め　なら切り出せるけど、左斜め→左斜め　と続いたら線分A-B、B-Cと読み込まれなきゃならないはずなのに、A-Cとして認識されてしまいます。

でも、もうこれ以上どうしたらいいのかわからなくて途方にくれてます…
（長文ｽﾏｿ…）

点と線の部屋
http://plaza16.mbn.or.jp/~graph_puzzle/index.html

dx,dyを保持しておく。

"C言語による最新アルゴリズム事典"ってどうですか？
これより完璧なアルゴリズムに関する本ありますか？
あったら教えてください。

>>630
奥村氏の本だよね。安いし持っていても悪くないと思われ。
解説がやや少ないのでコードで理解できる人がサワリを学ぶのに向いてる

アルゴリズムC++なんてのはどうですか？

この６２１のはなし
とある研究室でやりそうな話な気が・・・・・・

どうも…
先日皆さんの知恵を借りて作ったプログラムを持っていったら全否定食らってしまいました…
先生がいうにはこのやり方はタフなやり方じゃないらしいです。
先生がいうには
「例えば６つずつドットを飛ばして読んでいって、そこに線のドットがあったらその座標を保存していく。
　その後、２つの点を使って線の式を求め、同じように他の２点から求めた線の交点をとっていく。
　ちょっとずつ荒くみていくドットの幅を変えていったりして、何回かこれを繰り返し、似通っていた交点の座標がたくさん出てきたら、そこを図形の頂点とみなせばいい」
らしいです。

言うことはわかるんですが、これはどうやってコードにするんだろう…
画面から取れた点達から全部の線のパターンを考えて、その交点を取らなきゃだめってことでしょうか？
膨大な計算量になりそうな予感が…
実際、よくわかってないもので弱りますた…(´･ω･)

たぶんPerlだったと思うけど、半角カタカナの イ だけを
例外にしてループ処理するのは何をする時だったかな？？

多分ネパールだと思うけれどミャンマーに国名変わったよな？？

ビルマだよっ（ミャンマー）

>>634
ロバストって条件ですか・・・厄介ですね。
点列が綺麗に集まってる付近でグループ化して、グループサイズを大きくしながら幾何的な最小2乗直線を求めて
2乗誤差が敷居を割ったら止めるとか　そんな処理が思いつくけど

ちょっとゲームのアルゴリズムで分からない事があるんで
教えてください。

シミュレーションゲームを作りたいんですが、いくら頭をひねっても、
移動可能な範囲を表示する方法が思い浮かびません。

　　↓こんなのです
■■■■■■■■■■■
■■■■□■□■■■■
■■■□□木□□■■■
■■□□□□□□□■■
■□□□□俺□□□□■
■■□□□□壁壁壁■■
■■■□□□壁■■■■
■■■■□□□■■■■
■■■■■□■■■■■
■■■■■■■■■■■

どなたか、分かる方教えてもらえませんか？

>>639
座標と移動可能値をキューに積む
キューから要素を取り出す
四方を調べて、それが「値−１」より小さいなら、置き換えてキューに積む
キューが空になるまで繰り返す

>>639
お世辞にもきれいなコードとは言えんが、これでどうだ？

#include <stdio.h>
#define X 11
#define Y 10
typedef enum {DM=99,KB=-1,KI=-2,OR=-3,} Map[Y][X];
Map map = {
{DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,},{DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,},
{DM,DM,DM,DM,DM,KI,DM,DM,DM,DM,DM,},{DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,},
{DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,},{DM,DM,DM,DM,DM,DM,KB,KB,KB,DM,DM,},
{DM,DM,DM,DM,DM,DM,KB,DM,DM,DM,DM,},{DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,},
{DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,},{DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,DM,},};
void PrintMap(Map m){int x, y;for(y=0;y<Y;y++){for(x=0;x<X;x++)
switch(m[y][x]){
case KB: printf("壁"); break; case KI: printf("木"); break;
case OR: printf("俺"); break; case DM: printf("■"); break;
default: printf("□"); break;}printf("\n");}printf("\n");}
void FindRec(Map m,int x,int y,int v,int w){m[y][x]=w;
if(w++<v){
if((0<=x-1)&&(w<m[y][x-1])) FindRec(m,x-1,y,v,w);
if((x+1<X)&&(w<m[y][x+1])) FindRec(m,x+1,y,v,w);
if((0<=y-1)&&(w<m[y-1][x])) FindRec(m,x,y-1,v,w);
if((y+1<Y)&&(w<m[y+1][x])) FindRec(m,x,y+1,v,w);}}
void Find(Map m,int x,int y,int v){FindRec(m,x,y,v,0);m[y][x]=OR;}
int main(void){Find(map,5,4,4);PrintMap(map);return 0;}

せめてインデントしてよｗ

>>640
あっそうか、一歩ずつ四方を調べれば、確かにできますね。
四方じゃなくて、来た道を除く3方向でもOKかな？
移動できるコマの平均がnだとすると、 3^n だけ調べなきゃ
いけないんで速度が気になりますが、一度やってみます。

>>641
わざわざコードまで書いてもらってありがとうございます。
が、実はCはただいま勉強中で、詳しくありません。ToT
Cも分からないのかよ！！　なんて怒らないで下さいね。^-^;
そのうち理解できる日がくるはずなので、しっかり保存させてもらおうと
思います。

640,641さんどうも親切にありがとうございました。

>>643
そんなに大きいnを扱うのか？
たとえばLSIの設計だとn=100万以上ということもあるので、
この手法だと数日かけて計算することもあるが・・・。

>>639はLSIでいう詳細配線問題に相当するので、その線で調べてみ。
ちなみに>>640の手法を「迷路法」と呼ぶ。

アナルリズムて何ですか

その手のアルゴリズムはゲーム系プログラミングのサイトなんかにもにあったな……
ヘクス 移動 範囲 アルゴリズム あたりでｸﾞｸﾞﾙと吉

探索済みかつ遠回りして来たマスに辿り着いたらそのルートはそこでおしまい、
とすると余計な計算を省ける。

>>664
大きくても10ぐらいかな〜？でも3^10だと6万近くに・・・。
ほうほう、ちゃんと名前がついてるんですね。
探索で言うと、線形探索みたいなもんですか？

>>646
＞ヘクス 移動 範囲 アルゴリズム
キーワードサンクスです！
やっぱり最終的にはそういう高速化が必要ですよね。
今度は高速化のアルゴリズム考えるのが大変・・・。
好きだからいいんですが。^-^

あ、すみませんsage忘れました。鬱。

アルゴリズム体操〜、　始め！！

100以下の数値が多数あって合計で100以内に収まるよう
数値を加算してできる最小のパターンを出す
っていうようなアルゴリズムを教えてください
VBのサンプル紹介してくださるとなお有難いです

例えば次の16個の数があれば...
11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
次の7つの組み合わせに分ける
41+59, 47+53, 11+17+71, 13+19+67, 37+61, 23+31+43, 29

>>650
収納美人になる！

「任意のN個の数の幾つかの和で、数xを作れるかどうかを判定する関数」
として、↓はちゃんと動きますか？
http://pc.2ch.net/test/read.cgi/prog/1042565432/32

PLI GLPL
Jeda
せりに　きりせり
まいしち

>>650
結局自分で組みますた

heap ってどういうときに使えるのですか?
今ひとつ使える場面がピンとこないのですが。

>>655
hsp?ちょことっと3Dモデル表示したり、サウンドノベル作ったり、
ちょこっと画像表示させるようなプログラムには最適でしょ。

・・・・・・じゃなくてヒープか。
確かに、何に使うんだろう。データの整列をするとき、じゃ駄目か。
自分も知りたいです。

>>655
priority_queue

>>639
最短経路の探索だったらダイクストラのアルゴリズムかな。
この場合だったら、3*n^2くらいで収まるはず。

>>655
あるデータから上位n個を取り出したい時とか、ヒープ使うと便利かな。

＞639
まさか、塗りつぶしのアルゴズムが分からない、というわけではなかろうな

チェーンコードのプログラムを作ってみました。
ただ、このプログラムでは考えなしに次の点を決めているので、今度はロボットが自走するように、これまでのチェーンコードのログを元に、次の進行先を決定するものを作りたいと考えています。
例えば、56565656　というログがあった時、次の注目点の周囲８点の0番目,4番目、5番目にそれぞれドットがあったら、先ほどのログを参考に、自動的に「5番のドットへ進め」という
プログラムにしたいのですが…どう組みこめばいいのかわからず困っています。
すいませんがよろしくお願いします。

↓作ってみたプログラム。かきこの関係でぎちぎちですが･･ｽﾏｿ

while(1){
　if(xs==i && ys==j && l>10)　break;

　switch(vec){
　case 5:　if(gazou[j+1][i-1]!=0){j=j+1; i=i-1;　vec=4; l++;　break;}
　case 6:　if(gazou[j+1][i]!=0){j=j+1; i=i;　vec=5; l++;break;}
　case 7:　if(gazou[j+1][i+1]!=0){j=j+1; i=i+1;　vec=6;　l++;　break;}
　case 0:　if(gazou[j][i+1]!=0){j=j; i=i+1;　vec=7; l++;break;}
　case 1:　if(gazou[j-1][i+1]!=0){　j=j-1; i=i+1;　vec=0; l++;break;}
　case 2:　if(gazou[j-1][i]!=0){　j=j-1; i=i;　vec=1; l++;break;}
　case 3:　if(gazou[j-1][i-1]!=0){　j=j-1; i=i-1;　vec=2; l++;break;}
　case 4:　if(gazou[j][i-1]!=0){j=j; i=i-1;vec=3; l++;　break;}

　 　vec=5;　}
　gazou[j][i]=label_no;//再度読みこませない為に印付け}

あの。。。アルゴリズム以前の話なのですが、
WORDを返す乱数ジェネレータ(rnd)から0〜100の範囲で
偏り無く取る場合、rnd*100/65535 とやらなければ成らないのでしょうか？
もっと簡潔に得る事は出来るんでしょか。

2の累乗なら&で上位ビット外すだけで良いのですが。。

>>662
rnd % 100

>>663
正直、最近迄何も考えずに%使ってたんですが、
上が65535だから、 100だと35以下に偏るじゃないですか。
0.15%程ですが。

じゃあ、その0.15%は捨ててしまえばいい。
do{rnd=rand();} while( rnd > 65500 ) ;
val = rnd % 100;

>>662
0〜99迄の範囲で隔たりなくではなく、0〜100で隔たりなくですよね？

WORDを返すような環境だと、除算は掛算より遅いから %より
rnd*101/65536　として (rnd*101)>>16 とした方がいいでしょう。
アセンブラで int MulShr16(int n , int m); みたいなのを作っておくといい。

>664
0.15%の偏りを気にする以前にrnd自体の乱数が偏ってたりして。

【何処も】情報科学総合ｽｯﾄﾞﾚ【板違い】
http://science.2ch.net/test/read.cgi/rikei/1046173479/l50

rnd自体も適当なnずつ何度も掛けて繰り返していたのだっけ？

>>666
+1でシフトですか。。有難う御座います。
ちなみにこの場合、DWORDが必要になりますが、WORDをWORD内で
処理する方法はありますでしょか。

>>667
よく考えると0.15て全く見当違いの数字でした；
0〜100の場合の話で、範囲が広くなれば随分偏りますよ。

Javaでディレリ情報を再帰的に取得しようと四苦八苦しております。
その際に、取得する深さを指定したいのです。
指定ディレクトリから、ｎ階層下までのファイル名一覧を取得したいって感じです。

この指定階層より深いところは無視するという処理に関して、
どこか参考になるサイトないしアルゴリズムはあるでしょうか？

再帰呼び出しを使えば？
int depth を引数につけて、再帰するときに 1 ずつ減らす。

遅レスすみません。
>>658
3*n^2ですか、結構少なくて済むんですね。
物は試しってことで今作っているので、できたら
何回ループするか計ってみます。

>>660
塗りつぶしのアルゴリズムは分かるんですが、これに障害物なんかが
入ってくるとさっぱりでした。
単純な塗りつぶしは、キャラクタからのx,y座標の絶対値を足した値が
移動力以下なら移動可でいいんですよね。

問題：次の構文規則で定義される記号列「特列」を考える。
　　　　特列＝'0'|'1' 特列 特列
入力が「特列の後ろに'$'の続いたもの」となっているかどうかを判定し、
なっていればYESと出力し,なっていなければNOと出力するプログラムを、
再帰降下法に従って実現して書き下せ。ただし、次の前提を置く。
getch()を呼び出すと,つぎの1文字が変数chに読み取れる。また、文字列ｓを引数として呼び出しerror(s)を行うとsが出力され,プログラムの実
行が終わる。この問題で
t(){
if(ch=='0')
getch();
else if(ch=='1'){
getch();
t();
t();
}
else
error(NO);
}
if(ch=='$')
error(YES);
else
error(NO);
こう書いて間違ってるみたいなんだけどどう書くと正解か分かったら教えてください

★あなたのお悩み解決致します！！
●浮気素行調査
彼氏、彼女、妻、夫の浮気を調査致します！！
●盗聴器盗撮機発見
あなたの部屋に誰かが仕掛けているかも！！
●行方調査
行方不明になっている家族の消息を調査致します！！
●電話番号から住所割り出し
一般電話、携帯から住所を割り出し致します！！
●ストーカー対策
社会問題ともなっているストーカーを撃退致します！！
その他人生相談からどんなお悩みでも解決いたします！！
　直通　　０９０−８５０５−３０８６
ＵＲＬ　　http://www.h5.dion.ne.jp/~grobal/
メール　　[email protected]
　　　グローバル探偵事務局　

3つの定数 S, D, C があり、それぞれ S: 初期値　D: 増分値　C: 分割数 と定義します。
この3定数を一組としてパラメータ X で決まる値 A を用意し、Aを
　A = S + D * X ( 0 <= X < C, 0 < C )
と定義します。

ここでAの式および各定数が独立して n 個( 0 < n )あるとして、
　A1 = S1 + D1 * X1 ( 0 <= X1 < C1, 0 < C1 )
　A2 = S2 + D2 * X2 ( 0 <= X2 < C2, 0 < C2 )
...
　An = Sn + Dn * Xn ( 0 <= Xn < Cn, 0 < C3 )
という n 個の式があるものとします。
パラメータ X1〜Xn は初期状態で全て0とします。

パラメータは Xn を+1ずつカウントアップさせ、Xn < Cn が満たされないとき
Xn = 0 に戻し、Xn-1 (1つ上のパラメータ) を+1するというパラメータ変化を
行うものとします。Xn-1 < Cn-1 が満たされないときは Xn-2 を+1です。
Xnカウントアップ繰り返しの結果、最終的に X1 < C1 が満たされなくなった時点で終了とします。

総繰り返し回数を T とすると、T はC1〜Cnを全て掛け合わせた値となります。ここで

(1) 初期状態から終了状態(T回)までの各状態における A1〜An の和の総累積値
(2) 初期状態から任意の繰り返し時点 P (1<=P<=T) までの各状態における
　　A1〜An の和の総累積値
(3) 任意の繰り返し時点 Q (1<=Q<=T) から終了状態(T回)までの各状態における
　　A1〜An の和の総累積値

を求めたいのですが、皆さんの知恵を貸してください。
条件で不明な点がありましたらご指摘ください。

総累積値を求めたい背景も書いておきます。

現在既に、任意の繰り返し時点 P (1<=P<=T) におけるA1〜Anは求めることが出来ています。
A1〜Anは時間値として扱い、同時にｎ個の独立した電圧値V1〜Vnを用意して A1〜Anに割り当てて、
階段状に変化する電圧波形を出力させています。

ここで任意の時点 P において、 時点Tの電圧波形パターンを出力し終えるまでに掛かる時間を
正確に求めようとしたとき、>>676の(3)を計算により求める必要が出てきたのです。

時点P〜Tの各状態におけるA1〜Anを生成し、順次足し合わせるという方法は最も安易ですが、
nやC1〜Cnの値が大きいときには計算量が大きすぎて実用になりません。
現在 S, D, C と等差級数の和を求める数式を活用できないか、ということで試行錯誤していますが
正確な残り時間の累計値が出るに至っていない状況です。

面倒だからカウンタ X の添字は一番下を1、一番上を n とする。
t(X) = Σ[i=1〜n]{ (Π[j=1〜i-1]{ C[k] }) * X[i] }
以下では X を t の関数と考え、X(t)[i] のように書く。
時刻のときの A[i] の値 a(i,X) は a(i,X) = S[i] + D[i]*X(t)[i]
(1) A[i] の累積 f1(i) は f1(i) = Σ[t=1〜T]{ a(i,t) }
t=1〜T で X(t)[i] が値 k をとる回数は T/C[i] なので、
f1(i)
= T*S[i] + Σ[k=0〜C[i]-1]{ (D[i]*T/C[i])*k }
= T*S[i] + T*D[i]*(C[i]-1)/2
これを i=1〜n で和をとればよい。すなわち、Σ[i=1〜n]{ Y(i) }

(2) Qまでの A[i] の累積 f2(Q,i) は
f2(Q,i) = Q*S[i]+D[i]*Σ[k=0〜C[i]-1]{k*n(Q,i,k)}
ただし n(Q,i,k) はt=1〜Q で X(t)[i] が値 k をとる回数で
「Q÷C[i] = q あまり r」として、
k ≦ r なら n(Q,i,k) = q+1 であり r < k なら n(Q,i,k) = q である。
Σ[k=0〜C[i]-1]{k*n(Q,i,k)}
= Σ[k=0〜r]{k*(q+1)} + Σ[k=r+1〜C[i]-1]{k*q}
= ( (q+1)*(r+1)*r + q*(C[i]+r)(C[i]-r-1) )/2

(3) は (1) から (2) を引けばよい。

レス遅れました。

>>672
うまくいってるような感じです。ありがとうございました。

>>678さんどうもありがとうございます。

>>676内に示す表記において
　n = 2
　S1 = 1, D1 = 1, C1 = 10
　S2 = 1, D1 = 1, C1 = 10
という簡単な例(T=100)で検証中です。

(1)の計算結果は 1100 となり正しい値となるようですが、
(2)の計算結果が Q = 99 としたとき 900 となってしまいました。
本来の結果は 1100 - (10 + 10) で 1080 となるはずでしょうか。

f2(Q,i) = Q*S[i]+D[i]*Σ[k=0〜C[i]-1]{k*n(Q,i,k)} に従うと
Q = 99, i = 1 のとき q = 99 / 10 = 9, r = 99 % 10 = 9 となって
( (q+1)*(r+1)*r + q*(C[i]+r)(C[i]-r-1) )/2
= ( 10 * 10 * 9 + 9 * (10 + 9) * (10 - 9 - 1) ) / 2
= 450
i = 0 のときも q, r は同じであるから計算結果は 450 となり、
450 + 450 = 900 が(2)の答えとなってしまった次第です。

只今、納期に追われてます・・・
チェックデェジットのモジュラス43をＶＢで至急書かなければなりません。
アルゴリズムは解ったのですが、ＶＢコードの関数お持ちの方、実コード教えて下さい。
お願いします・・・・

HELPです・・・

只今、納期に追われてます・・・
チェックデェジットのモジュラス43をＶＢで至急書かなければなりません。
アルゴリズムは解ったのですが、ＶＢコードの関数お持ちの方、実コード教えて下さい。
お願いします・・・・

マップ自動生成するプログラムは解りますか？

どんなマップ？

関数型言語の map にきまってるだろ。

普通、マップといったら関数の写像関係を表す言葉しか思い浮かばないが。
f: Z -> N とかね。
関数を与えると、こういうマップを書き出してくれるプログラムのことだろ？
prolog でも作るの？

φ Z/{1,-1} -> N

↑　顔文字かと思った・・・

すいません。マップ生成とは、アートディンクのアトラスのような世界マップの自動生成と
トルネコみたいなダンジョンマップとティルナノーグみたいなフィールトのマップの
ことを言います。
わかる方どうかお願いします。

>>690
各ソフトがどんな作り方してるか、考えてみるといいですよ。

>>680
寝ぼけてたｽﾏｿ
A[i]の Q までの累積は
(Q+1)*S[i] + D[i]*(
　　((q0+1)*P[i-1])*Σ[c=0〜q1-1]{c} +
　　(q0*P[i-1]+r1)*q1 +
　　(q0*P[i-1])*Σ[c=q1+1〜C[i]-1]{c})
＝(Q+1)*S[i] + D[i]*(
　(q0*P[i-1]+r1)*q1 + ((q0+1)*(q1-1)*q1 + q0*(C[i]+q1)*(C[i]-q1-1))*P[i-1]/2 )

ただし P[i]=Π[k=1..i] C[i]、Q+1÷P[i]=q0 あまり r0、r0÷P[i-1]=q1 あまり r1

>>690
rogue の level.c:make_level() は短いから読んでみれば

三次元上で円柱と三角形の交差判定を行いたいのですが、どうしてもうまくいきません。
どなたか知恵を貸していただけないでしょうか。

Javaで10*10程度の小さな四角形を十字キーでコントロールできるプログラムを作っています。
その四角形が通ったあとに軌跡を残るようにして、
その軌跡にぶつかったら画面が赤く光るようにしたいのですが、

この問題は、どうすれば解決できるでしょうか？

>>695
何が問題なわけで?

>>695
その四角形が通ったあとに軌跡を残るようにして、
その軌跡にぶつかったら画面が赤く光るようにすればいい。

>694
三角形は枠だけ? それとも板?

>>696
>>697
具体的にはどのようにコーディングすればよろしいでしょうか？

三角形は板です。
それから、円柱は基本的にx,z軸に対して垂直です。

>699
そんなのここで語る話じゃないな。
Javaスレで聞け。

>>700
なら、真上からみたら？

>>701
分かった

株価のチャートソフトを作りたいのです。
データを時系列にプロットするプログラムなのですが、
アイディアを貸していただけないでしょうか？

>>702
ありがとうございます
試してみます

>>702
真上から「だけ」ではだめなオカン

数学板が読めないのでここをお借りします。
問題：時刻t0にて位置x0、速度v0。時刻t1にて位置x1、速度v1。この条件下で滑らかに補間せよ。
で、加速度aを一定と仮定して、横軸ｔ、縦軸xとするとtnで値xn、傾きvnの放物線ができると予想。
F(t)=x=a(t-p)^2+q--------------A
｢ F(t0)=x0=a(t0-p)^2+q---------(1)
L F(t1)=x1=a(t1-p)^2+q---------(2)
dF(t)/dt=dx/dt=V(t)=2a(t-p)----B
｢ V(t0)=v0=2a(t0-p)------------(3)
L V(t1)=v1=2a(t1-p)------------(4)
で解いたところ
p=(v0t0-v1t1-2(x0-x1))/(v0-v1)
a=(v0-v1)/2(t0-t1)
q=2x0/(v0(t0-p))=2x1/(v1(t1-p))
となりましたが、全然違うみたい。式の立て方が間違ってますか？
qの等式成り立つのかと疑問ですし。添削おながいします。

あー、加速度=2aだけどね

数学板ふっかつしたようなのでそっちに逝ってきます

…

VB初心スレから誘導されました。初心者質問で申し訳ないのですが，
＜全部平均するとこちらが設定したような数Ｎになるような乱数（乱数の個数も
こちらが設定）を発生するような方法＞というのはどのようなものなのでしょうか？
どうかよろしくお願いします。

>>711
まず好きな特性の乱数を作りだす
その後、その乱数の平均を求めて、　設定した値 N との差を出し、　乱数列の全部の要素に足せばいい

>712
どうも有難うございました。助かりました。

アルゴリズムと聞くとリンゴを思い浮かべてしまうね

オーダ記法で教えてください
O(f(n)) + O(g(n)) = O(max(f(n) , g(n)))
この式のmax(f(n) , g(n))とはどういう数式なんでしょうか？

エクセルのmax関数と同じでいいんでしょうか？

>>715
もしもし？

突然ですが、この間ゲーセンで「ぷよぷよ」やってたんですが
そこでふっと疑問。
あの同色のぷよが４つ以上そろったら消えるって、どういうアルゴリズムなんですか？
ぷよのならべ方はべつに直線とは限らないし、時には６つ・７つと繋がる
こともあるわけで。
ほんと疑問です。誰か分かる方おられます？
ひょっとしたら初歩的な質問かもしれませんんが。

>>717
ttp://chaos2.org./xpuyopuyo/index.shtml
ttp://www.geocities.jp/catt9a/program/p2001_06.html

>>718
わ〜い　１０２１点いった〜ヽ(∇⌒ヽ)(ノ⌒∇)ノ

わ〜い　１６２７点更新〜ヽ(∇⌒ヽ)(ノ⌒∇)ノ　南無ロックキー使いましょう（謎）

red black tree　の名前の由来は何ですか?
google ってみても、うまく引っかからない。

なぜ white black や red blue ではなくて red black か、ってこと？

Standard C/C++　赤黒木の改良 P. J. Plauger/熊谷典大訳

まぁ、これでも読んでみ

引用、失敗。
上記記事は C MAGAZINE, 2000年10月号 に掲載なのだ

（゜Д゜）ｺﾞﾙｱﾘｽﾞﾑ
ｽﾞﾝﾁｬｽﾞﾝﾁｬ♪

＞721
Red Sun Black Clossからきているんだよ(w

赤字黒字？

1 次時間、 2 次時間ってなんですか？

配列から要素を削除することの説明で出てきたのですが。

O(n) O(n^2) のことじゃない？

first order, second order かもしれない。

(doubly)linked list はどういうときに使うと効果的なのですか?
普段は Java を使っているんですけど、 LinkedList のありがたみがあまりよく分かりません。

可変長配列が作れる。
ArrayList とか連結リストじゃないっけ。

他には、キューからデキューするときのように全体をシフトしたい場合とか。

すみません、教えてください。

行列（最大１０×１０）の固有値を
Cのプログラムで求めたいです。

世には色々な方法がありますが、
ソースが手に入って、精度も良いお勧めの方法を教えてください。
希望をいえば、matlabのeigと同じ精度（欲張ってすみません）

行列要素は、実数です。ただし、対称行列ではありません。
C言語によるアルゴリズム辞典
http://www.matsusaka-u.ac.jp/~okumura/algo/
では、全部実対称行列が対象だった。（泣）

よろしくお願いします。

>>734
ふらっと立ち寄ったものですが，LAPACKではどうでしょうか．
初めての方には，たとえば大西さんのページがよいと思います．

ttp://www.a.mei.titech.ac.jp/~yonishi/Program/CLapack/

>>735さん、ありがとう。

でも、Cのソースが欲しいのですよ。
よい方法を模索中です。

いつもここから「NHKピタゴラスイッチ アルゴリズムたいそう」

>>734
マルチはマナーとしてあまりｲｸﾅｲよ。
今度から気をつけてね。

>>738さん

そうですね。気をつけます。
（ちょっと慌てていたもので、、、）

Cの標準関数 sqrt より
高速に平方根を求めるアルゴリズムはありますか？

sqrt はニュートン・ラプソン法の逐次計算によって
根を求めているのでしょうか？初期値は？

sqrt って基本的な関数ですけど
ふと、どうやってんだろうと思ったもので。

>>740
> Cの標準関数 sqrt より
> 高速に平方根を求めるアルゴリズムはありますか？

答えは「ある」だろうけど、数値計算の相応の専門知識が必要になるのでは?
まちがっても、このスレでちょっと質問して、すぐわかるような問題ではないと思われ。

x86なら、多分FPUのfsqrt命令使ってるのでは？

>>740
標準関数だからといって実装まで<標準>があるのではありません。
>>742さんが書いてる通り、パソコンではFPU命令が使われるのでそれ以上高速にするのは不可能です

浮動小数点の場合、初期値は、
指数部を半分にして、奇数なら√2倍する事を覚えておいて、実数部はテーブル検索で用意するのでしょう

>>それ以上高速にするのは不可能です

俺742だけど、そんな風に書かれると注釈加えたくなるなあw

標準関数といえど関数の中に入っている以上、インラインアセンブラでfsqrtを直接書けば
スタックフレームとかcallまわりの処理を省けるので速くなります。
でも、コンパイルオプションによっては数学関数を自動的に展開してくれるコンパイラもあるのでなんとも。

>>744
それは実装上のテクニックだから、アルゴリズムを改善した事にはならないでしょう。

ニュートン法は1回毎に精度桁数が倍になるんで、初期値を適切に選べば
これより高速なアルゴリズムは難しいでしょうね。

精度が不要なら別だろうけど

AMD の 3DNow はsqrtや逆数を
・精度の低い値を求める命令
・Newton-Raphson法で精度を高める命令
と段階をふんで求めるようになってるね。
低精度でいいのなら、1命令=1clkですぐに結果がでるという。

>>740
see.
情報処理学会論文誌 Vol.31 No.07

いろいろ参考になりました。
自分でもいろいろ調べてみます。

パトリシア木やDouble Array　なんかが解説されている書物はありますか?

>>749
あります。

ヾ(゜▽、゜)ノ パトリシア……

（＾＾）

1:1のマッチングのロジックを書く時って大体

if a > b
a only処理
if a < b
b only処理
if a = b
match処理

だと思うけど、他に良い方法ってあるかな？

if a > b
　a only処理
else if a < b
　b only処理
else
　match処理

分かっているとは思うけど、整順序の場合は比較評価は２回で済む。

いくつかの数字があって、それらを自由に組み合わせて二つのグループに分け、
各グループの数字の合計が、全数字の合計の半分の値に最も近くなるような組み合わせを、
発見するようなアルゴリズムってありますか。

「ナップサック問題」で検索すると幸せになれるかもしれない。

>>756
レス、サンクスです。ググって調べてみます。

ググって調べたところ、自分にできるのは総当たりしか無いことが分かりました。
幸せになったような、なってないような・・・。微妙なところです。

diffのアルゴリズムを教えてください。
一応動く程度の処理なら書けるのですが、出力結果が最小になるようにする方法が
全然わかりません。

>759
diffのソース読め

>>755
ソートして交互に取り出したら、正解になったりしない？

>>754
アセンブラだと比較自体は1度で済むね。
条件分岐は2回入るので一緒だけど。

>>761
両グループ同じ要素数とは書いてないからそれじゃだめじゃない？
｛10,1,1,1,1,1｝のような場合、｛10,1,1｝と｛1,1,1｝じゃなくて
｛10｝と｛1,1,1,1,1｝に分けたほうが近いじゃん。

>>759
vivi の作者さんのページに文書比較アルゴリズムについての説明と
論文へのポインタが載ってる。

>760

見てはみたのですが何をやってるのかさっぱり...でした。

>764

はい、これも読ませてもらいましたが理解できなかったんです。
いろいろ調べてみたんですが良くわからなかったので、
諸先輩方に教えを乞おうっと思って書き込みさせてもらいました。

>>765
diff もどきが作れるのに、ソースも論文もわからないとなると、
関連参考書を買って、勉強するしかないんじゃないか。

>766

何か参考になるものがあれば、喜んで購入します。
もしご存知でしたら、関連参考書を教えてください。

>>763
あーそうかー。

じゃぁ、二つの集合A,Bに合計値を覚えながら追加することにして、
Aの合計がBの合計より大きいときだけBに追加（それ以外はAに追加）したら、
正解にならないだろうか？

>>768
例えば {2, 9, 9, 10, 10} なんかで困りそう。
多かったらどれかを戻して…とかやってくと、やっぱり総当たりと同じになりそうだし…

>>769
ん？大きい順に分けていけば？

ソートするなりして、最小値のを一つ取って再帰する。
再帰の結果に残しておいたのを合計値の半分により近くなるように分配する。

大きいほうから並べて>>788のやり方でもいいと思うけど。

さあ、>>788に期待がかかりました。

ゴメン。>>768だったね。

>>755 の問題って、結局のところナップサック問題(合計の半分の大きさのナップサックに詰める)で、

ナップサック問題はNP完全だろ。

ちゃんと解こうとしたら総当たりにしかならないんじゃないか。

AVLムズい。頭パンクしそう、、、

>>770,771
>>769 のは {2, 9, 9} と {10, 10} に分けたい例だけど、最初から均等にしてたらできないよ。
大きいほうからだと、 {9, 10} と {9, 10} のどっちかに 2 を追加するって感じになっちゃう。

>>776
あー、だめか。解説どうも。

>>767
アルゴリズムイントロダクション第2巻の最長共通部分系列

>>755
以前、もう一つのアルゴリズムスレで話題になった。

>>775
B木ならまだなんとかなるけど、AVLとか赤黒ってよっぽど慣れてないと
ちゃんと動くまでに時間掛かりすぎるよね。

>>778

ありがとうございます。
探してみます。

1970年を起点とした秒数から、年月日・時刻を求めるアルゴリズムを探しています。
丁度、gmtime関数がtime_t型の値を変換するものと同じです。

単純に秒を365*24*60*60で割ると閏年の問題で4年ごとに1日ずれてくるので、
Year/4-Year/100+Year/400-477 (閏年で増えた日数)
を単純計算で求めた日数から引いてマイナスになったらYearから1引く…なんて考えましたが、
そもそもYearが正しく求められていないので使用することができませんでした。

誰かご存じの方がいればよろしくお願いします。

２年ずらしたら？

year%4==0
(year-1970)/4 ?
色んな計算式を挙げてみたら？
Ｃ言語？

>>782
400年の日数は 146097 = 400 * 365 + 400 / 4 - 400 / 100 + 400 / 400
100年の日数は 36524 = 100 * 365 + 100 / 4 - 100 / 100
4年の日数は 1461 = 4 * 365 + 4 / 4

n400 = day / 146097;
n100 = (day % 146097) / 36524;
n4 = ((day % 146097) % 36524) / 1461;
n1 = (((day % 146097) % 36524) % 1461) / 365;
year = n400 * 400 + n100 * 100 + n4 * 4 + n1;

みたいな感じでやれば？

秒>分>時>日と出していき、>>785さんの方法で試したらできました。
意見を出して頂いた方々、ありがとうございます。

例えば大量の千円〜9千円ぐらいの領収書が大量にあったとして、
その中の組み合わせで3万円に
一番近い数字になるように計算して一番近い順にならべていく方法が
あったら教えてください。
一応、考えている言語はC言語です。
ちなみに
ナップザック問題を見たのですがどう応用するばいいかよくわかりませんでした

>>786
気にスンナ

>>787
総当りで。

>>789
総当りしかないんすかねー。
バカなんで、総当りでもどうやったらいいか悩みそう・・。

>>790
名前入れるのを忘れた・・。

後、そういうフリーまたはシュアのソフトがあれば、それでもいいのですが。。
ソフトがあるかどうか質問するスレで聞いたのですがなかったもので
自分で作るしかないかなと思って質問しました。

そのうちの一つが3万円に近いことを優先するのか、
3万円から最大誤差のセットで差を出来るだけ小さくしたいのか

>>793
そのうちの一つが3万円に近いことを優先のほうです。

あ、すいません。ちなみに3万は越えないという条件で・・。

２千円ばかりの物だったら、２万８千円のばかりを作ってもいいということ？
２８千円×１４組？

配列[ a b c d e f g h i j]があってこれは昇順で整列されているとする。
で、配列が正規分布に従うと仮定する。でa+j = b+i = c+h = d+g =e+f　
と推測して、a〜jが1から9である場合、(a+j) + (b+i) + (c+h) = 30
になるとするってどうよ

>>796
えーと。
3万円までのグループでOKです。
3万1円はXで、3万円は○です。

>>797
まだ理解してないんですけど、どうなんだろうか。。

１〜１００までの自然数において、２の倍数、３の倍数、５の倍数の和をそれぞれ求める
SU…１〜１００までの自然数、B2…２の倍数の和、B3…3の倍数の和、B5…5の倍数の和

このアルゴリズムがかけないです・・・
どなかた助言お願いします

>>800
小学生からやりなおせ

>>800

for(i=1; i <= 100; i++){
　　if(i % 2 == 0) B2 += i;
　　if(i % 3 == 0) B3 += i;
　　if(i % 5 == 0) B5 += i;
}

>>800
教えたので教えてください．
組み合わせ／パズルに関するアルゴリズムについてです．

「カ」「キ」「ク」「ケ」「コ」の文字を使って形を作ります．
（別にカキクケコじゃなくてもそれぞれの文字が見分けられれば何でもいいです）

・作る形の例

＋＋＋＋＋＋＋　＋＋＋＋＋＋＋
＋＋＋キ＋＋＋　＋＋＋＋＋＋＋
＋＋カクケコ＋　＋キカクケコ＋
＋＋＋＋＋＋＋　＋＋＋＋＋＋＋
＋＋＋＋＋＋＋　＋＋＋＋＋＋＋

好きなように配置して形を作ればいいのではなく，
どこになら置いていいのか，というのが決まっています．

・置くきまりの例

「カ」の横に置ける文字　「キ」と「ク」
「キ」の横に置ける文字　「カ」と「ク」
「ク」の横に置ける文字　「カ」と「キ」と「ケ」
「ケ」の横に置ける文字　「ク」と「コ」
「コ」の横に置ける文字　「ケ」

（続く）

（続き）

で，このきまりに当てはまる形が上の 作る形の例 で示したものです．

次の２つは同じ形とします．

＋＋＋＋＋＋＋　＋＋＋＋＋＋＋
＋＋＋キ＋＋＋　＋＋＋＋＋＋＋
＋＋カクケコ＋　＋＋カクケコ＋
＋＋＋＋＋＋＋　＋＋＋キ＋＋＋
＋＋＋＋＋＋＋　＋＋＋＋＋＋＋

・・・
こんな具合のパズルなんですが，
これを 置くきまり を元に，何通りの形があるのか，
どんな形が作れるのかを求めるアルゴリズムは何かありますか？
応用できそうなアルゴリズムでも結構です．
なにか情報があれば教えてください．

（ｽﾞﾚました．実際は＋マークがそろいます）

>>802
ｽｹﾞｰよ、あんた天才さよ

コケコケコケコ．．．．と無限に続くような気が．．．
それとも枠が決まってて、それが＋で表した領域？

>>806
あ，文字は一度しか使えません．
説明不足でした．

ペントミノのピースに文字を書くみたいなものか。

>>808
そうですねぇ，近いかもしれません．
置くきまりを，
「カ」の横に置ける文字　「キ」「ク」「ケ」「コ」
「キ」の横に置ける文字　「カ」「ク」「ケ」「コ」
「ク」の横に置ける文字　「カ」「キ」「ケ」「コ」
「ケ」の横に置ける文字　「カ」「キ」「ク」「コ」
「コ」の横に置ける文字　「カ」「キ」「ク」「ケ」
と，自身以外の文字全て指定すれば
ペントミノのピース（12種類）の形は全て作成できると思います．
ペントミノ（その他のミノでもいいですが）のピースを
生成するアルゴリズムがあれば参考になるかも知れません．．

ピースの自動生成は後回しにして、取りあえず手作業でデータを作る。
個々のピースの各位置に文字を書いていけるか総当たりでチェック。
対称性のチェックは後回し。。。

ピースの構造体 (Pascal)

　type
　　moji = (ka, ki, ku, ke, ko);

　var
　　piece: array[1..5] of record
　　　V: moji;
　　　l, r, u, d: integer;{上下左右に連結してるパートの番号）
　　end;

■
■■■　　　
■

例えば上のピースの定義は

　piece[1].d := 2;
　piece[2].u := 1; piece[2].d := 3; piece[2].r := 4;
　piece[3].u := 2;
　piece[4].l := 2; piece[4].r := 5;
　piece[5].l := 4;

で、piece[1]からpiece[5]にルールチェックしながら文字を順に入れていく。

ルール表現 (Pascal)

　type
　　moji = (ka, ki, ku, ke, ko);

　var
　　rule: array[moji] of set of moji;

としておいて

　rule[ka] := [ki, ku];
　rule[ki] := [ka, ku];
　rule[ku] := [ka, ki, ke];
　rule[ke] := [ku, ko];
　rule[ko] := [ke];

せっかくあるんだから、ついでだからと
Pascalの集合やスカラー型を目一杯使ってみたりして。
わざわざ面倒な（他言語使用者に分かりにくい）書き方をしてるとも言える。

ペントミノは12種類くらいじゃなかった？

御参考まで、ペントミノ全12種類

■■■■■　■■■■　■■□□
□□□□□　□□□■　□■■■

■■■　■■□　■□□　■■
□□■　□■■　■■■　■□
□□■　□□■　□□■　■■


□■□□　■■□　■□□
■■■■　□■■　■■■
□□□□　□■□　■□□


■■■
■■□


□■□
■■■
□■□

最後の2つは、この問題の解にはならないね。

ランダム置換列の生成の問題で、0からn-1の整数値があり、全て値が異なるような長さＬ(Ｌ<=n）であるランダム置換列をできるだけ速く、短いプログラムを作り、その正当性を証明して。
という問題が出んです。rand()を使ってみるといいって言われたんだが、どうもできません。助けてください！

知りたかったらageなさい。

スマソ。age
ぜひともアドバイスくださいまし。

>>814
同じ質問を答えたことがあったな。宿題スレだったかな？
そのときは
・n個の配列を作り 0〜n-1 まで順に入れてゆく
・randを使い、配列をシャッフル
・先頭からLまでを答えとする
などの解答がでた。過去ログさがしたがDATオチかな

毎年、必ずこの時期に出る質問だよね。　俺も、もう２度書いたと思う。飽きた。

そんなにベタな問題なのでしょうか？
それとも同じ学校、同じ授業で誰かが毎年2chで質問？((((；ﾟДﾟ)))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ

>>819 たぶん同じ授業だな。5年は続いてるよ。　そろそろ課題変えろって先生に言え

とにかく　ニフティ時代から毎年ゴールデンウイークあけにこの問題だ

そうなんだ。
とにかくなんとかなりそうです。ありがとうございます

正当性って定義によるけど例えば順列上の一様分布になることの証明って
簡単じゃないと思う。

たぶん、正当性をきちっと証明するのは要求して無いとおもいます。
その方法が一番早いよってことを説明する程度でよかったとおもう。

>>824
> その方法が一番早いよってこと

むしろそっちの方が難しいと思われ

そっか。うぬぬ。まあちゃんと動くよってことぐらいにしときますw
でもうまく書けないんですよ。プログラム自体が。
100*rand()%50
こんな感じにrand使えばいいんですかね？変数にして。

>>826
まずは、何の言語を使うかだな。

>>827
今C++でやってます。
char s[n]
で数列ｓをつくってみて
for文でn回ループさせて・・・
ってとこまでで、それから進みません(|| ﾟДﾟ)
明日なのに、やばいです・・・・

先頭になれるのは Nから一つ 　次は (N-1)から一つ って手順をそのまま書くのが一番はやいだろうな

// 変な方法
#include <time.h>
#include <stdlib.h>
#include <stdio.h>

int shuffle_cmp(const void *x, const void *y){return 2*(random()%2)-1;}
void shuffle(void *b, size_t n, size_t s){return qsort(b,n,s,shuffle_cmp);}

int main(int argc, char **argv)
{
int n, i, *a;
long s;
n = argc>1 ? atoi(argv[1]) : 10;
s = argc>2 ? atoi(argv[2]) : time(NULL);
if (NULL == (a = (int*)malloc(n*sizeof(int)))) return 1;
for(i=0; i<n; i++) a[i] = i;
srandom(s);
shuffle(a,n,sizeof(int));
for(i=0; i<n; i++) printf("%d ", a[i]); puts("");
return 0;
}

>>830
これは？いったいどうなっているのでしょうか？
変な方法なのですか？

c:\program files\microsoft visual studio\myprojects\ＸＸＸＸＸ\test.cpp(14) :
error C2065: 'shuffle' : 定義されていない識別子です。
srand(s);
っていわれます。これはどうなってるんですか？

>>814
C++でもっともマトモな方法ならば、
#include <algorithm>
#include <vector>
std::vector<int> make(int n, int k)
{
  std::vector<int> x;
  x.reserve(n);
  for(int i = 0; i < n; ++i)
    x.push_back(i);
  std::random_shuffle(x.begin(), x.end());
  return std::vector<int>(x.begin(), x.begin() + k);
}
これ以上はないでしょう

g++ だと random_shuffle() って順にランダムな相手と交換してるだけなのか。
このアルゴリズムである特定の順列の確率ってどうやったら求まるんだろ。

ttp://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc%2b%2b-v3/include/bits/stl_algo.h?rev=1.29&content-type=text/x-cvsweb-markup

スレ立てるまでもない質問はここでスレ(http://pc2.2ch.net/test/read.cgi/tech/1051370263/)
より誘導されてきました。

経路探索アルゴリズムを勉強しているのですが、A*(A-Star)アルゴリズムがいまいち
つかめません。
breadth first search(bfs)にコストを導入したもの、というところまではわかったのですが…。

1.パス情報を持つデータを用意する
2.それをオープンリストとし、開始点q(親)を選ぶ
3.qの子ノードのコストを計算する
4.子ノードから一番コストの低いものを選ぶ
5.qをクローズリストに追加し、選ばれた子を親として終点にたどり着くまで繰り返す

これでいいんでしょうか？
これだと行き止まりにいってしまった場合探索が失敗すると思うのですが…。

google による検索結果から以下のURLを参考にしました。
ttp://rajiv.macnn.com/tut/search.html

>>834
random_shuffle が利用する乱数生成器が一様分布に従う場合を考える。
まず k 回目の交換が終った時点で x[k]〜x[n-1] は未交換であることに注意しよう。
n-1 回の交換の結果 x[0]〜x[n-2] の順列が等確率に生成されることを仮定すれば、
n 回目の置換によって末尾の要素 x[n-1] を x[0]〜x[n-1] のいずれかと
等確率で初めて交換されるので n 回の交換によって作られる各順列は等確率となる。

あれから他にも調べて理解が進んだので・・・

1.オープンリストに開始点を入れる
2.オープンリストが空になるまで繰り返す
3.　オープンリストの中から最小コストfを持つもの選び、取り出す
4.　それをqとし、周囲8セルの子ノードを作る
5.　子ノードの数繰り返し(8回)
6.　コストを計算する
7.　オープンリストの中に存在すればスキップ
8.　クローズリストの中に存在すればスキップ
9.　そうでなければオープンリストに追加する
10. 子ノード繰り返し終了
11.クローズリストにqを追加する
12.オープンリスト繰り返し終了
13.解はクローズリスト

これでOKなんでしょうか？
どうしても無駄な要素がクローズリストに出てくるのはコスト計算を失敗しているから？

>>837 理解が進んだというか、全然読んでなかったように見えるけど…
closed list は解じゃなくて探訪済みのすべてのノードをとっとく集合。
これがあるせいで A* は指数領域オーダー。
解かどうかの判定は5,6の間で行なって、子がゴールに到達してたらその時点で返すの。
7, 8 はコスト比較の条件が抜けてる。

そもそも該当ページのsuccessorがいったい何なのかが不明だったんです。
申し訳ない。
closed listが探訪済みノードの集合だとすれば解は一体どこへ…？
7,8のコスト比較はリスト内にコストの低い点があればを追加すればいいという
事でOKでしょうか。

>>839
ゴールに着いたらそこから親をたどっていけば解を作れるでしょ。

> 7,8のコスト比較はリスト内にコストの低い点があればを追加

逆。全然分かってないっぽいので注意しとくと、
比較するのは closed にある「同じ位置を指すノード」。
子が未探訪の位置を指すか探訪済みでも既知の道より近道(コストの低い道)だったら
open と closed の両方に加える。だから open 内のノードと比べる必要は本来ない。

そうか、親へのリストを辿ればいいわけですね、thx

7,8はつまりリストに一致するものがあって且つその一致するものと現在のノード
コストの比較を行えばいいんでしょうか？
つまり
function check (list, node) {
　for each (list) {
　　if (list == node && list.cost < node.cost) skip;
　}
}
抽象的な表現ですがこんな感じ？

>>841
コードの意図がよく分からん。正しいともいえるし間違ってるともいえる。

この辺見るよろし
ttp://www-fs.informatik.uni-tuebingen.de/~hueffner/

可能ならこの記事で参照してる以下の論文を入手して読むこと
P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the
heuristic determination of minimum cost paths. IEEE Transactions on
Systems Science and Cybernetics, SSC-4(2):100-107, 1968

>>842
そのページも一度みてみたんですけどね。
とりあえず論文取り寄せてみます、ありがとうございます。

＃関係ないけど「A-Star(A^*)」という出だしの(A^*)が顔文字に見えた…

ランダムな数値配列の中である数値にもっとも近い組み合わせを導きたいのですが
総アタックよりも効率的な方法がありますか？
配列をソートして
・・・という感じになるような気がするんですが、そこからどうやれば良いかわかりません。

>>844
前も聞いてなかったか？

初めてです。でも過去ログにあるってことかな？
見てなかった。ごめんね

846==787?

>>847
ありましたね。しかもすぐ近所に。
しかし、797の回答ではプログラムに起こすのは困難な上に
非効率的すぎるのですが・・・
もともと、仮定と推測って・・・。
そんなファジーなアルゴリズムはアルゴリズムって呼べるんでしょうか？

>>848
自分の無知を誇るようなレスはやめたほうがいいよ。
リアル厨房なら仕方ないが。