从实验三开始使用scanf与printf进入输入输出,具体原因详见:[ACM学习心得]关于sync_with_stdio(false);
实验项目:ACM程序设计基础(1)
实验目的:掌握C++程序设计基础。
实验要求:使用VC++6.0实现实验要求。
实验内容:
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.FireNet问题,要求输出最优值和最优值对应的最优解。
比正常的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,然后输入各个物品费用和价值,输出最大价值。
可分割示例:
输入:
320182515241015
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;
float 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 += (float)v * vec[i].w / vec[i].c ; //总价值加上放入的部分物品的价值
v = 0; //背包空间全部放满,剩余容量为0
}
if(v == 0) //背包放满,跳出循环
break;
}
printf("%.1f\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;
}
=======================签 名 档=======================
原文地址(我的博客):http://www.clanfei.com/2012/03/326.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
ACM国际大学生程序设计竞赛基础知识
本资料含 ACM国际大学生程序设计竞赛简介、 程序设计基础、 程序设计简单问题以及 组合数学中的程序设计算法的分析,资料比较全面,为大学生程序竞赛提供了很好的资源
本课件是沈云付老师写的《ACM程序设计竞赛辅导》这本教材的配套课件包括ACM程序设计竞赛简介和程序设计基础、 高精度计算 、数论、 组合数学 、动态规划 、计算几何等
ACM国际大学生程序设计竞赛:知识与入门,是你提高算法思想,锻炼算法实践能力的不二之选!你值得拥有!!
第1章讲解了ACM程序设计入门知识;第2章讲解了C++泛型编程的容器、迭代器和常用算法;第3章讲解了ACM程序设计的基本编程技巧;第4章讲解了50道原版ACM竞赛题的解题思路,并配有C++泛型编程参考答案和题目的中文翻译...
国际程序大学生程序设计竞赛教程和程序设计基础课程设计
ACM国际大学生 程序设计竞赛基础知识
主要用于ACM竞赛,书里面包含了基础算法和较为高级的算法,无论是小白还是大神都者的一看~
推选文档ACM程序设计基础之贪心法PPT.ppt
ACM程序设计基础之贪心法PPT课件.pptx
ACM程序设计竞赛基础教程_俞经善等编.pdf,算法竞赛题解
ACM程序设计基础之贪心法学习教案.pptx
ACM程序设计基础之贪心法PPT学习教案.pptx
ACM程序设计基础之贪心法PPT教学课件.pptx
ACM竞赛,程序设计资料包,包含ppt,经典题目,常用算法,已经一套基础训练题
最新的ACM培新计划和培训内容,包含代码和解析,培养最出色的ACMer
ACM程序设计-基础ACM课件(与“问题”有关文档共30张).pptx
UTF-8''ACM程序设计竞赛基础教程_俞经善等编,算法入门经典完整版,算法入门经典训练版。
《ACM国际大学生程序设计竞赛题解Ⅰ》——基础编程题