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).

代码：

#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)。

代码：

#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)的代码。

代码：

#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).

代码：

#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[][]，只是这样写成滚动数组可以更加节省空间。

代码：

#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:方法二相较于方法一思维上更加简单，容易想到，但是代码就相对麻烦，并且时间复杂度不够优秀，当然如果加上记忆化搜索后时间复杂度和动态规划是相当的。我个人更喜欢方法一。

代码：

#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)

代码：

#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").

代码：

#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）

代码：

#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).

代码：

#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.二分查找2.求解投骰子游戏问题3.0-1背包4.求解组合问题5.最小重量机6.最长公共子序列7.活动安排问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。