算法设计与分析王晓东答案

Ⅰ 王晓东的出版着作

王晓东，《计算机算法设计与分析》，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版)》课后答案/习题详解

还有很多其他相关资料、课件、视频等等

（下载不用积分）

Ⅸ 计算机算法设计与分析 王晓东第二版与第三版的差别

增加了一些内容如下：为突出教材的可读性和可用性，章首增加了学习要点提示；章末配有难易适度的习题，分为算法分析题和算法实现题两部分；配套出版了《算法设计与实验题解》；并免费提供电子课件和教学网站服务。