小靈通不得不學(xué)好之大二下篇b homework供參考

1、張毅勤 1733422639HW5a1.1 對(duì)于元素個(gè)數(shù)為n的數(shù)組，要同時(shí)求出其最大值和最小值及其位置最多需要進(jìn)行3n次運(yùn)算，最少需要進(jìn)行n次運(yùn)算，所以計(jì)算復(fù)雜度為（n）。1.2 每個(gè)交點(diǎn)上面有(k+1)種狀態(tài)，即空棋或者放置某種顏色的棋子，一共有m*n個(gè)交點(diǎn)，所以棋盤(pán)的狀態(tài)有（k+1）（m*n）種，每列出一種棋盤(pán)狀態(tài)不超過(guò)某常數(shù)次操作，但至少等于1次操作，所以計(jì)算復(fù)雜度為（k+1）（m*n）。function AS=Sort1M(A,n)if mod(n,2)=0 A1=A(1:n/2);A2=A(1+n/2:n);n1=n/2;n2=n/2;function AS=Sort1M(A,n)i

2、f mod(n,2)=0 A1=A(1:n/2);A2=A(1+n/2:n);n1=n/2;n2=n/2;else A1=A(1:n-1/2);A2=A(1+(n-1)/2:n);n1=(n-1)/2;n2=1+(n-1)/2;endA1_new=Sort1(A1,n1);A2_new=Sort1(A2,n2);AS=Merge(A1_new,n/2,A2_new,n/2);end2.2 Sort1M需要(C3/2)*n2+C4*n+C5*n,則當(dāng)n較大時(shí)，Sort1M更快。2.3 第一次輸入：load Test_256.matAS=Sort1M(A,n);B1=AS(1), AS(round

3、(n/7), AS(round(n/5), AS(n)第一次輸出:B1 =1.0e+03 * -1.0225 -0.6843 -0.5434 1.0171第二次輸入：load Test_4096.matAS=Sort1M(A,n);B2 =AS(1), AS(round(n/7), AS(round(n/5), AS(n)第二次輸出：B2 =1.0e+03 * -1.0239 -0.7326 -0.6124 1.0239第三次輸入：load Test_8192.matAS=Sort1M(A,n);B3= AS(1), AS(round(n/7), AS(round(n/5), AS(n)第三次

4、輸出：B3 = 0.0462 14.4521 19.9555 99.9887HW5bQuestion 1第一次輸入：load(Test_65536)tic; AS=Sort1(A,n); toc;第一次輸入：load(Test_65536)tic; AS=Sort1(A,n); toc;tic; AMS=MergeSort(A,n); toc;tic; AMS2=MergeSort2(A,n); toc;%設(shè)定的臨界值n0=512B=AMS2(1), AMS2(round(n/7), AMS2(round(n/5), AMS2(round(3*n/7), AMS2(n)第一次輸出：時(shí)間已過(guò) 5

5、.371301 秒。時(shí)間已過(guò) 0.160030 秒。時(shí)間已過(guò) 0.071673 秒。B =1.0e+03 * -1.0240 -0.7300 -0.6118 -0.1505 1.0240MergeSort2函數(shù):function A=MergeSort2(A, n)if(n=512) A=Sort1(A,n);else n1=floor(n/2); n2=n-n1; A1=MergeSort2(A(1:n1),n1); A2=MergeSort2(A(n1+1:n),n2); A=Merge(A1,n1, A2, n2);end由上可知，當(dāng)n值足夠大時(shí)，Sort1用時(shí)最長(zhǎng)，MergeSort次

6、之，MergeSort2用時(shí)最短。Question 2factorial_loop函數(shù)：factorial_loop函數(shù)：function A=factorial_loop(n)A=1;for i=1:n A=A*i;endendfactorial_re函數(shù)：function A=factorial_re(n)if n=1A=1;elseA=n*factorial_re(n-1);endend第一次輸入：第一次輸入：n=10;tic; A=factorial_re(n); toc;tic; A=factorial_loop(n); toc;第二次輸入：n=50;tic; A=factorial

7、_re(n); toc;tic; A=factorial_loop(n); toc;第三次輸入：n=100;tic; A=factorial_re(n); toc;tic; A=factorial_loop(n); toc;第四次輸入：n=500;tic; A=factorial_re(n); toc;tic; A=factorial_loop(n); toc;第一次輸出：時(shí)間已過(guò) 0.002784 秒。第一次輸出：時(shí)間已過(guò) 0.002784 秒。時(shí)間已過(guò) 0.001949 秒。第二次輸出：時(shí)間已過(guò) 0.000269 秒。時(shí)間已過(guò) 0.000010 秒。第三次輸出：時(shí)間已過(guò) 0.000078 秒。時(shí)間已過(guò) 0.000010 秒。第四次輸出：時(shí)間已