kowala's home

kowala's home
這裡是我的學習筆記,陸續增加中。
http://kowala21.blogspot.com

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

2011-10-12

Dev C++ 製作動態三維陣列物件

資料存取物件化之二

kowala's home
http://kowala21.blogspot.com

繼前一篇 物件化的資料存取-動態二維陣列物件,再接再厲推出了三維陣列物件,其實原理都一樣,就是ㄧ串指標陣列,後面接個 int 元素陣列(本例為int),示意如下。

二維陣列物件     指標陣列->int 元素陣列

三維陣列物件    指標陣列-> 指標陣列->int 元素陣列

然後把它封裝起來,三維陣列物件應該很夠用了,已能處理大多數的問題了。

先來看看執行結果


紅色圈選處是測試寫入,最下面三個是讀出測試,完整程式碼如下。

#include <cstdlib>
#include <iostream>

using namespace std;

/*******************************************************************
3D array Object
2011-10-12
kowala's home  http://kowala21.blogspot.com
ref: http://www.programmer-club.com.tw/ShowSameTitleN/c/37868.html  
********************************************************************/
typedef int** array3d;
class SrcData3D{
    array3d *matrix;
    int m_rows;
    int m_cols;
    int m_hight;
    public:
    SrcData3D();
    void initData(int row,int col,int hight,int var);
    void relaxData();
    void dumpData();
    void setData(int row,int col,int hight,int var);
    int getData(int row,int col,int hight);
};

int main(int argc, char *argv[]){
    system("cls");
    int row=3,col=7,hight=5;

    SrcData3D s3d;

    cout << "initial 3D array by -1 ..." << endl;
    s3d.initData(row,col,hight,-1);
    s3d.dumpData();
  
    cout << "set value to 3D array..." << endl;
    s3d.setData(0,1,0,1);
    s3d.setData(0,2,1,2);
    s3d.setData(0,3,2,3);
    s3d.setData(1,2,1,4);
    s3d.setData(1,3,2,5);
    s3d.setData(1,4,3,6);
    s3d.setData(2,3,2,7);
    s3d.setData(2,4,3,8);
    s3d.setData(2,5,4,9);
    s3d.dumpData();
  
    cout << "get value from 3D array..." << endl;
    cout << "[0,3,2]=" << s3d.getData(0,3,2) << endl;
    cout << "[1,4,3]=" << s3d.getData(1,4,3) << endl;
    cout << "[2,5,4]=" << s3d.getData(2,5,4) << endl;
  
    s3d.relaxData();  

    system("PAUSE");
    return EXIT_SUCCESS;
}
//建構子
SrcData3D::SrcData3D(){    m_rows=1;m_cols=2;m_hight=3;}
//設定參數
void SrcData3D::setData(int row,int col,int hight,int var){    matrix[row][col][hight]=var;}
//取出參數
int SrcData3D::getData(int row,int col,int hight){    return matrix[row][col][hight];}
//初始化陣列
void SrcData3D::initData(int row,int col,int hight,int var){
    m_rows=row;m_cols=col;m_hight=hight;
    SrcData3D::matrix=new array3d[m_rows];
    for(int i=0;i<m_rows;i++){
        SrcData3D::matrix[i]=new int*[m_cols];
        for(int j=0;j<m_cols;j++){
            SrcData3D::matrix[i][j]=new int[m_hight];
            for(int k=0;k<m_hight;k++){
                SrcData3D::matrix[i][j][k]=var;
            }
        }
    }
}
//釋放陣列
void SrcData3D::relaxData(){
    for(int i=0;i<m_rows;i++){      
        for(int j=0;j<m_cols;j++){
            delete [] SrcData3D::matrix[i][j];      
        }
        delete [] SrcData3D::matrix[i];
    }
    delete [] SrcData3D::matrix;
}
//傾印資料
void SrcData3D::dumpData(){  
    cout << "rows=" << m_rows << ",cols=" << m_cols << ",hight=" << m_hight << endl;
    for(int i=0;i<m_rows;i++){      
        for(int j=0;j<m_cols;j++){
            for(int k=0;k<m_hight;k++){
                cout << "[" << i << "," << j << "," << k << "]=" << SrcData3D::matrix[i][j][k] << "  ";
            }
            cout << endl;
        }
        cout << endl;
    }
    cout << endl;
}

2011-10-11

Dev C++ 物件化的資料存取-動態二維陣列物件

資料存取物件化

kowala's home
http://kowala21.blogspot.com

這裡使用Dev C++ 來製作動態二維陣列物件,通常在使用陣列時,常常會被指標搞的暈頭轉向,但是使用陣列用來儲存資料,卻又是必須的工具,如何避免被複雜的指標干擾寫作程式,使用物件的觀念卻是必要的,把底層複雜運算封裝起來,上層就可以單純的存取,這對於大型程式開發,是很重要的觀念。

底下程式是先製作一個動態二維陣列物件,然後實作,存取測試,完整程式碼如下:
本篇是使用 C++ 語法



#include <cstdlib>
#include <iostream>

using namespace std;
/*******************************************************************
2D Array Object
2011-10-11kowala's home  http://kowala21.blogspot.com
ref: http://www.programmer-club.com.tw/ShowSameTitleN/c/37868.html   
********************************************************************/
typedef int* array;
class SrcData{
    array *matrix;
    int m_rows;
    int m_cols;
    public:
    SrcData();
    void initData(int row,int col,int var);
    void relaxData();
    void dumpData();
    void setData(int row,int col,int var);
    int getData(int row,int col);
};

int main(int argc, char *argv[]){
    system("cls");
    int row=3,col=7;
    SrcData sd;
   
    cout << "initial array by -1 ..." << endl;
    sd.initData(row,col,-1);
    sd.dumpData();
   
    cout << "set value to array..." << endl;
    sd.setData(0,1,1);
    sd.setData(0,2,2);
    sd.setData(0,3,3);
    sd.setData(1,2,4);
    sd.setData(1,3,5);
    sd.setData(1,4,6);
    sd.setData(2,3,7);
    sd.setData(2,4,8);
    sd.setData(2,5,9);
    sd.dumpData();
   
    cout << "get value from array..." << endl;
    cout << "[0,1]=" << sd.getData(0,1) << endl;
    cout << "[1,2]=" << sd.getData(1,2) << endl;
    cout << "[2,3]=" << sd.getData(2,3) << endl;
   
    sd.relaxData();   
   
    system("PAUSE");
    return EXIT_SUCCESS;
}
//--------------------------------------------------
//建構子
SrcData::SrcData(){    m_rows=1;m_cols=2;}
//設定參數
void SrcData::setData(int row,int col,int var){    matrix[row][col]=var;}
//取出參數
int SrcData::getData(int row,int col){    return matrix[row][col];}
//初始化陣列
void SrcData::initData(int row,int col,int var){
    m_rows=row;m_cols=col;
    SrcData::matrix=new array[m_rows];
    for(int i=0;i<m_rows;i++){
        SrcData::matrix[i]=new int[m_cols];
        for(int j=0;j<m_cols;j++){
            SrcData::matrix[i][j]=var;
        }
    }
}
//釋放陣列
void SrcData::relaxData(){
    for(int i=0;i<m_rows;i++){
        delete [] SrcData::matrix[i];       
    }
    delete [] SrcData::matrix;
}
//傾印資料
void SrcData::dumpData(){
    cout << "rows=" << m_rows << ",cols=" << m_cols << endl;
    for(int i=0;i<m_rows;i++){       
        for(int j=0;j<m_cols;j++){           
            cout << "[" << i << "," << j << "]=" << SrcData::matrix[i][j] << "  ";
        }
        cout << endl;
    }
    cout << endl;
}

執行結果如下圖




參考資料:
1.如何傳遞動態的二維陣列給函式 doggie (franklin)
http://www.programmer-club.com.tw/ShowSameTitleN/c/37868.html
2.C++教學(二十八):在參數列傳遞陣列 大頭嬰
http://www.hala.bz/read.php?tid=7138

2011-10-01

Dev C++ 參數 main(int argc, char *argv[])

這是第一篇介紹 Dev C++ 如何操作,開始先介紹環境設定,再來是如何讀入參數,用 Dev C++ 這個工具可以完全取代 Turbo C 2.0,毫無問題.

經過這幾天測試,它可以正確的編譯32位元命令列程式,不再有定址的限制了 ^^
但是它預設的編輯視窗,若在要左邊顯示行號,則會出現一片黑,或者用滑鼠反白,也會出現一片黑,這是預設前景色跟背景色沒設好的關係,沒關係,直接找到 Visual Studio 風格套用,就一切正常了。



 一開始要先開個專案,名稱隨意,然後選擇 Console Application,這就是命令列模式,然後找個地方存起來,我是在桌面弄一個資料夾來放,比較方便。


可以先試跑一下看看,這是 DevC++ 產生的程式碼。



接著來看看如何傳參數給程式,當作第一個範例。我們必須先設定執行的參數,然後再用程式碼去取出來,最後印出來。先找到

執行\參數\要傳給程式的參數

輸入

70230 out70230 20 2 2

 一共5個,然後按確定,如下圖。



然後輸入下列程式碼


 #include <stdio.h>
#include <stdlib.h>
    char msg[128]="\nKG Ver:\t1.0.0\nDate:\t2011-09-30\nUsage:\tKG infile outfile samples chknum continuenum\n";
    char inputfile[32];        //資料檔名
    char outputfile[32];    //輸出檔名
    int samples;            //樣本數
    int chknum;                //比對基數
    int contnum;            //連續次數
 int main(int argc, char *argv[]){
     int i,n;
     system("cls");
    printf("%s",msg);
    //取參數
    strcpy(inputfile,argv[1]);
    strcpy(outputfile,argv[2]);
    samples=atoi(argv[3]);
    chknum=atoi(argv[4]);
    contnum=atoi(argv[5]);
    printf("\nargc = %d\n",argc);
    for(i=0;i<argc;i++)printf("argv[%d] = %s\n",i,argv[i]);
    system("PAUSE");
    return 0;
}

輸入完成後,按下工具列圖示,左上第2排第3個,編譯並執行,就可以看到執行畫面了,很簡單就可以上手的,語法就是標準的C語言。
上面程式碼中,用 system("cls"); 來清畫面,以取代以前 Turbo C 的  clrscr();

執行畫面,如何?正確取得參數並秀出來了。 ^^


附帶一提,我在除錯過程中,發生過 lag 現象,CPU跑到99%,等了許久,原因不明,當時是使用單步執行 F7。若是迴圈太多的話,建議直接看程式跑的結果,或是加入暫停的副程式碼來代替單步執行 F7,如下所示。

 mywait("now, it is at where...");
 ...

 /***************************
    暫停,Enter繼續,除錯用
****************************/
void mywait(char *msg){
    char ch;
    printf("\n%s",msg);
    while ((ch=getchar())!='\n'){}  
}


Dev C++ 網址  http://www.bloodshed.net/dev/devcpp.html
這篇本來昨天就要寫的,結果都在看 youtube,昨天的大熱門新聞,就是天宮一號了,現在有太空站的國家就是美、俄、中 三國了,真強。

天宮一號發射圓滿成功 
http://www.youtube.com/watch?v=IVZSs1GmG5M

這是之前神州七號的太空漫步,回顧一下。
http://www.youtube.com/watch?v=gMxQEHfU6hM&feature=like-suggest&list=UL