アルゴリズムに関する質問、議論総合スレ
レス数が950を超えています。1000を超えると書き込みができなくなります。
0001デフォルトの名無しさん
NGNG類似スレが多くてどこに書きこめば分からないときは
とりあえずこちらにどうぞ。
0002デフォルトの名無しさん
NGNG0003デフォルトの名無しさん
NGNG「直線や円の2ドット以上の太さを持つ描画アルゴリズム」
をどうしてるか聞きたい。
0004デフォルトの名無しさん
NGNG刺繍と同じ。
0005デフォルトの名無しさん
NGNGコルメン、ライザーソン、リベスト共著「 アルゴリズムイントロダクション全３巻 」近代科学社
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
# ほぼ完全なプログラムが載っていて初学者におすすめ。
0006仕様書無しさん
NGNGウチの会社の筆記試験だYo!
0007デフォルトの名無しさん
NGNGデバイスの解像度、速度優先か見た目優先か、アンチエリアシングするか、とかによって違うから、
これだけじゃ答えようがない、が正解。
0008デフォルトの名無しさん
NGNGじゃ、デバイスはPCのモニタ、速度優先、アンチエリアなしで。
0009デフォルトの名無しさん
NGNG0010デフォルトの名無しさん
NGNG数学できないヤツは全然理解できないですよね
ということで数学やり直し中。黄チャートまでやったら読めるようになるかな・・・・
0011デフォルトの名無しさん
NGNG0012デフォルトの名無しさん
NGNG直線作画を少しづつずらしながら太さのぶん連続で行う方法と
円作画を少しづつずらしながら長さのぶん連続で行う方法があります。
がんばってください。
0013デフォルトの名無しさん
NGNG描くなんてことはしてないよ。
00143
NGNGあくびが出るほど遅いんですよ。
リアルタイムでやる必要があるのであくびが出ちゃうと
まずいな、と。
>直線作画を少しづつずらしながら太さのぶん連続で行う方法と
これはいいかも。0.5ピクセルずつずらせば大丈夫かなあ。
ありがとうっす。
00153
NGNG意見聞きたいっす。
0016デフォルトの名無しさん
NGNG円ずらしって最悪でも最速アルゴリズムの８倍程度の処理時間におさまるはずだ
実装がまずいんじゃないの？
0017デフォルトの名無しさん
NGNG太さ２だとして４５度の線なら途中は３ピクセル分水平にドットを並べる
円の場合も同じで、直径の違う２円として、水平に輪切りして処理するとか
0018デフォルトの名無しさん
NGNGまさか、毎回円を１から描いてるんじゃないよね？
直径ｎの円のビットマップ作って、転送してるよね？
0019デフォルトの名無しさん
NGNG0020デフォルトの名無しさん
NGNG0021デフォルトの名無しさん
NGNGアクセラレータが使えないドでかい画像処理なら今もそうだよ
0022デフォルトの名無しさん
NGNG00233
NGNGすんません、言うの忘れてたんですけどレタッチ的なものを作ってるので
アルファブレンドも考慮に入れないといけないんす。
なので、ビットマップの転送ってのは出来ないんです。自力で計算しないと。
>最速アルゴリズム
聞きたいです。
>>17
あ、これもいいですね。直線ずらしは別バッファに一度書きこんでおかないと
重ね書きしちゃう可能性があったんですけどいいっすね。
ちょっとアルファ値の計算が時間かかりそうだけど問題ないかな。
0024デフォルトの名無しさん
NGNG> >直線作画を少しづつずらしながら太さのぶん連続で行う方法と
> これはいいかも。0.5ピクセルずつずらせば大丈夫かなあ。
横方向もDDLで書いてみるとどうなのかな?
pixelに空きが出来ちゃうのかな?
0025デフォルトの名無しさん
NGNG002619
NGNG002719
NGNGマスク画像かによるけど）それの時間がかかってるっぽいね。
だったら、出来るだけ同じpixelの処理を何度もやらない方法が速いでしょう。
もしかしたら、図形をポリゴンにして、スキャンラインにしたほうが速いかも。
プロファイルとってみたら？
0028デフォルトの名無しさん
NGNGαﾌﾞﾚﾝﾃﾞｨﾝｸﾞしても同じです
ﾌﾞﾚﾝﾄﾞのコスとがデカイなら、別に形だけマスクとして作っといて
マスクのあるとこだけ計算すればいいんだから
00293
NGNG円ずらしをしてたので、遅い原因は同じ座標を何度も計算しなおしてる
ところにあったんす。ですので直線描画のアルゴリズムを見直せば（同じ
座標を計算しないようなアルゴリズムならば)アルファブレンドに関係なく
速くなるかな、と思ったんすけど。すんません。
とりあえず教えてくれたもの全部試してみるっす。
0030John ◆0z.4Is5E
NGNG0031John ◆0z.4Is5E
NGNGごめん
0032デフォルトの名無しさん
NGNG最速計算アルゴリズムはどうやってるんですか？
0033デフォルトの名無しさん
NGNG0034デフォルトの名無しさん
NGNG0035John ◆0z.4Is5E
NGNGファイルが変更されたかどうかをチェックする場合、
1/2^(16*8*2)の確立で失敗するんでしょうか？
MD5の計算方法ってどんな感じですか？
0036デフォルトの名無しさん
NGNG0037デフォルトの名無しさん
NGNG0038デフォルトの名無しさん
NGNGhttp://www.google.com/search?q=rfc+md5
0039John ◆0z.4Is5E
NGNGじゃあ、ここはいったいどう利用するの？
0040デフォルトの名無しさん
NGNG一々説明するのが大変だから既存の文書を読めって話でしょ。
0041デフォルトの名無しさん
NGNG少なくとも、「誰が調べてもすぐ答えが一つに定まるような
質問に答えるコーナー」として利用するのはつまらんではないか。
大勢に訊いて議論に持ち込む余地があるよーな質問、なら面白いが。
0042デフォルトの名無しさん
NGNG英語読めません...
0043デフォルトの名無しさん
NGNG読めるようになってから来てください。
0044デフォルトの名無しさん
NGNG初心者歓迎質問スレに行けば教えてくれると思う。
0045デフォルトの名無しさん
NGNGところで 1/2^256 というのは、宇宙が生まれてから滅びるまでに一度あれば奇跡と考えてよいような
数字だよ
0046デフォルトの名無しさん
NGNGこの256はどこから出てきた？
0047self !=35 && self !=45
NGNG多分>>45は>>35へのレスだと思われ。
MD5は16バイト＝16*8ビット＝128ビットなのを>>35のレスに
引きずられて16進32桁＝32*8ビット（本当は*4）=256ビットと
勘違いしたんじゃない？
0048デフォルトの名無しさん
NGNG解説してるとこ無いでしょうか。
0049デフォルトの名無しさん
NGNGページの心当たりはありませんが、かなり昔のLispコンパイラの最適化に
関する記事で見た覚えがあります
0050デフォルトの名無しさん
NGNG再起 除去 あたりのキーワードで検索すれ。
0051デフォルトの名無しさん
NGNG末尾再帰
0052デフォルトの名無しさん
NGNG0053デフォルトの名無しさん
NGNG0054デフォルトの名無しさん
NGNG0055デフォルトの名無しさん
NGNG正１２８角形でもかけや。
0056デフォルトの名無しさん
NGNG{
for (int i = 0; i < 360; i ++) {
double r = i * PI2 / 360;
PSet(x + cos(i) * radius, y + sin(i) * radius);
}
}
0057デフォルトの名無しさん
NGNGツッコミ所満載で、どこにツッコんだら良いのやら･･･
0058デフォルトの名無しさん
NGNG0059デフォルトの名無しさん
NGNGrは半径ね。
円の1/8だけ演算して、あとは鏡像をコピー。
0060デフォルトの名無しさん
NGNGsqrtが重い
0061デフォルトの名無しさん
NGNGターゲットによるでしょ。
SSE2でも平方根は有るんだし。
0062デフォルトの名無しさん
NGNGy=√(r^2-x^2) を微分して y*dy = -x*dy を求めて45°までの略算形式にするのがDDA
他の方法としては、汎用のベジェ描画を作ってベジェ係数に変換してしまうのが一般的で楽かも
といえば、じゃベジェ描画はどうするのか疑問が出るんだろうけど
0063Po
NGNG議題：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方向の再帰関数の呼び出し */
}
こんなんでいいのか？
まあ、はじめの呼び出しをどうやればいいかは宿題だな。
テーブルの初期化を含めて、それも一つの関数にしておくと楽だな。
0064デフォルトの名無しさん
NGNG4方向のやつはこれか
http://game.2ch.net/test/read.cgi/gamedev/1005040025/220
0065デフォルトの名無しさん
NGNGパスを作って枝借りしたほうがいいかも、っつーことで、
A* 調べろに１票
0066デフォルトの名無しさん
NGNG0067デフォルトの名無しさん
NGNG{
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でやってる人にはイイ。
0068デフォルトの名無しさん
NGNG0069デフォルトの名無しさん
NGNGいやーそれは数学の教科書見たほうが早いよ。
0070デフォルトの名無しさん
NGNGここで調べて
http://www.google.co.jp/search?q=%90%FC%95%AA+%8C%F0%8D%B7%94%BB%92%E8
判らなかったら、そこを質問してね
0071デフォルトの名無しさん
NGNG領域を線で選択 のイメージが判らないので答えられないのだと思います
007266
NGNGうう、言葉で説明するの難しい。
0073デフォルトの名無しさん
NGNG007466
NGNG自分で考えたのは一度フリーハンドを描画してから左右1ピクセルずつ
大きくして左上から塗りつぶしを行って反転させる、って方法なんだけど
もうちょっといい方法あるかな、と思って。
0075デフォルトの名無しさん
NGNG0076デフォルトの名無しさん
NGNGのマンデルブロートのパラメータ教えてください。
xmin,xmax,ymin,ymax,maxiterの初期値例が載ってたような気がします。
(いま本が手元にない)
0077デフォルトの名無しさん
NGNGちょっと頼む。
0078デフォルトの名無しさん
NGNGそこら中で公開されとる検索せれ
0079デフォルトの名無しさん
NGNG石が囲まれてるか､囲まれていないかの判定をする
最速のアルゴリズムを教えてください。
0080デフォルトの名無しさん
NGNG石は置いた時にグループ番号を振る。
グループにはダメの数を記録しておく。
置いた時に隣接に同じ色の石があったら、自分も同じグループにする。
隣接に違うグループ番号の石があったら、そのグループの番号も自分の番号にする。
グループのダメの数は、自分のぶんを引き、自分のダメの数を足す。
こうしておくと、囲まれてるかどうかは、グループのダメの数を見ただけでわかる。
0081デフォルトの名無しさん
NGNGMTだ。
７行スレにソースあったぞ
0082デフォルトの名無しさん
NGNG0083デフォルトの名無しさん
NGNGいまさら２分木を勉強してるあなたは何者？
0084デフォルトの名無しさん
NGNGそんなことで得意げになっているあなたは何者？
0085デフォルトの名無しさん
NGNGコンピューター関係の勉強をしていて、ゲームよりも面白い、と最近感じることが多くなりました。
仕事をさぼって勉強している、というのがまた良いんですけどね。
いかにも給料泥棒してるぞーって感じで。
0086デフォルトの名無しさん
NGNG×マンデルブロート
○マンデルブロー
>いかにも給料泥棒してるぞーって感じで。
いや、業務時間内の勉強は必ずしも給料泥棒とはいいきれない
「ライブラリの勉強にはむしろ通常の倍支払っても良い」
なんて書いてある本もあったよ
0088デフォルトの名無しさん
NGNGどちらか買ったほうが（・∀・）ｲｲ？
0089デフォルトの名無しさん
NGNG0090デフォルトの名無しさん
NGNG同意。勉強はサービスなんて言ってたらやってられないよ。
0091デフォルトの名無しさん
NGNGリストが１万件以上必要。
しかし、その場合、ソートに時間がかかるから、あぼーん。
0092デフォルトの名無しさん
NGNGオミー・Ｃ・リオキ法で検索するとよい。
0093デフォルトの名無しさん
NGNGはあ? キーが何かも定義せずにいい加減なこと言ってんなよ！
keyが32bit固定とかの話をしてるのかい?
ソートに時間がかかるってなんだい? sorted treeじゃないの?
二分木検索って二分木探索のこと?
返事しなくていいぞ、スレが汚れるから。
0094デフォルトの名無しさん
NGNG必要になるまで計算しない技法のことを何といいましたっけ？
遅延なんとか？
0095デフォルトの名無しさん
NGNG0096デフォルトの名無しさん
NGNG>>90
いやー実は私はISPのヘルプデスクなんですよ。
本当はTCP/IPとかADSLの勉強をしなきゃいけないんですけどね。
それらってつきつめると、結局Cで書かれてるじゃないですか。
わかんないことあって質問しても、すぐ
「ソース読め」
って言われるしそれでプログラミングの勉強はじめたらこっちの方が面白くなってきちゃったんでもうネットワークなんかどうでもいいです給料泥棒まっしぐら
0097デフォルトの名無しさん
NGNGそれが真剣であるならそれこそネットワークスペシャリストになって、会社にもっと貢献できるだろ。
まぁ、いつまでも二分木やソートやってたら無理だが
009894
NGNG0099シェルソート
NGNGfor(;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;
}
}
}
0100デフォルトの名無しさん
NGNG誰か教えてください
二次元座標系、長方形は回転して斜めになっている場合でも適用できるようなの
0101デフォルトの名無しさん
NGNG0102デフォルトの名無しさん
NGNGいずれかの頂点が他の長方形の域内にあるか、
または二つの長方形の辺が交差しているなら共通の領域が存在する。
0103100
NGNGレスありがと
やっぱり二つ組み合わせないとだめか
0104デフォルトの名無しさん
NGNG辺が交差しているかどうかを調べるだけでよくないっすか？
0105デフォルトの名無しさん
NGNG完全に含まれちゃってる時は?
0106104
NGNG失礼しました。
0107デフォルトの名無しさん
NGNG91の言ってることがよくわかってないな。
0108デフォルトの名無しさん
NGNGいずれかの頂点が他の長方形の域内にあるか、
106は誰やねん。
0109デフォルトの名無しさん
NGNG0110デフォルトの名無しさん
NGNG0111デフォルトの名無しさん
NGNG0112DQN
NGNG0113デフォルトの名無しさん
NGNG0114デフォルトの名無しさん
NGNG座標と大きさを間違えなければ描画できるだろ。
0115デフォルトの名無しさん
NGNGBOOL 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;
}
0116デフォルトの名無しさん
NGNGBOOL 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;
}
先頭文字の限定ソート
0117デフォルトの名無しさん
NGNG0118デフォルトの名無しさん
NGNG最悪
0119デフォルトの名無しさん
NGNG2文字じゃ効果無いでしょ？
もっときっちりソートした奴書いて
0120デフォルトの名無しさん
NGNG数字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は範囲を含んだ表現なので、その必要精度だけのビット数で表現しなおせば
圧縮して表現出来るという理屈
0121デフォルトの名無しさん
NGNGちょっとわからないので、ソース出してください
0122デフォルトの名無しさん
NGNG書いた事は原理であって、
実際のコードは整数演算で 吐き出したMSB分だけ全体を2^N倍しな
がから考える必要があります。
120の説明の例で１０進で考えると
最初に２が選ばれた場合は 0.9=W1<1
となり最初の桁が 9と確定します。
確定すれば１０倍して９を吐き出します。
コードがどうしても必要ですか？
0123デフォルトの名無しさん
NGNGif文の羅列はしたくないんで、ﾋﾞｯﾄ操作でできないでしょうか
0x80->0x01
0x40->0x02
0x20->0x03
0x10->0x04
0x08->0x05
0x04->0x06
0x02->0x07
0x01->0x08
0124デフォルトの名無しさん
NGNGそれぐらいなら、swich() で書けばいいとおもうが...。
0126585
NGNG結局入力をxとして (-1 XOR (x-1) )を２進で表現して1の数を数えたいという事ですよね？
トリッキースレ
http://pc.2ch.net/test/read.cgi/tech/983191866/
にビット数を数えるコードがあります
0127126
NGNGfor(i=1;i<8;i++) if( ( 0x100>>i ) & x ) break;
return i;
みたいな意味？
0128123
NGNGfor(i=0;i<8;i++){
if( ( 0x10>>i ) & x ){
break;
}
}
でできそうな感じがしてきました
0129デフォルトの名無しさん
NGNG気のせいだ。もっとよく >>127 を見ろ。
0130126
NGNG>>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;
0131デフォルトの名無しさん
NGNG算術圧縮は特許だらけだとかここ↓で見た。
http://www.tomozo.ne.jp/yamazaki/download/doc_basic_compression.htm
RangeCoderの方がﾖｻｹﾞ？
0132デフォルトの名無しさん
NGNG0133デフォルトの名無しさん
NGNG本を読んでいると２分探索は
実行回数：long n
計算量：O(log n)
等、いきなりでてきて、何を基にこういう式が求まるのかが
良く分かりません。
分かりやすく説明されている本やサイト、
もしくはどなたか説明できる方がいれば教えてほしいです。
0134デフォルトの名無しさん
NGNG算数とか数学でいいんじゃないかな？
Bサーチだと、
木が平衡な場合の最悪のケースの場合の探索の時間が
logN(底は２だよ）なのはわかるよね？
個人的には
アルゴリズム設計者になるわけではないのなら、
厳密な計算量がわからなくてもいいと思うよ。
0135デフォルトの名無しさん
NGNG0136デフォルトの名無しさん
NGNG＞logN(底は２だよ）なのはわかるよね
とありますが、そのあたりが今一つ分からないんです。
logとか底が２とかがどこからきてるのかが分からないです。
数学の勉強からやり直さないとだめですかね・・・
> 厳密な計算量がわからなくてもいいと思うよ。
性格上、気になって・・・
できればすっきりして勉強進めたいかなと思うので。
0137デフォルトの名無しさん
NGNGlogの意味は分かってるんだよね？
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回。
0138デフォルトの名無しさん
NGNG>>135に書いてあるとおり1回の比較で探索範囲は半分になるのだから
n = 2^x
よって
x = log n
0140デフォルトの名無しさん
NGNGなるほど、良く分かりましたo(^o^)o
はじめはlog nの底がてっきり常用対数の
10かと思ったりして混乱してました。
親切にありがとうございます。
本よりも勉強になりました(^_^;
いやーインターネットって本当に凄いですね。
そして、なによりも、見ず知らずの無知な私に
丁寧にアドバイスしていただいた方々に感謝です。
それでは、また、分からないことがあったら
よろしくお願いいたしますm(_ _)m
0141デフォルトの名無しさん
NGNG>(^_^;
>m(_ _)m
2chで見るとムカツク
0143デフォルトの名無しさん
NGNGアルゴリズムの優劣を比較するときは、定数倍の違いを無視するんだ
よ。
例えば「かけ算を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回」が正しい。
0144143
NGNG> 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)
0145デフォルトの名無しさん
NGNG1000000近くの素数をテストする時間を1000近くの
素数をテストする時間と比べどのくらいと予想するか。
って1000000近くのテストは1000近くのテストの1.5倍ですか？
0146デフォルトの名無しさん
NGNG0147デフォルトの名無しさん
NGNGlog10 1000000 = 6
よって、２倍でいいの？
0148デフォルトの名無しさん
NGNGまあそうだけど、底が10でなくても
(log x 1000000)/(log x 1000) = log 1000 1000000 = 2
だ。(1000や1000000が何進法でもOK。)
0149デフォルトの名無しさん
NGNGまた、分布数えソートよりも逆写像ソートを使った方がいい場面というのはあるのですか？
0150デフォルトの名無しさん
NGNG0151www
NGNG0152デフォルトの名無しさん
NGNG0153デフォルトの名無しさん
NGNG0154デフォルトの名無しさん
NGNGその前にお前が自力でさめがめを作れるかどうかをおしえれ
0155デフォルトの名無しさん
NGNG作れる
0156デフォルトの名無しさん
NGNG二次元座標上に、円と線がある時、この線が円と交わる点(0ヶ所か、1ヶ所か、2ヶ所)
の座標を求めたいのですが、どのようにすれば求められるでしょうか？
数学ｻﾊﾟｰﾘなのですが、一応自分でも考えたのですが詰まってしまいました。
私が足りない頭で必死に考えた方法は、この線を直角三角形の斜辺として考えれば
良いのではないかと思ったのですが、その先が思い付きませんでした
よろしくお願いします。
0157デフォルトの名無しさん
NGNG円の中心とその線までの距離を求めて円の半径と比較
0158156
NGNGレスありがとうございます。
ちょっと質問が分かりづらかったのかもしれません。
交わっている点の数ではなくて、
交わっている座標を知りたいのです。
よろしくお願いします。
0159デフォルトの名無しさん
NGNG普通に線と円の方程式を連立して解いたらいかんの？
0160156
NGNGレスありがとうございます。
「普通に」と言われてしまうと悩むのですが、
そう言われても私には「線と円の方程式を連立して解く」という言葉の意味すら
理解できないのです。
「線 円 連立 方程式」で Googleってみましたが、
それらしいものが見つかりませんでした。
どういう事をすればよいのでしょう？
よろしくお願いします。
0161デフォルトの名無しさん
NGNGいま、線はどうやって表現しているの？2点を通る直線？
0162156
NGNGレスありがとうございます。
はい、２点を通る直線です。
この線と、その延長線上で、円と交わる点の座標を得たいのです。
よろしくお願いします。
0163デフォルトの名無しさん
NGNG2点(Px,Py)(Qx,Qy)を通る直線の方程式は
(Qy-Py)(x-Px)-(Qx-Px)(y-Py)=0となる。
ここまでいいかい？
0164デフォルトの名無しさん
NGNGに代入して
その結果の式
(x-c)^2+(ax+b-d)^2-r^2=0
を公式で解く、というのが王道だと思う。
あとは「円の方程式」とか「二元方程式の公式」とかで適当に検索しる！
0165164
NGNGスマソ、見てなかった・・・
0166163
NGNGいいさ。
0167156
NGNGありがとうございます。
ｻﾊﾟｰﾘ理解できませんが、公式と検索のヒントを教えて頂けたので
後はなんとか自力で頑張って理解したいと思います。
本当にありがとうございました。
0168デフォルトの名無しさん
NGNG2元方程式？
2次方程式じゃないの？
変数がxしかないので1元では？
0170156
NGNG「二元方程式」だけでググルって57件しかないので、
片っ端から見ても……？？？？？？う～ん。
>>168
二次方程式なのでしょうか？
あらゆる二次方程式は解の公式に変形できると書いてあるサイトを見つけたのですが
↑もできるのでしょうか？
>>169
直線を X軸に合わせるというのはどういう事でしょうか？
円の中心を Y軸に合わせるというのはわかるのですが…。
0172164
NGNG鬱だ詩嚢。
あと、164の式中の ax というのは a*x のこと。
^2 はもちろん二乗のこと。
円の方程式は
円の中心の座標が(c,d)で、半径が r のときに164の式になる。
念のため。
>166
ありが㌧！
0173156
NGNG大人ですよ(汗)
学生時代は数学の時間は寝るものだと決めていたので…。
今になって禿しく後悔しています。
実は円じゃなくて四角形で代用できるような問題の気がしてきました。
四角形なら線と線の交わる点だけでいいですね……。
四角形で片づけようかな…。
0174デフォルトの名無しさん
NGNG直線って、ひょっとして水平か垂直な直線だけなのか？
0176デフォルトの名無しさん
NGNGもっと変数減らせるかは知らん。
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
0177デフォルトの名無しさん
NGNG全然違う。
0178156
NGNGありがとうございます。
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
0179156
NGNGこっちです。
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
0180176
NGNGもう自信ない。
k = (a*c + b - d) / (1 + a*a)
D = r*r - k*k
x = (c - a*b + a*d) / (1 + a*a) ± sqrt(D)
0181176
NGNGk = (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)
0182デフォルトの名無しさん
NGNG0183156
NGNGそれらしい値が出てきました！！
結局全部他力本願になってしまいましたが、皆さんのおかげで
なんとかなりそうです。本当にありがとうございます。
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
0184デフォルトの名無しさん
NGNG最小になるように行列積M1M2M3…Mnに括弧をつける問題に対する
アルゴリズムを、コードじゃなくて日本語で説明してください。
0185デフォルトの名無しさん
NGNG0186184
NGNG0187デフォルトの名無しさん
NGNG0188デフォルトの名無しさん
NGNG何の？
トポロジカルソーティングの事か？
0189デフォルトの名無しさん
NGNG辞書順でなくてもいいです。
0190デフォルトの名無しさん
NGNGttp://news.lycos.co.jp/comp/story.html?q=10impressi03&cat=14
0191デフォルトの名無しさん
NGNG正直、とっくに亡くなってると思ってた。。
（だって、「ダイクストラの亡霊」とか言うじゃん。いやうそいわないかも。。）
0192デフォルトの名無しさん
NGNG0193デフォルトの名無しさん
NGNG0194デフォルトの名無しさん
NGNGn文字テキストからm文字キーワードを探す場合、
キーワード末尾の比較を行って、一致しなければ、一気にm文字分比較したのと同じ効果が得られる。
すなわち、最小比較回数が n/m 回になる。そして、実際もかなり小さい。
他の方法（KMPとか）は、必ず n 回比較するので、BM法の方が速い。
0195デフォルトの名無しさん
NGNG定数部分がおっきい感じがする。
って言うか、多バイト文字とかBMで検索するのって
難しそうだし。
0196192
NGNG＞＞n文字テキストからm文字キーワードを探す場合、
＞＞キーワード末尾の比較を行って、一致しなければ、一気にm文字分比較したのと同じ効果が得られる。
まさにそこがわからんのです。
説明しずらいのですが、n文字列の先頭（厳密には先頭でないが）からキーワードの末尾との比較を行い、一致しなかったら次はキーワードの末尾の一個前（後ろから2番目）と
比較を行い、文字が一致すれば一文字文スキップする。一致しなければ、またキーワードの今比較した文字の一個前（キーワードの後ろから3番目）と比較して文字が一致すれば
2文字分スキップする。一致しなければ、同様にキーワードの後ろから4番目と比較する、、、、というふうにキーワードをスキップさせて行くんですよね？
これだと比較の回数はn／m回にはならないのですが、、どうでしょう？
何か私の説明は間違ってますか？
0197デフォルトの名無しさん
NGNG> ＞＞キーワード末尾の比較を行って、一致しなければ、一気にm文字分比較したのと同じ効果が得られる。
> まさにそこがわからんのです。
テキスト側の一致しなかった文字を x としよう。
もし、x がパターン文字列に含まれていなければ、一気に m文字分
スキップできる。これは OK?
もし、x がパターン文字列に含まれているなら、その出現位置によって
スキップできる文字数が決まる。
実際には、マッチングに先立ち、パターン文字列をもとにして、この
「スキップできる文字数」のテーブルを使っておく。
0198デフォルトの名無しさん
NGNG○ 作っておく
0199デフォルトの名無しさん
NGNG表を１つだけつかうならば、定数部分はそんなに大きくないよ。
演算数は、せいぜい2倍。
もちろん、パターンが１文字とか２文字とか、
アルファベットサイズが２とか１０くらいだと、単純法より遅くなるだろうけど。
多バイト文字は、まぁ、wchar_t とかJavaのcharとか、
あるいは自前で (unsigned) short int とか、使ってやってくれぃ。
0200デフォルトの名無しさん
NGNGShiftJIS や EUC とかでも別に難しくはない。
普通にBMでマッチングかけた後、マッチした部分が1バイトずれた
ところでないかどうかをチェックすればよいだけ。
0201192
NGNGレスありがとうございます
>>もし、x がパターン文字列に含まれていなければ、一気に m文字分
>>スキップできる。これは OK?
これは理解できます
しかし
>>もし、x がパターン文字列に含まれているなら、その出現位置によって
>>スキップできる文字数が決まる。
この説明で、出現する位置まで一つ一つ比較を行っているとれば
>>194さんの説明の最小比較回数がn／mになることはありえないと思うのですが、
0202デフォルトの名無しさん
NGNGオーダーで考えればO(n/m+m-1)=O(n/m)だな。
あるいは、見つからなければn/mである。
0203デフォルトの名無しさん
NGNG円周上におかれた、3点の座標から、その円の半径と、中心座標を
求めるプログラムを書きたいのですが・・・。
どっかに、アルゴリズムありませんか？・・（＾＾；
よろしくーです
0204デフォルトの名無しさん
NGNG３点でわかるの？
１２０度ずつの３点なら中心求めれば簡単だけど
０、１、２度の３点ではわからないのでは。
0205デフォルトの名無しさん
NGNG残念ながらその最適アルゴリズムは俺様が特許を持っています。
0206203です
NGNG円の方程式から、連立方程式を立てて、解けばできると思うんですが・・。
やっぱり、ガウスジョルダンとか使わないとだめなのかな・・・
めんどくさいよー
引き続き、ご意見募集
0207デフォルトの名無しさん
NGNG高校数学の問題。「三角形の外心」で調べろ。
>>204, >>205 も中学からやり直し(w
0208デフォルトの名無しさん
NGNG残念ながらその発言方法はボクが特許を取っています。
月末に特許料の請求書を送りますので、間違いなく振り込んで下さい。
0209デフォルトの名無しさん
NGNG３点で解けないのは楕円だけだろ
0210デフォルトの名無しさん
NGNG（ズンチャチャズンチャ）＾ｎ
0211203です
NGNG外心の計算をする場合、２元２次連立方程式、あるいは、３元２次連立方程式の
解をもとめないと、いけないの思うのですが、
プログラム上で、連立方程式を行列で解くのが、手間なので質問してます（－－；
よろしくです。
0212デフォルトの名無しさん
NGNG0213デフォルトの名無しさん
NGNGこのスレの趣旨わかってないだろ
0215203です
NGNGなんか、数学の板に同じ質問をしていた人がいたので、
参考にさせてもらいました。
0216デフォルトの名無しさん
NGNG0217デフォルトの名無しさん
NGNGよかったね。 じゃ回答のあるリンクをひとつのせておくよ
http://www.infoeddy.ne.jp/~tensyo/prog/linealgo.htm
0218デフォルトの名無しさん
NGNG0219デフォルトの名無しさん
NGNG0220デフォルトの名無しさん
NGNG日本語の場合は人工知能のまず開発をお願いします
0221デフォルトの名無しさん
NGNG日本語の場合は茶筅とか案山子使えばいいんでは？
英語の行末ハイフンは連結語のハイフンも兼ねている場合があるので、
単語辞書も持っていたほうがいいね。
0222デフォルトの名無しさん
NGNG細かい文法的なことはあんまりきにしないで
漢字の単語だけ切り分けたい
茶筅 案山子 ってなんですか？
0223デフォルトの名無しさん
NGNG漢字コード決め打ちして、Perl などで正規表現使っても良いと思う。
ChaSen
http://chasen.aist-nara.ac.jp/
Kakasi
http://kakasi.namazu.org/
0224hoge
NGNG三角形の各辺の中点を軸に180度回転させながら、図形を形作ろうと考えてます。
もっと良いアルゴリズムがあったら教えてください。
0225デフォルトの名無しさん
NGNGsageで聞いても皆が見てくれないよ。
とりあえずもっと良いアルゴリズムって言われてもなあ
bitmapをリージョンかけて切り出してそれをまた回転するくらいかなあ
0226デフォルトの名無しさん
NGNGあるいは自前で (unsigned) short int とか、使ってやってくれぃ。
0227デフォルトの名無しさん
NGNGD = r*r/(1 + a*a) - k*k
x = (c - a*b + a*d) / (1 + a*a) ± sqrt(D)
0228デフォルトの名無しさん
NGNGそれぞれにソート済みのn個の実数が入っているとき、これら2n個の実数の
中央値を求める、オーダーがlognのアルゴリズムを探しているんですが、
何か良いアルゴリズムはありますでしょうか？
0229デフォルトの名無しさん
NGNG２分探索木じゃダメなの？
0230デフォルトの名無しさん
NGNG抽象的な割には、やけに汎用性の乏しい問題だな。。。
これが宿題でなく、実際に問題になっているのなら
まず先にデータ構造の方を考え直せ。
0231228
NGNG二分探索木をどのように使えばいいんでしょうか？
空の二分探索木に2n個の数を入れると根の数が中央値になる…なんて性質
ありましたっけ？この操作ならO(logn)で出来ますが…。
0232デフォルトの名無しさん
NGNG木にする必要ないと思うんだが。
0233デフォルトの名無しさん
NGNG0234デフォルトの名無しさん
NGNG二つの配列の値を比較しながら、近づくように走査していくのかな？
このとき、それぞれの総和を求めて行った方が良いのか？とか
二つの配列のそれぞれ両端から色々比較したりするのであれば、
４つ場所を保持しておかなければいけないと思うのだけれど、
その辺もわからない。わからないだらけの第３者です。
0235デフォルトの名無しさん
NGNG中央値を求めるってだけなんで…。
宿題なので実行効率とかそういうのは考えなくていいと思います。
変数や配列などの記憶場所も好きに使って良いと思います。
わざわざ配列が二つあるってことはマージを利用するのかなーとか
いろいろ考えては見てるんですけど…。
0236デフォルトの名無しさん
NGNG0237デフォルトの名無しさん
NGNG値を2個ずつとってきて、
「現在の中央値」「新しい値（１）」「新しい値（２）」
の＜3つの中の中央値＞をとれば、
それが新しい中央値になるじゃないの。
0238237
NGNG0240デフォルトの名無しさん
NGNGおまえしっかりしてください。
0241デフォルトの名無しさん
NGNGhigh1 = 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);
ここに直書き。あってるかどうかまったくわからない。
0242デフォルトの名無しさん
NGNG（ちょっと怪しいけど）こんな感じでは？
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;}
0243デフォルトの名無しさん
NGNG0244デフォルトの名無しさん
NGNG0245デフォルトの名無しさん
NGNG中央値を求めるのではなく、集合を大きい方と小さいほうに二等分する問題と
考えてみる。たとえば
集合Ｘ｛1, 3, 6, 7, 10}
集合Ｙ {2, 4, 5, 8, 9}
としてみる。
まず、集合Ｘを二つに分けると、ある敷居を境に大きいグループと小さい
グループにわかれる。この敷居を動かしていくと考える。まずは真中近辺
からスタート。６と７の間に敷居があるとしよう。
Ｘ｛1, 3, 6 || 7, 10}
Ｘが小さい方に３つ、大きい方に２つに分けたのだから、
Ｙは小さい方に２つ、大きいほうに３つに分けることになる。だから
Ｙ {2, 4 || 5, 8, 9}
となる。このとき、６＞５だから、この分け方は正しくないことがわかる。
＃分け方が正しいか正しくないかを見分けるには、例の場合４＞７、６＜５
＃を確認すればいいので、o(1)で調べられる。
では、この敷居の位置が悪かったことがわかる・・・、あとはバイナリサーチ
よろしく敷居の位置を変えればいい。o(logn)回敷居の位置を変えれば、正しい
分け方が発見できる。そうすれば中央値も求まる。
0246こう？
NGNG#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);
}
0247デフォルトの名無しさん
NGNG0248デフォルトの名無しさん
NGNG４色あれば十分なことが証明されてますが（いわゆる４色定理），
その塗り方を求めるアルゴリズムを教えて下さい．
0249デフォルトの名無しさん
NGNGBrute Force
0250デフォルトの名無しさん
NGNG0251デフォルトの名無しさん
NGNG>平面グラフの頂点を，隣接する頂点を異なる色で塗るとき，
>４色あれば十分なことが証明されてますが
一点から辺が５本以上出ている "頂点" は
４色では塗れませんが、何か？
0252デフォルトの名無しさん
NGNG真ん中を青で塗って、周りの五つを赤、緑、赤、緑、白とすればよい。
0253デフォルトの名無しさん
NGNG日本語をもっとしっかり読め。
>>248
mod4で２足したりとか順にしていけばけっこうできるんじゃ無いの？
0254デフォルトの名無しさん
NGNGつーか、今はどんな手法使っているのよ？
始めは>>249のように力任せでもいいと思うけどな。
頂点数が1000くらいまでなら、最近のコンピュータなら十分速い。
0255248
NGNGそのアルゴリズムを使って別のことをしようとしています．
（具体的に何をしようとしているかはかなりややこしいので書きません）
考えて頂いておいて申し訳ないのですが，時間がかかるかもしれないけど
解けるというような方法は，私の目的には使えそうにりません．
真面目に文献調査をすることにします．
0256プロの逝って良しの１ ◆MvRbZL6NeQ
NGNG再帰探索じゃダメ？
0257デフォルトの名無しさん
NGNG0258デフォルトの名無しさん
NGNGN. 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.
0259hiloshi
NGNG0260デフォルトの名無しさん
NGNG一松信先生の「正多面体を解く」とか読むと良いかも。
三十ﾍﾟｰｼﾞ辺りだけでも。
0261248
NGNG>>258
ご指摘の STOC の論文を入手し読みました．まだ理解できておりませんが，
４色問題の証明に基づくアルゴリズムということで，非常に面倒そうだという
ことだけ分かりました．逆に言うと，単純なアルゴリズムがあれば，４色問題の
単純な証明になる！ということですね．．．
>>260
調べてみます．
0262デフォルトの名無しさん
NGNG0263デフォルトの名無しさん
NGNGわかりません。
0264デフォルトの名無しさん
NGNG0265デフォルトの名無しさん
NGNG0266level 1
NGNG番号の高い物は上に重ねられません。
１
３ １
２３ ２
────
0267level ２
NGNG１３３
１２２１
─────
0268デフォルトの名無しさん
NGNG0269デフォルトの名無しさん
NGNGというのはアルゴリズム論のよくある試験問題かも
0270デフォルトの名無しさん
NGNG右手法
0271デフォルトの名無しさん
NGNGn^2-1
光速で導きだせましたが何か？
0272デフォルトの名無しさん
NGNG立体迷路で通用しません。
0273デフォルトの名無しさん
NGNG0274デフォルトの名無しさん
NGNG平面でも壁の連結成分が2個以上になった時点でｱｳﾄ
0275デフォルトの名無しさん
NGNG交差点で進んだ方向を記録しる。
平面なら最高３回、立体なら最高５回（つーか、分岐数－１回）
0276デフォルトの名無しさん
NGNG0277デフォルトの名無しさん
NGNG0278デフォルトの名無しさん
NGNG袋小路を見つけて、道を埋めていけ。
0279デフォルトの名無しさん
NGNG0280デフォルトの名無しさん
NGNGあるんだけど、すごくリアルなモーションのくせにモーションデータが
小さすぎ。２、３分のデータでなぜか数百バイトとかなんだけど……。
どういうアルゴリズムか少しでも知ってる人いませんか？
0281デフォルトの名無しさん
NGNG0282デフォルトの名無しさん
NGNG一度通った道を壁と考えるのだ。
0283デフォルトの名無しさん
NGNG0284デフォルトの名無しさん
NGNGゴールへの道が塞がっちゃった
0285デフォルトの名無しさん
NGNGttp://cathand.org/etc/patramaze.jpg
http://cathand.org/etc/toromaze.jpg
0286デフォルトの名無しさん
NGNG0287デフォルトの名無しさん
NGNGttp://www.e.yamagata-u.ac.jp/~sakai/HOME_PAGE/H9/Mika/index.html
0288デフォルトの名無しさん
NGNGDQN大学っぽい卒論だと思ったらやはり山形かよ
0289デフォルトの名無しさん
NGNG0290デフォルトの名無しさん
NGNGこれ、卒論なんですか？
0291デフォルトの名無しさん
NGNGドクター請求論文でつ。
0292デフォルトの名無しさん
NGNG0293デフォルトの名無しさん
NGNGおれはこの子の論文どうこうに興味はないが、この子がついている教授がどの程度のもんなのか
見てみたい。
0294デフォルトの名無しさん
NGNGhttp://www.e.yamagata-u.ac.jp/~sakai/HOME_PAGE/Sakai/sakai.html
0295デフォルトの名無しさん
NGNG学外活動
看護管理者（ファーストレベル）研修会
ナースいっぱい・・・ﾊｧﾊｧ
0296デフォルトの名無しさん
NGNG数値を浮動小数化するのは難しくないのですが、
浮動小数同士の足し算掛け算などで詰まってしまいました。
計算方法を解説してるHPなどありませんでしょうか
0297デフォルトの名無しさん
NGNG足し算掛け算に詰まるのに、浮動少数化するのが難しくないとはどういうわけですか?
漏れには信じられん。
0298デフォルトの名無しさん
NGNGただ掛け算はともかくとして、
足し算引き算は指数の離れている同士だとどうしましょうといった感じです
0299デフォルトの名無しさん
NGNG有効数字が被らなければ無視すれば？
0300デフォルトの名無しさん
NGNGそれで失われる情報が「桁落ち」というやつだよ。
しかし、掛け算も結構面倒なはずだがなー
たとえば、仮数どうしをかけた後で、もう一度正規化する必要があるとか…
(1/2*1/2は1/4になっちゃうから。)
0301デフォルトの名無しさん
NGNG色々情報ありがたいことです。さらに調べてみます
0302デフォルトの名無しさん
NGNGそういうときこそ Knuth の本を読むのがよいと思われ
0303デフォルトの名無しさん
NGNG0304デフォルトの名無しさん
NGNG凸型の多角形を前提にしてるものばっかりに思えるんだけど
凹型でも問題なくて、プログラムしやすそうなアルゴリズムって
どんなのがありますか？
あとこの辺りの計算幾何学のオススメの本とかあったら知りたいですけど
こういう本ってやっぱ高いのはしょうがないんですかね？
ちょっと安めでいい本があったら知りたいです。
0305デフォルトの名無しさん
NGNG0306デフォルトの名無しさん
NGNGとりあえずこれは買っとけ。
コンピュータ・ジオメトリ－－計算幾何学：アルゴリズムと応用－－
http://www.kindaikagaku.co.jp/bookdata/ISBN4-7649-0277-X.htm
0307デフォルトの名無しさん
NGNG0308デフォルトの名無しさん
NGNG0309デフォルトの名無しさん
NGNGWinAPIに、BitBltという画像転送があるのですが
主にそのままコピー、or合成, and合成, xor notができます
それらを組み合わせて上手く加算合成とかをつくれないかなと
0310デフォルトの名無しさん
NGNGシフトが無いと 配列として処理するしかないけど
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
この表から論理演算を作ればいい
0311デフォルトの名無しさん
NGNGhttp://www.aya.or.jp/%7Esanami/peace/memorial/code21-30.html
0312デフォルトの名無しさん
NGNG> WinAPIに、BitBltという画像転送があるのですが
下位からの繰り上げの処理が実装しにくいと思うので、Bit数に応じて同等数
以上のBitBltが必要になると思うんだけど、、、
間違っているかもしれないので、突っ込みよろしく。
0313デフォルトの名無しさん
NGNG1ビット出力＊１とキャリー出力）を作ると、
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)
これをビット数だけ繰り返せばよいわけだが。
0314デフォルトの名無しさん
NGNGピクセルごとに処理する方法は別に簡単なのですが、BitBltはハードウェアサポートのおかげで
超高速です。
それこそ100回や200回描画したところでびくともしません
シフトがないので桁あがりが無理そうですね…
0315デフォルトの名無しさん
NGNGじっくり読んで理解するよう勤めます
0316デフォルトの名無しさん
NGNGなるほど、
まず合成する画像の特定bit部分だけとりだすのは、andを使えば簡単ですね。
特定の色で塗りつぶした画像を作り、それとand合成すれば良いわけですから。
加算器の構造に関してもHPと併用して理解できました。
しかしやはり繰り上がりができませんね。
シフトができない以上ここで手詰まりでしょうか。
0317デフォルトの名無しさん
NGNG線分の始終点のどちらかあるいは両方が多角
形内部の場合は交差。
多角形が反時計周りか時計周りか調べておく。
後は、線分と多角形の辺との交差関係を順次
調べて、交点での外積値の比較によって線分
が多角形の内部に入り込んでいるかをチェッ
ク（反時計周りか時計周りかの情報も利用）。
てのはどうでしょう。
0318デフォルトの名無しさん
NGNG> シフトができない以上ここで手詰まりでしょうか。
Bitmapを一次元にするとxを1ビットずらしてクリッピングでOKでは？グラフィッ
クカードに演算させるもは面白そうなので頑張ってね。
0319デフォルトの名無しさん
NGNGでも実際交換回数は、バブルの方がぜんぜん多いんですけど。
0320デフォルトの名無しさん
NGNGRGBデータ部を１バイトずつ読み、シフトして返すのは可能ですが今回の目的にはそぐわないです
RGBデータ部全体を1bitシフトするのは流石に無理な気がします
何故シフト演算合成つくらなかったんだﾏｲｸﾛｿﾌﾄ!!
0321デフォルトの名無しさん
NGNGなんで?
単純なインプリメントだと
選択ソートは(n-1)(n-2)/2回
バブルの場合は(n-1)^2回
だと思う。
バブルソートでも最後に交換のあった位置を覚えておけば減るけどな。
0322デフォルトの名無しさん
NGNG> RGBデータ部を１バイトずつ読み、
2値のBitmapじゃないんだ。じゃ大変そうですな。
0323JPS ◆M0LaMzf5rY
NGNG0324デフォルトの名無しさん
NGNG0325JPS ◆M0LaMzf5rY
NGNGみためは上に向かってるけど、木として考えたら根に向かってるから
ダウンだけど。
0326なるなる ◆QkRJTXcpFI
NGNG我17だ。
そこまで知識を得るのに何歳から勉強してんだ？
たのむおしえて
0327デフォルトの名無しさん
NGNGと言っても本当に簡単なものだけどね
1から作りはじめたのは小学校後半
0から作るようになったのは高校ぐらいだ
17だったら丁度2種とって喜んでた頃だな
0328デフォルトの名無しさん
NGNG韓国人の総会屋に一歩も引かなかったんだけど、
高校生の娘がレイプされて陥落。
ピストルをあそこに突っ込んだ写真を送ってきたらしい。
ネガは返してもらったらしいが親にしたらたまったもんじゃないだろう。
,
帰ってきただけまだましかも・・・・・・。
同じような目にあって、薬漬けにしてパチンコ屋の店長に
ペットとして払い下げられた中学生を知ってます・・・・・・。
http://ex.2ch.net/test/read.cgi/korea/1035676130/
↑ レイプ、拉致、人身売買、バラバラ殺人、カルト、毒殺、暴力など
0329デフォルトの名無しさん
NGNGhttp://bbs3.sekkaku.net/bbs/poohpooh.html
韓国人が集まりそうな掲示板
ここにいって書いて来い
0331デフォルトの名無しさん
NGNG別に総和じゃないけど...
>>325
ふつう根を上に書けば「ダウン」は下へ行くだろ。
まあ、本によって説明の仕方は違うかも知れんが。
根が最小値のとき、ヒープ(priority queueともpartially-ordered tree
とも言う)へ値を挿入するには、葉から根へ向かって適当な場所まで
シフトして行く。最小値を削除するときは、空いた根の位置に、
いちばん端の葉の値をまず入れ、葉に向かってシフトして行く。
0332デフォルトの名無しさん
NGNG適当なアルゴリズムの参考書を購入しる。
最初は分からなくてもいいから、同じものを全部を通して最低１０回は読む。
あら不思議、５回目くらいから書いてあることが頭にどんどん入ってくるYo!
...これ、ちゃんとした学習法でつよ？
0333デフォルトの名無しさん
NGNG> 根が最小値のとき、ヒープ(priority queueともpartially-ordered tree
> とも言う)へ値を挿入するには、葉から根へ向かって適当な場所まで
heapとpriority queueとは同じじゃないよ。priority queueを実装するのに
heapを使うことが良くあるだけ。つまりheapじゃなくてもpriority queueは実
装できる。partially-ordered treeってのはあまり(というかほとんど)耳にし
たことがない。
0334デフォルトの名無しさん
NGNGなんだかんだとそれが一番正しい勉強法だと思う。
私も同じ方法で勉強してましたｗ
どの分野にも言えるけどがむしゃらに手を出すよりは、
ひとつの本を何度も読んで理解した方が早いよね。
その上で、内容がものたりなかったり、どうしてもわかりにくいところがあれば、
別の本に手を出して、また読み返していれば良し。
ちゃんと理解もしていないのにどんどん本を変えると、
かえってわかりにくくなるときもあるよ。
書く人によっては言葉の定義が違ってたり、くせもあるから。
後は、やはり実践かな。
0335デフォルトの名無しさん
NGNGまあそうね。priority queueを実装するのには単にbinary partially-ordered
treeが標準的な手法というだけで、イコールではないね。
partially-ordered treeを聞いたことがないってのは…（笑
「ヒープ｣なんて呼ぶのはヒープソートの時だけだよ。ふつーの
文脈でヒープといったら別の意味だから。
0336デフォルトの名無しさん
NGNG0337デフォルトの名無しさん
NGNGねぇ、マージソートはできたの？
0338デフォルトの名無しさん
NGNGヒープってデータ構造のことだろ。Cormen,Leiserson&Rivestでも読め。
0339デフォルトの名無しさん
NGNGほかのヒープもあるからややこしいの。
ややこしく無いようにpotと呼んどけ。
0340デフォルトの名無しさん
NGNG0341デフォルトの名無しさん
NGNGそりゃまたぜんぜん違う意味っス。
これだから知ったかは…（ｗ
0342デフォルトの名無しさん
NGNGいよいよっすね！
0343デフォルトの名無しさん
NGNGほんとのスペルミスかどうかわかりにくいボケはやめて…
0344デフォルトの名無しさん
NGNG0345デフォルトの名無しさん
NGNG0346デフォルトの名無しさん
NGNGはいはい。わかったわかった。
ageずにおれないほど悔しかったのね、ボクチャン？
0347デフォルトの名無しさん
NGNGえまともに勉強してないのがバレバレなのに。
0348デフォルトの名無しさん
NGNGはいはい。ゼミで読んでうれしかったのね。
じゃ、君はPOTの替わりにずっとヒープと言ってなさい。
ちなみに俺のゼミではAho, Hopcroft, Ullmanだったよ。
0349デフォルトの名無しさん
NGNG0350デフォルトの名無しさん
NGNG> ちなみに俺のゼミではAho, Hopcroft, Ullmanだったよ。
まだそんなひどいの使ってるのか…だいたいゼミってなんだよ。学部2年で終
わらせとくもんだろう、アルゴリズムの単位なんて…日本の大学ってやっぱレ
ベル低いな。
0351デフォルトの名無しさん
NGNGいや、18年前の話なんだが…
ま、いずれにせよ「ヒープ」といったらデータ構造のほかに
動的メモリ割り当てのための領域のことを指すことも多いから、
よりspecificにpartially-ordered-treeと言った方が安全。
0352デフォルトの名無しさん
NGNG0353デフォルトの名無しさん
NGNGフーン…
別にたいした人じゃないのね。
0354デフォルトの名無しさん
NGNG> >>350
> いや、18年前の話なんだが…
で、それっきり研究の進展を勉強してない、と。ひとりで通用しない
partially-ordered-treeって言い続けてろや。
0355デフォルトの名無しさん
NGNG> 別にたいした人じゃないのね。
そのとおり。こんな時にこんなところで書きこんでるあなたさまと比べたら。
0356デフォルトの名無しさん
NGNGたしかにそっちのheapの方がよく使うよね。
0357デフォルトの名無しさん
NGNG（フﾟ
partially-ordered-treeと言われると理解できないらしい。
0358デフォルトの名無しさん
NGNGまあ、あんたは「メモリ領域じゃないほうのヒープ」と言いつづけてろや（ｗ
0359デフォルトの名無しさん
NGNG0360デフォルトの名無しさん
NGNG0361デフォルトの名無しさん
NGNG0362デフォルトの名無しさん
NGNG禿同
なにをこんな朝早くから議論してるかと思えば、アルゴリズムじゃなくて名前に
ついてかい…
0363デフォルトの名無しさん
NGNG> CLR程度の初級教科書を読んで「研究」（禿藁
CLRさえ読んでないのか。タイトルだけで入門書だと思ってる。
0364デフォルトの名無しさん
NGNGなにやら知らんが必死だな（藁
漏れはCormen, Leiserson, Rivest and Steinなら読んだが、
あれを読むと何か研究したことになるんか？
0365デフォルトの名無しさん
NGNG0366デフォルトの名無しさん
NGNG0367デフォルトの名無しさん
NGNG入門でいいならここでいいと思う。
ttp://kyu.pobox.ne.jp/softcomputing/ga/
0368デフォルトの名無しさん
NGNGサンクス
でも何か具体例がないから難しいですね
0369デフォルトの名無しさん
NGNG具体例は分かりづらいかと思われるが>287にある。
0370デフォルトの名無しさん
NGNG考察、結論のない論文、初めて見た
0371デフォルトの名無しさん
NGNG・全てのファイル名はユニークで、一つのディレクトリ内に集めれている
・あるファイルと、中身の文字列が全く一緒であるファイルが最大20個程度
ある可能性があります(内容ダブっているってこと。)
これらのファイルを、内容が重複するものを削除したいのです。
更に、A⊃B となるような(Aは、Bの内容になんらかの文字列を追加したもの)
ファイルもあるので、Bも無駄なので削除してしまいたいのです。
最速、いやせめて実用的な方法ってどうやればいいんでしょう。。
0372デフォルトの名無しさん
NGNG0373デフォルトの名無しさん
NGNGこれをDisAsm32に架ける
http://henachoko.homeip.net/uploader/updata/20021124044847.zip
0374デフォルトの名無しさん
NGNG比較時にA⊇Bであるようなペアを記憶しておく。
上の前提条件を改めれば劇的に速くなるだろうけど。
たとえばデータ構造やらファイルの命名規則やら
ファイル作成時にチェック入れるとか。
0375371
NGNG1) ディレクトリのエントリからなるリストの上から順に
次のファイルとdiffで比較→同じなら削除
→違うなら更に次のファイルとdiff..(以下略
この馬鹿げた方法では、10時間経っても終わりませんでした(藁
少しは無い頭使ったところ、以下のようになりました。
2) ディレクトリエントリのリストを使うのは一緒ですが、初めに
サイズ順にソートしておきました。ファイルサイズが一緒の
場合のみ、実際にdiffで比較。ファイルサイズが異なるファイル
に出会ったら、中身の文字列が完全に一致しないのは明らかなの
でスキップ。次以降のファイルも、サイズが違うのは明らかなの
で同様にスキップ。次のループへ...
これでやると、3分で終わりました。
しかし、A⊃Bの場合にBを削除する要求にはノータッチなのです。
なやんでるところ。
0376デフォルトの名無しさん
NGNG>>373で終わったな。終了
0377374
NGNG0378デフォルトの名無しさん
NGNG0379371
NGNG>>372
効率よい＆＆実装できそう な方法を使っても、それでも遅かったら
そうしてみようと思います。
>>373
早速、今日試してみます。出勤なので・・
>>374
その方法で検討中ｗちょっと楽しみ。
そもそもの背景が、3交代シフト勤務の現場で、勤務交代するときに
生成される引継ぎファイルの内容を全文検索可能にしようという企画です。
1件の引継ぎ項目ごとにファイルに分割し、それにユニークな名前を
つけて一箇所に集めているのです。
個々の引継ぎ事項ってのは全員に行き渡るまで消去されないので、
複数日の引継ぎファイルに残る → 結果、重複する内容がある
データ構造かぁ。。問題ありあり、というかマークアップもなにも
ない、プレーンテキストだからなぁ。
0380371
NGNGしまつた！この仕組みは、Linuxで動いてます・・
0381デフォルトの名無しさん
NGNGcreate table hikitugi (
hikitugi_cd char(10),
author_cd char(10),
naiyo varchar2(4000)
insert_date date,
);
SELECT * FROM HIKITUGI WHERE NAIYO LIKE '%もうね%'
0382デフォルトの名無しさん
NGNG112020343440474059510510606136
という結果を得たとき、これを復号化する際
～106
を10番目の語句＋6ではなく、1番目の語句＋0+6番目の語句＋…と解釈すると
1122333344445551203316612334となります。
辞書の番号が一桁なのか二桁なのかどう区別したらいいのでしょうか？
0383デフォルトの名無しさん
NGNGdef 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
0385383
NGNGのマチガイ。逝ってきます…
0386デフォルトの名無しさん
NGNG何故十進数で符号化するのか分からないんだけど・・・
固定長でも可変長でもいいから別の符号化法使うか、
そういうのがダメ（っていうのは無いと思うけど）ならセパレータを使ったら？
0388383
NGNGsortじゃなくて
sort!ですた。
0389デフォルトの名無しさん
NGNG論文ではなく、研究発表用の資料だろう。発表は短時間で概要を説明するのが
主眼だから、細かい証明や考察なんかはザックリ落とす。
0390デフォルトの名無しさん
NGNG0391デフォルトの名無しさん
NGNG宿題？
直接的にはシステムの応答特性を見たり
畳み込みを高速に処理したり、
それを応用して多倍長掛算を高速化したり
0392デフォルトの名無しさん
NGNGあと、lossyなデータ圧縮にも使う。
0393デフォルトの名無しさん
NGNGそれはコサイン変換では？
0394デフォルトの名無しさん
NGNGDCTもFFTも似たようなもんでしょ。
0395デフォルトの名無しさん
NGNG0396デフォルトの名無しさん
NGNG0397デフォルトの名無しさん
NGNG例えば？
DCTをFFTで実現するのは普通にあると思うけど
0398デフォルトの名無しさん
NGNGふーん、よくわからんからやっぱいいです
0399デフォルトの名無しさん
NGNGDragon Cuest Ten
Final Fantasy Ten
合併だってな・・・
0400デフォルトの名無しさん
NGNGそれとも Final Quest になるのかな？
0401デフォルトの名無しさん
NGNG＞DCTをFFTで実現するのは普通にあると思うけど
そしたら、それは「FFTを使ったデータ圧縮」といって良いんとちゃうんかと…
0402デフォルトの名無しさん
NGNG波形をコピーして、位相をずらしたFFTの特殊系をDCTと呼ぶのでつ。
その変形方法によってDCT I,II,III,IV の4種類がありまつ。
JPEGなどで使われているのはDCT-IIでつ。
0403デフォルトの名無しさん
NGNG0404デフォルトの名無しさん
NGNGまぁ普通のFFTが普通はlossyで、無歪みのFFTは特殊なFFTです。
0405デフォルトの名無しさん
NGNG頂点数ｎの完全２分木の高さがlog nであることを証明しなければならないのですが、わかりません。
どうやって証明すればいいのですか？
教えてください。お願いします。
0406デフォルトの名無しさん
NGNG0407594
NGNG0408デフォルトの名無しさん
NGNG> 頂点数ｎの完全２分木の高さがlog n
高さ k の完全二分木に含まれる頂点数が 2^k - 1 ってのは証明できたか？
帰納法を使うなり何なりして導け。
あとは n = 2^k - 1 とおいて k について解けば良い。
0409405
NGNG高さがnのときって頂点数は2^k-1って証明できたんですが、2^kでいいんですか？
>408
2^k - 1 ってのは証明できました。
でも、n = 2^k - 1 じゃなくてlog n は、n = 2^k じゃないとでないんですが。
0410デフォルトの名無しさん
NGNG0411デフォルトの名無しさん
NGNG> でも、n = 2^k - 1 じゃなくてlog n は、n = 2^k じゃないとでないんですが。
O(log n) だろ？ 定数項は捨てられるやん
0412デフォルトの名無しさん
NGNG質問
統計です。データがN個あり、データの値で累積度数分布を作ります。
一応は正規分布するもの（分布のイメージね）、とでも思って下さい。
このときのX％値を素早く求めるアルゴリズムを教えて下さい。
今は、単にソートして、例えば100個（ほんとは101個）あるとすると、
5％なら5個目を選んでます。
0413405
NGNGあがとうございます。分かりました。
まだ勉強が始まったばかりなんで、また来るかもしれませんがそのときはお願いします。
0414デフォルトの名無しさん
NGNGその5%を密度関数に代入して出てくる値をインデックスにすればいいのでは？
0415デフォルトの名無しさん
NGNG0416デフォルトの名無しさん
NGNGそれでいいんじゃないの？
「ソートして、順位がx%になるデータの値を求める。」でOKだろ。
累積度数分布表ができれば、ソートはおわったも同然
（累積度数分布表は「値nから順位への表」とみなせるので）
だから。
>>414
実際のデータから密度関数をどうやって求める？
また、そこから求めた百分位点が、実際の標本の百分位とあってる
確率は低いと思うが。
0417デフォルトの名無しさん
NGNG平均と標準偏差だけ求めて，後は標準正規分布表見てやるのかなあ．Nが大きくなきゃ別にそれでもいいと思うけど．
0418デフォルトの名無しさん
NGNG標準偏差ってなんですか？
0419デフォルトの名無しさん
NGNGなんで>>416じゃだめなのさ？
度数ソートならO(N)時間で（つまり平均や標準偏差の計算と同じオーダーで）
できるんだよ？
0420412
NGNGう～ん、それしかありませんか、やっぱし。
今作っているのが、実は一組当たり3万～4万個のデータがあって、
その一組ごとに％値を求め、それをいっぺんに数百回やらないと
いけないんです。これが結構時間がかかるので・・・
注）416さんの仰るとおり、％値は標本値と一致しないといけません。
0421デフォルトの名無しさん
NGNGだあか～ら～。
どうせ累積度数分布表つくってるんなら、それでソートが終わったも同然でしょ
ってば。つまり、それ以上は速くなりようがないんでしょ？
まさかqsortとか使ってるんじゃないでしょうね。
0422412
NGNGなんか誤解されてしまったようですね。わかりにくい質問ですみません。
質問の意図は「X％値を求めること」であって、累積度数分布は実際に
は作ってません。「累積度数分布のX％値を求める」です。
ん？度数分布表作った方が速いの？
0423デフォルトの名無しさん
NGNGそれなら完全ソートしなくてもよいので、
よほど変なことをしない限りO(n)で求まると思います。
0424デフォルトの名無しさん
NGNGまずソートについて。
累積度数分布表が作れるようなデータ（つまり、０～１００とかみたいに、
値の範囲が限られた整数になるデータ）では、累積度数分布表を作ってソート
するのがもっとも高速です。O(N)時間でソートできます。「度数ソート」
「分布数えソート」等で検索してください。
x%点について。累積度数がx%を超えるまで累積度数を計算し、その順位にある
データを見つければよいわけですが、
・度数分布…N回ループ
・累積度数…(xN/100)回ループ
・その順位のデータを見つける…(N/2)回ループ
で、まあ、何割か早くなるでしょうが、「度数ソートしてX番目」と
オーダーとしてはおんなじです。
0425412
NGNG分布数えソートがあるというのは知りませんでしたが、
昔考えたことはありました。値の範囲を決めないといけないので
汎用ルーチン化は難しいと思って、放棄。
うーむ、頭が固いのはだめですねぇ。クイックソートが一番速い
と思いこんでましたから。
結果、めちゃくちゃ速くなりました。ありがとうございました。
0426デフォルトの名無しさん
NGNGひとつ賢くなれたよありがとう！
0427デフォルトの名無しさん
NGNG0428426
NGNGごめん 分布数えソート のタイプミスです。
0429_
NGNGただ挿入とか削除が遅いと。でもプログラム中ってアクセスのほうが多いから
時々挿入とか削除が起こるくらいならvectorの方がいいのでしょうか?
0430デフォルトの名無しさん
NGNG0431デフォルトの名無しさん
NGNGベンチマークを取ってみたら？
0432デフォルトの名無しさん
NGNG> でもプログラム中ってアクセスのほうが多いから
プログラムによる。
あと list は node 単位でメモリを確保・解放するのに対して、vector は
一括してメモリを処理するから、iterator を長時間に渡って保持してお
きたい場合には list の方が良い。
0433デフォルトの名無しさん
NGNG＼＿＿＿＿ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／
／||ミ Ｖ
＿／ ::::||＿＿＿＿_
[ ／ . :::::::||＿＿＿＿ ]
|:::::::::::::::|| ||
|:::::::::::::::||│ ／ ||
|:::::::::::::::||￣＼ ｶﾞﾁｬｯ
|:::::::::::::::||ﾟ ∀ﾟ）─ ||
|:::::::::::::::||＿／ ||
|:::::::::::::::||│ ＼ ||
|::::::: C=||∧ ∧∩ ||
|:::::::::::::::|| ﾟ∀ﾟ）/. ||
|:::::::::::::::||∧ ∧∩ ||
|:::::::::::::::|| ﾟ∀ﾟ）/. ||
|:::::::::::::::|| 〈. ||
|:::::::::::::::||,,／＼」. ||
[＼ . :::::::||￣￣￣￣ ]
￣＼ ::::||￣￣￣￣￣
＼||
0434デフォルトの名無しさん
NGNGFFTなら、2のべき乗になるようにダミーのデータを足せ。
0435デフォルトの名無しさん
NGNGttp://momonga.t.u-tokyo.ac.jp/~ooura/fftman/ftmn1_3.html
これで判らないなら
http://www.google.co.jp/search?q=Winograd+FFT
0436デフォルトの名無しさん
NGNG0437デフォルトの名無しさん
NGNG座標はｘ、ｙを任意に与えられるものとします。格子状とは限りません。
（格子状ですらわからないｱﾌｫですので、格子状でもいいですが）
0438デフォルトの名無しさん
NGNGx, yが任意に与えられるだけだったら等高線なんか描けないが。
それともその等高線は同一高度に限られてて画面に一本だけか?
0439デフォルトの名無しさん
NGNG失礼。測点のｘ、ｙ座標というべきでしたかね。当然、その位置の
高度（ｚ座標）は与えられます。
0440デフォルトの名無しさん
NGNGダミーのデータを足すってことは、ある画像に対して例えば200＊200Pixelならば
縦横56ずつ、何かの画像をプラスして256*256にするって事ですか？
そのとき足すデータはどういうものが良いのですか？
0441デフォルトの名無しさん
NGNG手順１、 与えられた座標点間を補間した関数 F(x,y) を求める
補間は色々。フーリエ変換とかスプラインとか
手順２、F(x,y)-C=0 を解く
数式上解けないならニュートン法を使う
0442デフォルトの名無しさん
NGNGあかん、素人にはようわからん。それなりに難しいのかなぁ、やぱし。
（フーリエ変換とかスプラインとか、知ってはおるが結びつかん）
本とかURLとか紹介して下さる人いないですか？
できれば、その逆に等高線図から（スキャンして）任意のX,Y点の高度とかも
求められたらなぁ、などとｱﾌｫが壮大な夢を見ているのだが。
0443デフォルトの名無しさん
NGNGまずグリッド生成。これは三角格子が楽だと思う。
なるべく正三角形に近い三角形になるように、点を結んでいく。
次に、等高線をどの高度についてどれくらいの間隔で引くか決める。
すべての三角形の辺について、等高線が辺と交わる（辺の両端が、
片方は等高線より高く、他方は低い）なら、直線補間で交点を決める。
等高線は、
・三角形の１つの頂点だけを通る。
・三角形の１辺から入り、別の辺から出る。
・三角形の頂点から入り、対辺から出る。
のいずれか。
こうしてできた等高線の点の連なりを結んでいく。
その時にスプライン補間などを使ってなめらかな曲線にする。
0444デフォルトの名無しさん
NGNG等高線書いてくれるソフト使った方が早いと思うなー
Mathematicaとか、gnuplotとか。
0445デフォルトの名無しさん
NGNGサンクス。
で、グリッドに測点を持ってこいってことですか？
・・・・とまれ、なんか分かりそうでわからんような、難しそうですな、なかなか。
>>444
てか、ああいうのがどうやっているのかを知りたいんでね。多くのソフトが
コンター図作れているわけで、何かセオリーみたいなのがあるのかなぁ、
と思った次第。ナントカ法によるコンター図とか。
0446デフォルトの名無しさん
NGNG200点なら まず素因数分解してみろ
200 = 2^3*5^2
な？ FFTが使えるだろ？
0447デフォルトの名無しさん
NGNG443さんの案を元にして、グリッド生成の代わりにドロネー図を使うってのも
良さそうな気がします。
http://www.sra.co.jp/people/aoki/Voronoi2dDiagram/
0448デフォルトの名無しさん
NGNG幾何的に等高線を生成するのはかなり面倒くさい。
任意展の高度を求めるのは近傍の測点から補完して高度を求めればよい。ので簡単だ。
等高線図にしても描くだけなら画面上の点すべてについて高度を求めて等高線の高度なら点を打てばよい。
0449デフォルトの名無しさん
NGNG( ﾟдﾟ)ﾎﾟｶｰﾝってな感じでした。ｱﾌｫですのですみません。せっかくご紹介
いただいたのでそのアドレスはお気に入りに入れときます。
>>448
>等高線図にしても描くだけなら画面上の点すべてについて高度を求めて等高線の高度なら点を打てばよい。
無茶いわないで下さい。実は測点の高度というのは、実際には「高度」ではなく
計算値（これが結構時間がかかるのです）なのです。従って、それではほぼ永遠
に終わりません。手で書いた方が速い（ｗ
0450デフォルトの名無しさん
NGNG>
> 無茶いわないで下さい。実は測点の高度というのは、実際には「高度」ではなく
> 計算値（これが結構時間がかかるのです）なのです。従って、それではほぼ永遠
> に終わりません。手で書いた方が速い（ｗ
等高線ってもしかして地形じゃなくてシミュレーションかなんかの可視化なのか?
そんな前提はしとらん。
本当の高度を求めるのは適当に決めた測点だけにして、その他の点は測点の値から補完すれ。
0451441
NGNG正方格子 つまり等間隔なら簡単
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をやった方が簡単かもね
0452デフォルトの名無しさん
NGNG問題はどの点同士をつないで三角形を作るか、なんだろうな。
0453452
NGNGその後、ドロネー三角形を作ってるのか。
２ステップ踏まなきゃ三角形で埋め尽くした図は作れないんだな。
ボロノイ図（蜂の巣の方）の作り方はこんな感じかな。
１）点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とか）の情報をもとに
重複を避けながら登録していく。
0454452 ２重カキコチェックうぜえ
NGNGドロネー三角形の図になるそうだが、
幸い、上のルーチン中では使用した3つの点の情報を既に記録してある。
だから三角形を作るには、この3点を使えば良いわけだ。
等高線は各ボロノイ点ごとに（それの作る三角形ごとに）処理していけばよさそうだね。
0455デフォルトの名無しさん
NGNG> 問題はどの点同士をつないで三角形を作るか、なんだろうな。
それをメッシュ生成と呼ぶ。
なかなか難しい問題で、まだいろいろと研究されている。
0456452
NGNG三角形を作る段で3点の情報（A, i, jとか）は必要になるんだが。
別な話だが、中学生の頃、気象図（等圧線）を作る宿題が全然できなかった。
（手順なんかは一切教わらず地図と各点での気圧のデータを渡されただけ）
出来た人（他のクラス）のを見た時は「なんだ、こんなの簡単じゃん」とか思ったんだが
実際やり始めたらどこから手をつけていいかさっぱり分からず
何本か線が引けただけで、どーにもならなかったな。
0457デフォルトの名無しさん
NGNG0458デフォルトの名無しさん
NGNG＼＿＿＿＿ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／
／||ミ Ｖ
＿／ ::::||＿＿＿＿_
[ ／ . :::::::||＿＿＿＿ ]
|:::::::::::::::|| ||
|:::::::::::::::||│ ／ ||
|:::::::::::::::||￣＼ ｶﾞﾁｬｯ
|:::::::::::::::||ﾟ ∀ﾟ）─ ||
|:::::::::::::::||＿／ ||
|:::::::::::::::||│ ＼ ||
|::::::: C=||∧ ∧∩ ||
|:::::::::::::::|| ﾟ∀ﾟ）/. ||
|:::::::::::::::||∧ ∧∩ ||
|:::::::::::::::|| ﾟ∀ﾟ）/. ||
|:::::::::::::::|| 〈. ||
|:::::::::::::::||,,／＼」. ||
[＼ . :::::::||￣￣￣￣ ]
￣＼ ::::||￣￣￣￣￣
＼||
0459447
NGNG> ２ステップ踏まなきゃ三角形で埋め尽くした図は作れないんだな。
そんなことないですよ。ボロノイ図を書かなくてもドロネー図を生成できます。
英語ですが、解説ページ見つけました。サンプルも色々そろってます。
http://astronomy.swin.edu.au/~pbourke/terrain/triangulate/
0460453
NGNGあ、なるほど、これが>>447のページで言われている
『母点を一つずつ付け加えていく逐次添加法(incremental insertion method)』
になるわけですか。
>>453のやり方だとnの4乗のオーダーの計算時間がかかりそうですから
こっちの方が全然速そうですね。
=== >>459のページの内容 ===
アルゴリズムの概要は
既に存在する三角メッシュに点を1つずつ加えてメッシュを更新していく。
処理の最初には全ての点を内包する任意のスーパートライアングルを1つ作成する。
これに1点ずつ母点を加えていってメッシュを更新し、処理が終わったら
スーパートライアングル自身と、それと辺を共有する三角形を削除する。
点を付け加えていくプロセスは
Figure 2a.の様に、メッシュと新しい母点があった場合、
・新しい母点を内包する外接円を持つ三角形を全て選びだす。（Figure 2b.）
・それらの三角形をつなぎ合わせると母点を内包する多角形ができる。
・多角形内の三角形を削除し、多角形の辺と母点を結んで新しい三角形を作る。（Figure 2c.）
0461デフォルトの名無しさん
NGNG展開するのに速いアルゴリズムってあります？
今は
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*高さ分やってるんだけど
べたすぎて、他にいい方法がないものかと
0462デフォルトの名無しさん
NGNG0463デフォルトの名無しさん
NGNGy += vy;
0464デフォルトの名無しさん
NGNGvy += ay;
y += vy;
0465デフォルトの名無しさん
NGNG0466デフォルトの名無しさん
NGNGhttp://save.k.u-tokyo.ac.jp/~mimura/ja/study/method/q_newton/node4.html
を見ました。
ここで、使われているx(k+1)は現在のxの値で
x(k)が一つ前のxの値ということでいいのでしょうか？
0467デフォルトの名無しさん
NGNGRSA暗号をCで作りたいのですが、150桁くらの素数が必要になります
10,000,000くらいまでの素数表ならネットに転がっていたのですが、
到底安全と思える桁数ではありません。
何か大きめな素数を手に入れる方法はありませんでしょうか
0468デフォルトの名無しさん
NGNG0469デフォルトの名無しさん
NGNG0470デフォルトの名無しさん
NGNG0471デフォルトの名無しさん
NGNGっていわれたのだけれど。そんなことできるの？
0472468
NGNG0473デフォルトの名無しさん
NGNGA* って基本的には「全探索」のアルゴリズムだから、できるんじゃない。
0474デフォルトの名無しさん
NGNG形式的な検証方法があるのかな？
フリーソフト／オープンソースでも、ネットワークでプログラムを
ばら撒いただけで特許権侵害になるんでしょ？
果てしない禅問答に巻き込まれる様な気がする…。
0475デフォルトの名無しさん
NGNG0476デフォルトの名無しさん
NGNG特許権の及ばない国で公開する。
時間設定が間違っているサーバで公開する。
0477デフォルトの名無しさん
NGNGすべてが収まるような長方形の最小サイズを求めたいのです。
調べてみたところこれはNP完全問題で、局所最適解を求める
しかないようなのですが、なにかいいアルゴリズムをご存じのかた
いらっしゃらないでしょうか？
0478デフォルトの名無しさん
NGNGどうか教えて下さい。
0479デフォルトの名無しさん
NGNG良いアルゴリズムといっても評価の基準は様々だけど、何を重視してるの？
0480デフォルトの名無しさん
NGNGもろにナップサック問題だね。厳密解を求める良いアルゴリズムは無い。
確率的アルゴリズムや、近似解を求める発見的手法ならあるかも。
>>479
計算論で「良いアルゴリズム」と言ったらクラスPに属するアルゴリズムを言う。
0481477
NGNGご回答ありがとうございます。
速度重視で探索したいと考えています。
それほど厳密な解は必要ないんです。
>480
ご回答ありがとうございます。
調査したんですが、どうも近似解を求める
方法はみつかりませんでした。
確率的アルゴリズムというのはGAとかの
ことでしょうか？
0482デフォルトの名無しさん
NGNG> 計算論で「良いアルゴリズム」と言ったらクラスPに属するアルゴリズムを言う。
近似解を求めるアルゴリズムにしても基準が色々あるだろ、という話だと思うが。
最適解の定数倍オーダーの答えを出すが計算量 O(n^3) のアルゴリズムと、
最適解の二乗のオーダーの答えを出すが計算量 O(n^2) のアルゴリズムが
ある場合、どちらが良いかは用途による。
0483デフォルトの名無しさん
NGNG質問者は誤解して使っているのかも知れんが「良いアルゴリズム｣というのは
定義ずみの用語であり、その定義は「多項式オーダー｣ということ。
0484デフォルトの名無しさん
NGNGGAは確かに近似アルゴリズムとして動作するが、
うまく動くようにプログラムする技術が確立していない。
問題の種類によって異なるが、GAのほかに、
シミュレーティッドアニーリングとか、シミュレーティッドエボリューション、
などを検証するとよろし。
0485デフォルトの名無しさん
NGNGどんな物がありますか？
名前で検索しようと思ったのですが、
黄金分割法しか知らないのでできませんでした。
よかったら、極小探査アルゴリズムの名前を教えてください。
0486デフォルトの名無しさん
NGNGとりあえず「最小値問題」 でｸﾞｸﾞﾚば？
0487デフォルトの名無しさん
NGNG解く時に、どう言った遺伝子にコーディングすればいいか悩んでます。
例えば話を簡単にするために、ABCDの４グループに分類する場合、n個の
配列を遺伝子として表現すると、同じグループ分けのことなる遺伝子表現
が出来てしまいます。これは、あまり収束が良くなさそうなのでアイディア
なんかないですか？
例）同じグループ分けなのに異なる遺伝子になってしまう例
AABBBADDCCABBC
BBCCCBAADDBCCD
0488デフォルトの名無しさん
NGNG0489デフォルトの名無しさん
NGNG0490な
NGNGこんな感じで遺伝子を変換してはどうでしょう。
'言語は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
あんまりいい方法じゃないかも。
場合によっては、変換のコストが無視できないほど掛かりそうですし。
0492デフォルトの名無しさん
NGNG例を挙げると、たかだか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だから遅いの？
0493デフォルトの名無しさん
NGNGアルゴリズムというか、使ってる API が悪いんだと思うが。
VB は知らんが、Win32 API だとピクセル単位で画像データを処理するのは
SetPixel(), GetPixel() という API だが、これは GDI 汎用に作られてるために
ムチャクチャ遅い。
画像処理をやる場合には、ふつうは CreateDIBSection + BitBlt を使う。あと
画像反転程度なら、自前でコード組むまでもなく BitBlt の引数で指定できる
ぞ。
（続きは Win32 関係のスレに行った方が、詳しい人間が見つかると思われ）
0494デフォルトの名無しさん
NGNGありがとう
やっぱアルゴリズムどうこうではないようですね
そっちのスレで聞いてみます
0495デフォルトの名無しさん
NGNGあったらぜひ紹介して下さい。
0496デフォルトの名無しさん
NGNGアルゴリズムは手段であり、目的があってこそ発明され利用されるものだろ？
何を目的にするのかわからないのに、アルゴリズムを紹介できるか。
0497デフォルトの名無しさん
NGNG○ABS
○ビット単位ストア
○条件付交換
○２のベキ乗かどうか
0498デフォルトの名無しさん
NGNG○除算を使わずに剰余を求める
0499デフォルトの名無しさん
NGNG○条件付交換
○奇偶判定
○除算を使わずに剰余を求める
横レスだがどんな処理してるの？
奇遇判定は最下位ビットを見てるのかなとおもったんだけど
0500デフォルトの名無しさん
NGNGとりあえず用途は限定していませんでした。
>>497-498
ありがとうございます、参考になりました。
0501デフォルトの名無しさん
NGNGtmp変数を使わず実装することはできますか？
0502デフォルトの名無しさん
NGNG0503デフォルトの名無しさん
NGNGXOR や + - を使うやりかたの事？
トリッキーなコード その２ の前スレに詳しいよ。
http://pc3.2ch.net/test/read.cgi/tech/1038215563/
0504デフォルトの名無しさん
NGNGmain(){
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;
}
0507デフォルトの名無しさん
NGNGおいおい。少なくとも>>496のいうことは>>501の質問だけを見ると半分正しいと思うが。
俺は>>497-498の回答を有用とは思っていないからね。
つうか、レス間違い？>>501の質問は目的がはっきりしているだろうに。
0509デフォルトの名無しさん
NGNG歴史と同じ。>>496は歴史を学ぶことは不可能だと言うのか？
0510デフォルトの名無しさん
NGNG吐き気がする。
0511おしえてください。
NGNGとあるボードをRT-Linuxで利用したいのですが、付属のドライバでうまく
使えなかったので、ボードに直接アクセスして利用しようと考えています。
幸い、ドライバのソースを手に入れることができたので、何とか理解して必要な部分を
利用ようとしているんですが、ソースの中のioremap( )が良くわかりません。
引数が2つ在るんですが、それぞれ何と何を表しているのかご存知の方折られませんか？
0512デフォルトの名無しさん
NGNGうちんところでは、iomapのベースアドレスと、サイズのように思えるが。
0514デフォルトの名無しさん
NGNG0515511
NGNG0516デフォルトの名無しさん
NGNG0517デフォルトの名無しさん
NGNG/usr/src/linux/Documentation/IO-mapping.txt
に説明があった。
0518IP記録実験
NGNGhttp://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を提出することがある。
0519デフォルトの名無しさん
NGNGオマンコなんて書いたら捕まっちゃうかな（；´Д｀）ｺﾜﾋｺﾜﾋ
0520デフォルトの名無しさん
NGNGあっ？やんのかコラ！
0521デフォルトの名無しさん
NGNG逆転も何もないって。
勢いで上告なんかしても一発で上告却下(門前払い)だよ。
二審も一審を支持。これに対して上告しようにも、
刑事訴訟と同様、自由に上告できるってもんでもないのです。
民事訴訟法312条 （上告の理由） 1項
「上告は、判決に憲法の解釈の誤りがあること
その他憲法の違反があることを理由とするときに、することができる。」
http://www.m-net.ne.jp/~doba/goto/hon.htm
ようするに上告しても今の制度では100％無駄。 これで完全終了ってことか。
0522デフォルトの名無しさん
NGNG２ちゃんねるのお勧めな話題と
ネットでの面白い出来事を配送したいと思ってます。。。
===============================読者数： 138720人 発行日：2003/1/9
年末年始ボケがそろそろ収まり始めた今日このごろのひろゆきです。
そんなわけで、年末に予告したIP記録ですが実験を開始しています。
「２ちゃんねる20030107」
こんな感じで各掲示板の最下部に日付が入ってるんですが、
20030107以降になってるところはログ記録実験中ですー。
んじゃ！
────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
0523デフォルトの名無しさん
NGNG0524デフォルトの名無しさん
NGNG0525デフォルトの名無しさん
NGNGcell computingとは、ブロードバンドに接続された家庭内や
企業内のPCの余剰CPUパワーを統合し、
仮想的なスーパーコンピュータとしての利用を実現する
技術を用いたSI、ネットワークサービスです。
バイオ、物理計算、設計、金融工学、CGレンダリングなどの
分野のお客様へ、安価に仮想スーパーコンピュータパワーを
提供することを目的としております。
なお、将来的には収益にあわせてCPUパワーを提供してくださる
参加者へポイントシステムやデジタルコンテンツによる
利益還元を考えております。
http://www2.cellcomputing.jp/
２ちゃんねるのチーム作ってみました。
http://members.cellcomputing.jp/services/teams/team.htm?id=ABBE425B-CE11-4DA4-8591-C68DF67DA41A
0526デフォルトの名無しさん
NGNG2chで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
0527デフォルトの名無しさん
NGNG2chで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
0528デフォルトの名無しさん
NGNG日本語の分からない人だね。内容証明があったからといって
名誉毀損があったとは限らないって言ってるの。
その上で裁判所は訴状送達の翌日としたのは、その時点で
名誉毀損を「認識した」ではなくて、「認識しえた」からなの。
わかる？この違い。
0529デフォルトの名無しさん
NGNGそしてバレて逮捕されるわけだが・・・
0530デフォルトの名無しさん
NGNGはぁぁぁ。あと、1週間以内で生理・・・。
何事にもむかついてたまらないっ！
生理前って、ブルーになったり、いらいらしたり。。。
ほんと勘弁してって感じ。
0531デフォルトの名無しさん
NGNG１年を通じて勤務した給与所得者
男性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
0532デフォルトの名無しさん
NGNGそして今そのうちの１つが無くなった、まあ「人数の多さ」だけでも人は集まるんだろうが
しかしこうなると「匿名性」と「人数の多さ」が合体して出来る"祭り"という物が、無くなっ
ていくんじゃないかなあ？祭り厨房としてはとてもそれが心配なんだが、、、
0533デフォルトの名無しさん
NGNG腐れの良い物件選びの講座開いてください
0534デフォルトの名無しさん
NGNG毛利宇宙飛行士でなければ追跡は不可能です。
0535デフォルトの名無しさん
NGNG0536デフォルトの名無しさん
NGNG応援だけはします！
0537デフォルトの名無しさん
NGNGでも、普通そんな風には思えませんが。
0538デフォルトの名無しさん
NGNG２ちゃんねるのお勧めな話題と
ネットでの面白い出来事を配送したいと思ってます。。。
===============================読者数： 139038人 発行日：2003/1/10
なにやら、連日メルマガだしてるひろゆきです。
そんなわけで、ログ記録実験ですが、いちいちサーバ指定するのが面倒なので、
全部のサーバに入れてみました。
重くなって落ちたりしてもご愛嬌ってことで。。。
んじゃ！
────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
0539デフォルトの名無しさん
NGNG0540デフォルトの名無しさん
NGNG0541デフォルトの名無しさん
NGNGＡさんが、ある「特定の結果」を得られるアルゴリズムを作りました。
のちにＢさんが「同一の結果」を得られる別のアルゴリズムを作りました。
そしてＡさんが「Ｂはパクリだ訴えちゃる」と言い出した。さて筋は通る？
通例では「筋は通らん」「Ａにそこまで縛る権利はない」の筈だが…。
0542デフォルトの名無しさん
NGNG0543デフォルトの名無しさん
NGNG半角とと芸能板もなってるけど。。
0544デフォルトの名無しさん
NGNG犯人が１７歳以下なら話は別だが
0545デフォルトの名無しさん
NGNG0546デフォルトの名無しさん
NGNG0547デフォルトの名無しさん
NGNGでも、大きいのと、高そうなのが・・・ちょっと・・・
でも・・・
カミサンだまし作戦開始・・・
0548デフォルトの名無しさん
NGNG0549デフォルトの名無しさん
NGNGある意味なんかスゲェと思う
っつーか、ヴァカすぎる。
今まで2ちゃんで書かれた意味ない予告にイチイチ社会が振り回されて
たらどうなるっていうんだか。
0550デフォルトの名無しさん
NGNG0551デフォルトの名無しさん
NGNG0552デフォルトの名無しさん
NGNGメールや電話だと「届いていない」「読めなかった」「回線の調子が悪くて聞こえなかった」で抜けられるからね。
0553デフォルトの名無しさん
NGNG0554山崎渉
NGNG0555デフォルトの名無しさん
NGNGは 低 学 歴
4 n d ！！
0556山崎渉
NGNG0557デフォルトの名無しさん
NGNG0558デフォルトの名無しさん
NGNG∵.☆:*・∵.゜.☆.・∴.,★ :*・∵.:☆.。.:*・:* ・∵.+:*・∵.゜ ★
★http://www6.ocn.ne.jp/~endou/index2.html★
★こんなサイト見つけました★
0559デフォルトの名無しさん
NGNG0560デフォルトの名無しさん
NGNG自分の稚拙な頭じゃ思いつかないので質問いたします。
長さ 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)の計算量でこのような操作は可能でしょうか？
0561デフォルトの名無しさん
NGNG0562デフォルトの名無しさん
NGNG実装上の問題というよりも、純粋に数学的興味が重きを占めてます。
なんかうまい方法がないですかな…
クイズみたいで気になってねれないよう
0563デフォルトの名無しさん
NGNGi'=j;
j'=i;
じゃ駄目なの？
0564デフォルトの名無しさん
NGNG例えば 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] = …以下続く…
0565563
NGNG俺が言ってるのは、そういう事じゃなくて
わざわざ、メモリ上の値を入れ替えなくても
アクセス方法を入れ替えたんじゃ駄目なのって事
例えば4×8の行列の(2,6)成分は
2*8 + 6 = 22 だから A[22]
これを8×4の行列の(6,2)成分として読むには縦と横を入れ替えて
6 + 2*8 = 22 だから A[22] /* 当たり前だけど同じでしょ */
0566デフォルトの名無しさん
NGNG各行を（横方向に）走査して変換するルーチンがありまして、
それを各列に対して縦方向にも適用したいのです。
もちろんルーチン内でのアクセス方法をおっしゃる
とおりに変えれば良いんですけど、それはそれで結構
面倒なんで（連続する2つの実数を一つの複素数の実部
と虚部として扱っている部分があり、複素演算ライブ
ラリでは当然実部と虚部のアドレスは連続しているもの
と仮定しているので、単純に添字を変えていくだけでは
うまくいかない）
最初は長さがNのテンポラリーな配列を動的に確保して
各々の行にたいして
一時配列にコピー → ルーチン適用 → もと配列に戻す
としていたんですけど、malloc するのはなんだかなって
思ったんで、なんかスマートな方法ないかなと。
きっかけはそれで、今や数学的興味のみです。
上げておきます、知ってるかたはヒントくだされ。
0567デフォルトの名無しさん
NGNGの誤りです。
各行はルーチンに直接わたせます。
失礼しました。
0568デフォルトの名無しさん
NGNGhttp://pc3.2ch.net/test/read.cgi/tech/992671330/192
に関連しているのでは
0569デフォルトの名無しさん
NGNG0570山崎渉
NGNG0571デフォルトの名無しさん
NGNG0572デフォルトの名無しさん
NGNG0573空間回転移動
NGNG例えばある点(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)の通る球の大円を描くように回転させたいと思っているのですが学力不足でできません。どなたか分かる方教えて下さい；；
大円を描く回転の場合もう一つラジアン値を設定しないといけませんが…
0574デフォルトの名無しさん
NGNGヽ ＿＿_＼（＼・∀・）＜ 赤黒木ってなによ？
＼＿／⊂ ⊂＿)＿ ＼＿＿＿＿＿＿＿＿＿＿＿＿
／￣￣￣￣￣￣￣／|
l￣￣￣￣￣￣￣￣| .|
| |／
0575デフォルトの名無しさん
NGNG0576デフォルトの名無しさん
NGNG日本語がおかしいのも学力不足だからですか？
がんばって解読すると「原点中心で点(X,Y,Z)を通る大円」を書きたいって
言っているように見えるんだけど、その条件では一意にならないし...
0577デフォルトの名無しさん
NGNGで、かつ、通る辺の数をなるべく小さくしたいのですが、どんなアルゴリズムを
使えばいいですか？
0578デフォルトの名無しさん
NGNG0579デフォルトの名無しさん
NGNGそれだけじゃ仕様が曖昧だな。
・開始点と終了点は違っているのか、同じなのか
・すべての頂点を通らなければならないのか、最短パス上の頂点のみでよいのか
ダイクストラのアルゴリズムは検討した？
それで解けない問題なら、サラリーマン問題と同じくNP問題用アルゴリズムだな。
0580577
NGNG始点と終点が違うし全頂点を通るわけでもないのでTSPとは別物でした
グラフのある点からある点への経路を探したいのですが、
通る辺の値の和を最小にすることと通る辺の数をなるべく少なくするという
２つの目的があって、ダイクストラのアルゴリズムを応用できないかとも思う
のですが、いまいち思いつきません。
「なるべく」というのもはっきりしないので、質問の仕方が悪いかもしれませんが
この事例ににた問題など紹介していただければありがたいです。
0581デフォルトの名無しさん
NGNG0582デフォルトの名無しさん
NGNG二つの条件を同時に満たす解が、必ずしも見つからないことは承知してる？
普通は、辺の重みを最小にする「最短経路問題」を使うわけだが。
通過する辺（頂点）の数も同時に最小にするのは、
辺の重みとどちらを重視するかの重み付けが、別に必要となる。
たとえば、距離が1でも重みが100の経路と、
距離が100で各辺の重みが1の経路がある場合（それら二つしかない場合）、
どちらを採用するの？
0583デフォルトの名無しさん
NGNG「講義用スライド・人工知能特論第1」という中に、
いくつかのネットワーク問題を最小化する問題についての資料があるよ。
また、この人が訳者になっている
「組合せ最適化アルゴリズムの最新手法」丸善
は、良書なので買っておこう！
0584デフォルトの名無しさん
NGNGありがとうございます
0585デフォルトの名無しさん
NGNG538＞なにやら、連日メルマガだしてるひろゆきです。
おまえはひろゆきに何を感謝しているんだ？
0586デフォルトの名無しさん
NGNG2chがあることに感謝してるんじゃ！
と明後日の方向にレス
0587アルゴ初心者
NGNG課題は下の画像ファイルを模したものから直線、斜線を切り出し、始まりの点と
終わりの点の座標をとってくるﾌﾟﾛｸﾞﾗﾑです。0が背景で、1が線の部分です。
どういうふうにﾌﾟﾛｸﾞﾗﾑを組めばいいのかわからず困っているのでお願いします…
000000000000000000000000000000000000000000000000
000000000000000000100000000000000010000000000000
000000000000000001000000000000000010000000000000
000000000000000010000000000010000010000000000000
000000000000000100000100000100000010000000000000
000000000000001000000010001000000010000000000000
000000000000010000000010010000000010000000000000
000000000000100000000001100000000010000000000000
000000000001000000000001000000000010000000000000
000000000010000000000010100000000010000000000000
000000000100000000000100010000000010000000000000
000000001000000000001000010000000010000000000000
000000010000000000010000001000000010000000000000
000000000000000000000000000000000010000000000000
000000000000000000000000000000000010000000000000
000000000111111111111111111111111111111111110000
000000000000000000000000000000000010000000000000
000000000000000000000000000000000000000000000000
0588デフォルトの名無しさん
NGNG0589質問君
NGNGコメントが入り組んでるとわかりにくいんですけど…
0590デフォルトの名無しさん
NGNGman cpp
0591デフォルトの名無しさん
NGNG運的要素が強い麻雀などを確率的に判断して、最強のアルゴリズムで
有名な研究などありますか？
0592デフォルトの名無しさん
NGNGＴＤギャモンとかは？
でもあれは普通に評価関数使って打ってるだけだったかな。
0593デフォルトの名無しさん
NGNG0594593
NGNG0595アルゴ初心者
NGNGすいませんが、理解しやすいサイトがあったら教えてください
0596デフォルトの名無しさん
NGNGとりあえず縦線横線だけ限定で考えれば？
それならできるっしょ
斜めは後で追加
0597デフォルトの名無しさん
NGNG自分で解けよ
マインスイーパーみたいな感じでできるじゃん
周辺の８方向をチェックする
0598組込もしまっせ
NGNG水平垂直なら596さんの通り、同じX座標に連続して点がある って条件で取れる
それと同じで４５度の線分も x+a,y+b (a,bは±1) の４方向に連続してる条件で取れる
ってやると、45度以外の斜めの線が水平垂直線と斜め線にバラバラに分解されてしまう
だから、最後に、分解した線分の始点、終点を接続してみて、直線上に並ぶなら接続という感じの処理で接続してゆく
0599デフォルトの名無しさん
NGNG将棋の桂馬飛びみたいにパターンが連続してるかチェックする
0600デフォルトの名無しさん
NGNG0602アルゴ初心者
NGNGすいません、何か簡単でいいのでソースとかありますか？
0603デフォルトの名無しさん
NGNG0604アルゴ初心者
NGNG全ての縦線と横線の始点と終点の座標を求めるサンプルﾌﾟﾛｸﾞﾗﾑをお願いします。
斜め線は…どうしよう つД;)
0605デフォルトの名無しさん
NGNG0606デフォルトの名無しさん
NGNG自分が頭が良いと勘違いしているｷﾓｦﾀ君のサイト
0607デフォルトの名無しさん
NGNG0608デフォルトの名無しさん
NGNG0609デフォルトの名無しさん
NGNG0610デフォルトの名無しさん
NGNG□□□□□□□□□□□□□■
左と右の■を結ぶ直線
0611デフォルトの名無しさん
NGNGチェーンコードの考え方を使って縦横、斜めの線を切り出そうというﾌﾟﾛｸﾞﾗﾑをつくりました。
つまり、線の始点を見つけたら８連結内を時計周りに見て、他のドットと繋がっている部分を探して、そこに次々移動していくというものです
（ちょっとわかりにくい説明だな…）
縦横はいいんだけど、斜めがちょっとまだ不十分…
例えば
******
******
******
******
だと斜め線でなく横線４つと認識してしまう…
どうしよう…
0612組込もしまっせ
NGNG基本的に区別つかないから 短い線分同士が接続してるかどうかチェックしてゆく作業は必要じゃないかな
長い線分から順に検索して、２つの線分A,Bの端点同士が一致していたら
1本の線に出来るかどうかチェックしていったら？
0613デフォルトの名無しさん
NGNG□■■ □■□ □■□ □■□
□□□ □■□ ■□□ □□■
0614デフォルトの名無しさん
NGNGPDFを出力するプログラムを書いているのですが、円を描く所で躓いてしまいました。
PDFには円を書くというオペレータがなく、3次ベジェ曲線を書くオペレータがあります。
或る円をかいているPDFファイルをみると4つの3次ベジェ曲線で円を描いているようでした。
4つの3次ベジェのそれぞれが、円の1/4弧を描いているらしいことはわかったのですが、
制御点をどのように算出しているのかがわかりませんでした。
ご存知の方いましたらおしえてください。
0615組込もしまっせ
NGNG斜め楕円の描画 で検索すると見つかりますよ
0616デフォルトの名無しさん
NGNGある矩形領域に、大きさがまちまちな矩形領域を、はみ出さず、かつ
それぞれが重ならないようになるべくたくさん並べて置けるようにする
アルゴリズムってどういったものがあるのでしょうか？
データはあらかじめ配置するので探索に時間がかかってもokです。
0617デフォルトの名無しさん
NGNG0618組込もしまっせ
NGNGほぼナップザック問題のような気がします。
0619デフォルトの名無しさん
NGNG0620アルゴ初心者
NGNG下の図を、垂直水平、そして斜めに切り出すことができました！ そして各辺の始点と終点の座標を得ることができました。
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
0621アルゴ初心者
NGNGさて次のステージですが…
これを２つの三角形として認識させて、それぞれの三角形の頂点の座標を得るのにまた困っています
この場合だと、１つめの三角形は頂点(2,13),(26,13),(14,1)、２つめは(6,25),(19,25),(13,7)という具合に…
線と線の座標が重なる部分が１ドットずれてることがあるけど、それを許容範囲にして一つの頂点としてみなしたいと考えています
どういう風に頂点をみつけていけばいいでしょうか… つД;)
0622デフォルトの名無しさん
NGNGせっかくだから完成したプログラム書いとけば？
0623デフォルトの名無しさん
NGNG普通に点と点の距離の数学的公式使ったら？
差の２乗を取って～～
0624621です
NGNGhttp://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)では線の終点という具合です。
このﾌﾟﾛｸﾞﾗﾑを実行すると、それぞれ四角形の場合の全ての頂点の座標、五角形の頂点の座標を別々に表示します。その頂点の表示のされ方も、反時計周りに辺の順番に表示されています。
線の切り出しの部分でまだバグがあるため、角数１というものが出ますが、今回は三角形以上の図形のみに着目したツールを作るつもりなので、角数１の場合はこの頂点を見つけるﾌﾟﾛｸﾞﾗﾑであらかじめ除いておこうと考えています。
これで一応頂点の座標を取るﾌﾟﾛｸﾞﾗﾑは完成としました ﾐﾝﾅ(･∀･)ｻﾝｸｽ!
しかし…
0625デフォルトの名無しさん
NGNGhttp://homepage3.nifty.com/digikei/ten.html
0626621です
NGNGまず前準備で①白黒の画像を読み込み ②１ピクセルごとにＲＧＢ値を調べる ③背景である黒だったら０番、白である線の部分であったら１番を割り付け、画像の大きさと同じぶんの２次元配列gazou[y][x]に格納
線の切り出しですが、原点からｘ軸方向に順に走査していって、線の始まりを見つけます。
始めに横線だけを抜き出し、そしてまた原点に戻ってから縦線、次にまた原点に戻り左斜め、次にまた原点に戻り右斜め、といった具合に線の種類事に切り出しを行いました。
線の切り出しの方法ですが、
（続く）
0627621です
NGNG線の切り出しのﾌﾟﾛｸﾞﾗﾑ
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として認識されてしまいます。
でも、もうこれ以上どうしたらいいのかわからなくて途方にくれてます…
（長文ｽﾏｿ…）
0628デフォルトの名無しさん
NGNGhttp://plaza16.mbn.or.jp/~graph_puzzle/index.html
0629デフォルトの名無しさん
NGNG0630デフォルトの名無しさん
NGNGこれより完璧なアルゴリズムに関する本ありますか？
あったら教えてください。
0631デフォルトの名無しさん
NGNG奥村氏の本だよね。安いし持っていても悪くないと思われ。
解説がやや少ないのでコードで理解できる人がサワリを学ぶのに向いてる
0632デフォルトの名無しさん
NGNG0633デフォルトの名無しさん
NGNGとある研究室でやりそうな話な気が・・・・・・
0634621です
NGNG先日皆さんの知恵を借りて作ったプログラムを持っていったら全否定食らってしまいました…
先生がいうにはこのやり方はタフなやり方じゃないらしいです。
先生がいうには
「例えば６つずつドットを飛ばして読んでいって、そこに線のドットがあったらその座標を保存していく。
その後、２つの点を使って線の式を求め、同じように他の２点から求めた線の交点をとっていく。
ちょっとずつ荒くみていくドットの幅を変えていったりして、何回かこれを繰り返し、似通っていた交点の座標がたくさん出てきたら、そこを図形の頂点とみなせばいい」
らしいです。
言うことはわかるんですが、これはどうやってコードにするんだろう…
画面から取れた点達から全部の線のパターンを考えて、その交点を取らなきゃだめってことでしょうか？
膨大な計算量になりそうな予感が…
実際、よくわかってないもので弱りますた…(´･ω･)
0635デフォルトの名無しさん
NGNG例外にしてループ処理するのは何をする時だったかな？？
0636デフォルトの名無しさん
NGNG0637デフォルトの名無しさん
NGNG0638組込もしまっせ
NGNGロバストって条件ですか・・・厄介ですね。
点列が綺麗に集まってる付近でグループ化して、グループサイズを大きくしながら幾何的な最小2乗直線を求めて
2乗誤差が敷居を割ったら止めるとか そんな処理が思いつくけど
0639名無し＠さん
NGNG教えてください。
シミュレーションゲームを作りたいんですが、いくら頭をひねっても、
移動可能な範囲を表示する方法が思い浮かびません。
↓こんなのです
■■■■■■■■■■■
■■■■□■□■■■■
■■■□□木□□■■■
■■□□□□□□□■■
■□□□□俺□□□□■
■■□□□□壁壁壁■■
■■■□□□壁■■■■
■■■■□□□■■■■
■■■■■□■■■■■
■■■■■■■■■■■
どなたか、分かる方教えてもらえませんか？
0640デフォルトの名無しさん
NGNG座標と移動可能値をキューに積む
キューから要素を取り出す
四方を調べて、それが「値－１」より小さいなら、置き換えてキューに積む
キューが空になるまで繰り返す
0641デフォルトの名無しさん
NGNGお世辞にもきれいなコードとは言えんが、これでどうだ？
#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;}
0642デフォルトの名無しさん
NGNG0643名無し＠さん
NGNGあっそうか、一歩ずつ四方を調べれば、確かにできますね。
四方じゃなくて、来た道を除く3方向でもOKかな？
移動できるコマの平均がnだとすると、 3^n だけ調べなきゃ
いけないんで速度が気になりますが、一度やってみます。
>>641
わざわざコードまで書いてもらってありがとうございます。
が、実はCはただいま勉強中で、詳しくありません。ToT
Cも分からないのかよ！！ なんて怒らないで下さいね。^-^;
そのうち理解できる日がくるはずなので、しっかり保存させてもらおうと
思います。
640,641さんどうも親切にありがとうございました。
0644640
NGNGそんなに大きいnを扱うのか？
たとえばLSIの設計だとn=100万以上ということもあるので、
この手法だと数日かけて計算することもあるが・・・。
>>639はLSIでいう詳細配線問題に相当するので、その線で調べてみ。
ちなみに>>640の手法を「迷路法」と呼ぶ。
0645デフォルトの名無しさん
NGNG0646デフォルトの名無しさん
NGNGヘクス 移動 範囲 アルゴリズム あたりでｸﾞｸﾞﾙと吉
探索済みかつ遠回りして来たマスに辿り着いたらそのルートはそこでおしまい、
とすると余計な計算を省ける。
0647名無し＠さん
NGNG大きくても10ぐらいかな～？でも3^10だと6万近くに・・・。
ほうほう、ちゃんと名前がついてるんですね。
探索で言うと、線形探索みたいなもんですか？
>>646
＞ヘクス 移動 範囲 アルゴリズム
キーワードサンクスです！
やっぱり最終的にはそういう高速化が必要ですよね。
今度は高速化のアルゴリズム考えるのが大変・・・。
好きだからいいんですが。^-^
0648名無し＠さん
NGNG0649デフォルトの名無しさん
NGNG0650デフォルトの名無しさん
NGNG数値を加算してできる最小のパターンを出す
っていうようなアルゴリズムを教えてください
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
0651デフォルトの名無しさん
NGNG収納美人になる！
0652デフォルトの名無しさん
NGNGとして、↓はちゃんと動きますか？
http://pc.2ch.net/test/read.cgi/prog/1042565432/32
0653デフォルトの名無しさん
NGNGJeda
せりに きりせり
まいしち
0655デフォルトの名無しさん
NGNG今ひとつ使える場面がピンとこないのですが。
0656名無し＠さん
NGNGhsp?ちょことっと3Dモデル表示したり、サウンドノベル作ったり、
ちょこっと画像表示させるようなプログラムには最適でしょ。
・・・・・・じゃなくてヒープか。
確かに、何に使うんだろう。データの整列をするとき、じゃ駄目か。
自分も知りたいです。
0657デフォルトの名無しさん
NGNGpriority_queue
0658デフォルトの名無しさん
NGNG最短経路の探索だったらダイクストラのアルゴリズムかな。
この場合だったら、3*n^2くらいで収まるはず。
0659デフォルトの名無しさん
NGNGあるデータから上位n個を取り出したい時とか、ヒープ使うと便利かな。
0660デフォルトの名無しさん
NGNGまさか、塗りつぶしのアルゴズムが分からない、というわけではなかろうな
0661デフォルトの名無しさん
NGNGただ、このプログラムでは考えなしに次の点を決めているので、今度はロボットが自走するように、これまでのチェーンコードのログを元に、次の進行先を決定するものを作りたいと考えています。
例えば、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;//再度読みこませない為に印付け}
0662デフォルトの名無しさん
NGNGWORDを返す乱数ジェネレータ(rnd)から0～100の範囲で
偏り無く取る場合、rnd*100/65535 とやらなければ成らないのでしょうか？
もっと簡潔に得る事は出来るんでしょか。
2の累乗なら&で上位ビット外すだけで良いのですが。。
0663デフォルトの名無しさん
NGNGrnd % 100
0664デフォルトの名無しさん
NGNG正直、最近迄何も考えずに%使ってたんですが、
上が65535だから、 100だと35以下に偏るじゃないですか。
0.15%程ですが。
0665デフォルトの名無しさん
NGNGdo{rnd=rand();} while( rnd > 65500 ) ;
val = rnd % 100;
0666組込もしまっせ
NGNG0～99迄の範囲で隔たりなくではなく、0～100で隔たりなくですよね？
WORDを返すような環境だと、除算は掛算より遅いから %より
rnd*101/65536 として (rnd*101)>>16 とした方がいいでしょう。
アセンブラで int MulShr16(int n , int m); みたいなのを作っておくといい。
0667デフォルトの名無しさん
NGNG0.15%の偏りを気にする以前にrnd自体の乱数が偏ってたりして。
0668デフォルトの名無しさん
NGNGhttp://science.2ch.net/test/read.cgi/rikei/1046173479/l50
0669デフォルトの名無しさん
NGNG0670デフォルトの名無しさん
NGNG+1でシフトですか。。有難う御座います。
ちなみにこの場合、DWORDが必要になりますが、WORDをWORD内で
処理する方法はありますでしょか。
>>667
よく考えると0.15て全く見当違いの数字でした；
0～100の場合の話で、範囲が広くなれば随分偏りますよ。
0671デフォルトの名無しさん
NGNGその際に、取得する深さを指定したいのです。
指定ディレクトリから、ｎ階層下までのファイル名一覧を取得したいって感じです。
この指定階層より深いところは無視するという処理に関して、
どこか参考になるサイトないしアルゴリズムはあるでしょうか？
0672デフォルトの名無しさん
NGNGint depth を引数につけて、再帰するときに 1 ずつ減らす。
0673名無し＠さん
NGNG>>658
3*n^2ですか、結構少なくて済むんですね。
物は試しってことで今作っているので、できたら
何回ループするか計ってみます。
>>660
塗りつぶしのアルゴリズムは分かるんですが、これに障害物なんかが
入ってくるとさっぱりでした。
単純な塗りつぶしは、キャラクタからのx,y座標の絶対値を足した値が
移動力以下なら移動可でいいんですよね。
0674デフォルトの名無しさん
NGNG特列＝'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);
こう書いて間違ってるみたいなんだけどどう書くと正解か分かったら教えてください
0675tantei
NGNG●浮気素行調査
彼氏、彼女、妻、夫の浮気を調査致します！！
●盗聴器盗撮機発見
あなたの部屋に誰かが仕掛けているかも！！
●行方調査
行方不明になっている家族の消息を調査致します！！
●電話番号から住所割り出し
一般電話、携帯から住所を割り出し致します！！
●ストーカー対策
社会問題ともなっているストーカーを撃退致します！！
その他人生相談からどんなお悩みでも解決いたします！！
直通 ０９０－８５０５－３０８６
ＵＲＬ http://www.h5.dion.ne.jp/~grobal/
メール [email protected]
グローバル探偵事務局
0676デフォルトの名無しさん
NGNGこの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 の和の総累積値
を求めたいのですが、皆さんの知恵を貸してください。
条件で不明な点がありましたらご指摘ください。
0677676
NGNG現在既に、任意の繰り返し時点 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 と等差級数の和を求める数式を活用できないか、ということで試行錯誤していますが
正確な残り時間の累計値が出るに至っていない状況です。
0678デフォルトの名無しさん
NGNGt(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) を引けばよい。
0679671
NGNG>>672
うまくいってるような感じです。ありがとうございました。
0680676
NGNG>>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)の答えとなってしまった次第です。
0681モジュラス43
NGNGチェックデェジットのモジュラス43をＶＢで至急書かなければなりません。
アルゴリズムは解ったのですが、ＶＢコードの関数お持ちの方、実コード教えて下さい。
お願いします・・・・
0682モジュラス43
NGNG0683モジュラス43
NGNGチェックデェジットのモジュラス43をＶＢで至急書かなければなりません。
アルゴリズムは解ったのですが、ＶＢコードの関数お持ちの方、実コード教えて下さい。
お願いします・・・・
0684デフォルトの名無しさん
NGNG0685デフォルトの名無しさん
NGNG0686デフォルトの名無しさん
NGNG0687デフォルトの名無しさん
NGNGf: Z -> N とかね。
関数を与えると、こういうマップを書き出してくれるプログラムのことだろ？
prolog でも作るの？
0688デフォルトの名無しさん
NGNG0689デフォルトの名無しさん
NGNG0690デフォルトの名無しさん
NGNGトルネコみたいなダンジョンマップとティルナノーグみたいなフィールトのマップの
ことを言います。
わかる方どうかお願いします。
0691デフォルトの名無しさん
NGNG各ソフトがどんな作り方してるか、考えてみるといいですよ。
0692デフォルトの名無しさん
NGNG寝ぼけてたｽﾏｿ
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
0693デフォルトの名無しさん
NGNGrogue の level.c:make_level() は短いから読んでみれば
0694デフォルトの名無しさん
NGNGどなたか知恵を貸していただけないでしょうか。
0695Neiklot ◆pNTQ.vzQQM
NGNGその四角形が通ったあとに軌跡を残るようにして、
その軌跡にぶつかったら画面が赤く光るようにしたいのですが、
この問題は、どうすれば解決できるでしょうか？
0696デフォルトの名無しさん
NGNG何が問題なわけで?
0697デフォルトの名無しさん
NGNGその四角形が通ったあとに軌跡を残るようにして、
その軌跡にぶつかったら画面が赤く光るようにすればいい。
0698デフォルトの名無しさん
NGNG三角形は枠だけ? それとも板?
0700694
NGNGそれから、円柱は基本的にx,z軸に対して垂直です。
0701デフォルトの名無しさん
NGNGそんなのここで語る話じゃないな。
Javaスレで聞け。
0702デフォルトの名無しさん
NGNGなら、真上からみたら？
0703Neiklot ◆pNTQ.vzQQM
NGNG分かった
0704プログラム売買
NGNGデータを時系列にプロットするプログラムなのですが、
アイディアを貸していただけないでしょうか？
0705694
NGNGありがとうございます
試してみます
0706デフォルトの名無しさん
NGNG真上から「だけ」ではだめなオカン
0707デフォルトの名無しさん
NGNG問題：時刻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の等式成り立つのかと疑問ですし。添削おながいします。
0708707
NGNG0709707
NGNG0710デフォルトの名無しさん
NGNG0711初心もの
NGNG＜全部平均するとこちらが設定したような数Ｎになるような乱数（乱数の個数も
こちらが設定）を発生するような方法＞というのはどのようなものなのでしょうか？
どうかよろしくお願いします。
0712デフォルトの名無しさん
NGNGまず好きな特性の乱数を作りだす
その後、その乱数の平均を求めて、 設定した値 N との差を出し、 乱数列の全部の要素に足せばいい
0713初心もの
NGNGどうも有難うございました。助かりました。
0714デフォルトの名無しさん
NGNG0715デフォルトの名無しさん
NGNGO(f(n)) + O(g(n)) = O(max(f(n) , g(n)))
この式のmax(f(n) , g(n))とはどういう数式なんでしょうか？
エクセルのmax関数と同じでいいんでしょうか？
0716デフォルトの名無しさん
NGNGもしもし？
0717ヌーン
NGNGそこでふっと疑問。
あの同色のぷよが４つ以上そろったら消えるって、どういうアルゴリズムなんですか？
ぷよのならべ方はべつに直線とは限らないし、時には６つ・７つと繋がる
こともあるわけで。
ほんと疑問です。誰か分かる方おられます？
ひょっとしたら初歩的な質問かもしれませんんが。
0718デフォルトの名無しさん
NGNGttp://chaos2.org./xpuyopuyo/index.shtml
ttp://www.geocities.jp/catt9a/program/p2001_06.html
0719デフォルトの名無しさん
NGNGわ～い １０２１点いった～ヽ(∇⌒ヽ)(ノ⌒∇)ノ
0720デフォルトの名無しさん
NGNG0721デフォルトの名無しさん
NGNGgoogle ってみても、うまく引っかからない。
0722デフォルトの名無しさん
NGNG0723デフォルトの名無しさん
NGNGまぁ、これでも読んでみ
0724デフォルトの名無しさん
NGNG上記記事は C MAGAZINE, 2000年10月号 に掲載なのだ
0725デフォルトの名無しさん
NGNGｽﾞﾝﾁｬｽﾞﾝﾁｬ♪
0726デフォルトの名無しさん
NGNGRed Sun Black Clossからきているんだよ(w
0727デフォルトの名無しさん
NGNG0728デフォルトの名無しさん
NGNG配列から要素を削除することの説明で出てきたのですが。
0729デフォルトの名無しさん
NGNG0730デフォルトの名無しさん
NGNG0731デフォルトの名無しさん
NGNG普段は Java を使っているんですけど、 LinkedList のありがたみがあまりよく分かりません。
0732デフォルトの名無しさん
NGNGArrayList とか連結リストじゃないっけ。
0733デフォルトの名無しさん
NGNG0734見習中
NGNG行列（最大１０×１０）の固有値を
Cのプログラムで求めたいです。
世には色々な方法がありますが、
ソースが手に入って、精度も良いお勧めの方法を教えてください。
希望をいえば、matlabのeigと同じ精度（欲張ってすみません）
行列要素は、実数です。ただし、対称行列ではありません。
C言語によるアルゴリズム辞典
http://www.matsusaka-u.ac.jp/~okumura/algo/
では、全部実対称行列が対象だった。（泣）
よろしくお願いします。
0735デフォルトの名無しさん
NGNGふらっと立ち寄ったものですが，LAPACKではどうでしょうか．
初めての方には，たとえば大西さんのページがよいと思います．
ttp://www.a.mei.titech.ac.jp/~yonishi/Program/CLapack/
0736見習中
NGNGでも、Cのソースが欲しいのですよ。
よい方法を模索中です。
0737デフォルトの名無しさん
NGNG0738デフォルトの名無しさん
NGNGマルチはマナーとしてあまりｲｸﾅｲよ。
今度から気をつけてね。
0739見習中
NGNGそうですね。気をつけます。
（ちょっと慌てていたもので、、、）
0740デフォルトの名無しさん
NGNG高速に平方根を求めるアルゴリズムはありますか？
sqrt はニュートン・ラプソン法の逐次計算によって
根を求めているのでしょうか？初期値は？
sqrt って基本的な関数ですけど
ふと、どうやってんだろうと思ったもので。
0741デフォルトの名無しさん
NGNG> Cの標準関数 sqrt より
> 高速に平方根を求めるアルゴリズムはありますか？
答えは「ある」だろうけど、数値計算の相応の専門知識が必要になるのでは?
まちがっても、このスレでちょっと質問して、すぐわかるような問題ではないと思われ。
0742デフォルトの名無しさん
NGNG0743デフォルトの名無しさん
NGNG標準関数だからといって実装まで<標準>があるのではありません。
>>742さんが書いてる通り、パソコンではFPU命令が使われるのでそれ以上高速にするのは不可能です
浮動小数点の場合、初期値は、
指数部を半分にして、奇数なら√2倍する事を覚えておいて、実数部はテーブル検索で用意するのでしょう
0744デフォルトの名無しさん
NGNG俺742だけど、そんな風に書かれると注釈加えたくなるなあw
標準関数といえど関数の中に入っている以上、インラインアセンブラでfsqrtを直接書けば
スタックフレームとかcallまわりの処理を省けるので速くなります。
でも、コンパイルオプションによっては数学関数を自動的に展開してくれるコンパイラもあるのでなんとも。
0745デフォルトの名無しさん
NGNGそれは実装上のテクニックだから、アルゴリズムを改善した事にはならないでしょう。
ニュートン法は1回毎に精度桁数が倍になるんで、初期値を適切に選べば
これより高速なアルゴリズムは難しいでしょうね。
精度が不要なら別だろうけど
0746デフォルトの名無しさん
NGNG・精度の低い値を求める命令
・Newton-Raphson法で精度を高める命令
と段階をふんで求めるようになってるね。
低精度でいいのなら、1命令=1clkですぐに結果がでるという。
0747デフォルトの名無しさん
NGNGsee.
情報処理学会論文誌 Vol.31 No.07
0748デフォルトの名無しさん
NGNG自分でもいろいろ調べてみます。
0749デフォルトの名無しさん
NGNG0750デフォルトの名無しさん
NGNGあります。
0751デフォルトの名無しさん
NGNG0752山崎渉
NGNG0753デフォルトの名無しさん
NGNGif a > b
a only処理
if a < b
b only処理
if a = b
match処理
だと思うけど、他に良い方法ってあるかな？
0754デフォルトの名無しさん
NGNGa only処理
else if a < b
b only処理
else
match処理
分かっているとは思うけど、整順序の場合は比較評価は２回で済む。
0755デフォルトの名無しさん
NGNG各グループの数字の合計が、全数字の合計の半分の値に最も近くなるような組み合わせを、
発見するようなアルゴリズムってありますか。
0756デフォルトの名無しさん
NGNG0757デフォルトの名無しさん
NGNGレス、サンクスです。ググって調べてみます。
0758デフォルトの名無しさん
NGNG幸せになったような、なってないような・・・。微妙なところです。
0759デフォルトの名無しさん
NGNG一応動く程度の処理なら書けるのですが、出力結果が最小になるようにする方法が
全然わかりません。
0760デフォルトの名無しさん
NGNGdiffのソース読め
0761デフォルトの名無しさん
NGNGソートして交互に取り出したら、正解になったりしない？
0762デフォルトの名無しさん
NGNGアセンブラだと比較自体は1度で済むね。
条件分岐は2回入るので一緒だけど。
0763デフォルトの名無しさん
NGNG両グループ同じ要素数とは書いてないからそれじゃだめじゃない？
｛10,1,1,1,1,1｝のような場合、｛10,1,1｝と｛1,1,1｝じゃなくて
｛10｝と｛1,1,1,1,1｝に分けたほうが近いじゃん。
0764デフォルトの名無しさん
NGNGvivi の作者さんのページに文書比較アルゴリズムについての説明と
論文へのポインタが載ってる。
0765デフォルトの名無しさん
NGNG見てはみたのですが何をやってるのかさっぱり...でした。
>764
はい、これも読ませてもらいましたが理解できなかったんです。
いろいろ調べてみたんですが良くわからなかったので、
諸先輩方に教えを乞おうっと思って書き込みさせてもらいました。
0766デフォルトの名無しさん
NGNGdiff もどきが作れるのに、ソースも論文もわからないとなると、
関連参考書を買って、勉強するしかないんじゃないか。
0767デフォルトの名無しさん
NGNG何か参考になるものがあれば、喜んで購入します。
もしご存知でしたら、関連参考書を教えてください。
0768761
NGNGあーそうかー。
じゃぁ、二つの集合A,Bに合計値を覚えながら追加することにして、
Aの合計がBの合計より大きいときだけBに追加（それ以外はAに追加）したら、
正解にならないだろうか？
0769デフォルトの名無しさん
NGNG例えば {2, 9, 9, 10, 10} なんかで困りそう。
多かったらどれかを戻して…とかやってくと、やっぱり総当たりと同じになりそうだし…
0770デフォルトの名無しさん
NGNGん？大きい順に分けていけば？
0771デフォルトの名無しさん
NGNG再帰の結果に残しておいたのを合計値の半分により近くなるように分配する。
大きいほうから並べて>>788のやり方でもいいと思うけど。
0772デフォルトの名無しさん
NGNG0774デフォルトの名無しさん
NGNGナップサック問題はNP完全だろ。
ちゃんと解こうとしたら総当たりにしかならないんじゃないか。
0775デフォルトの名無しさん
NGNG0776デフォルトの名無しさん
NGNG>>769 のは {2, 9, 9} と {10, 10} に分けたい例だけど、最初から均等にしてたらできないよ。
大きいほうからだと、 {9, 10} と {9, 10} のどっちかに 2 を追加するって感じになっちゃう。
0778デフォルトの名無しさん
NGNGアルゴリズムイントロダクション第2巻の最長共通部分系列
0779デフォルトの名無しさん
NGNG以前、もう一つのアルゴリズムスレで話題になった。
0780デフォルトの名無しさん
NGNGB木ならまだなんとかなるけど、AVLとか赤黒ってよっぽど慣れてないと
ちゃんと動くまでに時間掛かりすぎるよね。
0781デフォルトの名無しさん
NGNGありがとうございます。
探してみます。
0782デフォルトの名無しさん
NGNG丁度、gmtime関数がtime_t型の値を変換するものと同じです。
単純に秒を365*24*60*60で割ると閏年の問題で4年ごとに1日ずれてくるので、
Year/4-Year/100+Year/400-477 (閏年で増えた日数)
を単純計算で求めた日数から引いてマイナスになったらYearから1引く…なんて考えましたが、
そもそもYearが正しく求められていないので使用することができませんでした。
誰かご存じの方がいればよろしくお願いします。
0783デフォルトの名無しさん
NGNG0784デフォルトの名無しさん
NGNG(year-1970)/4 ?
色んな計算式を挙げてみたら？
Ｃ言語？
0785デフォルトの名無しさん
NGNG400年の日数は 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;
みたいな感じでやれば？
0787デフォルトの名無しさん
NGNGその中の組み合わせで3万円に
一番近い数字になるように計算して一番近い順にならべていく方法が
あったら教えてください。
一応、考えている言語はC言語です。
ちなみに
ナップザック問題を見たのですがどう応用するばいいかよくわかりませんでした
0788デフォルトの名無しさん
NGNG気にスンナ
0789デフォルトの名無しさん
NGNG総当りで。
0790デフォルトの名無しさん
NGNG総当りしかないんすかねー。
バカなんで、総当りでもどうやったらいいか悩みそう・・。
0792787
NGNGソフトがあるかどうか質問するスレで聞いたのですがなかったもので
自分で作るしかないかなと思って質問しました。
0793デフォルトの名無しさん
NGNG3万円から最大誤差のセットで差を出来るだけ小さくしたいのか
0795787
NGNG0796デフォルトの名無しさん
NGNG２８千円×１４組？
0797デフォルトの名無しさん
NGNGで、配列が正規分布に従うと仮定する。でa+j = b+i = c+h = d+g =e+f
と推測して、a～jが1から9である場合、(a+j) + (b+i) + (c+h) = 30
になるとするってどうよ
0800デフォルトの名無しさん
NGNGSU…１～１００までの自然数、B2…２の倍数の和、B3…3の倍数の和、B5…5の倍数の和
このアルゴリズムがかけないです・・・
どなかた助言お願いします
0801デフォルトの名無しさん
NGNG小学生からやりなおせ
0802デフォルトの名無しさん
NGNGfor(i=1; i <= 100; i++){
if(i % 2 == 0) B2 += i;
if(i % 3 == 0) B3 += i;
if(i % 5 == 0) B5 += i;
}
0803802
NGNG教えたので教えてください．
組み合わせ／パズルに関するアルゴリズムについてです．
「カ」「キ」「ク」「ケ」「コ」の文字を使って形を作ります．
（別にカキクケコじゃなくてもそれぞれの文字が見分けられれば何でもいいです）
・作る形の例
＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋
＋＋＋キ＋＋＋ ＋＋＋＋＋＋＋
＋＋カクケコ＋ ＋キカクケコ＋
＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋
＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋
好きなように配置して形を作ればいいのではなく，
どこになら置いていいのか，というのが決まっています．
・置くきまりの例
「カ」の横に置ける文字 「キ」と「ク」
「キ」の横に置ける文字 「カ」と「ク」
「ク」の横に置ける文字 「カ」と「キ」と「ケ」
「ケ」の横に置ける文字 「ク」と「コ」
「コ」の横に置ける文字 「ケ」
（続く）
0804802
NGNGで，このきまりに当てはまる形が上の 作る形の例 で示したものです．
次の２つは同じ形とします．
＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋
＋＋＋キ＋＋＋ ＋＋＋＋＋＋＋
＋＋カクケコ＋ ＋＋カクケコ＋
＋＋＋＋＋＋＋ ＋＋＋キ＋＋＋
＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋
・・・
こんな具合のパズルなんですが，
これを 置くきまり を元に，何通りの形があるのか，
どんな形が作れるのかを求めるアルゴリズムは何かありますか？
応用できそうなアルゴリズムでも結構です．
なにか情報があれば教えてください．
（ｽﾞﾚました．実際は＋マークがそろいます）
0805デフォルトの名無しさん
NGNGｽｹﾞｰよ、あんた天才さよ
0806デフォルトの名無しさん
NGNGそれとも枠が決まってて、それが＋で表した領域？
0808デフォルトの名無しさん
NGNG0809802
NGNGそうですねぇ，近いかもしれません．
置くきまりを，
「カ」の横に置ける文字 「キ」「ク」「ケ」「コ」
「キ」の横に置ける文字 「カ」「ク」「ケ」「コ」
「ク」の横に置ける文字 「カ」「キ」「ケ」「コ」
「ケ」の横に置ける文字 「カ」「キ」「ク」「コ」
「コ」の横に置ける文字 「カ」「キ」「ク」「ケ」
と，自身以外の文字全て指定すれば
ペントミノのピース（12種類）の形は全て作成できると思います．
ペントミノ（その他のミノでもいいですが）のピースを
生成するアルゴリズムがあれば参考になるかも知れません．．
0810デフォルトの名無しさん
NGNG個々のピースの各位置に文字を書いていけるか総当たりでチェック。
対称性のチェックは後回し。。。
ピースの構造体 (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]にルールチェックしながら文字を順に入れていく。
0811デフォルトの名無しさん
NGNGtype
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の集合やスカラー型を目一杯使ってみたりして。
わざわざ面倒な（他言語使用者に分かりにくい）書き方をしてるとも言える。
0812デフォルトの名無しさん
NGNG0813デフォルトの名無しさん
NGNG■■■■■ ■■■■ ■■□□
□□□□□ □□□■ □■■■
■■■ ■■□ ■□□ ■■
□□■ □■■ ■■■ ■□
□□■ □□■ □□■ ■■
□■□□ ■■□ ■□□
■■■■ □■■ ■■■
□□□□ □■□ ■□□
■■■
■■□
□■□
■■■
□■□
最後の2つは、この問題の解にはならないね。
0814デフォルトの名無しさん
NGNGという問題が出んです。rand()を使ってみるといいって言われたんだが、どうもできません。助けてください！
0815そのこちゃん
NGNG0816814
NGNGぜひともアドバイスくださいまし。
0817デフォルトの名無しさん
NGNG同じ質問を答えたことがあったな。宿題スレだったかな？
そのときは
・n個の配列を作り 0～n-1 まで順に入れてゆく
・randを使い、配列をシャッフル
・先頭からLまでを答えとする
などの解答がでた。過去ログさがしたがDATオチかな
0818デフォルトの名無しさん
NGNG0819814
NGNGそれとも同じ学校、同じ授業で誰かが毎年2chで質問？((((；ﾟДﾟ)))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ
0820デフォルトの名無しさん
NGNG0821デフォルトの名無しさん
NGNG0822814
NGNGとにかくなんとかなりそうです。ありがとうございます
0823デフォルトの名無しさん
NGNG簡単じゃないと思う。
0824814
NGNGその方法が一番早いよってことを説明する程度でよかったとおもう。
0825デフォルトの名無しさん
NGNG> その方法が一番早いよってこと
むしろそっちの方が難しいと思われ
0826814
NGNGでもうまく書けないんですよ。プログラム自体が。
100*rand()%50
こんな感じにrand使えばいいんですかね？変数にして。
0827デフォルトの名無しさん
NGNGまずは、何の言語を使うかだな。
0828814
NGNG今C++でやってます。
char s[n]
で数列ｓをつくってみて
for文でn回ループさせて・・・
ってとこまでで、それから進みません(|| ﾟДﾟ)
明日なのに、やばいです・・・・
0829デフォルトの名無しさん
NGNG0830デフォルトの名無しさん
NGNG#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;
}
0831デフォルトの名無しさん
NGNGこれは？いったいどうなっているのでしょうか？
変な方法なのですか？
0832デフォルトの名無しさん
NGNGerror C2065: 'shuffle' : 定義されていない識別子です。
srand(s);
っていわれます。これはどうなってるんですか？
0833デフォルトの名無しさん
NGNGC++でもっともマトモな方法ならば、
#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);
}
これ以上はないでしょう
0834デフォルトの名無しさん
NGNGこのアルゴリズムである特定の順列の確率ってどうやったら求まるんだろ。
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
0835デフォルトの名無しさん
NGNGより誘導されてきました。
経路探索アルゴリズムを勉強しているのですが、A*(A-Star)アルゴリズムがいまいち
つかめません。
breadth first search(bfs)にコストを導入したもの、というところまではわかったのですが…。
1.パス情報を持つデータを用意する
2.それをオープンリストとし、開始点q(親)を選ぶ
3.qの子ノードのコストを計算する
4.子ノードから一番コストの低いものを選ぶ
5.qをクローズリストに追加し、選ばれた子を親として終点にたどり着くまで繰り返す
これでいいんでしょうか？
これだと行き止まりにいってしまった場合探索が失敗すると思うのですが…。
google による検索結果から以下のURLを参考にしました。
ttp://rajiv.macnn.com/tut/search.html
0836デフォルトの名無しさん
NGNGrandom_shuffle が利用する乱数生成器が一様分布に従う場合を考える。
まず k 回目の交換が終った時点で x[k]～x[n-1] は未交換であることに注意しよう。
n-1 回の交換の結果 x[0]～x[n-2] の順列が等確率に生成されることを仮定すれば、
n 回目の置換によって末尾の要素 x[n-1] を x[0]～x[n-1] のいずれかと
等確率で初めて交換されるので n 回の交換によって作られる各順列は等確率となる。
0837835
NGNG1.オープンリストに開始点を入れる
2.オープンリストが空になるまで繰り返す
3. オープンリストの中から最小コストfを持つもの選び、取り出す
4. それをqとし、周囲8セルの子ノードを作る
5. 子ノードの数繰り返し(8回)
6. コストを計算する
7. オープンリストの中に存在すればスキップ
8. クローズリストの中に存在すればスキップ
9. そうでなければオープンリストに追加する
10. 子ノード繰り返し終了
11.クローズリストにqを追加する
12.オープンリスト繰り返し終了
13.解はクローズリスト
これでOKなんでしょうか？
どうしても無駄な要素がクローズリストに出てくるのはコスト計算を失敗しているから？
0838デフォルトの名無しさん
NGNGclosed list は解じゃなくて探訪済みのすべてのノードをとっとく集合。
これがあるせいで A* は指数領域オーダー。
解かどうかの判定は5,6の間で行なって、子がゴールに到達してたらその時点で返すの。
7, 8 はコスト比較の条件が抜けてる。
0839835
NGNG申し訳ない。
closed listが探訪済みノードの集合だとすれば解は一体どこへ…？
7,8のコスト比較はリスト内にコストの低い点があればを追加すればいいという
事でOKでしょうか。
0840デフォルトの名無しさん
NGNGゴールに着いたらそこから親をたどっていけば解を作れるでしょ。
> 7,8のコスト比較はリスト内にコストの低い点があればを追加
逆。全然分かってないっぽいので注意しとくと、
比較するのは closed にある「同じ位置を指すノード」。
子が未探訪の位置を指すか探訪済みでも既知の道より近道(コストの低い道)だったら
open と closed の両方に加える。だから open 内のノードと比べる必要は本来ない。
0841835
NGNG7,8はつまりリストに一致するものがあって且つその一致するものと現在のノード
コストの比較を行えばいいんでしょうか？
つまり
function check (list, node) {
for each (list) {
if (list == node && list.cost < node.cost) skip;
}
}
抽象的な表現ですがこんな感じ？
0842デフォルトの名無しさん
NGNGコードの意図がよく分からん。正しいともいえるし間違ってるともいえる。
この辺見るよろし
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
0843835
NGNGそのページも一度みてみたんですけどね。
とりあえず論文取り寄せてみます、ありがとうございます。
＃関係ないけど「A-Star(A^*)」という出だしの(A^*)が顔文字に見えた…
0844デフォルトの名無しさん
NGNG総アタックよりも効率的な方法がありますか？
配列をソートして
・・・という感じになるような気がするんですが、そこからどうやれば良いかわかりません。
0845デフォルトの名無しさん
NGNG前も聞いてなかったか？
0846デフォルトの名無しさん
NGNG見てなかった。ごめんね
0847デフォルトの名無しさん
NGNG0848844, 846
NGNGありましたね。しかもすぐ近所に。
しかし、797の回答ではプログラムに起こすのは困難な上に
非効率的すぎるのですが・・・
もともと、仮定と推測って・・・。
そんなファジーなアルゴリズムはアルゴリズムって呼べるんでしょうか？
0849デフォルトの名無しさん
NGNG自分の無知を誇るようなレスはやめたほうがいいよ。
リアル厨房なら仕方ないが。
0850デフォルトの名無しさん
NGNGttp://www.google.co.jp/search?q=knapsack+heuristics
0851デフォルトの名無しさん
NGNGてゆーか普通にケツから詰めてけばいいんじゃねーの
それが嫌ならもっとファジーな遺伝アルゴリズムを使えば？
終
了
0852デフォルトの名無しさん
NGNG確率（ランダム）アルゴリズムは、矛盾した名称ということになるのかね？
0853デフォルトの名無しさん
NGNG配列をソートするところまでしか考えられない奴よりマシ。
0854デフォルトの名無しさん
NGNG0855デフォルトの名無しさん
NGNGお前の頭のファジーさが足りねぇ
さらに、結局総当りくらいしか思いつかず、
答えられねぇから叩くだけの香具師も能無し杉だな
と、叩くだけの能ﾅｼからのメッセージ
0856デフォルトの名無しさん
NGNG今のところ、総当りしか解が存在しないからでは？
0857デフォルトの名無しさん
NGNGここは夏休み子供相談室じゃない。
0858デフォルトの名無しさん
NGNG0859デフォルトの名無しさん
NGNG本しか読まずに考えることをしないのはどうかと。
本や資料に「出来ない・難しい」って書いてあると君はトライしようとも思わんのね
>848
工夫次第である程度までなら総当りを避けられるんだから、そっから攻めてけばいい
俺は一般的なアルゴリズム知らんからどこまで説明できるかわからんけど
大---小
0001111 ←は最小からの総和で目標値を超えない位置
0010111 この時、４つのアイテムについて確認するものとし、このリスト中のアイテム数も
0011011 ４を超えない事がわかる
0011101
0100111
0101011
0101101
で、総当りをほんの少し回避できるかなー。と思った
0860デフォルトの名無しさん
NGNGあの下もずっと同じようなルールで 1111000まで続くんよ。
0861デフォルトの名無しさん
NGNG近似解で満足しろよ
0862デフォルトの名無しさん
NGNGそこそこの解を見つけるには、いくつか手法が知られている。
代表的なものは、Genetic Algorithm（遺伝的アルゴリズム）、シミュレーティドアニーリング、など。
そんなおおざっぱな分類をあげても困るという場合は、
情報処理学会の「数理モデル化と問題解決」研究会の論文などを入手して読むよろし。
大勢の人が、弁当を詰め込むのにいかに効率よくするかを研究しているから。
ttp://www.ipsj.or.jp/sig/mps/
0863デフォルトの名無しさん
NGNG参考になります
0864862=858
NGNGLSIの設計や、暗号理論、などに組み合わせ最適化問題が使われています。
金融工学にも応用があるようですね（専門外ですが）。
その手の参考書を読むとよいかと。
0865デフォルトの名無しさん
NGNGﾊｧ？ ああ、そうですね。それはよかったですね。
ところで、二度とプログラム板には来ないでください。
アニメ板が良くお似合いです
p2pで拾ったVBでも使って時計でも作っててください。
0867デフォルトの名無しさん
NGNG???
0868デフォルトの名無しさん
NGNG厳密解に10000年かかるのが、9800年で済むのでうれしいね、くらいの役割しかない。
それがNP問題ですから。
これを現実時間でとくには、>>861 やその他で言及したように近似解で我慢するか、
P=NPであることを証明しなければならない。
...
0869デフォルトの名無しさん
NGNG正反対の感情をもって返答しているのだろうか。
0870デフォルトの名無しさん
NGNG>>859-870 が自作自演であることが判明するわけだが。
0871デフォルトの名無しさん
NGNG???
>>859
ナップザック問題といえば、一般には動的計画法を使うのがよろしいかと。
実装が容易で、実行時間も速い。
0872デフォルトの名無しさん
NGNG馬鹿だから。
0873デフォルトの名無しさん
NGNG0874デフォルトの名無しさん
NGNG内容理解できなかったから納得。理解できるものは煽る
という糞房特有の性質だから
0875デフォルトの名無しさん
NGNG863 ですが、865 ではありません。
まじめにこの問題について聞いているつもりですが
騙りが発生した責任をとって二度とここにはきません。
さようなら
0876教えて君
NGNGであるのは、何故ですか？
また、枝を一本削除するのに必要な計算時間もο(log(n))であるのは、何故ですか？
0877デフォルトの名無しさん
NGNG>>863=>>865だと思ってしまうあんたはおかしいね。
レスした時間と順番から見て別の人間だろ。
>>875
誰も騙っていないと思うが・・・
>>861を無視しないでレスしておけばよかったんだよ。
0879デフォルトの名無しさん
NGNG解決したなら、おせーて
0880デフォルトの名無しさん
NGNG0881デフォルトの名無しさん
NGNG10000桁2進数→10進数ってな感じの
0882デフォルトの名無しさん
NGNG君、本屋に行って基本情報の参考書の
一番最初の章の一番最初の項目でも
読みなさい。
0883デフォルトの名無しさん
NGNG人間が脳内変換する分には参考書の方法で良いけど、
プログラムのロジックとしてはまずいんじゃないの?
0884デフォルトの名無しさん
NGNGたいていサメンションを用いた記述変換公式が載っているかと。
0885デフォルトの名無しさん
NGNGお騒がせしました。
0886デフォルトの名無しさん
NGNG> たいていサメンションを用いた
サメが住むマンションとか？
0887デフォルトの名無しさん
NGNG10000桁2進数をそのままの精度で変換したかったらgmpかrubyでも使うかな
何にせよ多倍長数演算の除算と剰余の実装と同じことをしないと
0888デフォルトの名無しさん
NGNG0889デフォルトの名無しさん
NGNG0890デフォルトの名無しさん
NGNG>>887
足算だけ実装すれば大丈夫ですよ。
a=1
b=0;
を初期値にして
2進数で下の桁から見ながら
２進数のその桁が1ならb=a+b;
その後、 a=a+a;
0891デフォルトの名無しさん
NGNGデータ構造として10進文字列で持つってこと?
それなら10進の全加算器を書けばいいわけだから納得。
0892デフォルトの名無しさん
NGNGa1,a2,a3....anがあったとして、
それぞれ
a1<a2....<an
が保証されているとする。
この時
下限minと上限maxが与えられて
min<ai<max
となるような
すべてのiを求める最速のアルゴリズムを考えているのですが。
具体的には
1,3,5,6,7,9,10,11,13,16
という数列があった時
最小4
最大10の時
5,6,7,9を返すという処理です。
DBのbetweenのアルゴリズムなんかが参考になりそうです。
誰か興味がある人議論しましょう。
今考えているのは
線形リストで数列を保存し
それらをBTREE（ハッシュでもいい）にマッピングして
minとmaxを検出して、ぶっこ抜くのが一番速いのではと考えています。
0893デフォルトの名無しさん
NGNGhttp://members.goo.ne.jp/home/madcap0
0894名無し＠沢村
NGNG出発点 (0,0,…,0), 吸収点 (1,1,…,1) の
n次元超立方体上の対称量子ウォークの
吸収時間は Tr Xn - 1 で与えられるんだよ。
ここで Xnは方程式の解となるんだよ。わかるか？
おれはいまそういう簡単な研究に取り組んでいるんだよ！！！
0895デフォルトの名無しさん
NGNGそれで研究になるのか？
0896デフォルトの名無しさん
NGNGおまいは自分の書いていることがわかっているのかと小一時間(W
0897デフォルトの名無しさん
NGNGなぜ？
0898デフォルトの名無しさん
NGNGなんか必死だな・・・
0899デフォルトの名無しさん
NGNG普通の方法
数列を 配列に入れておいて、min max でバイナリ検索し、アドレスを求め
挟まれた区間を取り出す
0900名無し＠沢村
NGNGおまいらよ、量子重ね合わせの状態とは何かわかるか？
まあくだいていえば、一台の車が右向きに走っている状態と左向きに走っている状態が同時に成立しているということよ。
だが、おれらが実際見ると、車は右向きか左向きかに固定して走ってるだろ？それは観測することによって、重ね合わせの状態のうちのひとつが固定するからよ。
おまいらよ、重ね合わせの状態のうちのひとつがどれに固定するかは、重ね合わせの係数によって決まるのよ。おまいらよ、重ね合わせの係数は複素数よ。複素数の勉強をしてみろ？
おまいらよ、量子PCでいう演算とは、この量子重ね合わせの状態を担う物理系に対してに対して、パルス電波を与えることよ。
いままでのPCでは4bitで表現できる16の状態のうち一つについて1回づつ演算を行い、合計16回計算して16通りの結果を出力してたが、量子PCでは4bitで表現できる16の状態を同時に実現している重ねあわされた量子状態に対して1回の演算を行い、結果を出力するんだよ。
当然処理bit数が増えるほど、量子PCの威力は大きくなるわな。だから並列処理よ。
だが、おまいらよ、その演算結果を見ようとすると、重なり合った状態のうちの一つしか見れないだろ？
この問題を解決するものとしてShorのアルゴリズムというのがあるよ。
Shorのアルゴリズムは量子PCの教科書には必ず出てくる有名なアルゴリズムだから、見てみろ？
おまいらよ、このようにこれからのプログラムは量子の時代よ。
おまいらも量子に取り組んだらどうだ？量子でないプログラミングなんて意味ねーよ！
0901デフォルトの名無しさん
NGNG0902デフォルトの名無しさん
NGNG0903山崎渉
NGNGﾋﾟｭ.ｰ ( ＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
＝〔~∪￣￣〕
＝ ◎――◎ 山崎渉
0904デフォルトの名無しさん
NGNG0905デフォルトの名無しさん
NGNG量子コンピュータの登場は沢村が死んでからになります。
0906デフォルトの名無しさん
NGNGわからないことあったらここで訊いていいから
0907デフォルトの名無しさん
NGNG（ABCDは0または1の任意のビットとする）
0000ABCD
を
A0B0C0D0
に変換するスマートな方法はないものでしょうか？
今のところは、左シフトもしくは加算でAならAだけをとりあえず目的の位置に移動したのち&でゴミを除去、
というのをビットの桁数ぶんだけ行うという地道な方法しか思いつかない状態です。
0908デフォルトの名無しさん
NGNGchar c = ( b&0x08 ? 0x80 : 0x00 ) |
( b&0x04 ? 0x40 : 0x00 ) |
( b&0x02 ? 0x20 : 0x00 ) |
( b&0x01 ? 0x10 : 0x00 );
こんなんでどう？
0909デフォルトの名無しさん
NGNGa = ((a & 0x08) << 4) | ((a & 0x04) << 3) | ((a & 0x02) << 2) | ((a & 0x01) << 1);
0910たぶん
NGNGa := ((a shl 2) and $30) or (a and $03) ;//AB00CD
a := ((a shl 1) and $88) or (a and $22) ;// (AB00CD0 and 10001000)+(0AB00CD and 00100010
0911たぶん
NGNG00000000abcdefgh -> 0000abcd0000efgh ->00ab00cd00ef00gh ->a0b0c0d0e0f0g0h0
てな感じに処理したいから適当に
0912デフォルトの名無しさん
NGNGa[0], a[1], a[2]・・・a[n-1]
b[0], b[1], b[2]・・・b[m-1]
があるとして、これらの数を配列c[0]～c[n+m-1]に
効率よく(n+mに比例する時間で)昇順に蓄えるには
どのような方法が考えられるでしょうか？
0913デフォルトの名無しさん
NGNGsort -m のような方法
0914デフォルトの名無しさん
NGNGマージソート (>>913 と意味は同じ)
0915デフォルトの名無しさん
NGNG0916名無し＠沢村
NGNGマージソートはマジ（真剣）にソートするという意味だよ。
これは本当だぞ！
ちなみにバブルソートはバブルの時代にはやったソートという意味な。
0917デフォルトの名無しさん
NGNG0919名無し＠沢村
NGNGおまいらよ、intのことをインテグラていうだろ？
あれはもともと積分記号のことよ。
0920デフォルトの名無しさん
NGNG0921デフォルトの名無しさん
NGNGhttp://anzu.sakura.ne.jp/~kuga/wol/
２ｃｈスレ
http://game3.2ch.net/test/read.cgi/mmominor/1053536167/
0922デフォルトの名無しさん
NGNGインテグラルじゃねーの？
0923デフォルトの名無しさん
NGNG0924デフォルトの名無しさん
NGNGhttp://anzu.sakura.ne.jp/~kuga/wol/
２ｃｈスレ
http://game3.2ch.net/test/read.cgi/mmominor/1053536167/
0925デフォルトの名無しさん
NGNG0926デフォルトの名無しさん
NGNGそれよりアルゴリズム体操しってるか
面白いぞ
0927デフォルトの名無しさん
NGNG0928デフォルトの名無しさん
NGNG0929デフォルトの名無しさん
NGNG0930デフォルトの名無しさん
NGNGそう
アルゴリズム体操は一人でやってもつまんないよね
そんな一人ぼっちには律動体操がおすすめ
0931デフォルトの名無しさん
NGNGttp://www.nhk.or.jp/sch/sch2002/schoolpro/youho/pitagora.html
0932デフォルトの名無しさん
NGNG移動してたよ
ttp://www.google.co.jp/search?q=cache:LwzrvbrtNZEJ:www.nhk.or.jp/sch/sch2002/schoolpro/youho/pitagora.html+&hl=ja&ie=UTF-8&inlang=ja
0933デフォルトの名無しさん
NGNGしてみたんですが、問題作成アルゴリズムの見当が全く付きません；
どなたかクローン作った事ある方いらしたら大まかでよろしいので
教えて頂けませんか。。。
0934デフォルトの名無しさん
NGNGWindowsのフリーセルで、ゲーム番号の指定で-1か-2と入れてみな。絶対に勝てないから。
0935デフォルトの名無しさん
NGNGアレ以外は全部解ける様に作られてるわけで。
0936デフォルトの名無しさん
NGNGランダムに配置した場合にとけない場合があるかどうかって証明済？
0937デフォルトの名無しさん
NGNG例えば、 -1・-2
乱数でばらまいて出る事はまずあり得ないけど。
0938デフォルトの名無しさん
NGNG今は、全部の行を配列に読み込んで、
その配列内をループして検索してますが、
ファイルの行数が300～500くらいあるので時間がかかります。
もっと早く検索する方法ってあるんでしょうか。
0939デフォルトの名無しさん
NGNGどんなレコード構造で、どんなデータを探したいのか書け
0940学生
NGNG----
データ(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 を求めればいいことはわかりました．
しかし，この先がわかりません．
最小自乗法の式の導き方はわかったのですが，
今回のやり方では偏微分の式の中に絶対値が入ってしまっているので，
どうしたらいいかわかりません．
ヒントください．
0941デフォルトの名無しさん
NGNGマルチポスト非常にうざい。
氏ね。
0942デフォルトの名無しさん
NGNGttp://pc2.2ch.net/test/read.cgi/tech/1053963794/933-
0943デフォルトの名無しさん
NGNG0945デフォルトの名無しさん
NGNG登録日(yyyymmdd),姓,名,姓ふりがな,名ふりがな,性別,年齢,E-Mail,電話番号
検索というより、ソートと抽出です。
全行を姓ふりがな、名ふりがなの値を利用して、五十音順（文字コード順）にソート。
その後、
性別（男、女、すべて）
年齢（20歳以下、30歳以下、40歳以下、すべて）
の条件に合うデータを抽出したいと考えています。
0946940
NGNGこっちのスレッドのほうが質問の内容に適していると思い，
こちらに書き込みさせていただきました．
すいません．
0947938
NGNG0948デフォルトの名無しさん
NGNGワラタ
最高だ
0949デフォルトの名無しさん
NGNGもう遅い。自分で解決するんだな
0950デフォルトの名無しさん
NGNG検索するキーごとについて予めソートしておく。
それぞれのキーについて二分法で探索し、得られた結果の共通部分をとる。
0952デフォルトの名無しさん
NGNG>>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
許してくれよ
0953945
NGNGあらかじめ、インデックスを作成しておくということですね。
全部の行を読むのは仕方ないにしても、検索処理は早くなりそうですね。
データファイルの更新日付を見て、更新されていなければ現在のインデックスファイルを
利用して、更新されていればその場でインデックスを作り直すというのがいいんでしょうか。
0954デフォルトの名無しさん
NGNGインデックス再構成のスケジュールは用途に応じて決めるべし。
オンデマンドで再構成だと応答の遅延が実用的でないかもしれないし、
更新が頻繁だとロックする必要がある。
検索が定型ならインデックスのインデックスを更に作っておくと早い。
例えば年齢に関するインデックス(それはレコードへのポインタの配列だろう)の
何番目からがn歳以上なのかをインデックスしておくと、検索の必要がない。
ただし、この配列の共通部分の計算がボトルネックになる場合は、
ソートせずにビットマップで持っておく。
例えば age[10] は i 番目の人が10歳であるときに age[10][i] = 1 であり
そうでなければ age[10][i] = 0 であるようなビットマップ。
これらのビットマップを年齢や単語などの数だけ用意しておき、
合致するデータをマスクとの積によって計算しビットマップの束として得る。
最後にこの束についてビット積をとることで求めたい共通部分が出る。
ビットマップ演算を bitfield で出来るのでtune-upしやすい。
また、定型の検索についてはマスクとの積を予め行なっておくことで、
要求時には共通部分をとる操作だけで済む。
googleなどで使われているのはおそらくこの手の方法じゃなかろうか。
0955デフォルトの名無しさん
NGNGってでました。助けて下さい。
0956デフォルトの名無しさん
NGNG意味がわからん
0957デフォルトの名無しさん
NGNG寡聞にして縮小法というのを知らないのだが、
Hoareのfindアルゴリズムがそれになっていないかな？
0958デフォルトの名無しさん
NGNG関節部の座標を求めるアルゴリズムってなんでしたっけ？
わかりづらくてすんません。
0959デフォルトの名無しさん
NGNGインバースキネマティクス
0960958
NGNG0961デフォルトの名無しさん
NGNG何かいい方法有りますか？
0962デフォルトの名無しさん
NGNG意味がわからん。
2次元空間で、その領域が直線のみで囲まれているということか？
0963デフォルトの名無しさん
NGNGもしかしてこんなものをお探しですか？
http://www.google.co.jp/search?q=Ray-Intersection+Method&lr=lang_ja
0964デフォルトの名無しさん
NGNGすみません。そのとうりです
0966デフォルトの名無しさん
NGNGありがとうございます。
でも、この方法だと半無限線の方向が問題になると思われます
仮に半無限線を＋の水平方向にした場合
********* **********
* * * *
* * * *
* × ******** *
* *
* *
* *
*************************
***********
* *
* *
* × *******
* *
* *
* *
*****************
上は交点３、下は交点２ですが
どちらも領域内部です
0967デフォルトの名無しさん
NGNG0968デフォルトの名無しさん
NGNG************ **********
* * * *
* * * *
* × ********** *
* *
* *
* *
******************************
************
* *
* *
* × *****
* *
* *
* *
****************
半無限線が水平で作成した場合
上は交点３、下は交点２ですが
どちらも領域内部です
0969デフォルトの名無しさん
NGNG0970デフォルトの名無しさん
NGNG0971デフォルトの名無しさん
NGNG0972デフォルトの名無しさん
NGNG0973デフォルトの名無しさん
NGNG0974デフォルトの名無しさん
NGNG半分、無限の線
>>973
無限の線
0975デフォルトの名無しさん
NGNG「半直線」・「半無限～」は、片側が端点で、もう片方が無限。
「線分」が、両方に短点を持つもの。
0976デフォルトの名無しさん
NGNG短点 → 端点 でした。
端点って辞書に載ってないのね。専門用語だから？それとも誤用？
0977デフォルトの名無しさん
NGNGどっかの業界の隠語？
0978デフォルトの名無しさん
NGNG0980デフォルトの名無しさん
NGNG＞方式１ 交差回数法: 点qから直線を引き、多角形と何度交わるか
＞方式２ 巻付判定法: 多角形をゴムに換えたら点qに巻付くか？
＞ ＝点qから見て多角形の線分を順に追いかけてゆくと１回転以上するかどうか
とあって、サンプルコードまで付いてるじゃないか。よく見てみなさい。
＞方式１ 交差回数法:y軸と交わった時の符号が正ならインクリメント
＞ 線分が y軸と交わるかどうかは 線分の始点終点のx座標の符号が違うかどうか
でサンプルコードはこうだ
＞ if ((rx<0)and(nx>=0)) or ((rx>=0) and (nx<0)) then begin
この部分で水平線はひっからないだろ？
0981デフォルトの名無しさん
NGNGこれは、方式２のサンプルですよね。
良く解らないですが（頭悪いので）、サンプル手に入りました。みなさんありがとうございました
0982デフォルトの名無しさん
NGNG１も２も考え方は違うけどコードは殆ど同じになると書いてあるぞ
レス数が950を超えています。1000を超えると書き込みができなくなります。