隨筆 - 154  文章 - 60  trackbacks - 0
          <2008年2月>
          272829303112
          3456789
          10111213141516
          17181920212223
          2425262728291
          2345678

          聲明:

          該blog是為了收集資料,認(rèn)識朋友,學(xué)習(xí)、提高技術(shù),所以本blog的內(nèi)容除非聲明,否則一律為轉(zhuǎn)載!!

          感謝那些公開自己技術(shù)成果的高人們!!!

          支持開源,尊重他人的勞動!!

          常用鏈接

          留言簿(3)

          隨筆分類(148)

          隨筆檔案(143)

          收藏夾(2)

          其他

          學(xué)習(xí)(技術(shù))

          觀察思考(非技術(shù))

          搜索

          •  

          最新評論

          閱讀排行榜

          評論排行榜

          /**
           *
           *問題或許可以是這樣:產(chǎn)生m個隨機(jī)正整數(shù),要求范圍是從1到n,平且它們互不相同。
          問題或許可以這樣解決:

          假設(shè)我們已經(jīng)有了經(jīng)過排序的(升序),且滿足要求的k個正整數(shù),我們繼續(xù):
          1、在從1到n-k的區(qū)間范圍內(nèi),產(chǎn)生一個隨機(jī)的正整數(shù)i1;
          2、統(tǒng)計在已有序列中比i1小的數(shù),將其個數(shù)加到i1上,得到i2;再統(tǒng)計從i1到i2數(shù)的個數(shù),得到i3;一直循環(huán),直到i不變?yōu)橹埂H缓螅裪插入已有的序列。這個過程相當(dāng)于從頭數(shù)出i1個空白,以此來保證新的數(shù)是隨機(jī)的。
          3、這時得到了k+1個滿足要求的數(shù),然后就循環(huán)吧。
          上面的方法適用于n很大,但是m很小的時候。

          如果m和n都很大,并且希望一次性的產(chǎn)生,那么:
          1先產(chǎn)生有一定冗余的隨機(jī)正整數(shù),然后排序,然后去掉相同的數(shù)。
          如果,產(chǎn)生了超額的數(shù),可以將數(shù)列再打亂順序,然后,取出符合規(guī)定的數(shù)目的數(shù)。

          當(dāng)然,也可以兩種方法相結(jié)合,就是:
          1、先產(chǎn)生超過需求的、有一定冗余的隨機(jī)正整數(shù),然后排序,然后去掉相同的數(shù),并且保存下來。記錄它的數(shù)目m1 >m;
          2、當(dāng)要用時,在產(chǎn)生一個從1到m的隨機(jī)數(shù)j,然后取出數(shù)據(jù)庫中第j個數(shù),輸出,并且把它從數(shù)據(jù)庫中刪除到。
           *
           *
           *
           *
           *
           *
           *
           *
           *數(shù)據(jù)有點(diǎn)大,用了128m
          start_1   ();   是即時輸出(因?yàn)橛胋oolean數(shù)組,所以內(nèi)存小得多)
          start_2   ();   是把數(shù)據(jù)存進(jìn)數(shù)組,以便再處理(需要內(nèi)存很大,不贊成使用)
          如果要處理數(shù)據(jù),可以用   start_1   ();   把數(shù)據(jù)保存進(jìn)文件,再從文件中讀取數(shù)據(jù)進(jìn)行處理。

           */
          public class Main{
           
           public final int n = 10000000;
           
           public Main () {
                  start_1();
                  //start_2 ();
              }
             
              public static void main (String[] args) {
                  new Main();
              }
             
              public void start_1() {
                  //布朗型默認(rèn)為 false
                  boolean[] barr = new boolean[n];
                  //
                  java.util.Random r = new java.util.Random ();
                  int j = 0, x;
                  int m = n;
                  while(j < m) {
                      x = r.nextInt (n);
                      if (! barr[x]) {
                          j++;
                          barr[x] = true;
                          System.out.println (x);
                      }
                  }
              }
             
              public void start_2() {
                  //整型默認(rèn)為 0
                  int[] iarr = new int[n];
                  //
                  java.util.Random r = new java.util.Random ();
                  int j = 0, x;
                  int m = n;
                  //少循環(huán)一次,因?yàn)橐?0
                  while(j < m-1) {
                      x = r.nextInt (n);
                      if (iarr[x] == 0) {
                          j++;
                          iarr[x] = j;
                      }
                  }
              }
          }
          /*
           *上面的算法,沒有優(yōu)化,生成數(shù)據(jù)耗時間。
          下面的算法改進(jìn)了一下。生成所有數(shù)據(jù)半分鐘左右。
          +----------
          |   0...999999
          |   .
          |   .
          |   .
          |   99

          Java code
          public class Main {
             
              public Main () {
                  start_1 ();
                  start_2 ();
              }
             
              public static void main (String[] args) {
                  new Main ();
              }
             
              ** void start_1 () {
                  for (int i = 0; i < n; i++) {
                      byte j = 0;
                      while(j < m-1) {
                          int x = r.nextInt (m);
                          if (barr_1[x] == 0) {
                              j++;
                              barr_1[x] = j;
                          }
                      }
                  }
              }
             
              ** void start_2 () {
                  int j = 0;
                  while(j < n) {
                      int x = r.nextInt (n);
                      int y = (int) barr_2[x];
                      if (y < m) {
                          j++;
                          barr_2[x]++;
                          int z = ((int) barr_1[x][y]) * n;
                          //System.out.println (x + z);
                      }
                  }
              }
             
              ** final int s = 10000*10000;
              ** final int m = 100;
              ** final int n = s/m;
              ** byte[][] barr_1 = new byte[n][m];
              ** byte[] barr_2 = new byte[n];
              ** java.util.Random r = new java.util.Random ();
             
          }
          */

          /*
           *和一位仁兄在另一個帖子爭論中,受到啟發(fā)。
          終于悟出一種時間復(fù)雜度極低的算法。
          (可以證明,任意一個數(shù)   在   任意位置的概率   都為   1/n)

          因?yàn)閮?nèi)存不夠,所以改成了7個9來算。總時間2秒

          Java code
          public class Main {
             
              public Main () {
                  start ();
              }
             
              public static void main (String args[]) {
                  new Main ();
              }
             
              ** void start () {
                  java.util.Random r = new java.util.Random ();
                  for (int i = 0; i < n; i++) {
                      int x = r.nextInt (i+1);
                      iarr = iarr[x];
                      iarr[x] = i;
                  }
                  //
                  int m = 10;
                  for (int i = 0; i < m; i++) {
                      System.out.print (iarr + " ");
                  }
              }
             
              ** final int n = 1000*10000;
              ** int[] iarr = new int[n];
             
          }
          */

          posted on 2008-02-01 11:20 lk 閱讀(785) 評論(0)  編輯  收藏 所屬分類: j2se
          主站蜘蛛池模板: 周至县| 阿克| 封开县| 合水县| 滨海县| 湟源县| 区。| 柘荣县| 扶余县| 酉阳| 资源县| 全椒县| 阿克| 茂名市| 根河市| 大方县| 江西省| 南澳县| 武清区| 远安县| 新源县| 巴林右旗| 曲松县| 大兴区| 太谷县| 崇义县| 翁源县| 南木林县| 阿瓦提县| 青浦区| 林西县| 莎车县| 泾川县| 渑池县| 嵊州市| 长海县| 扶风县| 华容县| 新乐市| 湘乡市| 专栏|