模拟算法(Simulation algorithm)
模拟算法，就是指程序完全按照题目描述的方式运行，从而获得相应的结果。它的特点就是不需要去想怎么样去解决问题，而是有现成的解决方案，只要按照方案一步步去实现。
例一：求一组数的平均数(mean)，中位数(median)、众数(mode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | /**************************************************************** * Description: mean median mode * Author: Alex Li * Date: 2024-06-10 17:43:49 * LastEditTime: 2024-06-10 20:08:18 ****************************************************************/ #include <iostream> #include <algorithm> using namespace std; //找平均数 float mean(float arr[], int n){ float sum = 0; for(int i = 0;i < n; i++) sum += arr[i]; return sum/n; } //找中位数 float median(float arr[], int n){ //对数组排序 sort(arr, arr + n); if(n % 2 == 0) return (arr[n/2 - 1] + arr[n/2])/2; return arr[n/2]; } //找众数 float mode( float arr[], int n){ // 排序 sort(arr, arr + n); //找最大的序列 int max_count = 1, res = arr[0], count = 1; for (int i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) count++; else { if (count > max_count) { max_count = count; res = arr[i - 1]; } count = 1; } } // 如果最后一个是众数 if (count > max_count){ max_count = count; res = arr[n - 1]; } return res; } int main(){ int n; float arr[50]; cout<<"Enter the size of array: "; cin>>n; //input in the array cout<<"Enter the elements of array: "; for(int i = 0; i < n; i++) cin>>arr[i]; //print mean, median and mode of ungrouped data in array cout<<"\nMean = "<<mean(arr, n); cout<<"\nMedian = "<<median(arr, n); cout<<"\nMode = "<<mode(arr, n); return 0; } |
例二、如果众数不唯一
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | //计算众数，输出众数及其个数 #include <iostream> using namespace std; int a[100],b[100][100]={0}; int main(){ int n,q=0,zero=0,max_number=0; bool m=true; cin>>n; for (int i = 0; i <n ; i++){ cin>>a[i]; } for (int i = 0; i < n; i++){ m=true; for (int j = 0; j <= q; j++){ if(b[j][0]==a[i]){ b[j][1]++; m=false; } } if(m){ b[q][0]=a[i]; b[q][1]=1; q++; } } for (int i = 0; i < n; i++) { if(a[i]==0)zero++; } for (int i = 0; i < n; i++){ if(max_number<b[i][1])max_number=b[i][1]; } if(max_number>zero){ cout<<"max number is: "<<max_number<<endl; cout<<"mode index is: "; for (int i = 0; i < q; i++){ if(b[i][1]==max_number)cout<<b[i][0]<<' '; } } else cout<<"max number is: "<<zero<<"mode index is : "<<"zero"; } |
NOIP2010普级组接水问题 (P1190) P1460
题目描述
学校里有一个水房，水房里一共装有 m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1。
现在有 n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 1 到 n 编号，ii 号同学的接水量为 wi。接水开始时，1到 m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学 jj完成其接水量要求 wj后，下一名排队等候接水的同学 k马上接替 j同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j同学第 x秒结束时完成接水，则 k 同学第 x+1 秒立刻开始接水。若当前接水人数 n′不足 m，则只有 n′个龙头供水，其它 m−n′个龙头关闭。
现在给出 n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
输入格式
第一行两个整数 n 和 m，用一个空格隔开，分别表示接水人数和龙头个数。
第二行 n 个整数 w1,w2,…,wn，每两个整数之间用一个空格隔开，wi表示 i号同学的接水量。
输出格式
一个整数，表示接水所需的总时间。
输入输出样例
输入 #1
5 3
4 4 1 2 1
输出 #1
4
输入 #2
8 4
23 71 87 32 70 93 80 76
输出 #2
163
说明/提示
【输入输出样例 #1 说明】
第 1秒，3 人接水。第 1 秒结束时，1,2,3 号同学每人的已接水量为 1,3 号同学接完水，4 号同学接替 3 号同学开始接水。
第 2 秒，3 人接水。第 2 秒结束时，1,2 号同学每人的已接水量为 2,4 号同学的已接水量为 1。
第 3 秒，3 人接水。第 3 秒结束时，1,2 号同学每人的已接水量为 3, 4 号同学的已接水量为 2。4 号同学接完水，5 号同学接替 4 号同学开始接水。
第 4 秒，3 人接水。第 4 秒结束时，1,2 号同学每人的已接水量为 4, 5 号同学的已接水量为 1。1,2,5 号同学接完水，即所有人完成接水的总接水时间为 4 秒。
【数据范围】
1≤n≤104，1≤m≤100，m≤n；
1≤wi≤100。
P1996 约瑟夫问题