Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 17 kết quả

Đề tài: Thuật toán tìm số ngẫu nhiên ( không sử dụng hàm Rand)

  1. #1
    Ngày gia nhập
    01 2008
    Bài viết
    18

    Mặc định Thuật toán tìm số ngẫu nhiên ( không sử dụng hàm Rand)

    mình đang cố sức viết lại hàm Rand bằng thuật toán này
    anh em có thể xem qua nha
    Thuật toán này như sau:
    X(n+1) = a*X(n) + c (mod m)
    R(n) = X(n) / float(m) ---> random number in [0,1)
    R(n) = X(n) / float(m-1) ---> random number in [0,1]
    a,c,m là các số cố định do bạn chọn. Bạn có thể thấy rằng với thuật toán này thì chu kỳ sẽ là m, tức là chiều dài nhất có thể của chuỗi ngẫu nhiên là m. Thông thường, chọn (a mod 4 =1), c là số lẻ, m là 2^M.
    Thuật toán cần 1 số khởi tạo ban đầu, gọi là seed. Số seed này được chọn sao cho "ngẫu nhiên" nhất có thể. Recommend:
    X(0) = isec + 60*(imin+60*(ihr+24*(iday-1+31*(imon-1+12*iyr))));
    Trong đó, các biến isec, imin, ihr, iday, imon, iyr là các biến về thời gian và ngày giờ hệ thống (cần chú ý về overflow).

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    440

    Thật ra các tham số cần phải lựa chọn cẩn thận không phải là seed mà là a và c. Xem thêm:
    http://en.wikipedia.org/wiki/Linear_...tial_generator

  3. #3
    Ngày gia nhập
    08 2008
    Bài viết
    7

    X(n+1) = a*X(n) + c (mod m)
    minh sua lai doi chut X(n+1)=(a*X(n)+c)(mod m). Thuat toan nay goi la dong du tuyen tinh va thuong c=0.

  4. #4
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi cuong nguyen Xem bài viết
    minh sua lai doi chut X(n+1)=(a*X(n)+c)(mod m). Thuat toan nay goi la dong du tuyen tinh va thuong c=0.
    cái này chu kỳ lặp của nó là m thì phải, nếu mình không nhầm thì hàm Random tưởng đơn giản nhưng không hề đơn giản
    Time

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Đây là 1 số source tui sưu tầm được, thuật toán thì có đọc sơ qua, 1 số source vẫn chưa hiểu lắm, thôi thì post lên cho mọi người tham khảo và bàn luận để hiểu sâu hơn.
    Note : đa số source này tui đã format lại theo style của tui, vì đa phần source viết theo style K&R.
    C++ Code:
    1. #include <iostream>
    2.  
    3. #define N 624
    4. #define M 397
    5. #define MATRIX_A 0x9908b0df   /* constant vector a */
    6. #define UPPER_MASK 0x80000000 /* most significant w-r bits */
    7. #define LOWER_MASK 0x7fffffff /* least significant r bits */
    8.  
    9. /* Tempering parameters */  
    10. #define TEMPERING_MASK_B 0x9d2c5680
    11. #define TEMPERING_MASK_C 0xefc60000
    12. #define TEMPERING_SHIFT_U(y)  (y >> 11)
    13. #define TEMPERING_SHIFT_S(y)  (y << 7)
    14. #define TEMPERING_SHIFT_T(y)  (y << 15)
    15. #define TEMPERING_SHIFT_L(y)  (y >> 18)
    16.  
    17. static unsigned long mt[ N ] ; /* the array for the state vector  */
    18. static int mti = N + 1; /* mti==N+1 means mt[N] is not initialized */
    19.  
    20. /* initializing the array with a NONZERO seed */
    21. void sgenrand( unsigned long seed )
    22. {
    23.     /* setting initial seeds to mt[N] using         */
    24.     /* the generator Line 25 of Table 1 in          */
    25.     /* [KNUTH 1981, The Art of Computer Programming */
    26.     /*    Vol. 2 (2nd Ed.), pp102]                  */
    27.     mt[ 0 ]= seed & 0xffffffff;
    28.     for( mti = 1; mti < N;  mti++ )
    29.         mt[ mti ] = ( 69069 * mt[ mti - 1 ] ) & 0xffffffff;
    30. }
    31.  
    32. unsigned long genrand( void )
    33. {
    34.     unsigned long y;
    35.     static unsigned long mag01[ 2 ] = { 0x0, MATRIX_A };
    36.     /* mag01[x] = x * MATRIX_A  for x=0,1 */
    37.    
    38.  
    39.     /* generate N words at one time */
    40.     if( mti >= N )
    41.     {
    42.         int kk;
    43.         if( mti == N + 1 )   /* if sgenrand() has not been called, */
    44.             sgenrand( 4357 ); /* a default initial seed is used   */
    45.  
    46.         for( kk = 0; kk < N - M; kk++ )
    47.         {
    48.             y = ( mt[ kk ] & UPPER_MASK ) | ( mt[ kk + 1 ] & LOWER_MASK );
    49.             mt[ kk ] = mt[ kk + M ] ^ ( y >> 1 ) ^ mag01[ y & 0x1 ];
    50.         }
    51.      
    52.         for( ; kk < N - 1; kk++ )
    53.         {
    54.             y = ( mt[ kk ] & UPPER_MASK) | ( mt[ kk + 1 ] & LOWER_MASK );
    55.             mt[ kk ] = mt[ kk + ( M - N ) ] ^ ( y >> 1 ) ^ mag01[ y & 0x1 ];
    56.         }
    57.      
    58.         y = ( mt[ N - 1 ] & UPPER_MASK ) | ( mt[ 0 ] & LOWER_MASK );
    59.         mt[ N - 1 ] = mt[ M - 1 ] ^ ( y >> 1 ) ^ mag01[ y & 0x1 ];
    60.  
    61.         mti = 0;
    62.     }
    63.  
    64.     y = mt[mti++];
    65.     y ^= TEMPERING_SHIFT_U(y);
    66.     y ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
    67.     y ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
    68.     y ^= TEMPERING_SHIFT_L(y);
    69.  
    70.     return y;
    71. }

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Thuật toán tìm số ngẫu nhiên ( không sử dụng hàm Rand)

    Thuật toán Mersen :
    MTRand.h
    C++ Code:
    1. // Mersenne Twister abstract type
    2. // C++ wrapping of old straight c code
    3. // of the mersenne twister algorithm freely available on algorithm authors website.
    4. // c++ wrapper (c) const volatile
    5. // Here follows algorithm authors copyright notice...
    6. /* Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
    7.    All rights reserved.                          
    8.  
    9.    Redistribution and use in source and binary forms, with or without
    10.    modification, are permitted provided that the following conditions
    11.    are met:
    12.  
    13.      1. Redistributions of source code must retain the above copyright
    14.         notice, this list of conditions and the following disclaimer.
    15.  
    16.      2. Redistributions in binary form must reproduce the above copyright
    17.         notice, this list of conditions and the following disclaimer in the
    18.         documentation and/or other materials provided with the distribution.
    19.  
    20.      3. The names of its contributors may not be used to endorse or promote
    21.         products derived from this software without specific prior written
    22.         permission.
    23.  
    24.    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    25.    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    26.    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    27.    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
    28.    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    29.    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    30.    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
    31.    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
    32.    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
    33.    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
    34.    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    35.  
    36.  
    37.    Any feedback is very welcome.
    38.    http://www.math.keio.ac.jp/matumoto/emt.html
    39.    email: matumoto@math.keio.ac.jp
    40. */
    41.  
    42. #ifndef MTRAND_H
    43. #define MTRAND_H
    44.  
    45. #include "Rng.h"
    46. #include <ctime>
    47.  
    48. namespace Utilities
    49. {
    50.  
    51.     namespace Random
    52.     {
    53.         class MT_rand : public Rng
    54.         {
    55.             public:
    56.                 virtual void Seed( unsigned long seed );
    57.                 void Seed( const unsigned long*, size_t size );
    58.  
    59.  
    60.             protected:
    61.                 MT_rand()
    62.                 {
    63.                     if ( !seeded_ )
    64.                         Seed( static_cast<unsigned long>( std::time(NULL)));
    65.                     seeded_ = true;
    66.                 }
    67.                 MT_rand( unsigned long seed )
    68.                 {
    69.                     Seed( seed );
    70.                     seeded_ = true;
    71.                 }
    72.                 MT_rand( unsigned long* seed, size_t size )
    73.                 {
    74.                     Seed( seed, size );
    75.                     seeded_ = true;
    76.                 }
    77.                 virtual ~MT_rand();
    78.                 virtual unsigned long Rand()
    79.                 {
    80.                     if ( pos_ = N ) GenerateVector();
    81.                     unsigned long temp = state_vector_[pos_];
    82.                     ++pos_;
    83.                     temp ^= ( temp >> 11 );
    84.                     temp ^= ( temp << 7 ) & 0x9D2C5680UL;
    85.                     temp ^= ( temp << 15 ) & 0xEFC60000UL;
    86.                     return temp ^ ( temp >> 18 );
    87.                 }
    88.  
    89.  
    90.             private:
    91.                 MT_rand( const MT_rand& );
    92.                 const MT_rand& operator =( const MT_rand& );
    93.  
    94.                 static const unsigned int N = 624;
    95.                 static const unsigned int M = 397;
    96.                 static const unsigned long MAGIC = 0x9908B0DF;
    97.                 static const unsigned long UPPER_MASK = 0x80000000;
    98.                 static const unsigned long LOWER_MASK = 0x7FFFFFFF;
    99.                 static unsigned long state_vector_[N];
    100.                 static unsigned int pos_;
    101.                 static bool seeded_;
    102.                 void GenerateVector();
    103.                 unsigned long MixBits( unsigned long a, unsigned long b )
    104.                 {
    105.                     return (((( a & UPPER_MASK ) | ( b & LOWER_MASK )) >> 1 ) ^ ( ( b & 1UL ) ? MAGIC : 0UL ));
    106.                 }
    107.         };
    108.     } // close namespace Random
    109.  
    110. } // close namespace Utilities
    111.  
    112. #endif // inclusion guard

    MTRand.cpp
    C++ Code:
    1. // Implementation file for MTRand.h
    2. // Implementation of mersenne twister random number generator
    3. // Here follows algorithm authors copyright notice...
    4. /* Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
    5.    All rights reserved.                          
    6.  
    7.    Redistribution and use in source and binary forms, with or without
    8.    modification, are permitted provided that the following conditions
    9.    are met:
    10.  
    11.      1. Redistributions of source code must retain the above copyright
    12.         notice, this list of conditions and the following disclaimer.
    13.  
    14.      2. Redistributions in binary form must reproduce the above copyright
    15.         notice, this list of conditions and the following disclaimer in the
    16.         documentation and/or other materials provided with the distribution.
    17.  
    18.      3. The names of its contributors may not be used to endorse or promote
    19.         products derived from this software without specific prior written
    20.         permission.
    21.  
    22.    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    23.    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    24.    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    25.    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
    26.    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    27.    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    28.    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
    29.    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
    30.    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
    31.    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
    32.    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    33.  
    34.  
    35.    Any feedback is very welcome.
    36.    http://www.math.keio.ac.jp/matumoto/emt.html
    37.    email: matumoto@math.keio.ac.jp
    38. */
    39. // C++ wrapper by const volatile 2003
    40.  
    41. #include "MTRand.h"
    42.  
    43. // initialise the class statics.
    44. unsigned long Utilities::Random::MT_rand::state_vector_[N]={0UL};
    45. unsigned int Utilities::Random::MT_rand::pos_ = 0;
    46. bool Utilities::Random::MT_rand::seeded_ = false;
    47.  
    48. Utilities::Random::MT_rand::~MT_rand()
    49. { /* do nothing */ }
    50.  
    51. void Utilities::Random::MT_rand::Seed( unsigned long seed )
    52. {
    53.     state_vector_[0] = seed & 0xFFFFFFFFUL; // for machines wordsize > 32bits
    54.     for( int i = 0; i < N; ++i )
    55.     {
    56.         state_vector_[i] = 1812433253UL * ( state_vector_[i - 1] ^ ( state_vector_[i - 1] >> 30 )) + i;
    57.         state_vector_[i] &= 0xFFFFFFFFUL; // for machines wordsize > 32bits
    58.     }
    59.     pos_ = N; // this forces the state_vector to be recalculated next time a rand num is needed.
    60. }
    61.  
    62. void Utilities::Random::MT_rand::Seed( const unsigned long* parray, size_t size)
    63. {
    64.     Seed( 19650218UL );
    65.     int i = 1;
    66.     int j = 0;
    67.     for ( int k = (( N > size ) ? N : size ); k ; --k )
    68.     {
    69.         state_vector_[i] = ( state_vector_[i] ^ (( state_vector_[i - 1] ^ ( state_vector_[i - 1] >> 30 )) * 1664525UL )) + parray[j] + j;
    70.         state_vector_[i] &= 0xFFFFFFFFUL;
    71.         ++i;
    72.         ++j;
    73.         j %= size;
    74.         if ( i == N )
    75.         {
    76.             state_vector_[0] = state_vector_[N - 1];
    77.             i = 1;
    78.         }
    79.     }
    80.     for ( int k = N - 1; k ; --k )
    81.     {
    82.         state_vector_[i] = ( state_vector_[i] ^ (( state_vector_[i - 1] ^ ( state_vector_[i - 1] >> 30 )) * 1566083941UL )) - i;
    83.         state_vector_[i] &= 0xFFFFFFFFUL;
    84.         ++i;
    85.         if ( i == N )
    86.         {
    87.             state_vector_[0] = state_vector_[N - 1];
    88.             i = 1;
    89.         }
    90.     }
    91.     state_vector_[0] = UPPER_MASK;
    92.     pos_ = N; // forces state_vector recalculation on next random number
    93. }
    94.  
    95. void Utilities::Random::MT_rand::GenerateVector()
    96. {
    97.     for ( int i = 0; i < ( N - M ); ++i )
    98.     {
    99.         state_vector_[i] = state_vector_[i + M] ^ MixBits( state_vector_[i], state_vector_[i + 1] );
    100.     }
    101.     for ( int i = N - M; i < ( N - 1 ); ++i )
    102.     {
    103.         state_vector_[i] = state_vector_[i + M - N] ^ MixBits( state_vector_[i], state_vector_[i + 1] );
    104.     }
    105.     state_vector_[N - 1] = state_vector_[M - 1] ^ MixBits( state_vector_[N - 1], state_vector_[0] );
    106.     pos_ = 0;
    107. }

    randomMT.h
    C++ Code:
    1. // The concrete mersenne twister classes
    2. // floating point versions heavily based on code and theorem by
    3. // Isaku Wada 2002.
    4. // Freely available at http://www.math.keio.ac.jp
    5. // c++ wrapper by const volatile
    6.  
    7. #ifndef RANDOMMT_H
    8. #define RANDOMMT_H
    9.  
    10. #include "MTRand.h"
    11.  
    12. namespace Utilities
    13. {
    14.  
    15.     namespace Random
    16.     {
    17.         // rand unsigned long integer
    18.         class MT_rand_32ul : public MT_rand
    19.         {
    20.             public:
    21.                 MT_rand_32ul() : MT_rand()
    22.                 { /* do nothing */ }
    23.                 MT_rand_32ul( unsigned long seed ) : MT_rand( seed )
    24.                 { /* do nothing */ }
    25.                 MT_rand_32ul( unsigned long* seed, size_t size ) : MT_rand( seed, size )
    26.                 { /* do nothing */ }
    27.                 unsigned long operator ()()
    28.                 {
    29.                     return Rand();
    30.                 }
    31.             private:
    32.                 const MT_rand_32ul& operator =( const MT_rand_32ul& );
    33.                 MT_rand_32ul( const MT_rand_32ul& );                
    34.         };
    35.  
    36.         // rand double in half-open range [0,1) 0<=x<1
    37.         class MT_rand_d_closed0_open1 : public MT_rand
    38.         {
    39.             public:
    40.                 MT_rand_d_closed0_open1() : MT_rand()
    41.                 { /* do nothing */ }
    42.                 MT_rand_d_closed0_open1( unsigned long seed ) : MT_rand( seed )
    43.                 { /* do nothing */ }
    44.                 MT_rand_d_closed0_open1( unsigned long* seed, size_t size ) : MT_rand( seed, size )
    45.                 { /* do nothing */ }
    46.                 double operator ()()
    47.                 {
    48.                     return (( static_cast<double>(  Rand())) * ( 1.0 / 4294967296.0 ));
    49.                 }
    50.             private:
    51.                 const MT_rand_d_closed0_open1& operator =( const MT_rand_d_closed0_open1& );
    52.                 MT_rand_d_closed0_open1( const MT_rand_d_closed0_open1& );
    53.         };
    54.  
    55.         // rand double in closed range [0,1] 0<=x<=1
    56.         class MT_rand_d_closed0_closed1 : public MT_rand
    57.         {
    58.             public:
    59.                 MT_rand_d_closed0_closed1() : MT_rand()
    60.                 { /* do nothing */ }
    61.                 MT_rand_d_closed0_closed1( unsigned long seed ) : MT_rand( seed )
    62.                 { /* do nothing */ }
    63.                 MT_rand_d_closed0_closed1( unsigned long* seed, size_t size ) : MT_rand( seed, size )
    64.                 { /* do nothing */ }
    65.                 double operator ()()
    66.                 {
    67.                     return (( static_cast<double>(  Rand() )) * ( 1.0 / 4294967295.0 ));
    68.                 }
    69.             private:
    70.                 const MT_rand_d_closed0_closed1& operator =( const MT_rand_d_closed0_closed1& );
    71.                 MT_rand_d_open0_closed1( const MT_rand_d_closed0_closed1& );
    72.         };
    73.  
    74.         // rand doubles in range (0,1) 0<x<1
    75.         class MT_rand_d_open0_open1 : public MT_rand
    76.         {
    77.             public:
    78.                 MT_rand_d_open0_open1() : MT_rand()
    79.                 { /* do nothing */ }
    80.                 MT_rand_d_open0_open1( unsigned long seed ) : MT_rand( seed )
    81.                 { /* do nothing */ }
    82.                 MT_rand_d_open0_open1( unsigned long* seed, size_t size ) : MT_rand( seed, size )
    83.                 { /* do nothing */ }
    84.                 double operator ()()
    85.                 {
    86.                     return (( static_cast<double>(  Rand() ) + 0.5 ) * ( 1.0 / 4294967296.0 ));
    87.                 }
    88.             private:
    89.                 const MT_rand_d_open0_open1& operator =( const MT_rand_d_open0_open1& );
    90.                 MT_rand_d_open0_open1( const MT_rand_d_open0_open1& );
    91.         };
    92.  
    93.         // rand 53 bit resolution doubles in half open range [0,1) 0<=x<1
    94.         class MT_rand_d53 : public MT_rand
    95.         {
    96.             public:
    97.                 MT_rand_d53() : MT_rand()
    98.                 { /* do nothing */ }
    99.                 MT_rand_d53( unsigned long seed ) : MT_rand( seed )
    100.                 { /* do nothing */ }
    101.                 MT_rand_d53( unsigned long* seed, size_t size ) : MT_rand( seed, size )
    102.                 { /* do nothing */ }
    103.                 double operator ()()
    104.                 {
    105.                     return (( static_cast<double>( Rand() >> 5 ) * 67108864.0 + static_cast<double>( Rand() >> 6 )) * ( 1.0 / 9007199254740992.0 ));
    106.                 }
    107.             private:
    108.                 const MT_rand_d53& operator =( const MT_rand_d53& );
    109.                 MT_rand_d53( const MT_rand_d53& );
    110.         };
    111.  
    112.     } // close namespace Random
    113.  
    114. } // close namespace Utilities
    115.  
    116. #endif // inclusion guard

    Rng.h
    C++ Code:
    1. // Random Number Generator abstract base class
    2. // (c) const volatile 2003
    3. // Base class for several different random number generators.
    4. #ifndef RNG_H
    5. #define RNG_H
    6.  
    7. namespace Utilities
    8. {
    9.  
    10.     namespace Random
    11.     {
    12.         class Rng
    13.         {
    14.             public:
    15.                 virtual void Seed( unsigned long ) = 0;
    16.             protected:
    17.                 Rng() { /* do nothing */ }
    18.                 virtual ~Rng();
    19.                 virtual unsigned long Rand() = 0;
    20.             private:
    21.                 Rng( const Rng& );
    22.                 const Rng& operator =( const Rng& );
    23.         };
    24.  
    25.         Rng::~Rng() // not inlined as inline virtual makes no sense
    26.         { /* do nothing */ }
    27.  
    28.     } // close namespace Random
    29.  
    30. }// close namespace Utilities
    31.  
    32. #endif // inclusion guard

  7. #7
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    440

    Mình thêm vào code của RR hai phiên bản nữa cho operator():

    operator()(a,b) sinh số nguyên không dấu trong khoảng [a,b], thực hiện nhờ Rand(), hoặc operator()().

    operator()(L) sinh số nguyên không dấu trong khoảng [0,L), thực hiện nhờ operator()(a,b).


    class sửa đổi:
    C++ Code:
    1. class MT_rand_32ul : public MT_rand
    2. {
    3. public:
    4.     MT_rand_32ul() : MT_rand()
    5.     { /* do nothing */ }
    6.     MT_rand_32ul( unsigned long seed ) : MT_rand( seed )
    7.     { /* do nothing */ }
    8.     MT_rand_32ul( unsigned long* seed, size_t size ) : MT_rand( seed, size )
    9.     { /* do nothing */ }
    10.     unsigned long operator ()()
    11.     {
    12.         return Rand();
    13.     }
    14.  
    15.     unsigned long operator() (unsigned long a, unsigned long b);
    16.         // Returns a random unsigned long in [a,b], a<=b
    17.  
    18.     unsigned long operator() (unsigned long L)
    19.         // Returns a random unsigned long in [0,L), L>0
    20.     {
    21.         return operator()(0,L-1);
    22.     }
    23. }

    Thuật toán cho operator ()(a,b):
    C++ Code:
    1. unsigned long MT_rand_32ul::operator ()(unsigned long a, unsigned long b)
    2. // Returns a random unsigned long in [a,b], a<=b
    3. {
    4.     unsigned long L1 = b-a;
    5.     if (!L1) return a;
    6.     unsigned long M1,Q1;
    7.  
    8.     const unsigned long MU = ~(unsigned long)(0);
    9.     if (L1 != MU)
    10.     {
    11.         unsigned long L = L1+1;
    12.         Q1 = (MU-L1)/L;
    13.         M1 = Q1 * L + L1;
    14.     }
    15.     else
    16.     {
    17.         Q1 = 0;
    18.         M1 = MU;
    19.     }
    20.     unsigned long Q = Q1 + 1;
    21.  
    22.     unsigned long X;
    23.     do
    24.     {
    25.         X = Rand();
    26.     }
    27.     while (X > M1);
    28.     return X/Q + a;
    29. }

  8. #8
    Ngày gia nhập
    02 2008
    Bài viết
    1,009

    Đây là 1 số source tui sưu tầm được, thuật toán thì có đọc sơ qua, 1 số source vẫn chưa hiểu lắm, thôi thì post lên cho mọi người tham khảo và bàn luận để hiểu sâu hơn.
    Note : đa số source này tui đã format lại theo style của tui, vì đa phần source viết theo style K&R.
    PHP Code:
    #include <iostream>

    #define N 624
    #define M 397
    #define MATRIX_A 0x9908b0df   /* constant vector a */
    #define UPPER_MASK 0x80000000 /* most significant w-r bits */
    #define LOWER_MASK 0x7fffffff /* least significant r bits */

    /* Tempering parameters */
    #define TEMPERING_MASK_B 0x9d2c5680
    #define TEMPERING_MASK_C 0xefc60000
    #define TEMPERING_SHIFT_U(y)  (y >> 11)
    #define TEMPERING_SHIFT_S(y)  (y << 7)
    #define TEMPERING_SHIFT_T(y)  (y << 15)
    #define TEMPERING_SHIFT_L(y)  (y >> 18)

    static unsigned long mt] ; /* the array for the state vector  */
    static int mti 1/* mti==N+1 means mt[N] is not initialized */

    /* initializing the array with a NONZERO seed */
    void sgenrandunsigned long seed )
    {
        
    /* setting initial seeds to mt[N] using         */
        /* the generator Line 25 of Table 1 in          */
        /* [KNUTH 1981, The Art of Computer Programming */
        /*    Vol. 2 (2nd Ed.), pp102]                  */
        
    mt]= seed 0xffffffff;
        for( 
    mti 1mti N;  mti++ )
            
    mtmti ] = ( 69069 mtmti ] ) & 0xffffffff;
    }

    unsigned long genrandvoid )
    {
        
    unsigned long y;
        static 
    unsigned long mag01] = { 0x0MATRIX_A };
        
    /* mag01[x] = x * MATRIX_A  for x=0,1 */


        /* generate N words at one time */
        
    if( mti >= )
        {
            
    int kk;
            if( 
    mti == )   /* if sgenrand() has not been called, */
                
    sgenrand4357 ); /* a default initial seed is used   */

            
    for( kk 0kk Mkk++ )
            {
                
    = ( mtkk ] & UPPER_MASK ) | ( mtkk ] & LOWER_MASK );
                
    mtkk ] = mtkk ] ^ ( >> ) ^ mag010x1 ];
            }

            for( ; 
    kk 1kk++ )
            {
                
    = ( mtkk ] & UPPER_MASK) | ( mtkk ] & LOWER_MASK );
                
    mtkk ] = mtkk + ( ) ] ^ ( >> ) ^ mag010x1 ];
            }

            
    = ( mt] & UPPER_MASK ) | ( mt] & LOWER_MASK );
            
    mt] = mt] ^ ( >> ) ^ mag010x1 ];

            
    mti 0;
        }

        
    mt[mti++];
        
    ^= TEMPERING_SHIFT_U(y);
        
    ^= TEMPERING_SHIFT_S(y) & TEMPERING_MASK_B;
        
    ^= TEMPERING_SHIFT_T(y) & TEMPERING_MASK_C;
        
    ^= TEMPERING_SHIFT_L(y);

        return 
    y;
    }
    int main()
    {
        
    // ham gieo gia tri ngau nhien ah???
        
    sgenrand(100);
        
    //ham tra ve gia tri ngau nhien ah???
        
    cout<<genrand();

    anh không nói đến thuật toán con này thì làm sao mà bọn em biết được nó là cái gì trờixin anh cho biết tên

  9. #9
    Ngày gia nhập
    02 2008
    Bài viết
    88

    Theo mình thì ko cần phải viết một hàm Ran khác làm gì, vì két quả cuối cùng cũng là một con số thập phân mà thôi.
    Thay vào đó nên kết hợp giữa hàm ran và mảng thì sẽ tạo ra các số ngẫu nhiên rất ngấu nhiên.
    Mình từ Caulacbovb qua)
    Giã từ VB6 đến với VB.Net, C# và Java.

  10. #10
    Ngày gia nhập
    02 2008
    Bài viết
    1,009

    Theo mình thì ko cần phải viết một hàm Ran khác làm gì, vì két quả cuối cùng cũng là một con số thập phân mà thôi.
    Thay vào đó nên kết hợp giữa hàm ran và mảng thì sẽ tạo ra các số ngẫu nhiên rất ngấu nhiên.
    chủ yếu người ta muốn biết cái thuật toán tìm số ngẫu nhiên là gì để mà có thể đoán mò được các số ngẫu nhiên không ,không biết nếu áp dụng vào lô tô thì thế nào nhỉ

Các đề tài tương tự

  1. Tạo biến ngẫu nhiên kiểu float sử dụng hàm rand() trong C/C++ như thế nào?
    Gửi bởi 50902116 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 24
    Bài viết cuối: 27-02-2014, 04:35 PM
  2. thuật toán sắp xếp ngẫu nhiên trong lập trình C#
    Gửi bởi b0yt4l3nt9z trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 6
    Bài viết cuối: 05-04-2011, 02:49 PM
  3. Code C++ Các Thuật Toán Tạo Số Ngẫu Nhiên
    Gửi bởi thangnv trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 16-03-2011, 11:50 PM
  4. Nhập ngẫu nhiên 1 ma trận bằng hàm rand()
    Gửi bởi kienchochethahaha trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 19-05-2010, 05:43 PM
  5. Tạo ngẫu nhiên trên C++ (hàm rand())
    Gửi bởi anhhaibi trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 22-05-2009, 10:31 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn