没有合适的资源？快使用搜索试试~ 我知道了~

文库首页行业研究行业报告算法设计与分析(第2版)-王红梅-胡明-习题答案.doc

算法设计与分析(第2版)-王红梅-胡明-习题答案.doc

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

算法设计与分析

课程资料

计算机专业

0 下载量 51 浏览量 2024-06-24 08:00:57 上传评论收藏 181KB DOC 举报

温馨提示

试读

41页

课程资料，算法分析与设计，计算机专业课程资料，教案PPT，期末复习，期末考试题，知识点总结等，PDF，WORD下载，重点难点知识点，复习备考资料。

资源推荐

资源详情

资源评论

习题 1

1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（ Leonhard Euler ，

1707—1783）提出并解决了该问题。七桥问题

是这样描述的：一个人是否能在一次步行中穿

越哥尼斯堡（现在叫加里宁格勒，在波罗的海

南岸）城中全部的七座桥后回到起点，且每座

桥只经过一次，图 1.7 是这条河以及河上的两

个岛和七座桥的草图。请将该问题的数据模型

抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。

输入：一个起点

输出：相同的点

1，一次步行

2，经过七座桥，且每次只经历过一次

3，回到起点

该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个

奇点的图形。

2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减

法。请用伪代码描述这个版本的欧几里德算法

1.r=m-n

2.循环直到 r=0

2.1 m=n

2.2 n=r

2.3 r=m-n

3 输出 m

3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代

码和 C++描述。

//采用分治法

//对数组先进行快速排序

//在依次比较相邻的差

#include <iostream>

using namespace std;

int partions(int b[],int low,int high)

{

图 1.7 七桥问题

北区

东区

岛区

南区

int prvotkey=b[low];

b[0]=b[low];

while (low<high)

{

while (low<high&&b[high]>=prvotkey)

--high;

b[low]=b[high];

while (low<high&&b[low]<=prvotkey)

++low;

b[high]=b[low];

}

b[low]=b[0];

return low;

}

void qsort(int l[],int low,int high)

{

int prvotloc;

if(low<high)

{

prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴

qsort(l,low,prvotloc-1); //递归调用排序由 low 到 prvotloc-1

qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1 到 high

}

void quicksort(int l[],int n)

{

qsort(l,1,n); //第一个作为枢轴，从第一个排到第 n 个

}

int main()

{

int a[11]={0,2,32,43,23,45,36,57,14,27,39};

int value=0;//将最小差的值赋值给 value

for (int b=1;b<11;b++)

cout<<a[b]<<' ';

cout<<endl;

quicksort(a,11);

for(int i=0;i!=9;++i)

{

if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) )

value=a[i+1]-a[i];

else

value=a[i+2]-a[i+1];

}

cout<<value<<endl;

return 0;

}

4．设数组 a[n]中的元素均不相等，设计算法找出 a[n]中一个既不是最大也不是最小的

元素，并说明最坏情况下的比较次数。要求分别给出伪代码和 C++描述。

#include<iostream>

using namespace std;

int main()

{

int a[]={1,2,3,6,4,9,0};

int mid_value=0;//将“既不是最大也不是最小的元素”的值赋值给它

for(int i=0;i!=4;++i)

{

if(a[i+1]>a[i]&&a[i+1]<a[i+2])

{

mid_value=a[i+1];

cout<<mid_value<<endl;

break;

}

else if(a[i+1]<a[i]&&a[i+1]>a[i+2])

{

mid_value=a[i+1];

cout<<mid_value<<endl;

break;

}

}//for

return 0;

}

5. 编写程序，求 n 至少为多大时，n 个“1”组成的整数能被 2013 整除。

#include<iostream>

using namespace std;

int main()

{

double value=0;

for(int n=1;n<=10000 ;++n)

{

value=value*10+1;

if(value%2013==0)

{

cout<<"n 至少为:"<<n<<endl;

break;

}

}//for

return 0;

}

6. 计算 π 值的问题能精确求解吗？编写程序，求解满足给定精度要求的 π 值

#include <iostream>

using namespace std;

int main ()

{

double a,b;

double arctan(double x);//声明

a = 16.0*arctan(1/5.0);

b = 4.0*arctan(1/239);

cout << "PI=" << a-b << endl;

return 0；

}

double arctan(double x)

{

int i=0;

double r=0,e,f,sqr;//定义四个变量初

sqr = x*x;

e = x;

while (e/i>1e-15)//定义精度范围

{

f = e/i;//f 是每次 r 需要叠加的方程

r = (i%4==1)?r+f:r-f;

e = e*sqr;//e 每次乘于 x 的平方

i+=2;//i 每次加 2

}//while

return r;

}

7. 圣经上说：神 6 天创造天地万有，第 7 日安歇。为什么是 6 天呢？任何一个自然数的

因数中都有 1 和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的

真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此 6 是完美数。神 6

天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数

#include<iostream>

using namespace std;

int main()

{

int value, k=1;

cin>>value;

for (int i = 2;i!=value;++i)

{

while (value % i == 0 )

{

k+=i;//k 为该自然数所有因子之和

value = value/ i;

}

}//for

if(k==value)

cout<<"该自然数是完美数"<<endl;

else

cout<<"该自然数不是完美数"<<endl;

return 0;

}

8. 有 4 个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，

并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后

必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用 1 分钟，乙过桥

要用 2 分钟，丙过桥要用 5 分钟，丁过桥要用 10 分钟，显然，两个人走路的速度等于其中

较慢那个人的速度，问题是他们全部过桥最少要用多长时间？

剩余40页未读，继续阅读

评论收藏

内容反馈

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

随风浪仔

粉丝: 709
资源: 2889

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

算法设计与分析(第2版)-王红梅-胡明-习题答案.doc

算法设计与分析(第2版)-王红梅-胡明-习题答案

算法设计与分析第2版王红梅胡明习题答案.doc

算法设计与分析-王红梅

算法设计与分析 王红梅

算法设计与分析（第二版）王红梅，胡明 第一章课后答案

计算机算法设计和分析习题及答案解析.pdf

算法设计与分析&#40;第2版&#41;-王红梅-胡明-习题答案.doc

算法设计与分析基础课后答案

算法设计与分析(第2版) 王红梅 胡明 习题.pdf

计算机算法设计与分析(第3版)C++版和课后答案

C++版数据结构王红梅胡明王涛编著+习题答案

算法设计与分析（第三版）课后答案

数据结构（C++版）（第二版--王红梅）所有课件

数据结构（C++版）王红梅胡明王涛编著+习题答案

算法设计与分析 王红梅 第三版 PPT

算法设计与分析 王红梅 第二 算法设计基础PPT学习教案.pptx

算法设计与分析（王红梅）

数据结构C++版王红梅版课后答案khdaw.doc

数据结构 C++ 版 （第2版） 王红梅等 扫描版

相关实用应用程序（Windows可用）

2023年各高校录取分数线

李飞飞自传 我看见的世界 The World I see

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

智联招聘：2024年大学生就业力调研报告.pdf

4个亲测好用的ChatGPT4渠道

学术海报模板+论文科研+研究生

最新资源

算法设计与分析王红梅

算法设计与分析（第二版）王红梅，胡明第一章课后答案

算法设计与分析(第2版)-王红梅-胡明-习题答案.doc

算法设计与分析(第2版) 王红梅胡明习题.pdf

算法设计与分析王红梅第三版 PPT

算法设计与分析王红梅第二算法设计基础PPT学习教案.pptx

数据结构 C++ 版（第2版）王红梅等扫描版

李飞飞自传我看见的世界 The World I see