1.二分查找
描述
给定一个单调递增的整数序列,问某个整数是否在序列中。
输入
第一行为一个整数n,表示序列中整数的个数;第二行为n(n不超过10000)个整数;第三行为一个整数m(m不超过50000),表示查询的个数;接下来m行每行一个整数k。
输出
每个查询的输出占一行,如果k在序列中,输出Yes,否则输出No。
输入样例
5
1 3 4 7 11
3
3
6
9
输出样例
Yes
No
No
思路:
方法一:
按照题目要求进行二分查找,由于a[]是单增数列,所以对于每一个输入查询x,我们先设置左边界l=1,有边界r=n,ans储存可能的位置,进行二分查找,每一次二分查找时mid=(l+r)/2。如果a[mid]>=x,说明如果存在x,那么x一定在左边界(包括mid),那么此时r=mid-1,ans=mid;如果a[mid]<x,则说明x一定在有边界。二分查找完之后,要验证a[ans]是否等于x,因为二分只是由于它是有序序列进行二分,不断查找与x最接近的数字,但它不一定能够是x。
这个方法时间复杂度为O(nlogn).
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=50000+50; int n,a[maxn],m; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; cin>>m; while(m--){ int x; cin>>x; int l=1,r=n,ans=0; while(l<=r){ int mid=(l+r)/2; if(a[mid]>=x){ r=mid-1; ans=mid; } else{ l=mid+1; } } if(a[ans]==x){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } return 0; }
方法二:
题目要求很明确,就是问x是否在a[]中存在,那就把a[]中出现过的数字进行标记就可以了,这里对 a[]中的每一个数字的范围解释不够清楚,所以我们可以用map进行映射处理。当然其实也可以vis[]数组进行标记,vis[]大小设置为5e5,这样让vis[a[i]]=1,然后查询vis[x]是否等于1就可以了,或者用map标记方法也一样。这种方法的时间复杂度O(n)(直接数组标记)或者O(nlogn)(map)。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<map> using namespace std; const int maxn=50000+50; map<int,int>mp; int n,a[maxn],m; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]=1; cin>>m; while(m--){ int x; cin>>x; if(mp[x]==1){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } }
2.求解投骰子游戏问题
问题描述:玩家根据骰子的点数决定走的步数,即骰子点数为1时可以走一步,点数为2时可以走两步,点数为n时可以走n步。求玩家走到第n步(n≤骰子最大点数且投骰子方法唯一)时总共有多少种投骰子的方法。
输入描述:输入包括一个整数n(1≤n≤6)。
输出描述:输出一个整数,表示投骰子的方法数。
输入样例:6
输出样例:32
思路:
方法一:
看到这个题的第一个思路是用递推/动态规划。很容易看出来对于状态i(当前走到第i步)可以由状态0,1,…,i-1得到(即走i步,走i-1步,…,走1步),设dp[0]=1(即处于原始位置的方式只有一种),那么dp[i]=dp[i-1]+dp[i-2]+…+dp[0].所以n^ 2枚举即可,当然为了时候的优化,我们还可以进行前缀和优化(即每一次得到dp[i-1]都在pre之中,对于dp[i+1]我们就可以O(1)求得),当然这里n<=6,就不必这么复杂了。所以写了一个时间复杂度为O(n^2)的代码。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=20; int n,dp[maxn]; int main(){ cin>>n; dp[0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=i-1;j++){ dp[i]+=dp[j]; } } cout<<dp[n]<<endl; return 0; }
运行结果:
方法二:
老师出这个题应该是为了考察dfs,所以这样写一下dfs的方法:
对于x,与方法一的解释一样,它肯定是由0,1,…,x-1得到的,所以我们再dfs求走到第0,1,…,x-1步的方法,dfs的边界设置为 if(x==0)return 1;这样也是可以求得结果的,只是时间复杂度是指数级别。但是如果我们进行记忆化搜索,即用dp[]进行记录每一个状态的答案,一旦存在就不再dfs,这样的时间复杂度可以优化到O(n^2).
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int dfs(int x){ if(x==0)return 1; int res=0; for(int i=0;i<=x-1;i++)res+=dfs(i); return res; } int main(){ cin>>n; cout<<dfs(n)<<endl; return 0; }
3.0-1背包
描述
需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。
输入
多个测例,每个测例的输入占三行。第一行两个整数:n(n<=10)和c,第二行n个整数分别是w1到wn,第三行n个整数分别是p1到pn。n 和 c 都等于零标志输入结束。
输出
每个测例的输出占一行,输出一个整数,即最佳装载的总价值。
输入样例
1 2
1
1
2 3
2 2
3 4
0 0
输出样例
1
4
思路:
方法一:
0-1背包的裸题,那就可以直接写一个01背包的动态转移方程:dp[j]=max(dp[j],dp[j-w[i]]+p[i])。dp[j]的意思是:当背包已装j的重量的物品时的最大价值。那么它可以由背包已装j-w[i]时最大的价值进行转移,即由dp[j-w[i]]+p[i]得到。注意每一次要将dp[]设置为0,因为背包此时无价值。当状态方程枚举结束后,我们再从 dp[]数组中找一遍,求得答案maxx=max{dp[i]}(i from 0 to c),输出答案maxx。这种动态规划的方法的时间复杂度为O(n^2).
ps:0-1背包也可以写成二维dp[][],只是这样写成滚动数组可以更加节省空间。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn= 2000+50; int n,c,w[maxn],dp[maxn],p[maxn]; int main(){ int i,j; while(1){ scanf("%d%d",&n,&c); if(n==0&&c==0)break; for(i=1;i<=n;i++)cin>>w[i]; for(i=1;i<=n;i++)cin>>p[i]; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++){ for(j=c;j>=1;j--){ if(j-w[i]>=0&&dp[j]<dp[j-w[i]]+p[i]){ dp[j]=dp[j-w[i]]+p[i]; } } } int maxx=0; for(i=0;i<=c;i++) if(maxx<dp[i]) maxx=dp[i]; cout<<maxx<<endl; } return 0; }
方法二:
除了直接写0-1背包的动态转移方程,还可以直接写dfs,每一个背包无非就是取和不取两个状态,如果要取则要求背包容量 res>=w[now]。分别用ans1,ans2表示取当前物品,不取当前物品的最大价值,dfs返回max(ans1,ans2),dfs的终止条件是now ==n+1。时间复杂度(2^n)。
ps:方法二相较于方法一思维上更加简单,容易想到,但是代码就相对麻烦,并且时间复杂度不够优秀,当然如果加上记忆化搜索后时间复杂度和动态规划是相当的。我个人更喜欢方法一。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn= 2000+50; int n,c,w[maxn],p[maxn]; int dfs(int now,int res){ if(now==n+1)return 0; int ans1=0,ans2=0; if(res>=w[now]){ ans1=dfs(now+1,res-w[now])+p[now]; } ans2=dfs(now+1,res); if(ans1>=ans2)return ans1; return ans2; } int main(){ int i,j; while(1){ scanf("%d%d",&n,&c); if(n==0&&c==0)break; for(i=1;i<=n;i++)cin>>w[i]; for(i=1;i<=n;i++)cin>>p[i]; cout<<dfs(1,c)<<endl; } return 0; }
4.求解组合问题
编写一个实验程序,采用回溯法输出自然数1~n中任取r个数的所有组合。
思路:
用回溯法求组合,n个数字选r个,每一个数字有两种选择,要么选,要么不选。dfs(int now)表示当前的决策数字是now,则dfs的边界条件是now=n+1。对于数字now,可以选择,也可以不选择。选择的话a[++a[0]]=now,a[0]记录当前选择的数的数量,回溯的时候记得a[0]–,再进行不选择now的dfs搜索。当now==n+1的时候表明当前已经选择完了,如果a[0]==r,则当前的选择组合刚好是满足条件的,输出即可。时间复杂度O(2^n)
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=100+50; int n,r,a[maxn]; void dfs(int now){ if(now==n+1){ if(a[0]==r){ for(int i=1;i<=a[0];i++)cout<<a[i]<<' ';cout<<endl; } return ; } a[++a[0]]=now; dfs(now+1); a[0]--; dfs(now+1); } int main(){ cin>>n>>r; dfs(1); return 0; }
5.最小重量机
设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设 wij 是从供应商j处购得的部件 i 的重量, cij 是相应的价格。试设计一个算法,给出总价格不超过 c 的最小重量机器设计。
输入:第一行3个整数n,m,cost,接下来n行输入wij (每行m个整数),最后n行输入cij (每行m个整数),这里n>=1, m<=100.
输出:第一行包括n个整数,表示每个对应的供应商编号,第2行为对应的重量。
输入样例:
337
123
321
232
123
542
212
输出样例:
131
4
思路:
这里用dfs进行搜索,每找到一个符合条件的情况,就更新bestw和x[]。bestw储存最小的重量,x[i]表示部件i所对应的供应商,nowx[i]表示dfs过程中部件i选择的供应商。w[i][j] 表示从供应商j处购得的部件i的重量 ,c[i][j]表示相应的价格。dfs(int now,int noww,int nowp)表示搜索第now个部件时的当前重量为noww,耗费nowp,对于第now个物品它有m个供应商可以选择,当nowp+c[now][i]<=cost时则符合条件可以进行dfs(now+1,noww+w[now][i],nowp+c[now][i]);dfs的边界条件时now==n+1,此时如果bestw>noww,则要更新bestw,以及x[]。最后输出bestw和x[].
ps:如果PE的话,把最后的空格去掉(输出x[]的时候,x[n]后面不要跟空格),并且加上printf("n").
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=200+50; int n,m,cost,w[maxn][maxn],c[maxn][maxn],bestw=0x3f3f3f3f,nowx[maxn],x[maxn]; void dfs(int now,int noww,int nowp){ int i,j; if(now==n+1){ if(bestw>noww){ bestw=noww; for(i=1;i<=n;i++)x[i]=nowx[i]; } return ; } for(i=1;i<=m;i++){ if(nowp+c[now][i]<=cost){ nowx[now]=i; dfs(now+1,noww+w[now][i],nowp+c[now][i]); } } } int main(){ cin>>n>>m>>cost; int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>w[i][j]; for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>c[i][j]; dfs(1,0,0); for(i=1;i<=n;i++){ cout<<x[i]; if(i!=n)cout<<' '; } cout<<endl; cout<<bestw<<endl; return 0; }
6.最长公共子序列
描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1, x2,…, xm>,则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>,使得对于所有j=1,2,…,k有:
Xij = Zj
如果一个序列S即是A的子序列又是B的子序列,则称S是A、B的公共子序列。
求A、B所有公共子序列中最长的序列的长度。
输入
输入共两行,每行一个由字母和数字组成的字符串,代表序列A、B。A、B的长度不超过200个字符。
输出
一个整数,表示最长各个子序列的长度。
格式:printf("%dn");
输入样例
programming
contest
输出样例
2
思路:
像LCS这样的问题,它具有重叠子问题的性质,因此:用递归来求解就太不划算了。因为采用递归,它重复地求解了子问题。采用动态规划时,并不需要去一 一 计算那些重叠了的子问题 。对于**dp[i][j]**表示 (s1,s2…si) 和 (t1,t2…tj) 的最长公共子序列的长度 。
当i== 0|| j== 0 时,dp[i][j]=0;
当i,j>0,si==tj时, dp[i][j]=dp[i-1][j-1]+1;
当i,j>0,si!=tj时,dp[i][j]=max{dp[i][j-1],dp[i-1][j]};
时间复杂度:
由于只需要填一个m行n列的二维数组,其中m代表第一个字符串长度,n代表第二个字符串长度
所以时间复杂度为O(m*n)
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=1000+50; char s[maxn],t[maxn];int lens,lent,dp[maxn][maxn]; int max(int x,int y){ if(x>y)return x; return y; } int main(){ scanf("%s%s",s+1,t+1); lens=strlen(s+1); lent=strlen(t+1); for(int i=1;i<=lens;i++){ for(int j=1;j<=lent;j++){ if(s[i]==t[j]){ dp[i][j]=dp[i-1][j-1]+1; } else{ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } printf("%dn",dp[lens][lent]); return 0; }
ps:这个NOJ就离谱,我写成maxn=1e3+50,运行时错误,刷屏了一页,最后才发现编译器无法识别1e3,这编译器是有多垃圾???
7.活动安排问题
问题:有n个活动的集合A={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。
求解:安排尽量多项活动在该场地进行,即求A的最大相容子集。
设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下:
将此表数据作为实现该算法的测试数据。
i 1 2 3 4 5 6 7 8 9 10 11
s[i] 1 3 0 5 3 5 6 8 8 2 12
f[i] 4 5 6 7 8 9 10 11 12 13 14
思路:
方法一:
题意很明显希望参加的活动数目尽量多。对于活动安排问题可以采取动态规划的策略:
首先将活动的结束时间按照第一关键字排序(由小到大),再将活动的开始时间作为第二关键字排序(由小到大)
定义dp[i]表示在前i场比赛中最多可以参加几场比赛,
由此得出方程:dp[i]=max(dp[i-1],dp[temp]+1);
temp指从dp[i-1]向前找到的第一个允许参加第i场活动的活动编号,由它推导出dp[i]=dp[temp]+1;
由于每次循环时都向前找一次temp会浪费太多时间,又因为活动开始或结束时间是单调递增的,
故可以令temp在循环时逐步递增,这样时间复杂度就降到了O(n).
这里只是讲解一下动态规划的想法。就不写代码了,动态规划的代码和下面的贪心方法相似。只是这种动态规划的思路是基于贪心的思想来实现的。
方法二:
这个问题可以抽象为在一个数轴上有n条线段,现要选取其中k条线段使得这k条线段两两没有重合部分,问最大的k为多少。
最左边的线段放什么最好?
显然放右端点最靠左的线段最好,从左向右放,右端点越小妨碍越少。
其他线段放置按右端点排序,贪心放置线段,即能放就放。
以上两种方法的时间复杂度都是O(nlogn),快速排序的时间复杂度是O(nlogn),而动态规划或者贪心执行更新策略的时间复杂度是O(n).
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=2e3+50; int n; struct Node{ int s,f; }a[maxn]; bool cmp(Node x,Node y){ if(x.f==y.f)return x.s<y.s; return x.f<y.f; } int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i].s>>a[i].f; sort(a+1,a+1+n,cmp); int ans=1,now=1,opt=2; while(opt<=n){ if(a[opt].s>=a[now].f){ ans++; now=opt; } opt++; } cout<<ans<<endl; return 0; }
最后
以上就是贤惠高跟鞋最近收集整理的关于NWPU-算法设计理论作业1.二分查找2.求解投骰子游戏问题3.0-1背包4.求解组合问题5.最小重量机6.最长公共子序列7.活动安排问题的全部内容,更多相关NWPU-算法设计理论作业1内容请搜索靠谱客的其他文章。
发表评论 取消回复