宮崎大学 >> 工学部 >> 情報システム工学科 >> 伊達 >>
Last modified: Wed Apr 9 17:15:39 JST 2008

アルゴリズム

ここではアルゴリズムを簡潔に表現できる言語を使います．
個別の言語については別のところで学んでください．

• 問題： 1,2,...,n という n 個の整数から m 個の重複のない乱数列を 生成せよ．
  Robert W. Floyd 教授 (1936-2001) によるアルゴリズム． （とても自分では発見・発明できそうにない．）
  More Programming Perls (J.L. Bentley 著）を参考： floyd001.awk
  

  BEGIN { m = 10; n = 20
                  for (j = n-m+1; j <= n; j++) {
                          t = 1 + int(j * rand())
                          if (t in s) s[j] = 1
                          else s[t] = 1
                  }
                  for (i in s) print i
  }
  

  rand() return a pseudo-random floating point number grater than or equal 0 and less than 1
  int(j*rand()) +1 returns a random number integer between 1 and j

  % awk -f floyd001.awk
  

• 問題： そもそも，コンピュータでどうやって乱数（らしきもの）を 生成できるか．
  Derrick H. Lehmer 教授(1905-1991) による linear congruential generator (1949? 1951?)．

  x[t+1] = ( a x[t] +c ) mod m
  

  たとえば a-12,c=0,m=31, x[1]=1 を代入してみると，1,13,14,27,...
  実際に最も推奨されているパラメータは a=16807, c=0, m=2147483647 ．
  S.K.Park and K.W.Miller (Comm. ACM, vol.32) より．

使わないと，すぐに忘れる．
一度習った記憶があれば，これを見れば思い出せる，というようなメモの作成が， このページのねらい．

宮崎大学 >> 工学部 >> 情報システム工学科 >> 伊達 >>