06/12/06 12:47:48
>>467
自然界では普通の兄弟もいれば異母兄弟も異父兄弟もいるよね。
有性生殖と単性生殖（クローン）の両方を行う奴もいるし。
470:461
06/12/07 08:13:17
>>468
実際にやってみることは大切ですね。
ありがとうございます。
>>469
兄弟などを考えたら親が同じ可能は0じゃないですもんね。
同じ親でも子が全く同じになる可能性は遺伝子長にもよりますが余り多くはないですよね。
昨日借りてきたジョンホランドの訳書なんですが軽く読み流しただけでは無能は自分には理解できない様な内容でした。
と言うか自分が考えていた以上と言うか。
スレ違いになりますが今日伊庭さんの遺伝的アルゴリズムの基礎？って本を借りるつもりですが
他に初心者でも分かりやすいお勧めの書籍有りましたら教えていただければ幸いでございます。
色々有り難う御座いました。
471:デフォルトの名無しさん
07/02/09 17:59:10
スレタイ通りの人物がいれば知っていそうな気がするので質問。
URLﾘﾝｸ(oshiete1.goo.ne.jp) で話題になっているアルゴリズムの由来はご存知ない?
このアルゴリズム、フラグ用の配列を初期化しないで使う、アイディアものだと思うのですが。
#いっそ、「森田のよく利用する賢いアルゴリズム」って名前で公表しろよと思ったのは内緒。
472:デフォルトの名無しさん
07/02/09 18:16:44
↓戯言なので読み飛ばし推奨
数年前に友人と酒飲んで話した時のあやふやな記憶
CPUだかメモリだかの量子っぽい回路ので似たような処理の話を聞いた
ような気がする
473:デフォルトの名無しさん
07/02/10 02:08:18
由来は知らんが、数値計算で同じ配列を使いまわして計算する場合
なんかには、常識的に使われているテクニック。他のところでも
しばしば見ることのある技法だと思う。
やっているのことは、配列 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 のような言語に特有のものなので、
＃「アルゴリズム」というほど一般的でないと思う。
474:デフォルトの名無しさん
07/02/10 05:20:56
>>471
このアルゴリズムはデータ数＜データの変域が前提になってるね。
フラグの初期化の処理をフラグの正しさの確認の処理に置き換えてるから。
475:虚構世界内存在 ◆vWilh8Qklc
07/02/26 23:43:49
オタクとは何か。
より多くの人びとはオタクという概念について混乱している。
それは、特定の種類の虚構作品の選好と総体的外見との間に因果的関係を見て取ったこと、ならびに感覚を即座に絶対化したことから始まった。
そろそろオタク概念の整備をしよう。
URLﾘﾝｸ(www.google.co.jp)
したがって、「オタクは気持ち悪い」というのはトートロジーである（そもそも、気持ち悪い者にオタクという固有名を付けたのであるから）。
あとは、「気持ち悪い」という感覚や感情を即座に正当化することが問題か。
URLﾘﾝｸ(www.google.co.jp)
一般人とは……（虚構世界内存在による使用法）
URLﾘﾝｸ(www.google.co.jp)
476:デフォルトの名無しさん
07/03/04 22:38:00
どうしてもつくれないアルゴリズムがあるので助けてください
１円～９９９円のお買い物をするときに
はらう硬貨の枚数とお釣りの硬貨の枚数の和が最小になる払いかたで
払う金額と持っている硬貨枚数がいかなるときでも対応できるアルゴリズムがわかりません
１０００円札は１枚は持っています
硬貨は1.5.10.50.100.500です。お札は1000のみです
477:デフォルトの名無しさん
07/03/04 22:41:13
ｽﾚﾘﾝｸ(tech板:448-番)
478:デフォルトの名無しさん
07/03/04 23:43:08
全探索しかないか…
479:デフォルトの名無しさん
07/03/05 01:06:42
>>476
簡単じゃないか。
払う硬貨の枚数は常に0が最小なのだから、釣りとして受け取る硬貨の枚数を最小にする呪文を唱えればいい。
「釣りはいらねぇよ、とっときな」
480:デフォルトの名無しさん
07/03/05 02:30:54
すごく・・・漢です
481:デフォルトの名無しさん
07/03/05 23:13:34
人間の考えをプログラムにする感じでやってみたがゴチャゴチャになってしまった
482:デフォルトの名無しさん
07/03/05 23:34:44
この手の問題はコンピュータには、人間の思考と同じやり方ではやりづらいだろうな。
もっと究めてニューラルネットワークでも組めば別だろうが。
483:デフォルトの名無しさん
07/03/09 23:48:50
「お会計は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枚。
うーん
484:京大生ｗｗｗ ◆HEfxsk5e3k
07/03/10 00:18:41
>>476
面白い、おれさまが考えよう
んん・・・・・・・難しい・・・・・・
485:デフォルトの名無しさん
07/03/10 01:09:48
1165円払って501円受け取るのもあるね。7枚だけど
486:デフォルトの名無しさん
07/03/10 01:15:30
アルゴリズム的に最小でも、店員が妙な顔する組み合わせはやめてあげようよ
487:デフォルトの名無しさん
07/03/10 01:17:33
>>485
硬貨枚数とあるから、6枚だと思う。
488:京大生ｗｗｗ ◆HEfxsk5e3k
07/03/10 01:36:59
こういうのはまず1~99までで考えるべきだと思う。
その過程で有効なアルゴリズムを考え付くこともある。
というわけでやってみようかな
ところで1000円札は硬貨ではないけど
999円の時は1000円札だして1円お釣りが最速だから1枚っていう風に考えていいのか？
489:デフォルトの名無しさん
07/03/10 01:38:22
1000円だけ特別扱いするのは美しくない
490:デフォルトの名無しさん
07/03/10 02:04:30
硬貨は十分な枚数あるものとする。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枚
491:デフォルトの名無しさん
07/03/10 02:13:08
さすが
492:デフォルトの名無しさん
07/03/10 03:12:36
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枚
493:デフォルトの名無しさん
07/03/10 05:35:07
797=1000-100-100-1-1-1 6枚
494:デフォルトの名無しさん
07/03/10 07:47:26
改善改善とか言ってる企業にかぎってアルゴリズムを工夫しないんだよね
495:デフォルトの名無しさん
07/03/10 12:03:45
こういった探索系のアルゴリズムは全探索が基本で
後はいかに無駄な探索を省くか(枝刈り)を考えた方が簡単でしかも速く、正確に動く。
496:デフォルトの名無しさん
07/03/10 12:53:21
払う側が硬貨をもっとも減らすアルゴリズムを考えるともなく使っている人間って偉大。
ちなみにいつもは手持ちの硬貨を減らしつつ、例外的に100円玉をもっとも増やす
アルゴリズムを使っています。
497:デフォルトの名無しさん
07/03/10 15:19:13
スーパーのレジの中に2000円札を見かけるけど、おつりでもらった事は無いなあ・・
498:476
07/03/10 17:45:38
全探索＆所持硬貨枚数での場合わけ
Rを使ってプログラムを作りました。
時間かかりすぎる・・・orz
499:デフォルトの名無しさん
07/03/10 17:54:29
単純な全探索でも一瞬で終わるが･･･
500:476
07/03/10 18:46:57
ｍｊｓｋ
501:デフォルトの名無しさん
07/03/10 19:11:48
理由判明
所持硬貨枚数のwhile文に対して
外側に所持硬貨枚数を計算させる部分をもってきていました。
それにしても時間がかかる… 誰か修正してくれ…orz
502:デフォルトの名無しさん
07/03/10 23:45:43
例えば1円玉を払って1円玉がお釣りで返ってくるようなやり方は排除していいから
1円玉が-4～4枚
5円玉が-1～1枚
10円玉が-4～4枚
50円玉が-1～1枚
100円玉が-4～4枚
500円玉が0～1枚
1000円札が0～1枚
と考えてよさそうだ
503:デフォルトの名無しさん
07/03/11 10:44:00
全検索でいいじゃんｗｗｗｗｗｗｗｗ
何か不満でも？ｗ
504:デフォルトの名無しさん
07/03/11 12:08:33
さめがめ(samegame)で全探索するときの枝刈りって良い方法あるのかな?
昔Gooゲームかなんかでこれと同じルールのゲームがあったんだけど(たしか名前はブロキシー)
時間制限がなかったから手動で配置を入力して探索させてみたけど
なんの工夫もしなかったから全然良い点の手みつけられなかった
そのうえGooのやつはランダム要素を持ったブロックが一個だけあって、
それは最後まで残すようにするしかなかった。
505:デフォルトの名無しさん
07/03/11 15:16:09
1円から999円までの「硬貨の枚数の和が最小になる払い方」での
枚数の和のリストを出力してみた。
(例: 1円は1枚, 2円は2枚, 3円は3枚, 4円は2枚 ... 999円は2枚)
誰か検算してくれ。
1232123321234323443234543455434554345432344323432123432344323454345543456545654345543454323443234321
2343234432345434554345654566545665456543455434543234543455434565456654567656765456654565434554345432
3454345543456545665456765677656776567654566545654345654566545676567765678767876567765676545665456543
4565456654567656776567876787656776567654566545654345654566545676567765677656765456654565434554345432
3454345543456545665456765676545665456543455434543234543455434565456654566545654345543454323443234321
2343234432345434554345654566545665456543455434543234543455434565456654567656765456654565434554345432
3454345543456545665456765677656776567654566545654345654566545676567765678767876567765676545665456543
4565456654567656776567876788767887678765677656765456765677656787678876788767876567765676545665456543
4565456654567656776567876787656776567654566545654345654566545676567765677656765456654565434554345432
345434554345654566545676567654566545654345543454323454345543456545665456654565434554345432344323432
506:デフォルトの名無しさん
07/03/11 15:39:42
所持金の枚数に制限を加えた場合のリスト
（1円1枚, 5円2枚, 10円2枚, 50円2枚, 100円2枚, 500円2枚）
1432124321254323543236543465434654345432354323432125432354323654346543476545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876798767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
365434654347654576545876567654576545654346543454323654346543476545765457654565434654345432354323432
507:デフォルトの名無しさん
07/03/11 15:46:05
ソースうp
508:デフォルトの名無しさん
07/03/11 16:44:47
>>507
出力結果が正しそうだったら、ね・・・
509:デフォルトの名無しさん
07/03/11 17:11:32
>476の問題だと千円札は一枚持っているけど、
硬貨を何枚持っているかは不明なんじゃないの？
510:デフォルトの名無しさん
07/03/11 17:57:22
>>509
もちろんそうだろ？
「任意の枚数指定ができるプログラムを作れ」ってのが本来の課題。
511:デフォルトの名無しさん
07/03/11 18:01:02
>>506
総当たり、たぶん同じ
1432124321254323543236543465434654345432354323432125432354323654346543476545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434654347654576545765456543465434543236543465434765457654587656765457654565434654345432
3654346543476545765458765687656876567654576545654347654576545876568765698767876568765676545765456543
4765457654587656876569876798767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656876569876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545765458765676545765456543465434543236543465434765457654576545654346543454323543234321
512:デフォルトの名無しさん
07/03/11 18:50:13
>>511
ソースうp
513:デフォルトの名無しさん
07/03/12 16:09:47
所持硬貨数に制限無しなら色々ありそうだけど制限ありだとまったく思いつかない
514:デフォルトの名無しさん
07/03/12 17:45:22
>>506
なあ、その条件で10円を1枚にしてやってみてくれないか
515:デフォルトの名無しさん
07/03/13 00:16:42
>>514
これでいいか？（1円1枚, 5円2枚, 10円1枚, 50円2枚, 100円2枚, 500円2枚）
1432124321254323654347654565434654345432354323432125432354323654347654576545654346543454323543234321
2543235432365434765458765676545765456543465434543236543465434765458765687656765457654565434654345432
3654346543476545876569876787656876567654576545654347654576545876569876798767876568765676545765456543
4765457654587656987679876787656876567654576545654347654576545876568765687656765457654565434654345432
3654346543476545876568765676545765456543465434543236543465434765457654576545654346543454323543234321
2543235432365434765458765676545765456543465434543236543465434765458765687656765457654565434654345432
3654346543476545876569876787656876567654576545654347654576545876569876798767876568765676545765456543
476545765458765698767A987898767987678765687656765458765687656987679876798767876568765676545765456543
4765457654587656987679876787656876567654576545654347654576545876568765687656765457654565434654345432
365434654347654587656876567654576545654346543454323654346543476545765457654565434654345432354323432
516:515
07/03/13 00:18:20
あ、A っていうのは 10 枚のことね(16進数表記)。
517:デフォルトの名無しさん
07/03/20 23:49:46
age
518:デフォルトの名無しさん
07/03/29 23:52:40
来月入社する者ですが、入社前までの宿題として出されたアルゴリズムの
最後の問題がどうしても解けないお（;^ω^）
当方文系出身のせいでちんぷんかんぷんなんだお・・・
心優しい方手伝ってはくれないだろうか？お願いしまつ・・・
ageて申し訳ない。次からはsageて行くので・・
519:デフォルトの名無しさん
07/03/29 23:55:39
どれどれ。
とりあえず問題を見せてもらおうか。
520:デフォルトの名無しさん
07/03/29 23:59:32
ありがとうございまつﾟ+.ﾟ(´っω・｡｀)ﾟ+.ﾟ
問題；複数の生の整数を入力し、その中の最大値と最小値、平均値を求める
処理の流れ図を作成せよ。なお、入力の終了は-1を入力した場合とし、
データは必ず１件以上入力されるものとする。
多分かなり初歩的なアルゴリズムかと思われるのですが自分にとっては
難しいです・・何せアルゴリズムの本当の初歩しか本で勉強していない
身ですのでorz
お願いしまつ（;´д｀）
521:無知な新社会人
07/03/30 00:00:26
あ・・正の整数です('A`)
522:デフォルトの名無しさん
07/03/30 00:15:48
>>521
アルゴリズムと言うにもおこがましい。人間がそれを為すようにすればよいだけだ。
ついでに言えば、流れ図なんぞを書かせるような会社には似合いの人材というわけだな。
523:無知な新社会人
07/03/30 00:20:14
>>522
手厳しいお返事ありがとうございます。
ですが・・・本当にどういう風に書けばいいのか理解できないのでここの
住人の力を借りさせて頂こうと思った次第ですので・・何卒お手柔らかに
(´･ω･`）
524:デフォルトの名無しさん
07/03/30 00:21:59
>>520
悪いことは言わん、他所の業界へ行け。
罵るつもりはないが、このままじゃお前とお前に関わる者が不幸になる。
・・・と、思ったが、普通の初心者ってこんなんだっけ？
もう20年以上もプログラミングやってるし、初心者の感覚がさっぱりわからん。
525:無知な新社会人
07/03/30 00:27:53
>>524
この業界には文系ながらも興味がある上、勉強していてもとても楽しいので
実際仕事に携わってみてから貴方の意見を参考にさせていただきたいです。
ですが、玄人から見たら多分自分みたいな雑魚が入っても迷惑なだけという
意見は理解できます・・・そうならないように努力します。
初心者の私からみたら･･･正直こんなアルゴリズムとも呼べない問題でも
どういう風に図を組み立てればいいかわからないですorz
526:デフォルトの名無しさん
07/03/30 00:32:39
流れ図は書いたことがない。
時代遅れだと思うしうちの会社でも使わないんで。
力になれなくてすまんね。
527:デフォルトの名無しさん
07/03/30 00:34:43
まぁ、過疎ってることだし、少しぐらい相手してやるか。
>勉強していてもとても楽しいので
この業界ではこれが一番大切な才能だ。それを持っているならどうにかなる。
とりあえず一度に解決しようとするな。一度問題を噛み砕け。
たとえば、まず最大値だけを求めることを考えろ。それでもイメージが沸かなければ
さらに噛み砕いて二つの値が与えられた時にその内の大きなほうの値を求めることを考えろ。
528:無知な新社会人
07/03/30 00:35:57
>>526
そうなんですか。
仕方ないです。なんとか自力でｶﾞﾝｶﾞｯﾃみます(;´･ω･`)
529:デフォルトの名無しさん
07/03/30 01:34:20
かけるけど、AAで表現するのはめんどくさいなぁ
流れ図云々より、プログラム書くこと覚えたほうが手っ取り早
530:デフォルトの名無しさん
07/03/30 13:36:51
<繰り返し>
数字の入力
|
正の数か？ ->-1以外の負の数：怒る
|
-1なら入力した個数がいくつかチェック ->0個：コラッ！
正の数ならリストに数値を追加
</繰り返し>
|
-1で個数が0以上の時計算に入る
|
ごにょごにょ
|
出力
531:デフォルトの名無しさん
07/03/30 14:28:38
前に作った簡易フローチャート風表記を使うとこうなるかな。
() //端子
{} //繰り返し開始記号
[]数字の入力 //処理
<>数値チェック //分岐
<-1
[]怒る
()終了
<>数値チェック
==-1
[]ループ脱出
[]リストに数値を追加
{}
<>入力個数チェック
==0
[]怒る
()終了
[]最大値、最小値、平均値の算出
()終了
処でこの問題、求めた値を出力しないでいいんだろうか｡
532:無知な新社会人
07/03/30 14:53:45
すみません。
そんな所よりも肝心要の
「入力処理部分（キーボード割り込みから、整数のparsingぐらいまで）」
をメインにお願いします。
自力でｶﾞﾝｶﾞｯﾃるんですが、全然かけません・・・OTL
533:デフォルトの名無しさん
07/03/30 15:32:39
>>532
ちょっと待て。あんたの言う要の部分は普通はOS側にライブラリ経由で処理してもらうところだ。
#パースはライブラリだけど。
一体全体、どんな環境の何をやろうとしているんだ?
534:無知な新社会人
07/03/30 15:56:28
宿題では環境の指定はないですが、
もし書きにくいようでしたら、
PC/AT互換機という事でいいでつ。
# OS が絡むと面倒なので、"OS は無し" という事で・・・（;^ω^）
私としては、それなりに流れ図が書けていて、
入社後に教育担当の方から怒られなければ
それでいいでつ（;´д｀）
535:デフォルトの名無しさん
07/03/30 16:02:44
OSなしでIO処理しろって、どんな課題だよ。
環境が指定されてなければ、このあたりは
環境に用意されているものとしていいはずだ。
パースはともかく割り込みのあたりなんて
アルゴリズムの範疇ではない。
536:デフォルトの名無しさん
07/03/30 16:19:06
>>535
>OSなしでIO処理しろって、どんな課題だよ。
多分、入社後の研修では H8 とか PIC とか使わされる事に
なりそうなんですが・・・
また、この宿題については、研修担当の方からは
「（所詮、流れ図だから）君の得意な環境を想定して書けばよい」
と言われました。
助けてくださいﾟ+.ﾟ(´っω・｡｀)ﾟ+.ﾟ
537:デフォルトの名無しさん
07/03/30 16:21:46
>>534
情報が少なすぎてなんとも言えないけど、
ろくに会話もできないぼんくらをプログラマとして雇うような糞会社が要求する流れ図なんて、
>531のレベルで書けてりゃ充分だろ。
538:無知な新社会人
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;