kowala's home

2011-10-26

Dev C++ 亂數產生器-究竟版

嘿嘿！此究竟非彼究竟，這只是限於使用time來產生的最亂，當然，這還不真亂，眼尖者必能覺察。

先看一下代碼

//亂數產生器
int getRandom(int min,int max){
    int r;
    clock_t seed = clock();
    srand(seed);
    r= min + rand()%(max-min+1);
    return r;
}

這是取時間來當種子，使用的值是毫秒，下圖是模擬大樂透開獎，49選6... 主要是要產生49個不重複的亂數，但是現在電腦都算太快，亂數結果數值會一樣...

這時就要想個辦法減速一下，在前一個主題，遞迴函數-費式數列(Fibonacci)，就派上用場了，我們可以利用遞迴函數算很慢的特性，來當減速器，隨便找個質數填進去，f(31)

#include <cstdlib>
#include <iostream>
#include <iomanip.h>

using namespace std;

//亂數產生器
int getRandom(int min,int max){
    int r;
    clock_t seed = clock();
    srand(seed);
    r= min + rand()%(max-min+1);
    return r;
}
//費式數列(Fibonacci)
double f(double n){
    if(n<=2)return 1;
    return f(n-1)+f(n-2);
}
int main(int argc, char *argv[]){
    int i;
    system("cls");

    cout << "亂數測試..." << endl;
    for(int i=1;i<=49;i++){
        f(31);    //減速器
        cout << setw(3) << setprecision(3) << getRandom(1,49) << " ";
    }
    cout << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

看來有點亂了，減速成功!

接著是消去重複數，這需要用個陣列來幫忙。

int main(int argc, char *argv[]){
    int i,n,v,lo[49];
    system("cls");

    cout << "亂數測試..." << endl;
    for(int i=0;i<49;i++){
        f(37);
        v=getRandom(1,49);
        n=0;
        while(n<i){
            if(lo[n++]==v){
                f(23);
                v=getRandom(1,49);
                n=0;
            }
        }
        lo[i]=v;
        cout << setw(3) << setprecision(3) << lo[i] << " ";
    }
    cout << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

這還是不夠亂，生氣，最後一招，改良種子，取 UTC + 毫秒來當種子

clock_t seed = time(0)+clock();

結果不錯，每次都不一樣，這樣就夠亂了。

//亂數產生器-究竟版
int getRandom(int min,int max){
   int r;
   clock_t seed = time(0)+clock();
   srand(seed);
   r= min + rand()%(max-min+1);
   return r;
}

其實，這還是不夠亂，上圖每個數字都差3-4之間，而且都是規律遞增，所謂亂數，就是無規律，閉著眼亂點，點中就算，這樣才夠亂，我深深懷疑，電腦或是數學式能否產生出真正的亂數，要真亂的話，我只想到一個，自己拿骰子擲，然後記錄點數。

下表是我找的亂數表，懶得自己打字，所以從網路copy來的，應該是比這個時間產生的要亂些，可以充當種子。

http://www.stat.nuk.edu.tw/prost/content2/statics_2.htm

29280 39655 18902 92531 90374 07109 26627 59587 84340 98351
20123 82082 55477 22059 43168 12903 13436 25523 21090 73449
66405 35287 33248 67657 07702 01474 66068 01125 59258 30138
97299 83419 13069 17826 76984 48906 10567 17829 00723 46700
83923 92076 98880 33942 46841 58731 36513 16681 88722 61984
11258 92175 94894 97606 11134 51941 43733 00514 06694 27706

http://wiki.mbalib.com/zh-tw/%E9%9A%8F%E6%9C%BA%E5%8F%B7%E7%A0%81%E8%A1%A8%E6%B3%95

03 47 43 73 86 36 96 47 36 61 46 98 63 71 62
97 74 24 67 62 42 81 14 57 20 42 53 32 37 32
16 76 02 27 66 56 50 26 71 07 32 90 79 78 53
12 56 85 99 26 96 96 68 27 31 05 03 72 93 15
55 59 56 35 64 38 54 82 46 22 31 62 43 09 90
16 22 77 94 39 49 54 43 54 82 17 37 93 23 78
84 42 17 53 31 57 24 55 06 88 77 04 74 47 67
63 01 63 78 59 16 95 55 67 19 98 10 50 71 75
33 21 12 34 29 78 64 56 07 82 52 42 07 44 28
57 60 86 32 44 09 47 02 96 54 49 17 46 09 62
18 18 07 92 46 44 17 16 58 09 79 83 86 19 62
26 62 38 97 75 84 16 07 44 99 83 11 46 32 24
23 42 40 54 74 82 97 77 77 81 07 45 32 14 08
62 36 28 19 95 50 92 26 11 97 00 56 76 31 38
37 85 94 35 12 83 39 50 08 30 42 34 07 96 88
70 29 17 12 13 40 33 20 38 26 13 89 51 03 74
56 62 18 37 35 96 83 50 87 75 97 12 25 93 47
99 49 57 22 77 88 42 95 45 72 16 64 36 16 00
16 08 15 04 72 33 27 14 34 09 45 59 34 68 49
31 16 93 32 43 50 27 89 87 19 20 15 37 00 49

假定這兩張表是真亂數，但是引用時，仍然會有決定哪個數值，索引值取捨的問題，你索引如何產生？如果還是時間來源的話，那依舊是陷入先前同樣的問題。

再接再厲，引入亂數表充當種子，再把前次結果加入種子，結果看起來似乎很亂了，改善了數字差3-4之間，規律遞增的問題，這樣的結果是可以接受，但是缺點是複雜了點...

//亂數產生器-引入亂數表充當種子+反饋
int getRandom(int min,int max,int res){
    int n,v,seed[]={
        29280,39655,18902,92531,90374, 7109,26627,59587,84340,98351,
        20123,82082,55477,22059,43168,12903,13436,25523,21090,73449,
        66405,35287,33248,67657, 7702, 1474,66068, 1125,59258,30138,
        97299,83419,13069,17826,76984,48906,10567,17829, 723,46700,
        83923,92076,98880,33942,46841,58731,36513,16681,88722,61984,
        11258,92175,94894,97606,11134,51941,43733, 514, 6694,27706    };
    n=(time(0)+clock())%60;
    v=seed[n]+clock()+res;
    srand(v);
    return (min + rand()%(max-min+1));
}

執行結果，似乎很亂，這樣的結果是可以接受了。

完整測試列表

#include <cstdlib>
#include <iostream>
#include <iomanip.h>

using namespace std;

//亂數產生器-引入亂數表充當種子+反饋
int getRandom(int min,int max,int res){
    int n,v,seed[]={
        29280,39655,18902,92531,90374, 7109,26627,59587,84340,98351,
        20123,82082,55477,22059,43168,12903,13436,25523,21090,73449,
        66405,35287,33248,67657, 7702, 1474,66068, 1125,59258,30138,
        97299,83419,13069,17826,76984,48906,10567,17829, 723,46700,
        83923,92076,98880,33942,46841,58731,36513,16681,88722,61984,
        11258,92175,94894,97606,11134,51941,43733, 514, 6694,27706    };
    n=(time(0)+clock())%60;
    v=seed[n]+clock()+res;
    srand(v);
    return (min + rand()%(max-min+1));
}
//費式數列(Fibonacci)
double f(double n){
    if(n<=2)return 1;
    return f(n-1)+f(n-2);
}
int main(int argc, char *argv[]){
    int i,n,v,lo[49];
    long k=0;
    system("cls");

    cout << "亂數測試..." << endl;
    for(int i=0;i<49;i++){
        v=getRandom(1,49,lo[i]);
        f(i%31); //減速器
        n=0;k=0;
        while(n<i){
            if(lo[n++]==v){
                 v=getRandom(1,49,lo[i]);
                f(i%11); //減速器
                n=0;
            }
            k++;   //計次
        }
        lo[i]=v;
        cout << setw(3) << setprecision(3) << lo[i] << " ";
    }
    cout << "\n共計算了 " << k << " 次..." <<endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

2011-10-25

Dev C++ 有趣的遞迴函數-費式數列(Fibonacci)

C 語言有個好玩的寫法，就是遞迴函數(Recursive call)，遞迴函數有幾項特徵，就是

1.自己呼叫自己
2.必須存在終止條件

來找個例子，一般談到遞迴，總是喜歡拿費式數列(Fibonacci)來說明，這裡也簡單的介紹一下，詳細的資料可以在維基百科[1]找到。

費式數列(Fibonacci)
數列的前兩項為 1、1，之後的每一項為前兩項之和，
即 Fn=Fn-1+Fn-2，數列的前 10 項為：
1、1、2、3、5、8、13、21、34、55、89。

是使用一種線性遞迴關係式來定義：

$F_{0} = 0 \,$

$F_{1} = 1 \,$

$F_{n} = F_{n-1}+F_{n-2} \,$

設若: $F_{n} / F_{n-1}\,$ 當n趨於無限大之極限值存在，則其值為 $1+\sqrt{5} \over 2\,$ = Φ 恰為黃金分割之ㄧ值，1.618....，另一值則為0.618....，兩值互為倒數，也就是說1.618....分之1=0.618....，反之亦然。

我們任意取兩個連續的數來除，很容易可以得到一比值

    89/55=1.618181818181...
    55/34=1.617647058823...
    34/21=1.619047619047...
    21/13=1.615384615384...
    13/8=1.625
    8/5=1.6
    5/3=1.66666666666666...

這就是有名的黃金比例 1.618...

好了，介紹到這裡，讓我們來看看如何在 C++ 中實現...

這是費式數列(Fibonacci)的寫法，C++可以很簡潔的表示出來[2].

double f(double n){
    if(n<=2)return 1;
    return f(n-1)+f(n-2);
}

簡單說明一下遞迴函數的特徵

if(n<=2)return 1;          這是中止條件
return f(n-1)+f(n-2);    這是自己呼叫自己

來實做一下
//-----------------------------------------------------------
#include <cstdlib>
#include <iostream>
#include <iomanip.h>

using namespace std;

//費式數列(Fibonacci)
double f(double n){
   if(n<=2)return 1;
   return f(n-1)+f(n-2);
}
int main(int argc, char *argv[]){
   int i,n;
   system("cls");

   cout << "遞迴測試 - 費式數列(Fibonacci)" << endl;
   cout << "------------------------------" << endl;

   n=30;
   for(int i=1;i<=n;i++){
       cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i
       << setw(10) << setprecision(10) << setfill(' ')<< f(i) << "\n";
   }

   cout << "\n黃金比例 (f(9)/f(8)) = " << f(9)/f(8) << endl << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

//-----------------------------------------------------------

結果如下

這個是為了對齊而對 cout 做了一些指定
cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i

setw(5) 設定5個字組寬
setprecision(5) 設定5個數字
setfill(' ') 空格補 space

為了觀察遞迴函數的運作，我們在裏頭加一行顯示其值，如下

double fi(double n){
    cout << n << " ";
    if(n<=2)return 1;
    return fi(n-1)+fi(n-2);
}

再把 n 改小一點，n=10，再跑看看

   n=10;
   for(int i=1;i<=n;i++){
       cout << "Loop " << setw(5) << setprecision(5) << setfill(' ') << i
       << setw(10) << setprecision(10) << setfill(' ')<< fi(i) << "\n";
   }

這次就可以清楚看到它被執行幾次了。

參考資料：
1.遞迴關係式
http://zh.wikipedia.org/wiki/%E9%81%9E%E8%BF%B4%E9%97%9C%E4%BF%82%E5%BC%8F
2.費式(Fibonacci)數列
http://dhcp.tcgs.tc.edu.tw/c/p014.htm