[ACM实验三]ACM程序设计基础（1）

杰拉斯 | 时间：2012-03-31, Sat | 6,241 views
编程算法　

从实验三开始使用scanf与printf进入输入输出，具体原因详见：[ACM学习心得]关于sync_with_stdio(false);

实验项目：ACM程序设计基础(1)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1．输入年、月、日，计算该日是该年的第n天，输出n。

2．对于大于等于6的偶数，可以表示为2个素数之和，请判断一个数是否是对称数，如果该数为对称数而且是偶数，输出其和等于该数的2个素数。

3．Fire Net问题，要求输出最优值和最优值对应的最优解。

4．附加题：0-1背包问题：有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。物品（1.可以;2.不可）切割出来只是装一部分，求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大，先输入物品数n和背包容量v，然后输入各个物品费用和价值，输出最大价值。

可分割示例：

输入：

3 20 18 25 15 24 10 15
5 20 6 3 2 5 3 8 10 6 7 4

输出：

31.5
21.9

不可分割示例：

输入：

5 100 77 92 22 22 29 87 50 46 99 90
8 200 79 83 58 14 86 54 11 79 28 72 62 52 15 48 68 62

输出：

133
334

1．输入年、月、日，计算该日是该年的第n天，输出n。

#include<stdio.h>
int main(){
	int y, m, d, n, days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};	//每月的天数
	while(scanf("%d%d%d", &y, &m, &d) != EOF){
		n = 0;
		for(int i = 0; i < m - 1; ++i){
			n += days[i];	//加上输入月前所有月份的天数
		}
		n += d;	//加上输入的日期
		if(m > 2 && (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0 ))){
			++n;	//若是闰年，且输入月份大于2月，再加1天
		}
		printf("%d\n", n);
	}
	return 0;
}

2．对于大于等于6的偶数，可以表示为2个素数之和，请判断一个数是否是对称数，如果该数为对称数而且是偶数，输出其和等于该数的2个素数。

#include<stdio.h>
#include<cmath>
bool isSu(int n){
	if(n > 3)	//若小于等于三，必然是素数
		for(int i = 2; i <= sqrt(n); ++i)
			if(n % i == 0)	//从2到该数的平方根，若能整除，则不是素数。
				return false;
	return true;
}
int main(){
	int n, m = 0;
	scanf("%d", &n);
	if(n % 2 == 0 && n >= 6){
		int temp = n;
		while(temp){
			m = m * 10 + temp % 10;
			temp /= 10;
		}	//得出与原数字倒转后的数字
		if(n == m){	//若两数相等，说明是对称数
			for(int i = 1; i <= n / 2; ++i){	//若i是素数，n - i也是素数，则输出。
				if(isSu(i) && isSu(n - i)){
					printf("%d %d\n", i, n - i);
					break;
				}
			}
		}
	}
	return 0;
}

3． Fire Net问题，要求输出最优值和最优值对应的最优解。

比正常的FireNet问题，多了输出最优解的要求，本题只对最优解部分做出解释，具体解题思路详见文章：[ACM_ZOJ_1002]Fire Net

代码如下：

#include<stdio.h>
#include<cmath>
char net[4][5];
char best[4][5];	//用来储存最优解
int max = 0;
bool allow(int n, int row, int col){
	if(net[row][col] == 'X'){
		return false;
	}
	int i;
	for(i = row; i >= 0; --i){
		if(net[i][col] == '@')
			return false;
		else if(net[i][col] == 'X')
			break;
	}
	for(i = col; i >= 0; --i){
		if(net[row][i] == '@')
			return false;
		else if(net[row][i] == 'X')
			break;
	}
	return true;
}
void BackTrack(int n, int k, int num){
	if(k == n * n){
		if(num > max){
			max = num;
			for(int i = 0; i < n; ++i){
				for(int j = 0; j < n; ++j){
					best[i][j] = net[i][j];	//若当前解法最优，则将解法保存进best数组中
				}
				best[i][n] = '\0';
			}
		}
		return;
	}
	int row = k / n, col = k % n;
	if(allow(n, row, col)){
		net[row][col] = '@';
		BackTrack(n, k + 1, num + 1);
		net[row][col] = '.';
	}
	BackTrack(n, k + 1, num);
}
int main(){
	int n, i;
	while(scanf("%d", &n) && n){
		max = 0;
		for(i = 0; i < n; ++i){
			scanf("%s", net[i]);
		}
		BackTrack(n, 0, 0);
		printf("%d\n", max);
		for(i = 0; i < n; ++i){
			printf("%s\n", best[i]);	//输出最优解
		}
	}
	return 0;
}

附加题：

4． 0-1背包问题：有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。物品（1.可以;2.不可）切割出来只是装一部分，求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大，先输入物品数n和背包容量v，然后输入各个物品费用和价值，输出最大价值。

可分割示例：

输入：

3 20 18 25 15 24 10 15
5 20 6 3 2 5 3 8 10 6 7 4

输出：

31.5
21.9

不可分割示例：

输入：

5 100 77 92 22 22 29 87 50 46 99 90
8 200 79 83 58 14 86 54 11 79 28 72 62 52 15 48 68 62

输出：

133
334

可切割（比较简单，直接找性价比最高的不断放入直到放满为止）：

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct goods{
	int c, w;	//自定义结构体，c为体积，w为价值
	goods(int c, int w):c(c),w(w){}
	bool operator < (const goods t) const{
		return (float)w / c > (float)t.w / t.c;
	}	//重载运算符，使其按照性价比降排序
};
int main(){
	int n, i, v;
	double max = 0;
	vector<goods> vec;
	while(scanf("%d%d", &n, &v) != EOF){
		for(i = 0; i < n; ++i){
			int c, w;
			scanf("%d%d", &c, &w);
			vec.push_back(goods(c, w));
		}
		sort(vec.begin(), vec.end());	//排序
		for(i = 0; i < n; ++i){
			if(v - vec[i].c >= 0){	//若当前性价比最高的物品可以全部放入背包中
				v -= vec[i].c;	//背包容量减去该物品的体积
				max += vec[i].w;	//总价值加上该物品的价值
			}else{	//否则只放入一部分，将背包放满
				max += (double)v * vec[i].w / vec[i].c ;	//总价值加上放入的部分物品的价值
				v = 0;	//背包空间全部放满，剩余容量为0
			}
			if(v == 0)	//背包放满，跳出循环
				break;
		}
		printf("%.1lf\n", max);	//输出并保留一位小数
	}
	return 0;
}

不可切割（相对较难，思路与FireNet一样，通过回溯求解）：

#include<stdio.h>
int max = 0;
void BackTrack(int **a, int n, int v, int k, int m){
	if(k == n){	//若已经遍历完所有物品
		if(m > max)	//且当前放置方式的价值大于之前的最大价值
			max = m;	//最大价值等于当前放置方式的价值
		return;
	}
	if(v - a[k][0] >= 0){	//若背包容量足够放第k件物品
		BackTrack(a, n, v - a[k][0], k + 1, m + a[k][1]);	//放入该物品，继续检测下一个物品
	}
	BackTrack(a, n, v, k + 1, m);	//不放入该物品，继续检测下一个物品
}
int main(){
	int n, i, v;
	scanf("%d%d", &n, &v);
	int **a = new int*[n];
	for(i = 0; i < n; ++i){
		a[i] = new int[2];	//两个元素，分别为体积和价值
		scanf("%d%d", &a[i][0], &a[i][1]);
	}
	BackTrack(a, n, v, 0, 0);	//开始递归
	printf("%d\n", max);
	return 0;
}

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客