アルゴリズムオタク

アルゴリズムを考えるのが好きな人、自分以外にいませんか？
エレベーターを待っているときは、動きを制御するアルゴリズムを考えたり
既存のサブルーチンのアルゴリズムを考えたり、ゲームをやってても敵の
動きのアルゴリズムを考え、ストーリーなどは全く頭に入らない
愛読書は「アルゴリズムとデータ構造？」
言語なんて関係ない！アルゴリズムが好き！

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

アルゴリズムは、ここのサイトがくわしくて参考になる
ttp://sidhes.hp.infoseek.co.jp/alg3.htm

クヌース先生著の聖書か？

はよアルゴリズムについて語れ>>1

よし、じゃあまずものすごいかっきてきなアルゴリズムだ。
x = x ^ y;
y = x ^ y;
x = x ^ y;
これで x と y の値がいれかわるのだ！すごい

>>6
http://www.dd.iij4u.or.jp/~okuyamak/Information/xor_fixed_swapping.html

>>6
これが真に役立つ場面ってなかなかないんだよねぇ。
俺がいままでやった中ではフィボナッチ数列を求めるプログラムぐらい。
もっともそのまんまの形じゃなくて

  x = x +y;
  y = x -y;
  x = x -y;

こんな形をベースにして。ちなみにそのフィボナッチ数列を求めるプログラムはこんな感じ。

  int x = 1;
  int y = 0;
  for(int i = 0; i < 10; ++i) {
    printf("%d\n", x);
    x = x +y;
    y = x -y;
    //x = x -y; この二つの行は相殺できるのでコメントアウト
    //x = x +y;
  }

さっき、国会でやった小泉兄貴凄かったです！ガチムチの嘉朗兄貴がイット連呼で
インパクにぶちこまれ首振ってました。俺も掴まされてｶﾞｾﾈﾀ食らい無様に
醜態さらしました。懲罰動議出されたときは一瞬引いたけど、兄貴の「いやなら
辞めていいんだぜ！」の一言で覚悟決め、生まれて初めて謝りました。そ
の後、幹事長・党首も晒しあげられてビンビンの冷や汗、思いっきり謝り派手に脳無し
ﾀｹﾍﾞの顔に飛ばしました。スッゲー男らしく気持ちよかったです。また行くとき
カキコして下さい！帰ってからＮＨＫのニュース見て、また感じまくってます！

>>8
似たようなのでユークリッドの互除方が好き

ネタすれの乱立ｳｻﾞｽ

Introduction to Algorithmsを解説してくれ……とは期待しないが、
解説してるどっかの大学のオンライン講義資料知りませんか。

遺伝的アルゴリズムや免疫アルゴリズムなどいろいろありますが
とっておきのを思い付きました。
「検便アルゴリズム」です。
みんなで熱く語り合いませんか。

quick sortで最悪のケースを避けるために
最初に粗くshell sortしておくと速くならんかな。
細かい部分はinsertion sortして。

>>14
marge sort使えって

margeじゃなくて
mergeだって

アルゴリズム中毒
略してアル中

>>17
おまい、それを言いたいためだけにこのスレたてたんか？！

>>13
おまいから、語ってみろよ

それはそうと、自己組織化のアルゴリズム教えてくれ

見つけたデータを配列の先頭に移す。
ただこれだけだ。

分けの分からん名前つけたがる奴ら多すぎ。

もうちょっと機能や用途を的確に表す分かり
やすいダイレクトなネーミングしろよ。

＞見つけたデータを配列の先頭に移す。
自己組織化という名前とどう関係あるのかさっぱり分からない。

一度ヒットした検索の結果を頭に持ってくるようなことは
ちょっと気が利いたやつなら普通にやるが、そういう用途
なのか？

絶対アル感＝あらゆる現象をアルゴリズムとして表現することの出来る能力

俺ゴリズム　＝　自分で編み出したアルゴリズム。だが実は再発明。
猿ゴリズム　＝　アルゴリズムと呼ぶには、あまりにも稚拙。

アルゴリズマー＝アルゴリズムの考案を生業としている人。

調べるより再発明した方が早い場合もある。ソースが無けりゃあ
再実装はさけられないしな。

早いかどうかはどうでもいいな〜
重要なのは楽しいかどうか
どうせ最終的にやることは変わらんしな

>>24
どっちかというと、アルゴリズミストという感じがするな。

>>26
調べる訓練を十分積んでないと、再発明の方が心理的に楽なんだよな。
しかしそれまでに研究されたアルゴリズム上の穴や欠点が反映されない罠。

【先進国アルゴリズム協会】
「先進国アルゴリズム協会」（通称：SAK）は北半球の国々による
アルゴリズムの研究を目的とした公的機関である。
世界から優秀なSEやプログラマが集められており、年に数回の学会を催している。
最近有名なのは、画像ファイルからそれがエロ画像であるかを判定するアルゴリズムである。
これにより、エロ画像掲示板等向けの巡回ソフトを開発する際に、
余計なネタ画像を避けてエロ画像のみを収集することができ、日米を中心としたIT先進国も注目している。

しかし、ネタ画像で十二分に性的興奮を覚える人間に対しての
不当な文化の押し付けであるとして、アジアを中心とした人権団体から非難が出ている。
これに対しSAK側は沈黙を決め込み、半ば強引な進め方が行われており、
人権団体では、日米主体のエロ文化が蔓延するのではないかと懸念している。

一部分に肌色のピクセルが集中していたらエロ画像の可能性が高いかな

グロ画像の可能性も大いに有り

エロ画像フィルタは既にあるが
赤ん坊の写真まで除去されてしまう

こっこのアルゴリズムヌケる………………………うっっ

↓heap sortで3回ヌケる

適当なスレがないのでここで聞いて見ます
あるコントロールを作ってこれは角ならその方面のサイズを
辺ならその辺を基準にした高さを
右クリックなら回転を
マウス操作で行おうとしてるんですが
マウス座標はXYなので回転後の伸縮幅の計算でわけがわからなくなってしまった
三角関数が入り組んでる状態で頭がいたいので
どっかにサンプルころがってないですかね？
あるいはスマートに共通の関数とかで処理する方法があれば教えてください

>>35
おまいの日本語がわかりにくい

回転移動の１次変換
ttp://www.geisya.or.jp/~mwm48961/kou2/linear_image3.html

着衣エロ、もしくは着色エロで対抗だ！

>>36
回転はできてます
例えば４５度左にすでに傾いていた場合、上辺をドラッグして左右辺の長さを変えるわけです
マウスの位置に上辺が来ないといけないわけですが
マウスのY座標から左上と右上の角の座標が知りたいわけです
これは単純にサイズ変更だけじゃなくて移動もしないといけません
この時に回転軸も重心を取ってるのでずれてきます
上辺がマウスに重なるように下辺は固定したまま上辺だけを移動したいのです

コントロールじゃなくて

ぜんぶ自前で線描画した図形にしたらどーかね

コントロールといっても回転なんか出来ないので全部自前の描画ですよ？
なにをゆっているのですか？

なんで計算できんのかわからんな

ではウォーミングアップからお願いします。

リストから重複要素を取り除いたリストを得るアルゴリズムをお願いします。
高速なのをお願いします。

>>41
じゃあもう少し要点をまとめるので答えてね
ある角度αで回転した四角形があります
左上角を(x,y)とします
上辺の中心を(x',y')とします
この中心をドラッグし移動するとマウスと上辺は交差する位置を維持します
下辺２点は固定です
この時いまマウスがいる座標を(x'',y'')とします
この座標と交差する上辺の左角の座標を求める計算式を提示してください

>>43
＞ある角度αで回転した四角形があります
どこを中心にどう回転したのか書いてないしな。
曖昧な情報を出してくる辺りネタとしか思えない。
もう帰っていいよ。

>>42-43
ほんとに聞きたいなら、その部分コード書いて、判らない所をコメントにして聞いてくれよ。

>>42　リストって言ってるのはホントのリストだな Delphi/BuilderのTListじゃないね？
　　ただ、どういうリストなのか構造が判るようなコードで書いてくれよ。
　　じゃないと単なるリストならアルゴリズムもクソもリストを全部辿るしか方法ないじゃない

>>43　判りにくい。コードで書いて

>>45
僕の考えた低速そうなアルゴリズムはこうです。

fun expMul nil = nil
| expMul (h::nil) = [h]
| expMul (h::rest) = h::expMul(cut(h,rest))
and cut (x,nil) = nil
| cut (x,(h::nil)) = if x=h then nil else [h]
| cut (x,(h,rest)) =if x=h then cut(x,b) else h::cut(x,b);

目当ての女の子画像を集めるアルゴリズムおながいします

>>47あ〜、それ俺もすげぇ欲しい
顔で判断するのか？

>>47
Google イメージ検索

>>44
重心って書いてるじゃんｗ
ばーか

>>判りにくい。コードで書いて
コードで書いたらもうほとんど答えでバグ広いだけじゃんｗ
ばかじゃねーの

// 重心を中心に回転済みの座標
function (mouse, leftup, rightup, leftbottom, rightbottom, kakudo){
　　// mousex mouse.y が (leftup.x leftup.y)-(rightup.x,rightup.y)の線分と交差するように
　　// leftup rightupを修正
　　// ↓
　　？？？？？？？？？？？
　　// ↑

　　return points
}
はいコードどうぞｗ

>>51
ならそれで質問者は解決するわけで、みんなハッピーだ

>>52
つまり、(leftup.x leftup.y)-(rightup.x,rightup.y)の線分と交差するのは、何？

mousex mouse.y が

むしろ解答するように見せかけた釣りとしか思えないｗ

線分と交差するのは2次元なら線分でなければいけないよ？

君には一生解答できないからいいよｗ

>>52
引き数の型が書かれていない
mouse, leftup, rightup, leftbottom, rightbottom,　はpoints　として kakudoは何？

それから leftbottom, rightbottom, kakudoはこの関数の動作に関係しないなら引き数にする必要はない
関係するならその説明をしないと意味がないだろう

>>57
あのさ、この板でこの手の回答の半分はオレなの。
オレが答えなきゃ、回答率は半分になるよ。

kakudoは現在の回転角0-360
points は変化後のすべての座標の省略

形なんか好きにしろｗ
角度計算する際の常識的な形ってやつがあるだろ
使うか使わないかもわからないのかお前は？ｗ

常識は人によって色々だ

オレはこの手の処理をするときは角度じゃなくて　sin/cos成分を引き数で渡す。　これはオレの常識

つまり、これは関数というより手続きなんだね？　それを表現してくれないといけない。
それで、入力としては　mouse, leftup, rightup, leftbottom, rightbottom, kakudo
出力は何？

想像としては、
　leftup, rightup, leftbottom, rightbottom　の相対関係を固定して kakudoで回転させたいように思うが mouseはどういう拘束条件？

(leftup)-(rightup)が点(mouse)を通過する
角度reftupは９０度rightupは９０度を固定された
leftupとrightupを入れ替えて
返す
kakudoha現在の座標がその角度で回転されたものだって意味じゃぼけ

>>62
判った事は
mouse, leftup, rightup, leftbottom, rightbottom　が点座標
kakudo が　現在の座標の回転角　ここまでは判った

現在の座標の回転角とは何？

90度というの何と何の角度？
もしかして長方形?　長方形なら2点だけでいいよね？

長方形だって言ってるじゃんｗ
引数の数がその後の計算に影響するとは思えないんだが
自閉症なみのこだわりですねｗ

いや、未熟ですまん。

じゃ、ムダな、2点を削除して　
(POINT mouse, POINT p1 , POINT p2 , double kakudo) にしよう
左上p1と右下p2の　kakudo で回転された　長方形があるとする。

このmouse上の点が上辺になるように　移動変換したい　というのが疑問かい？

課題をもう少し変形する。

W
┌┐
││H
└┘
POINT mouse ,POINT center , doubke kakudo , double W , double H

center が 重心の位置、kakudoがこの図形の回転角

点　mouse にWが一致するように center を平行移動して返す関数を作れ。

でいいの？水平移動優先？　垂直移動優先？それとも最短移動距離優先？

そんな感じ

まてよ、
＞　この座標と交差する上辺の左角の座標を求める計算式を提示してください

これを翻訳すると

　このmouse座標上に上左点が来るように　center を設定せよ

これでいいんじゃないの？

>>66
は違う気がする

.>>68
アーぜんぜん違うｗ

回転してない長方形があって上をひっぱると上に伸びるだけね
下は固定
これはその長方形を回転させた状態のときに同じく上にひっぱるわけ

問題が
　W
┌┐
││H
└┘
POINT mouse ,POINT center , doubke kakudo , double W , double H
center が 重心の位置、kakudoがこの図形の回転角
mouse座標上に回転後の上左点が来るように　center を設定せよ

だとすれば　
center.MOVE(POINT(-W/2,+H/2)).ROTATE(kakudo) == mouse を解けばいい

center.MOVE(POINT(-W/2,+H/2)) == mouse.ROTATE(-kakudo)
center == mouse.ROTATE(-kakudo).MOVE(POINT(W/2,-H/2))
　
という答えだったけど、これは問題が違うわけね。
ちょっとまってね

　W
┌┐
││H
└┘
POINT mouse ,POINT center , doubke kakudo , double W , double H
center が 重心の位置、kakudoがこの図形の回転角

mouseを重心の位置が原点になるように回転移動逆変換する
rmouse=mouse.ROTATE(-kakudo).MOVE(-center)

問題：
rmouseのy座標の位置が上辺と一致し、下辺座標が変化しないように centerとHを変更せよ

って、事で、もう答え書く必要はないでしょ

コレでレスが無いって事は、オレやり遂げたのか？

自分を祝福したいよ。

その方法はすでに考えてた
その説明だけじゃたりんがね
回転演算を３回しないといけない
書いててもスマートじゃないからなんかいい方法ないものかと聞いてみただけ

ありがとう。　
どっちかいうと問題が秘密で問題に到達するまでのゲームだったね。　けっこう面白かった。

問題が判らないから表現方法を模索した結果、こうなっただけで
実際のデータとしては四角形に固執せずに、任意多角形の問題として
マウスで図形を動かす＝マウスの動きに対して何を拘束して何を追従させるかという
問題と捕らえて、一般的に解かせる方がいいよ。
図形を動かす方時のコストなんてしれてるから、多少リッチにＣＰＵコストをかけさせてもいい

で、ここには単なる長方形ではなくて、この長方形にビットマップのようなものを貼り付けるんだろ？
だったら、そっちのコストがずっと大きいから

【エロゴリズム】
与えられた情報を湾曲させ、猥褻な情報に変換するアルゴリズム。
文字列の変換に関するエロゴリズムが多く考え出されているが、
画像や音声に関してのエロゴリズム考案にもSAKは力を入れている。

文字列変換の例：
　　　愛されて10万戸→愛されて汁マンコ
　　　私の父はSEです→私の乳はSEです

ピタゴラスイッチ

>>75
「アルゴリズムオタク」というスレにふさわしい回答ではないな。
どんなささいなコストも、なんらかのアルゴリズムで回避できるならしなきゃ。

>>76
>愛されて10万戸→愛されて汁マンコ
>私の父はSEです→私の乳はSEです

ただ下品なだけじゃん。
お前ごときがエロゴリズムを語るのは１０年早いわ！
童貞からやり直せ！

やり直すまでもないに一票

>>78
>「アルゴリズムオタク」というスレにふさわしい回答ではないな。
質問も回答もｽﾚ違いだろ阿呆。

結局僕はどうなりましたか？

>>46
みんなの知らない言語みたいだから、説明を入れてみたらどう？

head::body
はリストで、例えば
[1,2,3,4,5,6,7]とすると、
要素head=1
リストbody=[2,3,4,5,6,7]
を意味します。
nilは空リストです。

あ、>>47のラストの行の引数(h,rest)のところ、
正しくは(h::rest)でした。

>>42
結局、ソートされたデータなわけ？　ソートされてるなら先頭から順に見るだけでいいし
そうでないなら、ソートしつつ削除するような方法になると思うよ

何この糞スレ？

>>86
リストの順序を保ちたい場合は考慮されてますか？

>>88
そもそも　リスト構造のままソートするのは効率が悪いから
リストとは別にポインタ配列としてソートする事になるだろうね

>>89
実装の話ではなくアルゴリズムの話の筈ですが…

普通に大学1回生のときに単方向リストで重複要素を除く機能つきのマージソート作った。
比較するときに同一の場合は除去すればいいだけだからソートの延長で考えればいい。

そういや大学のときC言語の授業で
配列とポインタの練習としてスタックとキューを実装しる、みたいな問題が出て
再配置がﾏﾝﾄﾞｸｻｰだった俺は循環キューに思いいたったわけだが、
それが俺の始めての「車輪の再発明」だった。
懐かしい。

【積年の】旦那にしてる密かな仕返し【恨みじゃー】
http://human5.2ch.net/test/read.cgi/ms/1141694640/

8 名前：可愛い奥様[] 投稿日：2006/03/07(火) 11:05:23 ID:8dtluKkp
夫の歯ブラシで洗面所の排水溝掃除。
洗面所をビショビショに汚した罰だ。

20 名前：可愛い奥様[age] 投稿日：2006/03/08(水) 00:40:17 ID:pRrk6A21
前に頭きた時あって
１度だけ歯ブラシで肛門カキカキしちゃった

22 名前：可愛い奥様[] 投稿日：2006/03/08(水) 01:27:12 ID:gU5mHc7J
よかった。どこのお宅も同じようなことしてて。

24 名前：可愛い奥様[] 投稿日：2006/03/08(水) 01:36:35 ID:SSSFsTqE
そうそう、ヘンなモノはダンナのお皿へ直行だよね。

41 名前：可愛い奥様[] 投稿日：2006/03/08(水) 11:55:18 ID:sjj+/60Q
見てるだけで気が晴れるな！
皆さん、頑張ってね！

42 名前：可愛い奥様[sage] 投稿日：2006/03/08(水) 20:33:51 ID:Ju2N1s7+
年金分割が楽しみじゃのう

63 名前：可愛い奥様[] 投稿日：2006/03/10(金) 08:55:20 ID:qLfJYpJR
家族で密かにはぶっている。

男性は肉体が汚く、精神が美しい傾向がある。（気に入らない相手に肉体的攻撃を加える⇒精神的攻撃も加える男は猛者）
女は肉体が美しく、精神が汚い傾向がある。（気に入らない相手に精神的攻撃を加える⇒肉体的攻撃も加える女は猛者）
女は隠れて悪事をする。気に入らない女子を便所でボコったり、便器舐めさせたり、男の友人を使ってレイプ、仲間外れにしたり。陰口、嫉妬。
女は対人関係において、この汚い性格を隠そうとするため、外面が非常によくなる。（猫かぶり）
男性諸君は外面に騙されないように気を付けて下さい。

アルヲタ

アルゴリズム体操

>>91
考えられる限り高速な方法で。
普通になら作れます＞＜

>>96
>>89
ソートしてあればO(n)で重複を取り除けるし、
配列にリンクポインタへのポインタ相当のものを格納すればリストそのものの順序を変える必要はないし
配列ならデータの種類によっては(フラッシュソートなど)O(n)で出来るソートアルゴリズムが存在する

TextSS　のWindowsXP(Professional)64bit化おながいします

もしくは64bitにネイティブ対応したテキスト置換ソフトありますか？

では、荒し検出アルゴリズムを。

100get!!

>>99
簡単だ

>>101
うｐして

if(名前!="デフォルトの名無しさん"){
　　for(;;)MessageBox("荒らしだーーーーーーー！！！！");
}

>>103が荒らし。

puts(レスの内容);
puts("これ荒らし？[y/n]");
if(getchar() == 'y') for(;;) puts("荒らしだーーーーーーー！！！！");

今、プログラマの数学って本を読んでるんだけど
そこに出てくるハノイの塔の再帰的処理が理解できない。

どこを繰り返し処理してるの？
パターンがある事に気付けないんだけど。

ちなみに階乗のアルゴリズムが再帰的だとは理解できます。
5!=5*4!
4!=4*3!
3!=3*2!
2!=2*1!
1!=1*0!
0!=1

本にはハノイの塔を解く手順、
すなわち３本の柱が左からA, B, Cとあって、
n枚の円盤を柱xから柱yへ柱zを利用して移す手順
をＣ言語で書いてある。

#include <stdio.h>
#include <stdlib.h>

void hanoi(int n, char x, char y, char z);

void hanoi(int n, char x, char y, char z)
{
if(n == 0){
//何もしない
}
else{
hanoi(n-1, x, z, y);
printf("%c->%c, ", x, y);
hanoi(n-1, z, y, x);
}
}

int main(void)
{
hanoi(6, 'A', 'B', 'C');
return 0;
}

解き方を見てから強いてパターンを見つけると
１回目は、必ずAとCの間でやり取りをする。
２回目は、必ずAとBの間でやり取りをする。
３回目は、必ずBとCの間でやり取りをする。
で、また１回目に戻る。

でも、例えば１回目はAとCでやり取りすることは分かっても
どっちからどっちへ円盤を移すかはどうしてアルゴリズムから分かるの？
人間は「"小さい円盤"の方から"大きい円盤"の方へ」って
目で見て判断できるけど、コンピュータはできないのに。

>>106
ディスクN-ディスク1をバーAからバーBに移動しようとしたとする。
その行程は、
・ディスクN-1-ディスク1をバーAからバーCに移動
・ディスクNをバーAからバーBに移動
・ディスクN-1-ディスク1をバーCからバーBに移動
と書ける。
関数形式で書くとすると、
void moveDisk(int n, Bar a, Bar b)
{
printf("ディスク%d を バー%dからバー%dに移動\n", n, a, b);
}

void hanoi(int n, Bar a, Bar b, Bar c)
{
if (n > 0) {
hanoi(n - 1, a, c, b);
moveDisk(n, a, b);
hanoi(n - 1, c, b, a);
}
}
こうなる。
Nが3辺りのときの振る舞いを自分で追ってみればよく判ると思う。

・n=5を解くには

|54321
|
|
↓(n=4を解く)
|5
|
|4321
↓
|
|5
|4321
↓(n=4を解く)
|
|54321
|

・n=4を解くには(以下略)
...
・n=1を解くには

>>99
アルゴリズムを考えるアルゴリズムがわかってないはずだから無理だとおもいまーす。
荒らすのはそのアルゴリズムかどうかもわからないんだっけ、
わかってるんだっけ？

日本語でおｋ

>>1
アルゴリズムマニアの日記
http://d.hatena.ne.jp/higotakayuki/

だれか突撃しろ

は？

物凄い簡単なものなのかもしれませんが分からないので質問。
ｎ本のマッチがあって、一回に１〜３本取れる。
自分は先手で、最後の一本をとったら勝ちになる。
必勝のアルゴリズムを教えてください。

残りが4の倍数になるように取る

残りが3i+1になるように取る

>>118
（ ・д・）……

>>118
残り7で相手が3取って終了。

>>120

マッチ棒を取った本数がポイントになるが、
最後の一本は-10点とかだったらどうだろう?

>>122
その場合は最後の一本を取ったら負けというルールとほぼ等しいので、
4の倍数+1になるようにすればいい。

>>123
たとえば、1000の棒を取る時にはどうよ？
相手がずっと3取ってたら負けね？

お互いに3本づつとっていって、残り６〜７本あたりから勝負かな
勝ちパターン考えるのはメンドクセ

意外と深いな。
最後の一本をとったら負けというのなら簡単なんだけど。

>>124
すまん、マッチ棒という前提を読んだ段階で1000本は想定外だった。

アルゴリズム初心者には難しいのか？orz
もう少し頑張ってみます。
フローも書かないと・・・orz

ゲーム理論に帰着されそうな予感

前のターンまで同数の場合は、21を取った方が勝ちか引き分けに
なるんだけど、自分が21を取る為にそれより前のターンで本数調整
したら勝てなくなるから、結局最初の本数で決まりそう。

　　　　　　　　　 ／￣￣￣￣￣￣￣＼　　　　
── ＝ ニ 　 /=､｡｡｡｡｡｡｡｡｡｡｡｡｡｡｡｡ｒ=､ヽ
　─ ＝ニ三　（◎ ヽ-─────（◎ 　)
　　　　ノ◎､　 |＼　 ＼　　 　　　　/　 ／ |　 /◎､　
　　　(_,ｒへ　｀ｿ　 /> ◎) 　　　　 (◎く| 　レ'　,ｒへ )
─ ＝ ニ　 ＼◎'/　／　　　　　　 ＼ ヽ､◎／
　　　　　　　　 ノ ／　　　　　　　　　　＼ ヽ　　　
　─ ＝ニ三 ( ◎(　　　　　　　　　　　　 ) ◎)
　　　　─ ＝　 ｰ､_ら　　　　　　　　　 ⊂､_,ｒ´

このマシンがどうして前に進むのか教えてください。
普通だったら両方から押し合いへし合いして動かない気がするのです。

それは、コックリさんの原理だよ

この場所に秘密があるんじゃないかな
http://maps.google.com/maps?t=k&om=1&ll=37.401094,-116.868725&spn=0.006162,0.009291

>>133
ベームベーム？

右側の足は後ろ歩きすればいいんじゃね？

>>88
リストソートはスキップリストで決まりかな。

アルゴリズムの仕様を記述する言語作れないかな。

それ日本語でよくね？

いや、コンピュータで扱えるようにしたらなんかいいことあるかと思って。
たとえば実装が仕様にあってるかどうかテストできるとか。
あとアルゴリズムのデータベースつくってその言語で検索とかできないかなーと。

実装の検証ってどの程度のものを想定している？
それによって話は全然変わってくるんだが．

入力データもある程度自動生成してくれて、出力結果も検証してくれるやつ。
まあ完璧なテストは無理だけどある程度のテストはできそう。

それは実装の検証じゃなくて入出力の検証だよね。
ユニットテストのすごいバージョンってことでいいの？

入出力が正しければ実装も正しいというのは間違いですか？
まあ、確かにユニットテストのすごいバージョンです。

同じ入力に対して同じ出力を得られたからと言って、
アルゴリズムが同一とは限らないわけで・・・
入出力を検証しても必ずしも実装が正しいかどうかは分からないよね。

例えば安定クイックソートの実装のつもりでテストをして、
実際に実装されているのはバブルソートだったとしても出力だけでは分からないはず。

>>144
複雑度のテストとして、要素数の規模を変えて数回テストし、
実行時間の変化を見てくれるとか、うーん、むずかしいかな。

クイックソートもバブルソートもどちらもソートだから区別する必要は無いと考えています。
入出力の仕様の定義だけ行う言語を作るのも意味はあるかと。
そのあとどんな実装を行うかはまた別の問題ということで。

一階述語論理で良ければ Prolog でいいんじゃないの?

ソートだってアルゴリズムじゃないか。
仕様を後付けしすぎ。

>>146
O(n log n) のソートと O(n^2) のソートは
質的に全然違うものなので、それを記述できない言語は
アルゴリズムを記述するには不適当。

>>149
よく考えてみたらアルゴリズムを記述する言語というのが間違いでした。
私がほしかったのは問題を記述する言語とでもいいましょうか。
アルゴリズムが満たさなければいけない条件を定義したかったのです。

>>150
わかってねえなあ。
「O(n log n) である」 ことを 「満たさなければいけない条件」 として
書けないと、全然意味が無いんだって。

「O(n log n) でないと破綻する入力」 みたいなのを自動生成
できりゃいいけどさ、そんなのは不可能だ。

スピードに関していえばソートのような良く研究されたアルゴリズム
は最適解がわかってますが、最適解がわかってない問題もたくさんある
わけですし、それほど重要とは思っていません。

>>152
研究用途ならそういう結論になるかもしれないな。
だが計算量を記述できなければ実用の道をほとんど閉ざすことになる。

スピードは実装ががんばればいい話であって、仕様には関係の無い話です。
どれくらい頑張れるかは不明な場合が多いのです。
私は仕様を書いたら即動くものができるというようなことは考えていません。
実装する際に何らかの役に立てばいいと思っています。

アルゴリズムの仕様を記述する目的でPASCALで不足する部分は何？

>>154
世の中にはスピードが問題になることも多々あるわけだが。
理論上は可能、ただし、処理に１０億年掛かります、とかね。

そもそも仕様が適当すぎ。荒らしに来たとしか思えない。

ていうかさ、作りたければ作ればいいじゃん。
このスレ(の住人)に何を求めてるの？

>>155
原理的にＰＡＳＣＡＬでかけないものなんて無いでしょう。
もうちょっと楽にならないかなという程度のことです。
>>156
スピードを仕様に盛り込んだとしても達成できなければ意味が無いのです。
たとえばソートをO(logn)でやれといっても無理な話です。
結局できることといったら存在する実装から一番いいものを選ぶだけなんです。
>>157
まあ、一緒になって考えていただければ。

計算量を実装が頑張ればいい話とかいってる時点で
このひとが全然アルゴリズムを理解していないことが分かる。

ですから、私が最初にアルゴリズムといったのが間違いで、
解くべき問題を記述したいのです。
ソートには色々な計算量のソートがありますが、目的はどのソートも同じです。
その同じな部分を扱いたいのです。

じゃあすれ違い。

つーか同じソートでも目的が違うから複数のアルゴリズムがあるんだが

>>158
>まあ、一緒になって考えていただければ。
情報を小出しにし、わけの分からない仕様を提示し、アルゴリズムの話ですらないのに
その上、出て来た意見を片っ端から否定しといて「一緒になって」も無いだろ

お前らみたいな低脳とホントに一緒に考えられるわけねぇだろ。
リップサービスと言う言葉の意味を考えてみたらどうだ?

ナタク…。俺はどうしたらいい？

きっと>>137は
0+0=0
0+1=1
1+0=1
1+1=0
だけであらゆるプログラムを作れるんだろうな。

おめぇら、形式的仕様記述について知ってる事を書け
http://pc2.2ch.net/test/read.cgi/tech/1013507313/l50

こういうスレが欲しかったんだろ？ さあ逝ってきな

浮動小数（例えば[3バイト符号付整数] × [2のn乗|nは1バイト符合付き整数]）を、
対応する十進数（例えば[4バイトBCD] × [10のN乗|Nは1バイト符合付き整数]）
に変換するのはどうしたらいいかな。

当然、与えられた浮動小数の符合付き整数部のMSBは1に、
結果のBCDの最上位ニブルは0以外に正規化（？）されているものとする。

8ビットマイコンのアセンブラ想定でよろしく。

アルゴリズムもクソもそのままやるしかないでしょ
どっちかいうと実装テクニックじゃない

>>169
アルゴリズムとそうでないものの違いは「俺様が関心があるかどうか」
の違いではないでしょうw

まあ愚直にやるっきゃないのは確かっぽいが

8bitなら、2^N = b*10^M のテーブルを作っておいて
a*2^N = a*b*10^M とやって正規化するくらいだね

アルゴリズム好きとかものすんごいうらやましい。

逆に趣味でプログラミングやってますとかっていうヤツのなかにも
希に「そこを自分で考えるのが楽しいんだろ」ていう部分を
メーリングリストや掲示板で「どうやったらいいんでしょうか？」とかって
訊いてくるヤツのことがサッパリ理解できない。

>>174
そこを自分で考えるのが楽しいんだろ？

>>175
そういうレスを返すヤツのことがサッパリ理解できない。

>>173
>>113

ドッキングツールバーの設計をやっているけれど、
なかなかいい構造が思いつかない。

>>178
こーゆーケースは理解できるし共感できる。

ところでアルゴリズムを相談するスレってどこ？

ここでいいよ

あげ

なあ、グランドにごっちゃに人集めて、
はい背の順に整列！
って時さ、
全員がクイックソート理解してたと仮定して、その通りに整列してもらうより
普通に整列させた方が速そうじゃない？


モデル化すると、要素全てが各々同時並列的に他の任意の要素の値を知れる場合
そして要素が同時並列的に移動できる場合

コンピュータモデルとの一番の違いはデータの移動のコストが低いことだな。

大雑把にソートした列に、後はデータ自身が自分の入るべき場所を見つけて両側のデータに対して
スペースを作るように要求する感じかね。
オブジェクト指向のいいテストケースになりそうだが。

>普通に整列
脳はだいたい基数ソートみたいなことをしているんだってさ

「普通に整列」の手順を考えてみる。

周りのオブジェクト全部をみて整列する人はまずいない。
だいたい自分がどのくらいの序列になるか予想して、整列の初期には近くにいる数人の
オブジェクトのうち同じくらいの序列になる物同士で小グループを形成し、グループ内での
序列を決定した後に他の小グループと合体、境界付近を調整する。
小グループ同士が合体したあとにオブジェクトが余っている場合も、自分の序列がどれくらい
かを予想してそこに近い部分集合の中から自分の序列を決定する。

つーわけで、段階的にマージソートと挿入ソートを同時多発的にやっているような気がする。

>>186
>同じくらいの序列になる物同士で小グループを形成し
これがマージソートと根本的に違うところ．

簡単のため小グループとして「背の低いグループと背の高いグループ」
を取って，それぞれで再帰的に計算してやることにする．

マージソートだと，それぞれをソートした結果をマージするときに
前半のトップと後半のトップを比較して云々とやらないといけなくて，
マージの部分の計算量が O(n) になり，合計として O(n log n) になる．

しかし，「普通に整列」の場合は前半のほうが後半よりも小さいと
わかっているので単純にくっつければよく，マージの部分の計算量が O(1) ですむ．
その結果，合計として O(n) でソートできるようになる．

スマソ，長々と書いていながら誤読してた．
自分の経験から小さい人は前，大きい人は後ろに行って，そこでソート
をやってるもんだと思いこんでいた．

その逆の近くに居る人たちから結合することを考えていたのか．申し訳ない．

＃多分それでも「合体」の部分で適当にオラクルが利いて O(n) になるとは思うが

自分がどの程度の背の高さになるかは把握してるとするなら、
最初の移動は粒度の荒いバケツでバケツソートってことになる。
バケツ内での並び替えはどうやってるんかな。

100人の場合と1000人の場合で実験してみないとなんともいえないが・・・

だんだんバケツが小さくなる

マジレスすると、

１）全生徒はそれぞれ「自分及び他人が（同年代の中で）どの程度の背の高さか」を感覚的に知っている。恐らくはクラスの背の順等の経験から。１０％程度の粒度で。
２）全生徒はそれぞれ個別に（＝同時に）自分が特定の他者より高いか低いかを判断してそれらしい位置に移動することが出来る。
３）数が多くなればなるほど、身長の近い者が逆順に並んでいても問題にしない。

以上の要因から、ＣＰＵ一個が無情報で正確にソートしなければならないことを前提としたアルゴリズムに時間的に優っているのである。

>>191
3)に関しては相手にお前何センチって聞けばいんじゃね

>>191
機械がやる場合、たとえば標準偏差を与えて記憶や経験の代わりに予想の根拠とすることは
できるような気がする。

n 人で整列するとして、

・頭が n 個あるので log n 時間で整列が可能。
・人間が寝ている場合には、　n 台のロボットを使って log n 時間で整列可能。

ただし、

n が大きくなってくると、入れ替えるために移動させるためにかかる時間の方が
支配的になってくるので、O(n) になる。

たとえば、探索の場合には、
線形探索や二分探索という位置決めがデータによらない手法に対して、
データの種類によって次の探索位置を変える内挿探索という手法がある。

３次元空間上に２つの直線があって、
もしその２直線が交点を持つなら、
交点を計算するアルゴリズムってどうなりますか？
２次元平面上での交点計算みたいに方程式作ってもうまくいかないんですが・・・
なんかヒントくれるとありがたいです。

方程式で解くんじゃないの？
直線A：(x(s), y(s), z(s))
直線B：(x(t), y(t), z(t))
とパラメータ表示して、連立方程式
x(s)=x(t), y(s)=y(t)
から s, t を求める。
ここで解があれば、さらにz座標の式にいれてすべての座標が一致するかどうか確かめる。

あ〜、なるほど。
先に2次元で解いておいて、3次元にしてもOKか見るわけですね。
なんか頭混乱してて、こんなこともわからなかったです・・・
ありがとうございました。

数学板で聞けば一発計算できる公式とか教えてくれそう

大学受験の頃は一発で出せる公式も勉強したかもしれんが、もう忘れたな。

忘れたなら何度でも導けばいい

俺なら
(最大値 - 俺の値)/(最大値 - 最小値)

で数直線上の何%くらいに位置するか検討をつけ、
この場合は身長の分布を思い出して、区間の人数割合を想像してから
自分の属する区間あたりにまず向かう。

適当に整列されて来たら
自分より背の高い奴がすぐ前にいればそいつの前に出る。

アルゴリズムの達人が集まってるスレはここですか？
質問なんだけど、BPマッチングっていうアルゴリズムって存在する？検索してもそれらしいのがヒットしないんだが

Bipartite Matchingかな

DPマッチングの読み間違いとか

クイックsortより速いソート挙げて

スーパーウルトラデラックスsort

基数ソート

バケツソート

あらかじめソートされたデータだけしか扱わないようにする

ソート済みリストをソートしようとしたら
もっとも速く処理が終る(もとと同じリストを吐き出す)ソートは？

>>211
挿入ソート、バブルソート
どちらも一回の走査で終了を検出できてO(N)

マージソートでは？

マージ部分で手を抜くと O(n log n)．
ただ，ちょっと賢くマージをすると O(n) になる．

ここで質問してもいいでしょうか？


記号列　S1={aabbbcccceefffggggxxxxyzzzz} S2={xxxyzzzzzzzzqqqqcceeff}　みたいなのがあり、
それぞれの記号列の中で一致している長さX(可変、無限に長くしたい)以上の部分列を全て挙げる

この例では、X=5としたら {cceeff}　{xxxyzzzz} を挙げる。

これを、できるだけ計算量とメモリを節約してやるアルゴリズムは？

それから、このアルゴリズム（この問題）には名前みたいなのあります？

名前があるか知らんが、ちょこっと考えたもの
S1とS2の半直線部分文字列を、マージ後ソートして比較する
メモリは、文字列を記憶するメモリ＋文字数×（sizeof(ポインタ)+記号列を特定するIDなど)
速度は、クイックソートでも使えば速そう

半直線部分文字列のソート後には
abbbcccceefffggggxxxxyzzzz(S1)
...
cceeff(S2)
cceefffggggxxxxyzzzz(S1)
...
xxxyzzzz(S1)
xxxyzzzzzzzzqqqqcceeff(S2)
...
zzzzzzzzqqqqcceeff(S2)
てな感じに並んでるかな、文字列がメモリ中にあればポインタだけソートすればOK。任意の長さの一致が全て判明する。

{ceeff}とか{cceef}とか{xxxyz}とかは解の候補にならないの？

>>215
S1,S2のSuffix Arrayを生成してからマージするような形で判定していけば良いと思う。
まぁ、ぶっちゃけ>>216のマージとソートの順序が逆になっただけだけど。

>>215
Xが何の長さなのかわからんし、何が一致しているのかわからん

総じて何を言いたいのかさっぱりわからん

すまん、「以上」を読み落としてた

意味はわかったが、アルゴリズムは全然思いつかない

マージしてソートってよくわからん。
とりあえずバカ正直な方法は

ａａｂｂｂｃｃｃｃｅｅｆｆｆｇｇｇｇｘｘｘｘｙｚｚｚｚ（s1）
ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃｃｅｅｆｆ　　　　　（s2_0）
・・・
　　　ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃｃｅｅｆｆ　　（s2_3）
・・・
ｃｅｅｆｆ　　　　　ｘｘｘｙｚｚｚｚｚｚｚｚｑｑｑｑｃ（s2_10）

と、一方の文字列をずらしていって、一致する部分を探すことかな。
初めに文字のパターンを調べて、例えば a, b といった文字は片方にしか含まれないから
そういう位置ではパターン検索を省略できるとかくらいかな。

すみません >>221 と同じく、>>216の方法 よくわかりませんでした。
221 だと計算量 は |S1|×|S2|×|短い方|　ぐらいなると思うんですが、
216 だともっと計算量減るでしょうか

>>217
それも解候補です。
本当は"極大"な解だけにしたいんですが、 今は全部出していいです。


例として aaabbbccc.. なんていうのを出してしまいましたが、
本当はもっとランダムな任意の記号列でやりたいのです。

まず、一方の文字列から「辞書」を作る
aabbbcccceefffggggxxxxyzzzz から
a: aabbb, abbbc,
b: bbbcc, bbccc, bcccc
　・・・
y: yzzzz
（説明のために5文字だけだけど、当然、最長パターンまで作っても良い）
次に、もう一方の文字列から、一文字読み込んで、
そこから始まる文字列パターンが「辞書」に登録されてるか調べる。

メモリは食いそうだが、総当たりで調べるよりは少なくなる気がする

>>222
処理時間の大部分はソートの時間、クイックソートを使うとして
O(N log(N)) Nは|S1|+|S2|
特殊な例外を除いて計算量は減る。
問題は、文字数×8バイト(32bitマシンで)のポインタ領域が必要なこと

http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/2200.c

マージしてからソートはよくわからなかったから
ソートしてからマージで書いた．きちんと証明してないから
正当性はよくわからん．

Suffix Array の構成は O(n) でできることが知られていて，
マージの部分も同じ文字列を何度も比較するのをやめれば
O( (n+m)*min(n,m) ) でできる．合計して O( (n+m) * min(n,m) )．

>>224
長い文字列の比較はそれ自身コストが高いということを忘れてない？

>>226
もしかして最後の文字まで比較してると思ってる？

最後まで比較せずに済むという保証はどこにもない。

>>216
は、n-gram統計における「長尾・森の方法」だな。
岩波のソフトウェア科学の15巻参照
100万字での任意長重複列挙が1秒(Pen-M 1.5GHz)ってとこ。
ソートは文字列専用のソートを利用(単純なクイックソートをちょいと工夫)

>>224や>>228のいう「特殊な例外」（たとえばS1とS2が等しかったり、S1が
S2を包含する場合)では計算量は他の方法並みに大きくなる。

大量のエロ動画をRに焼こうと思うが、Rが最小枚数で済む様に最適化するアルゴリズム（もしくは応用できそうなアルゴリズム）ってある？

ビン詰め問題とかいう名前であった気がする。
その手の問題は、最適解を見つけるアルゴリズムは見つかってないか、
アルゴリズムが存在しないことが証明されてる（すべての組み合わせを調べるしかない）
ただし、最適解じゃないけど、そこそこ良い組み合わせを得る方法が研究されてる。

Hopfieldニューラルネットワークの最適化問題とか。

>>230
使える動画を 6 種類ローテで回して、単なる水着を一つ入れておくってどう？
これで一週間回せると思うけど。

ナップサック問題とはどう違うの？

いわゆる「ナップサック問題」は、袋の最大値が決まってて荷物の総価値が最大にするように選ぶって問題だよね。
荷物を全部入れる必要はない。
この質問は、荷物の全体が決まってて袋の数を最小にするって問題で、荷物を全部入れる必要がある。
だから問題としては違うんじゃないの。
アルゴリズムの本質的なテクニックは同じなのかも知れないけど。

どうせRに保存した動画なんてこの先見やしないので、
1枚用意して、そこに全動画を保存したと思い込めばok

どなたか、シェルソートとバブルソートの処理時間に差が出る
ことについて初心者でも分かるように説明させて
くださいませんでしょうか？お願いいたします。

適当にかき混ぜながらソートするので，
バブルソートや挿入ソートで遅くなるケースを回避しやすいから．

もちろん速くなるケースも回避しやすい．

で，結局どれくらいになるかは根性で期待値計算すると O(n^{3/2}) とか見えてくる，

よって初心者でも分かるように説明するのは無理．

以下のような単語がいくつかあった場合、
その全ての組み合わせのパターンを算出
するアルゴリズムってないですか？


カレー 餃子 牛丼 ラーメン

カレー 牛丼 餃子 ラーメン
牛丼 餃子 ラーメン カレー
・・・
・・・
・・・

総当りするしかないだろ。

>>242
宿題スレの方が

std::next_permutation？

>>242
ルール説明が雑すぎ

>>242
順列の計算習うのって中学だっけ高校だったっけ。

様々な大きさの矩形を整列させるアルゴリズムって既に有名な方法があります？

具体的には、横:sx 縦:syの大きさを持つ長方形を、なるべく無駄が出ないように
正方形の中に敷き詰めるような動作です。

//-----------------------------------------------------------------
struct SIZE { int sx; int sy; };
struct POINT { int x; int y; };

const int nBoxCount = 1000;
SIZE box[nBoxCount] = {{10,10}, {7,5}, {3,8}, ...こんな感じで1000個

POINT pos[nBoxCount]; // ←ここに整列後の位置座標を保存する
//-----------------------------------------------------------------

敷き詰め先の正方形のサイズは問いません。
（後でスケールを調整して、0.0〜1.0の浮動小数点座標に変換するので）

「なるべく無駄なく」「正方形に」敷き詰める事を重視してます。
とはいえ、整列時に矩形の辺同士を無理にくっつける必要はありません。

上記を満たすようなアルゴリズムが既に存在しているようなら、
そのアルゴリズム名を教えていただけませんか？


（話を単純化させるため、こんな書き方をしましたが、最終的には
　3D空間内全ての４頂点ポリゴンを平面投影し、それらを
　正方形面＝テクスチャUV空間　に敷き詰める動作をさせたいです）

遺伝的アルゴリズムでそんな研究が合ったような気がするなあ……

>>248
全部の組み合わせを評価するってのはダメなの？
一つの正方形に1,000個落とすって、枠に対する長方形の大きさが小さすぎて、
現実的に意味なくない？　ランダムに落としても、さほど差がないように思う
けれど。

なんか、丸の問題なら見たなー
それは、箱の中に数個の点を置きそれをちょっとづつ大きくしてくのだったかな・・・・？
これでやるときは、ランダムに座標を取って、ちょっとづつサイズを大きくしていき
当たり判定で、やるんだっけか？
まあ、プログラミング習ったばっかで読んだから忘れた

と書き終わってみたら、長方形じゃ無理か・・・・・

ネスティング(Nesting) アルゴリズムで検索してみ
普通は任意形状の配置だけど

>>248じゃないけど。

>>250
> 全部の組み合わせを評価するってのはダメなの？

理論的には出来るけど、何通りになると思う？
1000個の長方形を単純に一列にならべるだけで1000! 通り（大きすぎてよくわからん）
各長方形の縦横の向きまで考えれば、上の組み合わせにさらに2^1000をかけたものになる。

>>249-254の方々、色々な情報ありがとうございました。

>>253
素晴らしいです！
かなりヒントになりました。
この辺キーワードで検索かけまくって、お勉強いたします。

Expose?

↓こんな処理を考えています。

// 「 former は latter よりも前にこなければならない」という順序付け
struct ordering { int former, latter; };

// M 個の順序付け orderings に基づいて [0, N) の整数を並べ替えた結果を
// sorted に格納する。
// ただし orderings の全ての要素について former != latter であることが
// 保証されており、矛盾する順序付けも含まれていないとする。
void sort_by_ordering_set( int sorted[] , int N
, struct ordering const orderings[] , int M );

・この処理（問題）に、何か良く知られた名前が付いていればおしえてください。
・N, M に対する複雑度はどれぐらいになるでしょうか？
・お勧めのアルゴリズムがあれば教えてください。

ここ数日、仕事の片手間にいろいろ考えているんですが、
速度を無視した実装すらできていません。
今は make のソースでも見たらいいんだろうか、とか思っています。

トポロジカルソートでぐぐれ

>速度を無視した実装すらできていません。
Javaでやってみました。

void sortByOrderingSet(int[] sorted, int[][] orderings) {
　　boolean[] visited = new boolean[sorted.length];
　　for (int p = 0; p < sorted.length;) {
　　　YET:
　　　　for (int i = 0; i < sorted.length; i++) {
　　　　　　if (visited[i]) continue;
　　　　　　for (int j = 0; j < orderings.length; j++)
　　　　　　　　if (i == orderings[j][1] && !visited[orderings[j][0]])
　　　　　　　　　　continue YET;
　　　　　　visited[sorted[p++] = i] = true;
　　　　}
　　}
}

>>257
アルゴリズムの話じゃないが "latter" は "later" に直しとかないと
恥かくんじゃないか？

半順序関係ってかっこいいよね

>>260
former / latter はごくごく一般的な単語
恥かいてるのはあんただよ

>>258, >>259
ありがとうございます。道が開けました。

おまいら、半順序木からデータを探すとき、どのくらいの時間がかかるますか？
0(n)くらい？それともちょっとくらいは速くできる？

半順序木だけでやるなら計算量の意味では O(n) が限界。
ランダマイズとかすると減るかもしれんが。

構築段階から手を加えて良いなら、半順序木に要素が追加されるときに
ハッシュか何かにその要素を追加し、以後木に編集がかかったときに
ハッシュと同期する、とかいうのが常套手段。

x が与えられたとき，2^(a+1) > x ≧ 2^a となる 2^a を高速に(ループ等を使わ
ず，できればビット演算のみで)求める方法を探しているのですが，そういうア
ルゴリズムご存じの方いらっしゃらないでしょうか？
言語は C です．

それは俺も知りたい。

(int)(log(x)/log(2))
じゃマズいよな。

最上位ビット以外を0にすれば良いわけだな。
(x & x-1) ^ x
で最下位ビットが取り出せるので、前後でビットを逆に並べ替えれば良いんだが、
思いつかん。

>>266
ビット演算スレがあるから覗いてみたら?

>>268
ま、どうでもいいけどx&-xのほうがクール

>>270 それだと負の数の表現形式が問題になって嫌な予感。

>>266
ビット数決めうちなら以下の手がある(CPU依存の命令使うという手もあるが省略)。
x |= x>>1
x |= x>>2
x |= x>>4
x |= x>>8
x |= x>>16
x ^= x>>1

>>296
情報有り難うございます．書き込んでみました．

>>272
有り難うございます．

定石があるものとばかり思っていたのですが，意外と難しいんですね...
これから解読してみます．

>>274
実は上のコードはビット演算マニアから言えば定石だったりする。
もし、詳細が知りたければ「ハッカーの楽しみ」という本を読めばいい。
無駄に深い知識を得ることが出来る。

>>275
そういえば積ん読してあったなぁ，と思って探してみたら出てきました．
p.51 のやつですね．

理解にかかる時間が節約できそうです．有り難うございました．

おまいらマニアつーかヲタクです。

んで、変換対象のデータが複数ある場合はSSE2を使うと。

static const __m128 fp_mask = { 0xFF800000, 0xFF800000, 0xFF800000, 0xFF800000 };

__asm cvtdq2ps xmm0, xmmword ptr [vsrc] ;//32bit整数×4をロードし単精度×４に変換
__asm andpd xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア
__asm cvtps2dq xmm0, xmm0 ;//32bit整数×４に変換
__asm movdqa xmmword ptr [vdest], xmm0 ;//結果をストア

対象データが大量にある場合、まっとうな方法よりこれが一番スループット出るんだよね
ソフトパイプラインでレイテンシ埋めれば完璧。

× __asm andpd xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア

○ __asm andps xmm0, xmmword ptr [fp_mask] ;//仮数部をゼロクリア

演算結果から言えば同じなんだけど

>>279
素朴な疑問なんだけど、その両者の違いは32ビット単位か64ビット単位かってことだよね。
実際のCPUの動きとしては、何か違うの?

それと、対象データが大量にあるなら>278のfp_maskはxmmレジスタにロードした方がいいのかな?

CPUの実装にもよるんじゃないかな。

たとえばCore 2 Duoの技術情報には、SIMD整数命令とSIMD浮動小数命令を
同じレジスタ上で混ぜて使うとペナルティが生じるという趣旨のことが書かれてる。
見映え的にも型に合ってない命令を無闇に混ぜないほうがいいかな、と。

「movapsとmovapdとmovdqaって何が違うんだ？」と思ってロード帯域計ってみた
ことがあるけど、若干差が生じるんだよな、なぜか。
でもCPUによっては生じないかも知れない。


> fp_maskはxmmレジスタにロードした方がいいのかな?

基本的にはそう。
ロード帯域に余裕がある場合は、レジスタを定数1個のために占有するよりは
処理の並列化のために使った方がいい場合も無くはない。

>>281
なるほど、解説THX。

ある２つの文字列が「どの程度同じか」を見つけるアルゴリズムを教えて下さい。
例えば「aあいうえおbbb」と「ccあいうえおeeee」は『大体同じ』と判断したいのです。
この例の場合「あいうえお」の部分が同じな訳ですが、これが「あ いうえ お」とか
「あいう-えお」でも、「あいうえお」と同じとみなしたいです。
人間が目で見れば、「大体同じ文字列」というのはすぐ分かるのですが、
これをどうやってプログラムで実現すればいいのか・・・

LCSとは違うの？

>>284
ＬＣＳって何でしょうか・・・？
ググッてもよく分からない・・・

Longest Common Subsequence

>>286
成る程、深く研究されているんですね・・・
Windows 上で使えるプログラムやライブラリ、
DLL 等があれば教えて下さい。
比較する文字列を 2 つ渡すと、何 % 一致しているかを
返す関数みたいなのがあるといいのですが・・・

ライブラリは知らんが、O(nm) の実装なら
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
にある。そんなに複雑ではないので、参考にして書いてみたらどう？

Smith-Watermanかな
あとDNA配列の一致を調べるのと似てるからそれ関係を見てみると面白いかも
BLASTとかFASTAとかだっけかな・・・

ttp://www.topcoder.com/
のアルゴリズム部門に挑戦してみようという人はいないか？

現在、日本は、21位だぞ。
ttp://www.topcoder.com/stat?c=country_avg_rating

AGREPはどーよ

http://www.tgries.de/agrep/

>>290-291
英語は苦手だ。

インテルで最適化コンテストやってなかったっけ?
#あれだとアルゴリズムレベルでの工夫の余地はないのかな。

>>293
でもまあ機械語いじるのもパズル的な部分はあるし面白そう
オレは無理だが

ソースコード読むのに英語か日本語かなんて関係ないだろ

英語のドキュメントが読めないって致命的になるから勉強したほうがいいよ。

ﾜﾛpｗｗｗ

>296 言語による

>>283
http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
は？

経路を記憶するコードを追加すればdiffも簡単にできる。
一致度の%も、定義によって異なってくるが間単に計算できる。

>>299
自分でそのコードを書く事は出来そうもないので、>>287 の様な
「比較する文字列を 2 つ渡すと、何 % 一致しているかを返す」
様なツールというか関数を探してます・・・
でもないみたいですね。

自分で書けよ……

擬似コードが載っているんだから書けるべ。
>299見て書けないならプログラマに向いてないよ。

>>300
出鱈目書いてよこすが、こんなもんでいいだろうか？
double cmpstr(char *buf1,char *buf2,int size){
int i,j
j=0;
for (i==0;i>=size-1;i++){
if (buf1[i]==buf2[i]){
j++;
}
}
return j/(size-1);
}

あ、最後から2行目
return j/size;
だ。

>>300
phpのsimilar_textのソース読んでみてはどうだろう。
O(n^3) くらいだったような気がするが。

スローすぎてあくびが出るぜ

おまいら自分用のアルゴリズムライブラリとか持ってますか？

日本語でおｋ

脳内訂正能力の低下が顕著

脳内訂正能力を利用した圧縮アルゴリズム

昔々、あるところに、おじいさんとおばあんがいました。
おじいさんは山へ芝刈りに、おばあさんは川へ洗濯に行きまた。
おばあさん洗濯をしていると、
大きな桃がどんぶらこっこどんぶらっこと流れてきました。

そこで、おばあさんは
「おお、なんと大きな桃じゃ！」
と言い、嬉しそうに丸呑みにしました。

>>311
脳内訂正能力を利用した圧縮ですよね？

おばあん　←　１文字圧縮
芝刈り　 　←　”柴刈り”を暗号化
行きまた　←　１文字圧縮
おばあさん洗濯　←　１文字圧縮
どんぶらこっこどんぶらっこ　←　１文字圧縮

暗号化は意図しない動作でした

二次元平面において、線分と単純多角形が与えられたとき、
線分が多角形の内部を通るかどうかを判定する簡単な方法があれば教えてください。

幾つか自分でもやってみたのですが、線分が多角形の端点と重なる場合などで
正しい結果が出ませんでした。どなたかお願いします。

>>315
「単純多角形」の定義は何？

「多角形の端点」もおかしい。

「線分が多角形の端点と重なる場合など」（頂点や辺の意味だろうけど）を
内部を通ることにするかしないか自分の定義しだいじゃないのか？

グラフの自動レイアウト関係で参考になるアルゴリズムや考え方はありますか？
重力・斥力でやっているけれどいまいち効率の挙動が悪いんで素。

>>316
単純多角形とは自己交差を持たない穴の開いていない多角形のことです。
このとき、多角形は境界をなす頂点の列を用いて表現できます。

>>317
単純多角形の境界をなす頂点のことを「端点」と表現しました。

>>318
それを曖昧にしないように、「内部」という言葉を使ったのですが、説明不足でした。
境界と共有点を持つケースは、交わらないと判定したいのです。


よろしくお願いします。

>>307
10年以上育ててたのが、HDと共に逝った

まず >>318 の言うとおり自分でどういう判定をしたいのか定義する
あとはひたすら図を書いて場合分けするしかないよ

>>321 悲惨。それも10年以上。当然、こんなときどうするかバックアップなどのアルゴリズムは考えあるんだろうね？

>>315
つhttp://www.google.co.jp/search?q=%E5%A4%9A%E8%A7%92%E5%BD%A2+%E5%86%85%E5%A4%96%E5%88%A4%E5%AE%9A

>>315
0　　線分の始点が多角形内部にあるときは交差あり
1　　多角形を反時計回りに正規化
2　　多角形の全ての頂点を登録(配列1)
3　　線分の始終点を頂点として登録(配列2)
4　　線分と多角形の交点を(配列1)と(配列2)に新しい頂点として順序良く挿入。
　　ただし別の頂点と重なるときは登録しない。
5　　全ての交点(配列1の点Nと配列2の点Mが同じ座標とする)について、
　　(配列1)の前後の頂点と合わせた３点N-1,N,N+1、(配列2)の頂点Mに着目して
6　　M-1が存在してM→M-1がN-1→N→N+1の左側に出て行く線なら交差あり
7　　同様にM→M+1がN-1→N→N+1の左側に出て行く線なら交差あり
　　 N-1→N→N+1は折れ線の場合もあるので注意。外積と内積を組み合わせて判定。

線分と多角形の辺が頂点以外で交差する典型的ケースをあらかじめ判定してもOK

aはビットフラグで、メモリ、FDD、HDD、FANなどの故障状態を表しています。
bは条件です。FDDとHDDが両方故障なら2進で11です。
FDDとHDDが両方故障であるのを得るために2進の11がdefineしてあるのは
変更できませんが、FDDとHDDが両方故障であるのを調べるために
if ( a & b == b )
を実行するのには何か無駄がある気がしますが、もっとよい方法はありますか？

>>326
if ((a & FDD) && (a & HDD))

>>327
bの値もプログラム中で決定するので327のようにソースに直接書けません。
bを使ったプログラムにします。
bの条件を追加してFDDとHDDとUSBの3つとも故障で2進で111とした場合
もっとよい方法があれば教えてください。

>>326
「何か無駄がある気がします」なんて言われたら
どんな答えを出してもそういわれそうな気がして答える気にならない。
具体的に何が不満なんだ？

データ構造選んだ時点で
どのアルゴリズムが使えて
どのアルゴリズムが使えないかが決まってくるわけで

最適になるようにアルゴリズムとデータ構造を選択するのがプログラマの仕事。

ヒント：青い鳥
だな。理想を求めるのはいいけど、いつまでたっても納品できない悪寒。

ヲレライブラリを失わないためのヲレ危機管理アルゴリズムが不十分だったという検証ができたというヲチか。
バックアップぐらい危機管理の基本中の基本だぜ。

プログラマって人生設計も立てられずに人生のアルゴリズムもなくイベントドリブンで生活してそうだな。

なかなか厳しいな〜
特にイベントドリブンテところが痛いな〜

そんなプログラマに救いの手を♪

反復部分文字列の検索アルゴリズムを考えてます。

反復部分文字列とは一つの文字列中に複数回出現する文字列のことで
1.同じ反復部分文字列同士は重なりあわない(ABCABCABC => ABCと抽出 ABCABCは抽出しない)
2.反復部分文字列の部分文字列も反復部分文字列だがそれは抽出しない(ABCDEABCF => ABCと抽出 A B C AB BC は抽出しない)
という条件付きで2回以上出現するもので長さn以上の文字列を検索したいのです。

現在ドットマトリックス(str[i]==str[j]の値の行列を作り対角線方向に検索する方法)による検索しか思いつきませんが何か高速なアルゴリズムはありませんでしょうか？
SEQUITURアルゴリズムをいじれば早くなるかと思ったのですが条件を満たす文字列の一部しか見つけられないので悩んでます。

2つの任意の整数の組(a,b)が任意の数だけあるとする。
ただしa<bは常に満たされる。
『例えば「(2,4)(2,3)(1,6)(4,8)」の場合、
(2,4)(2,3)(4,8)は(2,3,4,8)という組を作る。』
というアルゴリズムを考えているのですが、いい方法が全く思いつきません。
分かる方、ヒントをください！

ハッシュ辞書使って、検索早めるのはどうよ。
gif なんかの LZW エンコードのソースに書かれているよ。

>>335
なるほど！圧縮でも部分配列の検索を利用しますね。そちら方面で調べてみます。

>>334
意味が今ひとつわからん。
かっこの中の数字のペアを数学で言うところの同値関係と考えて
その同値類に分けた集合をつくるってことか？

グラフのレイアウトで参考になるアルゴリズムはありませんか？
ノード間に関係を表すエッジが複数あるとしてランダムに表示されたノードを関係あるものを近くに表示させたいと思っています。
バネモデルなどを使った力学的モデルを使った配置の考え方は見つけたのですが、実行してみるとかなり遅くなってしまいます。
別に見つけた商用ライブラリyFilesのサンプルを使ってみるとあっという間に終わり何か別種のアルゴリズムを使っているとしか思えません。
ttp://www.yworks.com/en/products_yed_about.htm
何か考え方のヒントになるようなものでも助かるので何かないでしょうか。

>>326
ttp://oshiete1.goo.ne.jp/kotaeru.php3?q=2402835
ふてぇ野郎だ。

おしえてGoo煮出してみます。
スレ汚しすいませんでした。

>>337
ちょっと調べたのですが、同値関係？同値類？という状態です。

いま作ろうとしているのはN体問題に衝突･合体を組み合わせるため、
『どの物体が、どの物体へ衝突したか』
を判定するアルゴリズムです。
衝突したことが直接判定できるのは2つまで(物体a,物体b)で、
3つ以上が同時に衝突する場合、衝突に関与した物体はこの(a,b)の組み合わせから
判断しなければなりません。
「(2,4)(2,3)(1,6)(4,8)」の場合、合体して新たな物体を生じるのは
(2,3,4,8)(1,6)であることを見つけ出そうとしています。

なんだか長くなってしまいましたが、少し自分でも考えてみます。

>>341
「衝突・合体」 だけだったら Union Find．

分離もしたくなったら，単一要素を分離するだけなら Union Find Split，
接続している要素の切断なら Euler Tour Tree とか Topology Tree とか．

>>341
Pythonで作ってみた
（実際の言語固有の便利さを、どこまで使っていいのか良くわからん）

Data = ((2,4), (2,3), (1,6), (4,8))
ResultLists = []
TmpHash = {}

for (X,Y) in Data:
　if not (X in TmpHash):
　　if not (Y in TmpHash): #両方の数字が初めて出てきた場合
　　　　TmpHash[X] = [X, Y] #新しくリストを作成
　　　　TmpHash[Y] = TmpHash[X] #もう一方の数のハッシュを作成
　　　　ResultLists.append(TmpHash[X]) #結果リストに追加
　　else: #片方の数字(X)のみが初めて出てきた場合
　　　　TmpHash[Y].append(X) #既出の数字のハッシュのリストに初めての数字を追加
　　　　TmpHash[X] = TmpHash[Y] #初めての数字のハッシュを作成
　else:
　　if not (Y in TmpHash): #片方の数字(Y)のみが初めて出てきた場合（以下同様）
　　　　TmpHash[X].append(Y)
　　　　TmpHash[Y] = TmpHash[X]

print ResultLists

>>343
間違ってる．そのプログラムを
Data = [ (1,2),(2,3), (4,5),(5,6), (3,4) ]
で実行すると
[[1, 2, 3], [4, 5, 6]]
になるが，正しくは
[[1, 2, 3, 4, 5, 6]]
になるべき．

Python で作ってみた．Python よく知らんので拙いコードな気がする．

http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/2668.txt

ありがとうございます！
アルゴリズムの本を何冊か当たっても出なかった問題が
即座に出てくるなんて、2chの中の人すげー
いまからPython勉強します

いまだに>>334の数字にペアがなにを表してるかわからない自分は逝ってよしですか・・・orz

>>347
・物体 {1, ..., n} がある．
・物体同士の衝突を検査する関数 check(a,b) がある．
・衝突した物体は粘土のように合体する．

という設定で，

衝突している物体対のリスト [ (a_1,b_1), (a_2,b_2), ... , (a_m,b_m) ] が与えられる．
衝突して合体した結果，どのようになるか調べよ．

という問題．

C#でやったらこんなんになった。逝ってくる・・・orz
http://uploader.erv.jp/src/erv_jp0518.txt

複数の物体があるとして関係があるもの(これはユーザーの定義などにより設定される)はある程度近くなり、また物体同士で近すぎるものはある程度の距離を保つようにしたいと思います。

ここで計算して少し動かしてまた計算してとやってたんですが、微分積分などを使って一発でやることって可能ですか？

>>346
あたる本がよろしくないんだな．
セジウィック「アルゴリズムC」，CLR 「アルゴリズムイントロダクション」など
まともなアルゴリズムの本なら最小全域木との繋がりでたいてい書いてあるよ．

>>350
問題設定がよくわからん．
「物体」とか「関係」とか言わずに，どんな問題を解きたいかを
はっきり述べてくれたほうがよい．

問題だけ見ると >>338 と同じような気がするんだが．

>>350
３体問題を解決してフィールズ賞取れよ、って言ってるのかな？

簡単にできる場合と難しい場合があることくらいまでは俺にも分かるが、できない場合があることを証明するのは俺には荷が重いな。

>>352　あー同じようなもんです。
>>353　やっぱりそういう話ですよね。

B木をファイルとして実装する方法で詳しいサイトないですか

>>350
じゃあ 352 と同じ問題だと思って回答するぞ．

力学モデルは十分実用的のはずで，小規模系で遅いとしたら
時間刻みが細かすぎるか，用いてる力学モデルが致命的に悪い．
特に時間刻みは重要で，別にシミュレーションするわけじゃないんだから
かなり大雑把に計算しても大丈夫．数値安定性が保たれる限界くらいの
刻みに選んでも平気．

大規模系で遅いとしたら，アルゴリズムの改良が必要．
たとえば高速多重極展開なんかは有力な解決になりうる．

352 は 338 のミス

>>356
表示しながら収束状況を見てると、ノードが行ったり来たりしてるのは問題外ですよね・・・

>>338
こういうのって初期配置も結構重要だと思うんだけど、その辺意識してるのかな？

yEdすげー

.kjm;:,ok:k,;uhbvxew6te4z64c

>355

>>359
やってるうちに初期配置がかなり重要なことはわかってきました。
今は初期配置をうまくやるアルゴリズムを一つ思いついたので今度試してみるところです。
ただ、初期配置をうまくやってその後収束させる方向が正しいのか、全く違うやり方があるんじゃないかとヒントを探してるところです。

>>363
ノードを同心円状に配置するのはどうだろう。
グラフのあるノードを中心として、距離1のノードは半径1の円周上に等間隔に配置。
距離2のノードは半径2の円周上に…という感じ。
この方法で以前試した時は、そこそこうまくいった覚えがあるが、
グラフがツリーに近い形状だったからかもしれない。

力学モデルを使っていて遅いとのことだけど、
パラメータを弄ってやって、最初は移動量を大きくとって大まかな形をつくり、
それから移動量を小さくして微調整すると良いと思う。
もう既にやってるかもしれないしけど…

あと、遅くなる原因としてもう一つ。
これは自分がやったミスで、
収束するのが遅い遅いと思っていて、原因を探るために処理ごとの所要時間を取ってみたら、
実はグラフの収束を確認するための描画に時間がかかっていただけという情けないのもあった。
1回動かすたびに毎回描画なんてしてたから当たり前なんだけど。

> パラメータを弄ってやって、最初は移動量を大きくとって大まかな形をつくり、
> それから移動量を小さくして微調整すると良いと思う。

力学モデルなら自然とこうなるな…申し訳ない。

プロファイルぐらい取ればどこで遅いかぐらいは一目瞭然でしょ。

そういう話をしてるんじゃなくてな

エレベータで全押しする奴を止めるアルゴリズム作って

>>368
ボタンを押したら新しいボタンが表示される、ってシステムならＯＫ

同じボタンずっと押したらキャンセルとかつけてほしい

ダブクリでキャンセルできるエレベーターとかはあるよ

>>368
考え方が間違ってる
全押ししても正常に動作するようにする方法を聞くんだ

操作に論理ミスがあっても正常に動作する方法ってどんなんだ

エラー出せば？

全階ボタン押したらエラーが出るエレベータ

例外処理でワイヤー切断

エレベーターガールを配置する。

エレベーターガールがエレベーターアーント気味なのは仕様です

エレベータを止めるのではなく、全押しした奴を止めたいなら、このほかに縄が必要だな。

#define N 適当な数
if (押されたボタンの数>重さセンサが感知した量/60kgf+N)
{
SpeakMessage("ボタンが押されすぎです。一旦消します。");
UnlitAllButtons();
}
//地震とかで全押しする必要がある場合の処理をしていません。

全押しされた時点で一番近い階に止まったら
ボタンすべてキャンセルすればいんじゃね？
もし本当に必要ならもう一度押すだろうし。

>>380　こういうあほな使用を実システムでも作ってないかと心配になる

質問自体がネタなんだからいいじゃん。
そもそも、エレベータに全押し対策機能つけようと思う奴、いるわけないだろ？
(本当につけたら、誤認識の嵐で、相当使いづらいエレベータになるからね。)
あくまで、架空のエレベータの話だ。

実際に、ボタン長押しでキャンセルされるエレベーターがあるわけだが。

そんな話はしていない。

で、381のエレガントな解法は？

全ボタンに指紋読み取り機能を実装し、複数人によって全押しされた場合は有効。
一人により全押しされた場合は、全てのボタンをキャンセルし、移動方向直近の階に停止させ
上からタライと小麦粉を落とす。

水 → 小麦粉 → タライ
がベスト

# 同一人が違う指で押したらどうする？

エレベータに乗るドアに目的階のボタンが無いのはなぜなんだぜ？

新しいぜ。 疑問断定形。

>>386
親切な人いるじゃん。
ボタンの前に立つと、「何階ですか？」と聞く人。

>389
半年(ry

エレベーターのお姉ちゃんは毎日タライの餌食

http://www.youtube.com/watch?v=urFeIsct9Pc

>>392
押すボタンによって指を使い分ければok

普通，手袋してるっしょw

階層DFDを使って自分の費用・授業・図書のデータを管理するシステムプログラムを設計せよ
・費用は収入や食費・交通費・生活費等の支出等のデータを扱う
・授業は履修している、もしくは履修済みの授業、一週間の授業表等のデータを扱う
・図書は借りた本等のデータを扱う
ユーザーはこのシステムにIDとパスワードを使ってアクセスし、
データ倉庫user-dataに保存されている自分のデータを参照できるようにせよ。

プログラム設計っつー授業でこんな問題出されたんですが、
http://members.jcom.home.ne.jp/pokemon_glider/program.jpg
階層DFDはこんな感じでいいんですか？
これをデータ辞書を追加したり、構造化英語で書いたり最終的にはJavaで実装できるようにしろとまで言われてます

開閉同時押しで目的階をクアドゥルプルクリック→目的階以外キャンセル

思ったんだけど、キャンセル機能とかついてると、
逆にいたずらされて降りられなかったり、
変質者とかに悪用されたりとかしない？

全部キャンセルされたら最寄り階で開くってことでどうでしょ。

かべのなかにいる!

ゆかのしたにもいるかも

クラーケンが現れた!

優先度付き待ち行列をハッシュで効率よく実現する方法を教えてください。

優先度付きキューならヒープのほうが適任だと思うけど？

＞404
連結リストとヒープは使うなという制約が…
平衡木も考えたんだが効率がいまいち。

平衡探索木でよいような？
一番左下へのポインタを持ちまわれば計算量的には同じになるはずだけど。

k個のソート済みのリストを入力し、それらを１つのソートされたリストにマージしたい。
単純な方法を用いるとO(kn)かかってしまう（ｎはｋ個のリスト中の要素全ての数）

ヒープを用いて効率よく実行する方法を述べその計算量を示せ。

>>407 宿題はお断り。

>>407
どのリストの先頭が最も小さいか、を管理するためにヒープを用いる。O(n log k)。

A(♂)→B(♀)
B(♀)→C(♂)
C(♂)→D(♀)
D(♀)→C(♂)
C(♂)→B(♀)
A(♂)＝俺

だれかこの問題を解決できる画期的なアルゴリズムを考えてくだちい
ていうかC(♂)氏ね

delete A(♂)

int main() {
　　C = A;
　　return 0;
}

>>334
超亀レスだが、ポインタ書き換えによる単一化を使うと効率がいい。
C#っぽい擬似コードで。public省略。Nは物体数。

class Pair { int a; int b; }
class Cell { int n; Cell(int n) { this.n = n; } }

Cell[] MakeUnifiedCells(Pair[] pairs) {
　　Cell[] cells = new Cell[N]; // 要素はnull初期化
　　foreach (Pair pair in pairs) {
　　　　Cell cellA = cells[pair.a]; Cell cellB = cells[pair.b];
　　　　if (cellA == null && cellB == null) {
　　　　　　cells[pair.a] = new Cell(pair.b);
　　　　} else if (cellA == null) { // assert(cellB != null)
　　　　　　cellB.n = pair.a;
　　　　} else { // assert(cellA != null)
　　　　　　cellA.n = pair.b;
　　　　}
　　}
　　return ret;
}

int GetEquivalenceClass(int n, Cell[] cells) {
　　while (cells[n] != null) n = cells[n].n;
　　return n;
}

まず、MakeUnifiedCells(Pair[] pairs)を使って、Cell[] cellsを用意する。
物体nがどの同値類に属するかは、GetEquivalenceClass(n, cells)で求められる。

GetEquivalenceClassの最適化版は↓みたいなかんじ。

int GetEquivalenceClass(int n, Cell[] cells) {
　　if (cells[n] == null) return n;
　　else if (cells[cells[n].n] == null) return cells[n].n;
　　else {
　　　　int ret = GetEquivalenceClass(cells[n].n, cells);
　　　　cells[n].n = ret;
　　　　return ret;
　　}
}

あぁ、すまん。ミスった。MakeUnifiedCellsのほう、

int GetRoot(int n, Cell[] cells) {
　　while (cells[n] != null) n = cells[n].n;
　　return n;
}

Cell[] MakeUnifiedCells(Pair[] pairs) {
　　Cell[] cells = new Cell[N]; // 要素はnull初期化
　　foreach (Pair pair in pairs) {
　　　　Cell cellA = cells[pair.a]; Cell cellB = cells[pair.b];
　　　　if (cellA == null && cellB == null) {
　　　　　　cells[pair.a] = new Cell(pair.b);
　　　　} else if (cellA == null) { // assert(cellB != null)
　　　　　　cells[GetRoot(cellB.n, cells)] = new Cell(pair.a);
　　　　} else { // assert(cellA != null)
　　　　　　cells[GetRoot(cellA.n, cells)] = new Cell(pair.b);
　　　　}
　　}
　　return cells;
}

に修正。

最適解の探索アルゴリズムでは[1]を，最良優先探索のアルゴリズムでは[2]を，Aアルゴリズムでは[3]を知識として用いる．特に，Aアルゴリズムで用いる知識のうち，すべての節点において[2]が[4]よりも小さいか等しいとき，[5]が求まる保証がある．

選択肢 ア： 節点nを通る初期節点からゴールまでのコスト
イ： 1つ前の節点からゴールまでの実際のコスト
ウ： 隣の節点からゴールまでの予測（推定）コスト
エ： 初期節点からゴールまでの最適経路
オ： ゴールまでの実際のコスト
カ： 節点nからゴールまでの実際のコスト
キ： 初期節点から節点nまでのコスト
ク： 節点nからゴールまでの予測（推定）コスト
ケ： 初期節点からゴールまでの予測（推定）コスト
コ： 節点nからゴールまでの最適経路

どうぞ

最適解の探索アルゴリズムでは蟻コロニー最適化を，
最良優先探索のアルゴリズムでは優先度つきキューを，
Aアルゴリズムではヒューリスティックを知識として用いる．
特に，Aアルゴリズムで用いる知識のうち，
すべての節点においてA子がB子よりも小さいか等しいとき，
A子の年齢が求まる保証がある．

宿題は自分でやろうね

大量のエロ動画のファイル名を、似たようなグループに分けるアルゴリズムってないかな？
シリーズ物とか、制服物とか、素人物とか女優名とか。
ファイル名をn-gramに分解して、グループに対応するパラメータを学習させたベイジアンフィルタに
通すってのが、今のところ考え付いた解だけど、
大量の文字列を適当に分類する、分類軸の多様性は、学習させたパラメータで吸収みたい
なのは、みんな考えてそうな気がする。

test

>>418
でも実用化されていないから
お前がんばれ。ていうか頼む

WinAPIのリージョンと同様の処理を行いたいのですが、
どのようなアルゴリズムを使用するのか見当も付きません。

処理したい内容は
多角形 or 多角形
多角形 and 多角形
多角形 xor 多角形
などを繰り返し、最終的に矩形の配列(win32ならGetRegionData)を取得したいです。

アルゴリズム名とか、ここに同じようなコードがあるよとか、この本を見れなどなど
教えてください。

バイナリファイルからバイナリ文字列を検出するプログラムを
書きたいのですが、コレと言う手法が思い浮かびません。

なにかヒントをいただけないでしょうか？

よろしくお願いします。

どんな規則性かによるんじゃないかい。
構造体が並んでる感じでIDを探すというならバイナリサーチ。
特に何もないならシーケンシャルサーチ。

文書の自動カテゴリわけは結構研究されているから、
一般にはいろんな手法があると思う（ベイジアンもそう）。

だけど、問題領域を限定するといろいろ分かることはあって、
エロ動画のファイル名に限定するとよりよい方法が見つかるかもしれない。
面白い研究テーマだと思います。

毛有り毛無しとか、液の量とか透過差分とか
様々な差分ファイルが世の中には存在するからな。
それこそ特許取れる研究をしないと。

>>425
え？二次だったの？

縮尺や解像度、圧縮レベルが違うだけの同じ画像を検出する方法は？

>>427
不可逆圧縮の場合、圧縮レベルが違うと画像そのものの同一性も失われるわけだが。

フラクタル解析すればいけるんじゃね？
全く別物の画像を比較するんじゃないんだから。

「おなじ」をきちんと定義してもらわんといかんな

近さの度合いを測る方法はいくらでもある。

>>421
コンピュータグラフィックス 理論と実践
James D. Foley他
19章7節を見れ

バイナリ文字列って何？


Cのアルゴリズム本を見たが、ソートしか載ってないクズ本だった。orz

たぶん二進数の列のこと

Cプログラマのためのアルゴリズムとデータ構造とか？

ここ最近の本ってさAho-Corasickアルゴリズムとか実用的なの載ってなくね？
アカデミック関連の糞高い本ならたまに載ってるのもあるんだけど、まず
有限オートマトンだの写像だの語彙が理解できないと話にならない。

別に最近に限らず、昔からゴミな本はゴミだし、まともな本はまとも。

Aho-Corasick は若干アドバンスドなアルゴリズムだろう。
定本とされるアルゴリズムイントロダクションにも、アルゴリズムCにも無い。
まあ文字列系のアルゴリズムの本なら大体載ってるとは思うが。

Aho-Corasickってどう発音すればいいんだ？

アホ-コラシネカス

Aho博士は日本に来たときこういったそうだ（実話）
「Ahoは日本では馬鹿という意味だそうですが私はそれほど馬鹿ではありません」

エイホー

>>438
ギャグのつもりなのかムッとしていったのか微妙だなｗ

ギャグで言ったのなら相当寒い奴だな。
あまり頭が良いようには思えない。

>>441
お前が言うなよｗ

>>431
ありがとう。
初のCG系アルゴだから右も左もわからなかったよ。ほんとサンクス。

糞高い本だな

この手の本は自分を切り売りするようなもんだしね

この手の本は自分を切り売りするようなもんだな

この手の本は自分を切り売りするようなもんだよな

この手の本は自分を切り売りするようなもんたよしのり

今年の冬は冷えるな

最近ひとのレスパクるレスが多いけどなんかのブーム？

最近ひとのレスパクるレスが多いけどなんかのブーム？まで読んだ

最近ひとのレスパクるレスが多いけどなんかのブーム？まで読んだまで読んだ

最近ひとのレスパクるレスが多いけどなんかのブーム？まで読んだまで読んだ まで読んだ

おれはおれの道を行く

マダンテって何だけ？

イオナズン使える俺は勝ち組

しかし　MPがたりない！！

ザオリクしか使えない俺は負け組み

イオナズン使えなかったせいで就職失敗しました。
宿屋で眠れなかったんです。

そろそろ時の砂を使う時期じゃないか

遺伝的アルゴリズムについて質問があります。
GAの考え方で交叉を行う為の選択を行う場合
一般的には一度使った要素は排除して考えるべきですか？

2個を使って1個ができるわけだから元の要素が足りなくなりますよね？
一度使った要素も再利用してよろしいのでしょうか？

もう一度GAの本読み返せ

>>461
まさかこんなに早くレスをいただけるとは思っていませんでした。

GAの本はもっていないのでちょっとわからないです。
ネットで調べても曖昧な答えしか見つけられずに(説明上では無記述でもプログラム上では選んだ要素を2度選ばないようにしていたり)。
なので質問させていただきました。
すみません。

もしかして重大な間違いを犯していることに気づいたかもしれないです。
ルーレット式やランキング式は淘汰に使われるのであって交叉に使われるんじゃないんですね。
お恥ずかしいです。

交叉に使われるのはその中から本当にランダムで選んだ要素同士でよいのですかね。
図書館にでも行って勉強してきます。

同じ要素を複数箇所に複製できたら個体の「個性」がなくなるでしょ
個性、つまり要素の並び方の組み替えこそがGAのキモ

極端な例だけど、ABCとabcを交叉してAaAができたとして
それのどこに両親の「個性」が残ってる？
ぶっちゃけランダム生成と大差ないよ

誤：GAのキモ
正：交叉のキモ

>>465
わざわざ説明ありがとうございます。
自分はまず親自信の選択の仕方に疑問を持ったもので。

交叉の内容は初期収束を抑える為に8割〜9割を二点交叉、1〜2割程度を一様交叉に
しようと思っております。この辺りはやりながら詳しく検討してみますが。


やはり現時点じゃ資料もないので詳しくはわからないのですが

最低限同じ要素同士が親になることと、1度組み合わせた要素との交叉を避ければいいの
じゃないかと考えておりまして。

最初の質問の内容としては要素数20の配列から2個を選んで親にする。
その場合親は次に利用されないで配列の要素数は18個になる…と繰り返すのですか？という内容です。
この場合は10回やったら選ぶ親が居なくなると思ったので…。

エリート選択をするという意味ではありません。

頭の中で考えて分からないのであれば、
とりあえず動くものを作って実験データ取って検証してみればいいじゃん。

>>467
自然界では普通の兄弟もいれば異母兄弟も異父兄弟もいるよね。
有性生殖と単性生殖（クローン）の両方を行う奴もいるし。

>>468
実際にやってみることは大切ですね。
ありがとうございます。

>>469
兄弟などを考えたら親が同じ可能は0じゃないですもんね。
同じ親でも子が全く同じになる可能性は遺伝子長にもよりますが余り多くはないですよね。

昨日借りてきたジョンホランドの訳書なんですが軽く読み流しただけでは無能は自分には理解できない様な内容でした。
と言うか自分が考えていた以上と言うか。


スレ違いになりますが今日伊庭さんの遺伝的アルゴリズムの基礎？って本を借りるつもりですが
他に初心者でも分かりやすいお勧めの書籍有りましたら教えていただければ幸いでございます。
色々有り難う御座いました。

スレタイ通りの人物がいれば知っていそうな気がするので質問。

http://oshiete1.goo.ne.jp/qa2722011.html で話題になっているアルゴリズムの由来はご存知ない?
このアルゴリズム、フラグ用の配列を初期化しないで使う、アイディアものだと思うのですが。
#いっそ、「森田のよく利用する賢いアルゴリズム」って名前で公表しろよと思ったのは内緒。

↓戯言なので読み飛ばし推奨

数年前に友人と酒飲んで話した時のあやふやな記憶
CPUだかメモリだかの量子っぽい回路ので似たような処理の話を聞いた
ような気がする

由来は知らんが、数値計算で同じ配列を使いまわして計算する場合
なんかには、常識的に使われているテクニック。他のところでも
しばしば見ることのある技法だと思う。

やっているのことは、配列 a の内容のうち重複しないものを
配列 b につめなおす次のプログラムをメモ化しただけなので
初期化がいらないのは当たり前。
m = 0;
for (i = 0; i < n; ++i) {
  for (j = 0; j < m; ++j) /* find a[i] from b[0..m] ? */
    if (a[i] == b[j]) break;
  if (j == m) { /* not found */
    b[m++] = a[i];
}

＃この技法は未初期化が残る C のような言語に特有のものなので、
＃「アルゴリズム」というほど一般的でないと思う。

>>471
このアルゴリズムはデータ数＜データの変域が前提になってるね。
フラグの初期化の処理をフラグの正しさの確認の処理に置き換えてるから。

オタクとは何か。
より多くの人びとはオタクという概念について混乱している。
それは、特定の種類の虚構作品の選好と総体的外見との間に因果的関係を見て取ったこと、ならびに感覚を即座に絶対化したことから始まった。

そろそろオタク概念の整備をしよう。
http://www.google.co.jp/search?hl=ja&q=%22%E3%82%AA%E3%82%BF%E3%82%AF%E6%A6%82%E5%BF%B5%E3%81%AE%E6%95%B4%E5%82%99%22&lr=lang_ja

したがって、「オタクは気持ち悪い」というのはトートロジーである（そもそも、気持ち悪い者にオタクという固有名を付けたのであるから）。
あとは、「気持ち悪い」という感覚や感情を即座に正当化することが問題か。
http://www.google.co.jp/search?hl=ja&q=%22%E8%B6%85%E8%B6%8A%E8%AB%96%EF%BC%880%E2%86%921%EF%BC%89%22&lr=lang_ja

一般人とは……（虚構世界内存在による使用法）
http://www.google.co.jp/search?hl=ja&q=%E4%B8%80%E8%88%AC%E4%BA%BA+site%3Apub.ne.jp%2F&lr=lang_ja

どうしてもつくれないアルゴリズムがあるので助けてください
１円〜９９９円のお買い物をするときに
はらう硬貨の枚数とお釣りの硬貨の枚数の和が最小になる払いかたで
払う金額と持っている硬貨枚数がいかなるときでも対応できるアルゴリズムがわかりません
１０００円札は１枚は持っています

硬貨は1.5.10.50.100.500です。お札は1000のみです

http://pc11.2ch.net/test/read.cgi/tech/1129376543/448-

全探索しかないか…

>>476
簡単じゃないか。
払う硬貨の枚数は常に0が最小なのだから、釣りとして受け取る硬貨の枚数を最小にする呪文を唱えればいい。
「釣りはいらねぇよ、とっときな」

すごく・・・漢です

人間の考えをプログラムにする感じでやってみたがゴチャゴチャになってしまった

この手の問題はコンピュータには、人間の思考と同じやり方ではやりづらいだろうな。
もっと究めてニューラルネットワークでも組めば別だろうが。

「お会計は674円になります」
500 100 50 10 10 1 1 1 1 払うと 釣りなし。動いたお金は9枚。
500 100 50 10 10 5 払うと 釣り 1。動いたお金は7枚
500 100 100 払うと 釣り 10 10 5 1。動いたお金は7枚。
うーん

>>476
面白い、おれさまが考えよう












んん・・・・・・・難しい・・・・・・

1165円払って501円受け取るのもあるね。7枚だけど

アルゴリズム的に最小でも、店員が妙な顔する組み合わせはやめてあげようよ

>>485
硬貨枚数とあるから、6枚だと思う。

こういうのはまず1~99までで考えるべきだと思う。
その過程で有効なアルゴリズムを考え付くこともある。
というわけでやってみようかな

ところで1000円札は硬貨ではないけど
999円の時は1000円札だして1円お釣りが最速だから1枚っていう風に考えていいのか？

1000円だけ特別扱いするのは美しくない

硬貨は十分な枚数あるものとする。1000円札も1枚と数えるものとする。
1=1
2=1+1
3=1+1+1=5-1-1
4=5-1
5=5
6=5+1
7=5+1+1
8=10-1-1
9=10-1
(1) 与えられた支払額の上の位から順に機械的に上の置き換えを行なう。
(2) +-で打ち消すもの同士を消す。3のときだけ2とおりあるのでより打ち消せる方を選ぶ。
(3) +の方で払うと-の方のお釣りが帰ってくる。
674=(500+100)+(50+10+10)+(5-1)=(500+100+50+10+10+5)-(1) 動いたお金は7枚
348=(100+100+100)+(50-10)+(10-1-1)=(100+100+100+50)-(1+1) 動いたお金は6枚
999=(1000-100)+(100-10)+(10-1)=(1000)-(1) 動いたお金は2枚

さすが

797=(500+100+100)+(100-10)+(5+1+1)=(500+100+100+100+5+1+1)-(10) 8枚
797=1000+5+1+1-100-100-10 7枚

797=1000-100-100-1-1-1 6枚

改善改善とか言ってる企業にかぎってアルゴリズムを工夫しないんだよね

こういった探索系のアルゴリズムは全探索が基本で
後はいかに無駄な探索を省くか(枝刈り)を考えた方が簡単でしかも速く、正確に動く。

払う側が硬貨をもっとも減らすアルゴリズムを考えるともなく使っている人間って偉大。
ちなみにいつもは手持ちの硬貨を減らしつつ、例外的に100円玉をもっとも増やす
アルゴリズムを使っています。

スーパーのレジの中に2000円札を見かけるけど、おつりでもらった事は無いなあ・・

全探索＆所持硬貨枚数での場合わけ
Rを使ってプログラムを作りました。

時間かかりすぎる・・・orz

単純な全探索でも一瞬で終わるが･･･

ｍｊｓｋ

理由判明
所持硬貨枚数のwhile文に対して
外側に所持硬貨枚数を計算させる部分をもってきていました。

それにしても時間がかかる…　誰か修正してくれ…orz

例えば1円玉を払って1円玉がお釣りで返ってくるようなやり方は排除していいから

1円玉が-4〜4枚
5円玉が-1〜1枚
10円玉が-4〜4枚
50円玉が-1〜1枚
100円玉が-4〜4枚
500円玉が0〜1枚
1000円札が0〜1枚

と考えてよさそうだ

全検索でいいじゃんｗｗｗｗｗｗｗｗ
何か不満でも？ｗ

さめがめ(samegame)で全探索するときの枝刈りって良い方法あるのかな?

昔Gooゲームかなんかでこれと同じルールのゲームがあったんだけど(たしか名前はブロキシー)
時間制限がなかったから手動で配置を入力して探索させてみたけど
なんの工夫もしなかったから全然良い点の手みつけられなかった
そのうえGooのやつはランダム要素を持ったブロックが一個だけあって、
それは最後まで残すようにするしかなかった。

1円から999円までの「硬貨の枚数の和が最小になる払い方」での
枚数の和のリストを出力してみた。
(例: 1円は1枚, 2円は2枚, 3円は3枚, 4円は2枚 ... 999円は2枚)
誰か検算してくれ。
1232123321234323443234543455434554345432344323432123432344323454345543456545654345543454323443234321
2343234432345434554345654566545665456543455434543234543455434565456654567656765456654565434554345432
3454345543456545665456765677656776567654566545654345654566545676567765678767876567765676545665456543
4565456654567656776567876787656776567654566545654345654566545676567765677656765456654565434554345432
3454345543456545665456765676545665456543455434543234543455434565456654566545654345543454323443234321
2343234432345434554345654566545665456543455434543234543455434565456654567656765456654565434554345432
3454345543456545665456765677656776567654566545654345654566545676567765678767876567765676545665456543
4565456654567656776567876788767887678765677656765456765677656787678876788767876567765676545665456543
4565456654567656776567876787656776567654566545654345654566545676567765677656765456654565434554345432
345434554345654566545676567654566545654345543454323454345543456545665456654565434554345432344323432

所持金の枚数に制限を加えた場合のリスト
（1円1枚, 5円2枚, 10円2枚, 50円2枚, 100円2枚, 500円2枚）
1432124321254323543236543465434654345432354323432125432354323654346543476545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876798767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
365434654347654576545876567654576545654346543454323654346543476545765457654565434654345432354323432

ソースうp

>>507
出力結果が正しそうだったら、ね・・・

>476の問題だと千円札は一枚持っているけど、
硬貨を何枚持っているかは不明なんじゃないの？

>>509
もちろんそうだろ？
「任意の枚数指定ができるプログラムを作れ」ってのが本来の課題。

>>506
総当たり、たぶん同じ
1432124321254323543236543465434654345432354323432125432354323654346543476545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876798767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321

>>511
ソースうp 

所持硬貨数に制限無しなら色々ありそうだけど制限ありだとまったく思いつかない

>>506
なあ、その条件で10円を1枚にしてやってみてくれないか

>>514
これでいいか？（1円1枚, 5円2枚, 10円1枚, 50円2枚, 100円2枚, 500円2枚） 
1432124321254323654347654565434654345432354323432125432354323654347654576545654346543454323543234321
2543235432365434765458765676545765456543465434543236543465434765458765687656765457654565434654345432
3654346543476545876569876787656876567654576545654347654576545876569876798767876568765676545765456543
4765457654587656987679876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545876568765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434765458765676545765456543465434543236543465434765458765687656765457654565434654345432
3654346543476545876569876787656876567654576545654347654576545876569876798767876568765676545765456543
476545765458765698767A987898767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656987679876787656876567654576545654347654576545876568765687656765457654565434654345432
365434654347654587656876567654576545654346543454323654346543476545765457654565434654345432354323432

あ、A っていうのは 10 枚のことね(16進数表記)。

age

来月入社する者ですが、入社前までの宿題として出されたアルゴリズムの
最後の問題がどうしても解けないお（;^ω^）

当方文系出身のせいでちんぷんかんぷんなんだお・・・
心優しい方手伝ってはくれないだろうか？お願いしまつ・・・

ageて申し訳ない。次からはsageて行くので・・

どれどれ。
とりあえず問題を見せてもらおうか。

ありがとうございまつﾟ+.ﾟ(´っω・｡｀)ﾟ+.ﾟ

問題；複数の生の整数を入力し、その中の最大値と最小値、平均値を求める
処理の流れ図を作成せよ。なお、入力の終了は-1を入力した場合とし、
データは必ず１件以上入力されるものとする。

多分かなり初歩的なアルゴリズムかと思われるのですが自分にとっては
難しいです・・何せアルゴリズムの本当の初歩しか本で勉強していない
身ですのでorz

お願いしまつ（;´д｀）

あ・・正の整数です('A`)

>>521
アルゴリズムと言うにもおこがましい。人間がそれを為すようにすればよいだけだ。
ついでに言えば、流れ図なんぞを書かせるような会社には似合いの人材というわけだな。

>>522
手厳しいお返事ありがとうございます。

ですが・・・本当にどういう風に書けばいいのか理解できないのでここの
住人の力を借りさせて頂こうと思った次第ですので・・何卒お手柔らかに
(´･ω･`）

>>520
悪いことは言わん、他所の業界へ行け。
罵るつもりはないが、このままじゃお前とお前に関わる者が不幸になる。


・・・と、思ったが、普通の初心者ってこんなんだっけ？
もう20年以上もプログラミングやってるし、初心者の感覚がさっぱりわからん。

>>524
この業界には文系ながらも興味がある上、勉強していてもとても楽しいので
実際仕事に携わってみてから貴方の意見を参考にさせていただきたいです。
ですが、玄人から見たら多分自分みたいな雑魚が入っても迷惑なだけという
意見は理解できます・・・そうならないように努力します。

初心者の私からみたら･･･正直こんなアルゴリズムとも呼べない問題でも
どういう風に図を組み立てればいいかわからないですorz

流れ図は書いたことがない。
時代遅れだと思うしうちの会社でも使わないんで。
力になれなくてすまんね。

まぁ、過疎ってることだし、少しぐらい相手してやるか。

>勉強していてもとても楽しいので

この業界ではこれが一番大切な才能だ。それを持っているならどうにかなる。

とりあえず一度に解決しようとするな。一度問題を噛み砕け。
たとえば、まず最大値だけを求めることを考えろ。それでもイメージが沸かなければ
さらに噛み砕いて二つの値が与えられた時にその内の大きなほうの値を求めることを考えろ。

>>526
そうなんですか。

仕方ないです。なんとか自力でｶﾞﾝｶﾞｯﾃみます(;´･ω･`)

かけるけど、AAで表現するのはめんどくさいなぁ
流れ図云々より、プログラム書くこと覚えたほうが手っ取り早

<繰り返し>
数字の入力
|
正の数か？ ->-1以外の負の数：怒る
|
-1なら入力した個数がいくつかチェック　->0個：コラッ！
正の数ならリストに数値を追加
</繰り返し>
|
-1で個数が0以上の時計算に入る
|
ごにょごにょ
|
出力

前に作った簡易フローチャート風表記を使うとこうなるかな。
() //端子
{} //繰り返し開始記号
　[]数字の入力 //処理
　<>数値チェック //分岐
　　<-1
　　[]怒る
　　()終了
　<>数値チェック
　　==-1
　　[]ループ脱出
　[]リストに数値を追加
{}
<>入力個数チェック
　==0
　[]怒る
　()終了
[]最大値、最小値、平均値の算出
()終了

処でこの問題、求めた値を出力しないでいいんだろうか｡

すみません。
そんな所よりも肝心要の
「入力処理部分（キーボード割り込みから、整数のparsingぐらいまで）」
をメインにお願いします。

自力でｶﾞﾝｶﾞｯﾃるんですが、全然かけません・・・OTL

>>532
ちょっと待て。あんたの言う要の部分は普通はOS側にライブラリ経由で処理してもらうところだ。
#パースはライブラリだけど。
一体全体、どんな環境の何をやろうとしているんだ?

宿題では環境の指定はないですが、
もし書きにくいようでしたら、
PC/AT互換機という事でいいでつ。

# OS が絡むと面倒なので、"OS は無し" という事で・・・（;^ω^） 

私としては、それなりに流れ図が書けていて、
入社後に教育担当の方から怒られなければ
それでいいでつ（;´д｀） 

OSなしでIO処理しろって、どんな課題だよ。
環境が指定されてなければ、このあたりは
環境に用意されているものとしていいはずだ。

パースはともかく割り込みのあたりなんて
アルゴリズムの範疇ではない。

>>535
>OSなしでIO処理しろって、どんな課題だよ。
多分、入社後の研修では H8 とか PIC とか使わされる事に
なりそうなんですが・・・

また、この宿題については、研修担当の方からは
「（所詮、流れ図だから）君の得意な環境を想定して書けばよい」
と言われました。

助けてくださいﾟ+.ﾟ(´っω・｡｀)ﾟ+.ﾟ 

>>534
情報が少なすぎてなんとも言えないけど、
ろくに会話もできないぼんくらをプログラマとして雇うような糞会社が要求する流れ図なんて、
>531のレベルで書けてりゃ充分だろ。

>>537 
手厳しいお返事ありがとうございます。 

ですが・・・本当にどういう風に書けばいいのか理解できないのでここの 
住人の力を借りさせて頂こうと思った次第ですので・・何卒お手柔らかに 
(´･ω･`） 

手厳しいも何も、>531は理解できてないのか?
>531に後は最大値なんかのロジックを追加するだけだろ。

>>538
お前ちょっと「流れ図」でググッてこいよ。
>>531や>>530で何が駄目なんだ？

>>538
もう、わからないことや出来ないことは素直に「出来ませんでした」でいいんじゃね？
会社側も、「2chとかで調べて何となく作ってみました」よりも「わかりません。教えて下さい」って
社員の方が扱いやすいだろう。

>>539
>手厳しいも何も、>531は理解できてないのか? 

正直難しいです。(ρ＿；)・・・・
どうしてこれでよいのか、全然分かりません。

まずは早速教えていただいたとおりに、
一度問題を噛み砕いてみます。

例えば、キー押下によって割り込みピンが
アサートされた時の処理って何行目になるんですか？

>>542
流れ図ってそんな事まで書くか？

>例えば、キー押下によって割り込みピンがアサートされた時の処理
この意味わかって言ってんの？

520の問題文で「ピンが云々」なんていうやつは
まったく常識が無いやつだと思われても仕方が無い。

というか、「割り込みピンがアサートされた」ってどっから引っ張り出してきたの？

>>545
どっからといわれましても・・・

多分、私の対象とする課題のスコープと
回答して下さっている方が(勝手に)思い描いている
課題のスコープの差異を指摘なさっているのだと考えますが、
なぜか不思議な事に私の提示する要件の内容に耳を傾けることなく、
ただただ「俺が正しいんだ」
「お前は常識がない・流れ図を理解していない」
と言われ、責め続けられるのみで一向に話が進展しないので、
こちらから具体例を出したまでなのですが。(´･ω･`）

それとももしかして、実際の業務はそのように顧客に接するのが
「正しい SE のありかた」だ、と身をもって
教えてくださっているのでしょうか？

もっといろいろ勉強しなくてはいけない事があるんですね・・・
ありがとうございます。

別にアルゴリズム的には、その数値がキーボードコントローラから来ようが、
マウスで手書き入力しようが、携帯電話からメールしようが、シリアル伝送で来ようが、
VT端末から来ようが、トグルスイッチでDMAしようが、パンチカード読み取り機から
来ようが、念派で書き換えようが、些末なこと。
　そんなことはアルゴリズムを実装・適用する連中が考えればよいわけで、
アルゴリズムというのは、数値はどこからか入力されている、と抽象化した
レイヤーにあるわけ。

>>532,>>546 が本人ならネタ確定。
>>532 は天然ぽくって面白かったけど、
>>546 は天然ぽさが足りなくて全然面白くない。

>>546
仮に出題意図が低レベルのロジックだったとしよう。
それは普通はアルゴリズムとは呼ばないので、このスレで
質問したことが間違い。

もし割り込みとかそのあたりもアルゴリズムだと思ってるなら
計算機科学に関する常識が足りないので、ちゃんと勉強して
おいたほうがよいと思うよ。

組み込み系だったの？
「割り込みピンがアサートされた」のような事まで流れ図に書くようにとは
あの問題が書かれてないから皆に通じなかったのも無理はないよ。
せめてアセンブラレベルかプログラミング言語レベルかくらいは言えばよかったね。

>>549
>仮に出題意図が低レベルのロジックだったとしよう。 
>それは普通はアルゴリズムとは呼ばないので

>もし割り込みとかそのあたりもアルゴリズムだと思ってるなら 
>計算機科学に関する常識が足りないので、ちゃんと勉強して 
>おいたほうがよいと思うよ。 

「アルゴリズム」という言葉についての
非常にラディカルな定義、誠に有難うございます m(_ _)m
（Dekker 先生とかが聞いたら、さぞお喜びになるでしょう）。

「計算機科学」についても今後しっかり勉強していくつもりです。

多分、本物は >>528 までで、>>532 以降は春で沸いた池沼だろ。

久方ぶりにスレ覗いてみたら面白いことに・・

>>552さんの仰るとおり質問を最初にさせて頂いたのは528の私です。
>>532以降は偽者の私ですが、きっと彼も私と似た境遇で必死なんだと
思われますので、住人の方々も手厚く見守ってあげてください。

>>530-531さん、亀レスですが、本当にありがとうございます。自力でやった
のと比較してかなり違っていたので、大変参考になります。ご親切に図まで
書いていただき、感謝感謝です（*´д｀）

このスレも今後時たま覗くと思いますが、これからはまた名無しに戻ります。

いつか自分もちゃんとしたレスができる日を願って・・・

>>551
「非建設的」をインスタンス化した様な奴だなお前。

>>534

＞PC/AT互換機という事でいいでつ。
腹立つわぁ

>>534
キモイ顔文字使うヤツは、首釣って死ねよ

伸びてると思ったら・・・(　ﾟДﾟ)＜氏ね！

伸びてると思ったら、死ね

これはまた凄まじいキャラが・・・

age

でらえもん調査局がいるスレだな

ここはヲタクネタ限定スレ？
カレンダー生成のアルゴリスムで定番なの無い？

カレンダー生成ごときでアルゴリズムもへったくれも無いだろうよ。

kwsk

いつでもいいから（2000年1月1日とか）基準日の曜日を設定して
あとはうるう年のルールを考えて増減するだけでいいんじゃないか？

今時、何とかの公式なんかで曜日を計算するなんて流行らないしね。

夕飯食いながら書いた駄作
#include <stdio.h>

int month_table[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int is_leap_year( int y )
{
return ((y % 4 == 0) && (y % 100 != 0)) || (y % 400 == 0);
}

int days_of_month( int y, int m ) /* m:1〜12 */
{
if( (1 <= m) && (m <= 12) ) {
int d = month_table[m-1];
if( (m == 2) && is_leap_year( y ) ) ++d;
return d;
}
return 0; /* error */
}

int day_of_week( int y, int m, int d )
{
if( m < 3 ) {
--y; m += 12;
}
return (y + y/4 - y/100 + y/400 + (26*m+16)/10 + d) % 7;
}

void print_calendar( int y, int m )
{
int d = days_of_month( y, m ), w = day_of_week( y, m, 1 );
int n, dow;

printf( "Calendar %04d/%02d\n", y, m );
printf( "Sun Mon Tue Wed Thr Fri Sat\n" );
printf( "---------------------------\n" );

for( dow = 0; dow < w; ++dow ) printf( " " );
for( dow = w, n = 1; n <= d; ++n ) {
printf( " %02d ", n );
if( ++dow >= 7 ) {
dow = 0;
printf( "\n" );
}
}
printf("\n\n");
}

int main( void )
{
int m;
for( m = 1; m <= 12; ++m ) print_calendar( 2007, m );
return 0;
}
いじょ。

この流れでツェラーの公式がでてこないのが不思議。

>>569
それはもう既に、>566が予防線を張ってしまった。

return (y + y/4 - y/100 + y/400 + (26*m+16)/10 + d) % 7;

これじゃないのか

●4.3t積のトラックが一台ある。これにバラバラの重量の荷物を積み込む際、過積載にならずに出来るだけ多くの（最大積載量に近い重さの）荷物を積み込む組み合わせを求めよ。

ってNP問題だっけ？
いまHDDの整理してて出来るだけDVDの空き領域が小さくなるファイルの組み合わせを考えてるんだけど

実は4.3テラ…？

>>572
http://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C

なっぷさっく問題？

>>572のは、重さの和に制限があって、重さの和の最大値を求めるわけだから、
>>574リンク先の pi=ci が成り立つ場合だな。

ガーベジコレクタのアリゴリズム掲載された書籍知りませんかぁ？

ガベージコレクタ
アルゴリズム

不要な領域が法則無く発生するのに、アルゴリズム化できるとは思えないけどな。
CPUキャッシュのミスヒットのように、想定外の動作でむちゃくちゃ効率悪くなったりしない？

AABBBBCCCC

このようなソートされた配列がある。
データが変わる位置(上の配列なら0,2,6)を
逐次検索より速く見つけ出すアルゴリズムを考案せよ。

自分で二分検索法を改良した方法でやったら却って遅くなりますたorz

最大値と最小値と増分が判ってんだから例題だったら3等分から始めれば委員じゃね

>>580
一般的にその程度のサイズのデータの処理なら逐次処理が最速だぞ。

複雑なアルゴリズムはデータ量に対する計算量を少なくはできるが、
その１ステップ毎に必要な計算量はたいてい増えちゃうから、
データ量が少ない場合はかえって遅くなる。

>>582
＞一般的にその程度のサイズのデータの処理なら逐次処理が最速だぞ。
その程度のサイズのデータ量じゃないんだろ

>580
もっとサンプリングを細かくした方が効率良くなると思う。
まあデータの偏り具合にもよるが。

>>584
お前、二分検索法をちゃんと理解できてるか？

二分探索の改良法といったら、内挿探索

逐次検索での計算時間は自明にO(N)
２分探索はデータが変わる位置の数はO(N)に比例して,
探索そのものの時間はO(log N)なのでO(N log N)

∴ 逐次探索の方が高速

......と自分の中では直観に反した結論が出てしまった。
自分でもなんとなーく間違ってる気がするので、
だれか偉い人教えて！

データが変わる位置が重要なら、つまりデータの連続性が高いなら
A2B4C4 と記憶しておけばいい。

？

>>587
ふたつ間違ってる。

>データが変わる位置の数が O(N) に比例する
これは問題設定によるので、そうとはいえない。普通は変わる
位置の個数を M として、M に依存した計算量で評価すべき。

>探索そのものの時間はO(log N)なのでO(N log N)
これは実装に依存する。過去の探索の結果を忘れて探索を
繰り返すとそうなるが、過去の情報を保持するように実装すれば
探索木の頂点数が O(N) なので、最悪でもO(N) にできる。

http://pc11.2ch.net/test/read.cgi/tech/1178440398/1-100
会話のアルゴリズムぅ?

オーダは極限をとるから直観には反する
現実問題としてはデータ依存としか言えないね
扱う対象がどれくらいの大きさで、何種類の文字が何回くらい切り替わるのか、
これによって実装は変わる

飛び石のようにn文字ずつ進んでいくか
半分に区切っていくか
オーダをとると後者のほうが計算量は小さくなるけど、一般には前者が速いと思う

suffix　arrayを構成するときの最速の（と思われる）方法って何かわかりますか？

ttp://homepage3.nifty.com/DO/direct_linear_sa.htm

にいくつか紹介されてますが、ソート関係の話は1年違うと速度が大分違うと
聞いたので

>>593
実用上では、MSufSort か libsufsort が最速っぽい。

suffix array はだいぶ煮詰まってるので、
新奇なものが出ない限り、上記2つを追っていれば十分だとおもふ

>>594
おお、どもどもです

ちょっと相談させてください。
数独のプログラムを作っているのですが、インターフェースが出来て、
ランダムで適当な数字を残してやってみても、あまり面白い問題が出来ません。

数独で人間が仮置きとかせずに解けるような問題を自動生成するアルゴリズムって、
どんなのが考えられるでしょう？

>>596
その方法だと解が2通り以上出る可能性もあるな

>>596
そのノウハウで飯が食える人がいるから、そう簡単には教えてくれる人はいないんでない?
ヒント:プログラムで解いてみて、問題ないならOK

>>596
>あまり面白い問題が出来ません。

なにがどうだったら面白い問題とみなせるんだ？
そこを考えれば自ずとわかるような気がするけど。

そもそも数毒って面白いか？

自動生成の問題だと、作業している気分になって萎える。
巧い作者の問題だと、解いててセンスが感じられて楽しい。

ヒント：1/fゆらぎ

>>596
【解答】パズルのプログラミング【作成】
http://hobby9.2ch.net/test/read.cgi/puzzle/1092459010/

>>603
またずいぶんマイナーなスレを…

スレ以前に板が…

日経サイエンスの最新号（８月号）に、囲碁のための新アルゴリズムが登場したニュースが載っていました。

コンピュータによるゲームでは、IBMのディープブルーがチェスの世界チャンピオンを破って話題になりまし
たが、コンピュータが人間に勝てないゲームのうち残っている囲碁に関して、新しいアルゴリズムが開発
され、１０年以内にはプロ棋士を破ることが実現される可能性があるそうです。

ハンガリー人の研究者が、モンテカルロ法を拡張したUCT（日本語では「ツリー構造に適用された上位信頼限界」
というそうですが…）というアルゴリズムを開発し、その効果を高めるために様々な追加研究を行っているそうです。

このアルゴリズムの特徴は、単純にパターンを網羅して、無作為に抽出・評価するモンテカルロ法から発展して、
様々な評価指数を用い有望な選択肢を抽出し評価を行うようです。例えれば、統計的手法から学習的手法に
進化したもののようです。

コンピュータが誕生してから、時間が経ちますが、一歩ずつでありながらも、確実に人間の思考と互角に機能できる
ように、いろいろな人が研究を続けて進化していることを実感します。そして、そのような実験の結果が、部分的でも
家庭用ゲームやラーニングソフトウェア等にも吸収され、コンピュータの活用がさらに進化すればよいなと思います。
http://blogs.itmedia.co.jp/tsuruta/2007/06/post_6850.html?ref=rssall

Dijkstra法の最小経路問題のアルゴリズムの帰納法を使った証明を教えてください！

こんとんじょのいこ

アルゴリズムナタク
１話　俺のアルゴリズムは正しいのだ！
２話　貴様らのアルゴリズムに正義はあるのか！正義はあるのかと聞いている！
３話　アルゴリズムを教えてくれ！ナタク！
最終話　だから女は甘い

多倍長演算の割り算のアルゴリズムで
たとえば521を21で割るとき
↓
まず521が三桁で20が二桁だから答えも二桁だろう
↓
２桁目を決めよう
↓
答えは10かな？21*10＝210で521より小さい
↓
じゃ20かな？21*20＝420＜521
↓
じゃ30かな？21*30＝630＞521（もし90でも超えなければ二桁目は9にする）
↓
大きくなったからおそらく答えの2桁目は2だろう
↓
次は１桁目・・・

こんなのを考えたのですが、もっと良い方法はないですか？

何このマルチレス

車輪の再発明でググれ

n個のボール、k個の横に並べた箱がある。
n=3、 k=4 (A,B,C,D) とするとき、各箱にボールを入れるパターンを考える。
この場合、組合せの総数は 20 となるが、左右対称となるパターン( A=D、B=C ) を
除く条件もある場合、全パターンは以下のような 10 パターンになる。
n、k が任意の値であるとき、同様に全パターンを生成するアルゴリズムはどのようになるか？

　　A　　　　　B　　　　 C　　　　D
○○○　|　　　　　|　　　　　|　　　　　
○○　 　|　○　　 .|　　　　　|　
○○　　 |　　　　.　|　　○　 |　
○○　　 |　　　.　　|　　　　　|　○
○　　　　|　○○　.|　　　　　|
○　　　　|　○　　 .|　　○　 |　
○　　　　|　○　　 .|　　　　　|　○　
○　　　　|　　　　　.|　○○　|
　　　　　 | ○○○ |　　　　　|　　　
　　　　 　|　○○　 |　○　　 |

補足：　↑のパターンは例であり、左右対称パターンのいずれかが生成できれば、
　等価であるとみなすことができるものとする。

>>614 対称パターン例: (1) と (2) はどちらでも良く、等価な1パターンとみなす


(1)
　　A　　　　　B　　　　 C　　　　D
○○○　|　　　　　|　　　　　|　　　　　

(2)
　　A　　　　　B　　　　 C　　　　D
　　　　 　|　　　　　.|　　　　　| ○○○

20個のパターンを全列挙するプログラムで
A > D または (A = D かつ B > C) を
満たすもののみ出力すればいいよ

>>616
確かに、まず「箱毎のボール数」を全列挙するアルゴリズムが出発点ですね。
・・・しかし、nとkが任意の際のうまいアルゴリズムが思い浮かばない・・・

原始的、総当り法

0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
0, 0, 0, 3
0, 0, 1, 0
0, 0, 1, 1
0, 0, 1, 2
0, 0, 1, 3
...
3, 3, 3, 3

時計的な "n+1進数"が k桁の繰り上がりパターンを生成、
k個の数の和が n であるパターンを全列挙する・・・

>>618の着眼を応用して、n桁k進数を生成するようにして、
n個のボールに、どの箱に入れるかを決めるようにしたら。
パターン重複を避けるには、n個のボールに順序性をもたせる。
例えばボールno.2はno.1の左側に置いてはいけないようにする。

全部同じ箱に入るときの重複を考慮しないと逝けないな

>>613の絵を素直に見ると、とりあえず、

n個の○とk-1個の | を一列に並べろ

ってことでいいんじゃないのか？
配列を逆にして同じものはあとで省くということで。

>>617
再帰が使えるなら簡単で、
「n 個の箱に k 個のボールを入れる全パターンは
　先頭の箱に i 個入れて残りの箱に k-i 個入れる
　パターンを全部かき集めてきたもの」
でいい。
対称性は後で除いて十分 （計算量は O( nCk ) なので変わらない）

>>618
その計算量は O( n^k ) なので、
パターン総数 O( nCk ) に対して漸近的に悪い。

>>618に似てるけど、着眼点を変えて

A,A,A
A,A,B
A,A,C
A,A,D
A,B,A ← 降順が含まれるのでなので無視
A,B,B
A,B,C
A,B,D
A,C,A ← 降順が含まれるのでなので無視
A,C,B ← 降順が含まれるのでなので無視
A,C,C
A,C,D
A,D,A ← 降順が含まれるのでなので無視
A,D,B ← 降順が含まれるのでなので無視
A,D,C ← 降順が含まれるのでなので無視
A,D,D
　：
　：
D,D,D ← 降順が含まれるのでなので無視

A,B,C,Dをそれぞれ0,1,2,3に置き換えると「n桁のk進数」となる。

ごめん、日本語がおかしい上に頭もおかしかったｗｗ

>>621
そうかK-1回のループと変数2個配列2個くらいでいいのか。頭いいな
左右から交互に左>=右になるよう|を置いていけば
一発で重複パターンなしに生成できそうだ

>>621
パターン生成内容としてはそういうことかな。
>>625の実装イメージがまだ理解できず・・・


n個のボール、k個の箱の左右対称分を除いたパターン数は組合せの式で
(n+2)! / ( (k-1)! * (n-k+3)! ) でいいのだろうか。

n=3, k=4 だと 5! / ( 3! * 2! ) = (1*2*3*4*5) / ( (1*2*3) / (1*2) ) = 120/12 = 10

最初に10通りと分かって、そこから 0〜9 番目のうち x 番目のパターンはコレ、とやるには
やはり結果を配列に入れてことになるのかな。

ボール数: N
箱の数: K
箱内のボール数: NumBall[ K - 1 ]

パターン数: NumPattern= getNumPattern( N, K )
パターン番号: x ( 0 ≦ x ＜NumPattern)

x を指定したとき、対応する NumBall[ 0 ] ... NumBall[ K - 1 ] を求めよ

単純な計算式では出せない…よね？

よく考えたらK-1回じゃ無理じゃん、オレだめだな
アルゴリズム分かったけど携帯じゃ打ち込めないorz

> n個のボール、k個の箱の左右対称分を除いたパターン数は組合せの式で
> (n+2)! / ( (k-1)! * (n-k+3)! ) でいいのだろうか。

違うな。
Excel だと COMBIN(n+k-1, k-1)

COMBIN(n+k-1, k-1) は左右対称分を含むパターン数。

これで全パターンを格納する配列を確保できる

そして2で割れば重複分を除いたパターン数になるのだ！

#define N (10)
#define K (4)

struct stPattern
{
int NummBall[ K ];
int nDec;
int nDecRev;
};

int ipow(int nValue, int nPower)
{
int nRet = nValue;
int i;

for (i = 2; i <= nPower; i++)
{
nRet *= nValue;
}

return nRet;
}

int combi(int n, int r)
{
int i, p;
p = 1;

for (i = 1; i <= r; ++i) {
p *= (n - i + 1);
p /= i;
}

return p;
}

ソース貼りマンドクセ・・・ダサい実装
http://tool-ya.ddo.jp/webfs/~enigma/hoge.zip

DL/解凍パス
　NumBallPattern

0 : 3 0 0 0
1 : 2 1 0 0
2 : 1 2 0 0
3 : 0 3 0 0
4 : 2 0 1 0
5 : 1 1 1 0
6 : 0 2 1 0
7 : 1 0 2 0
8 : 2 0 0 1
9 : 1 1 0 1

N=3、K=4 の実行結果

include省略、拡張子 .c なのに new があったり、と
よくわからん上に、n = 6, k = 12 でさえ相当の時間がかかる。
ダサいというか、ひどい。

ほい。
#include <stdio.h>
void dispList(int *box) {
int i,e;
for(i=0;box[i]>=0;i++)/**/;e=i-1;
for(i=0;i<=(e-1)/2;i++){
if(box[i]<box[e-i]) return;
if(box[i]>box[e-i]) break;
}
for(i=0;i<=e;i++) printf("%d ",box[i]);
puts("");
}
void genLists(int *box,int n,int k) {
int i;
if(k==1) {
box[0]=n;
dispList(box);
}else{
for(i=n;i>=0;--i) {
box[k-1]=i;
genLists(box,n-i,k-1);
}
};
}
int main() {
int n=3,k=4,*box;
box=(int*)malloc(sizeof(int)*(k+1));
box[k]=-1;
genLists(box,n,k);
system("PAUSE");
return 0;
}

びっくりするくらい同じコードだ

http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/4817.c

>>637
実際はVC++でcpp、includeはコピペ忘れ。
書いていなかったけど、Kは6、Kは16くらいまでの上限を想定している。

>>638
スマートで速い。これの方がずっと良いね。

ソース見ている間に >>639も・・・ありがとう

あとは >>627 への対応か・・・xを決めたときに対応する箱毎のボール数が出るように

順番が指定されていない限り、その問題には答えられない

>>639
うわ、びっくりしたw。オレんと違ってデータ残してるのね…
>>642
ゴメン。627のことはすっかり忘れてた。 639さんの使ってけれ

最初はデータを残してなかったからもっと同じだったけど
613 が残していたのでそれにあわせたのです

>>643
パターンが網羅できていれば、順番は特に問いません。

>>638のソースをベースに、>>639のデータ記録を盛り込もうと試行中・・・

みんなのお陰で問題解決できたよ。ありがとう。

問題を単純化しようとして敢えて”ボール”と”箱”にしたけれど、本当はバス線の分岐パターンを網羅したいという問題。
バス線につながるノード数と分岐数を決めたとき、全体としてありえる接続パターンを無駄なく網羅したかった。
だから左右対称のパターンは要らないとかの付加条件も発生。

仮にノード数を 8、分岐数を 3 にするとき、バス両端の 2ノード、"分岐"を必ず発生するための 3ノードは固定条件で、
残り 3 ノードをどの各分岐点にいくつ接続するパターンはいくつで、具体的にどうか？という問題になる。

分岐数が変わっても問題を定義できるよう、バス両端のバスを (ノード数 - 2 + 1) 個に分割して考える。この例だと

　　　　　　N03　.N04　.N05　.N06　 .N07　N08
　　　　　　.│　　.│　　 │　　.│　　 │　　.│
N01─B01┴B02┴B03┴B04┴B05┴B06┴B07─N02

とB01〜B07の7本。分岐数を 3 にするということは、B02〜B06 のうち 3本の長さをゼロにする処理になる。
長さゼロにすべき3本の組合せパターンを網羅し、そこからランダムに一つ選んで、残りの長さゼロではないバス線と
分岐線による別の処理を・・・というところに行き着ける土台ができますた。

この例のパターンを示すソース
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/4819.c

>残り 3 ノードをどの各分岐点にいくつ接続するパターンはいくつで、具体的にどうか？という問題になる。

残り 3 ノードをどの各分岐点に接続するパターンはいくつで、具体的にどうか？という問題になる。

くそ天皇　くそ天皇　くそ天皇　くそ天皇

いい加減死ねっつってんだろ屑ニートくそ天皇が

相変わらず病的な粘着っぷりだな屑ニートくそ天皇が

毎日毎日毎日粘着出来て良いでちゅねくそ天皇

くそ天皇さっさと死にやがれゴミが

東京に在住している精神病珍米糞ニートくそ天皇君の末路

さっさと精神病院逝くか首吊って逝くか選べや糞天皇が

早く死ねよ糞ニート天皇が

粘着精神病屑ニート天皇君は自らニートくそ天皇であると公言しました
さっさと死ねやくそ天皇が

早く死ねっつってんだろ屑ニートくそ天皇が

お前みたいなゴミクズ天皇は息してるだけで空気が汚れるからさっさと死ねや

とっと死に晒せや糞ニート天皇が

どの各・・・益々ボケてきたorz

くそ天皇　くそ天皇　くそ天皇　くそ天皇

いい加減死ねっつってんだろ屑ニートくそ天皇が

相変わらず病的な粘着っぷりだな屑ニートくそ天皇が

毎日毎日毎日粘着出来て良いでちゅねくそ天皇

くそ天皇さっさと死にやがれゴミが

東京に在住している精神病珍米糞ニートくそ天皇君の末路

さっさと精神病院逝くか首吊って逝くか選べや糞天皇が

早く死ねよ糞ニート天皇が

粘着精神病屑ニート天皇君は自らニートくそ天皇であると公言しました
さっさと死ねやくそ天皇が

早く死ねっつってんだろ屑ニートくそ天皇が

お前みたいなゴミクズ天皇は息してるだけで空気が汚れるからさっさと死ねや

とっと死に晒せや糞ニート天皇が

>>647
敵を騙すにはまず味方から・・・って俺らを騙したのか！！！！？

いや、良い問題の簡単化だと思うよ。
俺は最初から >>647 の書き方をされたら、
読む気が起きなかったと思う。

AI人工知能のお勉強はこちらからどうぞ
ttp://www.1101.com/morikawa/index_AI.html

http://ss.nkk.affrc.go.jp/library/publication/seika/seikajyoho/2003/15/15.html
に記述されている、
図４の(a)から(b)の結果はどのようなアルゴリズムになりますか？

結果はアルゴリズムではありません。

マルチうぜえ

>>656
過程を知りたいわけです。

ボゴソートについて語ろうぜ

実際に実装しようとするとかなりと面倒だな。

age

はじめまして。プログラミングの勉強してるものです。
アルゴリズムについて質問があります。質問はどこでしたらいいのか
分からなかったのでこちらに書かせていただきます。スレ違いかもしれませんが
お願いします。もしアルゴリズムの質問板があるならそちらも教えていただけるとありがたいです。

C++言語を使っています。質問です。
４種類の連続した数値のデータがあります。４種類の測定時間や時間間隔は一緒です。
その４種類をひとまとまりとします。そのまとまりがいくつかあります。
それぞれのまとまりから一部分だけを取り出します。その一部分のデータの特徴を
どんどんと集めていき４種類のデータの特性を求めたいです。その方法がわかりません。
すいません。ホントシロートです。質問の意味がわからないかもしれません。
でも本当に困ってます。ヒントだけでもいいのでお願いします。

プログラムが違うのかもしれませんが、
「似たようなデータをどんどん記憶していくことによりそのデータ達の
特性を求める」ということかなと自分では考えたのですがその方法も分かりません。
方法を知っているとかこんなコマンドがあるなど本当に何でもいいのでよろしくお願いします。

４種類のデータはヘリコプタの制御に使う、スロットル、エルロン、エレベータ、ラダーです。
特性はホバリングをしている時の４種類のデータ入力の特徴を見つけたいです。
よろしくお願いします。

マルチすんな。

>>662
取り敢えず、「ヘリコプタ」「ホバリング」「制御」で検索して、見つかったサイトを全部読んできてくれ。

こっちでやってあげるからデータだけくれ

プログラム初心者です。
アルゴリズムとロジックの違いはなんですか？
新人研修で先輩に質問したら、ググレカスのひとことで片づけられましたが
いまだに謎が解けません。
よろしくです。

>>
アルゴリズムというより統計の分野ではないでしょうか。
ヒストグラムとか散布図とか描いてみればいかがですか？

アンカーつけ忘れ
>>662
アルゴリズムというより統計の分野ではないでしょうか。
ヒストグラムとか散布図とか描いてみればいかがですか？

>>666
アルゴリズムよりもロジックの方が大きな概念なんじゃないでしょうか。
アルゴリズムならロジック的である。
ロジック的だからといってアルゴリズムとは限らない。

何処かの雑誌でアルゴリズムとロジックを解説してたな。
アルゴリズム：代数的な要素をもった解析可能な処理手順。
　　　　　　　　または特定の言語に寄らない処理手順の記述　
　ロジック　：コーデイングよりの処理手順

チューリングマシンで表現できるのがアルゴリズム
公理と推論規則で構成するのがロジック

>>670
そんな本は捨てたほうがいいな

理由は？

ロジックの定義が根本的に間違ってる

じゃあ正しい定義は何？

>>671 が見えないのか？

>>671が定義に見えるのか？

アルゴリズムは理論で、ロジックは論理だろ

つまり？

ののたん最高！

>>677 >>671以外，どう定義しろと？

AはBである⇔BはAである

アルゴリズム ＝ 処理方法
ロジック ＝ 実装されている処理方法

でないの…何か違うな…

それ区分けしてなんか意味あんの?
そんな明確な定義が周知されてない言葉なんか場に応じて使い方が異なるに決まってんだろ

>>679
アルゴリズム（理論）はロジック（論理）で実装される。

実装だと語弊があるな。「構成される」と言い直そう。

AVL木と赤黒木を実装したんですけどなんかほとんど変わらないっつーか
AVL木の方が性能が良いんですがなんか間違ってますか？
赤黒木の方が使えるとか聞くんですけど。

どのくらいのデータサイズでどういう操作を何回やったのを比較したのかがわからないと何ともいえない

age

アルゴリズムがそのままロジックとして実装されるとは限らない。
バグがあるかもしれないし、処理範囲を限定して実装されるかもしれない。

あのさ質問があるんだけど

アルゴリズムの性能評価って何してるんだ
意味わかんね

分かる人いたら教えてクダーサイ

アルゴリズムの性能を評価しているんでしょう、きっと。

>>691
ということで、性能とは何か ということが焦点になると思う
アルゴリズムの性能 というのは何を意味するのか
ブラックボックス的な評価で言うなら
・機能を満たすこと
・メモリ使用量
・速度
この３つの観点に絞られるような気がする

algorithm初学者です。
C言語の学習とあわせて学習してます。

search algorithmについて質問です。
10冊ほどパラパラと実際にalgorithmのテキストを見て吟味しましたが、
どの本もツリー・スタックといったありきたりのデータ構造を前提として
そこからいかに高速に少ないメモリ使用量で検索するかという話になっていました。

私は、データ構造をいかに工夫するかという方向でも考察したいのですが、
手がかりになるテキストはありますでしょうか???
また、前提となる知識にどういったものがありますか??
数学については大学教養レベルまではかろうじてある程度です。
computer scienceについてはド素人です。

たとえば、データ使用頻度に応じて機械学習で動的に検索の仕方を変えるとか、
データエントリに優先度を指定したり、データエントリ間に距離を定義したりすると
有益な検索システムが出来そうな気がします。
「そういうことは普通やらない」or「そういうことは既に考え尽くされている」のだとしても、
そういうことを自分でしっかり考えてみたいんです。

よろしくお願いします。

>>694
具体例を挙げれないので申し訳ないが、
論文を探してみるのも良いかと思うよ。

前から思っていたんすがこの前教授がアルゴリズムの寿命がどうたらこうたら
いっていたんですが何でアルゴリズムに寿命があるんでしょうか？
アルゴリズムってプログラムだから寿命もくそも無いと思うんですが
頭悪い僕に簡単に教えてくれないでしょうか？お願いします。

よりよいアルゴリズムが開発されて古いアルゴリズムが広く実用的には使われなくなったって意味じゃないのか

ああ、一部の分野ではそういうこともあるよな。
よく考え付くよって思うよ。

>>694
> たとえば、データ使用頻度に応じて機械学習で動的に検索の仕方を変えるとか、

漢字変換アプリで1回変換したのは候補の最初に移動するって
のはあるけど、使用頻度の低い奴をスワップアウトするとかは
どうすんやろ、逆に教えて。

> データエントリに優先度を指定したり、データエントリ間に距離を定義したりすると
> 有益な検索システムが出来そうな気がします。

これはどう役に立つの？

>>694
データ構造で最近面白いと思ったのは succinct structure だな。
興味があったら調べてみて。

>>695
論文というとACMとか情報処理学会とか入ったほうがいいですかね。
オススメの論文誌ありますか。
ipsjは一度入ってたんですけどね、学生会員だから安いと思って。

>>699
前半は初学者なので分かりません。
後半はサーチをする順序の問題です。
優先度をエントリごとに与えることで優先度の高いものから順にサーチすることにより高速にデータが見つかる可能性が高まります。
優先度自体は人間的主観に基づいてつけるものなのでアルゴリズムの問題ではないですが、
それをどう動的に付け替えるかといったことはアルゴリズムをどう適用するかという問題だし、実践上役に立つと思います。
距離を定義することで、エントリ間の類似度が定義されますと、似たものどうしをまず一通り探すという深さ優先的なサーチをするのか
とりあえずいろんな種類のものをひととおりサーチするという幅優先的なサーチにするのかといった選択も可能になります。
すると、状況に応じて適したサーチメソッドの選択ができるようになります。
ツリーとかスタックといった定型的なデータ構造に限らないより一般的なデータ構造において、どうサーチをするのかということを
考える際に有益だと考えました。
もちろん以上は素人考えなので間違いも含まれると思います。
忌憚ないご意見ください。

>>700
succinct data structureというのはチラッと見た覚えがあります。
是非調べてみます。ありがとうございます。

>>701
検索対象に対して優先度を計算し直した時点で
すでにデータをナめてることになるんだけど・・・
だからあり得ない []

距離じゃなくてシグネチャとかハッシュ値の一致するものの
中から探すってのならあるけど。
こっちなら検索対象との距離じゃなくてただの絶対的に計算できる
値だから

学生なら大学経由で論文落とし放題というイメージがあるのだが、
大学によって違うのかな？

>>702
> 検索対象に対して優先度を計算し直した時点で
> すでにデータをナめてることになるんだけど・・・
ド素人の意見なので、通じないかもしれませんが、
私の考えとしては、検索のたびに優先度を計算しなおすのではなくて、
前もって優先度を指定してデータを格納しておき、そして毎回の検索に役立てるというやり方がいいかな
と考えました。

>距離じゃなくてシグネチャとかハッシュ値の一致するものの中から探す
なるほど、前もってデータを分類しておき、検索速度を上げるんですね。
私の興味があるのは、テキストデータのような容易には一律な分類が出来ないもの
(あるいは一律に分類してしまうと強い作為性が生じてしまい実用に耐えないもの)です。
そういった場合に、距離を定めるといいのではと思いました。

>>703
大学生のときにはipsj入っていたという意味で、今は卒業しています。
卒業生として図書館利用することもできますが遠隔地なので手間です。

追記
距離を定めるといい、と書きましたがこれは一例で、
そういった言わば「変な」「特殊な」数学を駆使した技術でこれまでにないことが出来たら
面白いと思っています。
私は学究的に変で特殊なことだけをやりたいのではなく、一つの選択肢として出来れば面白いと考えている程度です。
もちろん、スタンダードな理論も学習するつもりですが。

新しいことが何かを見定めるには地道なサーベイが必要だよ。
めんどくさがらずに沢山の論文を読むことだね。

>>706
ありがとうございます。ACM, ipsjに入ることにしました。

論文といった大それた話とは別に、データ構造の側の工夫というのが行われてはいないんでしょうか。
例えば、RDBでデータの格納のしかたを工夫することで検索コストとスピードを上げるだとか、
Googleなどで使われているようなテキスト検索技術だとか。
アルゴリズムとは違う話なのかもしれませんが、そういうのにも興味があって、アルゴリズムではそういうことは扱わないのかな
と思いました。

ACM・・・マーメイ・・・

googleとかRDBか。確かに気になる
namazとかか

既存のデータ構造以上のものが作れる可能性のある人間がこんなところで質問するわけねーｗ

あけおめ！！

>>693
他にも。
・安定性（データによって所用時間が大きく変動しない）
例：クイックソートでは、ソート済みのデータソートには時間がかかる
・確実性
例：漸近法では解が発散することがある。

>>710
既存のデータ構造以上のものを作る、が希望要件ではなくて、
今年中をめどに、アルゴリズムに関する学習を徹底してやる、というのが希望するところです。
来年からは違ったプロジェクトが発動するので、それのための準備期間です。

だから、学究的な立場でデータ構造を研究して成果をあげたいのではないです。
そうではなくて、ド素人からプロの知識レベルくらいになりたいということです。
そのためにリサーチをかけて、本を10冊ばかりざっと読みましたが、どうも求めているような
高い水準で特殊な実用にも耐えるタイプの本がすくないということです。
一番面白かったのは『情報の構造』という本でした。
これは他の本と違って、ユニークなデータ構造をからめたアルゴリズムの記述が多々ありました。
そこで、こういったタイプの本が他にもないか、と探していたのです。

高度な技術というものは細かくみれば基礎の組み合わせだけだったりする。
実用的なものほどそういう傾向が強い。
ユニークなものは大抵アカデミックに留まるもんだ。

>ド素人からプロの知識レベルくらいになりたい
焦らない方が…

何故ド素人の君がその10冊の本に載っていたものが実用に耐えない低水準なものだと分かるのか

素人なら素人らしく一般的なもので満足しとけ。
無理に変わったものに手をだそうとするのは時間の無駄。

>>714
一年猶予期間があります。それまでにプロフェッショナルになることは不可能な話では
ないでしょうか。いきなりプロになろうとしているのではありません。
昨日も100ページほど本をじっくり読み進めました。
ゆっくり確実にコツコツとやろうとしていますので、どうかその意図をご理解くださると嬉しいです。

>>715
よく見かけるアルゴリズムが低水準だという意味ではないので、誤解のある書き方をしてしまいました。
申し訳ありません。
私が言いたかったのは、私の想定する特殊な用途のためには、ハイパフォーマンスを発揮できないのではないか、
ということです。
たとえば、ネットワークルーティングアルゴリズムを実装するのにはどんなデータ構造が適しているでしょうか。
グラフ構造というちょっと手強いデータ構造を必要とするかもしれません。
つまり、どんな状況でどんなデータ構造が必要とされてくるか分からない状況で、
stack, treeといった初歩的なdata structureだけしか知らずに太刀打ちしようとするのは無謀だと考えたのです。
プロフェッショナルなスキルを身につける上では、当然グラフ構造、ひいてはグラフに関する
数学理論も理解したいものですよね。
私が言う特殊な状況での高水準というのはそういうことです。
まだどんな仕事がくるか分からないので、そういう万全な勉強をしたいのですよ。

>>716
はい、変わったものを要求しているわけではないことは上の記述でご理解いただけたのではないかと
思います。
逆にお聞きしますが、スタンダードなデータ構造でいかにプロフェッショナルな仕事をするかという方向性でも
今後一年勉強する予定なのですが、その場合私が見かける書籍での学習では不十分な気がしてなりません。
何かアドバイスください。

間違えました。

×　不可能な話ではないでしょうか。
○　不可能な話ではないのではないでしょうか。

論文検索や学会誌を漁って参考文献を遡ったほうが早い

>>719
そうします。助言ありがとうございます。

Knuthの基本算法は読んだ？

とても困っています。
アルゴリズムの問題を下に示します。

今、n個の数字を大きい順に並び替える事を考える。
ただし、同じ数字がある場合、これらは等価と見て並び替えなければならない。
つまり３つの0を考えた時、これらを
0a, 0b, 0cと見て、
これをソートした場合、毎回同じ並びになってはいけないものとする。
このようなソートアルゴリズムを考えよ。

良い方法はありませんかね。

>>722
宿題か？スレ違いだぞ。

通し番号つけてその番号でソートしろ。
毎回同じ並びになってはいけないって毎回同じデータが来るのか？
だったらn通りの組み合わせを全て出現させる方法を調べろ。
その方法で同値部分の通し番号をつけ直せ。

>>722
あるよー

stable_sort

>724
>724
>724

>>722
permutation

>>722
ソート時の大小比較の判定を，2つのoperandの値が等しい時は乱数で決定するようにすればどう？

いや、乱数で予測不明にするんじゃなくて、毎回同じ並びに決定できるようにするんだろ？

>毎回同じ並びになってはいけない

「毎回同じ並びでなければならない」だろう。常考

> ただし、同じ数字がある場合、これらは等価と見て並び替えなければならない。

というのが問題の意図なんだから、毎回同じ並びだとおかしい。

同じ数値がある場合は全組み合わせを列挙してしまえばよいではないか？

ふつうのソートとさほど変わらないような時間でやり遂げたいんだろうな

非効率的だけど単純に要素をシャッフルしてからソートすればいいんでないかい？
random_shuffle() -> sort()

どうやってランダムのシャッフルをするの？

クイックソートの入れ替える要素を選ぶときに、比較要素が等しい場合は適当な確率で入れ替えるとか。

>>734
シャッフルの計算量ってO(n)だから
十分効率的だよね。俺的にはそれでFAです。

同じになっちゃいけないんだからランダムはまずいんじゃね？

>毎回同じ並びになってはいけない
が「毎回必ず違う並びにならなければならない」なのか「必ず毎回同じになるようではならない」なのか

"同じ並びが出てはいけない"とすると、場合の数を出しつくした後の挙動に矛盾が出る。
まあボゴソートでいいんじゃない？ 実装簡単だし。テストが大変かもだけど。

ボゴソートって初めて聞いた。
調べたらプチわろたｗ　なんという天に任せる手法ｗｗｗ
投げやりすぎｗ

最初は後ろに追加していって最後にまとめてソートするのと、最初から順番通り挿入していくのでは、
前者の方が早い？

>>739
論理が破綻しているんですか？
~(毎回同じ並びになる)
って事だから、同じやつが連続で出てもいいが、無限回やって
毎回同じ並びになるのはやめいって事だよ。

あったまわる・・

>>741
これはソートというのか・・・
カード投げて拾うとか・・・

後者は所謂挿入ソートなので平均計算時間はO(n^2)になるが、
前者はソート法を選べるから例えばクイックソートを使えばO(n logn)になる。
従って、追加するデータがランダムならば前者がいい。
しかし、例えばカードゲームの持ち札のように常に部分がソートされている必要がある場合は
後者の方がいいとも言える。

>>743
http://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%B4%E3%82%BD%E3%83%BC%E3%83%88

どっかに、各ソートアルゴリズムの動きを比較して見られるようなサイトはないかなぁ。
例えばこんなのが並んでいるだけでもいいんだけど。
ttp://ja.wikipedia.org/wiki/%E7%94%BB%E5%83%8F:Bubble_sort_animation.gif

permutation

>>744
doubt

b-tree

ランダムな確率でランダムに入れ替えるという発想はいかんだろうか？

>>722
もしかして "stable sort でなければ何でもいい"って, 話なのではあるまいか?

おまいらは最強のボゴソートを知っているのか？
俺はあのソートの背景にある理論を知って涙を流した。

笑い涙だが。

俺は鳩の巣理論によるロンドン髪の毛話に感心したものだった

鳩ノ巣原理って中学受験で良く出るやつだな。

田中幸雄はカツラじゃないよ

えらいスレが延びてると思えばwww

>>742
うん

>>751
教えてください

c言語で、０〜５の乱数を取得する時

rand() % 6;

よりも

rand() / (RAND_MAX + 1.0) * 6;

の方がいいんですか？
なぜですか？

整数と実数

>>758
俺は前者の方が読みやすくて良いと思うけど、
後者の方にもメリットはある。

rand関数の実装方法は処理系依存で内部がどうなってるかわからない。
ただ、完全な乱数をコンピュータで手軽に作りだすことは出来ないから、
当然何らかの疑似乱数関数になっている。

その疑似乱数はあくまでも疑似で、実装によっては
もしかしたら一番下のビットが必ず0になるようなアホな設計かも知れない。
そんな場合、rand()%6 だと0 2 4しか取り出せなくなってしまう。

そういう場合、乱数の範囲から特定する方法（後者の方法）ならば
まず間違いなく0〜5の値を出力することが保証される。

多分こういうことだと思う。何か他にもあればだれかプリーズ

RAND_MAXが6の倍数じゃないと分布に偏りが出る。

RAND_MAXが32767である実装は世の中に多いが（VCとか）、
0〜5なら問題ないが

int x = rand() % 10000;

とかした場合、明らかな偏りが発生してしまう。

rand() / (RAND_MAX + 1.0) * 6;
これも偏りが発生すると思うんだが。
0-32767 -> 0-5
という変換なんだから。
擬似乱数スレに回避する方法があったぞ。

リソースが許せば、メルセンヌツイスタ拾ってきたほうが早いな。

擬似乱数の多くは線形合同法だから　0〜5が欲しいなら余りを求めるんじゃなくて割り算するのよ

実際は、2^ビット幅/6 と掛け算して、上位ワードを採用するんだけどね

一体いつの時代の話ですか

>>763
多分勘違いをしていると思うが、% 10000 で [0 .. 9999] にするとき、RAND_MAX が 32767 なら、
[0 .. 2767] が４通りになり、 [2768 .. 9999] が３通りになる。
>762 は、この４通りの部分がゼロ方向に集まることを指しているのだと思う。
[0 .. RAND_MAX] を [0 .. 9999] に線形に写像すれば、４通りの部分が全範囲にわたって均等に分布するようになる。
それでも４通りの部分をなくそうと思ったら、擬似乱数スレにあるように、RAND_MAX - (RAND_MAX % 10000) 以上を棄却するとよい。すると、どちらの方法でも均等になる（元の乱数が均等なら）。

[0,1,2, ..,N-1] のN個の整数から一つ選ぶ乱数を次のように実装すると
(int)(rand() / (1.0 + RAND_MAX) * N)

rand() は理想的な乱数生成器だとして、N = RAND_MAX - 1 ならば、
0になる確率が2/RAND_MAX、それ以外は1/RAND_MAXになるよね。
線形な写像でも誤差のせいで均等にならない場合もあると。

>>763 が言ってるのはこのことではないような気もするが

>>766 いつの時代ですかって、CのライブラリだろうがDelphiだろうが
みんな標準で入ってる乱数は線形合同法だよ。

あ、でも、間違えてる　乱数と掛け算するんだった。

Ｄｅｌｐｈｉｗｗｗｗ
一体いつの時代の話ですかｗｗｗｗｗｗｗｗｗｗｗ

文字列で指定した式を解析するのに
二分木で逆ポーランドに変換してからやる方法をさっき知って感動した

いつも思うんだけどさ
ポーランド記法が既に逆ナンであって
逆ポーランドって言ってしまうと
元に戻ってないか？ってことなんだ

>767,768
そういう意味だったのか。
でもなんか中途半端というか偏りを散らした(写像変換した)だけで
本質的な解決策じゃないように感じる。
それに、整数 -> 整数 の変換に実数キャストが挟まるのが凄く無駄に思える。
実数の実装も考慮してないし。
棄却するパターンの方が数学的に美しい。と思う。

>>758
大抵の実装は線形合同法。線形合同法の乱数は、そもそも特性が悪い。
そして下位ビット程特性が悪いんだ。
だから、余りを使って下位を採用すると隔たりが普通より大きくなるんだよ。

0〜5の乱数が欲しいなら余りじゃなくて上位を採用しなければいけない。

というのと
rand() % 6; 　は割り算が必要だけど

rand() / (RAND_MAX + 1.0) * 6;
は (RAND_MAX +1)は通常は２のべき乗だから、掛け算＋シフトで計算出来るから
大抵のCPUで後者が高速という

２つの理由がある。

gcc -O3 on core2duoで実測してみたけど後者が遅かった記憶がある。

>>776
それはgccのRAND_MAXがint型の最大値に近いから、じゃない？

>>776 まさか、このまま実行したんじゃないの？
イメージとしては
(long)rand() * ( 1L<<32L )/6L )>>32L;

アセンブラコードだと EDXに2^32/6を入れて
　 MUL EDX
　 MOV EAX,EDX

>>778
あー
ゲームとかではあるかもしれないけど、アルゴリズムスレの扱う範疇からは外れてるね

移植性が無さ過ぎる

君は実にばかだ

よく言われる

>>775
「偏る」を「へだたる」って読んでる？

さすがにそれはなかろう

>>774
>実数の実装も考慮してないし。

え？　intへのキャストを外すだけだろ。
rand() / (RAND_MAX + 1.0) は区間[0,1)
（rand() / (double)(RAND_MAX) なら区間[0,1]）
の実数の乱数だからな。

>>768 のひどい誤差は整数変換のせいなので
むしろ実数の方が均一でより理想的なんだが。

>>775
なにが高速だって？

実数の配列A,Bから
最も値の近い要素の組A[k],B[l]を求める良い方法はないですか？

Aの各要素にA由来という印とインデックスを付加
Bの各要素にB由来という印とインデックスを付加
二つを合わせて配列CとしてCをソート
Cを先頭から走査して隣り合う要素の由来が違うもので差が最小のところを探す
ってのは？
まぁ合わせないでAB別々にソートしてもできるけど

なるほど、つまり
AB別々にソートしてからマージの要領で
比較していけばいいんですね。
ありがとうございました。

ソートアルゴリズムに興味があるんですが、
Ο記法とか計算時間の算出部などの計算式の意味がさっぱりわかりません。
Ο(n log n)とか意味がわかりません・・・
文系で最後に数学に触れたのは高2だったので、とっくに忘れているし元々数学は得意ではありません。
自分もそのうち効率は悪くても自分なりのソートアルゴリズムを考えてみたいと思っているのですが、
何から勉強をはじめたらいいでしょうか？

初心者向けのアルゴリズム入門の本なら、Ο記法の説明してあるのもある。
さすがに、log の意味から書いてあるのは少ないと思うが、
それくらいは高校の教科書読んで勉強してこいよ。

>>789
nは要素数でO(n log n)はnが増減した時の計算量の増減。
O(n^2)ならnが倍になると計算量が4倍になるってだけ。(3倍なら9倍)
計算量はあくまで計算量なんでアルゴリズムによって単位量あたりの
計算の複雑さは違うからね。
nlognなやつでもクイックソートとヒープソートは速度が大分違う。
メモリの局所性の問題とかもあったりする。

余計なお世話だと思うがソートは優秀なものが出尽くしてしまっているから
今更考え出すより既存のものを学んだ方が良いよ。

==俺様用しおり=========================

今日はQTクラスタリングというのを知ったので
このスレにメモっておく。

ソートアルゴリズムを知らない状態から自分なりのものを作ると高確率でセレクションソートになる気がする。

高校の頃、自力で挿入ソートに辿り着きましたが。
マージャンプログラム作ってて発見したよ。

>>791
いろいろ間違ってるよね。O は計算量とは無関係な概念でしょ。

は？

f(n) = O( g(n) ) であるとは、ある正数 C と正整数 N が存在して
任意の n ≧ N に対して f(n) ≦ C g(n) が成立することをいう

が、オーダ記法の定義でしょ。

計算量をオーダ記法で表現することは多いけど、別に関係はないよね。
オーダ記法で計算量を表さない分野だってあるよ。

>>797
ほー勉強になるが全く意味がわからんわｗ
アルゴリズムって難しいね

オーダ記法は計算量の理論の研究の中から生まれたもの
だから密接な関係があると言うのが普通
概念として独立させることができるとしても

>>799
> オーダ記法は計算量の理論の研究の中から生まれたもの
このことのソースは？

私の認識では、そんなことは年代的に絶対に有り得ない。

計算量の理論は通常はコルモゴロフの1950年か
チューリングの1936年をスタートだと考えるはず。

一方、オーダ記法自体はバッハマンの1894年が初出で、
広く使われるようになったのはランダウの1909年くらいから。

オーダ記法のほうが古い歴史を持っていると思うのだけれど。

＞計算量の理論は通常はコルモゴロフの1950年か
＞チューリングの1936年をスタートだと考えるはず。
ダウト

では、あなたはいつからだと考えるのが自然だと思うの？

Wikipedia を見てみたが，確かに私の勘違いだったようだ．スマン．

ソースはWikipediaかよ

>>804
まあ大目に見てやれ。
その前は脳内ソースだったんだから。

こんなのみつけた。ソートを可視化するスクリプトなのか？
http://d.hatena.ne.jp/ytakamiya/20080125

Wikipediaにも画像あるし

っつーか10年くらい前に
技術評論者のSoftwareDesign(いまもあるのか？)が記事で
CQ出版のInterfaceが既に過去に取り扱ってた画像を
そっくりそのまま盗用してしまってお詫びしていた

>>807 でっていう。

suffix arrayは名前の通り、後ろからのインデックスを作っていく様ですが
なぜ前からじゃないんでしょうか

>>809
文字列系アルゴリズムでは prefix より suffix のほうが有用だ
（と思われている）から。

BM法とか

>>809
prefix tree, prefix list などがあるよ。

あるアルゴリズムの概念はわかっていても、それをどういう風に実装するかとなると、
自分のレベルが低いため、難しくて実装することができません。
やり方を暗記してしまえば問題ないのですが、
暗記に頼るのではなく、考えてちゃんと実装できるようにしたほうがいいでしょうか？
それとも暗記しとけばいいでしょうか？

意味がわからん

>813
同じアルゴリズムを毎回毎回実装するなんて愚かしい。そういうものはライブラリとして持っておくべき。
ということで、実装方法を暗記しても意味がない。

結局、何かやりたいことを実現する＝アルゴリズムを考えて実装する、になるし何もかも既存のアルゴリズムが
流用できる、なんてなるわけないから自分で考える必要はでてくる。
その練習として、有名どころのアルゴリズムを自分で実装してみて他の実装と比べてみるというのはいいことだと思う。

実装方法が分かって、うまく動けばそれで満足するけどね。
実装できないと言うよりも
適切なアルゴリズムが分かってないんじゃないのかな。
あるいは、目的がぼんやりしているとか。

まぁいずれにしても、アルゴリズムは暗記でいい派だね。
さらには、辞書とか検索で調べられる程度の情報だけでいい。

暗記でもいいから一回自分で書いてみたらいいと思うよ。

>>813
質問が二つ。

(1) 「自分のレベルが低い」というのは、プログラム能力が低いのか、
それともアルゴリズムを実装に起こす能力が低いのかどっち？
前者なら慣れればなんとかなる。後者ならそもそもアルゴリズムを
十分に理解できていない可能性が高い。

(2) あなたの立場と考えてるアルゴリズムは何？
極端なケースでは、研究者が自分の専門分野のアルゴリズムを
暗記しているようでは全然ダメ。

ソートアルゴリズムで言えばクイックソートやバブルソートとかの名前は知ってるけど、
どういう動作するのか、どうプログラムしていいのかとか分からないって状態なんじゃね？

とても概念がわかってるとは言えないと思うけど。

レス遅くなりすみません。昨日はあのまま寝てしまって・・・

>>819さんの指摘していただいてるような感じです。
ただ、どういう動作をするのかは理解しているつもりなんですが、
書き起こせないってことはやはり概念を理解していないんですかね・・・

>>818
1の質問についてですが、両方ですかねぇ・・・
プログラムでどういう風に書けばいいかわからないみたいな感じです。
特にループ部分などが・・・ループのネストなんてやったことなくて・・・

2についてですが、
立場はただの趣味でやっているみたいなもんですかね。
将来的にプログラマを目指したいとは思っています。
アルゴリズムは探索やソートなどの基本的なものです。

基本的にソートや探索などの関数は、プログラム側で用意されていますし、
>>815さんの仰るとおり外部ライブラリとしてもっておけばいいのですが、
一応理解したうえで使うべきものなのかなぁと思って質問しました。

ただのバブルソートだけでもいいからとにかく書いてみれ

自分で手を動かさない香具師は向いてない

そのレベルでは，何をするにしてもお話にならないので，
とりあえず何でも良いから山ほどプログラム書くところからだね．

>>821-822
どうもありがとうざいます。
そうですね。とりあえずプログラムを書きまくってみることにします。

新しいソートアルゴリズム発見した！
とはいっても、どうせ同じようなのを他の人が見つけてるだろうけど…

数学的に厳密な書き方を知らないので雰囲気で書くけど、
m個の離散値を取る（たとえば整数1〜mまで、など）集合に属する値のソートの場合、
O(n×m)でソートが出来る。

例えば0〜127の整数10000個を降順ソートするプログラムはこちら

int array[10000] = {};
for(int i = 0; i < 10000; i++) { array[i] = rand() % 128; }

// データ構造を配列から2次元マップに変更
bool map[10000][128] = {}; // 全部false
for(int i = 0; i < 10000; i++) {
for(int j = 0; j < array[i]; j++) { map[i][j] = true; }
}

// ソート
bool result[10000][128] = {}; // 全部false
for(int i = 0; i < 128; i++) {
int count = 0;
for(int j = 0; j < 10000; j++) { if(map[j][i]) result[count++][i] = true; }
}

// 結果を配列に変換
for(int i = 0; i < 10000; i++) {
for(int j = 127; j >= 0; j--) { if(result[i][j]) { array[i] = j; break; } }
}

コンパイル試してませんが…

実装が壊滅的に最悪最低で酷くて、
書いたやつは救いようが無いビンソートにしか見えない

酷評すぎてワロタ

>>824
何このゴミ

>>825
同じ事オモタ

空間計算量 O(nm) って劣化にも程が

ネタだろ？

アルゴリズムにソースコードの実装は関係ないだろ、かわいそうにｗ
この実装だと時間・空間計算量O(nm)だけど、
mを定数だと考えると、条件付きO(n)ソートになるな。
最も実用上どうかと思うけど、発想は面白そうだな。可視的にやればうけそう

今までにない発想で面白いと思ったんだけど、
想像以上に叩かれてｼｮﾝﾎﾞﾘ。スレ汚しすまんでした

筋の悪いバケットソートでしかないしなあ

作ってみた。
ビンソートと同列だから目新しさは全くないけど、
ドットを左に寄せていくとソートいう発想はなかなかいいな。
ttp://void-main.org/test/824.html

もっと簡単な方法を数分で思いついた。

int[] array = new int[10000], count = new int[128]; // 全部ゼロ

for (int i = 0; i < 10000; i++)
　array[i] = (int)(Math.random() * 128);

for (int i = 0; i < 10000; i++)
　count[array[i]]++;

for (int p = 0, i = 0; i < 128; i++)
　for (int j = 0; j < count[i]; i++, p++)
　　array[p] = i;

>>835
それは普通のバケットソート

アムロの親父スレ

自分のことを、誰も思いついてないような画期的なアルゴリズムを簡単に思いつけるような天才だと思ってんの？

>>824 >>838
子曰、學而不思則罔。思而不學則殆。

自分で考えるのは大事だけど、ここでこんなの思いついたって発表するが痛いってことだろ。
バカだから文脈読めないけど、難しい言葉使って少しでもかしこく見せたいってかｗ

なぜ努力もせずにただ考えようとするんだろう

基本も分からず、応用は出来ない

>>840

> 自分で考えるのは大事だけど、ここでこんなの思いついたって発表するが痛い

いや、それはいいんじゃね？

>>841
こういうのを「ゆとり」と言うんだろう

それこそ正にチラシの裏に書いておけってやつじゃね

でもそれをきっかけに他の住人が何か閃く可能性だってあるじゃん

遺伝的プログラムで
個々の優劣が明らかに出来る集団で
各順位の分布を初期からほぼ一定にする様なアルゴリズムってかDNA組合せ無いっすか?
自然淘汰してる様で実は歴史は繰り返すみたいなの

松竹梅な比率
1:3:4 第1世代
↓
1:3:4 第N世代

松竹梅それぞれの内から次世代を作れば出来なくは無いと思うけど、なんか意味あんの？

あ、優劣は生殖能力って事で
例えば各個体に付松なら６回、竹２回、梅１回の試行して次世代も同個体数

確立以上に存在するABO式血液型OO型のナゾを逆方向から見た考察です。

５＋６/３を２ステップで求めることできる？？

>>850
step1 『アルゴリズムオタク』スレで質問する
step2 答えを待つ

>>850
質問１　括弧がないけど 5 + (6/3) でいいのかな？
質問２　何を１ステップに数えるの？メモリへのロードとかは？

メモリアクセスを除外すると、演算回数が2回なんだから2ステップだけどそれは自明だしね。

値のロードを入れると3つの値をロードした瞬間3ステップだしなあ

全部固定値なんで何を言いたいのか判らん

a+(b/3) を a,b入力値で　四則演算で求めろとか？
加算＋シフト演算で出すのは２ステップじゃ無理っぽいな

>>751
激しくカメレスで恐縮だが、あのソートアルゴリズムは
量子コンピュータ向きなのではないだろうか。えっ、違う？

おぬしも相当悪よのう

８５０です。
教科書で問題として実際に出ているんです・・・・。
おれの頭じゃ無理で・・・

>>858
>>852 >>855
質問しといてレスをスルーすんな

test

エクスプローラのように文字列中の数値を考慮して並び替えるのに
定番の方法ってあるんですかね。
ぐぐっても参考になりそうなのが見つからなかった。
自分で適当に書いてみたが
数値がでかすぎるとオーバーフローしてソート順が狂う。

小数点や 3E5 みたいな１０のベキ表現が無いなら右寄せしてから比較すればいいんだけど
そうじゃないなら多倍長浮動小数点を自前で作るしかないね

右寄せって何ですか？

用途がファイル名のソートなので
少数とかは考慮しないで大丈夫です。

intのランダム数列に対して、ヒープソートとバブルソートをやって、所用時間を比較してるんですけど、
何度やってもバブルソートがヒープソートの半分くらいの時間でソートしてしまいます。
1〜100000のランダム数列に対して、
heap: 167.83 sec
bubb: 83.2852 sec
という感じです。ヒープソートの実装がまずいのでしょうか？
実装はwikipediaからパクりました。

864ですが、ソース貼ってもいい？

より速いの作ってやるぜ

貼っちゃった。
int a[size] = {1,2,3,4,5,...};と配列を宣言して、
mysort_bubble(a,size);
mysort_heap(a,size);
というように呼び出します。

void mysort_bubble(int* a, int SIZE)
{
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE-1-i; j++) {
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
}
}
}
}

void mysort_heap(int* a, int size)
{
int max = size;
while (max > 0) {
make_heap(a, max, 0);
swap(a[0], a[max-1]);
max--;
}
return;
}

続きです。
void make_heap(int* a, int size, int idx)
{
int j = idx * 2 + 1;
int k = idx * 2 + 2;
if (j > size-1) {
return;
}
if (j == size-1) {
if (a[j] > a[idx]) {
swap(a[j], a[idx]);
}
return;
}
make_heap(a, size, j);
make_heap(a, size, k);
int l;
if (a[j] > a[k]) {
l = j;
}
else {
l = k;
}
if (a[idx] < a[l]) {
swap(a[idx], a[l]);
make_heap(a, size, l);
}
return;
}

#include<iostream>
#include<vector>
#include<time.h>
using namespace std;

#define size 3000000+1
#define rnd(n) ((rand()&255)<<(8*n))
bool comp(const unsigned int &a, const unsigned int &b){return a < b;}

main(){
cout<<size-1<<" 個の配列のソート\n\n";
vector<unsigned int> x(size);
for(int i=0;i<size;i++)x[i]=rnd(0)+rnd(1)+rnd(2)+rnd(3);
int cl=clock();
sort(x.begin(),x.end(),comp);
cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";
cout<<"x[0]="<<x[0];
cout<<"\nx["<<size-1<<"]="<<x[size-1];
}

ありがとうございます。
-cout<<(cl+0.0)/1000<<"sec\n";
+cout<<(cl+0.0)/CLOCKS_PER_SEC<<"sec\n";
ですよね？
(自分の環境では、CLOCKS_PER_SECは1000000でした)。
たしかに、速いですね。

>>867
鈍すぎ

#include<iostream>
#include<vector>
#include<time.h>
using namespace std;

bool comp(const unsigned int &a, const unsigned int &b){return a < b;}

void mysort_bubble(int* a, int SIZE){
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE-1-i; j++) {
if (a[j] > a[j+1]) {swap(a[j], a[j+1]);}}}}

main(){
int SIZE=30000+1;
cout<<SIZE<<" 個の配列のソート\n\n";
int *a=new int [SIZE]; vector<int> x(SIZE);
for(int i=0;i<SIZE;i++)a[i]=x[i]=rand();
int cl=clock(); sort(x.begin(),x.end(),comp); cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";cout<<"x[0]="<<x[0];cout<<"\nx["<<SIZE-1<<"]="<<x[SIZE-1]<<"\n\n";

cl=clock(); mysort_bubble(a,SIZE); cl=clock()-cl;
cout<<(cl+0.0)/1000<<"sec\n";cout<<"a[0]="<<a[0];cout<<"\na["<<SIZE-1<<"]="<<a[SIZE-1]<<endl;
}

>>864
ちゃんと見ていないけど、
mysort_heap, make_heap のところで 1 ベースの配列用と
0 ベースの配列用のコードが混じってるからおかしくなっているんじゃない？

>>863
自己レス。

右寄せってunko1024とunko256ってのがあったら
数字の部分の文字列を抜き出して
256
1024
という風に右寄せしてさらに比較って感じなのかな。

あ、スペース消えてる…。
...256
1024

>>864
ja.wikipedia 見た．なんだこのクソ実装．

きちんと解析する気も起きんが，このヒープソートは
どれだけよく見積もっても O(n^2) はかかってる，

具体的には make_heap 1 回が，最後の再帰を止めても
O(n) かかり，これを sort_heap で n 回繰り返すので，
最後の再帰が一回も実行されないとして O(n^2)．

STLのsortに対抗できないないなら初めからやる意味無し

ていうかアルゴリズムの話になるとなんでいつもソートの話にばっかり収斂していくんだろう。
いまさらソートなんてそうとう早くない(ry

ネタ振り
ソートと同じでこれまた定番な話題に文字列検索がありますが、
文字列中で、複数の単語の中から最初に現れるものを検索
する場合はどうするのが良いでしょうか？

例
検索対象の文字列 abcdefg
単語 ac bc bd bcd

この場合だと検索結果は bc bcd の2つになる。

適当に単語の木を組めばいいんじゃね

>>875
ここまで糞なヒープソートも珍しいw
全く理解してないくせによくwikipedia書けるな…

>>864
http://www.sci.csuhayward.edu/~billard/cs3240/node33.html

>>878
「最初に現れるものを検索」ってのが理解できない
文字列 abcdefg で単語 bc, de だったら bc だけになるの？

なんにせよ Aho-Corasick の変形でいけそうだけど

>>878
ac|bc|bd|bcdを正規表現で検索

速度が大事なんだろ
一桁目の、ビットORをとって、対象文字とANDを取り一致すれば調べていけば

間違いに気付いたら誰か直して欲しいなあ>>ウィキペ

どの記事？

http://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88
これかな

アルゴリズムを通信授業で勉強してるんですが
かなりちんぷんかんぷんです
何故5→Aになるのかも意味が分かりません
アルファベットだったら代入するのは何でもいいんでしょうか？
それとも決まってますか？
後アルゴリズムの効率のいい勉強の仕方も教えてくださいｍ＿　＿ｍ

>>887
俺にはお前の質問がちんぷんかんぷんだ

> 後アルゴリズムの効率のいい勉強の仕方も教えてください

こんなこと言うやつは勉強しても身に付かず、結局
「効率のいいアルゴリズム教えてください」
って言うだけになるんだろうな。

＞効率のいい勉強の仕方も教えてくださいｍ＿　＿ｍ

まず国語の勉強。

お願いします。教えてください
文章が変なのはリアル厨房なので大目に見てくださいm（＿　＿）m
はじめはアルゴリズムの何を勉強したらいいんでしょうか？

「アルゴリズムを勉強する」ためのアルゴリズムを考えてみよう。

>>891
コミュニケーションに不自由しない程度の日本語力と
高校程度の数学の能力を身に着けることが先決．

たとえば、
　自然数に対して定義された関数 T(n) に関する漸化式
　T(n) = 2 T([n/2]) + c n, T(1) = c' を考える（c, c' は定数、[ ] は切り上げ）．
　この漸化式の解 T(n) が次の性質を持つことを証明せよ：
　「ある自然数 N と実数 C が存在して任意の n ≧ N に対して T(n) ≦ C n log n」
と言われて自力で証明できないようでは、アルゴリズム論を勉強しても
結局何も身につかない。

>>887
本を買え。推薦図書スレで推されている本格的なのを。

> 何故5→Aになるのかも意味が分かりません

ああ、まったく意味が分からん。

>>887
通信授業でアルゴリズムを勉強していますがかなりチンプンカンプンな状態です。
Ａに５を代入するにはＡ＝５と記述すると習いましたが理解できていません。代入するとはどういう意味なのでしょうか？
またＡ以外のアルファベットにも５を代入できるのでしょうか？それとも代入可能なアルファベットはＡだけなのでしょうか？
あと効率のいい勉強法をお知りでしたらそちらについてもアドバイスお願いいたします。ｍ＿　＿ｍ

>>896
代入ってのは変数に値を入れるという意味。
変数ってのは何らかの値を入れるための箱だと思っておけばいい。
そしてここではAってのが箱の名前で、５ってのが箱に入れる値。
ある種のプログラミング言語においてA=5という表現は、
Aという箱に5という値を入れる操作をコンピュータに行わせるという意味であって、
数学における同様の表現とは全く別の意味。
あと箱にAと名付ける事は代入ではないし、箱の名前はAじゃなくてもいい。

>>896
普通の（手続き型の）プログラム言語を一つ触ってみるといいんじゃないかな．
Java とか Ruby とか何でもいいから．
そうするとだいぶイメージがわくし，今後のためになるはずよ．

その通信授業で、わからないことをとことん聞くことは出来ないのか？
2chで通信授業するのはやめとけ。

ガキとオタクと田舎者はネットやんな

オタクに教えを請うことがいかに愚かなことか勉強になったな。

どんなことでも、勉強する時は、同じ分野の本を三冊以上読むんだ。
分からないことをスルーしながら、とにかく沢山読む。
すると、何が分からないのかが分かり、何を調べればよいのかがわかるようになるから、それまでに読んだ本から適切な部分を読んで調べることができるようになる。
とにかく沢山読め。

オタクってのは自分で勉強したり調べたりってことをしないのかね

いや自分で調べるくらい出来ないとオタクにはなれないだろ

昔のオタクはそうだったかもしれないが
今のオタクは・・・

>>902,903
オタクは自分で調べるが、他人に教えることは不得手。と思う。

>>905
オタクってのは自己満足のオナニスト。
知識の切り売りをしているような軽薄な連中とは違うのだよ。

>>1きもすぎｗｗｗ
まさかエレベータに乗ってるとき隣の奴がアルゴリズム考えてるとは思わないわ
きもいから死んでくれ

まさか、エレベータで隣り合わせた奴に「隣の奴がアルゴリズムを考えている」かどうか意識されているなんて思わないよ。

>>907
お前の方がキモイから

ｵﾚは小学校のときからﾊﾟﾁﾝｺ屋のﾈｵﾝがどうやって動いてるように見せているのかとか
信号で歩道用と車道用の切り替わりﾀｲﾐﾝｸﾞとかずっと考えてたけどな
そんで周囲からいつもボーっとしてるって言われてた
ココ居るやつらってみんなそんな感じじゃねーの？

>>910
あー、なんか判るわ。
私もエレベータの操作パネル見ながら点字を自力解釈したりしてたしね。

人工物全般から製作者の意図を考えたりする。

>>910
俺は、そういうのはプログラミングを始めてからだな。
ただ、ボーっとしてると言われたっていうのはよくわかるｗ
まさか小学生の子供がそんなこと考えてるとか大人は思いもしないんだよな。

点字は自分も考えたわ
ローマ字を習う前だったけど
50音表と睨めっこして
子音＋母音のパターンは見つけた
（母音や子音なんて言葉は知らなかったけど）
その時はボーッとしてるなんて言われてたけど
今は研究職やってます。脳味噌の構造はそのまま