07/03/30 16:25:18
>>537
手厳しいお返事ありがとうございます。
ですが・・・本当にどういう風に書けばいいのか理解できないのでここの
住人の力を借りさせて頂こうと思った次第ですので・・何卒お手柔らかに
(´･ω･`）
539:デフォルトの名無しさん
07/03/30 16:50:01
手厳しいも何も、>531は理解できてないのか?
>531に後は最大値なんかのロジックを追加するだけだろ。
540:デフォルトの名無しさん
07/03/30 17:44:51
>>538
お前ちょっと「流れ図」でググッてこいよ。
>>531や>>530で何が駄目なんだ？
541:デフォルトの名無しさん
07/03/30 17:54:25
>>538
もう、わからないことや出来ないことは素直に「出来ませんでした」でいいんじゃね？
会社側も、「2chとかで調べて何となく作ってみました」よりも「わかりません。教えて下さい」って
社員の方が扱いやすいだろう。
542:デフォルトの名無しさん
07/03/30 17:58:49
>>539
>手厳しいも何も、>531は理解できてないのか?
正直難しいです。(ρ＿；)・・・・
どうしてこれでよいのか、全然分かりません。
まずは早速教えていただいたとおりに、
一度問題を噛み砕いてみます。
例えば、キー押下によって割り込みピンが
アサートされた時の処理って何行目になるんですか？
543:デフォルトの名無しさん
07/03/30 18:08:44
>>542
流れ図ってそんな事まで書くか？
>例えば、キー押下によって割り込みピンがアサートされた時の処理
この意味わかって言ってんの？
544:デフォルトの名無しさん
07/03/30 18:38:21
520の問題文で「ピンが云々」なんていうやつは
まったく常識が無いやつだと思われても仕方が無い。
545:デフォルトの名無しさん
07/03/30 20:42:51
というか、「割り込みピンがアサートされた」ってどっから引っ張り出してきたの？
546:無知な新社会人
07/03/30 21:24:49
>>545
どっからといわれましても・・・
多分、私の対象とする課題のスコープと
回答して下さっている方が(勝手に)思い描いている
課題のスコープの差異を指摘なさっているのだと考えますが、
なぜか不思議な事に私の提示する要件の内容に耳を傾けることなく、
ただただ「俺が正しいんだ」
「お前は常識がない・流れ図を理解していない」
と言われ、責め続けられるのみで一向に話が進展しないので、
こちらから具体例を出したまでなのですが。(´･ω･`）
それとももしかして、実際の業務はそのように顧客に接するのが
「正しい SE のありかた」だ、と身をもって
教えてくださっているのでしょうか？
もっといろいろ勉強しなくてはいけない事があるんですね・・・
ありがとうございます。
547:デフォルトの名無しさん
07/03/30 21:44:21
別にアルゴリズム的には、その数値がキーボードコントローラから来ようが、
マウスで手書き入力しようが、携帯電話からメールしようが、シリアル伝送で来ようが、
VT端末から来ようが、トグルスイッチでDMAしようが、パンチカード読み取り機から
来ようが、念派で書き換えようが、些末なこと。
そんなことはアルゴリズムを実装・適用する連中が考えればよいわけで、
アルゴリズムというのは、数値はどこからか入力されている、と抽象化した
レイヤーにあるわけ。
548:デフォルトの名無しさん
07/03/30 21:52:00
>>532,>>546 が本人ならネタ確定。
>>532 は天然ぽくって面白かったけど、
>>546 は天然ぽさが足りなくて全然面白くない。
549:デフォルトの名無しさん
07/03/30 21:59:01
>>546
仮に出題意図が低レベルのロジックだったとしよう。
それは普通はアルゴリズムとは呼ばないので、このスレで
質問したことが間違い。
もし割り込みとかそのあたりもアルゴリズムだと思ってるなら
計算機科学に関する常識が足りないので、ちゃんと勉強して
おいたほうがよいと思うよ。
550:デフォルトの名無しさん
07/03/30 22:29:41
組み込み系だったの？
「割り込みピンがアサートされた」のような事まで流れ図に書くようにとは
あの問題が書かれてないから皆に通じなかったのも無理はないよ。
せめてアセンブラレベルかプログラミング言語レベルかくらいは言えばよかったね。
551:無知な新社会人
07/03/30 22:43:23
>>549
>仮に出題意図が低レベルのロジックだったとしよう。
>それは普通はアルゴリズムとは呼ばないので
>もし割り込みとかそのあたりもアルゴリズムだと思ってるなら
>計算機科学に関する常識が足りないので、ちゃんと勉強して
>おいたほうがよいと思うよ。
「アルゴリズム」という言葉についての
非常にラディカルな定義、誠に有難うございます m(_ _)m
（Dekker 先生とかが聞いたら、さぞお喜びになるでしょう）。
「計算機科学」についても今後しっかり勉強していくつもりです。
552:デフォルトの名無しさん
07/03/30 22:47:37
多分、本物は >>528 までで、>>532 以降は春で沸いた池沼だろ。
553:無知な新社会人
07/03/31 00:06:16
久方ぶりにスレ覗いてみたら面白いことに・・
>>552さんの仰るとおり質問を最初にさせて頂いたのは528の私です。
>>532以降は偽者の私ですが、きっと彼も私と似た境遇で必死なんだと
思われますので、住人の方々も手厚く見守ってあげてください。
>>530-531さん、亀レスですが、本当にありがとうございます。自力でやった
のと比較してかなり違っていたので、大変参考になります。ご親切に図まで
書いていただき、感謝感謝です（*´д｀）
このスレも今後時たま覗くと思いますが、これからはまた名無しに戻ります。
いつか自分もちゃんとしたレスができる日を願って・・・
554:デフォルトの名無しさん
07/03/31 00:45:22
>>551
「非建設的」をインスタンス化した様な奴だなお前。
555:デフォルトの名無しさん
07/03/31 01:11:56
>>534
＞PC/AT互換機という事でいいでつ。
腹立つわぁ
556:デフォルトの名無しさん
07/03/31 14:24:41
>>534
キモイ顔文字使うヤツは、首釣って死ねよ
557:デフォルトの名無しさん
07/04/02 11:15:50
伸びてると思ったら・・・( ﾟДﾟ)＜氏ね！
558:デフォルトの名無しさん
07/04/02 21:58:08
伸びてると思ったら、死ね
559:デフォルトの名無しさん
07/04/04 21:03:05
これはまた凄まじいキャラが・・・
560:デフォルトの名無しさん
07/04/05 17:21:21
age
561:デフォルトの名無しさん
07/04/07 21:56:20
でらえもん調査局がいるスレだな
562:デフォルトの名無しさん
07/04/24 04:41:24
ここはヲタクネタ限定スレ？
カレンダー生成のアルゴリスムで定番なの無い？
563:デフォルトの名無しさん
07/04/24 11:21:03
カレンダー生成ごときでアルゴリズムもへったくれも無いだろうよ。
564:デフォルトの名無しさん
07/04/24 16:31:48
kwsk
565:デフォルトの名無しさん
07/04/24 17:38:08
いつでもいいから（2000年1月1日とか）基準日の曜日を設定して
あとはうるう年のルールを考えて増減するだけでいいんじゃないか？
566:デフォルトの名無しさん
07/04/24 18:00:12
今時、何とかの公式なんかで曜日を計算するなんて流行らないしね。
567:デフォルトの名無しさん
07/04/24 18:23:27
夕飯食いながら書いた駄作
#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;
}
568:デフォルトの名無しさん
07/04/24 18:25:05
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:デフォルトの名無しさん
07/04/24 18:57:46
この流れでツェラーの公式がでてこないのが不思議。
570:デフォルトの名無しさん
07/04/24 18:59:23
>>569
それはもう既に、>566が予防線を張ってしまった。
571:デフォルトの名無しさん
07/04/25 22:08:37
return (y + y/4 - y/100 + y/400 + (26*m+16)/10 + d) % 7;
これじゃないのか
572:デフォルトの名無しさん
07/05/02 13:21:23
●4.3t積のトラックが一台ある。これにバラバラの重量の荷物を積み込む際、過積載にならずに出来るだけ多くの（最大積載量に近い重さの）荷物を積み込む組み合わせを求めよ。
ってNP問題だっけ？
いまHDDの整理してて出来るだけDVDの空き領域が小さくなるファイルの組み合わせを考えてるんだけど
573:デフォルトの名無しさん
07/05/02 13:30:41
実は4.3テラ…？
574:デフォルトの名無しさん
07/05/02 13:35:13
>>572
URLﾘﾝｸ(ja.wikipedia.org)
575:デフォルトの名無しさん
07/05/02 13:39:06
なっぷさっく問題？
576:デフォルトの名無しさん
07/05/02 14:25:00
>>572のは、重さの和に制限があって、重さの和の最大値を求めるわけだから、
>>574リンク先の pi=ci が成り立つ場合だな。
577:デフォルトの名無しさん
07/05/03 17:25:54
ガーベジコレクタのアリゴリズム掲載された書籍知りませんかぁ？
578:デフォルトの名無しさん
07/05/03 17:27:48
ガベージコレクタ
アルゴリズム
579:デフォルトの名無しさん
07/05/04 01:20:53
不要な領域が法則無く発生するのに、アルゴリズム化できるとは思えないけどな。
CPUキャッシュのミスヒットのように、想定外の動作でむちゃくちゃ効率悪くなったりしない？
580:デフォルトの名無しさん
07/05/04 08:59:19
AABBBBCCCC
このようなソートされた配列がある。
データが変わる位置(上の配列なら0,2,6)を
逐次検索より速く見つけ出すアルゴリズムを考案せよ。
自分で二分検索法を改良した方法でやったら却って遅くなりますたorz
581:デフォルトの名無しさん
07/05/04 09:15:42
最大値と最小値と増分が判ってんだから例題だったら3等分から始めれば委員じゃね
582:デフォルトの名無しさん
07/05/04 15:34:03
>>580
一般的にその程度のサイズのデータの処理なら逐次処理が最速だぞ。
複雑なアルゴリズムはデータ量に対する計算量を少なくはできるが、
その１ステップ毎に必要な計算量はたいてい増えちゃうから、
データ量が少ない場合はかえって遅くなる。
583:デフォルトの名無しさん
07/05/04 21:48:46
>>582
＞一般的にその程度のサイズのデータの処理なら逐次処理が最速だぞ。
その程度のサイズのデータ量じゃないんだろ
584:デフォルトの名無しさん
07/05/04 23:55:25
>580
もっとサンプリングを細かくした方が効率良くなると思う。
まあデータの偏り具合にもよるが。
585:デフォルトの名無しさん
07/05/04 23:58:24
>>584
お前、二分検索法をちゃんと理解できてるか？
586:デフォルトの名無しさん
07/05/05 00:19:51
二分探索の改良法といったら、内挿探索
587:デフォルトの名無しさん
07/05/05 08:06:53
逐次検索での計算時間は自明にO(N)
２分探索はデータが変わる位置の数はO(N)に比例して,
探索そのものの時間はO(log N)なのでO(N log N)
∴ 逐次探索の方が高速
......と自分の中では直観に反した結論が出てしまった。
自分でもなんとなーく間違ってる気がするので、
だれか偉い人教えて！
588:デフォルトの名無しさん
07/05/05 10:34:18
データが変わる位置が重要なら、つまりデータの連続性が高いなら
A2B4C4 と記憶しておけばいい。
589:デフォルトの名無しさん
07/05/05 11:27:31
？
590:デフォルトの名無しさん
07/05/05 16:01:21
>>587
ふたつ間違ってる。
>データが変わる位置の数が O(N) に比例する
これは問題設定によるので、そうとはいえない。普通は変わる
位置の個数を M として、M に依存した計算量で評価すべき。
>探索そのものの時間はO(log N)なのでO(N log N)
これは実装に依存する。過去の探索の結果を忘れて探索を
繰り返すとそうなるが、過去の情報を保持するように実装すれば
探索木の頂点数が O(N) なので、最悪でもO(N) にできる。
591:デフォルトの名無しさん
07/05/07 08:44:04
ｽﾚﾘﾝｸ(tech板:1-100番)
会話のアルゴリズムぅ?
592:デフォルトの名無しさん
07/05/12 20:09:19
オーダは極限をとるから直観には反する
現実問題としてはデータ依存としか言えないね
扱う対象がどれくらいの大きさで、何種類の文字が何回くらい切り替わるのか、
これによって実装は変わる
飛び石のようにn文字ずつ進んでいくか
半分に区切っていくか
オーダをとると後者のほうが計算量は小さくなるけど、一般には前者が速いと思う
593:デフォルトの名無しさん
07/05/25 15:29:37
suffix arrayを構成するときの最速の（と思われる）方法って何かわかりますか？
URLﾘﾝｸ(homepage3.nifty.com)
にいくつか紹介されてますが、ソート関係の話は1年違うと速度が大分違うと
聞いたので
594:デフォルトの名無しさん
07/05/26 08:08:02
>>593
実用上では、MSufSort か libsufsort が最速っぽい。
suffix array はだいぶ煮詰まってるので、
新奇なものが出ない限り、上記2つを追っていれば十分だとおもふ
595:デフォルトの名無しさん
07/05/29 18:07:29
>>594
おお、どもどもです
596:デフォルトの名無しさん
07/06/06 23:23:39
ちょっと相談させてください。
数独のプログラムを作っているのですが、インターフェースが出来て、
ランダムで適当な数字を残してやってみても、あまり面白い問題が出来ません。
数独で人間が仮置きとかせずに解けるような問題を自動生成するアルゴリズムって、
どんなのが考えられるでしょう？
597:デフォルトの名無しさん
07/06/06 23:29:19
>>596
その方法だと解が2通り以上出る可能性もあるな
598:デフォルトの名無しさん
07/06/07 00:01:57
>>596
そのノウハウで飯が食える人がいるから、そう簡単には教えてくれる人はいないんでない?
ヒント:プログラムで解いてみて、問題ないならOK
599:デフォルトの名無しさん
07/06/07 00:17:14
>>596
>あまり面白い問題が出来ません。
なにがどうだったら面白い問題とみなせるんだ？
そこを考えれば自ずとわかるような気がするけど。
600:デフォルトの名無しさん
07/06/07 06:54:52
そもそも数毒って面白いか？
601:デフォルトの名無しさん
07/06/07 09:43:45
自動生成の問題だと、作業している気分になって萎える。
巧い作者の問題だと、解いててセンスが感じられて楽しい。
602:デフォルトの名無しさん
07/06/07 10:40:17
ヒント：1/fゆらぎ
603:デフォルトの名無しさん
07/06/07 11:11:54
>>596
【解答】パズルのプログラミング【作成】
ｽﾚﾘﾝｸ(puzzle板)
604:デフォルトの名無しさん
07/06/07 12:53:57
>>603
またずいぶんマイナーなスレを…
605:デフォルトの名無しさん
07/06/07 16:35:12
スレ以前に板が…
606:デフォルトの名無しさん
07/06/24 18:56:38
日経サイエンスの最新号（８月号）に、囲碁のための新アルゴリズムが登場したニュースが載っていました。
コンピュータによるゲームでは、IBMのディープブルーがチェスの世界チャンピオンを破って話題になりまし
たが、コンピュータが人間に勝てないゲームのうち残っている囲碁に関して、新しいアルゴリズムが開発
され、１０年以内にはプロ棋士を破ることが実現される可能性があるそうです。
ハンガリー人の研究者が、モンテカルロ法を拡張したUCT（日本語では「ツリー構造に適用された上位信頼限界」
というそうですが…）というアルゴリズムを開発し、その効果を高めるために様々な追加研究を行っているそうです。
このアルゴリズムの特徴は、単純にパターンを網羅して、無作為に抽出・評価するモンテカルロ法から発展して、
様々な評価指数を用い有望な選択肢を抽出し評価を行うようです。例えれば、統計的手法から学習的手法に
進化したもののようです。
コンピュータが誕生してから、時間が経ちますが、一歩ずつでありながらも、確実に人間の思考と互角に機能できる
ように、いろいろな人が研究を続けて進化していることを実感します。そして、そのような実験の結果が、部分的でも
家庭用ゲームやラーニングソフトウェア等にも吸収され、コンピュータの活用がさらに進化すればよいなと思います。
URLﾘﾝｸ(blogs.itmedia.co.jp)
607:デフォルトの名無しさん
07/06/30 23:09:52
Dijkstra法の最小経路問題のアルゴリズムの帰納法を使った証明を教えてください！
608:デフォルトの名無しさん
07/07/03 21:48:25
こんとんじょのいこ
609:デフォルトの名無しさん
07/07/03 22:42:22
アルゴリズムナタク
１話 俺のアルゴリズムは正しいのだ！
２話 貴様らのアルゴリズムに正義はあるのか！正義はあるのかと聞いている！
３話 アルゴリズムを教えてくれ！ナタク！
最終話 だから女は甘い
610:デフォルトの名無しさん
07/07/10 16:43:27
多倍長演算の割り算のアルゴリズムで
たとえば521を21で割るとき
↓
まず521が三桁で20が二桁だから答えも二桁だろう
↓
２桁目を決めよう
↓
答えは10かな？21*10＝210で521より小さい
↓
じゃ20かな？21*20＝420＜521
↓
じゃ30かな？21*30＝630＞521（もし90でも超えなければ二桁目は9にする）
↓
大きくなったからおそらく答えの2桁目は2だろう
↓
次は１桁目・・・
こんなのを考えたのですが、もっと良い方法はないですか？
611:デフォルトの名無しさん
07/07/10 17:03:24
何このマルチレス
612:デフォルトの名無しさん
07/07/10 22:23:40
車輪の再発明でググれ
613:デフォルトの名無しさん
07/08/04 11:39:42
n個のボール、k個の横に並べた箱がある。
n=3、 k=4 (A,B,C,D) とするとき、各箱にボールを入れるパターンを考える。
この場合、組合せの総数は 20 となるが、左右対称となるパターン( A=D、B=C ) を
除く条件もある場合、全パターンは以下のような 10 パターンになる。
n、k が任意の値であるとき、同様に全パターンを生成するアルゴリズムはどのようになるか？
A B C D
○○○ | | |
○○ | ○ .| |
○○ | . | ○ |
○○ | . | | ○
○ | ○○ .| |
○ | ○ .| ○ |
○ | ○ .| | ○
○ | .| ○○ |
| ○○○ | |
| ○○ | ○ |
614:デフォルトの名無しさん
07/08/04 11:42:57
補足： ↑のパターンは例であり、左右対称パターンのいずれかが生成できれば、
等価であるとみなすことができるものとする。
615:デフォルトの名無しさん
07/08/04 11:45:10
>>614 対称パターン例: (1) と (2) はどちらでも良く、等価な1パターンとみなす
(1)
A B C D
○○○ | | |
(2)
A B C D
| .| | ○○○
616:デフォルトの名無しさん
07/08/04 12:08:28
20個のパターンを全列挙するプログラムで
A > D または (A = D かつ B > C) を
満たすもののみ出力すればいいよ
617:デフォルトの名無しさん
07/08/04 12:17:18
>>616
確かに、まず「箱毎のボール数」を全列挙するアルゴリズムが出発点ですね。
・・・しかし、nとkが任意の際のうまいアルゴリズムが思い浮かばない・・・
618:デフォルトの名無しさん
07/08/04 12:26:30
原始的、総当り法
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 であるパターンを全列挙する・・・
619:デフォルトの名無しさん
07/08/04 12:37:59
>>618の着眼を応用して、n桁k進数を生成するようにして、
n個のボールに、どの箱に入れるかを決めるようにしたら。
パターン重複を避けるには、n個のボールに順序性をもたせる。
例えばボールno.2はno.1の左側に置いてはいけないようにする。
620:デフォルトの名無しさん
07/08/04 12:41:25
全部同じ箱に入るときの重複を考慮しないと逝けないな
621:デフォルトの名無しさん
07/08/04 12:43:54
>>613の絵を素直に見ると、とりあえず、
n個の○とk-1個の | を一列に並べろ
ってことでいいんじゃないのか？
配列を逆にして同じものはあとで省くということで。
622:デフォルトの名無しさん
07/08/04 12:49:06
>>617
再帰が使えるなら簡単で、
「n 個の箱に k 個のボールを入れる全パターンは
先頭の箱に i 個入れて残りの箱に k-i 個入れる
パターンを全部かき集めてきたもの」
でいい。
対称性は後で除いて十分 （計算量は O( nCk ) なので変わらない）
>>618
その計算量は O( n^k ) なので、
パターン総数 O( nCk ) に対して漸近的に悪い。
623:デフォルトの名無しさん
07/08/04 13:02:13
>>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進数」となる。
624:デフォルトの名無しさん
07/08/04 13:02:54
ごめん、日本語がおかしい上に頭もおかしかったｗｗ
625:デフォルトの名無しさん
07/08/04 13:10:04
>>621
そうかK-1回のループと変数2個配列2個くらいでいいのか。頭いいな
左右から交互に左>=右になるよう|を置いていけば
一発で重複パターンなしに生成できそうだ
626:613
07/08/04 13:17:07
>>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 番目のパターンはコレ、とやるには
やはり結果を配列に入れてことになるのかな。
627:デフォルトの名無しさん
07/08/04 13:30:04
ボール数: N
箱の数: K
箱内のボール数: NumBall[ K - 1 ]
パターン数: NumPattern= getNumPattern( N, K )
パターン番号: x ( 0 ≦ x ＜NumPattern)
x を指定したとき、対応する NumBall[ 0 ] ... NumBall[ K - 1 ] を求めよ
628:デフォルトの名無しさん
07/08/04 13:35:40
単純な計算式では出せない…よね？
629:デフォルトの名無しさん
07/08/04 13:38:55
よく考えたらK-1回じゃ無理じゃん、オレだめだな
アルゴリズム分かったけど携帯じゃ打ち込めないorz
630:デフォルトの名無しさん
07/08/04 15:04:59
> n個のボール、k個の箱の左右対称分を除いたパターン数は組合せの式で
> (n+2)! / ( (k-1)! * (n-k+3)! ) でいいのだろうか。
違うな。
Excel だと COMBIN(n+k-1, k-1)
631:デフォルトの名無しさん
07/08/04 15:19:30
COMBIN(n+k-1, k-1) は左右対称分を含むパターン数。
これで全パターンを格納する配列を確保できる
632:デフォルトの名無しさん
07/08/04 15:37:02
そして2で割れば重複分を除いたパターン数になるのだ！
633:デフォルトの名無しさん
07/08/04 20:13:25
#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;
}
634:デフォルトの名無しさん
07/08/04 20:15:04
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;
}
635:613
07/08/04 20:21:12
ソース貼りマンドクセ・・・ダサい実装
URLﾘﾝｸ(tool-ya.ddo.jp)
DL/解凍パス
NumBallPattern
636:613
07/08/04 20:23:27
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 の実行結果
637:デフォルトの名無しさん
07/08/04 22:25:00
include省略、拡張子 .c なのに new があったり、と
よくわからん上に、n = 6, k = 12 でさえ相当の時間がかかる。
ダサいというか、ひどい。
638:629
07/08/04 22:47:53
ほい。
#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;
}
639:デフォルトの名無しさん
07/08/04 22:57:47
びっくりするくらい同じコードだ
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
640:613
07/08/04 23:04:13
>>637
実際はVC++でcpp、includeはコピペ忘れ。
書いていなかったけど、Kは6、Kは16くらいまでの上限を想定している。
>>638
スマートで速い。これの方がずっと良いね。
641:613
07/08/04 23:05:05
ソース見ている間に >>639も・・・ありがとう
642:613
07/08/04 23:11:08
あとは >>627 への対応か・・・xを決めたときに対応する箱毎のボール数が出るように
643:デフォルトの名無しさん
07/08/04 23:13:34
順番が指定されていない限り、その問題には答えられない
644:638
07/08/04 23:26:42
>>639
うわ、びっくりしたw。オレんと違ってデータ残してるのね…
>>642
ゴメン。627のことはすっかり忘れてた。 639さんの使ってけれ
645:639
07/08/04 23:31:05
最初はデータを残してなかったからもっと同じだったけど
613 が残していたのでそれにあわせたのです
646:613
07/08/04 23:37:19
>>643
パターンが網羅できていれば、順番は特に問いません。
>>638のソースをベースに、>>639のデータ記録を盛り込もうと試行中・・・
647:613
07/08/05 00:33:49
みんなのお陰で問題解決できたよ。ありがとう。
問題を単純化しようとして敢えて”ボール”と”箱”にしたけれど、本当はバス線の分岐パターンを網羅したいという問題。
バス線につながるノード数と分岐数を決めたとき、全体としてありえる接続パターンを無駄なく網羅したかった。
だから左右対称のパターンは要らないとかの付加条件も発生。
仮にノード数を 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本の組合せパターンを網羅し、そこからランダムに一つ選んで、残りの長さゼロではないバス線と
分岐線による別の処理を・・・というところに行き着ける土台ができますた。
この例のパターンを示すソース
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
648:613
07/08/05 00:36:13
>残り 3 ノードをどの各分岐点にいくつ接続するパターンはいくつで、具体的にどうか？という問題になる。
残り 3 ノードをどの各分岐点に接続するパターンはいくつで、具体的にどうか？という問題になる。
649:デフォルトの名無しさん
07/08/05 00:36:31
くそ天皇 くそ天皇 くそ天皇 くそ天皇
いい加減死ねっつってんだろ屑ニートくそ天皇が
相変わらず病的な粘着っぷりだな屑ニートくそ天皇が
毎日毎日毎日粘着出来て良いでちゅねくそ天皇
くそ天皇さっさと死にやがれゴミが
東京に在住している精神病珍米糞ニートくそ天皇君の末路
さっさと精神病院逝くか首吊って逝くか選べや糞天皇が
早く死ねよ糞ニート天皇が
粘着精神病屑ニート天皇君は自らニートくそ天皇であると公言しました
さっさと死ねやくそ天皇が
早く死ねっつってんだろ屑ニートくそ天皇が
お前みたいなゴミクズ天皇は息してるだけで空気が汚れるからさっさと死ねや
とっと死に晒せや糞ニート天皇が
650:613
07/08/05 00:36:54
どの各・・・益々ボケてきたorz
651:デフォルトの名無しさん
07/08/05 00:37:03
くそ天皇 くそ天皇 くそ天皇 くそ天皇
いい加減死ねっつってんだろ屑ニートくそ天皇が
相変わらず病的な粘着っぷりだな屑ニートくそ天皇が
毎日毎日毎日粘着出来て良いでちゅねくそ天皇
くそ天皇さっさと死にやがれゴミが
東京に在住している精神病珍米糞ニートくそ天皇君の末路
さっさと精神病院逝くか首吊って逝くか選べや糞天皇が
早く死ねよ糞ニート天皇が
粘着精神病屑ニート天皇君は自らニートくそ天皇であると公言しました
さっさと死ねやくそ天皇が
早く死ねっつってんだろ屑ニートくそ天皇が
お前みたいなゴミクズ天皇は息してるだけで空気が汚れるからさっさと死ねや
とっと死に晒せや糞ニート天皇が
652:デフォルトの名無しさん
07/08/05 01:03:57
>>647
敵を騙すにはまず味方から・・・って俺らを騙したのか！！！！？
653:デフォルトの名無しさん
07/08/05 01:15:33
いや、良い問題の簡単化だと思うよ。
俺は最初から >>647 の書き方をされたら、
読む気が起きなかったと思う。
654:デフォルトの名無しさん
07/08/05 13:11:45
AI人工知能のお勉強はこちらからどうぞ
URLﾘﾝｸ(www.1101.com)
655:デフォルトの名無しさん
07/08/15 23:43:02
URLﾘﾝｸ(ss.nkk.affrc.go.jp)
に記述されている、
図４の(a)から(b)の結果はどのようなアルゴリズムになりますか？
656:デフォルトの名無しさん
07/08/15 23:55:57
結果はアルゴリズムではありません。
657:デフォルトの名無しさん
07/08/16 00:11:57
マルチうぜえ
658:デフォルトの名無しさん
07/08/16 00:31:27
>>656
過程を知りたいわけです。
659:デフォルトの名無しさん
07/08/26 06:26:05
ボゴソートについて語ろうぜ
660:デフォルトの名無しさん
07/08/26 15:40:51
実際に実装しようとするとかなりと面倒だな。
661:デフォルトの名無しさん
07/10/10 21:54:17
age
662:シロートです
07/10/12 09:00:55
はじめまして。プログラミングの勉強してるものです。
アルゴリズムについて質問があります。質問はどこでしたらいいのか
分からなかったのでこちらに書かせていただきます。スレ違いかもしれませんが
お願いします。もしアルゴリズムの質問板があるならそちらも教えていただけるとありがたいです。
C++言語を使っています。質問です。
４種類の連続した数値のデータがあります。４種類の測定時間や時間間隔は一緒です。
その４種類をひとまとまりとします。そのまとまりがいくつかあります。
それぞれのまとまりから一部分だけを取り出します。その一部分のデータの特徴を
どんどんと集めていき４種類のデータの特性を求めたいです。その方法がわかりません。
すいません。ホントシロートです。質問の意味がわからないかもしれません。
でも本当に困ってます。ヒントだけでもいいのでお願いします。
プログラムが違うのかもしれませんが、
「似たようなデータをどんどん記憶していくことによりそのデータ達の
特性を求める」ということかなと自分では考えたのですがその方法も分かりません。
方法を知っているとかこんなコマンドがあるなど本当に何でもいいのでよろしくお願いします。
４種類のデータはヘリコプタの制御に使う、スロットル、エルロン、エレベータ、ラダーです。
特性はホバリングをしている時の４種類のデータ入力の特徴を見つけたいです。
よろしくお願いします。
663:デフォルトの名無しさん
07/10/12 09:39:36
マルチすんな。
664:デフォルトの名無しさん
07/10/12 10:55:47
>>662
取り敢えず、「ヘリコプタ」「ホバリング」「制御」で検索して、見つかったサイトを全部読んできてくれ。
665:デフォルトの名無しさん
07/10/12 20:23:57
こっちでやってあげるからデータだけくれ
666:デフォルトの名無しさん
07/10/12 22:38:27
プログラム初心者です。
アルゴリズムとロジックの違いはなんですか？
新人研修で先輩に質問したら、ググレカスのひとことで片づけられましたが
いまだに謎が解けません。
よろしくです。
667:exc
07/10/12 23:09:07
>>
アルゴリズムというより統計の分野ではないでしょうか。
ヒストグラムとか散布図とか描いてみればいかがですか？
668:exc
07/10/12 23:11:34
アンカーつけ忘れ
>>662
アルゴリズムというより統計の分野ではないでしょうか。
ヒストグラムとか散布図とか描いてみればいかがですか？
669:exc
07/10/12 23:16:02
>>666
アルゴリズムよりもロジックの方が大きな概念なんじゃないでしょうか。
アルゴリズムならロジック的である。
ロジック的だからといってアルゴリズムとは限らない。
670:デフォルトの名無しさん
07/10/13 17:20:04
何処かの雑誌でアルゴリズムとロジックを解説してたな。
アルゴリズム：代数的な要素をもった解析可能な処理手順。
または特定の言語に寄らない処理手順の記述
ロジック ：コーデイングよりの処理手順
671:デフォルトの名無しさん
07/10/13 21:38:36
チューリングマシンで表現できるのがアルゴリズム
公理と推論規則で構成するのがロジック
672:デフォルトの名無しさん
07/10/15 13:27:45
>>670
そんな本は捨てたほうがいいな
673:デフォルトの名無しさん
07/10/15 19:39:19
理由は？
674:デフォルトの名無しさん
07/10/15 20:17:17
ロジックの定義が根本的に間違ってる
675:デフォルトの名無しさん
07/10/15 21:16:41
じゃあ正しい定義は何？
676:デフォルトの名無しさん
07/10/16 00:50:13
>>671 が見えないのか？
677:デフォルトの名無しさん
07/10/16 00:57:06
>>671が定義に見えるのか？
678:デフォルトの名無しさん
07/10/16 16:09:43
アルゴリズムは理論で、ロジックは論理だろ
679:デフォルトの名無しさん
07/10/16 19:12:34
つまり？
680:デフォルトの名無しさん
07/10/16 21:57:35
ののたん最高！
681:676
07/10/17 23:54:03
>>677 >>671以外，どう定義しろと？
682:デフォルトの名無しさん
07/10/18 00:07:02
AはBである⇔BはAである
683:デフォルトの名無しさん
07/10/18 10:41:28
アルゴリズム ＝ 処理方法
ロジック ＝ 実装されている処理方法
でないの…何か違うな…
684:デフォルトの名無しさん
07/10/18 11:46:10
それ区分けしてなんか意味あんの?
そんな明確な定義が周知されてない言葉なんか場に応じて使い方が異なるに決まってんだろ
685:デフォルトの名無しさん
07/10/18 13:19:38
>>679
アルゴリズム（理論）はロジック（論理）で実装される。
686:デフォルトの名無しさん
07/10/18 13:21:37
実装だと語弊があるな。「構成される」と言い直そう。
687:デフォルトの名無しさん
07/10/21 16:55:37
AVL木と赤黒木を実装したんですけどなんかほとんど変わらないっつーか
AVL木の方が性能が良いんですがなんか間違ってますか？
赤黒木の方が使えるとか聞くんですけど。
688:デフォルトの名無しさん
07/10/21 20:03:12
どのくらいのデータサイズでどういう操作を何回やったのを比較したのかがわからないと何ともいえない
689:デフォルトの名無しさん
07/11/01 21:16:27
age
690:デフォルトの名無しさん
07/11/30 21:00:49
アルゴリズムがそのままロジックとして実装されるとは限らない。
バグがあるかもしれないし、処理範囲を限定して実装されるかもしれない。
691:デフォルトの名無しさん
07/12/31 15:10:26
あのさ質問があるんだけど
アルゴリズムの性能評価って何してるんだ
意味わかんね
分かる人いたら教えてクダーサイ
692:デフォルトの名無しさん
08/01/03 01:41:01
アルゴリズムの性能を評価しているんでしょう、きっと。
693:デフォルトの名無しさん
08/01/03 19:49:07
>>691
ということで、性能とは何か ということが焦点になると思う
アルゴリズムの性能 というのは何を意味するのか
ブラックボックス的な評価で言うなら
・機能を満たすこと
・メモリ使用量
・速度
この３つの観点に絞られるような気がする
694:デフォルトの名無しさん
08/01/04 16:21:28
algorithm初学者です。
C言語の学習とあわせて学習してます。
search algorithmについて質問です。
10冊ほどパラパラと実際にalgorithmのテキストを見て吟味しましたが、
どの本もツリー・スタックといったありきたりのデータ構造を前提として
そこからいかに高速に少ないメモリ使用量で検索するかという話になっていました。
私は、データ構造をいかに工夫するかという方向でも考察したいのですが、
手がかりになるテキストはありますでしょうか???
また、前提となる知識にどういったものがありますか??
数学については大学教養レベルまではかろうじてある程度です。
computer scienceについてはド素人です。
たとえば、データ使用頻度に応じて機械学習で動的に検索の仕方を変えるとか、
データエントリに優先度を指定したり、データエントリ間に距離を定義したりすると
有益な検索システムが出来そうな気がします。
「そういうことは普通やらない」or「そういうことは既に考え尽くされている」のだとしても、
そういうことを自分でしっかり考えてみたいんです。
よろしくお願いします。
695:デフォルトの名無しさん
08/01/04 22:47:10
>>694
具体例を挙げれないので申し訳ないが、
論文を探してみるのも良いかと思うよ。
696:デフォルトの名無しさん
08/01/05 00:40:45
前から思っていたんすがこの前教授がアルゴリズムの寿命がどうたらこうたら
いっていたんですが何でアルゴリズムに寿命があるんでしょうか？
アルゴリズムってプログラムだから寿命もくそも無いと思うんですが
頭悪い僕に簡単に教えてくれないでしょうか？お願いします。
697:デフォルトの名無しさん
08/01/05 00:51:04
よりよいアルゴリズムが開発されて古いアルゴリズムが広く実用的には使われなくなったって意味じゃないのか
698:デフォルトの名無しさん
08/01/05 01:00:13
ああ、一部の分野ではそういうこともあるよな。
よく考え付くよって思うよ。
699:デフォルトの名無しさん
08/01/05 01:05:37
>>694
> たとえば、データ使用頻度に応じて機械学習で動的に検索の仕方を変えるとか、
漢字変換アプリで1回変換したのは候補の最初に移動するって
のはあるけど、使用頻度の低い奴をスワップアウトするとかは
どうすんやろ、逆に教えて。
> データエントリに優先度を指定したり、データエントリ間に距離を定義したりすると
> 有益な検索システムが出来そうな気がします。
これはどう役に立つの？
700:デフォルトの名無しさん
08/01/05 01:27:48
>>694
データ構造で最近面白いと思ったのは succinct structure だな。
興味があったら調べてみて。
701:694
08/01/05 03:43:59
>>695
論文というとACMとか情報処理学会とか入ったほうがいいですかね。
オススメの論文誌ありますか。
ipsjは一度入ってたんですけどね、学生会員だから安いと思って。
>>699
前半は初学者なので分かりません。
後半はサーチをする順序の問題です。
優先度をエントリごとに与えることで優先度の高いものから順にサーチすることにより高速にデータが見つかる可能性が高まります。
優先度自体は人間的主観に基づいてつけるものなのでアルゴリズムの問題ではないですが、
それをどう動的に付け替えるかといったことはアルゴリズムをどう適用するかという問題だし、実践上役に立つと思います。
距離を定義することで、エントリ間の類似度が定義されますと、似たものどうしをまず一通り探すという深さ優先的なサーチをするのか
とりあえずいろんな種類のものをひととおりサーチするという幅優先的なサーチにするのかといった選択も可能になります。
すると、状況に応じて適したサーチメソッドの選択ができるようになります。
ツリーとかスタックといった定型的なデータ構造に限らないより一般的なデータ構造において、どうサーチをするのかということを
考える際に有益だと考えました。
もちろん以上は素人考えなので間違いも含まれると思います。
忌憚ないご意見ください。
>>700
succinct data structureというのはチラッと見た覚えがあります。
是非調べてみます。ありがとうございます。
702:デフォルトの名無しさん
08/01/05 05:17:27
>>701
検索対象に対して優先度を計算し直した時点で
すでにデータをナめてることになるんだけど・・・
だからあり得ない []
距離じゃなくてシグネチャとかハッシュ値の一致するものの
中から探すってのならあるけど。
こっちなら検索対象との距離じゃなくてただの絶対的に計算できる
値だから
703:デフォルトの名無しさん
08/01/05 07:52:46
学生なら大学経由で論文落とし放題というイメージがあるのだが、
大学によって違うのかな？
704:694
08/01/05 16:26:31
>>702
> 検索対象に対して優先度を計算し直した時点で
> すでにデータをナめてることになるんだけど・・・
ド素人の意見なので、通じないかもしれませんが、
私の考えとしては、検索のたびに優先度を計算しなおすのではなくて、
前もって優先度を指定してデータを格納しておき、そして毎回の検索に役立てるというやり方がいいかな
と考えました。
>距離じゃなくてシグネチャとかハッシュ値の一致するものの中から探す
なるほど、前もってデータを分類しておき、検索速度を上げるんですね。
私の興味があるのは、テキストデータのような容易には一律な分類が出来ないもの
(あるいは一律に分類してしまうと強い作為性が生じてしまい実用に耐えないもの)です。
そういった場合に、距離を定めるといいのではと思いました。
>>703
大学生のときにはipsj入っていたという意味で、今は卒業しています。
卒業生として図書館利用することもできますが遠隔地なので手間です。
705:694
08/01/05 16:30:57
追記
距離を定めるといい、と書きましたがこれは一例で、
そういった言わば「変な」「特殊な」数学を駆使した技術でこれまでにないことが出来たら
面白いと思っています。
私は学究的に変で特殊なことだけをやりたいのではなく、一つの選択肢として出来れば面白いと考えている程度です。
もちろん、スタンダードな理論も学習するつもりですが。
706:デフォルトの名無しさん
08/01/05 16:47:14
新しいことが何かを見定めるには地道なサーベイが必要だよ。
めんどくさがらずに沢山の論文を読むことだね。
707:694
08/01/05 18:48:59
>>706
ありがとうございます。ACM, ipsjに入ることにしました。
論文といった大それた話とは別に、データ構造の側の工夫というのが行われてはいないんでしょうか。
例えば、RDBでデータの格納のしかたを工夫することで検索コストとスピードを上げるだとか、
Googleなどで使われているようなテキスト検索技術だとか。
アルゴリズムとは違う話なのかもしれませんが、そういうのにも興味があって、アルゴリズムではそういうことは扱わないのかな
と思いました。
708:デフォルトの名無しさん
08/01/05 19:05:23
ACM・・・マーメイ・・・
709:デフォルトの名無しさん
08/01/05 22:03:42
googleとかRDBか。確かに気になる
namazとかか
710:デフォルトの名無しさん
08/01/08 04:29:03
既存のデータ構造以上のものが作れる可能性のある人間がこんなところで質問するわけねーｗ
711:泉 こなた
08/01/08 07:46:51
あけおめ！！
712:デフォルトの名無しさん
08/01/08 12:14:13
>>693
他にも。
・安定性（データによって所用時間が大きく変動しない）
例：クイックソートでは、ソート済みのデータソートには時間がかかる
・確実性
例：漸近法では解が発散することがある。
713:694
08/01/09 04:14:30
>>710
既存のデータ構造以上のものを作る、が希望要件ではなくて、
今年中をめどに、アルゴリズムに関する学習を徹底してやる、というのが希望するところです。
来年からは違ったプロジェクトが発動するので、それのための準備期間です。
だから、学究的な立場でデータ構造を研究して成果をあげたいのではないです。
そうではなくて、ド素人からプロの知識レベルくらいになりたいということです。
そのためにリサーチをかけて、本を10冊ばかりざっと読みましたが、どうも求めているような
高い水準で特殊な実用にも耐えるタイプの本がすくないということです。
一番面白かったのは『情報の構造』という本でした。
これは他の本と違って、ユニークなデータ構造をからめたアルゴリズムの記述が多々ありました。
そこで、こういったタイプの本が他にもないか、と探していたのです。
714:デフォルトの名無しさん
08/01/09 04:47:14
高度な技術というものは細かくみれば基礎の組み合わせだけだったりする。
実用的なものほどそういう傾向が強い。
ユニークなものは大抵アカデミックに留まるもんだ。
>ド素人からプロの知識レベルくらいになりたい
焦らない方が…
715:デフォルトの名無しさん
08/01/09 05:09:06
何故ド素人の君がその10冊の本に載っていたものが実用に耐えない低水準なものだと分かるのか
716:デフォルトの名無しさん
08/01/09 05:24:12
素人なら素人らしく一般的なもので満足しとけ。
無理に変わったものに手をだそうとするのは時間の無駄。
717:694
08/01/09 11:24:08
>>714
一年猶予期間があります。それまでにプロフェッショナルになることは不可能な話では
ないでしょうか。いきなりプロになろうとしているのではありません。
昨日も100ページほど本をじっくり読み進めました。
ゆっくり確実にコツコツとやろうとしていますので、どうかその意図をご理解くださると嬉しいです。
>>715
よく見かけるアルゴリズムが低水準だという意味ではないので、誤解のある書き方をしてしまいました。
申し訳ありません。
私が言いたかったのは、私の想定する特殊な用途のためには、ハイパフォーマンスを発揮できないのではないか、
ということです。
たとえば、ネットワークルーティングアルゴリズムを実装するのにはどんなデータ構造が適しているでしょうか。
グラフ構造というちょっと手強いデータ構造を必要とするかもしれません。
つまり、どんな状況でどんなデータ構造が必要とされてくるか分からない状況で、
stack, treeといった初歩的なdata structureだけしか知らずに太刀打ちしようとするのは無謀だと考えたのです。
プロフェッショナルなスキルを身につける上では、当然グラフ構造、ひいてはグラフに関する
数学理論も理解したいものですよね。
私が言う特殊な状況での高水準というのはそういうことです。
まだどんな仕事がくるか分からないので、そういう万全な勉強をしたいのですよ。
>>716
はい、変わったものを要求しているわけではないことは上の記述でご理解いただけたのではないかと
思います。
逆にお聞きしますが、スタンダードなデータ構造でいかにプロフェッショナルな仕事をするかという方向性でも
今後一年勉強する予定なのですが、その場合私が見かける書籍での学習では不十分な気がしてなりません。
何かアドバイスください。
718:694
08/01/09 11:26:34
間違えました。
× 不可能な話ではないでしょうか。
○ 不可能な話ではないのではないでしょうか。
719:デフォルトの名無しさん
08/01/09 13:03:38
論文検索や学会誌を漁って参考文献を遡ったほうが早い
720:694
08/01/09 15:09:17
>>719
そうします。助言ありがとうございます。
721:デフォルトの名無しさん
08/01/09 21:02:21
Knuthの基本算法は読んだ？
722:デフォルトの名無しさん
08/01/10 00:24:45
とても困っています。
アルゴリズムの問題を下に示します。
今、n個の数字を大きい順に並び替える事を考える。
ただし、同じ数字がある場合、これらは等価と見て並び替えなければならない。
つまり３つの0を考えた時、これらを
0a, 0b, 0cと見て、
これをソートした場合、毎回同じ並びになってはいけないものとする。
このようなソートアルゴリズムを考えよ。
良い方法はありませんかね。
723:デフォルトの名無しさん
08/01/10 00:41:14
>>722
宿題か？スレ違いだぞ。
通し番号つけてその番号でソートしろ。
毎回同じ並びになってはいけないって毎回同じデータが来るのか？
だったらn通りの組み合わせを全て出現させる方法を調べろ。
その方法で同値部分の通し番号をつけ直せ。
724:デフォルトの名無しさん
08/01/10 02:11:09
>>722
あるよー
stable_sort
725:デフォルトの名無しさん
08/01/10 09:09:12
>724
>724
>724
726:デフォルトの名無しさん
08/01/11 00:58:04
>>722
permutation
727:デフォルトの名無しさん
08/01/11 09:03:18
>>722
ソート時の大小比較の判定を，2つのoperandの値が等しい時は乱数で決定するようにすればどう？
728:デフォルトの名無しさん
08/01/11 10:38:12
いや、乱数で予測不明にするんじゃなくて、毎回同じ並びに決定できるようにするんだろ？
729:デフォルトの名無しさん
08/01/11 11:54:45
>毎回同じ並びになってはいけない
730:デフォルトの名無しさん
08/01/11 15:19:49
「毎回同じ並びでなければならない」だろう。常考
731:デフォルトの名無しさん
08/01/11 20:06:22
> ただし、同じ数字がある場合、これらは等価と見て並び替えなければならない。
というのが問題の意図なんだから、毎回同じ並びだとおかしい。
732:デフォルトの名無しさん
08/01/11 20:24:22
同じ数値がある場合は全組み合わせを列挙してしまえばよいではないか？
733:デフォルトの名無しさん
08/01/11 20:43:14
ふつうのソートとさほど変わらないような時間でやり遂げたいんだろうな
734:デフォルトの名無しさん
08/01/11 21:19:13
非効率的だけど単純に要素をシャッフルしてからソートすればいいんでないかい？
random_shuffle() -> sort()
735:デフォルトの名無しさん
08/01/11 21:49:32
どうやってランダムのシャッフルをするの？
736:デフォルトの名無しさん
08/01/11 23:45:15
クイックソートの入れ替える要素を選ぶときに、比較要素が等しい場合は適当な確率で入れ替えるとか。
737:デフォルトの名無しさん
08/01/12 00:03:31
>>734
シャッフルの計算量ってO(n)だから
十分効率的だよね。俺的にはそれでFAです。
738:デフォルトの名無しさん
08/01/12 00:07:58
同じになっちゃいけないんだからランダムはまずいんじゃね？
739:デフォルトの名無しさん
08/01/12 00:29:37
>毎回同じ並びになってはいけない
が「毎回必ず違う並びにならなければならない」なのか「必ず毎回同じになるようではならない」なのか
740:デフォルトの名無しさん
08/01/12 04:45:48
"同じ並びが出てはいけない"とすると、場合の数を出しつくした後の挙動に矛盾が出る。
まあボゴソートでいいんじゃない？ 実装簡単だし。テストが大変かもだけど。
741:デフォルトの名無しさん
08/01/12 09:27:53
ボゴソートって初めて聞いた。
調べたらプチわろたｗ なんという天に任せる手法ｗｗｗ
投げやりすぎｗ
742:デフォルトの名無しさん
08/01/12 09:45:58
最初は後ろに追加していって最後にまとめてソートするのと、最初から順番通り挿入していくのでは、
前者の方が早い？
743:デフォルトの名無しさん
08/01/12 09:48:06
>>739
論理が破綻しているんですか？
~(毎回同じ並びになる)
って事だから、同じやつが連続で出てもいいが、無限回やって
毎回同じ並びになるのはやめいって事だよ。
あったまわる・・
>>741
これはソートというのか・・・
カード投げて拾うとか・・・
744:デフォルトの名無しさん
08/01/12 09:56:54
後者は所謂挿入ソートなので平均計算時間はO(n^2)になるが、
前者はソート法を選べるから例えばクイックソートを使えばO(n logn)になる。
従って、追加するデータがランダムならば前者がいい。
しかし、例えばカードゲームの持ち札のように常に部分がソートされている必要がある場合は
後者の方がいいとも言える。
745:デフォルトの名無しさん
08/01/12 09:57:33
>>743
URLﾘﾝｸ(ja.wikipedia.org)
746:デフォルトの名無しさん
08/01/12 10:16:17
どっかに、各ソートアルゴリズムの動きを比較して見られるようなサイトはないかなぁ。
例えばこんなのが並んでいるだけでもいいんだけど。
URLﾘﾝｸ(ja.wikipedia.org)
747:デフォルトの名無しさん
08/01/12 10:38:41
permutation
748:デフォルトの名無しさん
08/01/12 10:41:53
>>744
doubt
b-tree
749:デフォルトの名無しさん
08/01/12 11:07:56
ランダムな確率でランダムに入れ替えるという発想はいかんだろうか？
750:デフォルトの名無しさん
08/01/12 11:23:26
>>722
もしかして "stable sort でなければ何でもいい"って, 話なのではあるまいか?
751:デフォルトの名無しさん
08/01/12 17:02:26
おまいらは最強のボゴソートを知っているのか？
俺はあのソートの背景にある理論を知って涙を流した。
笑い涙だが。
752:デフォルトの名無しさん
08/01/12 17:41:37
俺は鳩の巣理論によるロンドン髪の毛話に感心したものだった
753:デフォルトの名無しさん
08/01/12 20:25:01
鳩ノ巣原理って中学受験で良く出るやつだな。
754:デフォルトの名無しさん
08/01/12 20:45:29
田中幸雄はカツラじゃないよ
755:デフォルトの名無しさん
08/01/12 20:45:53
えらいスレが延びてると思えばwww
756:デフォルトの名無しさん
08/01/13 21:35:51
>>742
うん
757:デフォルトの名無しさん
08/01/13 21:36:51
>>751
教えてください
758:デフォルトの名無しさん
08/01/13 21:50:12
c言語で、０～５の乱数を取得する時
rand() % 6;
よりも
rand() / (RAND_MAX + 1.0) * 6;
の方がいいんですか？
なぜですか？
759:デフォルトの名無しさん
08/01/13 21:59:48
整数と実数
760:デフォルトの名無しさん
08/01/13 22:03:34
>>758
俺は前者の方が読みやすくて良いと思うけど、
後者の方にもメリットはある。
rand関数の実装方法は処理系依存で内部がどうなってるかわからない。
ただ、完全な乱数をコンピュータで手軽に作りだすことは出来ないから、
当然何らかの疑似乱数関数になっている。
その疑似乱数はあくまでも疑似で、実装によっては
もしかしたら一番下のビットが必ず0になるようなアホな設計かも知れない。
そんな場合、rand()%6 だと0 2 4しか取り出せなくなってしまう。
そういう場合、乱数の範囲から特定する方法（後者の方法）ならば
まず間違いなく0～5の値を出力することが保証される。
多分こういうことだと思う。何か他にもあればだれかプリーズ
761:デフォルトの名無しさん
08/01/14 04:49:51
RAND_MAXが6の倍数じゃないと分布に偏りが出る。
762:デフォルトの名無しさん
08/01/14 09:17:28
RAND_MAXが32767である実装は世の中に多いが（VCとか）、
0～5なら問題ないが
int x = rand() % 10000;
とかした場合、明らかな偏りが発生してしまう。
763:デフォルトの名無しさん
08/01/14 09:42:36
rand() / (RAND_MAX + 1.0) * 6;
これも偏りが発生すると思うんだが。
0-32767 -> 0-5
という変換なんだから。
擬似乱数スレに回避する方法があったぞ。
764:デフォルトの名無しさん
08/01/14 10:14:43
リソースが許せば、メルセンヌツイスタ拾ってきたほうが早いな。
765:デフォルトの名無しさん
08/01/14 13:19:16
擬似乱数の多くは線形合同法だから 0～5が欲しいなら余りを求めるんじゃなくて割り算するのよ
実際は、2^ビット幅/6 と掛け算して、上位ワードを採用するんだけどね
766:デフォルトの名無しさん
08/01/14 13:44:14
一体いつの時代の話ですか
767:デフォルトの名無しさん
08/01/14 14:23:17
>>763
多分勘違いをしていると思うが、% 10000 で [0 .. 9999] にするとき、RAND_MAX が 32767 なら、
[0 .. 2767] が４通りになり、 [2768 .. 9999] が３通りになる。
>762 は、この４通りの部分がゼロ方向に集まることを指しているのだと思う。
[0 .. RAND_MAX] を [0 .. 9999] に線形に写像すれば、４通りの部分が全範囲にわたって均等に分布するようになる。
それでも４通りの部分をなくそうと思ったら、擬似乱数スレにあるように、RAND_MAX - (RAND_MAX % 10000) 以上を棄却するとよい。すると、どちらの方法でも均等になる（元の乱数が均等なら）。
768:デフォルトの名無しさん
08/01/14 15:50:12
[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 が言ってるのはこのことではないような気もするが
769:デフォルトの名無しさん
08/01/14 16:52:22
>>766 いつの時代ですかって、CのライブラリだろうがDelphiだろうが
みんな標準で入ってる乱数は線形合同法だよ。
770:デフォルトの名無しさん
08/01/14 16:53:12
あ、でも、間違えてる 乱数と掛け算するんだった。
771:デフォルトの名無しさん
08/01/14 17:16:02
Ｄｅｌｐｈｉｗｗｗｗ
一体いつの時代の話ですかｗｗｗｗｗｗｗｗｗｗｗ
772:デフォルトの名無しさん
08/01/14 18:34:49
文字列で指定した式を解析するのに
二分木で逆ポーランドに変換してからやる方法をさっき知って感動した
773:デフォルトの名無しさん
08/01/14 21:12:50
いつも思うんだけどさ
ポーランド記法が既に逆ナンであって
逆ポーランドって言ってしまうと
元に戻ってないか？ってことなんだ
774:デフォルトの名無しさん
08/01/15 05:47:15
>767,768
そういう意味だったのか。
でもなんか中途半端というか偏りを散らした(写像変換した)だけで
本質的な解決策じゃないように感じる。
それに、整数 -> 整数 の変換に実数キャストが挟まるのが凄く無駄に思える。
実数の実装も考慮してないし。
棄却するパターンの方が数学的に美しい。と思う。
775:デフォルトの名無しさん
08/01/15 07:19:20
>>758
大抵の実装は線形合同法。線形合同法の乱数は、そもそも特性が悪い。
そして下位ビット程特性が悪いんだ。
だから、余りを使って下位を採用すると隔たりが普通より大きくなるんだよ。
0～5の乱数が欲しいなら余りじゃなくて上位を採用しなければいけない。
というのと
rand() % 6; は割り算が必要だけど
rand() / (RAND_MAX + 1.0) * 6;
は (RAND_MAX +1)は通常は２のべき乗だから、掛け算＋シフトで計算出来るから
大抵のCPUで後者が高速という
２つの理由がある。
776:デフォルトの名無しさん
08/01/15 07:31:37
gcc -O3 on core2duoで実測してみたけど後者が遅かった記憶がある。
777:デフォルトの名無しさん
08/01/15 07:37:03
>>776
それはgccのRAND_MAXがint型の最大値に近いから、じゃない？
778:デフォルトの名無しさん
08/01/15 07:53:45
>>776 まさか、このまま実行したんじゃないの？
イメージとしては
(long)rand() * ( 1L<<32L )/6L )>>32L;
アセンブラコードだと EDXに2^32/6を入れて
MUL EDX
MOV EAX,EDX
779:デフォルトの名無しさん
08/01/15 08:14:15
>>778
あー
ゲームとかではあるかもしれないけど、アルゴリズムスレの扱う範疇からは外れてるね
移植性が無さ過ぎる
780:デフォルトの名無しさん
08/01/15 08:31:31
君は実にばかだ
781:デフォルトの名無しさん
08/01/15 08:32:09
よく言われる
782:デフォルトの名無しさん
08/01/15 12:09:53
>>775
「偏る」を「へだたる」って読んでる？
783:デフォルトの名無しさん
08/01/15 14:09:24
さすがにそれはなかろう
784:デフォルトの名無しさん
08/01/15 14:19:39
>>774
>実数の実装も考慮してないし。
え？ intへのキャストを外すだけだろ。
rand() / (RAND_MAX + 1.0) は区間[0,1)
（rand() / (double)(RAND_MAX) なら区間[0,1]）
の実数の乱数だからな。
>>768 のひどい誤差は整数変換のせいなので
むしろ実数の方が均一でより理想的なんだが。
785:デフォルトの名無しさん
08/01/15 18:40:21
>>775
なにが高速だって？
786:デフォルトの名無しさん
08/02/06 02:28:50
実数の配列A,Bから
最も値の近い要素の組A[k],B[l]を求める良い方法はないですか？
787:デフォルトの名無しさん
08/02/06 02:42:39
Aの各要素にA由来という印とインデックスを付加
Bの各要素にB由来という印とインデックスを付加
二つを合わせて配列CとしてCをソート
Cを先頭から走査して隣り合う要素の由来が違うもので差が最小のところを探す
ってのは？
まぁ合わせないでAB別々にソートしてもできるけど
788:786
08/02/06 03:04:22
なるほど、つまり
AB別々にソートしてからマージの要領で
比較していけばいいんですね。
ありがとうございました。
789:デフォルトの名無しさん
08/02/06 10:55:18
ソートアルゴリズムに興味があるんですが、
Ο記法とか計算時間の算出部などの計算式の意味がさっぱりわかりません。
Ο(n log n)とか意味がわかりません・・・
文系で最後に数学に触れたのは高2だったので、とっくに忘れているし元々数学は得意ではありません。
自分もそのうち効率は悪くても自分なりのソートアルゴリズムを考えてみたいと思っているのですが、
何から勉強をはじめたらいいでしょうか？
790:デフォルトの名無しさん
08/02/06 11:34:34
初心者向けのアルゴリズム入門の本なら、Ο記法の説明してあるのもある。
さすがに、log の意味から書いてあるのは少ないと思うが、
それくらいは高校の教科書読んで勉強してこいよ。
791:デフォルトの名無しさん
08/02/06 12:22:49
>>789
nは要素数でO(n log n)はnが増減した時の計算量の増減。
O(n^2)ならnが倍になると計算量が4倍になるってだけ。(3倍なら9倍)
計算量はあくまで計算量なんでアルゴリズムによって単位量あたりの
計算の複雑さは違うからね。
nlognなやつでもクイックソートとヒープソートは速度が大分違う。
メモリの局所性の問題とかもあったりする。
余計なお世話だと思うがソートは優秀なものが出尽くしてしまっているから
今更考え出すより既存のものを学んだ方が良いよ。
792:デフォルトの名無しさん
08/02/07 01:10:13
==俺様用しおり=========================
今日はQTクラスタリングというのを知ったので
このスレにメモっておく。
793:デフォルトの名無しさん
08/02/07 20:12:15
ソートアルゴリズムを知らない状態から自分なりのものを作ると高確率でセレクションソートになる気がする。
794:デフォルトの名無しさん
08/02/07 23:13:29
高校の頃、自力で挿入ソートに辿り着きましたが。
マージャンプログラム作ってて発見したよ。
795:デフォルトの名無しさん
08/02/07 23:21:37
>>791
いろいろ間違ってるよね。O は計算量とは無関係な概念でしょ。
796:デフォルトの名無しさん
08/02/07 23:59:09
は？
797:デフォルトの名無しさん
08/02/08 00:06:36
f(n) = O( g(n) ) であるとは、ある正数 C と正整数 N が存在して
任意の n ≧ N に対して f(n) ≦ C g(n) が成立することをいう
が、オーダ記法の定義でしょ。
計算量をオーダ記法で表現することは多いけど、別に関係はないよね。
オーダ記法で計算量を表さない分野だってあるよ。
798:デフォルトの名無しさん
08/02/08 00:16:49
>>797
ほー勉強になるが全く意味がわからんわｗ
アルゴリズムって難しいね
799:デフォルトの名無しさん
08/02/08 04:02:58
オーダ記法は計算量の理論の研究の中から生まれたもの
だから密接な関係があると言うのが普通
概念として独立させることができるとしても
800:デフォルトの名無しさん
08/02/08 07:55:37
>>799
> オーダ記法は計算量の理論の研究の中から生まれたもの
このことのソースは？
私の認識では、そんなことは年代的に絶対に有り得ない。
計算量の理論は通常はコルモゴロフの1950年か
チューリングの1936年をスタートだと考えるはず。
一方、オーダ記法自体はバッハマンの1894年が初出で、
広く使われるようになったのはランダウの1909年くらいから。
オーダ記法のほうが古い歴史を持っていると思うのだけれど。
801:デフォルトの名無しさん
08/02/08 08:08:46
＞計算量の理論は通常はコルモゴロフの1950年か
＞チューリングの1936年をスタートだと考えるはず。
ダウト
802:デフォルトの名無しさん
08/02/08 08:18:45
では、あなたはいつからだと考えるのが自然だと思うの？
803:799
08/02/08 18:11:40
Wikipedia を見てみたが，確かに私の勘違いだったようだ．スマン．
804:デフォルトの名無しさん
08/02/08 18:18:29
ソースはWikipediaかよ
805:デフォルトの名無しさん
08/02/08 18:44:38
>>804
まあ大目に見てやれ。
その前は脳内ソースだったんだから。
806:デフォルトの名無しさん
08/02/09 20:21:35
こんなのみつけた。ソートを可視化するスクリプトなのか？
URLﾘﾝｸ(d.hatena.ne.jp)
807:デフォルトの名無しさん
08/02/10 16:00:22
Wikipediaにも画像あるし
っつーか10年くらい前に
技術評論者のSoftwareDesign(いまもあるのか？)が記事で
CQ出版のInterfaceが既に過去に取り扱ってた画像を
そっくりそのまま盗用してしまってお詫びしていた
808:デフォルトの名無しさん
08/02/10 20:46:42
>>807 でっていう。
809:デフォルトの名無しさん
08/02/14 07:09:16
suffix arrayは名前の通り、後ろからのインデックスを作っていく様ですが
なぜ前からじゃないんでしょうか
810:デフォルトの名無しさん
08/02/14 07:45:21
>>809
文字列系アルゴリズムでは prefix より suffix のほうが有用だ
（と思われている）から。
811:デフォルトの名無しさん
08/02/14 13:06:56
BM法とか
812:デフォルトの名無しさん
08/02/14 21:33:07
>>809
prefix tree, prefix list などがあるよ。
813:デフォルトの名無しさん
08/02/18 21:23:04
あるアルゴリズムの概念はわかっていても、それをどういう風に実装するかとなると、
自分のレベルが低いため、難しくて実装することができません。
やり方を暗記してしまえば問題ないのですが、
暗記に頼るのではなく、考えてちゃんと実装できるようにしたほうがいいでしょうか？
それとも暗記しとけばいいでしょうか？
814:デフォルトの名無しさん
08/02/18 21:31:54
意味がわからん
815:デフォルトの名無しさん
08/02/18 22:45:51
>813
同じアルゴリズムを毎回毎回実装するなんて愚かしい。そういうものはライブラリとして持っておくべき。
ということで、実装方法を暗記しても意味がない。
結局、何かやりたいことを実現する＝アルゴリズムを考えて実装する、になるし何もかも既存のアルゴリズムが
流用できる、なんてなるわけないから自分で考える必要はでてくる。
その練習として、有名どころのアルゴリズムを自分で実装してみて他の実装と比べてみるというのはいいことだと思う。
816:デフォルトの名無しさん
08/02/18 23:44:27
実装方法が分かって、うまく動けばそれで満足するけどね。
実装できないと言うよりも
適切なアルゴリズムが分かってないんじゃないのかな。
あるいは、目的がぼんやりしているとか。
まぁいずれにしても、アルゴリズムは暗記でいい派だね。
さらには、辞書とか検索で調べられる程度の情報だけでいい。
817:デフォルトの名無しさん
08/02/19 00:38:36
暗記でもいいから一回自分で書いてみたらいいと思うよ。
818:デフォルトの名無しさん
08/02/19 02:25:49
>>813
質問が二つ。
(1) 「自分のレベルが低い」というのは、プログラム能力が低いのか、
それともアルゴリズムを実装に起こす能力が低いのかどっち？
前者なら慣れればなんとかなる。後者ならそもそもアルゴリズムを
十分に理解できていない可能性が高い。
(2) あなたの立場と考えてるアルゴリズムは何？
極端なケースでは、研究者が自分の専門分野のアルゴリズムを
暗記しているようでは全然ダメ。
819:デフォルトの名無しさん
08/02/19 03:36:37
ソートアルゴリズムで言えばクイックソートやバブルソートとかの名前は知ってるけど、
どういう動作するのか、どうプログラムしていいのかとか分からないって状態なんじゃね？
とても概念がわかってるとは言えないと思うけど。
820:813
08/02/19 20:53:16
レス遅くなりすみません。昨日はあのまま寝てしまって・・・
>>819さんの指摘していただいてるような感じです。
ただ、どういう動作をするのかは理解しているつもりなんですが、
書き起こせないってことはやはり概念を理解していないんですかね・・・
>>818
1の質問についてですが、両方ですかねぇ・・・
プログラムでどういう風に書けばいいかわからないみたいな感じです。
特にループ部分などが・・・ループのネストなんてやったことなくて・・・
2についてですが、
立場はただの趣味でやっているみたいなもんですかね。
将来的にプログラマを目指したいとは思っています。
アルゴリズムは探索やソートなどの基本的なものです。
基本的にソートや探索などの関数は、プログラム側で用意されていますし、
>>815さんの仰るとおり外部ライブラリとしてもっておけばいいのですが、
一応理解したうえで使うべきものなのかなぁと思って質問しました。
821:デフォルトの名無しさん
08/02/19 21:02:26
ただのバブルソートだけでもいいからとにかく書いてみれ
自分で手を動かさない香具師は向いてない
822:デフォルトの名無しさん
08/02/19 21:42:40
そのレベルでは，何をするにしてもお話にならないので，
とりあえず何でも良いから山ほどプログラム書くところからだね．
823:813
08/02/19 22:43:50
>>821-822
どうもありがとうざいます。
そうですね。とりあえずプログラムを書きまくってみることにします。
824:デフォルトの名無しさん
08/02/21 00:09:25
新しいソートアルゴリズム発見した！
とはいっても、どうせ同じようなのを他の人が見つけてるだろうけど…
数学的に厳密な書き方を知らないので雰囲気で書くけど、
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; } }
}
コンパイル試してませんが…
825:デフォルトの名無しさん
08/02/21 00:34:34
実装が壊滅的に最悪最低で酷くて、
書いたやつは救いようが無いビンソートにしか見えない
826:デフォルトの名無しさん
08/02/21 00:37:02
酷評すぎてワロタ
827:デフォルトの名無しさん
08/02/21 01:02:25
>>824
何このゴミ
828:デフォルトの名無しさん
08/02/21 01:48:20
>>825
同じ事オモタ
829:デフォルトの名無しさん
08/02/21 07:31:17
空間計算量 O(nm) って劣化にも程が
830:デフォルトの名無しさん
08/02/21 10:21:12
ネタだろ？
831:デフォルトの名無しさん
08/02/21 11:57:59
アルゴリズムにソースコードの実装は関係ないだろ、かわいそうにｗ
この実装だと時間・空間計算量O(nm)だけど、
mを定数だと考えると、条件付きO(n)ソートになるな。
最も実用上どうかと思うけど、発想は面白そうだな。可視的にやればうけそう
832:824
08/02/21 16:03:55
今までにない発想で面白いと思ったんだけど、
想像以上に叩かれてｼｮﾝﾎﾞﾘ。スレ汚しすまんでした
833:デフォルトの名無しさん
08/02/21 17:53:30
筋の悪いバケットソートでしかないしなあ
834:デフォルトの名無しさん
08/02/21 18:04:54
作ってみた。
ビンソートと同列だから目新しさは全くないけど、
ドットを左に寄せていくとソートいう発想はなかなかいいな。
URLﾘﾝｸ(void-main.org)
835:デフォルトの名無しさん
08/02/21 19:04:42
もっと簡単な方法を数分で思いついた。
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;
836:デフォルトの名無しさん
08/02/21 19:11:45
>>835
それは普通のバケットソート
837:デフォルトの名無しさん
08/02/21 23:45:18
アムロの親父スレ
838:デフォルトの名無しさん
08/02/22 05:21:04
自分のことを、誰も思いついてないような画期的なアルゴリズムを簡単に思いつけるような天才だと思ってんの？
839:デフォルトの名無しさん
08/02/22 11:58:34
>>824 >>838
子曰、學而不思則罔。思而不學則殆。
840:デフォルトの名無しさん
08/02/22 12:55:53
自分で考えるのは大事だけど、ここでこんなの思いついたって発表するが痛いってことだろ。
バカだから文脈読めないけど、難しい言葉使って少しでもかしこく見せたいってかｗ
841:デフォルトの名無しさん
08/02/22 13:04:58
なぜ努力もせずにただ考えようとするんだろう
842:デフォルトの名無しさん
08/02/22 17:01:40
基本も分からず、応用は出来ない
843:デフォルトの名無しさん
08/02/22 17:02:23
>>840
> 自分で考えるのは大事だけど、ここでこんなの思いついたって発表するが痛い
いや、それはいいんじゃね？
844:デフォルトの名無しさん
08/02/22 17:04:06
>>841
こういうのを「ゆとり」と言うんだろう
845:デフォルトの名無しさん
08/02/22 17:04:54
それこそ正にチラシの裏に書いておけってやつじゃね
846:デフォルトの名無しさん
08/02/22 17:28:58
でもそれをきっかけに他の住人が何か閃く可能性だってあるじゃん
847:デフォルトの名無しさん
08/02/22 18:28:52
遺伝的プログラムで
個々の優劣が明らかに出来る集団で
各順位の分布を初期からほぼ一定にする様なアルゴリズムってかDNA組合せ無いっすか?
自然淘汰してる様で実は歴史は繰り返すみたいなの
松竹梅な比率
1:3:4 第1世代
↓
1:3:4 第N世代
848:デフォルトの名無しさん
08/02/22 20:19:20
松竹梅それぞれの内から次世代を作れば出来なくは無いと思うけど、なんか意味あんの？
849:847
08/02/22 21:54:22
あ、優劣は生殖能力って事で
例えば各個体に付松なら６回、竹２回、梅１回の試行して次世代も同個体数
確立以上に存在するABO式血液型OO型のナゾを逆方向から見た考察です。
850:デフォルト名無しさん
08/02/22 23:47:58
５＋６/３を２ステップで求めることできる？？
851:デフォルトの名無しさん
08/02/23 10:12:50
>>850
step1 『アルゴリズムオタク』スレで質問する
step2 答えを待つ
852:デフォルトの名無しさん
08/02/23 10:40:16
>>850
質問１ 括弧がないけど 5 + (6/3) でいいのかな？
質問２ 何を１ステップに数えるの？メモリへのロードとかは？
853:デフォルトの名無しさん
08/02/23 11:02:58
メモリアクセスを除外すると、演算回数が2回なんだから2ステップだけどそれは自明だしね。
854:デフォルトの名無しさん
08/02/23 11:23:09
値のロードを入れると3つの値をロードした瞬間3ステップだしなあ
855:デフォルトの名無しさん
08/02/23 11:29:57
全部固定値なんで何を言いたいのか判らん
a+(b/3) を a,b入力値で 四則演算で求めろとか？
加算＋シフト演算で出すのは２ステップじゃ無理っぽいな
856:デフォルトの名無しさん
08/02/24 11:39:06
>>751
激しくカメレスで恐縮だが、あのソートアルゴリズムは
量子コンピュータ向きなのではないだろうか。えっ、違う？
857:デフォルトの名無しさん
08/02/24 11:59:52
おぬしも相当悪よのう
858:デフォルト名無しさん
08/02/25 21:03:57
８５０です。
教科書で問題として実際に出ているんです・・・・。
おれの頭じゃ無理で・・・
859:デフォルトの名無しさん
08/02/25 21:21:59
>>858
>>852 >>855
質問しといてレスをスルーすんな
860:デフォルトの名無しさん
08/02/26 11:02:00
test
861:デフォルトの名無しさん
08/02/26 19:57:29
エクスプローラのように文字列中の数値を考慮して並び替えるのに
定番の方法ってあるんですかね。
ぐぐっても参考になりそうなのが見つからなかった。
自分で適当に書いてみたが
数値がでかすぎるとオーバーフローしてソート順が狂う。
862:デフォルトの名無しさん
08/02/26 20:59:19
小数点や 3E5 みたいな１０のベキ表現が無いなら右寄せしてから比較すればいいんだけど
そうじゃないなら多倍長浮動小数点を自前で作るしかないね
863:デフォルトの名無しさん
08/02/26 21:07:31
右寄せって何ですか？
用途がファイル名のソートなので
少数とかは考慮しないで大丈夫です。
864:デフォルトの名無しさん
08/02/27 16:39:07
intのランダム数列に対して、ヒープソートとバブルソートをやって、所用時間を比較してるんですけど、
何度やってもバブルソートがヒープソートの半分くらいの時間でソートしてしまいます。
1～100000のランダム数列に対して、
heap: 167.83 sec
bubb: 83.2852 sec
という感じです。ヒープソートの実装がまずいのでしょうか？
実装はwikipediaからパクりました。
865:デフォルトの名無しさん
08/02/27 16:43:21
864ですが、ソース貼ってもいい？
866:デフォルトの名無しさん
08/02/27 16:48:06
より速いの作ってやるぜ
867:デフォルトの名無しさん
08/02/27 16:50:16
貼っちゃった。
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;
}
868:デフォルトの名無しさん
08/02/27 16:51:15
続きです。
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;
}
869:866
08/02/27 17:03:03
#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];
}
870:デフォルトの名無しさん
08/02/27 17:13:34
ありがとうございます。
-cout<<(cl+0.0)/1000<<"sec\n";
+cout<<(cl+0.0)/CLOCKS_PER_SEC<<"sec\n";
ですよね？
(自分の環境では、CLOCKS_PER_SECは1000000でした)。
たしかに、速いですね。
871:866
08/02/27 17:14:22
>>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;
}
872:デフォルトの名無しさん
08/02/27 17:23:20
>>864
ちゃんと見ていないけど、
mysort_heap, make_heap のところで 1 ベースの配列用と
0 ベースの配列用のコードが混じってるからおかしくなっているんじゃない？
873:デフォルトの名無しさん
08/02/27 18:22:27
>>863
自己レス。
右寄せってunko1024とunko256ってのがあったら
数字の部分の文字列を抜き出して
256
1024
という風に右寄せしてさらに比較って感じなのかな。
874:デフォルトの名無しさん
08/02/27 18:23:41
あ、スペース消えてる…。
...256
1024
875:デフォルトの名無しさん
08/02/27 19:52:46
>>864
ja.wikipedia 見た．なんだこのクソ実装．
きちんと解析する気も起きんが，このヒープソートは
どれだけよく見積もっても O(n^2) はかかってる，
具体的には make_heap 1 回が，最後の再帰を止めても
O(n) かかり，これを sort_heap で n 回繰り返すので，
最後の再帰が一回も実行されないとして O(n^2)．
876:デフォルトの名無しさん
08/02/27 20:18:05
STLのsortに対抗できないないなら初めからやる意味無し
877:デフォルトの名無しさん
08/03/19 02:28:32
ていうかアルゴリズムの話になるとなんでいつもソートの話にばっかり収斂していくんだろう。
いまさらソートなんてそうとう早くない(ry
878:デフォルトの名無しさん
08/03/19 04:48:20
ネタ振り
ソートと同じでこれまた定番な話題に文字列検索がありますが、
文字列中で、複数の単語の中から最初に現れるものを検索
する場合はどうするのが良いでしょうか？
例
検索対象の文字列 abcdefg
単語 ac bc bd bcd
この場合だと検索結果は bc bcd の2つになる。
879:デフォルトの名無しさん
08/03/19 05:14:01
適当に単語の木を組めばいいんじゃね
880:デフォルトの名無しさん
08/03/19 05:22:02
>>875
ここまで糞なヒープソートも珍しいw
全く理解してないくせによくwikipedia書けるな…
>>864
URLﾘﾝｸ(www.sci.csuhayward.edu)
881:デフォルトの名無しさん
08/03/19 07:07:18
>>878
「最初に現れるものを検索」ってのが理解できない
文字列 abcdefg で単語 bc, de だったら bc だけになるの？
なんにせよ Aho-Corasick の変形でいけそうだけど
882:デフォルトの名無しさん
08/03/19 07:09:57
>>878
ac|bc|bd|bcdを正規表現で検索
883:デフォルトの名無しさん
08/03/19 07:14:43
速度が大事なんだろ
一桁目の、ビットORをとって、対象文字とANDを取り一致すれば調べていけば
884:デフォルトの名無しさん
08/03/19 08:19:57
間違いに気付いたら誰か直して欲しいなあ>>ウィキペ
885:デフォルトの名無しさん
08/03/19 08:50:11
どの記事？
886:デフォルトの名無しさん
08/03/19 08:53:39
URLﾘﾝｸ(ja.wikipedia.org)
これかな
887:デフォルトの名無しさん
08/04/08 21:40:54
アルゴリズムを通信授業で勉強してるんですが
かなりちんぷんかんぷんです
何故5→Aになるのかも意味が分かりません
アルファベットだったら代入するのは何でもいいんでしょうか？
それとも決まってますか？
後アルゴリズムの効率のいい勉強の仕方も教えてくださいｍ＿ ＿ｍ
888:デフォルトの名無しさん
08/04/08 21:46:17
>>887
俺にはお前の質問がちんぷんかんぷんだ
889:デフォルトの名無しさん
08/04/08 21:48:34
> 後アルゴリズムの効率のいい勉強の仕方も教えてください
こんなこと言うやつは勉強しても身に付かず、結局
「効率のいいアルゴリズム教えてください」
って言うだけになるんだろうな。
890:デフォルトの名無しさん
08/04/08 21:49:09
＞効率のいい勉強の仕方も教えてくださいｍ＿ ＿ｍ
まず国語の勉強。
891:デフォルトの名無しさん
08/04/08 21:56:05
お願いします。教えてください
文章が変なのはリアル厨房なので大目に見てくださいm（＿ ＿）m
はじめはアルゴリズムの何を勉強したらいいんでしょうか？
892:デフォルトの名無しさん
08/04/08 22:03:04
「アルゴリズムを勉強する」ためのアルゴリズムを考えてみよう。
893:デフォルトの名無しさん
08/04/08 22:16:48
>>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」
と言われて自力で証明できないようでは、アルゴリズム論を勉強しても
結局何も身につかない。
894:デフォルトの名無しさん
08/04/08 22:55:18
>>887
本を買え。推薦図書スレで推されている本格的なのを。
895:デフォルトの名無しさん
08/04/08 23:22:08
> 何故5→Aになるのかも意味が分かりません
ああ、まったく意味が分からん。
896:デフォルトの名無しさん
08/04/09 02:18:30
>>887
通信授業でアルゴリズムを勉強していますがかなりチンプンカンプンな状態です。
Ａに５を代入するにはＡ＝５と記述すると習いましたが理解できていません。代入するとはどういう意味なのでしょうか？
またＡ以外のアルファベットにも５を代入できるのでしょうか？それとも代入可能なアルファベットはＡだけなのでしょうか？
あと効率のいい勉強法をお知りでしたらそちらについてもアドバイスお願いいたします。ｍ＿ ＿ｍ
897:デフォルトの名無しさん
08/04/09 03:14:11
>>896
代入ってのは変数に値を入れるという意味。
変数ってのは何らかの値を入れるための箱だと思っておけばいい。
そしてここではAってのが箱の名前で、５ってのが箱に入れる値。
ある種のプログラミング言語においてA=5という表現は、
Aという箱に5という値を入れる操作をコンピュータに行わせるという意味であって、
数学における同様の表現とは全く別の意味。
あと箱にAと名付ける事は代入ではないし、箱の名前はAじゃなくてもいい。
898:デフォルトの名無しさん
08/04/09 05:37:03
>>896
普通の（手続き型の）プログラム言語を一つ触ってみるといいんじゃないかな．
Java とか Ruby とか何でもいいから．
そうするとだいぶイメージがわくし，今後のためになるはずよ．
899:デフォルトの名無しさん
08/04/09 08:04:05
その通信授業で、わからないことをとことん聞くことは出来ないのか？
2chで通信授業するのはやめとけ。
900:デフォルトの名無しさん
08/04/09 12:11:16
ガキとオタクと田舎者はネットやんな
901:デフォルトの名無しさん
08/04/09 14:01:06
オタクに教えを請うことがいかに愚かなことか勉強になったな。
どんなことでも、勉強する時は、同じ分野の本を三冊以上読むんだ。
分からないことをスルーしながら、とにかく沢山読む。
すると、何が分からないのかが分かり、何を調べればよいのかがわかるようになるから、それまでに読んだ本から適切な部分を読んで調べることができるようになる。
とにかく沢山読め。
902:デフォルトの名無しさん
08/04/09 21:54:33
オタクってのは自分で勉強したり調べたりってことをしないのかね
903:デフォルトの名無しさん
08/04/09 22:42:35
いや自分で調べるくらい出来ないとオタクにはなれないだろ
904:デフォルトの名無しさん
08/04/09 23:08:16
昔のオタクはそうだったかもしれないが
今のオタクは・・・
905:デフォルトの名無しさん
08/04/10 03:30:22
>>902,903
オタクは自分で調べるが、他人に教えることは不得手。と思う。
906:デフォルトの名無しさん
08/04/10 07:08:41
>>905
オタクってのは自己満足のオナニスト。
知識の切り売りをしているような軽薄な連中とは違うのだよ。
907:デフォルトの名無しさん
08/04/12 12:20:22
>>1きもすぎｗｗｗ
まさかエレベータに乗ってるとき隣の奴がアルゴリズム考えてるとは思わないわ
きもいから死んでくれ
908:デフォルトの名無しさん
08/04/12 14:55:18
まさか、エレベータで隣り合わせた奴に「隣の奴がアルゴリズムを考えている」かどうか意識されているなんて思わないよ。
909:デフォルトの名無しさん
08/04/13 02:44:50
>>907
お前の方がキモイから
910:デフォルトの名無しさん
08/05/06 07:36:00
ｵﾚは小学校のときからﾊﾟﾁﾝｺ屋のﾈｵﾝがどうやって動いてるように見せているのかとか
信号で歩道用と車道用の切り替わりﾀｲﾐﾝｸﾞとかずっと考えてたけどな
そんで周囲からいつもボーっとしてるって言われてた
ココ居るやつらってみんなそんな感じじゃねーの？
911:デフォルトの名無しさん
08/05/06 08:23:00
>>910
あー、なんか判るわ。
私もエレベータの操作パネル見ながら点字を自力解釈したりしてたしね。
912:デフォルトの名無しさん
08/05/06 08:32:23
人工物全般から製作者の意図を考えたりする。
913:デフォルトの名無しさん
08/05/06 09:40:46
>>910
俺は、そういうのはプログラミングを始めてからだな。
ただ、ボーっとしてると言われたっていうのはよくわかるｗ
まさか小学生の子供がそんなこと考えてるとか大人は思いもしないんだよな。
914:デフォルトの名無しさん
08/05/06 18:46:02
点字は自分も考えたわ
ローマ字を習う前だったけど
50音表と睨めっこして
子音＋母音のパターンは見つけた
（母音や子音なんて言葉は知らなかったけど）
その時はボーッとしてるなんて言われてたけど
今は研究職やってます。脳味噌の構造はそのまま
915:デフォルトの名無しさん
08/05/15 04:11:56
過集中って奴じゃないですか。
ボーッとしているように見えるほど没頭するのは。
916:デフォルトの名無しさん
08/05/26 23:16:42
ソートのアルゴリズムなんだけど
１．ランダムなプログラムをいくつか生成する。
２．データをプログラムに通す。
３．出力結果を評価する。
満足のいく速度でデータがソートされれば、終了する。
ダメなプログラムに対しては悪い評価を与える。あるいは破棄する。
それなりに有望なプログラムについては、良い評価を与える。
４．現在存在するプログラムをもとに、少し違ったプログラムを生み出す。
５．２へ
これってボゴソートとは違うよね？
時間計算量はどのくらいになるんだろ？
実際、わりと優秀なプログラムが生き残ったっていう話を聞いたけど。
917:デフォルトの名無しさん
08/05/27 00:53:03
それはソートのアルゴリズムってより、遺伝的プログラミングだと思う。
918:デフォルトの名無しさん
08/05/27 01:23:50
>>916
たぶん、本当にそのとおりに実行したら、
現実的な時間ではソートプログラムは作れないと思う。
919:デフォルトの名無しさん
08/05/27 02:31:24
>>916
ソートのアルゴリズムではなくて、個数が20個とかに限定されているときに
最小回数の比較でソートするには何番目と何番目をどの順番で
比較して交換いけばいいか？っていう問題だったと思う。
具体的な実装は>>917。
920:デフォルトの名無しさん
08/05/27 11:41:32
Core2Quad Q9450でPS2エミュをやると、実機と違い処理オチせず、激ムズになることが判明
ｽﾚﾘﾝｸ(news板)l50
921:デフォルトの名無しさん
08/06/12 22:56:25
赤黒木を1次元配列で実装したサンプルないですか？
922:デフォルトの名無しさん
08/06/14 11:55:28
>>921
あるよ
923:デフォルトの名無しさん
08/06/15 10:51:10
じゃあ教えて
924:デフォルトの名無しさん
08/06/15 22:49:45
見つかりました。ありがとう。
925:デフォルトの名無しさん
08/06/16 07:44:21
ねーよｗ
926:デフォルトの名無しさん
08/06/16 13:37:39
自己解決しました
927:デフォルトの名無しさん
08/06/16 14:20:28
なかったので自分で作りました。
928:デフォルトの名無しさん
08/06/16 20:45:58
ぐぐっても出てこないので、存在しません
929:デフォルトの名無しさん
08/06/16 21:06:02
ヤフったら出てきたので、存在します
930:デフォルトの名無しさん
08/06/16 22:41:46
まずさ、赤いのか黒いのか、どっちかはっきりしてくれないとわからないだろ？
931:デフォルトの名無しさん
08/06/16 23:51:53
ねーよｗ
はよだせコラ
932:デフォルトの名無しさん
08/06/18 22:11:51
と思ったらあった。すまんw