在此处输入标题

发表于 | 分类于

在此输入正文

EX1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import random


def darts(n):
    k = 0
    for i in range(n):
        x = random.uniform(0, 1)
        y = x
        if x * x + y * y <= 1:
            k += 1
    return 4 * k / n


i = 1
while i < 10000000000:
    print(i, darts(i))
    i = i * 10

EX2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random
import math


def HitorMiss(f, n):
    k = 0
    for i in range(n):
        x = random.uniform(0, 1)
        y = random.uniform(0, 1)
        if y <= f(x):
            k += 1
    return k / n


def fun(x):
    return 4*math.sqrt(1 - x * x)


i = 1
f = fun
while i < 10000000000:
    print(i, HitorMiss(f, i))
    i = i * 10

EX3

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
import random
import math


def Integral(f, n, a, b, c, d):
    k_pos = 0
    k_neg = 0
    maxv = max((d - c), (d - 0))
    s = maxv * (b - a)
    for i in range(n):
        x = random.uniform(0, 1) * (b - a) + a
        y = random.uniform(0, 1) * (d - c) + min(c, 0)
        if f(x) >= 0:
            if 0 <= y <= f(x):
                k_pos += 1
        else:
            if 0 >= y >= f(x):
                k_neg += 1
    return ((k_pos - k_neg) / n) * s


def fun(x):
    # y=x+4
    # return x * (x - 2)
    return x - 1


i = 1
f = fun
while i < 100000000:
    print(i, Integral(f, i, 0, 2, -1, 1))
    i = i * 10

EX5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random
import math


def setCount(x):
    k = 1
    s = set()
    a = random.randint(1, x)
    while a not in s:
        k += 1
        s.add(a)
        a = random.randint(1, x)
    return 2 * k * k / math.pi


roundNum = 10000
k = 1000
for j in range(5):
    total = 0
    for i in range(roundNum):
        total += setCount(k)
    print(k, total / roundNum,"error rate:",math.fabs(int(total / roundNum)-k)/k)
    k *= 10

EX7:

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
/*写一Sherwood算法C，与算法A, B, D比较，给出实验结果*/
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
int n=7,head=3;
int val[7]={2,3,13,1,5,21,8};
int ptr[7]={1,4,5,0,6,100,2};

int Search(int x,int i) //从i开始查找x的下表
{
	int count=1;
	while(x>val[i])
	{
		count++;   //比较次数
		i=ptr[i];  //寻找i的下一个元素
	}
	return count;  //返回比较的次数
}

int A(int x)
{
	return Search(x,head);
}

int D(int x)
{
	int i=rand()%n;
	int y=val[i];
	if(x<y)
	{
		return Search(x,head)+1;
	}
	else
	{
		if(x>y)
		{
			return Search(x,ptr[i])+1;
		}
		else
			return 1; //只比较了一次
	}
}

int B(int x) //设x在val数组中
{
	int i=head;
	int max=val[i]; //max的初值
	int y=0;
	for(int j=0;j<sqrt(n);j++)
	{
		y=val[j];
		if((max<y) && (y<=x))
		{
			i=j;
			max=y;
		}//小于等于x的最大值
	}
	return Search(x,i)+(int)sqrt(n); //从y开始继续搜索
}

int C(int x)  //在B算法基础上的改进
{
	int i=rand()%n;
	int max=val[i];
	int temp=0;
	int y=0;
	for(int j=0;j<sqrt(n);j++)
	{
		temp=rand()%n;
		y=val[temp];
		if((max<y) && (y<=x))
		{
			i=temp;
			max=y;
		}
	}
	return Search(x,i)+(int)sqrt(n);
}
int main()
{
	int number;
	while(1)
	{
		cout<<"请输入查找的关键字：";
		cin>>number;
		cout<<"A: "<<A(number)<<endl;
		cout<<"B: "<<B(number)<<endl;
		cout<<"C: "<<C(number)<<endl;
		cout<<"D: "<<D(number)<<endl;
	}
	return 0;
}

EX9：

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
/*写一算法，求n=12~20时最优的StepVegas值*/
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"

#define N 12
#define experTimes 100

int sol_vec[N+1] ={0};
int nodeCount = 0;

int legal_place(int k);
int backtrace(int n);
int QueensLv(int stepVegas);

int main()
{
	int n,i;
	int suc_count;  
	int sucNode;
	int failNode;
	int step_vegas = 0;
	double run_time;
	//clock_t start,finish;
	time_t start,finish;

	srand((unsigned) time(NULL));
	printf("StepVegas     p           s            e        t \n");
	for(step_vegas;step_vegas <= N;step_vegas++)
	{
		suc_count = 0;
		sucNode = 0;
		failNode = 0;
		start = clock();  

		for(i = 0; i < experTimes ;i++)
		{
			if(QueensLv(step_vegas))
			{
				suc_count++;
				sucNode+=nodeCount;
			}
			else
			{
				failNode+=nodeCount;
			}
		}

		finish = clock();  //结束时钟
		//run_time = (double)(finish - start)*1000/ CLOCKS_PER_SEC; 
		run_time=difftime(finish,start);

		printf("%d             ",step_vegas);
		printf("%f    ",(double)suc_count/experTimes);
		printf("%f    ",(double)sucNode/suc_count);

		if(failNode == 0)
			printf("---      ");
		else
			printf("%f      ",(double)failNode/(experTimes -suc_count));

		printf("%fms\n",(double)run_time/experTimes);
	}


	
	return 0;
}
/*从第r行开始回溯*/
int backtrace(int r)
{
	sol_vec[r] = 0; //第r行
	int tmp = r;

	do
	{
		sol_vec[r]++;
		while((!legal_place(r))&&(sol_vec[r] <= N))
			sol_vec[r]++;

		if(sol_vec[r] <= N)
		{
			nodeCount++;
			if(r == N)
			{
				return 1;
			}
			else
			{
				r++;
				sol_vec[r] = 0;
			}
		}
		else
		{
			sol_vec[r] = 0;
			r--;
		}

	}while(r > tmp);

	return 0;
}

/*判断第k个皇后的位置是否符合规则*/
int legal_place(int k)
{
	int i;

	for(i = 1;i < k;i++)
		if((sol_vec[i] == sol_vec[k]) || (abs(sol_vec[i]-sol_vec[k]) == abs(i-k)))
			return 0;

	return 1;
}

int QueensLv(int stepVegas)
{

	int count,k,i,j,tmp;
	k = 0; 
	/*纯回溯法*/
	if(stepVegas == 0)
	{
		nodeCount= 0;
		backtrace(1);
	}
	
	else 
	{
		nodeCount= 0;
		do
		{
			count = 0;  //当前行的open位置总数
			for(i = 1;i <= N;i++)
			{
				sol_vec[k+1] = i;
				/*如果列i对(k+1)皇后可用,那么(k+1)个皇后有一定几率放在i列*/
				if(legal_place(k+1)) 
				{
					count++;
					tmp	= rand()%count+1;
					if(tmp == 1)
					{
						j = i;
					}
				}
			}
			if(count > 0)
			{
				sol_vec[++k] = j;
				nodeCount++;
			}
		}while((count > 0) && (k!=stepVegas));
		/*折中算法，即是随机方法和回溯法结合*/
		if(stepVegas ==N)
		{
			if(count > 0)
				return 1;
			else 
				return 0;
		}    
		/*贪心LV算法*/
		else
		{
			if(count > 0)
			{
				backtrace(k);
			}
			else
				return 0;
		}
	}
}

ex10:

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
#include<iostream>
#include<cstdlib>
#include<math.h>
#include<time.h>
using namespace std;

bool Btest(int a, int n)
{
	int s=0;
	int t=n-1;
	int x=1;
	while(t%2!=1)
	{
		t=t/2;
		s++;
	}
	for(int i=0;i<t;i++)
	{
		x=x*a;
		x=x%n;
	}
	if((x==1) || (x==n-1))
		return true;
	for(int i=1;i<=s-1;i++)
	{
		x=(x*x)%n;
		if(x==n-1)
			return true;
	}
	return false;
}

bool MillRab(int n)
{
	int a=0;
	srand((unsigned) time(NULL));
	a=rand()%(n-3)+2;
	return Btest(a,n);
}

bool RepeatMillRab(int n,int k)
{
	for(int i=1;i<=k;i++)
	{
		if(!MillRab(n))
			return false;
	}
	return true;
}

int CerAlgorithm(int n)  //确定性算法
{
	int x=0;
	int count=1;
	bool flag=true;
	for(int j=3;j<=n;j=j+2)
	{
		x=(int)sqrt(j);
		for(int i=2;i<=x;i++)
		{
			if(j%i==0)
			{
				flag=false;
				break;
			}
				
		}
		if(flag)
			count++;
		flag=true;
	}
	return count;
}

int PrintPrimes(int n)  //打印1万以内的素数(概率)
{
	//cout<<"2 3 ";
	int count=2;
	int odd=5;
	int x=0;
	while(odd<=n)
	{
		if(RepeatMillRab(odd,(int)(log((double)odd)/log(10.0))))
		{
			count++;
			//cout<<odd<<" ";
			//if(count%10==0)
				//cout<<endl;
		}
		odd=odd+2;	
	}
	return count;
}


int main()
{
	cout<<"确定算法计算出100~10000内有"<<CerAlgorithm(10000)-CerAlgorithm(100)<<"个素数"<<endl;
	cout<<"概率算法计算出100~10000内有"<<PrintPrimes(10000)-PrintPrimes(100)<<"个素数"<<endl;
	return 0;
}