演算法概括課後題答案

① 《演算法導論》第三章-思考題（參考答案）

（多項式的漸進行為） 假設 是一個關於 的 次多項式，其中 ， 是一個常量。使用漸進符號的定義來證明下面的性質。

a. 若 ，則 。

b. 若 ，則 。

c. 若 ，則 。

d. 若 ，則 。

e. 若 ，則 。

已知： ，易得 。

故 。

情況 1：

，即： 。

故 。

情況 2：

，即： 。

故 。

情況 3：

，即： 。

故 。

情況 4：

，即： 。

故 。

情況 5：

，即： 。

故 。

（相對漸進增長） 為下表中的每對表達式 指出 是否是 的 或 。假設 且 均為常量。回答應以表格的形式，將「是」或「否」寫在每個空格中。

a.

令 代替 ，並令 代替 a，可得：

即： 。

又：若 。故： 。

b.

故， 。

令 。故 。

c.

。又 的值為在區間 中波動，故 與 無任何關系

d.

嚴格遞增，故對於任意正常量 ，總存在 ，使得 ，即：

也易證：故對於任意正常量 ，總存在 ，使得 ，即：

e.

。故 。

f.

故，

又， 是嚴格遞增的函數。故，

故， ，也即

也即

（根據漸進增長率排序）

a. 根據增長的階來排序下面的函數，即求出滿足 的函數的一種排列 。把你的表劃分成等價類，使得函數 和 在相同類中當且僅當 。

b.給出非負函數 的一個例子，使得對所有在（a）部分中的函數 ， 既不是 也不是 。

（漸進記號的性質） 假設 和 為漸進正函數。證明或反駁下面的每個猜測。

a. 蘊含 。

錯。例如： 。

b. 。

錯。例如： 。

c. 蘊含 ，其中對所有足夠大的 ，有 且 。

正確。

對於足夠大的 ，有 ；且 ，則存在正常量 ，使得 ，有

​

​

又 ，故當 ，且 足夠大，有：

​

故原問題成立。

d. 蘊含 。

錯。例如： 。

e. 。

當 時， ；其他條件下，不成立。

f. 蘊含 。

正確。 ，即存在正常量 ，使得 ，有

​ ，即

令 ，得 。

g. 。

錯。例如： 。

h. 。

正確。

易得， ，即存在正常量 ，使得 ，都有 。

令 ，即存在正常量 ，使得 ，都有 。

令 ，則 ，有 。

即 。

（ 與 的一些變形） 某些作者用一種與我們稍微不同的方式來定義 ；假設我們使用 （讀作「 無窮」）來標識這種可選的定義。若存在正常量 ，使得對無窮多個整數 ，有 ，則稱 。

a. 證明：對漸進非負的任意兩個函數 和 ，或者 或者 或者二者均成立，然而，如果使用 來代替 ，那麼該命題並不為真。

主要缺少了 這個條件；則若 ，必然有無窮多個正整數 ，使得 成立；

若 ，則上述兩者均成立；

反例： ，但 。

b. 描述用 代替 來刻畫程序運行時間的潛在優點與缺點。

優點： 對下屆的要求更寬松，可以兼容更多的情況；

缺點： 並非嚴格的漸進下界。因此實際意義並不大。

​ 某些作者也用一種稍微不同的方式來定義 ；假設使用 來標識這種可選的定義。我們稱 當且僅當 。

c. 如果使用 代替 但仍然使用 ，定理 3.1 中的「當且僅當」的每個方向將出現什麼情況？

沒有變化。 成立意味著 漸進非負，故 。

​ 有些作者定義 （讀作「軟 」）來意指忽略對數因子的 ：

：存在正常量 和 ，使得對所有 ，有 。

d. 用一種類似的方式定義 和 。證明與定理 3.1 相對應的類似結論。

：存在正常量 和 ，使得對所有 ，有 。

：存在正常量 和 ，使得對所有 ，有 。

（多重函數） 我們可以把用於函數 中的多重操作符 * 應用於實數集上的任意單調遞增函數 。對給定的常量 ，我們定義多重函數 為

​

該函數不必再所有情況下都是良定義的。換句話說，值 是為縮小其參數到 或更小所需函數 重復應用的數目。

​ 對如下每個函數 和常量 ，給出 的一個盡量緊確的界。

② 給出一些基本的演算法問題並給出答案

C語言演算法基礎
演算法（Algorithm）：計算機解題的基本思想方法和步驟。演算法的描述：是對要解決一個問題或要完成一項任務所採取的方法和步驟的描述，包括需要什麼數據（輸入什麼數據、輸出什麼結果）、採用什麼結構、使用什麼語句以及如何安排這些語句等。通常使用自然語言、結構化流程圖、偽代碼等來描述演算法。
一、計數、求和、求階乘等簡單演算法
此類問題都要使用循環，要注意根據問題確定循環變數的初值、終值或結束條件，更要注意用來表示計數、和、階乘的變數的初值。
例：用隨機函數產生100個[0，99]范圍內的隨機整數，統計個位上的數字分別為1，2，3，4，5，6，7，8，9，0的數的個數並列印出來。
本題使用數組來處理，用數組a[100]存放產生的確100個隨機整數，數組x[10]來存放個位上的數字分別為1，2，3，4，5，6，7，8，9，0的數的個數。即個位是1的個數存放在x[1]中，個位是2的個數存放在x[2]中，……個位是0的個數存放在x[10]。
void main()
{ int a[101],x[11],i,p;
for(i=0;i<=11;i++)
x[i]=0;
for(i=1;i<=100;i++)
{ a[i]=rand() % 100;
printf("%4d",a[i]);
if(i%10==0)printf("\n");
}
for(i=1;i<=100;i++)
{ p=a[i]%10;
if(p==0) p=10;
x[p]=x[p]+1;
}
for(i=1;i<=10;i++)
{ p=i;
if(i==10) p=0;
printf("%d,%d\n",p,x[i]);
}
printf("\n");
}
二、求兩個整數的最大公約數、最小公倍數
分析：求最大公約數的演算法思想：(最小公倍數=兩個整數之積/最大公約數)
(1) 對於已知兩數m，n，使得m>n；
(2) m除以n得余數r；
(3) 若r=0，則n為求得的最大公約數，演算法結束；否則執行(4)；
(4) m←n，n←r，再重復執行(2)。
例如: 求 m=14 ,n=6 的最大公約數. m n r
14 6 2
6 2 0
void main()
{ int nm,r,n,m,t;
printf("please input two numbers:\n");
scanf("%d,%d",&m,&n);
nm=n*m;
if (m<n)
{ t=n; n=m; m=t; }
r=m%n;
while (r!=0)
{ m=n; n=r; r=m%n; }
printf("最大公約數:%d\n",n);
printf("最小公倍數:%d\n",nm/n);
}
三、判斷素數
只能被1或本身整除的數稱為素數 基本思想：把m作為被除數，將2—INT（ ）作為除數，如果都除不盡，m就是素數，否則就不是。（可用以下程序段實現）
void main()
{ int m,i,k;
printf("please input a number:\n");
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<k;i++)
if(m%i==0) break;
if(i>=k)
printf("該數是素數");
else
printf("該數不是素數");
}
將其寫成一函數,若為素數返回1，不是則返回0
int prime( m%)
{int i,k;
k=sqrt(m);
for(i=2;i<k;i++)
if(m%i==0) return 0;
return 1;
}

③ 《計算機演算法設計與分析第5版習題及答案》pdf下載在線閱讀全文，求百度網盤雲資源

《計算機演算法設計與分析第5版習題及答案》網路網盤pdf最新全集下載:
鏈接：https://pan..com/s/1oxH2d3SdEUN0rx6LJRNBoA

④ 關於《數據結構與演算法分析 java語言描述》 的課後習題答案和項目設計的答案

http://download.csdn.net/download/tangzhnju/3688376， 別人的勞動成果，我只是搬運工，我下載看了下，好像不是所有題目都有答案，不過也很有參考意義
補充：不好意思，沒看清楚作者應該不是你需要的那一份

⑤ 誰有《數據結構與演算法javascript描述》這本書課後練習題的答案啊

[圖靈程序設計叢書].數據結構與演算法：JavaScript描述

鏈接: https://pan..com/s/1yx4OMqQdlo-ebkMq9keN-w

通過本書的學習，讀者將能自如地選擇最合適的數據結構與演算法，並在JavaScript開發中懂得權衡使用。此外，本書也概述了與數據結構與演算法相關的JavaScript特性。