模拟算法
一种通过模拟实际问题的步骤或过程来解决问题的算法。它通常按照问题的描述或规则，一步步地重现问题的场景，最终得到解决方案。
约瑟夫环问题
问题描述：N个人围成一圈，从第K个人开始报数，数到M的人出列，直到所有人出列。
代码示例:
#include <stdio.h>
#include <stdlib.h>/*** 约瑟夫环问题模拟* @param n 总人数* @param k 起始位置* @param m 报数间隔*/
void josephus(int n, int k, int m) {// 创建循环链表int *circle = (int *)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {circle[i] = i + 1; // 编号1-n}int current = k - 1; // 当前报数的人（转换为0-based索引）int remaining = n; // 剩余人数printf("约瑟夫环（%d人，从%d开始，数到%d出列）:\n", n, k, m);while (remaining > 0) {// 找到要出列的人int count = 0;while (count < m) {if (circle[current] != 0) {count++;}if (count < m) {current = (current + 1) % n;}}// 出列printf(" %d号出列\n", circle[current]);circle[current] = 0;remaining--;// 找到下一个开始报数的人while (circle[current] == 0 && remaining > 0) {current = (current + 1) % n;}}free(circle);
}int main() {josephus(5, 1, 3); // 5个人，从1开始，数到3出列return 0;
}//流程
约瑟夫环（5人，从1开始，数到3出列）:3号出列1号出列5号出列2号出列4号出列
模拟洗牌算法
#include <stdio.h>
#include <stdlib.h>
#include <time.h>/*** 模拟洗牌（Fisher-Yates算法）* @param cards 牌组数组* @param n 牌的数量*/
void shuffle(int cards[], int n) {srand(time(NULL)); // 设置随机种子printf("洗牌过程：\n");for (int i = n - 1; i > 0; i--) {int j = rand() % (i + 1); // 生成随机索引// 交换当前牌和随机位置的牌int temp = cards[i];cards[i] = cards[j];cards[j] = temp;// 打印交换过程printf(" 交换位置 %d 和 %d: ", i, j);for (int k = 0; k < n; k++) {printf("%d ", cards[k]);}printf("\n");}
}int main() {int cards[] = {1, 2, 3, 4, 5};int n = sizeof(cards) / sizeof(cards[0]);printf("初始牌序：");for (int i = 0; i < n; i++) {printf("%d ", cards[i]);}printf("\n");shuffle(cards, n);printf("\n最终牌序：");for (int i = 0; i < n; i++) {printf("%d ", cards[i]);}return 0;
}//流程
初始牌序：1 2 3 4 5
洗牌过程：交换位置 4 和 2: 1 2 5 4 3 交换位置 3 和 1: 1 4 5 2 3 交换位置 2 和 2: 1 4 5 2 3 交换位置 1 和 0: 4 1 5 2 3 最终牌序：4 1 5 2 3 银行排队系统模拟
#include <stdio.h>
#include <stdlib.h>
#include <time.h>// 客户结构体
typedef struct {int arrival_time; // 到达时间int service_time; // 服务时间
} Customer;/*** 模拟银行单窗口排队* @param customers 客户数组* @param n 客户数量*/
void bankQueueSimulation(Customer customers[], int n) {int current_time = 0;int total_wait = 0;printf("时间 | 客户到达 | 服务开始 | 服务结束 | 等待时间\n");printf("--------------------------------------------\n");for (int i = 0; i < n; i++) {// 客户到达时间int arrival = customers[i].arrival_time;// 客户开始服务时间int start = (current_time > arrival) ? current_time : arrival;// 客户等待时间int wait = start - arrival;// 服务结束时间int end = start + customers[i].service_time;total_wait += wait;current_time = end;printf("%4d | %8d | %8d | %8d | %8d\n", i+1, arrival, start, end, wait);}printf("\n平均等待时间: %.2f\n", (float)total_wait / n);
}int main() {srand(time(NULL));// 生成随机客户数据Customer customers[5];for (int i = 0; i < 5; i++) {customers[i].arrival_time = i * 3 + rand() % 3; // 随机到达时间customers[i].service_time = 5 + rand() % 6; // 随机服务时间5-10分钟}// 打印客户数据printf("客户数据：\n");printf("客户编号 | 到达时间 | 服务时间\n");for (int i = 0; i < 5; i++) {printf("%8d | %8d | %8d\n", i+1, customers[i].arrival_time, customers[i].service_time);}printf("\n");// 开始模拟bankQueueSimulation(customers, 5);return 0;
}//流程
客户数据：
客户编号 | 到达时间 | 服务时间1 | 1 | 82 | 4 | 73 | 7 | 94 | 10 | 65 | 14 | 5时间 | 客户到达 | 服务开始 | 服务结束 | 等待时间
--------------------------------------------1 | 1 | 1 | 9 | 02 | 4 | 9 | 16 | 53 | 7 | 16 | 25 | 94 | 10 | 25 | 31 | 155 | 14 | 31 | 36 | 17平均等待时间: 9.20电梯运行模拟
#include <stdio.h>
#include <stdlib.h>#define FLOORS 10/*** 模拟电梯运行* @param requests 各楼层请求数组（1表示有请求）* @param n 请求数量* @param start_floor 电梯起始楼层*/
void elevatorSimulation(int requests[], int n, int start_floor) {int current = start_floor;int direction = 1; // 1=上行，-1=下行printf("电梯从 %d 楼开始运行\n", current);printf("楼层 | 行动\n");printf("-----------\n");while (1) {// 检查当前楼层是否有请求if (requests[current] == 1) {printf("%3d | 停靠\n", current);requests[current] = 0; // 清除请求n--;if (n == 0) break;} else {printf("%3d | 经过\n", current);}// 决定是否改变方向if (current == FLOORS - 1) direction = -1;if (current == 0) direction = 1;current += direction;}printf("所有请求已完成\n");
}int main() {int requests[FLOORS] = {0}; // 初始化所有楼层无请求// 随机设置3个楼层请求requests[3] = 1;requests[7] = 1;requests[9] = 1;int n = 3;printf("楼层请求：");for (int i = 0; i < FLOORS; i++) {if (requests[i]) printf("%d ", i);}printf("\n\n");elevatorSimulation(requests, n, 0); // 从0层开始return 0;
}//流程
楼层请求：3 7 9 电梯从 0 楼开始运行
楼层 | 行动
-----------0 | 经过1 | 经过2 | 经过3 | 停靠4 | 经过5 | 经过6 | 经过7 | 停靠8 | 经过9 | 停靠
所有请求已完成模拟算法特点
-
直观性：直接模拟实际过程，易于理解和实现
-
准确性：只要模拟规则正确，结果通常准确
-
灵活性：可以处理复杂规则和异常情况
-
效率问题：对于大规模问题可能效率不高
优化技巧
-
事件驱动：只处理关键事件点而非每个时间步
-
空间分区：将模拟空间划分为网格或区域
-
简化模型：在不影响结果的情况下简化物理规则
-
并行计算：对独立部分进行并行模拟
适用场景:
| 场景类型 | 示例 |
|---|---|
| 物理过程模拟 | 弹道计算、流体模拟 |
| 系统行为模拟 | 电梯调度、交通灯控制 |
| 游戏逻辑 | 棋类游戏、角色行为 |
| 排队系统 | 银行窗口、呼叫中心 |
