模拟法(simulation method):自然界和日常生活中的有些问题难以找到公式或规律来解决,若用计算机很难建立起枚举、贪心等算法,甚至没法建立数学模型,这时可以按照步骤,模拟人的解决行为,一步一步往下走就能找到答案。

例子: 鸡兔同笼问题

问题】笼子里有若干只鸡和免子,鸡有两只脚,兔子有四只脚,没有例外情况。已知笼子里脚的数量,问笼子里至多有多少只动物?至少有多少只动物?

想法】对于同样数目的动物,鸡脚的总数肯定比免子脚的总数要少,因此在计算笼子里至多有多少只动物时,应该把脚都算作鸡脚,在计算笼子里至少有多少只动物时,应该尽可能把脚都算作兔子脚。

算法】设函数 Feets 实现鸡兔同笼问题,算法分析如下。

输入:脚的数量 n
输出:至多的动物数 maxNum,至少的动物数 minNum

  1. 如果 n 是奇数,则没有满足要求的解,maxNum=0, minNum=0:
  2. 如果 n 是偶数且能被 4 整除,则maxNum=n/2, minNum=n/4;
  3. 如果 n 是偶数但不能被 4 整除,则maxNum=n/2, minNum=(n一2)/4+1;
  4. 输出 maxNum 和 minNum;

【算法分析】算法 Feets 只是进行了简单的判断和赋值,时间复杂度是O(1)。
【算法实现】设形参 maxNum 和 minNum 以传引用方式接收求得的结果,程序如下。

1
2
3
4
5
6
7
8
9
10
void Feets(int n, int &maxNum, int minNum){
if(n % 2 != 0) {
maxNum =0; minNum = 0;
}else if(n % 4 ==0){
maxNum = n/2; minNum = n/4;
}else{
maxNum = n/2; minNum = (n-2)/4+1;
}
}

数学问题中的模拟法

  1. 约瑟夫环问题

    约瑟夫环问题在不同平台被的描述不一样,例如在力扣上剑指offer62的描述:圆圈中最后剩下的数字

    问题描述:0,1,···,n-1 这 n 个数字排成一个圆圈,从数字 0 开始,每次从这个圆圈里删除第 m 个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。

    例如,0、1、2、3、4 这 5 个数字组成一个圆圈,从数字 0 开始每次删除第 3 个数字,则删除的前 4 个数字依次是 2、0、4、1,因此最后剩下的数字是 3。

    示例

    1
    2
    3
    4
    5
    6
    输入: n = 5, m = 3
    输出: 3
    示例 2:

    输入: n = 10, m = 17
    输出: 2

    想法】设函数 Joseph 求解约瑟夫环问题,用数组 r[n] 存储 n 个人是否出列,下标表示人的编号,从 1 开始数到密码 m 则将其出列。如果编号 i 的人出列则将数组 r[i] 置为1,用求模运算%实现下标在数组内循环增1。算法如下。

    输人:参与游戏的人数 n,密码 m
    输出:最后一个出列的编号

    1. 初始化数组r[n]={o};
    2. 计数器count=0,下标i=一1:出列人数num=0:
    3. 重复下述操作直到数组 r[n] 仅剩一个人:
    • 当count<m时重复下述操作:
      • i=(i+1)%n:
      • 如果 r[i] 未出列,则计数器count十十,
    • 令r[i]=1:num++,
    1. 查找并返回仅剩的编号;

    分析】外循环执行 n-1 次,内循环执行 m 次,时间复杂度为 O(nm)O(n*m)

    实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int Joseph(int r[], int n, int m){
    int count, i = -1, num = 0;
    while(num < n-1>){
    count = 0;
    while(count < m>){
    i = (i+1) % n;
    if(r[i] != 1) count++;
    }
    r[i] = 1; num++;
    }
    for(i = 0; i < n; i++)
    if(r[i] == 0;) return i+1;
    }
  2. 埃拉托色尼筛法

    埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数 n 以内的全部素数,必须把不大于 n\sqrt{n} 的所有素数的倍数剔除,剩下的就是素数。

    【想法】假设有一个筛子存放整数 1~n,依次将2,3,5,…的倍数筛去(标记),最后没有打上标记的数都是素数。设数组A[n]表示筛子,元素值全部初始化为0,依次将下标是2,3,5,…倍数的元素值置1进行标记处理,最后所有元素值为0对应的下标都是素数。

    实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void EratoSieve(int A[ ], int n) {
    int i, j;
    for(i = 2; i<= n; i++) {
    if(A[i] != 0) continue;
    else {
    for(j = 2; i * j <= n; j++){
    A[i * j] = 1;
    }
    }
    }
    }

排序问题中的模拟法

计数排序:计数排序①(count sort),的基本思想是对每一个记录x,确定小于x的记录个数,然后直接将x放在应该的位置。例如,小于x的记录个数是10,则x就位于第11个位置。

算法】设函数 CountSort 实现计数排序,数组 num[k+l]num[k+l] 存储每个记录出现的次数以及小于等于值为 i 的记录个数,算法如下。

输人:待排序记录序列 A[n]A[n],记录的取值区间 kk
输出:排序数组 B[n]B[n]

  1. 统计值为i的记录个数存人 num[i]num[i]
  2. 统计小于等于i的记录个数存人 num[i]num[i],
  3. 反向填充目标数组,将 A[i]A[i] 放在 B[num[A[i]]]B[--num[A[i]]] 中,
  4. 输出数组 B[n]B[n]

分析】计数排序是一种以空间换时间的排序算法,并且只适用于对一定范围内的整数进行排序,时间复杂度为 O(n+k)O(n+k),其中 kk 为序列中整数的范围。
实现】计数排序的关键在于确定待排序记录 A[i]A[i] 在目标数组 B[n]B[n] 中的位置,由于数组元素 num[i]num[i] 存储的是 A[n]A[n] 中小于等于 i 的记录个数,所以填充数组 B[n]B[n] 时要反向读取 A[n]A[n]

1
2
3
4
5
6
7
8
9
void CountSort(int A[ ], int n, int k, int B[ ]){
int i, num[k+1] = {0};
for(i = 0; i < n; i++)
num[A[i]]++;
for(i = 1; i <= k; i++)
num[i] = num[i] + num[i - 1];
for(i = n-1; i >= 0; i--)
B[--num[A[i]]] = A[i];
}

参考