没有合适的资源?快使用搜索试试~ 我知道了~
首页《计算机常用算法解析与习题解答》
《计算机常用算法解析与习题解答》
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 49 浏览量
更新于2024-07-04
收藏 1.97MB PDF 举报
该资源是《计算机常用算法与程序的设计案例教程》的习题解答,主要涉及算法的设计与分析,包括分数分解算法和程序段的时间复杂度计算。 在习题1-1中,讨论的是一个分数分解成埃及分数的问题。算法的核心是找到小于给定分数a/b的最大埃及分数1/c,并通过迭代不断减少分数的分子,直至分解完毕。算法的伪代码描述了一个while循环,当找到的分母c超过预设阈值时退出,否则继续进行分解。在这个过程中,通过更新a和b的值来寻找下一个合适的分母。 习题1-2考察了对不同程序段的时间复杂度分析。第一段程序是一个双层嵌套循环,外层循环是k,内层循环是j,内层循环的次数随着外层循环的增加而线性减少。由于内层循环的总执行次数是n(n+1)/2,因此时间复杂度是O(n)。第二段程序也包含一个双层嵌套循环,但内层循环的次数是k/2,对于奇数n和偶数n分别给出了执行频数的表达式,无论哪种情况,时间复杂度也是O(n)。第三段程序有一个外层循环和一个内层循环,内层循环的次数与外层循环的乘积有关,导致时间复杂度为O((n+1)!), 显示了显著的指数增长。 这些习题解答强调了在计算机科学中,理解算法的时间复杂度是非常重要的,因为它直接影响到程序的效率。在设计算法时,通常会追求最优的时间复杂度,以便在处理大规模数据时能保持良好的性能。同时,习题还展示了如何将数学理论应用到实际编程问题中,如分数分解和时间复杂度计算,这些都是计算机科学教育中的基础内容。通过这样的习题,学习者可以提升自己在算法设计和分析方面的技能。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/85390224/bgd.jpg)
差。若某相邻的两素数m,f 之差大于 n,即 m-f>n,则区间[f+1,f+n]中的 n 个数为最小的连
续 n 个合数。
应用试商法求指定区间[c,d](约定起始数 c=3,d=c+10000)上的所有素数。求出该区间
内的一个素数m,设前一个素数为f,•判别:
若 m-f>n,则输出结果[f+1,f+n]后结束;
否则,作赋值f=m,为求下一个素数作准备。
如果在区间[c,d]中没有满足条件的解,则作赋值:c=d+2,d=c+10000,继续试商下去,
直到找出所要求的解。
(2) 程序实现
// 求最小的连续n 个合数
#include <stdio.h>
#include <math.h>
void main()
{ long c,d,f,m,j;
int t,n;
printf(" 求最小的 n 个连续合数.\n");
printf(" 请输入 n:");
scanf("%d",&n);
c=3;d=c+10000;
f=3;
while(1)
{ for(m=c;m<=d;m+=2)
{ for(t=0,j=3;j<=sqrt(m);j+=2)
if(m%j==0) //实施试商
{t=1;break;}
if(t==0 && m-f>n) //满足条件即行输出
{ printf("最小的%d 个连续合数区间为:",n);
printf("[%ld,%ld]。 \n",f+1,f+n);
getch();return;
}
if(t==0) f=m; //每求出一个素数m 后赋值给 f
}
if(m>d)
{c=d+2;d=c+10000;} //每一轮试商后改变c,d 转下一轮
}
}
2-10 和积 9 数字三角形
求解和为给定的正整数s(s≥45)的9 个互不相等的正整数填入9 数字三角形,使三角
. . .
![](https://csdnimg.cn/release/download_crawler_static/85390224/bge.jpg)
形三边上的4 个数字之和相等(s1)且三边上的4 个数字之积也相等(s2)。
图 2-7 9 数字三角形
(1)求解要点。
把和为 s 的 9 个正整数存储于b 数组 b(1),…,b(9)中,分布如下图所示。为避免重复,
不妨约定三角形中数字“下小上大、左小右大”,即 b(1)<b(7)<b(4)且 b(2)<b(3)且 b(6)<b(5)
且 b(9)<b(8)。
图 2-8 b 数组分布示意图
可以根据约定对b(1)、b(7)和 b(4)的值进行循环探索,设置:
b(1)的取值范围为1~(s-21)/3(因其他 6 个数之和至少为21)。
b(7)的取值范围为b(1)+1~(s-28)/2。
b(4)的取值范围为b(7)+1~(s-36)。
同时探索判断步骤如下:
1)若(s+b(1)+b(7)+b(4))%3≠0,则继续探索;否则,记s1=(s+b(1)+b(7)+b(4))/3。
2)根据约定对b(3)、b(5)和 b(8)的值进行探索,设置:
b(3)的取值范围为(s1-b(1)-b(4))/2+1~s1-b(1)-b(4)。
b(5)的取值范围为(s1-b(4)-b(7))/2+1~s1-b(4)-b(7)。
b(8)的取值范围为(s1-b(1)-b(7))/2+1~s1-b(1)-b(7))。
同时根据各边之和为s1,计算出 b(2)、b(6)和 b(9):
b(2)=s1-b(1)-b(4)-b(3)
b(6)=s1-b(4)-b(5)-b(7)
b(9)=s1-b(1)-b(7)-b(8)
3)若 b 数组存在相同正整数,则继续探索。
4)设 s2=b(1)*b(2)*b(3)*b(4),若另两边之积不为s2,则继续探索;否则探索成功,
打印输出结果,接着继续探索直到所有数字组探索完毕为止。
(2)9 数字三角形求解程序设计。
. . .
![](https://csdnimg.cn/release/download_crawler_static/85390224/bgf.jpg)
// 9 数字三角形求解
#include<stdio.h>
#include<math.h>
void main()
{
int k,j,t,s,s1,s2,n,b[10];
printf(" 请输入正整数s:");
scanf("%d",&s);
n=0;
for(b[1]=1;b[1]<=(s-21)/3;b[1]++)
for(b[7]=b[1]+1;b[7]<=(s-28)/2;b[7]++)
for(b[4]=b[7]+1;b[4]<=s-36;b[4]++)
{
if((s+b[1]+b[4]+b[7])%3!=0) continue;
s1=(s+b[1]+b[4]+b[7])/3;
for(b[3]=(s1-b[1]-b[4])/2+1;b[3]<s1-b[1]-b[4];b[3]++)
for(b[5]=(s1-b[4]-b[7])/2+1;b[5]<s1-b[4]-b[7];b[5]++)
for(b[8]=(s1-b[1]-b[7])/2+1;b[8]<s1-b[1]-b[7];b[8]++)
{
b[2]=s1-b[1]-b[4]-b[3];
b[6]=s1-b[4]-b[7]-b[5];
b[9]=s1-b[1]-b[7]-b[8];
t=0;
for(k=1;k<=8;k++)
for(j=k+1;j<=9;j++)
if(b[k]==b[j]) {t=1;k=8;break;}
if(t==1) continue;
s2=b[1]*b[2]*b[3]*b[4];
if(b[4]*b[5]*b[6]*b[7]!=s2) continue;
if(b[1]*b[9]*b[8]*b[7]!=s2) continue;
n++;
printf(" %3d:%2d",n,b[1]);
for(k=2;k<=9;k++)
printf(", %2d",b[k]);
printf(" s1=%d, s2=%d \n",s1,s2);
}
}
printf("共%d 个解。",n);
}
. . .
![](https://csdnimg.cn/release/download_crawler_static/85390224/bg10.jpg)
习题 3
3-1 递推求解b 数列
已知 b 数列定义:
b
1
1, b
2
2, b
n
3b
n 1
b
n 2
(n 2)
递推求 b 数列的第 20 项与前 20 项之和。
解:
#include <stdio.h>
void main()
{ int k,n; long b[3000],s;
printf(" 请输入 n: ");
scanf("%d",&n);
b[1]=1;b[2]=2;s=3;
for(k=3;k<=n;k++)
{ b[k]=3*b[k-1]-b[k-2];
s+=b[k];
}
printf(" b(%d)=%ld \n",n,b[n]);
printf(" s=%ld \n",s);
}
3-2 双关系递推数列
集合 M 定义如下:
1)
1 M
2)
x M 2x 1 M , 3x 1 M
3)再无别的数属于M
试求集合M 元素从小到大排列的第2011 个元素与前2011 个元素之和。
解:(1)设计要点
设 n 个数在数组 m 中,2x+1 与 3x+1 均作为一个队列,从两队列中选一排头(数值较小
者)送入数组m 中。所谓“排头”就是队列中尚未选入m 的最小的数(下标)。这里用 p2 表
示 2x+1 这一列的排头的下标,用p3 表示 3x+1 这一列的排头的下标。
if(2
*
m(p2)<3
*
m(p3))
{ m(i)=2
*
m(p2)+1;p2++;}
if(2
*
m(p2)>3
*
m(p3))
. . .
剩余76页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
a66889999
- 粉丝: 40
- 资源: 1万+
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-2.8b825a4e.png)
电子书特权
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)