アルゴリズムとデータ構造なら俺に聞け

このエントリーをはてなブックマークに追加
1スーパー(以下略)
何でも聞きなさい。
ワソーイ   ∧_∧     >>1      ∧_∧  
      (, ゚∀゚,∩     ↓     (゚∀゚∩)  アーーーーヒャヒャヒャヒャ
      (つ   ノ   ガクプル   ⊂    ;;;)
  ∧_∧  ( ノ  (((( ;゚Д゚)))    ヽ∧_∧
  (;;;;  ´∩ (_)   ノ( へ)ヽ    (;;;    )∩
  ノ;;;;   ノ       <       ⊂;;;;;      ノ
 ○   ノ                  ヽ  ○ )
  )\ ヽ  ∧_∧     ∧_∧  ノ  ノ(⌒)
  (____(____) (;;;;;;;;;;  )    (   ;;;;;;;)(_____)  ̄
       ⊂ ;;;;   )     ノ   ;;;;;;つ     モーヒョヒョヒョ
        (  ○ )     (○  (
        (  (  (    (⌒)ヽ  )
        (____)___)     ̄  (____)

          宴は始まったばかりだ・・・
3
4デフォルトの名無しさん:02/06/28 21:00
ニューラルネットワークについて聞きたいのですが、OK?
数学というか算数ダメダメな俺にも分かるように
rangecoderを1から教えて下さいコノヤロー
1は逃走した
ワソーイ   ∧_∧     >>1      ∧_∧  
      (, ゚∀゚,∩     ↓     (゚∀゚∩)  アーーーーヒャヒャヒャヒャ
      (つ   ノ   ガクプル   ⊂    ;;;)
  ∧_∧  ( ノ  (((( ;゚Д゚)))    ヽ∧_∧
  (;;;;  ´∩ (_)   ノ( へ)ヽ    (;;;    )∩
  ノ;;;;   ノ       <       ⊂;;;;;      ノ
 ○   ノ                  ヽ  ○ )
  )\ ヽ  ∧_∧     ∧_∧  ノ  ノ(⌒)
  (____(____) (;;;;;;;;;;  )    (   ;;;;;;;)(_____)  ̄
       ⊂ ;;;;   )     ノ   ;;;;;;つ     モーヒョヒョヒョ
        (  ○ )     (○  (
        (  (  (    (⌒)ヽ  )
        (____)___)     ̄  (____)

          宴は始まったばかりだ・・・
1でてこいゴルァ
重複スレです。

アルゴリズムに関する質問、議論総合スレ
http://pc.2ch.net/test/read.cgi/tech/1014783451/
πの出し方、10通りくらい教えてよ。
0.99999… = 1 って知ってたか?
1/3*3=1 って知ってたか?
>>11
知らなかった。
14ななし:02/06/29 00:16
RDB開発での行ロック(ロックエスカレーションしないやつ)の実装を教えてください。
π≒355/113 って知ってたか?
16デフォルトの名無しさん:02/06/29 08:45
age
垢グロ木をわかりやすく説明してくだちい
猪木ズムを教えてください。
>>17
ここに説明があるので読んでみてください
http://www.mmjp.or.jp/hujisyoudoku/gokiburi.htm
20デフォルトの名無しさん:02/06/29 11:44
1よニヤニヤするな。
>>11
>0.99999… = 1 って知ってたか?
0.99999… = 0.99999… * ( 10 - 1 )/ 9
    = ( 0.99999… * 10 - 0.99999… )/ 9
    = ( 9.99999… - 0.99999… )/ 9
    = 9 / 9
    = 1
[証明終]
>>21
それで本当に証明できてると思ってる?
>9.99999… - 0.99999…

がなんで 9 になんの?
24デフォルトの名無しさん:02/06/29 14:49
0.99999… = 1 なんて証明できないよ。
そういうもんだと思わないと無理。
そんなのを証明しようと思ったら、結局>>23が指摘したようになっちゃう。
25デフォルトの名無しさん:02/06/29 14:50
PhotoShopのエフェクトの、ラップってどうやってんの?
>>24
出来ないわけがない。0.9999・・・の定義さえちゃんとやれば。
>>25
そんなんあったっけか?
>>25
あった。

ラップ 光沢のあるプラスチックで画像をコーティングしたように見せ、表面のディテールを強調します。

白の画像に適応しても何らかの反応がある。なんだろうね。
0.99999… = 1 の証明?

x = 0.9999…
10x = 9.999…

10x - x = 9x = 9
x = 1

こんなんじゃ無かったか? 厨房か工房の時にやった記憶がある
いやだから0.9999999・・・と9.999999・・・がちょうど10倍になることを説明せんかゴルァ
>>28
ノイズ加えて微分しるんじゃないの?
見たこと無いからわからんけど。
10m先から走り出した亀に、アキレスは実際に追いつきました。
証明終わり。
33デフォルトの名無しさん:02/06/29 21:16
0.9999999…=1
この証明に関するスレ、数学板にあるよ。

1=0.9999999999999999999999999999・・・その2
http://science.2ch.net/test/read.cgi/math/1022253026/l50
1=0.9+0.1
1=0.99+0.01
1=0.999+0.001
1=0.999・・・9+0.000・・・1
1=0.9999・・・+0.0000・・・
などと書いてみるテスト。
>>34
じゃあlim xにしかならないのでは?まぁ、これは1か。
    x->1
36デフォルトの名無しさん:02/06/29 21:38
いやだからそれを無限大にやったら
0.9999999999999999999になるのか説明せんかゴルァ
0.99・・・÷3 = 0.3・・・ = 1÷3
38デフォルトの名無しさん:02/06/29 23:02
数学板の0.99…=1の話題で0.99…<1というレスを見つけました。
その人のレスを以前コピーしたので、それを載せておきます。


■ 以下、ある人のレス ■
1>0.999999…… の証明
◎証明
数直線上においてデデキントの切断公理が成立しているとする。
――――――A―――――→1――――――B――――――

今、数直線を1のところで切断し、1より左側(Aの部分)が右に開き、1より右側(Bの部分)が左に閉じているようにする。
0.999999999……はAの要素なので、適当な正の数kを選べば、
0.999999999…… +k<1とする事ができる。
よって 0.99999999……<0.99999999…… +k<1
よって0.99999999……<1

また、0.99999999…… は1の左隣の数ではない事が証明された。

「1の左隣の数」が定義できるとすると、矛盾が生ずる事を示す。
「1の左隣の数」をpとおくと、pはAの要素である。よって適当な正の数k’ を選べば、
p<p+k’<1 とできる。
つまり、pと1のあいだには更に数字が存在する事が証明される、という矛盾が生じている。
よって、「1の左隣の数」は定義できない事が証明された。
この問題に関してはデデキントの切断公理をどう扱うかで微妙な差が出てくると思うが、0.3333333……=1/3 よって、両辺を3倍して0.99999999……=1、と言うのは論外。
0.333333……=1/3 と言うのが証明されていないし、1=0.99999…… を証明する事と1/3=0.333333……を証明する事がほぼおなじである事に気付いていない時点で完全にDQN。

個人的には、数字の正確な位置というものを10進法や2進法で表現しようとする態度に問題ありと思われ。


1が必死にあげてるけど、1は何がしたいんだ?
>数直線上においてデデキントの切断公理が成立しているとする。

前提がさっぱりわからないのでそんな理論ちらつかされても困ります。
じゃあここいらで究極の証明を披露しよう。
1=0.9999を



googleで検索すると、反対意見もごく少数見られるが大部分、とくにここ
http://santaro.theory.cs.ritsumei.ac.jp/math/number01.html
なんかはデデキントを持ち出して1=0.9999と書いている。

よって、1=0.9999である。
42デフォルトの名無しさん:02/06/30 00:51
>>12
最近の電卓では、それが1になるんだよな。
賢くなったな。
俺の手元にあるものでは0.999…だけど。
そもそも 0.99999... がなんなのか、定義すらされていないという罠
>41
思いっきりタブーやっちゃってんじゃん。

>また右辺を10倍すると 0.9999……×10=9.9999……  であるから,

嘘つけ。
45 :02/06/30 01:15
1/3=0.333333......は単純に除算法則でしょ?
 __
3)1

 お腹が裂けるう……と夏子がギリギリと締めつける便意に苦悶の声をあげれば、真樹
子は反対に歓喜の声をあげる。
「あ、あうう……あん、ああん……」
「そんなにいいのか、真樹子。すっかり尻の穴で感じるようになったな、へへへ」
 冷二はゆっくりと指を抽送させた。
 真樹子のアヌスは、あいつぐ肛交のせいで夏子よりずっとひろがった感じで、とろけ
るような柔らかさを見せてヒクヒクとからみついてくる。
「とろかせやがって、へへへ。自分ばかり悦んでねえで、もっと締めつけるようにしね
えか」
「あ、あああ……冷二さん、もっと……あうッ、あうう……」
 まるで堰を切ったような真樹子の反応だった。こらえきれないよがり泣きの声がこぼ
れ、自分から高くもたげた双臀をゆする。
つーかさ、2ちゃんねるの住民の説明なんてみんな胡散臭いよ
まともな人がちゃんと説明している所ないの?
>>47
ウソをウソと見抜けない人は−>宝を宝だと見抜けない人は
つまり、

─ = 0.3333・・・

派とそうでない派があるということですね。
50デフォルトの名無しさん:02/06/30 01:38
現在のデフレは不況の原因ではなくむしろ結果。

デフレは不況を作っている一つの要素と言えなくもないが、たくさんあ
る要素の中の一つにすぎない。
不況の結果としてのデフレはよくないことだが、デフレのみを人為的、
作為的に調整しインフレにしたところで景気がよくなるものではない。
不況には他の要因が多く複雑に絡み合っているからだ。

今の状態で強引に人為的インフレを起こしたところで景気は回復せず、
不況とインフレの二重苦に苦しめられることになる。

喰らえィ! 『デフレ・スパイラル』ッッ!
>49

違う。
0.99999999×10=9.999999999派とそうでない派。
違う。
0.9999...==1 派と 0.9999...!=1 派 
1/3 = 0.3333・・・派なら両辺に3かければ1=0.9999・・・派になるってことだろ。
>>53
違う
「0.9999...==1 派」と「0.9999...==1 派となぜ言えるの」派
56デフォルトの名無しさん:02/07/13 22:20
age
57デフォルトの名無しさん:02/07/13 23:02
>1アルゴリズム体操はじめ!
58 :02/07/14 00:15
>>54
おまいは馬鹿だ(もしくは高校生以下)
俺は...否定派だ。
不毛な事に関してだと盛り上がるよね。
人間の性でしょうか?
61ポパイ:02/07/14 03:44
MSNメッセンジャーの会話中のバックの色とか文字色とか壁紙とか変えられる方法って
ありませんか??毎回同じようなやつで飽きちゃいました。
知ってる人教えてください。
>>61
どうして、このスレにそんなことを聞くのかと、
小一時間問い詰めたい
コロンブスのタマゴという話を知ってるか
知らん
コロンブス達はゆで卵を食べる時には
もっぱら大きい方からぱくりんと食べておりましたが
あめ〜りかの住民達は驚いたことに
小さいほうからちゅるりんと食べていて
あまりの驚きに脱糞してしまった
というお話です。
66デフォルトの名無しさん:02/08/17 07:33
AVL木とSKIP LIST 実際にはどっちが
性能が上なんでしょうか。
用途としては、ルーチングテーブルを想定。
67デフォルトの名無しさん:02/08/17 08:40
ソートでもっともよく使われるのって何?
>>67
バブルソートだろ。世界中のにわかプログラマが使ってる。

俺はマージソート使ってまふ。
バブルソートは普通おもいつくかな
選択ソートや挿入ソートは使っていたけど。
一番使われてるのはqsortのクイックソートじゃないのかな。
クイックソートって安定なソートじゃなかったんじゃない?
俺は不安だから安定なソート使ってる…。
>>70
微妙にワラタ!

...マジレスじゃないよね?(急に不安になった)
72デフォルトの名無しさん:02/08/17 11:02
アルゴリズムとデータ構造の専門家ってすごいな。
それでこそプログラマーとして一人前だな。
>>71
もしかして、安定・不安定なソートを知らない?
>>73
安定・不安定は必要に応じて使い分けはしても
不安だから安定なものを使うということはない
ことから70はネタだろうってことだと思う。
あ、そういう意味か。
不安定ソートって使ったらなんか欠点でもあんの?値は同じなんだから
別にどーでもいいような気がするんだけど。
>>75
ソートしたことあんの?
いや、あるけどライブラリのソート使っちゃう。
一応、メジャーどころは全部書けるけど、ライブラリとかに入ってるソートアルゴリズムって
なんか工夫を凝らしてるから自分で書くよりパフォーマンスいいし。
>>70は安定・不安定の意味を誤解してそう
>>77
そうじゃなくて、76が言いたいのは、メーラーなんかで
ソートしたことがないのか?ということだろ。
例えば差出人順に並べて、同じ差出人では時間順に並べたい
というような場合があるだろ。
80デフォルトの名無しさん:02/08/17 14:12
以下の言語を認識する標準型のちゅーりんぐ機械を設計せよ。
ただし、できるだけ高速に動作すること。
{0^n1^m|n<m}.
81デフォルトの名無しさん:02/08/18 11:17
>>79 そういう場合は 比較関数で差出人が一致したら時間の大小比較値を返せばいいんでは?
   それも一致したら順番なんてどうでもいいでしょ
>>80
課題丸投げするな!
宿題スレ逝け
83デフォルトの名無しさん:02/08/18 12:31
1/3=0.3333...
に3をかけた0.9999...
と、


Σ 9 * 10^(-x)
n=1
の0.9999...

は別物のような気が。
0.9999...==1 派はどっちも同じだと考えてるの?
>>83

Σ 3 * 10^(-x) ==0.333333333333333・・・
n=1
なら同じだし ≠なら違うわけで、それは定義でしょう
みんな、良く聞いてくれ。
>1が欲しがってた質問は「バブルソートってなんですか?」という技術とは離れた概念的な話だ。
先生は・・・>1がこんなことをしてしまったことが残念でしょうがない。




でもな、みんな・・・こんな>1だからこそ・・・

















ワソーイ   ∧_∧     >>1      ∧_∧  
      (, ゚∀゚,∩     ↓     (゚∀゚∩)  アーーーーヒャヒャヒャヒャ
      (つ   ノ   ガクプル   ⊂    ;;;)
  ∧_∧  ( ノ  (((( ;゚Д゚)))    ヽ∧_∧
  (;;;;  ´∩ (_)   ノ( へ)ヽ    (;;;    )∩
  ノ;;;;   ノ       <       ⊂;;;;;      ノ
 ○   ノ                  ヽ  ○ )
  )\ ヽ  ∧_∧     ∧_∧  ノ  ノ(⌒)
  (____(____) (;;;;;;;;;;  )    (   ;;;;;;;)(_____)  ̄
       ⊂ ;;;;   )     ノ   ;;;;;;つ     モーヒョヒョヒョ
        (  ○ )     (○  (
        (  (  (    (⌒)ヽ  )
        (____)___)     ̄  (____)


こんな>1だからこそ、宴の楽しみ甲斐があるってもんだ!
86デフォルトの名無しさん:02/08/18 15:51
>アルゴリズムとデータ構造の専門家ってすごいな。
>それでこそプログラマーとして一人前だな。
そんな人いません。
アルゴリズムの本書いてる人は、
コンパイラ関係と数学の人(クヌース、ビルト、エイホ、ウルマン他)。
87[天才] vuela嬢 [女神]:02/08/18 15:58
お前らアフォは、黙って俺様のいう通りに動いてりゃいいんだよ、ヴァカ
オノレでアルゴリズムやデータ構造なんか考えようとするな。ヴォケ。
時間の無駄なんじゃ。一辺死んでこい。ヴァカ。
88デフォルトの名無しさん:02/08/18 16:19
>>87
では、いままでにない斬新で、エレガントで、実用的なアルゴリズムを教えてください。
89デフォルトの名無しさん:02/08/18 16:25
0 LOCATE 13,12:PRINT "オレサマハ テンサイダ!!":RUN

WIDTH 40,25:CLS:RUN

どうかね?
90デフォルトの名無しさん:02/08/18 16:32
0 LOCATE 36,12:PRINT TIME$:IF TIME$="04:40:00" THEN BEEP 1:RUN
WIDTH 80,25:BEEP 0:RUN

完璧な目覚まし時計だNe!
91デフォルトの名無しさん:02/08/18 16:40
0 A$="俺様は天才だ ":WHILE 1:A$=RIGHT$(A$,LEN(A$)-2)+LEFT$(A$,2):LOCATE 33,12:PRINT A$:WEND
CLS:RUN
電光掲示板風表示、どうかね?

92デフォルトの名無しさん:02/08/18 16:51
0 PSET(RND(1)*639,RND(1)*399),RND(1)*7:RUN

STARDUST 幻想的だね
93デフォルトの名無しさん:02/08/18 16:54
94[女神] vuela嬢 [天才] :02/08/18 16:54
>>89-92
どうじゃ、実に斬新で、エレガントで、実用的なアルゴリズムだとは
おもわないかね。ちみたち
95デフォルトの名無しさん:02/08/18 17:10
>>[女神] vuela嬢 [天才]
(プププッ
>>94
目からウンコが落ちますた。
97デフォルトの名無しさん:02/08/18 17:31
アルゴリズム辞典とかって入力データは全てただしいっていう前提だけど
それって現場じゃ困るよね。
かといって、入力データひとつひとつを検査してもそれらが
正しいか間違っているかの判断が ある程度の塊にならないと
わからない判断できないような状況での エラールートと正常ルートとが
混在してるようなのって本だとわからないというか
経験って大事だね
>>97
紙面の都合で、って奴じゃない?一度本とか論文とか書いてみると分かるよ。
入力データのチェックなんてしてたら決まりの枚数に収まらんから。
アルゴ辞典なんて読む奴は問題の切り分けぐらいできるっしょ。サンプルコード
見れば何をどうすればいいか分かる奴が読む物。
逆にコピーペするような奴は何読んでも無駄だし。けして本が悪いわけではない。
99デフォルトの名無しさん:02/08/18 17:36
>>97
そのことを本にしてくださいm(__)m
10097:02/08/18 17:41
>>99
おれもそのことを系統立てて書いた本がほしいの。
ていうか、こういうアルゴリズム辞典に載ってない
ことを話合えるスレがほしいよな。 立てるか・・・
>>85
>>1より>>70のほうが面白い。
不安だから安定ソートだって。
>>81
論点が全然分かってないね君は。
>>70といい、>>81といい、うちの職場の奴といい(w
こんな基本もわからないやつが多いとは嘆かわしい。
まぁ夏休みだしな。
10581:02/08/19 11:23
>>102 判ってるよ
 言いたいのは、エクスプローラのような表示で、たぶんグリッド状の上のタブをクリックした
  時に、先に 名前でソートした時にどうなるかって事だろ?
   常に名前でソートした時には同名なら時間順にしたいなら、>>81の通り
   前回の並びにしたいなら比較関数で差出人が一致したら前回の並び順の大小比較値を返せばいい

 こういう場合、実際にソートするんじゃなくて、インデックスを付け替えるだけなんだから
  別に安定なソートを持ち出す必要もないという事さ
>>105
全然違う…
分かってるつもりになって得意気に語りだす>>81をみんなで憐れむスレはここですか?
>>107
そっとしといてやれよ…。
109107:02/08/19 23:12
ごめん、そうするよ。
110デフォルトの名無しさん:02/08/20 02:31
テンプレートって何?
>>110
あちこちで聞いてるね
逝ってよし
>>65
コロンブスじゃなくてガリバーだYO!
食べ方じゃなくて割り方だYO!

とひっそりとつっこめる裏技。
>>112
コロンブスの卵と、ハンプティダンプティが混じってないか?
>>113
コロンブスとガリバーとハンプティダンプティは全部別の話だYO。
ハンプティダンプティは、鶏から卵が生まれたのか、卵から鶏が孵ったのかってやつだろ?
115デフォルトの名無しさん:02/08/22 20:21
生物学的には卵が先ですね
ハンプティダンプティって、マザーグースのお話(童謡)のなぞなぞ唄だよ。
「われちゃったら元に戻せないものなーに」って感じの。
117116:02/08/22 22:32
コロンブスの卵は、机の上にどうやったら卵を立てられるか、という問いに、
卵をつぶして立てればいいという、発想の転換(無茶な発想?)をした話。

ガリバーの卵の話が、リトル&ビッグエンディアンの由来で、
大きい方から食べるか、小さい方から食べるかで、戦争を起こした小人の国の話が元になっている。
コロンプスの卵の話を聴いて素直に感心するのは文系
割れた卵を卵と言って良いかどうか疑問を持つのが理系
その後片付けたのは誰だろう, と思った俺は何系ですか?
>>119
メイド系
121デフォルトの名無しさん:02/09/05 10:58
メイドかよ!
>>116

  マジレスキボンヌ
卵とかOKなら皿とかもOKなんでは?っていうか,大抵のモノは割れたら元に戻らないだろ。
なんか気の利いた答えでもあるんじゃないかなぁ。
Humpty Dumpty sat on a wall,

Humpty Dumpty had a great fall.

All the King's horses, and all the King's men,

Couldn't put Humpty together again.
125デフォルトの名無しさん:02/09/07 18:13
「非可解な問題」を教えてください。
問題の名前だけでいいのでよろしくお願いします。
126デフォルトの名無しさん:02/09/09 15:27
>>125
「非可解」という単語は見慣れないのでgoogleしてみたら、結構出てきましたが、
使う人によって、微妙に意味が違うようです。
お望みの問題がどういう意味か判りませんので、3種類あげてみました。

1.解が存在しない(決められない)問題。いわゆる決定不能問題
  「チューリングマシンの停止問題」
2.解は存在するが、解法がない。
  「5次方程式の代数的解法」(「ガロワ理論」をキーワードに)
3.解法はあるが、現実的な時間内では計算不能。
  「巡回セールスマン問題」(「NP完全」がキーワード)
127コロンブス:02/09/09 18:41
水平なテーブルなら、卵は割らなくても大抵立つよ。
卵の殻の表面にある小さな凹凸は、じつは三点倒立に十分な大きさを持っている。
手が震えなければ誰でも立てられるんだな、これが。
卵を立てるのが難しい人は、塩を使うといいよ。
盛り塩をして、その上に卵を立てる。
後は死をを吹き飛ばせば、はいできあがり。
>>128
ネタだって分かってても試してみたくなったじゃねーか、ゴルァ!!
>>129
ネタじゃないと思う、昔教育チャンネルで見た気がする
131129:02/09/10 00:31
>>130
マ、マジデ? オ、オニイサン信ジチャウヨ? イイノ?イイノ?
>>129=130
卵の殻の表面につく小さな塩の粒粒は、じつは三点倒立に十分な量となっている。
129=131だたね。ごめん。
>>125
「不可解な問題」なら質問スレに山ほど。
135デフォルトの名無しさん:02/10/10 12:00
この問題のプログラム教えてください。(挿入ソートの問題)
ファイルにデータの個数nと,その個数分のデータ(整数データ)を保存する.
プログラムinsert.cは,まずファイルからnを読み込み,その数だけデータを読み込み,挿入ソートを実行する.そして最後にソート結果を表示する
136デフォルトの名無しさん:02/10/10 14:45
 99999以下とは限らない正の整数を次々と読み、データの個数と最小値、
2番めに小さい値および3番目に小さい値を印字するプログラムを作れ。ただし、
データがつきたことをあらわすために、0または負の数を入力することにする。

このアルゴリズムのを書いてください。流れ図でも箇条書きでもよいです。書き
方がさっぱりです。


(始め)
 |
(136が考える)
 |
(136が書く)
 |
(136が提出する)
 |
(終わり)
138デフォルトの名無しさん:02/10/10 14:53
>>126
リドルストーリー(ストックトンの「女か虎か」等)の結末を推理せよ、
というのは、非可解問題の範疇に入りますか?

>>128
子供の頃、実際にやったことがあり、うまくいきました。
でも、塩を吹き飛ばしたら、支えを失って転倒するのでは?
(ちなみに、塩を使わなくても、勃てることも可能らしい)
>>136
1〜3番目に小さい数を入れる変数(変数1〜3)と
データ数を入れる変数を用意しといて、

データをいっこよむ→0か負の数だったら終了(データの数と変数1〜3を出力)

データの数を入れとく変数を+1

変数1の数字と比較してそれより小さかったら
 変数3←変数2
 変数2←変数1
 変数1←読んだデータ
 最初へ

変数2の数字と比較してそれより小さかったら
 変数3←変数2
 変数2←読んだデータ
 最初へ

変数1の数字と比較してそれより小さかったら
 変数3←読んだデータ

最初へ
>>138
ほんの2〜3粒のこっていれば十分。
逆にいえば2粒程度の塩を使って卵を立てることが出来る。
141デフォルトの名無しさん:02/10/13 09:46
>>140
可能か不可能か、と聞かれれば、「可能」と答えるしかありませんが。
常人のスキルでは、長時間掛かりそうな予感・・・。
>>141
ん? 今やってみたが、10回中9回できた。
こつは塩を盛りすぎないことかな(卵が机に接触している方が成功しやすい)

欠点は、塩が散らかることさ。外でやればよかったよ・・・
143デフォルトの名無しさん:02/10/13 20:57
>>142
本当に検証する人がいるとは思わなかった。(笑)
(気を悪くされたらスマソ)
確かめずにおれないのは技術者の性ですかね。
いや、とても大事なことなんですが。
144 :02/10/14 14:09
>>139
ありがとう!!
145 :02/10/14 14:10
あげちゃったスマソ
146デフォルトの名無しさん:02/10/19 12:18
昔、ソートとかB木に関するスレがあった気がするけど、
場所知ってる人いませんか?
MIDIシーケンサー誰か作れる?
http://pc3.2ch.net/test/read.cgi/tech/1005053427/

かな
148名無しのジョー:02/10/19 13:44
積分の数値計算でシンプソン則ってありますよね。その原理を示しているサイトってありますか?

>>148 そのまま検索したらでると思うが?

http://www.google.co.jp/search?q=シンプソン 積分 原理
150146:02/10/19 17:26
>>146
よろしくお願いします。
>>150
ぐぐってでてきたページだけじゃだめ?
書籍紹介して欲しいのか、アルゴリズムそのものを教えて欲しいのか、何をお望み?
ーーーーーーー
153デフォルトの名無しさん:02/11/01 20:00
ソートの種類ってたくさんありますが、最低覚えておきべきソートはどれでしょうか?
くいっくそーと
155デフォルトの名無しさん:02/11/01 20:11
質問が2つあります。
1.お勧めの数学関数のヘッダーがあれば教えてください。
math.hにはnCm (組み合わせ)が入ってませんでした。
nCm=n!m!/(n-m)!
自分で作っていたのですが…階乗の関数を作るとintの範囲を超えてしまうので…
2.いいアルゴリズムはないでしょうか?
int k:=1;
for( i = n-m +1; i<=n ; i++) k*=i;
for( i = 2 ; i<=m ; i++) k*=i;

ではダメかな
157デフォルトの名無しさん:02/11/01 20:41
nCm=n!/m!(n-m)!
int k=1;
for( i = n-m +1; i<=n ; i++) k*=i;
for( i = 2 ; i<=m ; i++) k/=i;
158156:02/11/01 20:51
ああ、式が間違ってたんだね

すると、こうか
int k=1;
int mm=2;

for( i = n-m +1; i<=n ; i++) {
if( mm <m) if( (k % mm) == 0 ) { k/mm; mm++;}
k*=i;
}
for( ; mm<=m ; i++) k/=mm;
159デフォルトの名無しさん:02/11/01 21:54
>>158
すげー、みつかった時点で分母の数字を約分していくのですね。
ありがとうございました。
160155:02/11/01 22:16
int nCm(int n,int m){
int i;
int k=1;
int bunnsi=2;

for( i = n-m +1; i<=n ; i++) {
if( bunnsi <m){
if( (k % bunnsi) == 0 ) {
k/=bunnsi;
bunnsi++;
}
}
k*=i;
}
for( ; bunnsi<=m ; bunnsi++){
k/=bunnsi;
}
printf("k=%ld\n",k);
return k;
}

このプログラムで28C14まで計算することができました。
intの範囲内を超えてしまうのでこれ以上は無理のようでした。
161デフォルトの名無しさん:02/11/01 22:31
for( i = n-m +1; i<=n ; i++) {
while ( mm <m && (k % mm) == 0) k /= mm++;
if (mm<m && (i % mm) == 0) k*=i/mm++;
else k*=i;
}
for( ; mm<=m ; i++) k/=mm;
>>160
じゃあ配列作って、そこに順に数入れて割っていったらどう?
int dt[100];
int kk=0;
int nn=1;
for( i = n-m +1; i<=n ; i++) dt[kk++]=i;


for( i = m ; i>1 ; i--) {
 for( j = kk ; j>=0 ; j--) {
  if (dt[j] % i)=0 then dt[j]/=i; goto skp;
 }
puts("必ず割れるはずだからここは通らない筈;");
skp:;
}

 for( j = kk ; j>=0 ; j--) nn*=dt[i];
163デフォルトの名無しさん:02/11/01 22:40
テトリスつくってるんですが、ブロックが止まる時の判定ってどんな感じにすればいいんでしょうか?
int nCr(int n, int r)
{
int k, x = 1;
for (k = 1; k <= r; k++)
x = (x * (n - k + 1)) / k;
return x;
}

29Crまでいける
165デフォルトの名無しさん:02/11/01 22:49
>>164
それ正しい値返す?
166正規の参考値:02/11/01 23:47
29C17=51895935
29C15=77558760
29C13=67863915
souka int ka ...
sarashi age
int comb(int n, int r)
{
 if (r == 0 || n == r)
  return 1;
 else
  return comb(n - 1, r - 1) + comb(n - 1, r);
}
int nCr(int n, int r)
{
int i, j, tmp[30];

 tmp[0] = 1;
 for (i = 1; i < n; i++) {
  tmp[i] = 1;
  for (j = i; j > 0; j--) {
   tmp[j] += tmp[j - 1];
  }
 }
 return tmp[r];
}
171デフォルトの名無しさん:02/11/02 14:14
>>170
やってみると動くけど、なぜなのか理解できません。
せつめいきぼんぬ。
>>171
パスカルの三角形を計算しているだけ。
配列を増やせば33C16まであふれずに計算できるよ。
intで足りますか?
>>173
intが32ビットのとき、33Crまで計算できる。
64ビット符号なし整数を使えば67Crまで計算できる。
ビット数と大差ないね、その値。
わかりやすや。ちょっとビックリ。
コンビネーションね。
uint64_t comb(int n, int r)
{
static uint64_t tmp[100][100];

if (tmp[n][r]) {
return tmp[n][r];
} else if (r == 0 || n == r) {
return tmp[n][r] = 1;
} else {
return tmp[n][r] = comb(n - 1, r - 1) + comb(n - 1, r);
}
}
>>163
落下中のブロックの全部に対して、
その1マス下に別のブロックがあるかどうか調べたら?
178デフォルトの名無しさん:02/11/03 23:29
最強!
double c_i(int a,int b){
int pp;
double c=1.0;
for(pp=1;pp<=b;pp++){
c=c*(a-pp+1);
c=c/pp;
}
return c;
}
179デフォルトの名無しさん:02/11/04 00:03
ちょいと質問ですが
void xxx(void)
{
const int i = 1;
int j;

j = i;
}
これって最適化されると
void xxx(void)
{
int j;

j = 1;
}
になります?
void xxx(void)
{
}
181デフォルトの名無しさん:02/11/04 00:11
最速のソートアルゴリズムってどんなん?
quick_sort?
元のデータの分布の違いによる。
183デフォルトの名無しさん:02/11/04 00:22
分布を減らすための関数とかいろいろ研究されてた気がする。
値を素数で割るとか…
ハッシュ値とかそういったやつかな?
185デフォルトの名無しさん:02/11/04 00:29
ビンソートが最強です。
186第3者だが:02/11/04 00:34
ビンソートってなんでしょう?
どのようなもの?
リンクとかあります?
本の紹介でも良いですが。
>>186
とりあえず自分で検索してみれば?
188デフォルトの名無しさん:02/11/04 01:44
>>184
そうだハッシュ法だ。
>>186
一冊ぐらいアルゴリズムの本読め
190デフォルトの名無しさん:02/11/04 11:47
さらに最強!
unsigned double c_i(int a,int b){
 int pp;
 double c=1.0;
 for(pp=1;pp<=b;pp++){
  c=c*(a-pp+1);
  c=c/pp;
 }
 return c;
}
>>186氏は、本屋もなく、イソターネシトにも接続できない僻地の住人です。
哀れんでやってください。

・・・の割には、2ちゃんねるには書き込めるのが不思議だが?(w
>>190
なんのプログラム?
Combination?
どこが最強なんだ?
>>194
ネタに決まってるだろ。なんだよunsigned doubleって。
まあまあ、ここは熱いソートをおひとつ、ぐぐーっと

#include <stdlib.h>
typedef int cmp_t(const void*, const void*);
static int coin(const void *x, const void *y){return rand()-RAND_MAX/2;}
static void shuffle(void *b, size_t n, size_t s){qsort(b, n, s, coin);}
static int orderedp(void *b, size_t n, size_t s, cmp_t *c) {
char *p, *q; if (n < 2) return 1; q = (char *)b;
while(n-- > 1) { p = q; q = p + s; if (c(p, q) >= 0) return 0; } return 1; }

int
bsort(void *b, size_t n, size_t s, cmp_t *c)
{
int i = 0;
while(!orderedp(b, n, s, c)) {shuffle(b, n, s); i++;}
return i;
}
ランダムソートか。熱いか?
CPUがボゴっと熱いな
1/3*3=1 って知ってたか?
ソートに関する安定と不安定ってどういう事?
安定って同順位のものの順序関係が保たれるって書いてあったけど、
その順序関係って時間的なもの?
先に入力されたほうが、同順位の中でも前にくる、とか?
>>200
同順位のデータについては
もとのデータの並びが維持されることを
安定なソートという。
>>201
違いはそこだけ?
そう。
あとさソートの呼び方がわかんない。
セレクトソートって単純選択法?
インサートソートは単純挿入法?
オレ英語で覚えちゃったから日本ごと対応わからんのだが。
意味はわかっても、単純とかつけたりすのがさー。
対応きぼんぬ。
コピペ用
セレクトソート →
バブルソート →
インサートソート →
シェルソート →
クイックソート →
クイックセレクト →
レイジセレクト →
ファーストセレクト →
マージソート →
ヒープソート →
インデックスソート →
カウントソート →
ラディックスソート →
レイジラディックスソート →
>意味はわかっても、単純とかつけたりすのがさー。別に単純つけなくても良いと思うが。
>セレクトソート→
それをいうならセレクションソートだろ。選択法
>バブルソート→
泡立ち法とも言うが、バブルソートで定着してる。
>インサートソート→
挿入法
>クイックセレクト→
なんじゃそら? クイックソートで、狭いときに選択法と組み合わせることか?
いちいちクイックソートと分けないと思う。
>レイジセレクト→
レイジってlasyか? 意味不明。
>ファーストセレクト→
???
>インデックスソート→
ハァ? そりゃアルゴリズムの名前じゃなくてソートの使い方だろ。
>カウントソート→
頻度数えソートのことか?
>レイジラディックスソート→
聞いたことない。
>オレ英語で覚えちゃったから日本ごと対応わからんのだが。
フーン…(嘘つけ)
クイックセレクトは k 番目の要素を線型時間(O(n))で見つける、ってやつだね
数学的には厳密だけど、定数部分が大きくてあまり実用的ではない
それを、数学的な厳密さを犠牲にして(だいたい線型時間)実用的にしたのが
レイジー(lazy)セレクトだね。
ファーストセレクトは知らない。
>>204
http://www41.tok2.com/home/friendly/language/a1.htm
ここからコピペしたんだろ。
あと、ラディックスソートは基数ソートともいうね
ねぇねぇバケットソートとビンソートって
名前が違うだけで同じもの?
それとも全然違うアルゴリズム?
まちがってるかも。

セレクションソート → 選択整列法
バブルソート → 逆順訂正整列法、単純交換整列法
インサートソート → 挿入整列法
シェルソート → 改良交換整列法(シェーカーソートのことだっけ?)
クイックソート → ???
マージソート → 併合整列法
ヒープソート → ???
インデックスソート、カウントソート → 分配計数整列法、数え上げ整列法
ラディックスソート → 基数交換整列法と直接基数整列法の2種類を指す?
良スレの予感
1/3*3=1 って知ってたか?
213デフォルトの名無しさん:02/11/24 18:41
>>212
そのネタふるい
214デフォルトの名無しさん:02/11/24 22:18
バブルソートって使うときあるんですか?
常に使う
216デフォルトの名無しさん:02/11/24 22:24
>>215
そうなんですか?
でもクイックなんかの方がいいじゃないですか?
>>216
何がいいのか説明できるなら、いい方を使えばよい。
>>216
要素数が20とかそれくらい少ない場合は単純なソーティング法の方が速い。
クイックソートでも、分割していって、要素数がある程度少なくなったら
バブルソートとかそこらへんの単純な方法でソーティングする方が速くなる。
219デフォルトの名無しさん:02/11/24 22:33
>>218
バブルソートは使わんだろ。
>>219
何使う?シェルソートかな?
221219:02/11/24 22:42
>>220
シェルも使わない。シェルもある程度以上の要素数があって初めて効果的だから。
残るは選択ソートと挿入ソートだけど、どちらも簡単にかけるので性能がいい挿入ソートを使っている。。
挿入ソート
223219:02/11/24 22:45
>>222
なぜ書き込み時間が・・・・
>>221
thx。調べてみたら最近のqsortの実装もほとんどクイックソートと挿入ソートの組み合わせ
って書いてあった。
挿入ソートってArrayに対しては遅いと思ってた。
>>223
時間でソートしておいて
226ああ:02/11/26 07:35
ちょっとスレの趣旨とずれていて恐縮なんですが、
今私は数学系の学部に在籍しておりまして、研究上アルゴリズムや素因数分解
等をコンピュータ上で行わなければならない必要性が出てきました。
時間の関係上、手っ取り早くそのような計算が自在にできるようになりたいのですが、
当方、残念ながらコンピュータはネットする程度でプログラムやC言語、UNIX等の知識は
限りなく0に近いです。。何からはじめればよろしいでしょうか??
227ああ:02/11/26 07:36
さげちゃったんで、age!
2281:02/11/26 07:53
理論系でcomputerを使う研究をするやつは負け組.
コンパイラー用意する。
パソコン書籍のところに行って、C言語と書かれたものを立ち読み
わかりやすそうだと思ったら購入。
わからなくても、例題の多いやつ買ってとことん入力実行。
ブルーバックスについていたっけそう言えば?どんなものか知らんが。
mathmatica
231ああ:02/11/26 08:25
>>228
理論系はポスドクで大学に残れる奴はわずかでそれ以外の多数は
人生の負け組になっちゃうのよ。悲しいかなこれが現実。

>>229
とりあいず、C言語からやってみます。++とかじゃなくて良いのでしょうか?

>>230
mathmaticaとか、一つのソフトだけではあまり細かいことができなくて
融通がきかないかなと思って。
232デフォルトの名無しさん:02/11/26 09:36
2つの線分同士の距離の求め方教えてくれんか?
線分S1(点p0,p1)とS2(p2,p3)があったら、
p0とS2、p1とS2、p2とs1、p3とs1の距離をそれぞれ計算して
一番短いのが線分どうしの距離だと思うんだが,もっと高速な
方法ってないんかな?
答えになるかどうか知らんが参考になりそうなリンク貼っとく。
ttp://www.infoeddy.ne.jp/~tensyo/prog/linealgo.htm
234デフォルトの名無しさん:02/11/26 13:13
スタックは、アルゴリズム、データ構造のどっち?
どっちかというとデータ構造。
スタックを使って計算はするけどスタック自体で計算はしない。
236デフォルトの名無しさん:02/11/26 18:50
>>1
うにーくアルゴリズムはどうすればええですか?
>>235
じゃあどんなのがアルゴリズムなんですか?
>>237
TCP/IPスタックとか。
なんでTCP/IPスタックがアルゴリズムなんだよ。
スタックもアルゴリズムですが。
(゚Д゚)ハァ?首でも津ってろ
242デフォルトの名無しさん:02/11/26 19:28
漏れ的イメージではスタックというとデータ構造。
LIFOというとアルゴリズム。
無知な厨房は知らんだろうが、
ちゃんと教育を受けたプログラマなら
スタックアルゴリズムと言うアルゴリズムがちゃんとある
ことを知っている。

メモリ管理で出てくる。
TCP/IPというとNagleのアルゴリズムとか。
245デフォルトの名無しさん:02/11/26 20:02
やっぱりアルゴリズムの勉強は大学へ逝ったほうが良いですか?
2461:02/11/26 20:07
>231
そうか.それは悲しいな.
>>245
大学行かなくてもアルゴリズム辞典でも読んでればおっけー。
アルゴリズム辞典にスタックアルゴリズム載ってますか?
載ってます。
アルゴリズム大学
>>246
>>236
おながいしますm(_ _)m
>>231
最初はCでいい。
構造化プログラミングを意識してやっていれば良いよ。
まぁ、少しオブジェクトと言う言葉も意識しながらかな。
253よそで無視された。教えて:02/11/27 01:07
宿題でRDB作ってんだけど
ファイル保存形式について
なんか参考になるサイトない?
今はいったん全部メモリーに読み込んでるので
ロード&セーブの時間が現実的でない
>>253
RDBの前に知らなきゃいけないことがいっぱいありそうだね。
>>253
マルチうざい。
ちゃんと答えてもらっただろ。
>>253
Bツリーかハッシュ使え。
257よそで無視された。教えて:02/11/27 01:25
>>255
あっちじゃ無理だ

>>256
それ保存形式じゃないよ
>>257
ハッシュはともかく、Bツリーは保存形式だが?
ハッシュはインデックスで使うけど、微妙に保存形式とは違うかもな
>>257
じゃあ、お前の言う保存形式ってなんだ?
まさかVSAMとかISAMとか言い出すんじゃないだろうな?

他のスレでリンク張ってもらってたじゃないか。
260よそで無視された。教えて:02/11/27 01:31
>>258
じゃファイルフォーマットって言い直す。
ファイル上に赤黒木(?)をつくるのかい?
↓「すれ立てるまでもない質問」スレで教えてもらったページ見たのか?
ttp://www.cs.u-gakugei.ac.jp/~miyadera/LECTURE/algo2/5.html
red-black treeなんて知ってるくせにB木やハッシュファイル知らないって
面白いな。
263よそで無視された。教えて:02/11/27 01:36
>>261
そんなレスあったのか。
見てきます。もうしわけない。
264よそで無視された。教えて:02/11/27 01:41
見てきた。
でも更新されてレコード長が変わったり
インサート、デリート繰り返すと
虫食いだらけになっちゃうな。
どんな格納形式がおすすめ?
>>264
???RDBだろ?
だったらレコード長は固定にできるだろ?
そしたら、デリートされて空いた場所を
次にインサートされたレコードで使えばよいだろ?
266よそで無視された。教えて:02/11/27 01:50
>>262
Bツリーもハッシュも知ってまっせ。
でも赤黒木が一番はやいんじゃないの?

>>264
なんで?varcharとかあるじゃん。
固定にするの?varchar(256)は256で固定。
もっとスマートなのがいいですが。
結局OSのファイルシステムみたいのつくんないと駄目なのかい?
>でも赤黒木が一番はやいんじゃないの?
メモリ上ならな
>>253
>>254なわけだが
>>266
ファイルに置くときは、I/O回数が少ないことが性能的に非常に重要。
赤黒木だと書き換え回数が多すぎるし、アンバランスになる確率が高い。
B木のノードを4KBとか16KBにすれば数百とかに枝分かれするから、
I/O回数は非常に少ない。また、完全にバランスしている。

varcharを詰めて置く事もできるが、
・フィールド値へのアクセスが遅くなる。
・空き領域管理が極端に面倒になる。
のでお勧めしない。普通は固定長領域を取る。
text型だと固定長にはしないが、キーには使えないのが普通。
270よそで無視された。教えて:02/11/27 02:18
>>269
なるほど。メモリんときとファイルでは方法を変えないとだめか。
ためになりますた。
varcharは固定長で実装されてんのか。なら楽だ。
text型はあとで考えます。
>>270 varcharは固定長で実装されてんのか。なら楽だ。

調べず(検証せず)に鵜呑みにしちゃっているわけだが。
そんなんで良いのか?
>>271
デムパ登場
273よそで無視された。教えて:02/11/27 02:38
>>271
ほんとは可変長レコードでも更新が速いのがいい。
いいの知らない?
>>273
商用RDBだとCHAR, VARCHARは固定長領域だよ。
空白で埋めるか、長さ情報を持つかだけの違い。

どこまで本気で作るの?
トランザクション処理とか
並列性制御とかもやるの?
>>273
そういうことではなく、言われたまま鵜呑みにして
自分で検証せずにいても良いのか?って事だ。
またこの先分からないことが出てきたら人に聞いてそのまま実装するのか?
>>275
2ちゃんでものを尋ねる厨房に何を求める
説教ヲヤジよ?(w
277よそで無視された。教えて:02/11/27 02:54
>>274
ユーザ、トランザクション、バックアップ、トリガーなど全部省略です。
SQL文で答えが返るまで、です。

>>275
おっしゃることはもっともなんすが
varcharって固定長くさいなーとは思ってたんでついつい。

>>276
で、君は何しにきてるの?友達さがし?
固定長だよ。少し考えれば分る。
じゃなきゃ、なんで最大長を宣言する必要がある?
varcharはSQL ServerもOracleもPostgreSQLも制限つき可変長ですが何か?
>>279
制限つき可変長ってどういう意味ですか?
領域の大きさが変わるんですか?
>>280
領域は固定長。
その中で、実際のデータの長さを持っている。
>>274でガイシュツ
2000バイトだっけ?
4000バイト?


気持ちよく2Gバイトぐらい入れさせろ!
正直、>>253 には
> 宿題でRDB作ってんだけど
無理。
そんなんでRの部分やDBの部分を作れるのだろうか?
赤黒木の削除ってどうするんだろう?
>>281
完全な可変長にすると外部フラグメンテーションが起きるので
領域の詰め合わせが必要になったりしてやっかいだが、
8文字とか16文字単位で可変長にすれば詰め合わせの必要はない。

Oracleのvarchar2はそうやってリスト構造で表している。
287デフォルトの名無しさん:02/11/27 21:03
>>269の”B木のノードを4KBとか16KB”
ってどいう意味?ノード構造体が4K?ちがうな...
つっこまれるの覚悟で聞くけど、赤黒木ってなに?
>>288
おまえ あかくろき も しらん の かよ。
>>287
ノード構造体っていうか…

メモリ上で、キーの大きさがコンパイル時に分かっている場合と違って、
B木の1つのノードは、4KBとか16KBとかのブロックで管理して、
その中にキーとポインタの対を入るだけ詰め込むわけだ。
キーの長さによって、ブロック内にいくつのキーが入るかは変ってくる。

>>288
http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html
Windowsの
CreateWindow APIの
アルゴリズム(どうやってWindowを作成しているのか)
を教えて下さい。
>>291
どうやってとは?
ウインドウシステム全体の作りを解説しろと?
CreateWindow API
の範囲だけでいいです。
ソースということではなく、
アルゴリズムです。
>>293
はぁ?
Xでもかまいません。
ウィンドウの生成される仕組みが
知りたいです。
ウィンドウの実体はは画像データなのですか?
>>295
そうだよ、画像だよ
領域だろ
>>296-297
画像や領域(rect)だけではウィンドウに
ならないだろ。
292が言っているウインドウが分からないことには答えようがないだろ
実際に目に見えている物か
プログラムからいじることの出来るオブジェクトの事か
その両方か
どれもデータ構造は公開されてないしアルゴリズムって物でもないから
スレ違いなわけだが
メッセージをlisten
させるのも必要だろ
>実際に目に見えている物か
>プログラムからいじることの出来るオブジェクトの事か
ハァ?
XならオープソだからDLしてみ?
XFreeはGPLじゃないのか?
まずは、ウィンドウの定義と
いうか機能を洗い出して見れ。
>>299
>アルゴリズムって物でもないから
漏れはアルゴリズムのかたまり
だと思うが
>>293
> CreateWindow API
>  の範囲だけ
解説するってのは無理だ。

日本語を理解せずに1つの俳句だけ理解するのと
同じくらい無理だ。
>>306
画像にメッセージを
listenさせればウィンドウ
はできますか?
>>307
どうでしょう?
メッセージをlistenする画像は見たことないので
なんとも…
>>291
宿題は宿題スレへ。
普通こんな宿題でないだろ。
アルゴリズムというと特定の種類の計算を行なうための方法を指す言葉だよね。
日本語でいうと算法。基礎理論っぽい。

Windowを作成する処理っていうと、基礎じゃなくて応用だし、様々なアルゴリズムを
どう組み合わせて使うか、というどちらかといえばアーキテクチャの話。

極端な話、Windowを作成するにはWindow-System全体のアーキテクチャを理解して
いなければならないし、その層はある程度抽象化された世界だから、個別の
アルゴリズムの話は出てこない。

よってスレ違い。
>>312
で、おめーは
説明しようと思えば説明できるのか?
>>312
>その層はある程度抽象化された世界だから
プッ
>>312-313
ププッ
>アルゴリズムというと特定の種類の計算を行なうための方法を指す言葉だよね。
>日本語でいうと算法。基礎理論っぽい。
プププ
316デフォルトの名無しさん:02/11/29 03:42
>>290
大きさの分らない構造体なんて、どうやって書くの?
クソして寝ろ
>>316
…ひょっとしたらB木を使った索引ファイルは、
 Cでポータブルには書けないかもな。
319デフォルトの名無しさん:02/11/29 10:46
>>290
struct x {
    int n;
    char d[];
};
VCでは通るけどね。
他ではどうだろ。
>>319
gccやC99準拠処理系でも桶
>>319
それって
struct x {
 int n;
 char *d;
};
の意味だよね? 固定長だろ?
>>319
それを、正しいalignmentでメモリ上に置くのって、
どうやってポータブルに書いたらいい?
ブロック崩しのアルゴリズムが乗っているサイトきぼん。
>>324
別に「ブロック崩しのアルゴリズム」というような、特有の
アルゴリズムはないと思う。
>>325
テトリスの間違いでしたスマソ
>>326
別に「テトリスのアルゴリズム」というような、特別な
アルゴリズムはないと思う。
328319:02/11/29 14:08
>>321
いんや。ポインタじゃなくてラベルだ。(sizeofでしらべてないけど)

>>322
ほとんどの場合は大丈夫でしょう。
みんなインテルだし。
>>328
インテルだって、アラインされてないと
糞遅くなるのでは?
330デフォルトの名無しさん:02/11/29 14:39
ここには、3D-手とリスの作り方等のサンプルがある。
他は、オセロと昔はやったルービクキュー(=3、いけね、
ブと嚇つもりがブッとやっちまたい)のサンプルコードがある。
>>331
まじありがと〜
>>331
てか、テト★スのソースすら乗ってないじゃん。だめぽ。
丸投げなら他へ行けアフォ。

ここはアルゴリズムスレ蛇。
>>333
テトリスなら7行プログラミング2にあったべ
336デフォルトの名無しさん:02/12/04 20:54
ttp://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
これと GNU diff、どっちが速いの?
解説キボン
アルゴリズムが存在するかどうかを判定するアルゴリズムを教えてください。
>>337
存在しないことが証明されているはず
336 のURL の O(NP) ってまともに動くか?
だれかやってみそ
>>336
こりゃ懐かしいものが。

diffも同じアルゴリズムだったような気がする。
ソースプログラムを読んでみたら?
UNIX MAGAZINEで解説していた気もする。
341デフォルトの名無しさん:02/12/16 23:33
age
<html><body><font color=#111111>sage</font></body></html>
くいっくそーと
344IP記録実験:03/01/08 21:22
IP記録実験
http://qb.2ch.net/test/read.cgi/accuse/1042013605/

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

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

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

73 名前:ひろゆき ◆3SHRUNYAXA 投稿日:03/01/08 17:27 ID:rLfxQ17l
>ところで、IPが抜かれて何か今までと変わることってあるのでしょうか?
・今までより、サーバが重くなる。
・裁判所や警察からの照会があった場合にはIPを提出することがある。
ひろゆきとセックスしたい
【2ch】全鯖IPアドレス記録の方向で実験開始

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

11 :ひろゆき ◆3SHRUNYAXA :03/01/08 17:16 ID:rLfxQ17l
   全レスです。

22 :ひろゆき ◆3SHRUNYAXA :03/01/08 17:19 ID:rLfxQ17l
   家族構成と小学校時代の恥ずかしかった思い出も記録されます。
======2==C==H======================================================

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

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

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

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

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

んじゃ!

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
馬鹿yahooがニュースにしたりするから、
何も知らんような奴が流れ込んで来る
あとZDnetも何かにつけて2chネタばっかり書きすぎ
>225

 貴方達が古いパソコンに侵入していたの知ってましたよ。
 わざとJCOMのIP同じにしてた理由も分ります?
 トレースの実験してたらどうします。実戦積む事は大事です。(僕は素人だけど)

 これで自殺したら
 適当に作った恥ずかしい文章や、幾つか足した嘘のアドレス等の文章が流出する、、それは恥ずかしい・・

 そう思う為に結構痛々しい事も誇張して書きまくってましたがね。
 おかげさまで持ちこたえました

 ・・最初はハックは貴方方を想定していませんでしたが
 2ちゃんねるというサイトについてあまりに私は無知だった様です。

 只、量子論は今日全て解決しました。
怒られる前にキャップをはずしたのと
怒られてからキャップをはずしたのでは
裁判結果がちがうんだろうか
>けんす子
ちょっと2chが面白くなくなってしまうのでは・・・と心配してしまう
のですが、ワタクシ・・・。
告発系が駄目って事ですよね。
ううぅーん。雅の事も言えなくなっちゃうのかな?(関係ないか)
2003年1月9日より 計2731票

匿名性に絡む問題なので反対 27% 763 票
サイトのためになるから賛成 54% 1489 票
利用しないから関係ない 8% 242 票
2ちゃんねるってなに? 4% 122 票
アクセスログってなに? 4% 115 票

みんないい香具師がおおいのか?
テンプレートって何?

そのレスだけ放置して他のレスを対応するに一票
スレってなんですか?(´Д`)
まあ、危なっかしい書き込みの抑制にはなるかな
t
真っ先に帰るのが普通の客なんでないかな??冷やかしの人に裁判沙汰のリスクは
おえないでしょ。
本職はIP位ではへこたれずに留まるだろうけど、暫らくは半端な厨房が通常板へ
なだれ込んで無差別に悪さ(差別コピペ)をする、っつー事になりそう・・・

新しいテーマをだして書き込み募集したいんですけどどうしたらいいの?
広告とか電話番号らしきものとかIPだかホストだかそんなんだったと思いまつ。
実社会だろうとネット社会だろうと吉外はいるわけですから、
その吉外に関わることで被害を被らないようにしようと、
最高裁では棄却されることが分かっていて400万円を
払わねばならないからこそ気づいた、
ひろゆきならではの対処方法でしょう。
======2==C==H======================================================

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

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

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

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

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

んじゃ!

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
犯罪でなければIPが警察の手に渡る事はないだろう。
IPをぴろゆきに警察が聞いている時点で、ISPにも聞きに言ってるわな
それを照合すれば個人は特定できるわな
 IPを記録するって事は、実社会のルールに少し近づくだけな
ので、発言に責任を持つという当たり前の事さえ守ればどうって
ことはありません(その当たり前の事が今まで行われていなかった)。

 まあ、トラブル起こすと社会責任も取らなきゃならないかも
しれないので、社会責任を終えない未成年者はどうするかは分からない
けれど。よく知りませんが、中学生とかが大人を批判する権利自体
無い可能性もありますが。
asdf
warata
2ちゃんねる知らない人4%と言う事は、
96%の人が、2ちゃんねるの存在を知っていると言う事?
当然含まれるかと思われ。
凄ぇ………OSはNT系ですよね………?
2002年2ちゃんねるアニメランキング1位のアニメに・・・・

モナーが出演決定!!!!!!!!!!!!!!!!!!!!!

<<放送時間>>
1/12
大阪 テレビ大阪 (日)9:30〜10:00
東京 テレビ東京 (日)9:30〜10:00
名古屋 テレビ愛知 (日)9:30〜10:00
福岡 TVQ九州放送 (日)9:30〜10:00
札幌 テレビ北海道 (日)9:30〜10:00
岡山・高松 テレビせとうち (日)9:30〜10:00 

こいつ、気合い入ってるな
IP取られてるのになぁ・・
【予告】元スレは泣きながら残った宿題をやっている
どうもあんたは「匿名による告発の場がなくなる」という
前提をもって話をしてるようだけどね
そもそもここが告発の大本になったことなんて無いんだから
前提からしておかしいわな
2002年2ちゃんねるアニメランキング1位のアニメに・・・・

モナーが出演決定!!!!!!!!!!!!!!!!!!!!!

<<放送時間>>
1/12
大阪 テレビ大阪 (日)9:30〜10:00
東京 テレビ東京 (日)9:30〜10:00
名古屋 テレビ愛知 (日)9:30〜10:00
福岡 TVQ九州放送 (日)9:30〜10:00
札幌 テレビ北海道 (日)9:30〜10:00
岡山・高松 テレビせとうち (日)9:30〜10:00 
>発信者の特定は第三者機関からの要請があってから行えば十分な筈ですが?
(先日までは)そのような環境ではなかったワケですよね。
なるほどサンクス
379山崎渉:03/01/13 18:51
(^^)
ふぁーすと
せかんど
さーど
ふぉんど
ふぁいぶんど
381デフォルトの名無しさん:03/01/15 02:12
IPを記録することにしても、どこか別のサイトで中継をしてくれれば、
その中継サイトのIPアドレスが記録されることになるので、それが
望ましいと思うわけなんだな。別の中継サイトだろうとなんだろうと
とにかくIPを記録しさえすればいいのであればね。
故意に中継サイトのIPしか残らないような仕組みにしたら
IPを取っていないのと同等とみなされるのがオチ。
383山崎渉:03/01/15 17:44
(^^)
384デフォルトの名無しさん:03/01/16 15:39
ハッシュ法(チェイン法)の平均比較回数が1+α/2なのはなぜですか?
導出できそうにもありません。(※αは占有率)
>>384
ハッシュ法でチェインを利用した場合、
ハッシュ値を求めた後、キーワードが一致するかどうか最低、1回の検索が必要となり
最悪は、そのチェインの長さだけ必要になるという事では?
すばやいレスありがとうございます。
その考えだと1+(α+1)/2になると思うんですが、考え方が違うでしょうか。
線形探索の平均比較回数をα/2で考えるといけそうなんですが、+1/2を省略せずに導出したいです。
チェインの長さが0だとすると 1回の比較 平均は1回
チェインの長さが1だとすると 0,1 最悪2回の比較 最短1回の比較 平均1.5回
チェインの長さが2だとすると 0,1,2 最悪3回の比較 最短1回の比較 平均2回
 ・・・・
チェインの長さが4だとすると 0,1,2,3,4 最悪5回の比較 最短1回の比較 平均は3回
 ・・・・
チェインの長さがnだとすると 最悪1+n回の比較 最短1回の比較 平均は1+n/2回

次にα:占有率とチェインの平均長さとの関係は

最高比較回数がn+1っていうのは分かるんですが、この+1っていうのはハッシュ値による
グループの指定の1回だと思っているんですが、そうすると最短は2回だと思うんですが。
あのさ、>>384で [平均比較回数] って書いてるじゃないか

ハッシュ値を求めるのはハッシュ値を求めるという処理であって比較じゃないだろ
390デフォルトの名無しさん:03/01/19 15:12
テキストエディタを作っているのですが、横方向にスクロールバーは無い状況で
テキストが全体で何行になるか分かるアルゴリズムってありますか?

横スクロールありで改行まで1行だとすれば、全体の行数を
SetScrollRange(スクロールする最大行)に入れるだけで済みますが、横にスクロール無しの時に
画面の端で折り返す状態だと、SetScrollRangeに設定する値を決められないんです。
NHK教育のピタゴラスイッチに出てくるアルゴリズム体操と
ラジオ体操とではどちらが体に良いでしょうか?
>>390
単純に考えていいんじゃないの?
「論理行のN行目を表示するのにM行使う」をすべての論理行にたいしてカウント。
393山崎渉:03/01/23 20:10
(^^)
394デフォルトの名無しさん:03/01/24 00:19
C,C++のデータ構造を数学的に記述しようとする場合は
有向グラフということになるんでしょうか?
データ構造をですか?
関数の遷移ではなく?
396デフォルトの名無しさん:03/01/28 12:44
二分探索の平均比較回数がlog2(n)で、最大がlog2(n)+1なのはなぜですか?
すみません
これ単一RR回転ですよね?なんか教科書にはLL回転と書いてあるのですが…
http://www.42ch.net/UploaderSmall/source/1043732071.jpg

絵汚くてすみません(汗
>>396
最大はNじゃない?
AVL木ならそれで正しいけど
それってどれだろう?
>>400
>>396
    
souka int ka ...
403デフォルトの名無しさん:03/02/20 10:33
>>396
完全にバランスされているなら、
平均は log2(n)
最大は Ceil ( log2(n) ) じゃないかな?
404デフォルトの名無しさん:03/03/27 08:05
このスレ利用しようあげ
405デフォルトの名無しさん:03/03/27 08:35
ソートって種類が色々ありますが、どのソートを利用することが多いんでしょうか?
やっぱクイックソート?
あとC言語でソートを使うときは標準ライブラリのqsort()とかを使うんですよね?
>>405
バブルとセレクト
>>405
最近、ソートが必要なデータ構造使ってないからわからん。
メモリを贅沢に使った trie とか PAT-tree (or Suffix-Tree) とか。

ま、一番よいのは挿入だよ挿入。挿入を知らないなんて子供だね。
408デフォルトの名無しさん:03/03/28 07:27
そうだね。 ソート単体で使う事がめっきり少なくなった。
GUIが絡んでくると 動的に追加削除しながらソート状態を保つ必要があるからB木とか
それも面倒でついデータベース使ってしまうな。
>>406
バイブでエレクト
410デフォルトの名無しさん:03/03/28 13:56
この板の初心者です。教えてくださいませ。
よく大戦略などのゲームで使われている、
ユニットの目標への移動のアルゴリズムってどのようにやっているのでしょうか?
画面がスクエア四方ではなくて、ヘクスだし、
地形効果などによる重み付けなども考慮しないといけないし、
かなり難しいと思うんんですが。
よく情報数学の教科書にのってる最短経路アルゴリズムなどを
応用しているのでしょうか?

411デフォルトの名無しさん:03/04/01 22:23
スレ違いなのかもしれませんが、教えてください。
この4月にソフ開受けるのですが、BNFがいまいち理解できません。
「たとえば、次の生成規則にのっとって生成できる式を選べ(四択)」
みたいな問題が出たとき、
ある特定のアルゴリズムでを適用すればかならず正しいものが選択できる
ものなのでしょうか?
もしそういうアルゴリズムがありのであれば勉強したいのですが?
アルゴリズムの得意な人がたくさんいそうなので書いてみました。
412デフォルトの名無しさん:03/04/02 23:38
あへ
>>411
何を聞きたいのか、もう少し具体的に説明しれ。
414デフォルトの名無しさん:03/04/04 23:56
そもさん!
415デフォルトの名無しさん:03/04/05 00:05
>>411
ソフト開発技術者試験でしょ?
○があったり、矢印で繋がっている問題か?
>>414
せっぱ!
417デフォルトの名無しさん:03/04/05 00:19
>>416
両リーグ
418デフォルトの名無しさん:03/04/05 01:03
>>410
A*(エースター)というよく知られた経路探索アルゴリズムがあるでし。

ここらへんのリンクを辿るか、
http://www.gameai.com/pathfinding.html
Game Programming Gemsの1巻でも買うか、
http://www.amazon.co.jp/exec/obidos/ASIN/4939007286/
あるいはアルゴリズム名は出てこないけどこのページでも。
http://www.campus.ne.jp/~ishigami/CREATION/MAKING/index.html
419デフォルトの名無しさん:03/04/05 05:02
struct {char name[10]; char birth[10]; int age} data[1000]
のようなデータ構造があってflagを調べて各フィールドを出力するかどうかを決めたいんですけど
for(i){
 if(flag&NAME){
  puts(data[i].name);
 }
}
ってループごとにflagチェックしてて効率悪いと思うのですが
if(flag&NAME){
 for(i){
  puts(data[i].name);
 }
} else if(...) {
 for(i){
  puts(data[i].name);
  puts(data[i].birth);
 }
}
....
もなんか違う気がします。
普通どうするもんなんでしょうか?
>>419
0.001秒を争うのでなければ
上の書き方で3つ並べるのが見やすいし保守もしやすい文句なし。
puts()の方が1000倍以上遅いのでこの場合の最適化は無意味に近い。
421デフォルトの名無しさん:03/04/05 08:59
K仲川は、
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ
うんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこうんこ

はじめまして。スレ違いなのは十分承知しておりますが、ここ以外無さそ
うでしたので。。非可逆圧縮の1つであるLossy・JPEGの周波数処理の
ロジックと画質の関係についてお聞きしたくてレスしました。または著書
(ISBN−??)を紹介していただけるだけでもとてもうれしいです。
一般的なJPEGと呼ばれるものにはQファクター(画質)というものがあり
ますが(値:0〜100)、これと離散コサインの関係が知りたいのです。圧
縮率はQファクターも関係しますが、同じQファクターなら、画像そのもの
に依存しますので、それについては今のところ関心はありません。
長々とスミマセンでした。
>>419
struct s_t {char name[10]; char birth[10]; int age; } data[1000];

static void case1(struct s_t *s){ puts(s->name); }
static void case2(struct s_t *s){ puts(s->name); puts(s->birth); }
...
void (*put)(struct s_t *s);

put = (flag & NAME) ? case1 : case2;
for(i = 0; i < ...; i++){ put(&data[i]); }
>>422
量子化の精度ではなくて?
>>424さん。遅くなりました。424さんがおっしゃる通り、量子化レベルの係
数のことを自分は言っていたのだと思います。
ウェブ検索とか本屋行ってみたのですが、これというものが見当たらず、
現在,公開アルゴリズム(Independent JPEG group's software)などのソ
ースコードを調査していたら、クオリティの他に、サンプリングファクター,
やハフマンテーブル等出てきて、余計混乱しています。
どういうINPUTを与えたらどういうOUTPUTが出るのか、算術式と論理
で解りやすく説明されているウェブページや著書って無い物なのですかね?
>>425
サンプリングファクターはともかくハフマンテーブルは画質に関係ないはずだが。
>>426さん。どーも。
ソースコードと http://siisise.net/jpeg.html などを見ていて少しずつ解っ
てきました。結局、色分離、離散フーリエ変換、量子化を経た結果、ハフ
マン符号化により圧縮工程になる訳で、貴方のおっしゃっる通り、関係な
いぽいです。 もうちょっと自力で調べて見ます。 躓いたらまた来ます。
そのときはよろしく。
428デフォルトの名無しさん:03/04/14 21:58
k-d tree てなんだよ!
I love にくたま.
>>428
Clifford Shafferの「Javaによるデータ構造とアルゴリズム解析入門」
ttp://www.amazon.co.jp/exec/obidos/ASIN/4894711958/
とか、あるいは計算幾何学系の本を見ると載ってるよ。
この本、Javaに全く興味ない人にとっても、結構いい本だと思うんだが、
2chではあまりみないなあ。
431山崎渉:03/04/17 15:24
(^^)
432山崎渉:03/04/20 04:32
   ∧_∧
  (  ^^ )< ぬるぽ(^^)
433&& ◆VE2ur6fZVk :03/05/17 23:29
hs
434デフォルトの名無しさん:03/05/18 09:42
age
435名無し@沢村:03/05/18 11:03
おまいらよ、データ構造って知ってるか?
データ構造は下から右からで4バイト単位よ。わかるか?
つまり、
                       12番地
                       8番地
                       4番地
4バイト目 3バイト目 2バイト目 1バイト目 0番地

となるわけよ。配列に書き込むときはふつう左からだろ?だから順序が逆になるのよ。
おまいら、これは覚えとけ!!
TeleviのJion覚えとけ。
>>435
( ゚Д゚)/ 沢村!ずれすぎで分かりません
沢村はPDPエンディアソのマシンでも使ってろ
439山崎渉:03/05/28 12:59
     ∧_∧
ピュ.ー (  ^^ ) <これからも僕を応援して下さいね(^^)。
  =〔~∪ ̄ ̄〕
  = ◎――◎                      山崎渉

挿入ソート
442デフォルトの名無しさん:03/06/24 00:59
perlとphpしかできないおれがアルゴリズムを勉強するにあたって、
参考にできる書籍やサイトなんて。。。。ないよねー
Cとかなんだものなー、解説が・・・
アルゴリズムを解読するだけなら、Cの基本構文さえ覚えりゃいいんだから、
この機械にCを勉強しとき。
確かにアルごリズム本といったらC/C++が多いからな。
こういったとこでもCをおぼえるメリットが出てくるんだな。
B*-tree
って何て読むの?
445デフォルトの名無しさん:03/07/02 22:06

画像を45度回転させるのに上手い方法ってありますか?
−を/に変えるのを縦のピクセル分繰り返すっていう単純な方法だと、
サイズが約4割増しになってしまう上に隙間ができてしまうんですが・・
446デフォルトの名無しさん:03/07/02 22:23
>>445
発想を変えてお前が45度逆に回転する。
>>446
(・∀・)ソレダ!!

>>445
発想を変えて、逆に回転先のドットの色を
回転元から求めるようにすると隙間が出来ないよ
448デフォルトの名無しさん:03/07/03 00:26

いや、あの・・・
僕が回転しても意味がない様に思うんですが・・・
449デフォルトの名無しさん:03/07/03 00:41
>>448
ネタですか?
>>446
モニタを45度傾けるのも捨てがたい。
>>448
>>447で正解でてるぞ
これがダメならビフォーとアフターをわかりやすく
提示してもらわないとどうにもならん
>>450
眼球だけ45度ってどうよ?

452さま。ありがとうございます。
昨日から自分が回転したり、眼を回転したり、モニタを回転させたりして
がんばっても全て徒労に終わっていましたが、ようやく解答にたどり着く
事が出来ました。どうもです。
455デフォルトの名無しさん:03/07/04 00:51
_
456デフォルトの名無しさん:03/07/04 02:02
私が作りました!見てね♪
http://nuts.free-city.net/index.html
457山崎 渉:03/07/15 10:13

 __∧_∧_
 |(  ^^ )| <寝るぽ(^^)
 |\⌒⌒⌒\
 \ |⌒⌒⌒~|         山崎渉
   ~ ̄ ̄ ̄ ̄
http://cham.dyndns.org/list/source/up304.jpg
フォルダで表示→縮小版にすると画像が変わるんだけど(XPだけ?
これってどういう仕組み?
>>458
サムネール(縮小画像)入りのJpegかな?
>>459
縮小画像を指定できるってことですか?
>>458
埋め込みサムネイルでググってみ
すぐ判るでよ
>>461
縮小するさいの色抽出アルゴリズムみたいなものがあって
それを逆手にとって・・・みたいなことを考えてました
ここでする質問ではなかったみたいですが、応えてもらい感謝です。
ありがとう。
Blocksortingの復号時に、例えばファイルサイズがunsigned longで表せる場合、
必ず元データの4倍メモリが必要になってしまうようなのですが、

<参照ページ>
ttp://member.nifty.ne.jp/DO/blocksorting.htm

変換テーブルを動的に作成する等により、
必要メモリ量を削減するアルゴリズム(?)はないでしょうか?

ファイルサイズ*sizeof(unsigned long)の領域なんてでかすぎるよママン_| ̄|〇
>463
ファイルを1Mとかの適当なサイズで分割処理すれ
465463:03/07/29 21:13
>>464
現状Blocksize=Filesizeなので分割無理ぽ。

もっと分割して圧縮(変換)してくれYO!とか訴える方が妥当?(´・ω・`)
466山崎 渉:03/08/02 02:54
(^^)
467デフォルトの名無しさん:03/08/09 21:41
あげ

>>465
自分で実装すればよろしい。
468デフォルトの名無しさん:03/08/10 08:44
ソートも種類がたくさんあるよなぁ。どれを使えばいいのやら・・・
ほとんどソートされてるとか、ソートされたデータに追加する時とかでなければ
たいていの場合はクイックソートで十分だろう。
安定なソートがほしいならデータ順をキーの後ろに入れろ
470デフォルトの名無しさん:03/08/10 15:17
B*-tree
って何て読むの?
bee star treeじゃない?
コムペイトー
僕の肛門も閉鎖
「ミニロトを1500個、ダブりなしで選択する」っての
自分の頭じゃいちいち照合するか、ソートしてから照合するかしか
思いつかないんですが、もっとスマートな方法ってありますか?

ミニロトのルールは
・1-31の数字を5つ
・数字のダブりはなし
です。
>>474
出た数字を記録しておいて2度と出さないようにするとか?
ぜんぜんスマートじゃないけどな。

int main()
{
  static char flag[32][32][32][32][32]; /* zero filled */
  int i, n1,n2,n3,n4,n5;
  for (i = 0; i < 1500; i++) {
    do {
      n1 = (rand() % 31) + 1;
      n2 = (rand() % 31) + 1;
      n3 = (rand() % 31) + 1;
      n4 = (rand() % 31) + 1;
      n5 = (rand() % 31) + 1;
    } while (flag[n1][n2][n3][n4][n5] != 0);

    flag[n1][n2][n3][n4][n5] = 1;
    printf("%2d,%2d,%2d,%2d,%2d\n",n1,n2,n3,n4,n5);
  }
}
>>474
1から31までの数字からなる順列を一様ランダムに生成して、その最初の5つの
数字の列を取り出す。これを1500回繰り返す。1500くらいなら、まず衝突は起
きない。

順列のランダムな生成は、インデックス(i)をシフトしながら[i+1..n]の中か
らランダムに選ばれた位置(j)と入れ替えをする(swap(x[i],x[j]))。これを
i=1..n-1について繰り返すと、できあがる順列の生成確率は一様になる。
>>475
約33MBですか(^_^;)
478デフォルトの名無しさん:03/08/13 09:04
>>474
この程度の量だったら

while( 登録数が 5 より小さければ ) {
ミニロトの数を乱数で生成;
if( 生成された数が今までに登録されていなければ ) 生成された数を新たに登録;
}

ぐらいしか良い解法はないような気がするが・・・

ダブりのチェックはハッシュを使うと良いかも。
#!/usr/bin/ruby
def loto
  (1..5).map {(rand(31)+1).chr}.join
end
h = {}
h[loto] = true until h.size == 1500
h.each_key {|l|puts l.unpack("C*").join(" ")}
>>474
1から31x30x29x28x27までの数値を1500個生成する。
この1500個は重複しないようにする。
あとは、この数値をインデックスとみなした
1から31までの5個の数値の組を求めればよい。

必要なメモリ量は1500ワード+定数ワード。
>>480
>この1500個は重複しないようにする。

>>474 の質問は、どうやったらそれを重複しないように
(または最初から重複が出ないように)生成できるかってことなのでは?
>>481
1からnまでの数値をx個重複なしに選択する問題に縮小できているので簡単になったのでは?
もっとも単純な方法はサイズ31P5の配列を用意して乱数で配列にマーク
マーク済みの要素にヒットした場合はマークなしになるまでループ
ただしこの場合は必要なメモリが多くなるね
480じゃないけど、31*30*29*28*27=2038932に対して、たった1500個だから、
2038932個のフラグ作って、既に使ったかどうか見るのが速いと思う。
484483:03/08/13 14:33
思いっきりかぶってた。
0が抜けてた。
2038932 → 20389320
31P5 じゃなくて 31C5 であるよーな。
487デフォルトの名無しさん:03/08/14 23:33
CGIなんですが、
(ちなみにPerlで、DB使えない・・・ってこのスレ的には、そんなことはどうでもいいか)
複数画面にわたるメールフォームで、
答える内容によって、メールフォーム画面が、変わってきます。
(要するに、分岐点のある画面遷移)

いいかえると、各画面は静的なテンプレートhtmlとして、すでに用意されてて、
その静的なhtmlをCGIで読み込みつつ、hiddenで値を渡しつつ、
分岐してく・・・というものなんですが。

どうするのがスマートなんですかねー?
『<input type="hidden" name="next" value="hoge.html">ってかんじで、
テンプレートhtml内に次のテンプレートhtmlを指定しとく』
ってのが、すぐ思いつく方法なんですが、
なんか、そのまんますぎて、もっとスマートなアルゴリズムがあるような気がするもんで。。。

どうなんでしょうか?
板違いでしょう。
489487:03/08/15 01:40
うーん、迷ったんだけど、やっぱりそうかな。アルゴリズム的視点から考えようかな、と思ったんだけど。。。
ということで、
>>487は無視してください。WebProg板で聞いてみます。
490山崎 渉:03/08/15 15:18
    (⌒V⌒)
   │ ^ ^ │<これからも僕を応援して下さいね(^^)。
  ⊂|    |つ
   (_)(_)                      山崎パン
maintenance
0.99ゥ = 0.3・・・ = 1÷3
すいません。今、珠玉のプログラミングっていう本
読んでるんですけど、
次のソースが意味わかりません。
ビット配列についてらしいのですが、

enum{ SHIFT = 5, MASK = 0x1F };
int *x;
void set( int i ) { x[i>>SHIFT] |= ( 1<<(i & MASK) ); }
void clr( int i ) { x[i>>SHIFT] &= ~( 1<<(i & MASK) ); }
int test( int i ) { return x[i>>SHIFT] & ( 1<<(i & MASK) ); }

どうか教えてください。
x配列の、 下位 5bit のみを 連続した 1ビットのフラグとして扱う時に

set/clr/test してるというだけだと思うが?


ただ、アクセスするなら STORE が不足してるな。

void store(int i , int dt) //x ビット位置i のビット状態を dt にする 。

というのを書いてみたら?
set()とclr()使うんだろ。
でもこれ、xの確保とか拡張とかがないけど、それは>>493が省略しただけか?
496493:03/08/28 02:04
>494
レスありがとうございます。
ずっと考えてようやくわかりました。
x配列の1つの要素分を32ビットとし、ビット列をつくる。
setはパラメータiに対応したビット位置のビットを1にする。
clrはsetの逆でビットを0にする。
testはパラメータiに対応したビット位置のビット状態を返す(0か1)。

だと思うのですが...

>495
すいません。xの確保とかは省略しています。
set/clr を条件分岐で呼んでもいいけど、
xor and xor でやった方が面白いよ
>>494
5bitのみじゃない。0x1fでマスクしてるのは32(bit)に収まるようにするため。

>>497
dtを0/非0で考えるとこんなのしか思い付かんのだけど。
void store(int i, int dt)
{
    int mask = 1 << (i & MASK);
    i >>= SHIFT;
    x[i] &= ~mask;
    if (dt) x[i] |= mask;
}

>>498
x := x xor ( mask and ( x xor dt ) )

説明:
x xor dt // x と dt の違う位置が 1 になる
mask and * // そのうちマスクしたいものだけ消去すれば 変更すべき位置のみ1となる

ちょい待ち、dtの値をどう考えてる?
ヒントを出しただけだから、実際のコードは自分で書いてよってつもりだったけど

こんな感じ
const MASK = (1 << SHIFT) -1;
void store(int i, int dt)
{
int mask = 1 << (i & MASK);
int bitdt = dt << (i & MASK);
i >>= SHIFT;
x[i] ^= ( mask & ( x[i] ^ bitdt ) ) ;
}
store(0, -1)とかやったらどうする?
>>502
それより、test(i) の帰り値をそのまま渡せない方が問題だと思うけどな
まあ、
int bitdt =(dt!=0) << (i & MASK);
と論理型を経由したらいいじゃない。

ガイシュツか?
The Art of Computer Programmingペーパーバック
価格: ¥2,451
発売予定日は 2004/05/31

ttp://www.amazon.co.jp/exec/obidos/ASIN/0201853922/qid=1062408319/sr=1-1/ref=sr_1_0_1/250-7111058-9972260
うほっ。いい感じ。
なぜ推薦図書のスレに書かない? >>504
506505:03/09/01 18:43
>>504
これってVolume IVだよね。

こいつと同じISBN
ttp://www.holbornbooks.co.uk/details.aspx?sn=31007
>>505
来年5月発売だからね・・

>>506
今現在、
3版1巻
3版2巻
2版3巻
が、ハードカバー版で発売中(だよね?)
で、2004/05/31に
4版1巻
4版2巻
4版3巻
が、ペーパーバック版で発売される(らしい)。
508507:03/09/02 14:52
さらに
同日2004/05/31に
5,6,7巻(ハードカバー版)も同時に発売されるらしい。
bibleもついに完結。
509吉田:03/09/08 22:18
javaを勉強している物ですが、仕様言語がjavaの本でアルゴリズムとデータ構造を学ぶのにうってつけの本ってありますか?
510吉田:03/09/08 22:19
×物→○者
511mufu:03/09/08 22:44
すんまそん、
knuth本に、the shortest addition chain というのが出てくるんですけど、
だれかこれのアルゴリズム教えてちょん
>>509

初心者向けとして分かりやすい?
 Javaアルゴリズム+データ構造完全制覇
 (標準プログラマーズライブラリ)
 オングス著 杉山 貴章, 後藤 大地監修
 技術評論社 ISBN:4-7741-1632-7

真面目に勉強したい人向け
 Javaによるデータ構造とアルゴリズム解析入門
 クリフォード・シェーファー著 久野 禎子, 久野 靖訳
 ピアソン・エデュケーション ISBN:4-89471-195-8

実用的なリファレンスとして便利
 Javaによるアルゴリズム事典
 奥村 晴彦(他)著
 技術評論社 ISBN:4-7741-1729-3

あたりが定番かな?
最近は A+D=P は読まないのか?
>>513

509は「javaの本で」って書いてるからそもそも対象外でないの?
それにA+D=Pよりは、さすがにちと古いし。むしろCLRでしょ。
515デフォルトの名無しさん:03/09/21 08:24
null window search
について教えてください。

web上の情報、文献上の情報では理解できませんでした。
どうか、噛み砕いて、分かりやすいように説明して頂ければ。
>>515
ひとつ目の候補でαが決まったらその後の候補では(α,α+1)で探索して
α+1以上が帰ってきた場合だけ(その値,β)で再探索する方法。

このところソースを読んでないからうろ覚えだけど、確かこんなのだったと思った。
>>475-486
お前ら、C言語/Javaによるアルゴリズム辞典の「ランダムな順列」の項を読んで下さい。
HDDのデータの並びってどうなっているんでしょうか?

例えば初めにA、B、Cというデータを順番に記録したとします。
次にBのデータを消去して新しくDというデータを記録します。
この時、Bのデータがあった領域はどうなっているのでしょうか?
>>518
ファイルシステムによって異なる。

D < B ならば、B のところに上書きするかもしれない。
D を B とは全く別のディレクトリに作成するなら、まったく別の領域に書くかもしれない。
B より以前に消去した部分が存在しなくなるまで、B の領域を使わないかもしれない。
520デフォルトの名無しさん:03/09/22 11:28
1..5までの「理想的なランダムな並び」って何かで読んだ覚えが
あるんですけど、知ってる人いますか?勘違いかもしれないですけど。
[5,2,3,1,4]?
>>517
それには>>476以外のランダムな順列のアルゴリズムでも載ってるのか?
522517:03/09/23 00:57
こんな感じ?
public class RandomPerm {
  public static void main(String[] args) {
    int[] num = new int[31];
    for (int i = 0; i < num.length; i++) {
      num[i] = i + 1;
    }
    Random rnd = new Random();
    for (int i = num.length - 1; i > 0; i--) {
      int j = rnd.nextInt(i + 1);
      int tmp = num[i];
      num[i] = num[j];
      num[j] = tmp;
    }
    for (int i = 0; i < 5; i++) {
      System.out.println(num[i]);
    }
  }
}
>>522
>>475-486をちゃんと読め
一つのコマンド(文字列)を取得します
そしたらそのコマンドをコマンドリストの中から比較して対応する
関数を呼び出すようにしたいのですが
最初のほうがif elseif なんかつかってたんですが
膨大な量のコマンドになってしまいif elseifをずらぁっと何行にも
わたって書いています.
これでは非常に効率が悪いと思うのですが…直そうにも直し方がわかりません…
二分探査等をつかってやろうとおもっても.
そのコマンドに対応した関数を呼び出す方法がわかりません.
教えてください!
>>524
マップを使っては伺か?
526517:03/09/23 11:21
ああ、単に1500組の組み合わせではなくて、ダブり無しでか。鬱。
169911通りからダブり無く1500か。
ランダムな順列を作る方法だと、サイズが169911な配列はちょっと大きすぎる感じか。
工夫すれば、1500個以外は1ビットになるけど...
>>524
言語にって実装のやりやすい方法があるわけで・・・

とりあえず大抵の言語で使える方法は、
 "コマンド名", 関数名 の表を作っておいて
その表からバイナリ検索するプログラムを自動作成するプログラムを作るというのが汎用解だと思いますよ。
>>524
文字列なら trie を使ったほうが効率がいいけど、
人間が文字列も管理することを考えると、>>527 かなぁ。
C/C++/Delphi のような関数ポインタが使える場合は
 メンバ名と関数ポインタの構造体を配列作って そいつをハッシュ検索 か ソートしてバイナリ検索。

JAVAの場合は、オブジェクトにして同じように
530524:03/09/24 18:42
みなさんありがとうございます
なんとかできそうです!
>>529
ソートは必要ないでしょ。
整列した状態で配列を作ればいいんだから。
532デフォルトの名無しさん:03/09/25 16:35
あるアプリを作ってるんですが、
ランダムな数字のリストがあるとして、
それらの数字をいくつか選択して、それらの合計値がある値にもっとも近い(ただしオーバーはアウト)数字の
組み合わせを探し出す出す探索アルゴリズムってどこを参照すればいいですか?
533532:03/09/25 16:48
ツリー構造にしてバックトラッキングでしょうか
>>533
おひおひ冗談だろ。0-1ナップザックは典型的なダイナミックプログラミング
の例題じゃないか。バックトラック総当たりで解いてどうする?
ナップザック問題
536532:03/09/25 17:19
>534

>535

教えていただき、ありがとうございます。早速調べてきマッスル
537デフォルトの名無しさん:03/09/25 23:52
文字列を検索するプログラムで
ワイルドカード検索の機能をつけたいと思ってるのですが
自分で一からソース書くとしたら、どんなソースを書けばよいのでしょう?
ちなみに言語はCです。
よろしくおながいします。
>>537
マルチは困るなぁ。
マジレスすると、簡単なオートマトンでできる。
539デフォルトの名無しさん:03/09/26 00:20
オートマンって何ですか?
自分初心者な厨房でスマソ。
540デフォルトの名無しさん:03/09/26 00:21
あっ間違えた。
オートマンじゃなくて
オートマトンだった。
これは何ですか?
541デフォルトの名無しさん:03/09/26 00:36
>>537
仕事なら、書くな。
趣味なら、regexやregexpを読め。
ワイルドカードだと  単純に先頭からマッチさせていって
[]ならそのどれか
? ならスキップ
*なら次の検索文字と一致するまで
とするだけだから オートマトン というほどの事でもないような気もする
543532:03/09/26 10:38
ナップザックについてお聞きしたいのですが、
4700000000のナップザックに1000〜10個前後の物を、1つの重さは大体300〜2000000000
同じ重さのものは何度も重複していれられない、の状態で最適解(ナップザックを一番重い状態にしたい)を
見つけ出す時間と、ツリー上にしてバックトラックして最適解を探す場合どっちが早いですか・・。
また上と同じ状態で、物が3万個に増えた場合はどうなりますか。

あと実は最適解のみだけじゃなくて2番目3番目の答えも取得したいと思っております。
ナップザックの場合得られた表の値をリストに入れてソートすれば取れますよね・・?
544 :03/09/26 20:20
>>543
「最適解を見つけ出す時間と、最適解を差がすう場合どっちが早いですか?」
って質問は意味をなしていないよ。何を聞きたい?

ちなみにその規模だと最適解を求めるプログラムで実行時間が stable でかつ
無理の無い時間っていうものはないとおもうよ。
545デフォルトの名無しさん:03/09/29 20:26
ツリー構造を配列によって表現したときに関する質問です。

[fig.1] のようなツリー構造を、配列で [fig.2] のように実装した場合
配列のインデックス: x のノード(以下、ノード:x と表現します。)の
[a] 左の子のノードの配列のインデックス: 2 * x + 1
[b] 右の子のノードの配列のインデックス: 2 * x + 2
[c] 親ノードの配列のインデックス: (x - 1) \ 2 (\ は、整数除算演算子です。)
で求まる。

[fig.1] ツリー構造のイメージ図

[00]
[01] [02]
[03] [04] [05] [06]
[07] [08] [09] [10] [11] [12] [13] [14]

※ [x] は、ノードを表し、x は配列のインデックスを表す。
(1桁のインデックスに 0 が付いているのには桁合わせのためで意味はありません。)

[fig.2] 実際のメモリ上の各ノードの配置図

[00][01][02][03][04][05][06][07][08][09][10][11][12][13][14]

例えば、ノード: 4 に着目すると
[a] より 2 * 4 + 1 = 9
[b] より 2 * 4 + 2 = 10
[c] より (4 - 1) \ 2 = 1
よって、ノード: 2 の左の子はノード: 9、右の子はノード: 10、親はノード: 1 である。

[a], [b] に関しては、数学的にそれらの式が成り立つことを証明できたのですが
[c] に関して、なぜこの式が成り立つのかがわかりません。
ややスレ違いな質問になってしまいますが、よろしくおねがいします。
546545:03/09/29 20:29
失礼しました。
[fig.2] の訂正です。
          [00]
    [01]          [02]
 [03]    [04]   [05]    [06]
[07][08] [09][10] [11][12] [13][14]
547545:03/09/29 20:32
546 は、[fig.1] の訂正でした。
逝ってきます・・・
ヒープソートで使うデータ構造だね。
[a],[b]が理解できたなら、[c]はそれ使えばいいよ。

[00]以外の、任意のノードのインデックスは 2*k+1 または 2*k+2 (k は非負整数)
で表わせることは分かるよね。(これは[00]以外のノードは親ノード[k]を持つ
という事。)
この式を [c] (x-1)\2 のx に代入すれば。

((2*k+1)-1)\2 = (2*k)\2 = k
((2*k+2)-1)\2 = (2*k)\2 - 1\2 = k

で親ノードkが計算できる。
>>545
親ノードのインデックスを x、x の左の子のインデックスを xl、
x の右の子のインデックスを xr とすると、

[a]より
 xl = 2 * x + 1
x について解くと、
x = (xl - 1) / 2
xl は常に奇数だから、
x = (xl - 1) \ 2

[b]より
xr = 2 * x + 2
x について解くと、
x = (xr - 2) / 2 = (xr - 1) / 2 - 1/2
xl は常に偶数だから、
x = (xr - 1) \ 2
550549:03/09/29 21:28
× xl は常に偶数だから、
○ xr は常に偶数だから、
551545:03/09/29 23:24
>>548
>>549
レスありがとうございます。
お二人の解答のように [c] の式を、[a], [b] を使って証明するとは
自分で [a], [b] 証明しておきながら気づきませんでした。
まだまだ勉強不足な未熟者でした・・・

ところで >>549 さんの解答に関する質問なんですが
勝手ですが、こちらで証明過程の式に番号を振らせてもらって

x = (xl - 1) / 2 ---[1]
x = (xl - 1) \ 2 ---[2]

x = (xr - 2) / 2 ---[3]
x = (xr - 1) / 2 - 1/2 ---[4]
x = (xr - 1) \ 2 ---[5]

[1]から[2], [4]から[5] で / 演算子が \ 演算子に
変わっているのには何か意味があるのでしょうか?

また、[3]から[4]の式への変化は
[3] の右辺の分子 (xr - 2) は偶数であるから
「(xr - 2) に対する 2 で整数除算を行った商」と
「{(xr - 2) + 1} に対する 2 で整数除算を行った商」は
同値になるという理由からの式の変化なのでしょうか?

お二人の解答のおかげで、何となくわかりはじめてきたのですが・・・
まだハッキリと理解できていないというのが現状です。
情けない・・・
>>551
数学的ロジックの修行が足りんな。
>548,>549共に[c]を証明するための道具ということを忘れるな。

>549への疑問だが,計算の結果,[2]や[5]が出てきたわけじゃない。
xl = 2 * x + 1→x = (xl - 1) \ 2
xr = 2 * x + 2→x = (xr - 1) \ 2
と変形できれば,[c]が証明できる。
つまり,[c]を証明するためには,この2式の変形を示せばいい。

この考え方,ロジックがあるからこそ,>549の変形が必要になる。
逆に,このロジックが判らない人間には,>549の変形は意味が無い。
今の>551も後者の側だから,
> 何か意味があるのでしょうか?
なんて言葉が出てしまうわけだ。

さて,>548の式を使った証明方法のロジックは理解できるかな?
553うぅ:03/10/01 03:44
ソーディングのかなり基本的な質問です。
以下の特徴を持つアルゴリズムの名前を書けっ!!とのこと 以下の通り

(1).実用的には最も早いといわれているが最悪の場合O(n^2)かかってしまう
(2).ソート済みのデータが入力された場合にはO(n)の時間で処理
(3).C言語で書かれたとき最も短い
(4).逆順にソートされたデータが与えられら場合には、データの比較とデータ交換が
共にO(n^2)回必要となる
(5).どのようなデータが入力されようとO(n*log(n))の時間でソート完了
(6).どのようなデータが入力されようとデータ交換回数がn回を超えることがない

範囲が広くてとても・・・
ご教授願います。
宿題は自分でやれ。
教科書に書いてある通りじゃねえか。
2chのトリップのアルゴリズムを教えてください?
556デフォルトの名無しさん:03/10/06 20:45
イベント駆動型(ドリブン)プログラミングはどのような用途に使用されるの?
スレ違い?
GUIはユーザの入力イベントドリブン。
ネットワークサーバも大概、外からのイベント待ち。

プログラムの設計前半部分の話だ。

>スレ違い?
うむ、大幅にズレとる。
このスレは設計終盤や設計後、そこで用いる手段のお話し。
558デフォルトの名無しさん:03/10/11 18:09
クィックソートで、ソートが滅茶苦茶遅くなるデータの並び順ってどんなときか教えてくれ。
559558:03/10/11 18:35
ちょっと前を見たら、関連の書き込みが。
>>553の(1)がどんなケースが知りたい。
560sage:03/10/11 19:04
>>559
クイックソートは基準値として採用される数値がデータの中で極端に小さかったり、
大きかったりする場合に、普段よりたくさん時間がかかる。

よって、使用している関数が、「配列の一番最初の値を基準値として採用する」方式を
とっているならば、「すでに整列済みの配列」or「逆順にならんでいる配列」で
同程度の時間がかかり、約N^2回数の処理が必要になる。

ただし、標準関数のqsort等は、上記を考慮し配列のちょうど中間にある値を基準値として、
採用する方式なので、ソートするデータが配列の中心に向かって山形or谷形になっている
配列で最も時間がかかる。
561560:03/10/11 19:06
sageミスった…

でも、まぁ別にいっか。
そんなに細かく規定されているとは初耳だ。
563558:03/10/12 01:22
>>260
ありがd
たしかにそういうデータでは遅くなったよ。


comb sortの交換距離を求めるときに使う係数は
1/1.4から1/1.3程度が使われるようですが、
この値の論理的な根拠が気になっています。
アルゴリズム解析が紹介されているサイトか文献を
教えてください。
よろしくお願いします。
むかしの日経バイトの記事によると、実験して決めたって話だったと思う。

ただ、日経バイトの記事にあった「クイックソートより速い」という宣伝
文句は眉唾。汎用インターフェースの qsort() 関数と、特定の型専用の
comb ソートを比べてたし。
あ、眉唾なことを書いてたのは、comb ソートの作者じゃなくて、日経
バイトの記者の方だからお間違えなく。
566549:03/10/15 01:28
>>565
元の論文では「クイックソートの2倍程度の時間で済む」だったのが、
翻訳が間違っていて「クイックソートの2倍速い」になっていたような・・・。
567564:03/10/16 00:21
>>565-566 情報ありがとうございます。

あらてめて、検索してみたところ、極端に悪いケースという
のも報告されていないようですね。
568デフォルトの名無しさん:03/10/24 00:32
IDなどに使われる一意になる値の生成方法について、
エレガントなやつを教えてください。
569デフォルトの名無しさん:03/10/24 01:02
>>568
一回値返すごとにインクリメントする関数でも書けば?
570デフォルトの名無しさん:03/10/24 01:31
一意じゃないし、エレガントでもないけど、UUIDじゃだめなん?
571568:03/10/24 08:00
>> 569
エレガントじゃないぞ!


>> 570
UUIDとかああいうのはカコイイんだが、APIを通してしか
取得できないのでしょうか?アルゴリズムは公開されていない
のでしょうか?
>>569
同じだけど
乱数作る  合同法やM系列 ならその法の範囲内で重ならない
573デフォルトの名無しさん:03/10/24 20:42
FTPのメリットを教えてください。
>>568
MD5,SHA-1とかは?
>>571
仕様はこのへんで
ttp://www.opengroup.org/onlinepubs/9629399/apdxa.htm

でも、グローバルな一意性がいらないのなら、シーケンスでも乱数でも
適当にやればいいですよね。

>>574
それ一意違う。
576デフォルトの名無しさん:03/11/11 21:00
ハッシュを使うとき、大きな整数をハッシュ表のサイズで割って
ハッシュ値にすることが多いと思います。
この時のハッシュ表のサイズは素数が良く、
その理由はハッシュ値が適当に分散するから、
とよく言われているようですが、
その理由がよく分からないんですが……。
>>576
ハッシュル ハッシュル
578じじぃ:03/11/11 23:01
ハッシュで思い出した。
オープンハッシュ法という言葉は誰が言い出したのか教えてください。
Open Hashって英語として意味が通じないような気もするので
和製英語なのでしょうか?

恥ずかしながら、4,5年ぐらい前に、
若者と会話していて話がかみ合わないことがあった。
 若者「ここはオープンハッシュでやってます」
 私「でも、エントリの削除が面倒じゃないか?」
 若者「単方向のリンクですが、どうせ線形サーチしなきゃならないので面倒ではありません」
 私「いや、その線形探索でやるにしても、削除フラグつけたり、ダミー入れたりしなきゃならんでしょう?」
 若者「????」
結局、若者も私も衝突したエントリをリンクでつなぐハッシュ
のことを言っていたのでした。

それからしばらくして「オープンハッシュ」という言葉を
頻繁に聞くようになり、別の若者にたずねたら「アルゴリズム辞典」
みたいな本を持ってきて見せてくれた。
いまWebで検索してみたらやっぱりでてくる。
open addressingはクローズドハッシュで、
リンクでつなぐのハッシュはオープンハッシュというようです。

余談
 Knuthの3巻を若者にみせたとき、
 その装丁をみて、
 「映画とかに出てくる中世の古文書かと思った」
 といわれた...
579デフォルトの名無しさん:03/11/13 00:12
実稼働日数を計算するアルゴリズムを教えてください。

実稼働日数 期間中の休みの日を抜いた日数


開始日と終了日を設定する
開始日 2003/11/15
終了日 2003/11/20

この場合、日数は、15,16,17,18,19,20で6日間だが
16は休みのため実稼働日数は5日とする

休日はカレンダー通りではなく、休日テーブルから参照する。
開始日、終了日が休日であれば
開始日 翌日の稼働日(翌日も休みであればさらに次の日)
終了日 前日の稼働日(前日も休みであればさらに前の日)

休日テーブル
2003/11/02
2003/11/09
2003/11/16
2003/11/23
・・・

開始日から終了日までをカウントアップしていき、毎回、休日テーブルと比較すれば簡単なのですが、
もうすこし、効率の良い方法はないでしょうか?

こういうことを聞いても良いスレですよね?
580デフォルトの名無しさん:03/11/13 00:32
>>579
問題の対象の実装方法や大きさにもよるが、一番汎用的で高速な方法は、
まず日付の差を計算する関数と、指定された日付の範囲のレコードを
休日テーブルから拾い出す関数を用意して、

実稼動日数 = 終了日 - 開始日 - 開始日から終了日の間の休日の数 + 1

で出せばいいんじゃないの?
>>578
Open hashing は Aho, Hopcroft, Ullman らしい。
582579:03/11/14 00:42
>>580

なるほど、簡単に求められるんですね。
ありがとうございます。

開始日から実稼働日数で○日後は、
何月何日になるかを求める場合はどのようにするのでしょうか?

開始日 2003/11/15
実稼働 10日後を求める
11月
15,16,17,18,19,20,21,22,23,24,25,26・・・
1 X 2 3 4 5 6 7 X 8 9 10 日後

この場合は、終了日 2003/11/26 とする。
ただし、終了日が休日の場合は休日でない日まで日数を足す。

こんな風に考えました。

1) 11/15に10日足して1日引く11/24
2) 11/15と11/24の間にある休日件数を >>580でも求める
3) 16,23が休日なので、 2日足す。
4) 終了日 11/26 が求まる。

で良いと思いましたが、実稼働日が大きな数字の場合、
3)で足した分に休日があるとその分を再度足さないといけない。
その休日分をたしたら、またその休日分をたす。
というのを繰り返さなくてはいけないと思います。

どのようにすれば効率よく計算出来るのかお教えください。
お願いいたします。
>>582
2つテーブルを用意する。
Aは1/1からの実稼動日数を日付で引けるもの。
Bは日付を1/1からの実稼動日数で引けるもの。

1) Aを使って開始日の1/1からの実稼動日数を求める。
2) 1)で求めたものに実稼動日数を足す。
3) Bを使って2)で求めたもので日付を求める。
584デフォルトの名無しさん:03/11/17 02:39
Yahoo!とかであるような、
「トップ > インターネット > ホームページ作成 > ソフト」みたいな階層は、
どうやってテーブル設計すればいいのでしょうか?
>>584
各項目にIDを振って、自分の親になる項目を親IDとして登録しておけばいいのでは?

ID 親ID 項目
1 null トップ
2 1 インターネット
3 2 ホームページ作成
4 3 ソフト

親IDがnullのときはトップ階層ということで.
586579:03/11/17 23:59
>>583

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

>Aは1/1からの実稼動日数を日付で引けるもの。
>Bは日付を1/1からの実稼動日数で引けるもの。

ここがよくわからないです。
お手数ですがもう少し説明していただけませんでしょうか?
587583:03/11/18 02:19
>>586
2004年1月で仕事始めを5日、日祭を休日とすると
Aのテーブルは
1/1→0 1/2→0 1/3→0 1/4→0 1/5→1 1/6→2 1/7→3
1/8→4 1/9→5 1/10→6 1/11→6 1/12→6 1/13→7 1/14→8
Bのテーブルは
0→1/1 1→1/5 2→1/6 3→1/7 4→1/8
5→1/9 6→1/10 7→1/13 8→1/14

開始日1/6で実稼動日数6日の終了日は?
1) 1/6 → 2
2) 2 + 6 - 1 = 7
3) 7 → 1/13
となり、終了日は1/13。
hiduke=kaishibi;
while(kadoubi-->0)
while(oyasumi(hiduke=tsuginohi(hiduke))==TRUE);
589デフォルトの名無しさん:03/11/18 08:45
>>587
Aのテーブルは文字列をキーにした連想配列か?
590デフォルトの名無しさん:03/11/18 08:46
>>587
その方法で2003年12月15日から
2004年1月15日までの実働日数計算できる?
休日が始点として指定されたら直後の平日が指定されたものとみなす。
休日が終点として指定されたら直前の平日が指定されたものとみなす。
というルールを前提にするならば587は間違いを含む
592583:03/11/18 09:40
>>589
二次元の配列を休日テーブルの年数分用意する。

>>590
年毎にAのテーブルを作れば
2003年の総実稼動日数 - A2003[12][15] + A2004[1][15]
で求まる。(±1は適当に)

>>591
Aのテーブルに休日かどうかを含めといて、
開始日が休日なら1を足さない。

正直、>>591は考えてなかった。
毎年ソース修正とかは痛いな。
同じソースで長期的に使えた方がいい。
あと、わざわざテーブル作る必要性が見えない。
テーブル作るときに使う計算式をテーブル使うときに使えばいい。
594583:03/11/18 12:09
>>593
> 毎年ソース修正とかは痛いな。
> 同じソースで長期的に使えた方がいい。

プログラムの頭で休日テーブルから生成するなり、
予め別ファイルに2つのテーブルを用意しておいて読み込むなりする。

> あと、わざわざテーブル作る必要性が見えない。

>>582の「効率よく計算出来る」をもう少し突っ込んできいてないんで、
効率がいいかどうかは不明で、必要性があるかはわからん。
テーブル作る手間を言及しないことで、効率よさそうに見せようとはした。

> テーブル作るときに使う計算式をテーブル使うときに使えばいい。

テーブルを作るときに使う計算式はより簡単なものにすることができる。
595デフォルトの名無しさん:03/11/18 13:08
そのアルゴリズムを選択する妥当性を疑う
なにより美しくない
596583:03/11/18 23:38
>>595
妥当ではないかもしれませんなぁ。

終了日の計算の回数が多ければ効率がよくなるのですが、
579さんは複数回計算するとはいってないですし。
597579:03/11/19 00:17
レスありがとうございます。

>>>582の「効率よく計算出来る」をもう少し突っ込んできいてないんで、
>効率がいいかどうかは不明で、必要性があるかはわからん。

休日テーブルの条件として
 文字型としてデータベースに日付が格納されている。(べつに日付型でも可) 例) 2003/11/23
 常に昇順にソートされている状態である。
 毎年1月に翌年の情報が確定しデータを訂正する。
 未確定のデータとして2年分の祝祭日が登録してある。
 (1月の確定時に訂正及び追加する)
となっていています。

簡単の方法として(概略ですが)
 開始日を入力する。
 実可能日を入力する。
 終了日 EndDate に開始日を代入する。
 カウント変数 i に実可能日を代入する。
 休日テーブルとEndDateを比較しEndDateが休日か判定する。
  (休日テーブルのStart位置を初回に調べる、その後は、次の値との比較)
 休日の場合は、EndDate+1
 休日ではない場合は、Enddate+1,i-1,休日テーブルを次の行へ
 iが0になるまで繰り返す。
というのは考えたのですが比較のためにループするのが美しくないと思いました。
休日テーブルからの読み込みは、オブジェクトとして
初回に変数に読み込むことでオーバーヘッドを減らしてスピードを上げるつもりですが、
何かもっとうまい方法があると思いました。

>579さんは複数回計算するとはいってないですし。
手配時の納期計算です、複数回計算すると考えてください。
598デフォルトの名無しさん:03/11/19 10:10
DBに入れてるならindex引けばいいんじゃない?
休日テーブルのソートなんて利用者が関与することじゃないし
599デフォルトの名無しさん:03/11/19 23:21
1つ質問させてください。

今、巡回セールスマン問題の解法としてよく使われているアルゴリズムにはどういったものがあるのでしょうか?
よく教科書に載っているダイクストラ法などは今は全く使われていないのでしょうか。
質問ばかりですみませんが、よろしくお願いします。
ダイクストラと言えば、最短路木をgreedyに求めるやつじゃなかったっけ。
巡回セールスマン問題は近似解法を使って解かれることが多いと思う。
601デフォルトの名無しさん:03/11/20 01:17
>>599
あんまり詳しくないけど、遺伝的アルゴリズムがいいと本に書いてあったよ(受け売り)
602584:03/11/20 02:17
>>585
亀レスですいません。

もしそれだと、5階層目のページを表示する場合、
5回SQLを回さなきゃいけなくなりますよね・・・。それだと負荷がきついのかな?と思うのですが、どうでしょう?

あるいは、図書館みたいに、10進法分類を使うのも手なのかとも思ったのですが。。。

定番のセオリーみたいなのは、特にないんでしょうか?
null window search

について解りやすぐご説明ください。
絶対に失敗する探索というのが意味不明で難解で
非現実的でわかりません。
604デフォルトの名無しさん:03/11/20 09:41
ツリー構造で子孫側に探索するのをO(n)未満に抑えたいということか。
擬似ツリーにすりゃいいんじゃない?
>>603
それ単独で使えば必ずフェイルハイかフェイルローが起きる
606584:03/11/20 19:32
>>604
すいません。
O(n)と、擬似ツリーの意味を教えていただけませんでしょうか?
前者はググりようがなく、後者がググっても6件のみで、ページを見ても意味がわかりませんでした。
>>606
Oはオーダーって読むんだよ。
>>606
前者に関しては「計算量 オーダー」なんかでググればいいんじゃないかな
後者は俺もわからん。どういう文脈で使われていたんだろう
609604:03/11/20 23:59
AI関係のアルゴリズムで null window searchだけが
解ら無いのですよね。
a-b法の上を行くという説明だけで
実際にわかりやすく説明してくれる文献・HPが無いんですよね。

すげーくやしいです。
>>609
null window searchで検索して一番目の所の説明で十分詳しいと思うけど。
611604:03/11/21 00:33
>>610
カレー温泉さんですよね。
ディスプレイが焦げるほどに読み返してはみたのですが…

自分の頭の中で何か思い違いをしていて
それが引っかかって理解出来ないのだとは思うんですけどね。

今はあきらめるしか無いですね。
アルゴリズムを理解るには頭をやわらかくしないと駄目ですよねぇ。
柔らかく柔らかくです。
612584:03/11/21 02:05
>>607-608
ありがとうございます。O(n)の意味は分かりました。
でも、疑似ツリーの意味は分かりません。。。

いわゆるぱんくず(トップ > ネット > 2ch > はげ板)を生成するとき、
みんな、どうやってるんだろう。。。
613デフォルトの名無しさん:03/11/21 12:17
ハッシュドビーフとハッシュって何か関係あるのか?
>>613
ハッシュ(hash) は「細切れ」の意

牛肉を細かく切るから、ハッシュドビーフ
値を(一見すると)ばらばらに変換するから、ハッシュアルゴリズム
T○SHIBAの魔方陣アルゴリズムってなんですかぁー
>>615
魔方陣っていうくらいだから
縦横斜めどこ足しても同じ数字なんじゃね?(w
>>616
テレビの液晶画面のどこに数字を
>>615
東芝は魔法陣だろ?
画像処理のアルゴリズムらしいが、詳細は機密事項かなぁ。
家電は愚民相手の商売なので変らぬ商品を目新しく見せようと
宣伝文句を作るだけが多いので気をつけてね。
古くはニューロやAI、ファジー、1/f などなど。
(カテキン、マイナスイオンもそれ系)
なんと。企業に踊らされている可哀相な漏れ。
621デフォルトの名無しさん:03/11/23 22:33
xy 平面上に複数(十個〜数十個程度)の点があるとき、それに外接する最小の長方
形を求めるにはどうすればよいか、お教えいただけないでしょうか?
もちろん、長方形の4辺がxy軸に平行にならなくてもOKです。

「最小」の定義は、面積が最小、または、4 辺の長さの合計が最小、のどちらでも結
構です。(どちらがふさわしいか、今は決めかねているので・・・)

よろしくお願いします。
Oriented bounding-boxの二次元版って事か?
>612
ttp://www.sitepoint.com/article/1105
とか読んでみるといいかも。読んでないので内容は保証しないけど。
624621:03/11/24 11:30
色々と考えまして、結局、以下のようなやり方を試すことにしました。

- 与えられた点を P1,P2,・・・,Pn とする。
- 直線 y = ax を与え、P1,P2,・・・,Pn をこの直線上に投影して、その点を Q1,Q2,・・・,
 Qn とする。
- Q1,Q2,・・・,Qn を結んで作られる線分の長さ L を求める。
- 直線の傾き a を色々と変えて、それぞれの場合の L を求め、最小の L が得られ
 た時の a を、長方形の短辺の傾きとする。
- あとは、得られた傾きを元に長方形を求めるのみ・・・。

ホントにこれで欲しい長方形になるのか?
効率悪いんじゃ?
という疑問が残りますが、とりあえずこれで逝ってみます。
>>624
最小の長方形を得られるaの傾きの場合、
必ずaに投影する、ある2つの投影直線が重なるような気がするから
それを元に出してはどうだろう?

重ならないかもしれないけど
凸閉包を求めたらいいと思いますが
>>618 いちおう魔方陣らしい
http://www.toshiba.co.jp/product/tv/beautiful/fdp/index02.htm
> 魔方陣と呼ばれる数列に従って画素の明るさを処理することで、
> 画素データの偏りを防ぎながら、なめらかな階調表現を実現しました。
>>627
な、なんだってー(AA略

つーか、それってずいぶん昔に提案された平滑化アルゴリズムじゃないか?
実用的にもっとよいものはたくさんあると思うが…
630デフォルトの名無しさん:03/11/28 03:28
>>621
これでどうよ?

与えられた点の集合より、凸包を求める。
凸包の各辺に対し、
{
与えられた点の集合より、その辺を x 軸座標とした際に、
min( x ), max( x ), max( y )
なる点を見つける。
発見した点と辺(の1点)より長方形を求め、面積を求める。
}
計算した面積の組の中から最小の組を発見する。
631630:03/11/28 03:42
>与えられた点の集合より、その辺を x 軸座標とした際に、
あ、ここを「凸包を構成する点の集合」にすれば、多少早くなるか・・・
632デフォルトの名無しさん:03/11/28 20:39
※エレベーターシミュレータ

デパートなどにあるエレベータをシミュレートします。
各階には時々客が訪れ、(希望の行き先の階を指定する)エレベーターを呼ぶ
ボタンを押します。
客はその階で最初にドアを開いたエレベーターに必ず乗り込み、その後
希望した行き先の階でドアが開けば、勝手に降りていきます。

どのようなアルゴリズムであれば、客が現れた後、希望する階に降ろすまでに
かかる(客全員の合計の)時間を減らせるでしょうか?

条件:
建物は10階建て
エレベーターの設置数は3基
一台のエレベーターに乗り込める人数の制限はない
エレベーターが次の階へ移動する時にかかる時間は3秒
エレベーターのドアの開閉にかかる時間は計2秒(開:1秒・閉:1秒)
客がエレベーターの乗降りにかける時間は考慮しない(0秒)
各階に新規の客(一人)が訪れる確率は 5% /秒
エレベーターは移動途中に方向転換しても良い(5階へ移動->4階へ移動->5階へ移動)

初期状態:
エレベータの位置は全て1階、客はいないものとする
633デフォルトの名無しさん:03/11/28 20:51
>>632
ニューラルネットワークとかGAとかベイズとか使って実行時に最適化させちまえ。
そのほうが確実に待ち時間が短縮されるぞ。
>>633
なんか「とか」って辺りが、やけに馬鹿っぽい・・・
635621=624:03/11/28 23:13
621です。

当方からの反応がしばらく無かったにもかかわらず回答をいただき、ありがとうございま
す m(. .)m。

>>625
> 必ずaに投影する、ある2つの投影直線が重なるような気がするから

すみません。イマイチよく理解できないのですが・・・。
重なるような投影直線とは、長方形の頂点を通る直線のことを言っておられるのでしょう
か?
そうだとすれば、オリジナルの点集合の中に、必ずしも長方形の頂点が含まれるわけでは
ないので、うまくいかない場合が出てきてしまいます・・・。
636621=624:03/11/28 23:14
>>626
ふむ、凸閉包、ですか。
626 さんの書き込みを見るまで、このような言葉があることさえ知りませんでした。
勉強になります。

>>630
ふむふむ、なるほど。何だかよさそうですね。

ただ、気になるのは、630 さんの考え方だと、
「求める長方形の一辺と、凸包の一辺とが、必ず重なる」
ことを前提としていますよね。

でも、凸包の辺と、解となる長方形の辺とが、全く重ならないような場合(つまり凸包の
頂点が長方形の辺に接するだけの場合)というのはありえないのでしょうか?

そのような場合がありうるのかどうか少し考えてみたのですが、不勉強ゆえ、よくわかり
ませんでした・・・
>>632
エレベータが知りうる情報がわからない。

・今乗っている客と、その乗った階と希望行き先階
・各階で上下する客がいるかどうか

だけが知っている情報ということでよろしいか?
638632:03/11/29 03:02
>>637
・今乗っている客の行きたい階
・各階でエレベーターが来るのを待っている客が行きたい階
です。

2つとも客が現れた時点で知ることができます。
>(希望の行き先の階を指定する)エレベーターを呼ぶボタンを押します。
639632:03/11/29 03:17
各階ごとに1−10までのボタンがあり、その情報だけが分かる、と言えばよいでしょうか?
(同じ階へ行きたい客が複数現れた時はボタンが複数回押される)

客が待っている階についてエレベーターのドアを開ければ、
・この階に降りる予定だった客が全て降りる
・この階で待っていた客が全て乗り込む

この時点でこの階のボタンの押されていた数で、今乗り込んだ客がどこで
降りたいかを把握できます。
>>632
待ち行列の応用か、実行時最適化問題か。
いずれにしろ、>>633 の解で正しいのか。
>>640
>いずれにしろ、>>633 の解で正しいのか。
お前、自分で分からない問題は全部、 NN とかに突っ込めば
正しい解答が出てくると思っているだろ。
>>641
NP問題だから、正しい答えを出すのは、現実的には不可能だろう。
だから、GAとかで解くのが考えられる。
しかし、静的な問題ではないため、NNがよいと思われるが、いかが?
643デフォルトの名無しさん:03/11/29 10:03
過去の一時的な特異な例でおかしな学習をし
それによってそれ以降の成績が落ちるのは良くあること。
数学的根拠のある動作をするわけではなく
井の中の蛙状態のエレベーターが
過去の少ない経験に基づいて動作してしまう場合、
常に平常状態で状況の分散が小さく、
わずかな時間で学習が完了するならばうまくいく。

>>632
客の嗜好の平均状態が条件に無いので計算不可能では?
1階から乗った客の40%は3階に降りる、20%は5階に降りる
残りの人数は残りのフロアに同じ確率で降りる、など。

> 各階に新規の客(一人)が訪れる確率は5%/秒

これは何分布で?まさか一様とかいうんじゃないだろうな。

だいたい「人数の制限なし」「乗り降りにかかる時間なし」
なんてエレベーターをシミュレーションしても
何の役にも立たないし面白くもない。
>>643
>だいたい「人数の制限なし」「乗り降りにかかる時間なし」
>なんてエレベーターをシミュレーションしても
>何の役にも立たないし面白くもない。

問題にけちをつけるならば、最初から相手にしなければいいじゃん。
気持ちはわかるけど
>>643
お前、小学校の時

「りんご2個とみかん3個を合わせると何個になりますか?」

という問題が出たら、

「りんごとみかんは違うものだから足せません」

って言い張るタイプだったろ?
>>636
>でも、凸包の辺と、解となる長方形の辺とが、全く重ならないような場合(つまり凸包の
>頂点が長方形の辺に接するだけの場合)というのはありえないのでしょうか?
数学板に聞いてみるか・・・
http://science2.2ch.net/test/read.cgi/math/1069691754/569
647デフォルトの名無しさん:03/11/30 00:16
魔方陣アルゴリズムってどんなの?
先生!リスト構造を
単純選択法でソートする
アルゴリズムがわかりません。
650621=624:03/11/30 02:09
>>646
おおお、どうもありがとうございます!

数学板、読んでみました。
「辺を共有しない長方形を最小長方形だと仮定すれば矛盾が生じる。ゆえに、最小長方形と
凸包は必ず辺を共有する」
ということですね。

お陰で解決できました。助かりました!
651デフォルトの名無しさん:03/12/02 05:36
電波受信するときとか、反射とかして
似たような波を2つ3つ受信しちゃうのを
フィルタかけて1つの波に合成する
そのフィルタの名前ってなんだっけ?
にちゃんねる厨房フィルタースペシャル。
>>651
エコーキャンセラ?


検索したら、この語は、
音声の出力→入力エコーの除去しか認めてもらえないようだけど
654デフォルトの名無しさん:03/12/03 02:46
輪投げ選択って、どのように作るのでしょうか?

複数の点の内、ユーザーがドラッグで囲って作った輪の中
に入っているものだけを選択状態にしたいのですが、やり方
がわかりません。点やマウスの座標はわかるのですが、輪の中に
入ったかどうかをどのように判定するのでしょうか?
>>654
輪が閉じており、かつ交差していないという条件のもとでとりあえずぱっと出てきた方法。

点からどの方向でもいいんで半直線を引く。
輪と交差した回数が奇数なら輪の内側、偶数なら輪の外側。
「輪と交差する」の判定がドラッグで囲った輪だとちとつらいかもしれない。
多角形ならやりやすいだろうけど。
点が多いならラスタスキャンみたいな感じで走査した方が早いかもしれない。
ドラッグした人間の目に滑らかに見える線でも、結局は多角形でしょう。
多角形の内・外判定そのものでは?
内・外判定には2種類ありますが、どちらもコーデング上はほぼ同じです。

そのオブジェクトが点でない場合、輪の上にある時にだけ少し問題が出るでしょう
でも、
 オブジェクトが収まる円か四角形で代用すれば実用的には十分では?
657654:03/12/03 13:27
>> 655
すごい!ナイスアイディアです!

>> 656
「[多角形の内・外判定」
これって、私は知らなかったんですが、検索したら
出てきました。どうやら655さんのおっしゃる方法も
「交差回数法」として提唱されているようですね。

御二人方ともどうもありがとうございました。
このスレは勉強になるな
上下左右連結型マップのシューティングゲームの当たり判定で、
例えば、縦横256のサイズのマップ上に、
left=250、top=250、width=16、height=16のオブジェクトがいた場合、
left=250、top=250、right=255、bottom=255と、
left=0、top=0、right=10、bottom=10と、
left=250、top=0、right=255、bottom=10と、
left=0、top=250、right=10、bottom=255の、
4つの矩形に分けて当たり判定をする方法しか思いつかないのですが、
何かいい方法があったら教えてください
片方の座標系に連続的になるように、変換したらいいんでないかな?
手間は似たようなものかな?

つまり自弾の origin が画面右上 ( 252, 4 ) にあって、敵がそんな風にまたがっていた場合、
敵矩形を (250, -6) - (266, 10) に取る。
判定は一回で済む。
どのみち表示のためには最大4つの分身を用意しなきゃいけないわけだから、
そのうちのどれと判定すれば言いか調べるってことにはできないか。
661659:03/12/05 15:12
>>660
理解しきれてないんですが、
自弾の位置によって、敵矩形の座標を変換(256足したり、引いたり?)するって事ですよね?

どのように実装すればいいですか?
>>661
モジュロして判定すりゃいいんじゃないか?
663659:03/12/05 16:17
>>662
うーん、やはりよくわからないです

上下閉鎖左右連結の場合

if(a.right>mapWidth){
if(b.originX<mapWidth/2){
a.left-mapWidth;
a.right-mapWidth;
}
}
// ここでaとbを当たり判定

というようなイメージなのですが、間違っていますか?
>>663
そんな感じだね。
要はさ、テスト用のアプリケーションを作ってみればいいんだよ。
画面用意して、いろんなとこに敵配置して、マウス押したら「どーん」「すか」と表示するだけのもの。
665659:03/12/05 18:42
>>664
なるほど
試してみます

教えてくれた方々、どうもありがとうございました
666デフォルトの名無しさん:03/12/06 23:59
基数ソートはO(n)のはずなのに、C言語で整数乱数1000万件とかで試しても、
単純な再帰型のクイックソートよりなかなか速くできません。
なんかいいテクニックないでしょうか?
純粋でなければ他のソート法とくみあわせて速くできるのは知っている
のですが、とりあえずオーダーが違うというのを実証したいんです。
>>666
>単純な再帰型のクイックソートよりなかなか速くできません。
お前の基数の設定が悪いだけ。
基数は256とかだったんだが、桁をとりだすのに
変数に除数を入れて割ってたのがいかんかった。
素直にシフトにすれば速くなりました。
2の羃の除算なら、賢いコンパイラならシフトに
してくれると思いこんでました。
>>668
変数に除数を入れて…って事は、int x=256; v=v/x; とかいう形でしょうか。
ならまず最適化は無理でしょう。よほど直前でxを宣言してやるか、
constみたいな形で定義していない限り。
ハッシュ法の概念はわかっているんですけど、具体的に文字列をキーとした
ハッシュ配列みたいなものを作りたいときには、どのようなハッシュ関数を
使うのが一般的なのか教えてください。
スレ違いだと思うけど質問させてください。
CRCとかMD5とかをプログラムに組み込んだんですけど、
こういうアルゴリズムのライセンスってどうなってるんでしょうか?
GIFの圧縮アルゴリズムの件とかあるんで調べたんですけど、
俺には見つけられなかった。ご存知の方いませんか?
>>670
できる限り衝突の少ないハッシュ関数、としか言いようがないんじゃないかな。
基本的にハッシュ関数の評価は入力データに依存するわけで。
キーとする文字列がランダムな文字列なのか英単語なのか、英単語でも何か限定された範囲の単語なのか、とか。
もっともあんまり凝ってもしょうがないので、N を適当な定数として

char *p; int hash=0;
while(*p!=0) hash=hash*N+*p++;

みたいなのがありがちだと思う。

完全にキーが決まっている場合は、gperf というのを使うと完全ハッシュ関数ができるらしい…が
使ったことないのでよくわかんない。
ttp://sharl.haun.org/gperf.html

>>671
MD5 は RFC1321 で定義されており、RSA Data Security によるリファレンス実装がついている。
で、著作権表示を行う or 派生物であることを明示すれば利用 OK。
一応 RFC を確認してくれ。

CRC の方は正直考えたことなかった。
ISO 3309 で規定されてるらしいけど、そこにライセンスについて書いてあるのかとかこれ以上はちょっとわからん。
673671:03/12/08 18:49
>>672
ありがとうございます。調べてみますね。
>>668
> 2の羃の除算なら、賢いコンパイラならシフトに

わりこんでごめんなさい。
羃ってなんと読むのでしょうか
べき
ヲヰラが勘違いしているのかもしれませんが、
>>666 「とりあえずオーダーが違うというのを実証したいんです」
ということですが、>>668 みないな納得のしかたでは「実証」したことに
ならないとおもうんだけど。

「1000万件」ぐらい多くなると、log(N)はほとんど動かない(定数)ので、
O(NlogN)とO(N)の違いは現れないのが正解じゃないかと思います。
というか、だからこそ、O(NlogN)のありがたみがあるというか...
677デフォルトの名無しさん:03/12/16 10:00
アルバイトやパートタイマーの勤務シフトを自動作成するようなものを作りたいんだけど、
どういうアプローチをすればいいかさっぱり思いつかない
市販品は何種類か出てるし、Excelのマクロのようなものもあるみたいなんだけど、
どうやったらいいものやら・・・。
総当り的なやり方をするにしても漏れの脳みそでは最初のとっかかりすら思い
つかないよ(´・ω・`)ショボーン
ひとまずは個人個人を与えられた条件で振り分けて最後に微調整で済むものを作って、
最終的にはグループ単位でのバランスも考慮しながら自動作成出来るようにしたいです
人数とかにもよるけど、総当たりは現実的じゃないかもしれない

どうせ全員の希望が完璧には満たされないのだとすると、
ある配置の評価値を得るような評価関数を設けて
評価値を最大にするようなアルゴリズムを作ることになる。

問題は、
・「配置」をどう表現するか
・従業員・事業所の希望を含めた評価関数をどう作るか
・どうやって評価値を最大化するような「配置」を得るか
に絞られる。

「配置」の表現が決まれば、なにを重視するかという重みづけの問題はあるが、
評価関数はある程度作れる。
最大化するためのアルゴリズムはいろいろあって、
こういう「配置」最適化問題の場合は遺伝的アルゴリズムがいいかもしれない。
「配置」の表現方法がたぶん一番の問題。

ちゃんとしたのを作れば、売れるかもよ。
ただ、評価関数のいろんな要求条件があるから、一般化が難しそうだけど。
というかまず問題設定も晒してないのに
データ構造もアルゴリズムもないんじゃないか、>>677

たとえば、
「4人の人間に対して
 一週間周期で、1日16コマ×7週/日をどう振り分けるか。」
みたいな提示がないとどうしようもない。

その上で、
たとえば評価関数を使った最適化をするなら
入力値にあたる変数として
・個人レベル
「自分の担当する総時間数」
「連続するコマ数の最大値」
・集団レベル
「一人一人のコマ数の分散」
みたいなものを要求に応じて切り出す(これもケースバイケース)
ところから始める必要がある。

「この人はこの時間は絶対駄目」とか
「この人はこの人といっしょに組ませられない」、
みたいな要求は論理パズル的な分野に行くから
数値的な最適化手法よりも
バックトラックを使うとかprologを選択するべきだし。

ある程度現実的な問題を扱うとなると第一にモデル化が重要。
シミュレーションや最適化問題に関する本を
きちんと待ち行列に関する話題なんかから辿ってみた方が
具体的な方向性が見えてくると思うよ。
680677:03/12/16 13:21
>>678 >>679 ありがとうございます。
軽く考えてたのですが実は相当奥の深そうな問題なんですね。
参考書籍としてお奨めのものがあれば教えてください。
681679:03/12/16 15:02
書き込みをみる限り君の想定は
最適化よりも論理プログラミングの側ように思えるからな。
残念ながらそっちは俺はあまり知らない。
「バックトラック法」をキーワードにいろいろ調べてみてくれ。
コンピュータパズルの本なんかがわかりやすいかと。
あとは人工知能とprologの本をみれば似たような作業、
つまり複数の制約条件満たす解を順に探索する実例には困らないと思う。

というかとにもかくにも自分の対象とする問題と使用する手法が
どういったものに近いかを実例を当って確定させてくれないと
それぞれの手法に詳しい人でも今はこれがいいとは答えられないよ。
まずは自分で手当たり次第当ってみるべき段階だ。

まあどうしてもそうした問題に包括的に詳しい人に
あいたいのならシミュレート板で聞いてみれば
運がよければ3か月くらいで返事がもらえるかも
>>677
なんかそれ面白そうだから、ぜひ具体例を晒してくれ。
作ってみたいから。
>>677
昔、大学や高校の時間割を作成するといったらかなり難しい問題の部類にはいってたね。
最近のその方面の進展にうといのだけど、パソコンでも解けるようになったのかな?
一般には「スケジューリング」と呼ばれる問題だと思うんだけど、googleで探すと
CPUの命令スケジューリングが多くひっかかる。

時間割 アルゴリズム で索くといいみたい。遺伝的アルゴリズムを使ったのが目につくね。

スケジューリングだと
工場の生産システムなんか具体例として結構見るね。

作業の請負もとが人間だと要求の形がさまざまだから
バックトラックなんかよりニューラルネットとかの方が向いているかも。
数値化の方法と重み付けが悩ましいところだけど
最適割当問題だね。問題サイズが小さければ、GAとか
ニューラルネットとか使わなくても解けるよ。
ネットワークフローの最適化問題に還元できるとオモタ。
686677:03/12/17 18:41
みなさんいろいろとどうもです。
もともとは配送センターで働いてる友人からそういうものは出来るのかと酒の席で
聞かれた程度で具体的な条件や仕様もまだ何も無い段階ですし、単に私が興味を
持っただけなので先方から勤務形態や細かな条件を指定されたわけではないです。
私自身プログラムの勉強を初めて間が無いですし、一般的にはこんな処理をする
というケーススタディをいくつか出来ればありがたいなと思ったもので、
>>679氏や>>682氏には申し訳ありませんが、具体的なケースはむしろ私の方が
教えてもらいたいといった状況なんです、すいません。
687677:03/12/17 19:18
ただ、その話の中で出てたのは、3交代制(2交代も言ってたかも)である。
よく働く奴とあまり働かない奴を適度に混ぜて、リーダー格の奴は適度に
配置して欲しい。各人は都合の良い日や悪い日、都合の良い日でも昼だけとか
の条件をそれぞれ持っている。週に1日だけバイト等の極端な条件の人物を
除いては勤務時間がそこそこ均等になるようにしたい。
働き具合だけでなく、入荷チェックやフォークリフト操縦の出来る奴等を
上手に配置して仕事に必要な機能が欠ける事の無いようにしたい(それは
各機能について一人ずつ必ず配置するということではなくて、一人でいくつも
役割をこなせるなら一人か二人いればまぁ我慢できるということらしいです)
仲のいい悪いもほんの少しは考慮する。

今のところ思い出したのはこれぐらいの条件だったような気がします。
グループについてはどういうグループなのかよく覚えてなくて、なんか知らないけど
とにかくグループ間での偏りがないようにと言ってたような・・・
688677:03/12/17 19:21
あっ、それと曜日や時間帯や時節によって必要な人数が違うとも言ってました
689677:03/12/17 19:45
すいません、条件さらに追加です。
夜勤や日勤ががあまり連続しすぎないように。
夜勤から日勤への連続は禁止(そりゃそうですね)
最低でも週に1日は休みが取れるようにしたいので勤務日が連続しすぎない
22世紀は
家内制手工業が
ス−パ−トレンディ−
691デフォルトの名無しさん:03/12/18 21:32
日本人全員のデータベースがあったとして、各個人には
名前とその人の知り合いリスト(名前の配列)が登録
されているとします。

僕と小泉首相は直接の知り合いではありませんが、
知り合いの知り合いを辿れば、小泉首相までたどり着くと
思います。(Six degrees of separation)

「僕から小泉首相」と指定したときに、僕から小泉首相まで
最短でたどり着く、知り合いリストを抽出したいのですが、
総当り以外で何か良いアルゴリズムはあるのでしょうか?

 僕 - Aさん - Bさん - Cさん - 小泉首相

上の{Aさん, Bさん, Cさん}を抽出したい。
>>691
大工すとら法じゃないのかね?

でも全ての枝の重みが等しいから、両側からダイクストラ法でラベル付けして、
ぶつかった所の値で終了、とかの方が早そうだけど。
というか重み付けないのにダイキストラ?
幅優先探索で十分じゃない
つーかこの問題に対する期待から言うと
1.数回で探索は終了する。
2.名もない小市民より小泉を根とするノードそれぞれの方がよっぽど子の数が大きい。
この2点から>>692の案は何ら高速化にならないんじゃなかろうか
ああ、1.の書き方は問題があるな。
数回ってのは深さのことだ。
一人当たりの子の数がよっぽど大きいから
この結果が生まれるわけで。誤解が生まれたらスマソ。

ともかく幅優先探索で下って最初に見つかったのが答え。
ただし同じ深さに複数の解がある場合それを取り出したいのなら
その深さまでの探索は継続するべき。

目的のノードにたどり着いたらそこから
探索木中での親のノード(記録しとけよ?)を辿りながら
戻ってそれをリストに追加していけばいい。
ちなみに解が入る経路は深さがわからないから
可変長配列かリストを用意しておけ
696691:03/12/19 00:15
>>695
とっても参考になります。

これから、持ってるアルゴリズム本で「幅優先探索」を調べてみます。
「ダイクストラ法」については調べてみたのですが、確かに重み付けが
ないと意味がないような気がします。
697デフォルトの名無しさん:03/12/19 00:19
HTMLで、
<ul>
 <li>1
  <ul>
   <li>2</li>
   <li>2</li>
  </ul>
 </li>
 <li>1</li>
</ul>
のように、ネストされた階層を作りたいと思っています。
そして、
各行の階層だけは、以下のようにデータとして取得できてるのですが、
1
2
2
3
4
3
3
2
1
ここから、<ul>のネストされたhtmlをはき出すには、
どんなアルゴリズムを考えればいいのでしょうか?

なお、上記例から、生成を手作業でやると、↓こんなかんじです
http://31.com/test/ultest.html

どなたかお助けいただければ幸いです。
>>697
一言「再帰」
前の行の数字よりも大きければ差の数だけ<ul>を出力、小さければ</ul>を出力…

ではダメ?アルゴリズムって言うほどのものではないけど。
700
701697:03/12/19 00:58
>>698
いやぁ、再帰だということはわかるんですが、どうやって再帰すればいいのかが分からず。

>>699
それをやると、自分の考えだと(勘違いしてるかもしれませんが)、
</li>をどこに入れるかのアルゴリズムが分からないんですよね・・・
下の←の</li>が・・・

<ul>
 <li>1
  <ul>
   <li>2</li>←
   <li>2</li>←
  </ul>
 </li>←
 <li>1</li>←
</ul>
>>701
<li>を出力した後で呼び出した再帰から戻ってきたとき(あるいは再帰の必要の無かったとき)に決まってるじゃん。
まずいいから書いてみな。書いてみたらコツがつかめる。
703697:03/12/19 01:11
書いてはいるんですけどね、あたまわりーな自分(泣)

>>702さんありがとうございます。これから試してみます。
>>703
要するに 1対1になってるときは同じ階層で、
1対他になってるときは下の階層で。
これだけ守れば大抵うまくいく。

ただし「下位が無いときは改行しない」とか例外を盛り込むとうまくいかないこともある。
それは HTML の表現の自由度に妥協するとかの逃げ道もある。
先に予測・設計できるといいんだがね。
705697:03/12/19 01:53
php4とMySQLなんですが、
$sql = "SELECT categoryid, lft, rgt ,categoryname,categorytitle, flagcategorytree FROM categorymaster ".
"WHERE lft BETWEEN $row[lft] AND $row[rgt] ".
"ORDER BY lft ASC";

$rs = pg_query($con, $sql);
// display each row
while ($row = pg_fetch_array($rs)) {
//$row[lft] AND $row[rgt] から、階層度を取得(略)
  ★ここの中身で再帰しようとしてた
}

っていう風に、再帰してる中で再帰しよとしてるから、こんがらがってしまっているようです。

>>703の方法もいろいろに解釈してトライるんですが、必ずずれてしまう。。。どうしたものか。
ちなみに、冒頭のSQL文は、
カテゴリ構造を保持する方法という、
このスレの>>623さんが教えてくださった
「Storing Hierarchical Data in a Database」
ttp://www.sitepoint.com/article/1105
をそのままもってきました。
706デフォルトの名無しさん:03/12/19 13:02
マージの処理で質問なのですが3つ以上のテーブルを1つにマージする場合は
 SrcA[] + SrcB[] → TmpA[]
 SrcC[] + TmpA[] → TmpB[]
 SrcD[] + TmpB[] → Dst[]

・・・というように2つずつマージしていくしかないのでしょうか?
3つ以上のテーブルをマージする良いアルゴリズムがあれば教えて欲しいです。
アルゴリズムゴルゴリズム 
早口で10回癒え
ここでいうマージってなんだ?
マージソートのマージ?
>>706
 SrcA[] + SrcB[] + SrcC[] + SrcD[]  → Dst[]
「良い」って何を求めてるのかわからんが
とりあえずメモリ使用量なら
Dst = SrcA;
Dst += SrcB;
Dst += SrcC;
Dst += SrcD;
とするのが無駄な一時オブジェクトが省かれて効率がよい。
Dst = SrcA+SrcB+SrcC+SrcD
という書き方は一見スマートだけどこの点では全く良くない。
#expression templateでも用意してるなら別だが
Efficient C++参照。
711デフォルトの名無しさん:03/12/19 21:17
>>710 そだね。
 Dst = SrcA+SrcB+SrcC+SrcD
みたいに一気にマージしようとすると
比較の部分の処理がむちゃくちゃ面倒になりそう・・・
Dst += Src ができないのでは?
だとすると一時オブジェクトを使う必要がある

 SrcA[] + SrcB[] → TmpA[]
 SrcC[] + SrcD[] → TmpB[]
 TmpA[] + TmpB[] → Dst[]
同じ要素を繰り返し何回も見なくて済むかと思ったが...あまり変わらんな
マージってソート済み範囲に対するマージって前提があるの?
テーブルに順序がなくて、赤黒木のようなもので実装されてるっていう。
その場合に2つのテーブルずつでなくて複数まとめて比較して
適切な挿入位置を決定したいっていう問題?
まとめて処理できた場合。

第一に各要素の検索が出力先入力元すべて1度ずつ。
コピーも1度ずつで済むから一時メモリ量の増加を除いて速くなるってのはいいとして。

出力先の挿入位置が示されたとき、
予選決勝法的に、
k 個の入力元それぞれが持つそこに挿入すべき値の候補ってのを
結局その場で比較して順位付けしないといけないんだよね。
んである入力元 i から挿入されたらAの次の候補を順位表に加える必要がある。
ここで i 以外が出した候補値の順位は変化しないから
新たな順位を決めるための比較は log k-1 で済む。
k 個の入力元の要素数と値の分布がほぼ同じ形を持っていれば
この部分での高速化も期待できるかも?

……適当だ
3つ以上のテーブルをマージって、根本的に効率悪くない?

仮にテーブルが10000個あったら、
そのテーブルから取り出した要素を
またソートする必要があるのでは
どうせ足すときは 1レコードずつ足すんだからどうでも同じな感じ
以上、素人の意見でした
3個以上のテーブルの場合、足す順番を間違えると
データがおかしくなる。
718デフォルトの名無しさん:03/12/21 02:26
試しに3つのテーブルのマージを考えてみる。こんな感じ?

while( idxA<sizeof(SrcA) && idxB<sizeof(SrcB) && idxC<sizeof(SrcC) ) {
if( SrcA[idxA] > SrcB[idxB] ) {
 if(SrcA[idxA] > SrcC[idxC] ) {
  dst[idx++]=SrcA[idxA++];
 } else {
  dst[idx++]=SrcC[idxC++];
 }
} else {
 if(SrcB[idxB] > SrcC[idxC] ) {
  dst[idx++] = SrcB[idxB];
 } else {
  dst[idx++] = SrcC[idxC];
 }
}
}
だからそのやり方だと
実際にsrcCからdst(大小統一頼む)に要素が入るケースが連続して起こった場合、
同じ( srcA[idxA]>srcB[idxB] )の比較を繰り返すことになり。
無駄な要素の比較を繰り返したくないという目的には半分しか貢献しない。
まあ3つくらいなら単純な分実際の効率は変わらないが。
720デフォルトの名無しさん:03/12/21 02:47
>>718
それじゃ足りない。どれかのテーブルが終端に達した時点でループを抜けるんだが、
その先もまた似たようなループ(残りのテーブル2つのマージ)処理を書く必要があって、
非常に冗長なコードになってしまう。。。

これが4つとか5つのマージだったらガクブルものだな。
素直に2つずつマージしたほうが結果的に速い&きれいに書ける気がする
3つ以上の入力に対して一般性のあるルーチンを作った場合でも
毎回すべてのテーブルに対し終端チェックが入るから。
入力のテーブルのサイズが異なる場合はやっぱり無駄が入るな。

入力テーブル残った要素数はそうそう変化しないから
残り数の少ない奴を常に監視しておく方法もあるが……。

実用的そうなのはたとえば
テーブルの要素を取り出すイテレータを用意してやって
データが残ってる入力コンテナへのイテレータだけを
キューに入れておくって仕組みかな。

すると
1. キューのトップの値の供給と、
2. 値を供給したイテレータの前進、
3. 前進したイテレータが終焉を迎えていたら削除、
……こんな処理を追加することになる。
無駄を省こうとすると思いの外硬いコードになりそうだ。
722デフォルトの名無しさん:03/12/21 09:42
"mergen insertion"なるソートアルゴリズムがあるって聞いたんだけど、
どうにもこうにも日本語の解説が見あたららない。
だれか解説できる人いますか?
1ページみつけたけどなんかもったいなさそうなのでひみちゅ♥
大堀さんやガリグさんらの「コンピュータ サイエンス入門」はアルゴリズムの本として
どういう人に向いていますか?
リストについて勉強をしています。
連結リスト、線形リストについて調べてみると、

「リストは大きく線形リストと連結リストに分類される」
「線形リストには連結リストと呼ばれるものがある」
「連結リストには線形リストと呼ばれるものがある」

という記述がそれぞれ別々のサイトで見受けられて混乱しています。
どれが正しいのでしょうか?
>>725
どれも正しくない。リストはリスト。
それだけ。

「連結リスト」とか「線形リスト」っていう区分けは
分類過剰癖のジジイ供が暇にまかせてひねり出した造語。
だから個人毎によって定義が異なってくる。
でも、敢えて説明するとなると、

連結リスト(Linked List):
配列等と対比して、個々の要素の追加削除が容易に出来るという特徴を
表現するときに使用される。

線形リスト(Linear List):
2分木等と対比して、個々の要素の次の要素が1つしかない縮退した木で
リストを表現するときに使用される。

ってとこかなぁ?
要するに字面や文脈の違いだね(反論キボン)
「リスト」っていった時、思い浮かべる構造は、その人が使っている言語によって
違うんじゃないかな。(例えば LISPer と C/C++ 使いで。)
ちゃんとした教科書なら、定義をした上で議論を進めていると思う。

だから、そのサイトを書いた人の使っている言語 or 読んだ教科書で言い回しは
違ってくるんじゃないかな。

漏れ的には、、連結リストは実装法から見た言い回し
線形リストは使用法から見た言い回し、並べて書くのはおかしい感じがする。
英語のサイトとか回ったけど、どうやら「linear list(s)」は使われ方がまちまちだな。空気読むしかないのかな
730725:03/12/22 13:06
レスどうもです。
これらの言葉の意味はケースバイケースで、
これが正しいといったような答えはないのですね。
ありがとうございました。
731デフォルトの名無しさん:03/12/22 20:31
データベースを利用するアプリケーションを作成するとします。
<h1>作成者の立場</h1>と利用者の立場の2つにおいて、ハッシュ法と二分木ではどちらが有効
でしょうか?
教えて下さい。
732デフォルトの名無しさん:03/12/22 20:32
<h1></h1>は気にしないで下さい(^^;)
線形リスト(linear list)って言ったら、ふつう環状リスト(circular list)
じゃない普通の連結リスト(linked list)を指して言うと思うけど。
連結リスト ⊇ (線形リスト ∪ 環状リスト)
って感じか。
というわけで、725にある三つの文のうち、最後の奴だけは、まあ合ってる
んじゃ? 前の二つは、確かに間違ってる気がするな。

連結リストと配列の両方を含んだ概念として、リストという言葉を使ってる
教科書もあるので、728も合ってると思う。

727の定義だと、環状リストまで線形リストの一種と見なれてしまいかねない
から、ちとまずいような。
>>733
linear は tree に対する linear じゃないの?

circular だとか linked list だとか doubly linked list だとかは実装の話だから
レベルが違うでしょ。
735733:03/12/22 22:08
>>734
俺の知ってるデータ構造の教科書だと、linear ←→ circular の
対比はしてるけど、linear ←→ tree の対比はしてなかった。
すぐに思いつく例だと
ttp://www.amazon.com/exec/obidos/tg/detail/-/0898711878/
とかはそう。

linear ←→ tree という意味で linear list を使ってる本って、
例えば何がある?
>>731 ぜんぜん質問の意味がわからん・・・
もういちど日本語を勉強しなおして来い
>>735
Knuth

The Art of Computer Programming Vol. I の目次は

2.1 Introduction
2.1 Linear Lists
2.2.1 Staks, Queues, and Deques
2.2.2 Sequential Allocation
2.2.3 Linked Allocation
2.2.4 Circular Lists
2.2.5 Doubly Linked Lists
2.2.6 Arrays and Orthogonal Lists
2.3 Trees
2.3.1 Traversing Binary Trees
2.3.2 Binary Tree Representation of Trees
2.3.3 Other Representation of Trees
2.3.4 Basic Mathematical Properties of Tress
2.3.5 Lists and Garbage Collection
となっている。
typo がいっぱいあるけど見逃して。
2.2 Linear Lists
2.2.1 Stacks, ...
739733:03/12/22 22:47
おお、なるほど。
君の主張(が|も)正しいのは納得した。

Tarjan の分類だと、Knuth が言うところの
Linear List の代わりに単に List という用語を使っていて、
List ⊃ (配列 ∪ linked structure ∪ …)
linked structure ⊃ (linear ∪ circular ∪ …)
という分類だった。
linked structure の分類軸には、2軸あって、
singly linked / doubly linked の軸と
linear / circular の軸の
2つの軸が直交してるの。

俺は、Tarjanの分類の方がきれいな気がするんだがなあ。
Linear List って分類があるなら、Non-linear List って
分類もありそうなものだが、Knuth 流だと Tree が
Non-linear List に分類されるわけだろう。でも、Treeの
ことを Non-linear List と呼ぶのは、聞いたことがない。
Tarjan流だと、Circular List は Non-linear List なわけ
で、これは納得。(Linear には「直線の」という意味もあるから)

> circular だとか linked list だとか doubly linked list だとかは実装の
> 話だからレベルが違うでしょ。
Tarjan の本だと、各操作の計算量の違いとしてここら辺を説明してる。
doubly じゃないと削除が O(N) になるとか、環状 (あるいは尻尾への
ポインタつき) じゃないと、尻尾への挿入が O(N) になるとか。
Tarjan の環状リストは、先頭へのポインタがなくて、尻尾へのポインタ
だけがあるのね。

結論としては、「教科書による」になっちゃうのかな。
それとも Knuth 絶対?
なるほど、 linear list <=> circular list と対比させる人もいるわけか。

要するに >>729 が言っているように linear list は使う人によって
意味が違う場合があるというわけだ。
linear list 使えねえ。

>>725 が迷うのもしょうがない。
線形リストをソートするアルゴリズムで
O(n)で作業領域がほとんど必要なく安定ソートで非分岐ソートってありますか?
>>741
「非分岐ソート」って言葉の意味を知らないんだけど、
リストならQuicksortでも安定だったはず。

自分はマージソートを使っています。
KnuthのTAOCPの三巻目、「Sorting&Searching」の
pp. 165-166, Algorithm L.です。
>>741
失礼。御所望のものはO(n)でしたか。
上に挙げたのはどちらもO(n log n)です。

O(n)ソートは、比較対象が何らかの条件(例えば、ある範囲の整数)
を満たしていないと無理でしょう。
1 = 0.9999999........
745741:03/12/24 03:02
>>743
レスThanks。
非分岐ソートってのはそのまんま「分岐しない」ソートです。
http://www.emit.jp/prog/prog_s.html

もし>>741の条件を満たすアルゴリズムを開発したら特許取るべきだと思いますか?
>もし>>741の条件を満たすアルゴリズムを開発したら特許取るべきだと思いますか?
もし、お前が何か発明したつもりならば一言言っておく。
安心しろ、勘違いだ。
アルゴリズムで特許をとると嫌われるからなぁ・・・
>もし>>741の条件を満たすアルゴリズムを開発したら特許取るべきだと思いますか?
おまえが人間なら、まず大々的にWebにさらし、そしてどっかで発表しろ。
うんこなら特許とれ。
749デフォルトの名無しさん:03/12/26 00:15
数式じゃ特許とれないように
ソートの基本的やり方やアイデアに対しては取れないだろう

ていうか、アホなプログラマーが必ず通ると言われる
典型的な勘違いだな
>>749

昔(10年以上前)は確かにそうだったが、米国でのカーマーカー特許の
認可以来、それは成り立たなくなってきた。実際、米国のアルゴリズムに
関する論文には、特許取得ずみのものがかなりある。
ソフトウェア特許で検索してみ。

カーマーカー特許にしても、ソフトウェア特許にしても、反対論は根強いし、
特にヨーロッパでは、実質的にソフトウェア特許は行使不能な状態が続いて
いるが。
>>750
それは米国だけの話だ
752デフォルトの名無しさん:04/01/01 16:29
アルゴリズム体操で特許とれますか?
>>752
すでにひろく公開されているので無理。
未発表のものを考えて申請しる。
海外掲示板用オフラインリーダーを作るスレ
http://pc2.2ch.net/test/read.cgi/tech/1072883528/

海外でよく使われていうる掲示板スクリプト
専用のオフラインリーダー作って下さい。

必要な条件はID、PASSを管理できること、
OpenJaneみたいな三面型の見た目。
簡単にローカライズできるように言語ファイルを採用
755デフォルトの名無しさん:04/01/17 00:54
動的計画法について、具体例をまじえつつ誰か教えてください
756デフォルトの名無しさん:04/01/17 02:55
ソートさせつつプログレスバーを出したいのだけど、
たとえばヒープソートなら n回繰り返す forループがあるから
ほぼ正確な途中経過がわかりますよね。
クイックソートで途中経過を表示させたいときって、どうしよう?
いい質問だ。頼んだぞ>>758
まず経過の途中で全経過状態を数値で表せるかから考えてみよう。
途中経過状態を数値化する上で、分割された区間がそれぞれ均等な状態にないことについて考えてみよう。
再帰で実装する場合、通常回数を記録するイテレータを持たないことについて考えてみよう。

今までの比較・移動回数を記録する変数を挿入することはできるが
再帰処理の割合としての深さは終端が定まって初めてわかるんで無意味
プログレスバーなんていい加減な表示でいいんだから、
再帰でもぐる前(もし深いなら後も?)にglobalなカウンタを
インクリメントするだけでいいんじゃないのか。
2^n乗かかると思っておいて。
またまた失礼。nだ。
762756:04/01/17 05:16
>>758 お答えありがとうです。やっぱ無理っぽいでしょうかね。
今のところはVisualC6.0のライブラリ関数 qsortのソースをコピーして
メンバ関数にしてしまい、比較を行った回数をメンバ変数に入れる処理を
追加してやってます。
トータルの予想比較回数を n * log n としてプログレスバーを表示してます。

データのバラつきによって 85%くらいで終わったり、100%に到達しても
もうしばらく終わらなかったり・・・です。当然ですけど。
やっぱこれで我慢してもらおうかな。

ヒープソートだと100%できれいに終わるんですけど(もちろん進行速度は
一定ではありませんが見た目にはあまりわからないでしょう)、
クイックソートのほうがやはり早いですから迷ってます。
だいたいヒープソートの 2/3 くらいですね。
見た目を取るか早さを取るか・・・。
つーかたかだかソートにプログレスバー出すの?
どんなデータ扱ってるか知らないけどその処理の方がかえってネックになるような
B+木を実装した簡潔なJAVAのプログラムソースを解析したいのですが
どこかあったら教えてください
765756:04/01/17 12:27
>>763
件数は最大約20万件です。比較はほとんどが文字列で、第3キーまであります。
Windows2000 PenIII-800 のマシンでヒープソートを行った例をあげると、
プログレスバー表示アリだと 7分40秒、無しだと7分20秒でした。
たしかに若干遅くなりますが、数分間もユーザに情報を与えないというわけには
いきませんので・・・。
>>764
ttp://www.seanster.com/BplusTree/BplusTree.html
ぐぐれば、すぐに見つかるのに。
>>756
適当に(100くらい?)に分割して、qsort
& マージソート
途中経過をプログラスバー表示って感じでどうかな?
>>767
そんながんばらなくても、適当でいいんじゃない?
Windows でファイルコピーとかしてるときのプログレスバーの進行具合、
残り2時間とかからいきなり残り10分とかになったりするし。
だが100%になったのに終わらないケースは勘弁したいかなあ。
としたら、理論上の最大値をマックスに定めて
増加の比率や後半の動きをいじった方があるいはいいかも。
要素数 n に対して、最悪計算量が n*n から始まって、
1回の分割で a と b に分かれたとすると、 a*a + b*b になる。
a + b = n のとき、 a*a + b*b < n*n なので、分割するたびに最悪計算量が減っていく。

幅が n*n のプログレスバー用意して、 ( n*n - 現在の最悪計算量 ) を表示すれば、
それなりに表示されそうな気がした。

あんまり深く検証してません。
まずクイックソートして回数を調べ、プログレスバーを出す。
>>770
計算負荷は高いが信頼性は一貫してるな。
でもそこまで計算値を使うのなら
分割回数を元に典型的な進行度を算出して表示した方が負荷が軽くていいような。

それとちょっとだけけちつけると、
n*(n-1) まで言った時点で処理が終了してバーが永久に右端に行かない気がする。
#典型的に要素数が二のべき乗で表される場合
n*n を、 (n-1)*(n-1) とすれば、右端までいくかな?
774756:04/01/19 22:03
>>770-773
レスどうもです。今日そのように実装してみましたが、
途中のバラつきが大きくてうまくいかなかったです。

結局、ひとまずヒープソートで提示してみて、
これより 2/3 くらいの速度が出せますが、プログレスバーが・・・と
お客さんに説明してみます。

>>769
100%だけは表示しないようにしてます・・・
バーの横に 99%と表示したまま終了まで待ちです・・・
> 今日そのように実装してみましたが、
> 途中のバラつきが大きくてうまくいかなかったです。

実装されたのですね。興味深いところです。
うまくいかなかったそうですが、実際のバーの動きが不味かったのでしょうか?
個人的には、途中で戻ったりしなければ、別にいいんじゃないかと思いますが。
776756:04/01/19 23:43
>>775
>>770 に忠実に実装してみた場合ですが、
プログレスバーの進行度を ( n*n - 現在の最悪計算量 ) としますので、
一回目の分割が行われるまでの間 → 0%
行われた後 → 一気に 30%くらい進む という感じでした。
その後も 数10%一気に進むことが多く、安定して刻んだのは
残り 5%くらいだったようです。時間があるときもうちょっと工夫して
みたいですが・・・。
>>776
予想されたことだなw
クイックソートは対数で進んでいくから
気になるなら表示時には線形に補正した方がいいでしょうな
778デフォルトの名無しさん:04/01/21 22:54
20万件程度ならマージソートで10秒もかからないしな
マジかよ
780デフォルトの名無しさん:04/01/22 02:36
「NP困難な問題に対する多項式時間アルゴリズムを示せ。」
「示せたら単位をやる。人間性に大問題があっても単位をやる。」
って冗談で言っていた先生がいたな…。

誰か示してくれ。そしてノーベル賞とフィールズ賞とチューリング賞をとってくれ。
781デフォルトの名無しさん:04/01/23 18:31
麻雀ゲームを作ってるんだが、
役判定を作ってておもいっきりわからなくなった、誰か助けてくれ。

上がった牌14枚を役判定に渡したらありえない重複の仕方をしてしまうわけだ
たとえばチャンタイーペー三暗刻とか。
とりあえず今できているのは、14枚を渡すとそれがその役になっていれば
OKが帰ってくる関数はできてる。 つまりそのありえるところとありえないところ
の境界線を作りたい。あとは、ありえる最高の組み合わせをだすアルゴリズムを誰か
考えてくれないか・・・ 

自分でもかいててよくわからないが 興味示したら誰か助けてくれ・・・
ヨロシク。
麻雀板で聞けよ
アルゴリズムと関係ないだろ
>>781
適当にフラグとか優先順位作って共存できない役を弾け。

>あとは、ありえる最高の組み合わせをだすアルゴリズムを誰か
>考えてくれないか・・・ 
只のプログラム作成依頼じゃんか。
>>781
過去スレもろくに見ようともしない奴に
一体何を教えればいいのやら・・・
>>781
三暗刻と一盃口が両方成り立つということは、刻子3つと順子2つ
に分けることができたということだ。つまり、その判定関数が
間違っているということ。
786デフォルトの名無しさん:04/01/24 13:52
>>783 
>適当にフラグとか優先順位作って共存できない役を弾け。

最初そうやって考えたんだが共存できるときとできないときがあったりするんだよなぁ
111222333 78999
こういうときはピンフジュンチャンイーペー + 三暗刻三連刻
チャンタのときは三暗刻だめなのかとおもいきや
111 999 111 789 99
このときは ジュンチャン 三暗刻 になる

つくった役判定関数はおのおのが別々で存在していて、判定にひっかかった瞬間に
フラグを立てていくようにしてあるんだ。

その状況でどっちの役を優先してあがれば点が高くなるかっていう
判定の関数を作れないだろうか・・・・

わかりづらくてすまん。
だから麻雀のルールの話をここですんなつってんだろこのボケ!
しね!
麻雀プログラムのスレがあるじゃん。
なんでそっちいかないの?
789781:04/01/24 15:31
ですね。 そっちで聞きます。 

すんませんでした。
最近、ナンバーリンクの自動解答プログラムに夢中です。

ナンバーリンク(ニコリ)のルール:
1.同じ数字どうしを線でつなげます。
2.線はタテヨコに引き、 マスの中央を通ります。
3.線は1マスに1本だけ通過できます。
  線をワクの外に出したり、 交差や枝分かれさせてはいけません。
  また、 線は数字が入っているマスを通過してもいけません。

詳しくはここで。
http://www.nikoli.co.jp/puzzles/4/

総当りで解くプログラムだったら少し考えれば出来るのですが、
より人間的な思考を取り入れてゆくのが難しくて、また面白い。
>>790
トポロジー勉強したことあるならすぐでしょ。
壁があるから枝がばっさり落とせて楽だし。
>>790
ナンバーリンクからトポロジーを連想するのか。

・・なんか頭悪そうだな。
793デフォルトの名無しさん:04/01/29 18:58
f(x,y)=0とg(x,y)=0の両方を満たすx、yを数値的に求める
アルゴリズムって何かあるでしょうか?
解析的に解けない場合です。


>>793
ニュートン法。
横レスだけど、適当な初期値の見当がつかない場合は?
>>795
万能な解決策はなかったと思われ。
ニュートン法 初期値推定 とかでぐぐるといいかと。
>>756
遅レスだが、VC使って文字列比較20万件で7分はかかりすぎでは?

多少工夫していますが、単純な文字列キー(比較関数strcmp)で
オンメモリだと、PenIII-1GHzで20万件が一瞬(1秒以下)、50万件
も1秒以下、800万件に増やしたところ18秒でした。
>>797
全て書くと長くなるので省略しましたが・・・
文字列データをメモリに持っているわけではありません。
実際のデータはCSVファイル、つまりテキストファイルに
記述されていて、メモリに確保した配列にはそのテキストファイルの
レコード位置を記録しています。ですから、比較関数ではまず
ファイルから文字列を読み出します。

また、ソート比較項目はどれも数百種類のパターンでしかなく、
そのため、2つの項目の主キーについての安定ソートになります。
よって、ひとつのデータの比較に、1〜3回の文字列比較になります。

またさらに、住所データなどは「都道府県」+「市区町村」+「町域」
と分かれてますから、これも最悪な場合には6回の文字列読み出しが
伴います。前に挙げた時間はこの最悪な住所ソートでの数値です。

そりゃメモリを使えれば早くなることは承知してますが、時間と空間の
トレードオフですからね・・・。せめて2つの主キーだけでもメモリに
取れればだいぶ違うんですが、なにしろ空間は限られています・・・。
799798:04/01/30 00:48
それと・・・
CSVファイルですので、ひとつの項目を取り出すのに
レコードの先頭からCSV解析しながら n番目のトークンを
抜き出す処理も入ります。
でもまあ数十万件のソートをするというのは最悪の場合でして、
使用頻度はほとんど無いと思われます。
数百〜数千件までデータを絞り込んでからのソートであれば
それほど時間もかかりませんしね。
いまのところ客は満足してます。
>>798
外部ソートなんですね。
分割してメモリ内でソートし、その後マージソートした方がいいのでは。
>>800
ソート途中もソート後も、ファイルの内容はまったく変えずに
ファイルへのポインタ配列(を複数集めた構造体)をソートするわけです。

比較するときはファイル読込みするけど、データ交換自体は
メモリ内での移動ですので、計算量が同じ(n * log n)であれば
同じ結果になると思うんです・・・。
>>798
>>759 もそれらしいことを書いているけど、
確かにクイックソートは呼び出される "深さ" は一定ではないが、
呼び出される "回数" は常に一定だから、
それを利用できなかったのか?
>>801
いや、比較するデータもメモリにためて分割・併合ソートするんですよ。
ディスクとメモリの速度は絶望的に違いますから、比較対象を毎回ファイルか
ら読んでいたら、いかに計算量が良くても話にならない。
804デフォルトの名無しさん:04/02/03 00:09
>>803
ディスクキャッシュが存在しないことを前提にしてる?
805デフォルトの名無しさん:04/02/03 06:46
アルゴリズムとデータ構造の話からだいぶ反れて来ている事はたしか
806デフォルトの名無しさん:04/02/03 13:54
次のような BNFで表された文法(idは終端記号とする。):

E -> id
| E "[" E "]"
| E "." id
| E "(" X ")"
X -> E X'
X' -> "," E X'
| ε

に対して、

1. E の生成規則から左再帰を除去せよ。 (左再帰を除去するために、新しい非終端記号を導入する場合、 E'という名前をつけると良い。)
2. 左再帰を除去した文法に対して、構文解析表を作成せよ。

これ解いてください
宿題スレで解いてもらえなかったからってなんでここに投げる?
808デフォルトの名無しさん:04/02/03 22:07
>>807
お願いします、教えてください
>>803 データを読み込むほどメモリが使えたら苦労しないんじゃーないの?
>>798からすると。
(1)
E  ::= id E'
E' ::= ε
   | "[" E "]" E'
   | "." id E'
   | "(" X ")" E'
X  ::= E X'
X' ::= "," E X'
   | ε

(2)
(E,id) = E'
(E',"[") = E "]" E'
(E',"]") = ε
(E',"(") = X ")" E'
(E',")") = ε
(E',".") = id E'
(E',",") = ε
(E',$) = ε
(X,id) = E' X'
(X',")") = ε
(X',",") = E X'

たぶんまちがってる.
>>806
せめてどこが解らないのか書いてくれ
BNFがわからんのか、左再帰の除去がわからんのか…
812デフォルトの名無しさん:04/02/09 20:25
アスキーから出版されてるプログラミング作法、このP68の問2-4解けるかたいませんか?

問題概要:n個の数列をできる限り低速にソートするアルゴリズムを設計実装せよ。
インチキな実装はしてはならない。
そして、そのアルゴリズムの計算量はいくつか?

問題の意図はおそらくO(n^2)よりも遅いソートアルゴリズムを見つけよだと思うのですが…
お知恵を貸してもらえませんか?
お願いします。
>>812
do
{
乱数で数列をシャッフル();
} while(数列がソートされていない間);

さて、オーダーはいくつだろう・・・
配列で順列を作っていってソートされてたら終わり
としたらn!くらい?
n^2より遅いのって・・・どうやんだ?
無駄処理入れたらインチキなんだろ?
>>815
>>814のじゃだめなの?
>>813
>>814
両方とも、

ぱっと見オーダーは n! だが、シャッフル、順列をひとつ生成するのに
最低 n かかるので n * n!

であってる?
>>817
O(n * n!) = O(n * n! + n!) = O((n+1)!) = O(n!)
>>818
O((n+1)!) != O(n!)
820デフォルトの名無しさん:04/02/12 00:47
誰かべき集合を求めるアルゴリズムを教えてください
これ案外難しいっす
集合から一個取る
一個取った集合のべき集合を求める。
一個取った集合のべき集合の要素全てに最初に取った要素を加えたと
一個取った集合のべき集合を合わせる。
822デフォルトの名無しさん:04/02/12 01:05
>>821
よくわかんないので、できれば擬似コードお願いします
function powerset(a)
if a is 空集合 then return [[]]
else begin
b = car(a) // 一個取る
c = cdr(a) // 一個取った残り
d = powerset(c) // 一個取った残りのべき集合
e = map (b:) d // 要素全てにbを加えていく
f = e ++ d // 二つの集合を合わせる
return f
end
function_end
824デフォルトの名無しさん:04/02/12 01:36
>>823
ありがとうございます、リカーシブなんすね
825デフォルトの名無しさん:04/02/12 02:56
つか上のコードC++で書こうとしてるんだけど、むずいなぁ、、
集合の集合が、えーっと、、
>>821
集合の要素Nがlog2(UINT_MAX)以下なら

main()
{
 unsigned U = (1 << N) - 1;
 for (unsigned i = 0; i <= U; i++)
  print_contents_of_set(i);
}

void print_contents_of_set(unsigned x)
{
 int j;
 printf("[");
 for (j = 0; j < N; j++) {
  if ((x >> j) & 1)
   printf(" %s", name_of_element[j]);
 }
 printf(" ]\n");
}

というインチキな答もありだな。


>>825
#include <iostream>
#include <list>
template <class Ps, class It> void powerset(Ps &f, It start, It end) {
 if (start == end)
  f.push_back(Ps::value_type());
 else {
  It b = start, c = ++start;
  Ps d;
  powerset(d, c, end);
  for (Ps::const_iterator i = d.begin(); i != d.end(); ++i)
   f.push_back(*i), f.push_back(*i), f.back().push_back(*b);
 }
}
template <class Ps> void print(const Ps &ps) {
 for (Ps::const_iterator i = ps.begin(); i != ps.end(); ++i) {
  for (Ps::value_type::const_iterator j = i->begin(); j != i->end(); ++j)
   std::cout << *j << " ";
  std::cout << std::endl;
 }
}
int main() {
 typedef std::list <int> set_t;
 typedef std::list <set_t> powerset_t;
 set_t s;
 for (int i = 0; i < 3; i++) s.push_back(i);
 powerset_t ps;
 powerset(ps, s.begin(), s.end());
 print(ps);
 return 0;
}
非再帰解のほうが・・・
829デフォルトの名無しさん:04/02/12 18:29
え、それってどういうの?>>828
830デフォルトの名無しさん:04/02/12 23:53
BSPのアルゴリズムをよろしくお願いいたします。
BSEのアルゴリズムをよろしくお願いいたします。
>>831
namespace USA
{
    std::set<cow> cows;
}

for(std::set<cow>::iterator i = cows.begin(), i != cows.end(), ++i)
{
    i -> brain.insert(prion);
}
833デフォルトの名無しさん:04/02/15 03:14
BSEじゃなくてBSPでおながいします。
BPS
GPS
FPS
FPD
838デフォルトの名無しさん:04/02/16 15:52
"疎" な集合のグラフを扱いたいのですが、
行列にマップする方法のように無駄に大きいメモリを使うことなく、
なおかつ定数時間で各ノードのつながり具合を調べられる
データ構造が欲しいのです。

そんなものはあるでしょうか?
839838:04/02/16 15:55
定数時間がむりなら、できるだけそれに近い速度を
出せる方法とか・・・

私にはハッシュを組み込むことぐらいしか思いつきません。
>>838
graph-coloring register allocationのアルゴリズム中で
まさにそういうデータ構造を使っています。

bit-vector, list&vector, hashの三種類作ってみましたが、
案外bit-vectorが健闘しています。理論的なメモリ効率はhashがいちばんいいですね。

list&vectorというのは、ノードごとにサイズV(ノードの数)の配列をlistと
checkの二本もち、listには隣接ノードの番号を順につめて記録し、check に
は、list[check[v]] == vになるようにセットしておく方法です。

このデータ構造はメモリはO(V^2)だけ食いますが、初期化、隣接ノードの追加、
削除、二つのノードの隣接検査がすべて定数時間ででき、与えられたノードの
隣接ノードの集合を列挙するのも隣接ノード数に比例する時間しかかかりませ
ん。(bit-vectorだと隣接の列挙は総ノード数に比例する時間がかかります)
841838:04/02/17 01:49
>>840
ふむぅ・・・ list&vector 、そんな手があったんですか。
気づきませんでした。

どうもありがとうございました。
842デフォルトの名無しさん:04/02/17 02:03
配列A[1..n]に異なる数字が入っていて、整数xが与えられたときに
A[i]+A[j]=xとなるi,jが存在するか判定するアルゴリズムで
なるべく効率が良いもの教えてください
ソートしてx-A[i]をサーチ
オーダーのo(...)って数学のランダウの記号とほぼ同義と考えていい?
>>844
ほぼ、というより、どこか違う所があるのか?

まあ、数学の方が対象とするスパンが広いことは確かだが。
>>838
というか、「隣接行列」習ったのなら
それといっしょに「隣接リスト」も習わなかったの?
数学じゃなくてコンピュータ科学の方面から勉強してるなら
たいていいっしょにやると思うんだけど。
ああごめん。定数時間か。
それだと確か>>840みたいな拡張や組み合わせがいるね。
(データ構造の名前が出てなかったんでそこ気にしちゃった、スマソ)
848デフォルトの名無しさん:04/02/17 22:20
C言語で学ぶアルゴリズムとデータ構造基礎の基礎
を読んだんですが何一つ定番アルゴリズムを理解できません
なんなんですか
>>848
読んでるだけだから。




もしくはお前がとんでもないバカだから。
11を1+2+8(もしくは1+2+4+4)
みたいに分解したいのですが…
どうしたらよいでしょう?
>>850
それだけじゃ何をやりたいのかわからない。

2進数の桁に分解するのなら、ものすごく簡単。
1の位から順に立っているビットをテストするだけでしょ?
>>851
ええとですね
97^11 とかをやりたいんです
でもこのままじゃすごい大きな数になりますから

97^11 = 97^1 * 97^2 * 97^8
見たいな感じで分解したいんです
>>852
そもそもそういう分解をしたい理由がよくわからん(;´Д`)
突き詰めれば97*97*97*・・・*97に分解するのが確実なんじゃないのか?
それとも型のlimitで止めたいのか?
97^11 = 97^1 * 97^2 * 97^8
に分解して、それぞれのmodを取りたいんです。

97^2 = 9409 = 361 (mod 377)
97^4 = {97^2}^2 = 361^2 = 130321 = 256 (mod 377)
97^8 = {97^4}^2 = 256^2 = 65536 = 315 (mod 377)

97^11 = 97 * 97^2 * 97^8
= 97 * 361 * 315
= 35017 * 315
= 333 * 315
= 104895
= 89 (mod 377)

最終的にこうしたいんですが…
おわかりいただけたでしょうか?…←説明力不足!?
>>851が言うように2進数に分解すればいいかと。
ループにして毎回掛けてmod取る手もあるかな
>>854
RSAか?
ttp://www.faireal.net/articles/5/25/
でjavascript上で動かすサンプルがある。嫁。
>>852
> でもこのままじゃすごい大きな数になりますから
intであらわせないほど大きくなるかもしれないのなら、
ループで毎回modを取るのが簡単。

そうでないなら大きかろうとなんだろうとそのままmodをとるのが速い。
hoge(x, y, z) {
for (i = 1, r = 1; y >= i; i <<= 1, x *= x)
if (y & i) r *= x;
return r;
}
mod入れるの忘れてた。
hoge(x, y, z) {
for (i = 1, r = 1; y >= i; i <<= 1, x = x * x % z)
if (y & i) r = r * x % z;
return r;
}
861850:04/02/18 13:56
みなさんどうもいろいろありがとうございます。
サンプルまで提示していただいて恐縮ですm(_ _)m
がんばってみます
862850:04/02/18 15:06
あの、if (y & i)ってこれってどういう意味でしょうか?(汗
あほな質問ですが…おしえてくださいm(_ _)m
>>862
ビットごとにANDをとる。
ex.
1010 & 1001 -> 1000
1011 & 1001 -> 1001
ムズリゴルア!
誘導されてやってきました。
2個の四角形の交差判定ってどうやって考えればいいのでしょうか。
具体的にはシューティングの弾丸の衝突判定などです。
決められた文字列の集合とマッチするか調べる高速な方法として完全ハッシュ関数があり、
また、完全ハッシュ関数生成ツールとして gperf がある事は調べました。

質問なのですが、完全ハッシュ関数生成に関する一般的なアルゴリズムってあるのでしょうか?
(gperfを読めでもいいのですが、一般的なアルゴリズムの一実装でしかないとおもうので)

868デフォルトの名無しさん:04/02/26 09:10
誤り検出のCRCについて質問です。

CRCのCCITT方式を勉強してるんですが疑問が湧きました。
まず、CCITT方式は下記の特徴をもつようでした。

1.最初の16ビットを0⇔1反転してから計算する。
2.同一バイト内では右側(通常の下位ビット側)を上位ビットとみて割り算する。
3.結果(割り算の余り,16ビット)を0⇔1反転する。

このうちの3番目なんですが、これは何のために必要なんでしょうか?
CRCをデータに付加するときにさらにもう一度反転してから付加するのならば最初から
3番目をやらなければいいような気がするんです。
>CRCをデータに付加するときにさらにもう一度反転してから付加するのならば

ここをもうチョット詳しく説明してみて
870(1/4):04/02/26 11:12
返信ありがとうございます。
疑問の説明用ソースを貼り付けます。(空白を半角2→全角1に置換して貼ります)
※3での反転が無ければ※5でも反転しなくてすむのに、※3は何のためにあるのか?です。

--
Prompt>test
TEXT: "DataText"
--- GetCRC_CCITT() ---
CRC: 0xDB04
CHECK: 0x0000
--
#include <stdio.h>
#include <string.h>

typedef unsigned char byte;
typedef unsigned short word;

#define CRC_CCITT_POLY 0x8408   /* CCITT方式 : 0x11021のbit16排除&逆順 */
871(2/4):04/02/26 11:12
word GetCRC_CCITT(const byte *src, int size)
{
  word crc;
  int i, j;

  crc = 0xFFFF;                  /* ※1 */
  for ( i = 0; i < size; i++ ) {
    crc ^= (word)src[i];
    for ( j = 0; j < 8; j++ ) {
      if ( crc & 0x0001 ) {          /* ※2 */
        crc = (crc >> 1) ^ CRC_CCITT_POLY; /* ※2 */
      } else {
        crc >>= 1;             /* ※2 */
      }
    }
  }
  return ~crc;                  /* ※3 */
}
872(2/4):04/02/26 11:12
word GetCRC_CCITT(const byte *src, int size)
{
  word crc;
  int i, j;

  crc = 0xFFFF;                  /* ※1 */
  for ( i = 0; i < size; i++ ) {
    crc ^= (word)src[i];
    for ( j = 0; j < 8; j++ ) {
      if ( crc & 0x0001 ) {          /* ※2 */
        crc = (crc >> 1) ^ CRC_CCITT_POLY; /* ※2 */
      } else {
        crc >>= 1;             /* ※2 */
      }
    }
  }
  return ~crc;                  /* ※3 */
}
873(3/4):04/02/26 11:13
int main(void)
{
  const char *text = "DataText";
  char buf[256];
  int len;
  word crc;

  printf("TEXT: \"%s\"\n", text);

  printf("--- GetCRC_CCITT() ---\n");
  strcpy(buf, text);
  len = strlen(buf);

  crc = ~GetCRC_CCITT(buf, len);   /* ※5 */
  buf[len++] = (crc >> 0) & 0xFF;   /* ※4 */
  buf[len++] = (crc >> 8) & 0xFF;   /* ※4 */
  printf("CRC: 0x%04X\n", crc);

  crc = ~GetCRC_CCITT(buf, len);   /* ※5 */
  printf("CHECK: 0x%04X\n", crc);

  return 0;
}
874(4/4):04/02/26 11:14
--
※1:「最初の16ビットを0⇔1反転してから計算する」関連部
※2:「同一バイト内では右側(通常の下位ビット側)を上位ビットとみて割り算する」関連部
※3:「結果(割り算の余り,16ビット)を0⇔1反転する」関連部
※4: 右送りのCRCはバイト並びを逆順にして付加しなければいけない
※5: GetCRC_CCITT()から返ってきた値は反転しているため、反転してから付加しなければいけない
875868:04/02/26 11:16
(2/4)を2つ貼ってしまいました。申し訳ありません。
えと、実際に実装する場合は シフトしながらより 8ビット分一度に計算した方がいいよ。
一度に計算する方法が判らなければ検索すれば見つかるでしょう。

で、CCITTに従うなら、CRCは反転したままデータに追加せんといけんでしょう。
877868:04/02/26 12:19
返信ありがとうございます。
テーブルを使用する方法も一所に載っていたので知っていたのですが、この疑問とは関係
ないと考え、少しでもソースが短くシンプルですむベタなソースを貼りました。
しかし、助言ありがとうございます。

> で、CCITTに従うなら、CRCは反転したままデータに追加せんといけんでしょう。

反転したまま付加というと、
  crc = ~GetCRC_CCITT(buf, len);   /* ※5 */
    ↓
  crc = GetCRC_CCITT(buf, len);    /* ※5 */
となりますが、これだと「CHECK: 0x0F47」となってしまうんです。
CRCの正誤判定は、
「データからCRCまで含めてチェックし、その結果がゼロになれば正しい」
だと理解したつもりなのですが、CCITTは正誤判定の方法が違うのでしょうか?
ああ、そうか。 いえ、ちょっと勘違いしてました。

それなら、実装は、
・反転しない計算して 追加
・チェックの時はCRCを入れて計算して -1 と比較で

でいいんじゃないですか?
いや、ちょっと混乱して来ました。

読み出しの時は CRC初期値 0 で開始して、全部のCRCを求めると 0 になるようにするには
書き込みの時はCRC初期値 0xffffで開始してるので、
やっぱり、反転したデータを書き込まないといけないような・・・・
880868:04/02/26 14:54
どうしてそうなるのかまだはっきりとは理解できていないのですが、
※1の部分を0x0000と変更しても「CHECK: 0x0000」になりました。
※3の条件はなんのためにあるのでしょう。
>>880
アルゴリズム辞典より引用

そのままの方法では、ファイルの頭に余分なビット0がいくつ付いても誤りが検出されない。
この点を改善するために、CCITT方式では最初の16bitを反転してから計算し、結果を反転して元に戻す。

とのこと
初期値0でも-1でも CHECKで0になるの?

あれ? コードみたら
> 1.最初の16ビットを0⇔1反転してから計算する。

の*計算する*が入ってないようだよ。


ここに、代表的な値のCRC-CCITTの結果があるから実行して比較してごらん。
http://www.joegeluso.com/software/articles/ccitt.htm

長さ0の入力(入力が無い)時に  0x1D0F じゃないといけないよ

883868:04/02/26 15:22
有用なサイトの紹介ありがとうございます。
[const char *text = "";]とすると見事なくらい「CRC: 0xFFFF」になりました。
Bad_CRCですね。
"A"や"123456789"はGoodにもBadにも該当しませんでした。
英語が苦手なのでGood_CRCとBad_CRCの解釈が違う可能性もありますが、
Cソースなら読めると思うので読んでみます。
884868:04/02/26 15:24
>>881
テキストだけ用意して投稿を忘れていました。
--
ありがとうございます。
おかげで※1に関しては理由がわかってすっきりしました。
では※3にはどんな理由があるのでしょうか?
これも「ファイルの頭の余分なビット0」を検出するために必要な処理なのでしょうか?
関数からは※3で反転された値が返ってきますが、データに付加する辞典でまた反転する
なんて無駄にしか思えなくて悩んでいます。
>>883
そのサイトと値が違うのは、 そのサイトはMSBからデータを送っているのに、 >>272はLSBからデータを送ってるからでは?
886868:04/02/26 16:54
確かにそのサイトのCRCは※2が適用されていませんね。
てっきり、CCITTならば※1〜3の適用が必須だと思っていたのですが、
そうでもないのでしょうか?
HDLCなんかは当然そうだよね。
>※5: GetCRC_CCITT()から返ってきた値は反転しているため、反転してから付加しなければいけない

反転した状態を付加するみたいだよ。

で同じルーチンを使う場合は 付加CRCを含めて計算すれば 0xf0b8と比較すればいいみたい。

参考:
http://www2s.biglobe.ne.jp/~hig/ppp/ppp_HDLC.html#PPP_HDLC_C
889868:04/02/26 18:36
ありがとうございました。
これで正誤判定が出来そうです。
CCITTはほかのものとは正誤判定方法が異なるんですね。
しかし、ゼロじゃなくて0xF0B8というマジックナンバーで判定っていうのは
ちょっと気持ち悪いですね。
だから、最初の反転を止めて、追加時の反転も止めれば確かゼロになる筈。

その為の追加時の反転でしょ?
891868:04/02/26 21:01
申し訳ありません。読み取れませんでした。
具体的にどうすればいいのでしょうか?
0xF0B8と比較して正誤判定するのは間違いなのでしょうか?
CCITTでもゼロかどうかで正誤判定する方法があるのでしょうか?
892デフォルトの名無しさん:04/02/26 22:30
n個(ただし、n>=2)の浮動小数点型要素(double)を持つベクトルをVecとする。
また、既にVecがm個(ただし、m>=1)、配列 vecList に存在するものとする。
新たなVec Pが与えられた時、vecList中で最も距離が近い(普通の距離)Vec P'を
なるべく高速に求めよ。

Vec[] vecList = vec[m];
for(int i = 0; i < vec.length; i++) { vecList[i] = Math.random(); }
Vec P = Vec.createRandomVec();
// ここを実装してください ↓ お願いします。
Vec resultVec = getNearestVec(vecList, P);
// 実装が面倒でしたらヒントだけでも。。。
893892:04/02/27 08:53
お願い教えてプリーz うっかり言い忘れてたけどマジごめん。
Vecクラスには
Vec#size(), Vec#get(int), Vec#getDistance(Vec)があるのですよ。
あと上のソースs/vec.length/vecList.length/なのですよって分かるだろうけどスマソ。

正味な話、Javaでそういう機能が欲しいのですよ。既存ベクトルは
毎回どっかが変化する可能性があるからキャッシュしても高速化できないし
JakartaのMathプロジェクトにはベクトルクラス無いみたいだし
普通に組むとたかが1000件の処理でノイマン型PCの限界にぶちあたるし
金無いし時間も無いしでもう大変なんだよコンチクショー>自分

なんとかしてくだせえプログラマ様。へへー(平伏)
>>892
問題が良く判らないのだけど、それはたぶんデータ構造の問題だね。
その配列 vecList というけど、単純に配列に置く限りは改善されない。

2次元だとすれば、xとyでインデックスを持っていれば、 P.x P.yでそれぞれ2分検索して
それぞれの一番近い点の近辺を探すとか

あるいは、普通に配列を諦めて、何とか木でデータを持つとか、そんな工夫が必要だ。
wavファイルの音を重ねるプログラムを作成したいのですが
各サンプリングデータの差を取るだけじゃないと思うのですが
どのようにすればよろしいのでしょうか。

(ソフトウェアシンセサイザって言うんですかね?)
>>895
音を重ねるだけなら、
各サンプリングデータを適当な割合で混合するだけでいいんだが。
ソフトシンセっていうか、ただのミキサー。
割合というか普通に飽和加算
ボロノイ分割
javaで数値計算やるのが無駄。
飽和加算:ほんわかさん
と、読む
なぜか変換できない
このスレには少し似つかわしくないような気がしますが、
プログラミングテクニックに関する質問です。

Cでクイックソートのアルゴリズムを何回か実装したことがありますが、
未だに、ちゃんと動作するプログラムを一発で書くことができません。
クイックソートの原理は既に分かっていますが、
「left_ptr < right_ptr ではなく、left_ptr <= right_ptr にすると動く」
といった境界に関わるミスをいくつか修正・テストして、
やっとソートの機能を満たすプログラムが作れる、といった感じです。

このプログラムは、大抵このようなプロセスを経て作るものなのでしょうか?
それとも私が阿呆なのでしょうか?
よろしくおねがいします。
>>902
境界で迷うのは、仕様をきちんときめていないからでは?
いくらアルゴリズムを理解していても、細かい点も注意しないと。
データ数が
1個の場合
2個の場合
3個の場合
……
n個の場合

の動作を紙の上で確認して境界の処理をどうするかをバッチリ決め手からコーディングするのが吉
やっつけ仕事でテストすると、「そのテストデータではたまたま動作する」プログラムが出来上がることになるから

本番用に完成し複雑なプログラムで大きなデータを扱うときに原因不明のバグがでて死ぬる。
クイックソートじゃなくて一般論になってしまったが。
こっちのスレで本格的に議論した方がよいと思われ・・・
http://pc2.2ch.net/test/read.cgi/tech/1025264999/l50
906902:04/03/04 00:07
レスどうもです。
やはりじっくり考えてからコーディングをする必要があるのですね。
少し慌て気味だったようです。
どうもありがとうございました。
>>902
クイックソートは単純な割に、特に条件判定の間違いに敏感なのでも有名なん
ですよ。仕方ないかも。ループ変化/不変条件などをassertでチェックしたり
すると早めに間違いに気づきます。
908902:04/03/04 00:25
>>907
なるほど、assertを使うと良さそうですね。
ありがとうございます。とても為になります。
自分はアルゴリズム的な処理を考えたり試す時はまず  Pascal(Delphi) で書いてる。
理由はひとつで、関数内関数が書けるから、再帰的な定義がそのままの表現で書けるから。

これを、ネタ帳(そういうのを集める為のテキストファイル)に置いておいて、Cとか他言語に移植して利用
>>909
>関数が書けるから、再帰的な定義がそのままの表現で書けるから。
詳細キボン。
関数内関数の利点は余り感じられないんだが。

そのままの表現という意味では、逆立ちしても Lisp には勝てないだろうし。
C++ と Boost ライブラリの lambda 使ったり、
C# (時期版)の匿名デリゲート使うならともかく、
関数ない関数だと微妙に「再起的な定義がそのままの表現で」
って分けには行かない気が。
912複雑なシフト表作成:04/03/07 17:07
こちらの掲示板は始めて利用させていただきます。
うちの会社で、とても複雑なシフト表を
毎月月末手作りで作っているのですが、
なにか適当なプログラムソフトをご存知の方が
いればと思って書き込みしています。
シフト表の構成要素は、
部員が10名(男8女2)いる。
月〜木は毎日8種類の勤務形態(8人が何らかの形で出社している)、
金が7種、土が3種、日が4種。
そのうち月〜木、日の8種のうち2種は夜勤の勤務形態だから、
次の日とセットで設定しなくてはいけない。
また、夜勤の次の日は休みか夜勤とする。
2名の女性はその夜勤の回数の設定を男性の3〜4割減にする。
などなどなんですが。
こういった設定の表に、ある程度の有給休暇のマークを入れて、
計算を開始させたら「何パターン可能」といった表示ができれば
最高なんですが。書き込む場所を間違えていたらすいません。
>>912
例題とその回答例をキボン。
全パターン欲しいなら条件全部洗い出してprologにでも食わせろ
915デフォルトの名無しさん:04/03/07 22:02
>>912
従業員がどれだけワガママを言うのか良く分からんから
とりあえず行き当たりばったりにプログラムを作ってみたが、
こんな表が出力されればいいのか?
多分、総パターン数を数えるとなると計算量が膨大になると思う
(何千兆通りとか・・・)

※1日(日曜日)から31日まで。2 = 日勤, 8 = 夜勤, 9 = 休日

0(F): 8 8 8 9 9 9 9 9 9 9 2 9 2 2 2 2 2 2 2 2 2 9 2 2 2 2 2 9 9 2 2
1(F): 8 8 8 9 9 2 9 9 9 2 2 2 2 2 2 2 2 2 2 2 2 9 9 9 2 9 2 9 9 2 2
2(M): 2 9 9 8 8 9 2 8 8 8 9 9 9 2 9 2 2 2 2 2 2 2 2 2 2 9 9 9 9 2 2
3(M): 2 9 9 8 8 9 9 8 8 8 9 2 2 9 9 9 2 2 2 2 9 2 2 2 2 2 2 9 9 2 2
4(M): 9 2 2 2 2 2 9 9 2 9 8 8 9 9 8 8 8 9 9 2 9 9 2 2 2 2 2 2 9 2 2
5(M): 9 2 2 2 2 2 9 9 2 2 8 8 9 9 8 8 8 9 2 2 9 9 2 2 2 2 2 2 9 9 9
6(M): 9 2 2 2 2 2 9 9 2 2 2 2 2 9 9 2 9 8 8 9 9 8 8 8 9 2 2 2 2 9 2
7(M): 9 2 2 2 2 2 9 9 2 2 2 2 2 9 9 2 2 8 8 9 9 8 8 8 9 2 2 9 2 2 9
8(M): 9 2 2 2 2 2 2 2 2 2 2 2 2 9 9 9 9 2 9 2 9 9 2 2 8 8 9 9 8 8 8
9(M): 9 2 2 2 2 2 2 2 2 2 2 2 2 9 9 2 2 2 2 9 9 9 9 9 8 8 9 9 8 8 8

>912
そういう業務ごとに異なる規則に対応する汎用シフト管理ソフトはない。
普通は受注生産。
>>912
ここはプログラム版だから、コード書かずに凡用ソフト探してるって言うんなら
板違いだよ
>917
ぼんよう(←なぜか変換できない)
暗号仕様に耐える強度をもつ一様乱数発生アルゴリズムを探しています。
一様乱数、暗号等でぐぐって見ても周期性がどうのこうのというページしか
でてきません。具体的なアルゴリズムの名前と実装方法が知りたいのですが。
みなさん知っていたら教えてください
>>919
>暗号仕様に耐える強度
言っている事が曖昧すぎ。そもそも、その強度が
乱数列の乱数性に依存する暗号なんて
まともな暗号ではない。
921デフォルトの名無しさん:04/03/09 11:56
>>920
すみません変換ミスです。
暗号使用に絶える、つまり周期性が長いとかそういうことです
RSAの素数発生用に使いたいんです
>>920
1と0が交互に出てくる(超)擬似乱数でも安心できる暗号ってなんだよ
>>919
周期の長さを求めるならM系列乱数だろう。
しかしそれが(希望する)暗号使用に耐える
強度をもつかどうかは分からないな。
みなさんありがとうございます。
メルセンヌ・ツイスタが一番よさげので、それを使ってみることにします
>>923
鍵から擬似乱数を生成して XOR を取るというような暗号は
まともな暗号ではないと思うが?

まともな暗号は生成された「鍵」さえ分からなければ
その鍵の生成の作業にどのような擬似乱数を使おうが
暗号の強度には変わりはない。
>>925
一番よいのは、ユーザーにキーボードをバンバン叩いてもらって
乱数を生成する方法だと思うがな・・・
>>927
あほか
>>926
擬似乱数がボロボロならその鍵が限定されて推測されるっちゅうねん
>>925
!!注意!!
メルセンヌ・ツイスターはそのままでは暗号には使えず、
さらに加工する必要がある。(差分攻撃とかに弱いらしい)
>>928
>あほか

何処が?
>>928
PGPもユーザーにマウスをぐるぐる回させて乱数作成してるじゃん
933925:04/03/09 15:58
>>930
ユーザーにキーボードをたたくなり、マウスを回させるなりして
一定時間数値を収集して、その中からメルセンヌ・ツイスターをつかった乱数を
元に抽出して使ったらOKですか?
>>929
それは、平文の一部でも判ってる場合だね。
M系列や合同法なら一部が判ったら全部が判ってしまう。

でもその平分が4文字くらいで127bitの原始多項式M系列なら簡単って訳にはゆかないだろうけど
>>921を読むと、 暗号化そのものはRSAを使って
カギとなる素数ペアを作る為に乱数を発生したいという事だよね?

だったら、>>933でいいんじゃないの?
 ・時計
 ・キーボード
 ・マウス
 ・Waveデバイス
 とかのデータとかから16バイトくらいのバイト列を作って
それをM系列やメルセンヌ・ツイスターの種にして乱数を発生させて、
その乱数をタイマー割り込みで発生させつづけておいて、適当にサンプリングすると
>>933
>その中からメルセンヌ・ツイスターをつかった乱数を
>元に抽出して使ったらOKですか?

どうしてそこにわざわざメルセンヌ・ツイスターを
使わなくてはいけないのか小一時間問い詰めたい。
>>936
解像度から考えて発生する乱数の上限が固定されるからです。

ついでに、ちょっと質問したいのですが…
BYTEごとに区切ってRSAで暗号化していくと考えまして。
そうすると、必然的に入力される暗号文は0〜255までだということに
なりますよね?、BYTEごとに区切っていくやりかたは脆弱な実装でしょうか?
938デフォルトの名無しさん:04/03/09 17:04
暗号初心者です。以下のデータを解読して文書を見つけてください。
解読ができたらこのスレに見つけた文書をレスしてください。

D9 E7 E1 55 22 10 9F 4A 9A BD C8 AC BE A1 6C 07
13 BC 4C D3 E3 A4 B8 EF E7 5A 5B E7 41 9C D8 17
28 A9 47 14 7F 0B B0 E1 65 60 D4 5F 26 DF C6 42
5C 7F C7 72 F1 E8 9D CA B6 9E DE B9 2C 57 4B E9
4F 70 5C 16 3A 47 70 86 98 55 10 56 ED E9 85 1F
9A 34 68 F4 C6 BD 8E 4C 61 48 0B 10 A7 D7 91 6A
59 92 7D 2F D9 9C 25 C7 58 23 21 89 20 74 4E 08
27 31 D1 4D 58 B5 BD D3 78 E2 26 57 D8 A2 2A E1
38 5E 5A 20 3E 6C F5 C4 30 4B 22 3D 2C F5 03 2D
C3 84 61 8E D0 3C 58 3E 96 74 CD 01 4A A1 2A A9
8B A5 92 61 81 BA 1A 97 F1 E5 DF 01 CD 8C 00 6E
21 9C 08 BF 2C 2A 40 43 84 D6 03 8A 97 A9 52 E4
93 B6 C4 4B 8B D3 15 6A 45 07 93 04 E6 3A D3 3B
E0 9A C9 42 DB AE FD D1 29 A9 95 16 B5 62 BE 65
12 C1 C5 8B 07 DE 1C 3C B4 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 17

解読して文書を見つけたとしても
アクセスすると不正アクセス法だかで逮捕されるぞ
>>938
スレタイと空気読んでから釣りに来い
941デフォルトの名無しさん:04/03/09 19:04
参考のデータを頼りに問題の暗号文を解いてください。
http://www.42ch.net/UploaderSmall/source/1078823862.zip
あqwせdrftgyふじこlp
新聞から「政治家」や「容疑者」などの修飾つき人名だけ取り出す

とかってどう考える?
「政治家データベースを使う」とかはナシよ。

なんかベイズ理論てのまで逝ってしまいそうで、もうだめぽ。
容疑者の文字を見つけたらその前後の文字列を全部登録

”不在だった野木容疑者”
”夜勤だった野木容疑者"
"殺人容疑で野木容疑者"
  ↓
"野木容疑者"

"野木巨之(のりゆき)容疑者” 野本が一致するので 野本巨之(のりゆき)を抽出
945デフォルトの名無しさん:04/03/12 20:18
ハッシュについて教えてください。
シノニムが発生した時はその次に格納することにします。
サイズは10とします。

ここで
11 % 10 = 1に[One1]を格納
21 % 10 = 1で重複したので 2に[One2]を格納
13 % 10 = 3に[Three1]を格納
31 % 10 = 1で重複したので 4に[One3]を格納
41 % 10 = 1で重複したので 5に[One4]を格納

次に[One2]を削除する。One3,One4を辿れるようにする為に
One2以降Nullまでをひとつずつずらす。
すると[Three1]の位置が2にずれるので
検索する時に[Three1]は無いことになってしまいます。

これはどのようにしたらいいんですか。
チェーン法を使わずに、オープンアドレス法で解決する方法を教えてください
>945
削除した時に「削除された」マークを[One2]に格納する。
「データがない」とは区別できるからその後も普通に使える。
オープンアドレス法は怖くて使えない
>>947
なんで?
945みたいな不具合続出
削除をまともに実装すればいいだけでは?
951デフォルトの名無しさん:04/03/12 22:32
typedef struct _A{
B *b;
}A;

typedef struct _B{
A *a;
}B;

Aの構造体にはBのポインタ
Bの構造体にはAのポインタ

をお互いに参照させたいのですがどうすればよいのでしょうか?

構造体Aを先に書くと、構造体Bは後なので参照できず。
かといって、構造体Bを先に書くと、構造体Aが後ろになって参照できなくなってしまいます。

相互に構造体のアドレスを参照する方法を教えてください。
struct _B *b;
953デフォルトの名無しさん:04/03/12 22:47
>>950
なんつーの、
チェイン法よりアバウトさに欠けるっていうか。
バグる確立が高い。
なんだ、コーディングがタコなだけか
955貧乏紙:04/03/12 22:51
シーケンシャル方が確実!
まちがいない!!!
>>953
書き込みもバグってますよ
957951:04/03/12 23:02
>>952
ありがとうございます。こんなに簡単だったのか・・。
↓じゃ、オープン法のまともな実装ってやつを書いてくれや
959945:04/03/12 23:07
で、結局どうなんですか。
手元の本には削除について書いてない代わりに
チェーン法よりオープンアドレス法のほうが良く使われる
って書いてあるんだな
960デフォルトの名無しさん:04/03/12 23:59
オープンハッシュで削除許すと、キーがあるかどうかは
最後まで舐めてみないとわからないんで、
削除フラグの他に終端かどうかを示すフラグとか付けたり
細工しないとやってられん。

な、ややこしいだろ?
正直チェインとは天と地ほど違うぜ。
>>960
必要なのは削除フラグだけだぞ。
終端を示すフラグなんかいらん。
削除しないような応用だったらどうですか?
963デフォルトの名無しさん:04/03/13 00:15
>>961
それだとミスヒット検索がえらい遅くなるだろ。
>>963
検索したいデータがなかった場合、すべての要素を調べてしまうってこと?
要素数が多くなったらハッシュを拡張する前提だと、どこかに終端があるはずなんだがな。
966デフォルトの名無しさん:04/03/13 01:45
それを説明してみたまえよ
>>966
表を広げて隙間を作る
で?
>>959
昔、使えるメモリが本当に少なかった頃は、動的メモリ確保が
要らないオープンアドレッシングも良く使われてたと思うけど、
動的メモリ確保が当たり前な現代では、むしろ連鎖法の方が
良く使われている気がする。
少なくとも、オープンソースソフトウェアでは、ほとんどの場合
連鎖法を使ってると思うけどなあ。
970デフォルトの名無しさん:04/03/13 10:10
知ったかしか出来ないお前らに一つ問う。

" オープンハッシュ" って、一体どんなデータ構造だ?

まずは自分の知識だけで答えを用意してから Google で検索してみな。
>>970
次スレおねがいします
>>970
ワラタ
>>970
そんなの誰でも分かってたよ。
本筋に関係のないものに突っ込んでどうする。
974945:04/03/13 13:55
ワロタ
s/オープンハッシュ/オープンアドレス/g;
すまんなぁ。ネタじゃないんだよ
>>953
同意
チェインのなら10分ぐらいで組める。
976943
>>944 ありがとうです。やってみるです。