算法设计与分析课后总结-创新互联
- 算法设计与分析
- 第1章 算法设计基础
- 课后习题
- 第二章算法分析基础
- 课后习题
- 1、考虑下面算法，回答下列问题，算法完成什么功能？算法的基本语句时什么？基本语句执行了多少次？
- 2、分析以下程序段中基本语句的执行次数，要求列出计算公式
- 3、使用递归扩展技术求解下列公式
- 第三章 蛮力法
- 课后习题
- 1、设计算法，在数组r[n]中删除所有元素值为x的元素，要求时间复杂性为$O(n)$,空间复杂性为$O(1)$
- 2、设计算法，将数组r[n]中删除重复元素，要求移动次数较少并使剩余元素的相对次序保持不变
- 3、设表$A=\{a_1,a_2,...,a_n\}$,将A拆成B和C两个表，使A中值>=0的元素存入表B，值小于<0的元素存入表C，不外设空间，利用A的空间
- 第四章 分治法
- 课后习题
- 1、对于待排序列（5，3，1，9）分别画出归并和快排的递归运行轨迹
- 2、设计分治算法求数组大元素，并分析时间性能
- 3、在有序序列$(r_1,r_2,...,r_n)$中存在需序号$i（1<=i<=n）$使得$r_i=n$，设计一个分治算法找到这个元素
- 4、在一个序列中出现次数最多的元素称为众数，寻找众数
- 第五章 减治法
- 课后习题
- 1、折半查找的递归算法，并分析时间性能
- 2、120硬币问题
- 第六章 动态规划
- 课后习题
- 1、为什么动态规划法需要填表？如何设计表的结构？
- 2、动态规划求0->12最短路径
- 第7章 贪心法
- 课后习题
- 1.贪心法求背包问题，有7个物品，重量分别为（2，3，5，7，1，4，1），对应价值为（10，5，15，7，6，18，3）背包容量W=15，写出求解过程
- 2、 最短链接求TSP
- 3、n个顾客等待问题，使得顾客总等待时间最少
- 4、17/18、11/12埃及分数问题
- 第八章 回溯法
- 课后习题
- 1、回溯法求解三着色问题
- 2、回溯法求解作业问题
- 3、迷宫问题
主要包括课后习题、算法的总结
第1章 算法设计基础 课后习题1、设计算法求数组的相差最小的两个元素
思路：快排+顺序遍历
快排函数：
int part(int* r, int low, int hight)
{int i = low, j = hight, pivot = r[low];
while (i< j)
{while (ipivot) j--;
if (i< j) swap(r[i++], r[j]);
while (i< j && r[i]<= pivot) i++;
if (i< j) swap(r[i], r[j--]);
}
return i;
}
void Quicksort(int* r, int low, int hight)
{int mid;
if (low< hight)
{mid = part(r, low, hight); // 返回基准元素位置
Quicksort(r, low, mid - 1); // 左区间递归快速排序
Quicksort(r, mid+1, hight); // 右区间递归快速排序
}
} 相差最小值的函数:
int Min(int *r,int n)
{Quicksort(r,0,n-1);
int min=MAX;
for(int i=1;iif((a[i]-a[i-1]) 2、设计算法找出数组a[n]中即不是大，也不是最小的元素
思想：找出3个不相同的数，在三个数中找到中间值即可
int mid(int a,int b,int c)//找三个数的中间值
{if(a>b){if(b>c)return b;
else if(a>c)return c;
else return a;
}
else{if(a>c)return a;
else if(b>c)return c;
else return b;
}
}
int mid_find(int *r,int n)//找出三个不同的数
{int a=r[0];
int i=1;
while(i3、n至少为多大时，n个1组成的整数能被2013整除
这个题我写着有那么亿丢丢缺点，long long 范围里的数都不能被2013整除
大整数的话，写着又很麻烦。如果有好的想法，欢迎探讨
int main()
{long long n=11111;
while(n%2013){n*=10;
n+=1;
}
cout<（1）
int Stery(int n)
{int S=0;
for(int i=1;i<=n;i++)
S+=i*i;
return S;
}完成功能：计算
∑
i
=
1
n
i
2
\sum_{i=1}^n i^2
∑i=1ni2
基本语句：S+=i*i;
算法复杂度：
O
(
n
)
O(n)
O(n)
(2)
int Q(int n)
{if(n==1)
return 1;
else
return Q(n-1)+2*n-1;
}完成功能：
∑
i
=
1
n
(
2
n
−
1
)
=
n
2
\sum_{i=1}^n(2n-1)=n^2
∑i=1n(2n−1)=n2
基础语句：2*n-1
时间复杂度：
O
(
n
)
O(n)
O(n)
(1)
for(i=1;i<=n;i++)
if(2*i<=n)
for(j=2*i;j<=n;j++)
y+=i*j;基础语句：y+=i*j
执行次数：
∑
i
=
1
n
/
2
(
n
−
2
i
)
=
n
(
n
−
2
)
4
\sum_{i=1}^{n/2}(n-2i)=\frac{n(n-2)}{4}
∑i=1n/2(n−2i)=4n(n−2)
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
(2)
m=0;
for(i=1;i<=n;i++)
for(j=1;j<=2*i;j++)
m+=1;基础语句：m+=1
执行次数：
∑
i
=
1
n
2
i
=
n
(
n
+
1
)
\sum_{i=1}^n2i=n(n+1)
∑i=1n2i=n(n+1)
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
(1)
T
(
n
)
=
{
4
n
=
1
3
T
(
n
−
1
)
n
>
1
T(n) = \begin{cases} 4 &n=1 \\ 3T(n-1) & n>1 \\ \end{cases}
T(n)={43T(n−1)n=1n>1
解：
T
(
n
)
=
3
T
(
n
−
1
)
=
.
.
.
=
3
n
−
1
T
(
1
)
=
4
×
3
n
−
1
T(n)=3T(n-1)=...=3^{n-1}T(1)=4×3^{n-1}
T(n)=3T(n−1)=...=3n−1T(1)=4×3n−1
(2)
T
(
n
)
=
{
1
n
=
1
2
T
(
n
/
3
)
+
n
n
>
1
T(n)= \begin{cases} 1 &n=1\\ 2T(n/3)+n &n>1\\ \end{cases}
T(n)={12T(n/3)+nn=1n>1
解：令
n
=
3
k
n=3^k
n=3k
T
(
n
)
=
2
T
(
n
/
3
)
+
n
=
2
(
2
T
(
n
/
3
2
)
+
n
/
3
)
+
n
=
.
.
.
=
2
k
∑
i
=
0
k
(
3
k
/
2
i
)
T(n)=2T(n/3)+n=2(2T(n/3^2)+n/3)+n=...=2^k\sum_{i=0}^k(3^k/2^i)
T(n)=2T(n/3)+n=2(2T(n/32)+n/3)+n=...=2k∑i=0k(3k/2i)
void dlt(int r*,int n,int x)
{int j=0;
for(int i=0;iif(r[i]!=x)
{ r[j]=r[i];
j++;
]
}
} 算法思想：双重循环找重复值，将重复元素设置为固定值flag，再用上一题的代码删除即可
void dlt2(int r*,int n)
{flag=-1;
for(int i=0;iif(i==flag)continue;
for(int j=i+1;j++)
{ if(a[i]==a[j])
a[j]=flag;
}
}
dlt(r,flag);
} 算法思想：将A分为左边和右边，左边的数大于0，右边的数小于0即可
int divorce(int A*,int n)
{int i=0,j=n-1;
while(iwhile(A[i]>=0&&i 归并：
划分阶段：
(5,3,1,9)
(5,3),(1,9)
(5),(3),(1),(9)
归并阶段：
(3,5),(1,9)
(1,3,5,9）
快排：
（5，3，1，9）
5为基准点，将1与5交换
（1，3）5（9）
（1，3，5，9）
int Max(int *A,int low,int hight)
{if(low>hight)
return -1;
else if(low==hight)return A[low];
int mid=(low+hight)/2;
return max(Max(A,low,mid),Max(A,mid+1,hight));
}算法复杂度： O ( n ) O(n) O(n)
3、在有序序列 ( r 1 , r 2 , . . . , r n ) (r_1,r_2,...,r_n) (r1,r2,...,rn)中存在需序号 i （ 1 < = i < = n ） i（1<=i<=n） i（1<=i<=n）使得 r i = n r_i=n ri=n，设计一个分治算法找到这个元素int find(int *A,int low,int height)
{if(low>hight)
return -1;
if(low==height)
{if(A[low]==low) return low;
else return -1;
}
int mid=(low+hight)/2;
if(A[mid]=mid)
{return mid;
}
else if(A[mid]>mid)
return find(A,low,mid-1);
else
return find(A,mid+1,height);
}算法思想：先快排，再遍历一遍技术，算法复杂度为
O
(
n
l
o
g
n
+
n
)
=
O
(
n
l
o
g
n
)
O(nlogn+n)=O(nlogn)
O(nlogn+n)=O(nlogn)
快排函数：
int part(int* r, int low, int hight)
{int i = low, j = hight, pivot = r[low];
while (i< j)
{while (ipivot) j--;
if (i< j) swap(r[i++], r[j]);
while (i< j && r[i]<= pivot) i++;
if (i< j) swap(r[i], r[j--]);
}
return i;
}
void Quicksort(int* r, int low, int hight)
{int mid;
if (low< hight)
{mid = part(r, low, hight); // 返回基准元素位置
Quicksort(r, low, mid - 1); // 左区间递归快速排序
Quicksort(r, mid+1, hight); // 右区间递归快速排序
}
} 查找众数函数
int mode(int A*,int n)
{Quicksort(A,0,n-1);
int Max=0;
for(int i=0;iint t=a[i];
int num=0;
while(i int divfind(int *A,int low,int hight,int x)
{if(low>height)
return false;
mid=(low+height)/2;
if(A[mid]==x)
return mid;
else if(A[mid]>x)
return divfind(A,low,mid-1);
else
return divfind(A,mid+1,height);
}时间复杂度 O ( l o g 2 n ) O(log_2n) O(log2n)
2、120硬币问题我没看懂那个算法，有看懂的大佬麻烦讲一下，比心~
以下为硬币算法的链接：小球称重
动态规划本身是空间换时间，存在表格里，可以减少相同的计算，大大缩短计算时间
表的结构：
一般状态量为表的行
决策量为表的列
解题思路：贪心的本质为优先选择单位价值最重的
根据单位价值进行排序得：
| 物品编号 | 重量 | 价值 | 单位价值 |
|---|---|---|---|
| 5 | 1 | 6 | 6 |
| 1 | 2 | 10 | 5 |
| 6 | 4 | 18 | 4.5 |
| 3 | 5 | 15 | 3 |
| 7 | 1 | 3 | 3 |
| 2 | 3 | 5 | 1.7 |
| 4 | 7 | 7 | 1 |
先装5号物品背包已装容量为1，价值为6
再装1号物品背包已装容量为3，价值为16
装6号物品背包已装容量7，价值为34
装3号物品背包已装容量12，价值为49
装7号物品背包已装容量13，价值为52
装2号物品背包已装容量16>15,结束
最优解为{1，0，1，0，1，1，1}
#include#include#includeusing namespace std;
//查找最小边函数 Search
pairSearch(int **A,int N,int *flag,int **AF) {//查找最小边
int min=10e5,a=0,b=0;
for(int i=0; ifor(int j=0; jif(!AF[i][j]&&flag[i]<2&&flag[j]<2&& A[i][j]//如果这条边没有走过，两边的城市没有同时有两个被走过的边
a=i;
b=j;
min=A[i][j];//依次比较
}
}
}
flag[a]++;
flag[b]++;
AF[a][b]=1;
return pair(a,b);
}
//TSP2
int TSP2(int **A,int N,int *flag,int **AF) {int tsp=0,i,j,k;
for(k=0; k//选择N次最短边
paira=Search(A,N,flag,AF);
tsp+=A[a.first][a.second];//每次加入最增的最短边
}
return tsp;
}
int main()
{ //N初始化
int N=5;
//A初始化(城市之间的距离)
int **A=(int **)malloc(N*sizeof(int));
cout<<"输入5个城市之间的距离(0表示城市间不通):"<A[i]=(int*)malloc(N*sizeof(int));
for(int j=0;j cin>>A[i][j];
}
}
//AF初始化，记录边是否走过
int **AF=(int **)malloc(N*sizeof(int));//记是否边走过，初始值设为0，走过设为1
for(int i=0;iAF[i]=(int*)malloc(N*sizeof(int));
for(int j=0;j AF[i][j]=0;
}
}
//flag初始化,记录城市是否走过
int *flag=(int *)malloc(N*sizeof(int));//标记是否城市走过，初始值设为0，走进去又走出来成为2
for(int i=0;iflag[i]=0;
}
cout<<"最短路径长度：";
cout< 算法思想：快排一下，时间最少的排前面。
4、17/18、11/12埃及分数问题埃及分数流程：
E=B/A+1;
输出1/E;
A=AE-B;
B=E;
消除A，B大公约数;
直到A=1，输出1/B；
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章名称：算法设计与分析课后总结-创新互联
网页URL：http://6mz.cn/article/cddsjc.html