【深入浅出程序设计竞赛（基础篇）第三章 算法从0开始】

第三章 例题

例3-1

#include<iostream>
using namespace std;int main(){int a, b;cin >> a >> b;cout << (a > b) << ' ';cout << (a <= b) << ' ';cout << (a != b) << endl;return 0;
}//运算符优先级
//高                                         低
//() * / % + - < > >= <= == !=
//比较两个浮点数是否相等采用差值是否小于一定程序，如fabs(a-b) < 1e-6

例3-2

#include<iostream>
using namespace std;int main(){int x; bool p1, p2;cin >> x;p1 = x % 2 == 0;p2 = 4 < x && x <= 12;cout << (p1 && p2) << ' '; //两个性质同时成立cout << (p1 || p2) << ' '; //两个性质至少一个成立cout << (p1 ^ p2) << ' '; //两个性质刚好一个成立cout << (!p1 && !p2); //两个性质同时不成立// cout << !(p1 || p2); //也可以这么写return 0;
}// 运算优先级补充
// 高                                          低
// () ! - ++ -- * / % << >> < > <= >= == != && ||

例3-3

能被400整除 或者 被4整除且不能被100整除 是闰年

#include<iostream>
using namespace std;int main(){int x; bool p;cin >> x;p = (x % 400 == 0) || (x % 4 == 0) && (x % 100 != 0);//p = !(x % 400) cout << p << endl;return 0;
}

例3-4

#include<iostream>
using namespace std;int main(){int x;cin >> x;cout << "Today, I ate " << x << " apple";if(x != 0 && x != 1){ // 也可写成 !(x==0 || x==1)cout << "s";}cout << "." << endl;return 0;
}

例3-5

#include<iostream>
using namespace std;int main(){int n;cin >> n;if ((5 * n) < (11 + 3 * n)) {cout << "Local" << endl;} else{cout << "Luogu" << endl;}return 0;
}

例3-6

#include<iostream>
using namespace std;int main(){char opt;cin >> opt;switch(opt){case 'G': cout << "Hello, my master!" << endl;case 'N': cout << "I'm Xiaoluo." << endl; break;case 'S': cout << "Teinei teinei teinei~" << endl; break;case 'B': case 'Q':cout << "Bye bye!" << endl;break;default: cout << "Sorry.." << endl;}return 0;
}

例3-7

#include<iostream>
using namespace std;int main(){double m, h, BMI;cin >> m >> h;BMI = m / h / h;if(BMI < 18.5)cout << "Underweight";else if(BMI < 24)cout << "Normal";else{cout << BMI << endl;cout << "Overweight" << endl;}return 0;
}

例3-8

解法一：

#include<cstdio>
using namespace std;int main(){int a, b, c;scanf("%d%d%d", &a, &b, &c);if(a <= b && b <= c) printf("%d %d %d\n", a, b, c);else if(a <= c && c <= b) printf("%d %d %d\n", a, c, b);else if(b <= a && a <= c) printf("%d %d %d\n", b, a, c);else if(b <= c && c <= a) printf("%d %d %d\n", b, c, a);else if(c <=a && a <= b) printf("%d %d %d\n", c, a, b);else /*if (c <= b && b <= a)*/ printf("%d %d %d\n", c, b, a);return 0;
}

解法二：

#include<cstdio>
using namespace std;int main(){int a, b, c;scanf("%d%d%d", &a, &b, &c);if(a >= b && a >= c)if(b >= c) printf("%d %d %d\n", c, b, a);else printf("%d %d %d\n", b, c, a);else if(b >= a && b >= c)if(a >= c) printf("%d %d %d\n", c, a, b);else printf("%d %d %d\n", a, c, b);else // if(c >= a && c >= b) 本句可加可不加if(a >= b) printf("%d %d %d\n", b, a, c);else printf("%d %d %d\n", a, b, c);return 0;
}

例3-9

#include<iostream>
using namespace std;
int main(){int y, m;cin >> y >> m;switch(m){case 1: case 3: case 5: case 7: case 8: case 10: case 12: cout << 31 << endl; break;case 4: case 6: case 9: case 11:cout << 30 << endl; break;case 2:if(!(y % 400) || !(y % 4) && y % 100)cout << 29 << endl;elsecout << 28 << endl;break;default: break;}return 0;
}

例3-10

#include<iostream>
using namespace std;int main(){int t1, t2, maxtime = 8, maxday = 0;cin >> t1 >> t2;if (t1 + t2 > maxtime) maxtime = t1 + t2, maxday = 1;cin >> t1 >> t2;if (t1 + t2 > maxtime) maxtime = t1 + t2, maxday = 2;cin >> t1 >> t2;if (t1 + t2 > maxtime) maxtime = t1 + t2, maxday = 3;cin >> t1 >> t2;if (t1 + t2 > maxtime) maxtime = t1 + t2, maxday = 4;cin >> t1 >> t2;if (t1 + t2 > maxtime) maxtime = t1 + t2, maxday = 5;cin >> t1 >> t2;if (t1 + t2 > maxtime) maxtime = t1 + t2, maxday = 6;cin >> t1 >> t2;if (t1 + t2 > maxtime) maxtime = t1 + t2, maxday = 7;cout << maxday;return 0;
}

例3-11

解法一：

#include<iostream>
using namespace std;
int main(){int n, n1, n2, n3, p1, p2, p3, t1, t2, t3, total;cin >> n >> n1 >> p1 >> n2 >> p2 >> n3 >> p3;t1 = !(n % n1) ? n / n1 * p1 : (n / n1 + 1) * p1;t2 = !(n % n2) ? n / n2 * p2 : (n / n2 + 1) * p2;t3 = !(n % n3) ? n / n3 * p3 : (n / n3 + 1) * p3;total = t1; //解设第一种是最省钱的方案if (t2 < total) total = t2;if (t3 < total) total = t3;cout << total << endl;return 0;
}

解法二：
可以采用ceil函数进行上取整运算直接获取需要购买几包铅笔

#include<iostream>
#include<cmath>
using namespace std;
int main(){int n, n1, n2, n3, p1, p2, p3, t1, t2, t3, total;cin >> n >> n1 >> p1 >> n2 >> p2 >> n3 >> p3;t1 = ceil(1.0 * n / n1) * p1;t2 = ceil(1.0 * n / n2) * p2;t3 = ceil(1.0 *n / n3) * p3;total = t1; //解设第一种是最省钱的方案if (t2 < total) total = t2;if (t3 < total) total = t3;cout << total << endl;return 0;
}

例3-12

#include<iostream>
using namespace std;
int main(){char a, b, c, d, e, f, g, h, i, j;int check;scanf("%c-%c%c%c-%c%c%c%c%c-%c",  &a, &b, &c, &d, &e, &f, &g, &h, &i, &j);check = (a - '0') * 1 + (b - '0') * 2 + (c - '0') * 3 + (d - '0') * 4 + (e - '0') * 5 + (f - '0') * 6 + (g - '0') * 7 + (h - '0') * 8 + (i - '0') * 9;check %= 11;if(j=='X' && check == 10 || check == j - '0')printf("Right\n");elseprintf("%c-%c%c%c-%c%c%c%c%c-%c", a, b, c, d, e, f, g, h, i, check==10?'X':check+'0');return 0;
}

第三章 课后习题

3-1

#include<iostream>
using namespace std;
int main(){int a = 3, b = 4, c = 5;cout << (a < b || b > c || a > b); //1cout << (a > c || b > a && c > b); //1cout << (b - a == c - b); //1cout << (a * b - c > a * c - b || a * b + b * c == b * b * (c - a)); //1return 0;
}

3-2

#include<iostream>
using namespace std;
int main(){int a = 1, b = 0, c = 1;cout << (!a||!b); //1cout << (a&&!a) || (b||!b); //0 这是因为<<优先级高于||，所以结果为0cout << (a&&b&&c||!a||!c); //0cout << (a&&(b&&c||a&&c)); //1cout << (!b&&(c&&(a&&(!c||(!b||(!a)))))) ;//1return 0;
}

3-3

1) x % 2 == 0
2) x % 4 == 0
3) sqrt(x) == floor(sqrt(x))
4) cbrt(x) == floor(cbrt(x))
5) pow(x % 10, 3) + pow(x / 10 % 10, 3) + pow(x / 100, 3) == x 

3-4

#include<cstdio>
using namespace std;
int main(){int p;double ans;scanf("%d", &p);if (p <= 150) ans = 0.4463 * p;else if(p >= 151 && p <= 400) ans = 0.4463 * 150 + 0.4663 * (p - 150);else ans = 0.4463 * 150 + 0.4663 * 250 + 0.5663 * (p - 400);printf("%.1lf", ans);return 0;
}

3-5

#include<iostream>
using namespace std;int main(){int x;unsigned long long n, ans = 0;cin >> x >> n;for(int i = 0; i < n; i++){if (x != 6 && x != 7) ans += 250;if (x == 7) x = 1; //周日之后是周一所以赋值为1else x++;}cout << ans;return 0;
}

3-6

注意数据范围

#include<bits/stdc++.h> //万能头
using namespace std;
#define ll long longint main(){ll a, b, c;cin >> a >> b >> c;ll maxl = max(a, max(b, c));ll minl = min(a, min(b, c));cout << minl / __gcd(minl, maxl)  << '/' << maxl / __gcd(minl, maxl);return 0;
}

3-7

#include<iostream>
using namespace std;int main(){int a[10];for (int i = 0; i < 10; i++){cin >> a[i];}int height, ans = 0;cin >> height;height += 30;for (int i = 0; i < 10; i++){if(a[i] <= height) ans++;}cout << ans;return 0;
}

3-8

由余弦定理得, a^2 = b^2 + c^2 - 2bccosA
所以b^2 + c^2 - a^2 = 2bccosA
又因为b > 0 c > 0
当A为锐角时 cosA>0，则b^2 + c^2 - a^2 > 0，即b^2 + c^2 > a^2时为锐角三角形
当A为直角时 cosA=0，则b^2 + c^2 - a^2 = 0，即b^2 + c^2 = a^2时为直角三角形
当A为钝角时 cosA<0，则b^2 + c^2 - a^2 < 0，即b^2 + c^2 < a^2时为钝角三角形

#include<bits/stdc++.h>
using namespace std;int main(){int a[3];for (int i = 0; i < 3; i++){cin >> a[i];}sort(a, a+3);if (a[0] + a[1] <= a[2]) cout << "Not triangle" << endl;else{if (a[0] * a[0] + a[1] * a[1] == a[2] * a[2]) cout << "Right triangle" << endl;else if (a[0] * a[0] + a[1] * a[1] > a[2] * a[2]) cout << "Acute triangle" << endl;else cout << "Obtuse triangle" << endl;if (a[0] == a[1] && a[1] == a[2]) {cout << "Isosceles triangle" << endl;cout << "Equilateral triangle" << endl;}else if(a[0] == a[1] || a[0] == a[2] || a[1] == a[2]) cout << "Isosceles triangle" << endl;}return 0;
}

3-9

#include<iostream>
#include<algorithm>
using namespace std;int main(){int a[3];for(int i = 0; i < 3; i++){cin >> a[i];}sort(a, a+3);char b[3];for(int j = 0; j < 3; j++){cin >> b[j];if (j != 2) cout << a[b[j] - 'A'] << ' ';else cout << a[b[j] - 'A'];}return 0;
}