当前位置：首页 > ops >正文

2025年春季学期《算法分析与设计》练习15

ops 2025/6/20 19:47:13

A: 0-1背包问题（回溯法）

B: 递归求解III

C: 挑选奖品

D: HNUCM的批改作文

E: 最小积分

F: 数字迷宫

G: 路径统计

H: HNUCM的情人告白

A: 0-1背包问题（回溯法）

有n个物品，第i个物品重量为wi，价值为vi，现有一背包容量为C，要求把物品装入背包得到最大价值，并且要求出这些选取的物品。要求用回溯法求解。

输入

多组测试数据，请处理到文件尾，一个整数表示物品的数量n，后一行有n个整数，代表价值，再后一行有n个整数，代表重量，最后有一个整数C代表背包容量,1<=n<=15,1<=vi<=30,1<=wi<=30,1<=C<=80。

输出

背包的最大总价值和所选取的物品，如果选取的方案有多种，请输出字典序最小的那种方案，每组测试数据应输出一行，在这里字典序最小的意思是，我们假设存在两种不同方案S,T所能得到的总价值相同且是最大的，对于方案S种选取|S|种物品，方案T选取|T|种物品，对于i=1,2...j-1，我们有si = ti，但sj < tj,则方案的S的字典序比方案T的字典序要小。由于没有使用special judge，所以如果选取得方案是S，请按照从小到大的顺序输出方案S中的物品下标。
样例输入 Copy
5
6 3 6 5 4
2 2 4 6 5
8
样例输出 Copy
15 1 2 3

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
#include <iomanip>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N = 1e5+5;
const int MOD = 998244353;
const int inf = 0x3fffffff;
const int P = 13331;
int n,c;
int m=0;
vector<int> w,v,x,y;
void fun(int h,int ww,int vv){if(ww>c){return;}if(vv>m){m=vv;x=y;}else if(vv==m){if(y<x){x=y;}}for(int i=h;i<n;i++){y.push_back(i+1);fun(i+1,ww+w[i],vv+v[i]);y.pop_back();}
}
void solve(){while(cin>>n){v.resize(n);w.resize(n);for(int i=0;i<n;i++){cin>>v[i];}for(int i=0;i<n;i++){cin>>w[i];}cin>>c;m=0;x.clear();y.clear();fun(0,0,0);cout<<m;for(auto i:x){cout<<" "<<i;}cout<<"\n";}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);//int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

B: 递归求解III

使用递归编写一个程序求如下表达式前n项的计算结果： (n<=100)
1 - 4 + 9 - 16 + 25 - 36 +......
输入n，输出表达式的计算结果。

输入

输入n，n<=100。

输出

输出表达式的计算结果。

样例输入 Copy
1
2
样例输出 Copy
1
-3

#include<stdio.h>
int fun(int n)
{int s;if(n==1)s=n;elseif(n%2==0)s=fun(n-1)-n*n;elses=fun(n-1)+n*n;return s;
}
int main()
{int n;while(~scanf("%d",&n))printf("%d\n",fun(n));return 0;
}

C: 挑选奖品

X星人参加了一档幸运大抽奖节目，凭借无敌好运气中了一等奖。节目组给他准备了一个奖品箱，这个箱子中一共有M个格子，每个格子中只能放一个奖品。
现在一共有N个不同的奖品供X星人挑选，不同的奖品其价值不一定相等。
“贪心的”X星人希望所挑选的奖品的价值和最大，需要你编写一个程序帮他计算出所能得到的最大价值和。

输入

单组输入。
第1行包含两个正整数M和N，分别表示奖品箱中格子的数量和奖品的总数。（1< M<=10^5且1<N<=10^5）
第2行包含N个正整数，分别表示N个奖品的价值，两两之间用空格隔开。

输出

奖品箱中所有奖品的最大价值和。

样例输入 Copy
3 5
1 3 2 6 5
样例输出 Copy
14

#include<stdio.h>
#define ll long long
int a[100005];
void quickSort(int l,int r){if(l>r){return;}int tt=a[l];int i=l;int j=r;int t;while(i!=j){while(i<j&&a[j]<=tt){j--;}while(i<j&&a[i]>=tt){i++;}if(i<j){t=a[i];a[i]=a[j];a[j]=t;}}a[l]=a[i];a[i]=tt;quickSort(l,i-1);quickSort(i+1,r);   
}
int main(){int m,n;scanf("%d%d",&m,&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}quickSort(1,n);ll s=0;for(int i=1;i<=m;i++){s+=a[i];}printf("%lld\n",s);return 0;
}

D: HNUCM的批改作文

HNUCM的小王老师给同学们布置了一道小作文题，要求所有同学同时提交并现场批改。
批改完的同学即可以下课，否则就需要等待老师把自己的作文批改完才能够下课。
交小作文的时间到了，N个同学同时把作文提交给了小王老师，小王老师根据大家写的字数估算了一下批改时间（单位：分钟），现在请你编写一个程序帮助小王老师做一个决策，使得所有同学等待作文批改的平均时间最少，请输出最少平均等待时间（单位：分钟）。

输入

单组输入。
第1行输入一个不超过100的正整数N。
第2行输入N个不超过20的正整数，每一个正整数对应一个同学的作文批改时间（单位：分钟），两个正整数之间用英文空格分隔。

输出

输出所有同学的作文都批改完时的最少平均等待时间（单位：分钟），结果四舍五入保留两位小数。

样例输入 Copy
3
10 5 20
样例输出 Copy
18.33

#include<stdio.h>
#define ll long long
int a[105];
int main(){int n;scanf("%d",&n);double f=0,s=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=0;i<n-1;i++){for(int j=0;j<n-i-1;j++){if(a[j]>a[j+1]){int t=a[j];a[j]=a[j+1];a[j+1]=t;}}}for(int i=0;i<n;i++){s+=a[i];f+=s;}printf("%.2lf",f/n);return 0;
}

E: 最小积分

Kimi和Sunny决定在线组队玩一个数字游戏，该游戏的规则如下：
(1) 游戏系统随机生成两组正整数，每组N个数字，两组正整数可能不一样；
(2) 每个游戏团队两个人，每个人拿其中一组数字；
(3) 每一轮两个人从自己的那组数字中各取出一个数字，将两个数字相乘作为这一轮的积分，取出的数字不能再重复使用；
(4) 一共玩N轮，将每轮的积分求和，得到一个总积分；
(5) 总积分最小的队伍获胜。
现在需要你编写一个程序帮Kimi和Sunny计算出最小积分和。

输入

单组输入。
第1行输入一个正整数N，N不超过100。
第2行输入N个不超过1000的正整数，表示Kimi拿到的数字，两两之间用空格隔开。
第3行输入N个不超过1000的正整数，表示Sunny拿到的数字，两两之间用空格隔开。

输出

输出最小积分和。

样例输入 Copy
3
3 1 2
4 3 5
样例输出 Copy
22

#include<stdio.h>
#define ll long long
int a[105],b[105];
int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=0;i<n;i++){scanf("%d",&b[i]);}for(int i=0;i<n-1;i++){for(int j=0;j<n-i-1;j++){if(a[j]>a[j+1]){int t=a[j];a[j]=a[j+1];a[j+1]=t;}}}for(int i=0;i<n-1;i++){for(int j=0;j<n-i-1;j++){if(b[j]<b[j+1]){int t=b[j];b[j]=b[j+1];b[j+1]=t;}}}int s=0;for(int i=0;i<n;i++){s+=a[i]*b[i];}printf("%d\n",s);return 0;
}

F: 数字迷宫

X星有一个很神秘的数字迷宫。这个迷宫是一个由若干小方格区域组成的矩阵，一共包含M行和N列。每一个小方格中都有一个正整数，表示经过这个方格区域所需要的能量值。
现在小Z从最左边的列任选一个方格作为出发点，每一次只能向右边、右上或右下方向走一格，但不能走出数字迷宫，最终要到达最右边的列。
请你编写一个程序，输出消耗的总能量最少的那条路线所对应的总能量值（总能量值包含起点方格和终点方格所需能量值）。

输入

单组输入。
第1行输入两个正整数M和N，分别表示数字迷宫的行和列，M和N均不超过1000，两者之间用一个英文空格隔开。
接下来M行，每行包含N个正整数，每个正整数对应经过一个小方格区域所需的能量值，每个能量值均不超过100。同一行的两个正整数之间用一个英文空格隔开。

输出

输出一个正整数，表示总能量最少的那条路线所对应的总能量值。

样例输入 Copy
3 3
3 4 1
6 1 8
3 7 2
样例输出 Copy
5

#include<stdio.h>
#define ll long long
int a[1005][1005];
int dp[1005][1005];
int min(int a,int b,int c){int t=a<b?a:b;return t<c?t:c;
}
int mmin(int a,int b){return a<b?a:b;
}
int main(){int m,n;scanf("%d%d",&m,&n);for(int i=0;i<m;i++){for(int j=0;j<n;j++){scanf("%d",&a[i][j]);}}for(int i=0;i<m;i++){dp[i][0]=a[i][0];}for(int j=1;j<n;j++){for(int i=0;i<m;i++){if(i==0){dp[i][j]=a[i][j]+mmin(dp[i][j-1],dp[i+1][j-1]);} else if(i==m-1){dp[i][j]=a[i][j]+mmin(dp[i][j-1],dp[i-1][j-1]);}else{dp[i][j]=a[i][j]+min(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1]);}}}int mm=dp[0][n-1];for(int i=1;i<m;i++){if(dp[i][n-1]<mm){mm=dp[i][n-1];}}printf("%d\n",mm);return 0;
}

G: 路径统计

小Z住在一个建筑物很整齐的矩形小区的左下角，学校在小区右上角。
小Z和学校之间有M条东西向的道路，有N条南北向的道路。小Z的爸爸每天早上开车送他上学，但是这些道路都是单行线，只能朝北走或者朝东走。
由于道路施工，在某个路口现在有一个警示桩，表示此处暂不能通行。
现在告诉你M和N的值，以及警示桩的位置，请你统计从小Z家到学校有多少条不同的路径（答案对1e9+7取模）？
下图是当M=4，N=4，在从左到右第2条南北方向的道路和从上至下第2条东西方向的道路的交叉口有一个警示桩的示意图。

输入

单组输入。
第1行输入两个正整数M和N，分别表示东西向道路和南北向道路的数量，M和N均不超过100，两者之间用英文空格隔开。
第2行输入两个正整数X和Y，表示警示桩的位置，X表示从左到右第X条南北方向的道路，Y表示从上至下第Y条东西方向的道路。（1<=X<=N，1<=Y<=M）

输出

输出从小Z家到学校的不同路径条数（答案对1e9+7取模）。

样例输入 Copy
4 4
2 2
样例输出 Copy
11

#include <iostream>
using namespace std;
const int M = 1e9 + 7;
long long a[105][105];
int main()
{ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);int m, n, x, y;cin >> m >> n >> x >> y;a[m][0] = 1;for (int i = m; i >=1; i--)for (int j = 1; j <= n; j++){if (i == y && j == x)a[i][j] = 0;elsea[i][j] = a[i + 1][j]%M + a[i][j - 1]%M;}cout << a[1][n]%M << endl;return 0;
}

H: HNUCM的情人告白

一年一度的2月14日情人节又到了，HNUCM刚脱单的“码农”小明同学迎来了属于他的第一个情人节。
他想跟她说很多很多“520”，但是害羞的小明不知道如何开口，于是只能把这些“520”隐藏在一个神秘的二维数组中。
这个二维数组包含n行m列，数组中的每一个值都是一个0到9的数字。
寻找“520”的规则如下：
先找到一个数字为5，然后在它的八个方向（上、下、左、右和四个角）上寻找是否有2；如果成功找到2，再在这个2的八个方向上查找是否有0；如果找到0，就构成了一句“520”。不同的5、不同的2、不同的0可以组合成多个不同的“520”。
现在请你编写一个程序，统计在一个输入数组中包含多少个不同的“520”。当然，找到的“520”越多表示小明爱她爱得越深，^_^。如果一个都没有找到，则输出“爱你无法说出口！”。^_^......

输入

单组输入，每个测试样例包含n+1行。
第1行是二维数组的大小n和m，其中n表示数组的行数，m表示数组的列数，n和m均不超过30，两者之间用一个英文空格分开。
第2行到第n+1行，每行包含m个0到9的一位数字。

输出

输入数组中包含的不同的“520”的个数。如果一个都没有找到，则输出“爱你无法说出口！”。

样例输入 Copy
4 6
115211
442301
380021
432157
样例输出 Copy
5

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cmath>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <map>
#define ll long long
#define MM 0x3f3f3f3f
#define pii pair<int, int>
#define pll pair<long long, long long>
using namespace std;
const int N = 1e6 + 5;
const int P = 131;
int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
char a[35][35];
bool b[35][35];
int n,m,sum=0;
string c="520";
void dfs(int x,int y,int s){if(s==3){sum++;return;}for(int i=0;i<8;i++){int xx=x+dx[i];int yy=y+dy[i];if(xx>=0&&xx<n&&yy>=0&&yy<m&&!b[xx][yy]&&a[xx][yy]==c[s]){b[xx][yy]=true;dfs(xx,yy,s+1);b[xx][yy]=false;}}
}
void solve(){cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]=='5'){dfs(i,j,1);}}}if(sum){cout<<sum<<"\n";}else{cout<<"爱你无法说出口！"<<"\n";}
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t=1;//cin >> t;while (t--){solve();}return 0;
}

查看全文

http://www.xdnf.cn/news/13499.html