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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121 | #include <iostream>
#include <cstdlib>
#include <ctime>
#include <windows.h>
using namespace std;
const int N = 2000000; //定义数组的最大长度
int a[N];
bool majorityMC_once(int a[], int len, int *result) { //对长度为len的数组a[]进行一次蒙特卡洛寻找多数
int rnd = rand() % len; //生成[0, len-1)的一个随机下标
int x = a[rnd];
int count = 0; //记录 x 在数组a[]中出现的次数
for (int i = 0; i < len; i++) {
if (a[i] == x) {
count++;
}
}
if (count > (len / 2)) { //若 x 出现次数超过数组长度的一半，则一次蒙特卡洛找到多数，返回true
*result = x; //将找到的多数的值传给result
return true;
}
else { //否则，一次蒙特卡洛未找到多数，返回false
return false;
}
}
bool majorityMC_k_times(int a[], int len, int *result, int k) { //k次蒙特卡洛
for (int i = 1; i <= k; i++) {
if(majorityMC_once(a, len, result)) { //只要有一次蒙特卡洛找到多数，则返回true
return true;
}
}
return false; //k次蒙特卡洛均未找到多数，则返回false
}
bool majorityDC(int a[], int start, int end, int *result) { //分治法求解多数问题，数组下标区间为[start, end]
if (start == end) {
*result = a[end];
return true;
}
else {
int m1, m2;
majorityDC(a, start, (start + end) / 2, &m1); //m1为前半区间[start, (start + end) / 2]的多数
majorityDC(a, (start + end) / 2 + 1, end, &m2); //m2为后半区间[(start + end) / 2 + 1, end]的多数
int count1 = 0, count2 = 0;
for (int i = start; i <= end; i++) {
if (a[i] == m1) { //count1记录m1在数组a[]中出现的次数
count1++;
}
if (a[i] == m2) { //count2记录m2在数组a[]中出现的次数
count2++;
}
}
if (count1 > ((end - start + 1) / 2)) { //m1在数组a[]中出现的次数大于数组长度的一半，则m1为多数
*result = m1;
return true;
}
else if (count2 > ((end - start + 1) / 2)) { //m2在数组a[]中出现的次数大于数组长度的一半，则m2为多数
*result = m2;
return true;
}
else {
return false; //m1, m2均不是多数，则数组a[]的多数不存在
}
}
}
int main() {
srand(time(NULL)); //设置时间函数time(NULL)为随机数种子
char s[100];
cout << "请输入测试数据文件路径：" << endl;
cin >> s;
FILE *fp;
fp = fopen(s, "r");
if (fp == NULL) {
cout << "Can not open the file!" << endl;
exit(0);
}
int i = 0;
while (fscanf(fp, "%d\n", &a[i]) != EOF) { //读取文件中的数据到数组a[]中
i++;
}
fclose(fp);
cout << "********************** Monte Carlo *********************" << endl;
int k;
cout << "请输入 Monte Carlo 重复的次数： ";
cin >> k;
LARGE_INTEGER nFreq;
LARGE_INTEGER nBeginTime;
LARGE_INTEGER nEndTime;
QueryPerformanceFrequency(&nFreq);
QueryPerformanceCounter(&nBeginTime); //Monte Carlo计时开始
int resultMC;
if (majorityMC_k_times(a, i, &resultMC, k)) {
cout << resultMC << " is the majority" << endl;
}
else {
cout << "Can not find the majority!" << endl;
}
QueryPerformanceCounter(&nEndTime); //Monte Carlo计时结束
double time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / nFreq.QuadPart * 1000;
cout << "Running time: " << time << "ms" << endl;
cout << endl;
cout << "****************** Divide and Conquer ******************" << endl;
QueryPerformanceFrequency(&nFreq);
QueryPerformanceCounter(&nBeginTime); //分治法计时开始
int resultDC;
if (majorityDC(a, 0, i - 1, &resultDC)) {
cout << resultDC << " is the majority" << endl;
}
else {
cout << "Can not find the majority!" << endl;
}
QueryPerformanceCounter(&nEndTime); //分治法计时结束
time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / nFreq.QuadPart * 1000;
cout << "Running time: " << time << "ms" << endl;
return 0;
}
|