随机算法-简单来一发

（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦

目录

随机数(尽量避免用rand())

这个放在前面，不仅rand()容易被卡，random_shuffle也同样容易被卡。
因为RAND_MAX只有32767，当你的范围远超32767时，问题就来了。
参考：here
解决方案：
xjb改你rand()，当然还有mt19937和mt19937_64这种奇技淫巧。
注意：茅台创建很慢。

#include <random>
srand((unsigned)time(0));
LL RAND(){
    LL ret = rand()%10007, a = rand()%1000;
    return ret*a%n;
}
LL RAND(){
    LL ret = 0;
    while(ret < n) ret = ret * RAND_MAX + rand();
    return ret % n;
}

mt19937
mt19937_64
这是两个预定义类（类型），定义的变量可以用重载好的 () 运算符获取随机数，前者生成 [0, 2^32-1]，后者生成 [0, 2^64-1]
注意用的时候别直接转成有符号数了
mt19937 cai_dui_niu_bi;
mt19937_64 cai_dui_niu_bi_huai_le;
cout << cai_dui_niu_bi() << endl;
cout << cai_dui_niu_bi_huai_le() << endl;

mt19937 lh(std::clock());
mt19937 lh(time(NULL));

随机乱序

CF Round492 Div2 的E的可以用这个函数水过去。要不是fst我也知道可以这样玩。
后来知道了，原来random_shuffle也能被卡，原理同rand()。
可以用和mt19937相关的shuffle

#include <random>
random_shuffle(cw,cw+n);//cw数组已被随机乱序
for(int i=0;i<n;++i)cout<<cw[i]<<" "; cout<<"n";

for(int i = 0; i < n; ++i) arr[i] = i + 1;
std::mt19937_64 generator(std::clock());
std::shuffle(arr, arr + n, generator);

随机生成数组

unsigned int x,y,z;
inline unsigned int tang(){
  unsigned int t;
  x ^= x<<16;
  x ^= x>>5;
  x ^= x<<1;
  t=x;
  x=y;
  y=z;
  z=t^x^y;
  return z;
}

nth_element函数

API文档
例题：hdu6040

nth_element(cw,cw+len,cw+n);
//下标为len位置的值是这个数组的第len小。
//小于它的都在其前面，大于它的都在其后面，但不保证有序！

// nth_element example
#include <iostream>     // std::cout
#include <algorithm>    // std::nth_element, std::random_shuffle
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
  std::vector<int> myvector;

  // set some values:
  for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

  std::random_shuffle (myvector.begin(), myvector.end());

  // using default comparison (operator <):
  std::nth_element (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  std::nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << 'n';

  return 0;
}

随机选取k个数

bool getRand(const vector vecData, int m, vector& vecRand){
  int nSize = vecData.size();
  if(nSize  < m || m < 0)return false;
  vecRand.clear();
  vecRand.reserve(m);
  for(int i = 0, isize = nSize; i < isize ; ++i){
    double fRand = frand();
    if(fRand <= m*1.0/nSize){
      vecRand.push_back(vecData[i]);
      --m;
    }
    --nSize;
  }
  return true;
}

CF交互题

CF1020D
CF1088D
CF1100D
CF1114E
CF1117E：26进制加密解密

 最近在看王晓东的《计算机算法设计与分析(第3版) 》，感觉讲的挺不错的。这里先推荐下。

 接下来的几章(包括本章)，我准备以连载的方式讲出来，主要用到的资料是上面推荐的那本书以及《算法导论》和网上的资源，内容是概率分析与随机算法。文章内大部分内容出自书中，我仅以汇总形式以及个人理解加以补充。如有纰漏，欢迎指出。

 概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类:数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。

 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。

产生随机数最常用的方法是线性同余法。由线性同余法产生的随机序列a1,a2,…,an满足
1.a0=d
2.an=(b*an-1+c)mod m （n=1,2…….）
其中,b>0, c>=0, d>=m。d称为该随机序列的种子。

一般情况下，取gcd(m, b)=1，因此可取b为一素数。
这是一个随机数类

const unsigned long maxshort = 65535L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
 
class RandomNumber{
private:
    // 当前种子
    unsigned long randSeed;
public:
    // 构造函数,默认值0表示由系统自动产生种子
    RandomNumber(unsigned long s = 0);
    // 产生0 ~ n-1之间的随机整数
    unsigned short Random(unsigned long n);
    // 产生[0, 1) 之间的随机实数
    double fRandom();
};
 
// 产生种子
RandomNumber::RandomNumber(unsigned long s){
    if(s == 0)
        randSeed = time(0);    //用系统时间产生种子
    else
        randSeed = s;
}
// 产生0 ~ n-1 之间的随机整数
unsigned short RandomNumber::Random(unsigned long n){
    randSeed = multiplier * randSeed + adder;
    return (unsigned short)((randSeed >> 16) % n);
}
// 产生[0, 1)之间的随机实数
double RandomNumber::fRandom(){
    return Random(maxshort) / double(maxshort);
}

利用这个随机数类，写一个程序，模拟抛硬币的实验。

抛10次硬币构成一个事件，每次事件记录得到正面的个数。反复模拟这个事件50,000次，然后对这50,000L次进行输出频率图，比较每次事件得到正面次数的比例。

以下是总的代码：
头文件 RandomNumber.h：

// RandomNumber.h
const unsigned long maxshort = 65535L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;

#ifndef RANDOMNUMBER_H
#define RANDOMNUMBER_H

class RandomNumber{
private:
    // 当前种子
    unsigned long randSeed;
public:
    // 构造函数,默认值0表示由系统自动产生种子
    RandomNumber(unsigned long s = 0);
    // 产生0 ~ n-1之间的随机整数
    unsigned short Random(unsigned long n);
    // 产生[0, 1) 之间的随机实数
    double fRandom();
};

#endif

类实现文件RandomNumber.cpp :

// RandomNumber.cpp
#include "RandomNumber.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
// 产生种子
RandomNumber::RandomNumber(unsigned long s){
    if(s == 0)
        randSeed = time(0);    //用系统时间产生种子
    else
        randSeed = s;
}
 
// 产生0 ~ n-1 之间的随机整数
unsigned short RandomNumber::Random(unsigned long n){
    randSeed = multiplier * randSeed + adder;
    return (unsigned short)((randSeed >> 16) % n);
}
 
// 产生[0, 1)之间的随机实数
double RandomNumber::fRandom(){
    return Random(maxshort) / double(maxshort);
}

主文件Main :

 // 主文件main
/*
* Author: Tanky woo
* Blog:   www.WuTianQi.com
* Date:   2010.12.7
* 代码来至王晓东《计算机算法设计与分析》
*/
#include "RandomNumber.h"
#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
int TossCoins(int numberCoins){
    // 随机抛硬币
    static RandomNumber coinToss;
    int i, tosses = 0;
    for(i = 0; i < numberCoins; ++i)
        tosses += coinToss.Random(2);
    return tosses;
}
int main(){
    // 模拟随机抛硬币事件
    const int NCOINS = 10;
    const long NTOSSES = 50000L;
    // heads[i]得到的i次正面的次数
    long i, heads[NCOINS+1];
    int j, position;
    // 初始化数组heads
    for(j = 0; j < NCOINS+1; ++j)
        heads[j] = 0;
    // 重复50,000次模拟事件
    for(i = 0; i < NTOSSES; ++i)
        heads[TossCoins(NCOINS)] ++;
    // 输出频率图
    for(i = 0; i <= NCOINS; ++i){
        position = int (float(heads[i]) / NTOSSES*72);
        cout << setw(6) << i << " ";
        for(j = 0; j<position-1; ++j)
            cout << " ";
        cout << "*" << endl;
    }
    return 0;
}  

此部分内容转载：here

最后

以上就是长情飞机为你收集整理的随机算法-简单来一发的全部内容，希望文章能够帮你解决随机算法-简单来一发所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。