深入浅出程序设计竞赛（基础篇）第二章 算法从0开始
- 第二章 例题
- 例2-1
- 例2-2
- 例2-3
- 例2-4
- 例2-5
- 例2-6
- 例2-7
- 例2-8
- 例2-9
- 例2-10
- 例2-11
- 例2-12
- 第二章 课后习题
- 2-1
- 2-2
- 2-3
- 2-4
- 2-5
- 2-6
- 2-7
第二章 例题
例2-1
#include<iostream>
using namespace std;
int main(){
int v_a = 5, v_yao = 8, distance = 100; //小A和八尾勇的速度，以及距离
double delta, ans; //速度的差值和答案
delta = v_yao - v_a; //两人的相对速度，也就是每秒距离缩短多远
ans = distance / delta;
// ans = 1.0 * distance / (v_yao - v_a);
cout << ans << endl;
return 0;
}
例2-2
#include <ctime>
#include<iostream>
using namespace std;
int main(){
int ans1;
char ans2;
ans1 = 'M' - 'A' + 1;
ans2 = 'A' + 18 -1;
cout << ans1 << endl;
cout << ans2 << endl;
return 0;
}
// 65 A
// 97 a
// 97 - 65 = 32
// 48 0
例2-3
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int r1 = 4, r2 = 10;
const double PI = 3.141593;
double V , l;
V = 4.0 / 3 * PI * (pow(r1, 3) + pow(r2, 3));
l = pow(V, 1.0 / 3);
cout << (int)l << endl;
return 0;
}
例2-4
#include<iostream>
#include<cmath>
using namespace std;
int main(){
double a = 1, b = -100, c = 2400;
double delta, ans;
delta = pow(b, 2) - 4 * a * c;
ans = (-b + sqrt(delta)) / (2 * a);
cout << 110 - int(ans + 0.5) << endl; //加0.5是为了做四舍五入的操作，而不是直接去掉小数部分
return 0;
}
例2-5
#include<iostream>
using namespace std;
int main(){
int t, n; //每人的苹果数量和学生数量
cin >> t >> n; //各个数据之间的输入可以使用空格或者回车隔开，而多余的空格或者回车会被忽略
cout << t * n << endl;
return 0;
}
例2-6
#include<iostream>
using namespace std;
int main(){
char ch, ans;
cin >> ch;
ans = ch - 'a' + 'A';
cout << ans;
return 0;
}
例2-7
解法一：获取输入数字的千百十个位，再颠倒过来即可
#include<iostream>
using namespace std;
int main(){
double p; //输入的数字
int q, a, b, c, d; // 转换成的4位数和分离出来的4位数字
cin >> p;
q = int(p * 10);
a = q / 1000; //千位
b = q / 100 % 10; // 百位
c = q / 10 % 10; // 十位
d = q % 10; // 个位
cout << d << "." << c << b << a << endl;
return 0;
}
解法二：可以把输入视为5个字符，然后直接输出
#include<iostream>
using namespace std;
int main(){
char a, b, c, dot, d;
cin >> a >> b >> c >> dot >> d;
cout << d << dot << c << b << a << endl;
return 0;
}
解法三：使用c语言的风格进行输入输出
#include<cstdio>
using namespace std;
int main(){
char a, b, c, d;
scanf("%c%c%c.%c", &a, &b, &c, &d);
printf("%c.%c%c%c", d, c, b, a);
return 0;
}
例2-8
#include<cstdio>
using namespace std;
int main(){
double t;
int n;
scanf("%lf%d", &t, &n);
printf("%.3f\n%d", t / n, n * 2);
return 0;
}
//常见输入输出占位符
// %d 十进制整数，常用于int类型
// %nd 输出整数，若不足n位前面用空格补齐直到够n位
// %164d windows
// %lld linux 十进制整数，常用于long long类型
// %f 读入float类型的浮点数，或输出float或double类型的浮点数，默认6位小数
// %lf 读取double类型的浮点数
// %.nf 输出固定n位小数的浮点数
// %0nd 输出整数，若不足n位，前面用0补齐直到够n位
// %c char类型的字符
// %s 字符串
例2-9
#include<cstdio>
using namespace std;
int main(){
int a, b, t;
scanf("%d %d", &a, &b);
t = a; a = b; b = t; //一组相关的短语句也可以写在一行内
printf("%d %d", a, b);
return 0;
}
例2-10
直接全部转换成分钟数计算差值然后再转换成小时和分钟，就无需考虑是否进位借位的情况了
#include<cstdio>
using namespace std;
int main(){
int a, b, c, d, e, f, delta;
scanf("%d%d%d%d", &a, &b, &c, &d);
delta = (60 * c + d) - (60 * a + b);
e = delta / 60;
f = delta % 60;
printf("%d %d", e, f);
return 0;
}
例2-11
解法一：直接乘上权重后输出这个数，+0.5是为了四舍五入，最后输出需要强制类型转换
#include<cstdio>
using namespace std;
int main(){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%d", int(a * 0.2 + b * 0.3 + c * 0.5 + 0.5));
return 0;
}
解法二：题目在数据规模中提到“A、B、C都是10的整数倍”，这个非常重要，每一小项经过加权，即使又乘上一个小数，但是结果一定是整数。可以把 * 0.2 变成 * 2 / 10，使程序不会接触到浮点数，不必考虑浮点数误差。
#include<cstdio>
using namespace std;
int main(){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%d", a * 2 / 10 + b * 3 / 10 + c * 5 / 10);
return 0;
}
例2-12
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
int s, v;
scanf("%d%d", &s, &v);
int t_walk = ceil(1.0 * s / v) + 10; //两次类型转换注意到了吗
int from_zero = 60 * (24 + 8) - t_walk; //计算到前一天零点的时间
int hh = (from_zero / 60) % 24; //计算小时
int mm = from_zero % 60; // 计算分钟
printf("%02d:%02d\n", hh, mm); //输出两位，用0补齐
return 0;
}
// Waiting / Judging / Pending ：程序正在等待评测，或者正在评测
// Accepted(AC) ：程序通过了测试点
// Compile Error(CE)：程序编译错误
// Wrong Answer(WA)：错误的答案
// Runtime Error(RE)：运行时错误
// Time Limit Exceeded(MLE)：超出时间限制
// Memory Limit Exceeded(MLE)：超出内存限制
第二章 课后习题
2-1
#include<iostream>
using namespace std;
int main(){
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
cout << 1.0 * a / b / c *d * e << endl; //1
return 0;
}
其他略，读者自行尝试
cout << 480 / (1.4 + 1) << " " << 480 / (1.4 + 1) * 1.4 << endl; //3
cout << 11 + 1 << " " << 3 * (11 + 1) + 11 << endl; //4
cout << 80 * 12 / (120 - 80) << endl; //5
int x = (94 - 35 * 2) / 2 ;
int y = 35 - x;
cout << x << " " << y << endl; //6
double a = 10000 * (1 + 0.035) * (1 + 0.035) * (1 + 0.035) * (1 + 0.035) * (1 + 0.035);
double b = 10000 * (1 + 0.04);
cout << a << " " << b << endl;
2-2
题目中要求使用四舍五入，前面书中提到都是加0.5，但是亲自试了发现 printf("%.1lf", s)本身就已经进行四舍五入了，无需再加0.5作为四舍五入的操作
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
double a, b, c, s, p;
cin >> a >> b >> c;
p = 0.5 * (a + b + c);
s = sqrt(p * (p - a) * (p - b) * (p - c));
printf("%.1lf", s);
return 0;
}
2-3
2-4
#include<cstdio>
using namespace std;
int main(){
float a = 0.1;
// printf("%lf", 2 - a * a * 100);
printf("%d", int(2 - a * a * 100));
printf("\n");
printf("%.10f", 2 - a * a * 100);
return 0;
}
0
0.9999998808
2-5
#include<iostream>
using namespace std;
int main(){
int a, b;
cin >> a >> b;
int ans = (a * 10 + b) / (1 * 10 + 9);
cout << ans << endl;
return 0;
}
2-6
特殊情况t=0说明没有苹果可吃了要额外考虑
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int m, t, s;
cin >> m >> t >> s;
if (t == 0){
cout << 0;
return 0;
}
int cal = s / t;
if(s % t == 0){
cout << max(m - cal, 0);
}else{
cout << max(m - cal - 1, 0) << endl;
}
return 0;
}
2-7
解析：n可能很大且为正所以用unsigned long long类型，
推导公式：一条对角线需要两个顶点，两条对角线相交需要四个顶点，所以本题可以看作从n个顶点当中逐个取出四个顶点，进行组合，得到公式 n * (n-1) * (n-2) * (n-3) / 24，为了防止爆掉 采用这种公式n * (n-1) / 2 * (n-2) / 3 * (n-3) / 4即可。
#include<iostream>
using namespace std;
int main(){
unsigned long long n;
cin >> n;
cout << n * (n-1) / 2 * (n-2) / 3 * (n-3) / 4;
return 0;
}
