算法设计与分析作业

1、算法设计与分析徐玥SA一、 概率算法部分1. 求近似值的算法：若将y uniform(0, 1) 改为 y x, 则上述的算法估计的值是什么？解：改为y x，最终值为412=22.2. 在机器上用4011-x2dx估计值，给出不同的n值及精度。解：运行代码：#include#include#include#include#define N using namespace std;void HitorMiss()double x, y, f_x;int cnt = 0;srand(unsigned)time(NULL);for (int i = 0; i N; i+)x = (double)ra

2、nd() / RAND_MAX;y = (double)rand() / RAND_MAX;f_x = sqrt(1 - x*x);if (y f_x) cnt+;cout 4.0*cnt / N endl;int main()HitorMiss();system(pause);return 0;运行结果为：n值结果精度100003.173623.1367633.1416133.1410843.1416343.1415753设a, b, c和d是实数，且a b, c d, f:a, b c, d是一个连续函数，写一概率算法计算积分：abfxdx解：运行代码：#include#include#i

3、nclude#includeusing namespace std;/MC 积分函数void MC(double a, double b, double c, double d, double(*func)(double);/ 测试函数double test(double x);int main()MC(0, 4, -1, 8, test);system(pause);return 0;void MC(double a, double b, double c, double d, double(*func)(double)int cnt = 0, n = ;double x, y, f_x;s

4、rand(unsigned)time(NULL);for (int i = 0; i n; i+)x = a + (b - a)*(double)rand() / RAND_MAX;y = c + (d - c)*(double)rand() / RAND_MAX;f_x = func(x);if (y 0) cnt+;if (yf_x) cnt-;cout 36.0*cnt / n endl;double test(double x)return x*x - 2 * x;运行结果为：n值结果精度100005.50815.2966825.3161225.3359635.3368835.3339

5、444若I是01fxdx的正确值，h是由HitorMiss算法返回的值，则当nI(1-I)2时，有：Probh-I1-解：任取nI(1-I)2，设H(n)为n次命中的次数，则H(n)=nh为一个二项分布EH(n)=nI， DH(n) = nI(1-I)，利用切比雪夫不等式：Probh-I=ProbHnn-EHnn1-DHnn2=1-DHn2n2=1-I(1-I)n2由于nI(1-I)2，则I(1-I)n2，因此Probh-I1-5用上述算法，估计整数子集1n的大小，并分析n对估计值的影响。解：运行代码：#include#include#include#include#includeusing

6、namespace std;#define N #define PI 3.int main()random_device rd;uniform_int_distribution dist(1, N);long long number = dist(rd);double count = 0;set myset;for (int i = 0; i 50; i+)do myset.insert(number);count+;number = dist(rd); while (myset.find(number) = myset.end();myset.clear();count /= 50;long

7、 long result = (long long)(2.0 * count*count / PI);cout result endl;cout err:t 1.0*abs(N - result) / N endl;system(pause);return 0;运行结果为：n值估计值误差1000096373.63%17.71%10.50%4.39%7.01%6分析dlogRH的工作原理，指出该算法相应的u和v解：dlogRH采用了SherWood算法进行随机化的预处理该算法的C代码为：int dlogRH(int g, int a, int p)r = uniform(0.p - 2);b =

8、 ModularExponent(g, r, p);/求g=br mod p, 随机取其中一个元素c = mod(b*a, p); /(gr mod p)(gx mod p) mod p = gr + x mod p = c,将实例x转化为实例yy = log g, pc;/实验确定性算法求logp,gc, y=r+xreturn (y - r) mod(p - 1);在该算法中u为：grmod pgxmod pmod p= gr+xmod p=cv为：logp,gst mod p=logp,gs+ logp,gtmod(p-1)7写一Sherwood算法C，与算法A， B，D比较，给出实验结

9、果。解：运行代码：#include#include#include#include#includeusing namespace std;#define target 1int n = 15, head = 7;int val15 = 2, 5, 10, 7, 4, 14, 8, 1, 9, 6, 11, 13, 12, 15, 3 ;int ptr15 = 14, 9, 10, 6, 1, 13, 8, 0, 2, 3, 12, 5, 11, 100, 4 ;int search(int x, int i);int A(int x);/确定性O(n)算法int B(int x);/确定性为O

10、(n)的确定性算法int C(int x);/在算法B基础上改进的SherWood算法int D(int x);/时间为O(n)的概率算法int main()cout A(target) endl;cout B(target) endl;cout C(target) endl;cout D(target) endl;system(pause);return 0;int search(int x, int i)return 0;int A(int x)return search(x, head);int B(int x)int i = head;int max = vali;int y;for

11、(int j = 0; j sqrt(float(n); j+)y = valj;if (max y & y = x)max = y;i = j;return (search(x, i) + (int)sqrt(float)n);int C(int x)random_device rd;uniform_int_distribution dist(0, n - 1);int i = dist(rd);int max = vali;int y;for (int j = 0; j sqrt(float(n); j+)int temp = dist(rd);y = valtemp;if (max y

12、& y = x)max = y;i = temp;return search(x, i) + (int)sqrt(float)n);int D(int x)random_device rd;uniform_int_distribution dist(0, n - 1);int i = dist(rd);int y = vali;if (x y)return search(x, ptri);elsereturn i;运行结果为：查找对象A算法比较次数B算法比较次数C算法比较次数D算法比较次数10330213313243143553543346543076336874379853810933311

13、1044101211546131263914137341514859均值74.46673.44.73338证明：当放置（k+1)th皇后时，若有多个位置是开放的,则算法QueensLV选中其中任一位置的概率相等。证明：假设放置k+1个皇后时，有nb 个位置是开放的，分别极为a,binb那么第a个位置被选到的概率为1*12*23*i-1i*nb-1nb=1nb第b个位置被选中的概率为12*23*i-1i*nb-1nb=1nb第i个位置被选中的概率为1i*ii+1*nb-1nb=1nb第nb个位置被选到的概率为1nb所以算法QueensLV选中其中任一位置的概率为1nb9写一算法，求n=1220时

14、最优的StepVegas值。解：运行代码：#include#include#include#include#includeusing namespace std;#define N 12#define RUN_TIME 100int xN + 1 = 0 ;bool place(int k);void backtrace(int step);int QueenLV(int StepVegas);int main()int StepVegas, time_now, time_end;for (StepVegas = 1; StepVegas = N; StepVegas+)int j = 0,

15、sucess = 0;time_now = clock();dowhile (!QueenLV(StepVegas);backtrace(StepVegas + 1);if (xN != 0)sucess+;/cout sucess = sucess endl;for (int i = 1; i = N; i+)xi = 0;j+; while (j RUN_TIME);cout -StepVegas = StepVegas - endl;cout Run RUN_TIME times,;cout sucess sucess times!, ;cout sucess rate is 100.0

16、*sucess / RUN_TIME endl;time_end = clock();cout It takes (time_end - time_now) * 1000 / CLOCKS_PER_SEC / sucess;cout to solve this problem endl;system(pause);return 0;bool place(int k)for (int j = 1; j N) return;for (int i = 1; i = N; i+)xstep = i;if (place(step)backtrace(step + 1);int QueenLV(int S

17、tepVeags)random_device rd;int line = 1, nb = 1, j = 0;while (line 0)nb = 0;j = 0;for (int i = 1; i = N; i+)xline = i;if (place(line)nb+;uniform_int_distribution dist(1, nb);if (dist(rd) = 1) j = i;if (nb 0) xline+ = j;if (nb 0)return true;elsereturn false;运行结果为：N=12时，StepVegas运行时间/ms正确率162.5110026.8

18、210031.0710040.275519850.8360.6570.253680.2690.31100.4418643110.43100121.54100从运行结果来看，当StepVegas=5,6时运行时间最少，且正确率较高。N=13时，StepVegas运行时间/ms正确率1352.19100235.2710034.6310040.810050.260879260.8270.224494980.3390.31100.36110.57540120.59100131.9100从运行结果来看，当StepVegas=6时运行时间最少，且正确率较高。N=14时，StepVegas运行时间/ms正确

19、率12044.941002187.77100321.8410043.09919950.9960.279078670.7180.4290.28100.31110.7225120.42130.58100142.65100从运行结果来看，当StepVegas=7时运行时间最少，且正确率较高。N=15时，StepVegas运行时间/ms正确率113645.810021122.441003112.77100416.0310052.5310060.9470.8780.5790.435100.26110.30120.31130.52140.75100153.18100从运行结果来看，当StepVegas=7

20、，8时运行时间最少，为7时正确率较高。当N大于15，运行时间较长，从上面几个可以看出，当StepVegas=N/4N/2范围内，效果较好。10PrintPrimes /打印1万以内的素数 print 2，3； n 5； repeatif RepeatMillRab(n, ) then print n;n n+2; until n=10000;与确定性算法相比较，并给出10010000以内错误的比例。解：运行代码：#include#include#include#include#includeusing namespace std;#define N 100#define PI 3.bool B

21、east(int a, int n);/判断强伪素数bool Miller_Rabin(int n);/MR算法bool Repeat_Miller_Rabin(int k, int n);/MR算法重复K次bool simple(int n);/简单确定算法int main()set myset;for (int i = 101; i 10000; i += 2)if (simple(i)myset.insert(i);for (int i = 101; i 10000; i += 2)if (Repeat_Miller_Rabin(int)log(float)i), i)if (myset.find(i) = myset.end()cout MR算法找到的 i 不是素数 endl;myset.erase(i);if (myset.size() = 0) cout MR算法完全正确! endl;elseset:iterator it;cout MR算法没有找到的素数： endl;for (it = myset.begin(); it != myset.end(); it+)cout *it t;cout endl;system(pause);return 0;bool Beast(int a, int n)int s = 0, t = n