演算法設計與分析王曉東答案

Ⅰ 王曉東的出版著作

王曉東，《計算機演算法設計與分析》，ISBN：7505363913，電子工業出版社，2001年1月，字數：48萬字.
王曉東，《數據結構與演算法設計》，ISBN：7505374605，電子工業出版社，2001年12月，字數：60萬字.
王曉東，《數據結構與演算法》，ISBN：7040132044，高等教育出版社，2003年12月，字數：50萬字.
王曉東，《演算法設計與分析》，ISBN：7302061866，清華大學出版社，2003年1月，字數：49.5萬字.
王曉東，《計算機演算法設計與分析（第2版）》，ISBN：7121000016，電子工業出版社，2004年6月，字數：55萬字.
王曉東，《演算法設計與實驗題解》，ISBN：7121031035，高等學校規劃教材，電子工業出版社，2006年9月，字數：83萬字.
王曉東，《演算法設計與分析習題解答》，ISBN：7302140081，普通高等教育「十一五」國家級規劃教材，清華大學出版社，2006年12月，字數：60萬字.
王曉東，《計算機演算法設計與分析（第3版）》，ISBN：9787121042782，普通高等教育「十一五」國家級規劃教材，電子工業出版社，2007年5月，字數：62萬字.
王曉東，《數據結構（C語言版）》，ISBN：9787121046292，高等學校規劃教材，電子工業出版社，2007年7月，字數：42萬字.
王曉東，《演算法設計與分析（第2版）》，ISBN：9787302163435，普通高等教育「十一五」國家級規劃教材，清華大學出版社，2008年1月，字數：52.8萬字.
王曉東，《演算法設計與分析習題解答（第2版）》，ISBN：9787302167198，普通高等教育「十一五」國家級規劃教材，清華大學出版社，2008年2月，字數：61.7萬字.

Ⅱ Data Structures and Algorithm Analysis in C++書後的習題答案

下面是我根據別人的提示和自己的參考總結出的幾個階段的書籍，希望對你有幫助！！

第一階段：
1：：H.M.Deitel和P.J.Deitel的《 C++ How to Program 》（C++大學教程）
2：： 錢能的《C++程序設計教程》
3：：Stanley B.lippman著 侯捷 譯的《essential c++》
4：：Stanley B.Lippman,Josee LaJoie,Barbara E.Moo的《c++ primer》
5：：Bjarne Stroustrup的《the c++ programming language》

第二階段：
1：：Scott Meyers的《effective c++》
2：：Herb Sutter的《exceptional c++》
3：：Scott Meyers的《more effective c++》
4：：Herb Sutter的《more exceptional c++》

第三階段：
1：：Stanley B.lippman的《insied the c++ object model》（深度探索C++ 對象模型）
2：：Bjarne Stroustrup的《The design and evolution of c++》（C++的設 計與演化）
3：：tephen C. Dewhurst的《C++ Gotchas: Avoiding Common Problems in Coding and Design》（C++程序設計陷阱）

第四階段：
1：： Nicolai M.Josuttis的《the c++ standard library》（C++標准程序庫 —自修教程與參考手冊）
2：：Scott Meyers的《effective stl》
3：：Matthew H. Austern的《generic programming and the stl》（泛型編 程與STL)
4：：侯捷的 《stl源碼剖析》

第五階段：
1：：Herb Sutter的《exeptional c++ style》
2：：《c++ template》
3：：Andrei Alexandrescu的《modern c++ design》

第六階段
1：：《C++ 輸入輸出流及本地化》《C++ Network Programming》《大規模C++程序設計》
2：：Barbara E.Moo和Andrew Koenig的《Ruminations On C++》(C++ 沉思錄)

其他的：
Stanley B. Lippman,《Inside The C++ Object Model》影印版、中文版《深度探索C++對象模型》
Elements of Reusable Object-Oriented software》影印版、中文版《設計模式：可復用面向對象軟體的基礎》
John Lakos的著作《Large-Scale C++ Software Design》（《大規模C++程序設計》
Andrew Koenig和Barbara Moo在《Accelerated C++: Practical Programming by Example》《Ruminations on C++》
Bruce Eckel,《C++編程思想》

windows編程系列：

Charles Petzold 的 《Programming Windows》（Windows程序設計）
Jeffrey Richter 的《》（Windows核心編程）和《Advanced Windows》（Windows 高級編程指南）

數據結構和演算法
1：：清華教授嚴蔚敏和廣東工業大學教授吳偉民的《數據結構(C語言版)》
2：：清華教授殷人昆的《數據結構(用面向對象方法與C++描述）》
3：：經典書籍：Mark Allen Weiss的《Data Structures and Algorithm Analysis in C》（數據結構與演算法分析--C語言描述）和《Data Structures and Algorithm Analysis in C++》（數據結構與演算法分析--C++語言描述）
4：：王曉東的《演算法設計與分析》
5：：M.H.Alsuwaiyel（沙特）的 《Algorithms Design Techniques and Analysis》（演算法設計技巧與分析）
6：：經典：Thomas H.Cormen, Charles E.Leiserson的《Introction to Algorithms》（演算法導論）
另外,虛機團上產品團購,超級便宜

Ⅲ 急求專升本教材《數據結構與演算法》，王曉東編的課後習題答案

你去課後習題網看看 估計會有答案的

Ⅳ 誰能解釋一下用遞歸做的排列演算法的詳細步驟參考王曉東的《計算機演算法設計與分析》p11

用到遞歸的排序演算法有快速排序和歸並排序。
快速排序：先選最開始的元素為樞軸，然後分別從兩頭中的一頭開始與樞軸比較。後面的應該大於樞軸，前面的應該小於樞軸，不然則交換（前面與後面），最後確定下來的位置（前後重合）就是樞軸的位置。這樣一來原序列就一分為二。不斷遞歸，再一分為二，最後直到被分為的兩端中有一個元素單獨的時候就結束分割。
歸並排序:第一次兩個兩個的來，排序之後就歸並成一個有序列，然後再四個四個的來，排序之後歸並成一個有序列……直到最後兩個歸並為一個有序列。

Ⅳ 求NOIP2007普及組初賽試題（棋盤覆蓋問題）的程序解析，比如程序的思路以及每步的作用

聲明：本文使用的代碼和例子的來源：《計算機演算法設計與分析》（王曉東編著，電子工業出版社）。我對代碼做了少許修改，使可以在tc的圖形模式下看到題目的結果。

題目：在一個(2^k)*(2^k)個方格組成的棋盤上，有一個特殊方格與其他方格不同，稱為特殊方格，稱這樣的棋盤為一個特殊棋盤。現在要求對棋盤的其餘部分用L型方塊填滿（註：L型方塊由3個單元格組成。即圍棋中比較忌諱的愚形三角，方向隨意），切任何兩個L型方塊不能重疊覆蓋。L型方塊的形態如下：

■■*■■***■*■
■******■*■■*■■

題目的解法使用分治法，即子問題和整體問題具有相同的形式。我們對棋盤做一個分割，切割一次後的棋盤如圖1所示，我們可以看到棋盤被切成4個一樣大小的子棋盤，特殊方塊必定位於四個子棋盤中的一個。假設如圖1所示，特殊方格位於右上角，我們把一個L型方塊（灰色填充）放到圖中位置。這樣對於每個子棋盤又各有一個「特殊方塊」，我們對每個子棋盤繼續這樣分割，知道子棋盤的大小為1為止。
用到的L型方塊需要（4^k-1)/3 個，演算法的時間是O（4^k)，是漸進最優解法。

Ⅵ 請教各位如何編程實現"無優先順序運算問題"！急！

...暈，老大這題不是很簡單的，不過在《演算法分析與實驗題解》上有這題，你可以自己去看看，給你個C#版本的，down的，和C++差不多
主窗體源碼(C#)

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace 無優先順序運算
{
public partial class 無優先順序運算 : Form
{
public 無優先順序運算()
{
InitializeComponent();
}
private int Factorial(int n)//計算階乘
{
if (n < 1) return -1;
else if (n == 1) return 1;
else return n * Factorial(n - 1);
}
private double doCalculation(double x, double y, string sign)//計算表達式
{
if (sign == "+") return (x + y);
else if (sign == "-") return (x - y);
else if (sign == "*") return (x * y);
else if (sign == "/") return (x / y);
else return 0.0;
}

/*
這個全排列窮舉演算法的核心部分基於這樣一個思想：
從小到大列舉所有的可能的全排列
假設現有的一個數是m=a[1]a[2]....a[n-1]a[n]
則全排列中下一個緊接著的m的數(及比m大的數中最小的一個數)應該由如下原則產生：
設立相鄰的兩個指針k和flag，其中k=flag-1，當比較發現出現num[flag]>num[k]時，進行如下操作
從num[n]開始往回找出第一個大於num[k]的數num[k1]，交換num[k]和num[k1]
將num[flag]到num[n]的數倒置，以求得num[flag]到num[n]全排列裡面最小的數，之前的是到num[flag]到num[n]全排列裡面最大的數
如果往回找的時候發現滿足條件的只有第一個數，及k1=1，則表明已經列舉出最大的數N...21，完成任務#
否則繼續恢復那些變數的值，重復如上過程
如對於134652，當k=3，flag=4時，滿足num[flag]>num[k]
此時，從a[6]開始往前找第一個比num[3]=4大的數num[k1]=5
交換num[k]和num[k1]，形成數字135642，然後將642倒置
產生最終滿足條件的數135246
*/

private static int N = 9;
private int[] num = new int[N + 1]; //存放數字1到N，窮舉通過有規律的變化num數組裡面的各個數的位置實現；使用數組的num[1]到num[N]部分，不使用num[0]
private int cnt; //排列計數
private int[,] array;//存放排列數
private int cnt2;
private void exchange(int i, int j)//交換數組中位置i和位置j存放的數字
{
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
return;
}
private void output()//輸出由數組存放順序決定的一個數
{
for (int k = 1; k < N + 1; k++)
{
array[cnt2, k] = num[k];
}
if(cnt2<362880) cnt2++;
}
private void reverse_sort(int i, int j)//倒置數組中從位置i開始到j的元素
{
for (int k = 0; k < (j - i + 1) / 2; k++)
exchange(i + k, j - k);
return;
}
private void count(int n)//計算函數，由主函數generateArray()調用
{
output(); //輸出初始的一個數123...N
int flag = n; //初始flag指針指向最後一個數字
for (int k = n - 1; k > 0; k--)
{ //設立k指針，並往前找，k與flag是始終相鄰的
if (num[flag] > num[k])
{ //如果找到一對相鄰的數滿足後面的元素大於前面的
for (int k1 = n; k1 > 0; k1--)
{ //從最後一個數開始往前尋找
if (k1 == 1) return; //如果找到第一個元素，則完成窮舉任務，返回
if (num[k1] > num[k])
{ //否則必定會在到達k之前找到一個k1位置的元素比k位置的元素大
exchange(k, k1); //交換這兩個元素，產生一個中間組合數
break; //停止尋找
}
}
reverse_sort(flag, n); //倒置flag之後的數列，產生需要的組合數
output(); //輸出結果
cnt++; //記入總個數
flag = n; //flag恢復為初始值，准備下一個變換
k = n; //k恢復為初始值，但是考慮到後面循環結束時要運行k--，所以k要增加到(n-1)+1=n
}
else flag--; //如果當前沒找到一對相鄰的數滿足後面的元素大於前面的，則flag減1，之後進入下一循環前k也會減1
//保證二者還是相鄰
}
return;
}
private void generateArray()//全排列窮舉主函數
{
cnt = 1;
cnt2 = 1;
for (int k = 1; k < N + 1; k++)
{
num[k] = k;
}
count(N);
}
private void generateResult()//找出符合條件的等式並輸出
{
int a, b, c, d, f, goal, sNum;
goal = (int)numericUpDown6.Value;
string[,] solution;//存放所有方案的字元組
string[,] result;//存放符合要求的方案的字元組
a = (int)numericUpDown1.Value;
b = (int)numericUpDown2.Value;
c = (int)numericUpDown3.Value;
d = (int)numericUpDown4.Value;
f = (int)numericUpDown5.Value;
string[] element = new string[10];
element[1] = a.ToString();
element[2] = b.ToString();
element[3] = c.ToString();
element[4] = d.ToString();
element[5] = f.ToString();
element[6] = "+";
element[7] = "-";
element[8] = "*";
element[9] = "/";
int s1, s2, s3, s4, s5, s6, s7, s8, s9;
int n = Factorial(5) * Factorial(4);//所有方案的總數(5!*4!)
solution = new string[n + 1, 10];
result = new string[n + 1, 10];
int scount = 1;
int rcount = 1;
sNum = Factorial(9);//362880
array = new int[sNum + 1, 10];
generateArray();
for (int i = 1; i <= sNum; i++)//窮舉所有方案，送入solution字元串組
{
s1 = array[i, 1];
s2 = array[i, 2];
s3 = array[i, 3];
s4 = array[i, 4];
s5 = array[i, 5];
s6 = array[i, 6];
s7 = array[i, 7];
s8 = array[i, 8];
s9 = array[i, 9];
if ((s1 <= 5 && s3 <= 5 && s5 <= 5 && s7 <= 5 && s9 <= 5) && (s2 > 5 && s4 > 5 && s6 > 5 && s8 > 5)) //確保表達式形式正確
if ((s1 != s3 && s1 != s5 && s1 != s7 && s1 != s9 && s3 != s5 && s3 != s7 && s3 != s9 && s5 != s7 && s5 != s9 && s7 != s9) && (s2 != s4 && s2 != s6 && s2 != s8 && s4 != s6 && s4 != s8 && s6 != s8))
{
solution[scount, 1] = element[s1];
solution[scount, 2] = element[s2];
solution[scount, 3] = element[s3];
solution[scount, 4] = element[s4];
solution[scount, 5] = element[s5];
solution[scount, 6] = element[s6];
solution[scount, 7] = element[s7];
solution[scount, 8] = element[s8];
solution[scount, 9] = element[s9];
++scount;
}
}
for (int i = 1; i <= n; i++)//計算每個等式，如果結果等於n，保存到Result字元組
{
double x1, x2, x3, x4;
x1 = doCalculation(double.Parse(solution[i, 1]), double.Parse(solution[i, 3]), solution[i, 2]);
x2 = doCalculation(x1, double.Parse(solution[i, 5]), solution[i, 4]);
x3 = doCalculation(x2, double.Parse(solution[i, 7]), solution[i, 6]);
x4 = doCalculation(x3, double.Parse(solution[i, 9]), solution[i, 8]);
if (x4 == (double)goal)
{
for (int j = 1; j <= 9; j++) result[rcount, j] = solution[i, j];
++rcount;
}
}
int rrcount = rcount - 1;

//輸出符合條件的等式
richTextBoxResult.Clear();
if(rcount==1) richTextBoxResult.Text = "符合條件的等式不存在。";
else if (rcount > 1 && rcount < 200)
{
richTextBoxResult.Text += "符合條件的等式有" + rrcount.ToString() + "個，以下為全部等式：\n\n";
for (int i = 1; i <= rcount - 1; i++)
{
for (int j = 1; j <= 9; j++) richTextBoxResult.Text += result[i, j] + " ";
richTextBoxResult.Text += "= " + goal.ToString();
richTextBoxResult.Text += "\n";
}
}
else
{
richTextBoxResult.Text += "符合條件的等式多達"+rrcount.ToString()+"個，為避免程序不響應，只顯示前200個：\n\n";
for (int i = 1; i <= 200; i++)
{
for (int j = 1; j <= 9; j++) richTextBoxResult.Text += result[i, j] + " ";
richTextBoxResult.Text += "= " + goal.ToString();
richTextBoxResult.Text += "\n";
}
}
}
private void buttonOkClick(object sender, EventArgs e)
{
generateResult();
}
}
}

Ⅶ 5. 設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti，1<=i<=n。應如何安排n個顧客的服務次序才能

上面的 思路不錯

最優服務次序問題
一、問題描述：
設有n 個顧客同時等待一項服務。顧客i需要的服務時間為ti, 1≦i ≦n 。共有s處可以提供此服務。應如何安排n個顧客的服務次序才能使平均等待時間達到最小?平均等待時間是n 個顧客等待服務時間的總和除以n。
二、貪心選擇策略
假設原問題為T，而我們已經知道了某個最優服務系列，即最優解為A={t(1)，t(2)，…．t(n)}(其中t(i)為第i個用戶需要的服務時間)，則每個用戶等待時間為：
T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)；
那麼總等待時問，即最優值為：
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…2*t(n-1)+t(n)；
由於平均等待時間是n個顧客等待時間的總和除以n，故本題實際上就是求使顧客等待時間的總和最小的服務次序。
本問題採用貪心演算法求解，貪心策略如下：對服務時間最短的顧客先服務的貪心選擇策略。首先對需要服務時間最短的顧客進行服務，即做完第一次選擇後，原問題T變成了需對n-1個顧客服務的新問題T』。新問題和原問題相同，只是問題規模由n減小為n-1。基於此種選擇策略，對新問題T』，選擇n-1顧客中選擇服務時間最短的先進行服務，如此進行下去，直至所有服務都完成為止 。
三、問題的貪心選擇性質
先來證明該問題具有貪心選擇性質，即最優服務A中t(1)滿足條件：t(1)<=t(i)(2<i<n)。
用反證法來證明：假設t(1)不是最小的，不妨設t(1)>t(i)(i>1)。
設另一服務序列B=（t(i)，t(2)，…，t(1)…，t(n)）
那麼TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0
即TA>TB，這與A是最優服務相矛盾。
故最優服務次序問題滿足貪心選擇性質。
四、問題的最優子結構性質
在進行了貪心選擇後，原問題T就變成了如何安排剩餘的n-1個顧客的服務次序的問題T』，是原問題的子問題。
若A是原問題T的最優解，則A』={t(2)，…t(i)…t(n))是服務次序問題子問題T』的最優解。
證明：假設A』不是子問題T』的最優解，其子問題的最優解為B』，則有TB』<TA』，而根據TA的定義知，TA』十t(1)=TA。因此TB』+t(1)<TA』+t(1)=TA，即存在一個比最優值TA更短的總等待時間，而這與TA為問題T的最優值相矛盾。因此，A』是子問題T』的最優值。
從以上貪心選擇及最優子結構性質的證明，可知對最優服務次序問題用貪心演算法可求得最優解。
根據以上證明，最優服務次序問題可以用最短服務時間優先的貪心選擇可以達到最優解。故只需對所有服務先按服務時間從小到大進行排序，然後按照排序結果依次進行服務即可。平均等待時間即為TA/n。
五、演算法實現
由多處最優服務次序問題具有貪心選擇性質和最優子結構性質，容易證明演算法greedy的正確性。本演算法採用最短服務時間優先的貪心策略。首先將每個顧客所需要的服務時間從小到大排序。然後申請2個數組：st[]是服務數組，st[j]為第j個隊列上的某一個顧客的等待時間；su[]是求和數組，su[j]的值為第j個隊列上所有顧客的等待時間；
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;//循環分配顧客到每一個服務點上
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
六、演算法測試結果

七、演算法復雜性分析
程序主要是花費在對各顧客所需服務時間的排序和貪心演算法，即計算平均服務時間上面。其中，貪心演算法部分只有一重循環影響時間復雜度，其時間復雜度為O(n)：而排序演算法的時間復雜度為O(nlogn)。因此，綜合來看演算法的時間復雜度為O(nlogn)。
八、參考文獻
[1] 王曉東.計算機演算法設計與分析(第3版)[M]．北京：電子工業出版社,2007．
[2] 陳媛.《演算法與數據結構》[M],清華大學出版社, 第1版,2005.4.
[3] 王曉東.演算法設計與實驗題解 [M]．北京：電子工業出版社,2008．

附錄（程序代碼）
#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
using std::vector;
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
void main()
{int n;//等待服務的顧客人數
int s;//服務點的個數
int i;
int a;
int t;//平均服務時間
vector<int>x;
cout<<"please input the num of the customer:"<<endl;
cin>>n;
cout<<"please input the num of the server:"<<endl;
cin>>s;
cout<<"please input the need service time of each customer:"<<endl;
for(i=1;i<=n;i++){
cout<<"No."<<i<<endl;
cin>>a;
x.push_back(a);
}
t=greedy(x, s);
cout<<"the least average waiting time is:"<<t<<endl;
}

Ⅷ 《計算機演算法設計與分析》答案 王曉東編第三版

大學學習資料免費下載網 有

在 電子/信息/通信/計算機 版塊

標題：王曉東《計算機演算法設計與分析(第3版)》課後答案/習題詳解

還有很多其他相關資料、課件、視頻等等

（下載不用積分）

Ⅸ 計算機演算法設計與分析 王曉東第二版與第三版的差別

增加了一些內容如下：為突出教材的可讀性和可用性，章首增加了學習要點提示；章末配有難易適度的習題，分為演算法分析題和演算法實現題兩部分；配套出版了《演算法設計與實驗題解》；並免費提供電子課件和教學網站服務。