[关闭]
@JunQiu 2018-10-06T08:06:16.000000Z 字数 1267 阅读 724

迅雷笔试题(2018/09/13)

algorithm


1、计算勾股数

  1. 计算勾股数 - 后台开发工程师
  2. 时间限制:C/C++语言 1000MS;其他语言 3000MS
  3. 内存限制:C/C++语言 65536KB;其他语言 589824KB
  4. 题目描述:
  5. 勾股数,是由三个正整数组成的数组;能符合勾股定理 a*a + b*b = c*c (a, b, c) 的正整数解。如果 (a, b, c) 是勾股数,它们的正整数倍数,也是勾股数。如果 (a, b, c) 互质,它们就称为素勾股数。给定正整数N,计算出小于或等于N的素勾股数个数。(0 < a <= b <= c <= N)
  6. 输入
  7. 正整数N
  8. 输出
  9. 小于或等于N的素勾股数个数
  10. (0 < a <= b <= c <= N)
  11. 样例输入
  12. 10
  13. 样例输出
  14. 1
  15. ## 解题思路
  16. 暴力遍历。。。
  17. ## 题解
  18. #include <iostream>
  19. using namespace std;
  20. // gcd求两个数的最大公约数
  21. int gcd(int x, int y) {
  22. int t;
  23. while (y) t = x, x = y, y = t % y;
  24. return x;
  25. }
  26. // 判断三个数是否互质
  27. int isCoprimeNumber(int x, int y, int z) {
  28. if (gcd(x, y) == 1 && gcd(y, z) == 1 && gcd(x, z) == 1)
  29. return true;
  30. return false;
  31. }
  32. int main() {
  33. int n;
  34. cin >> n;
  35. int count = 0;
  36. for (int i = 1; i < n; ++i) {
  37. for (int j = i; j < n; ++j) {
  38. for (int k = j; k <= n; ++k) {
  39. if (i * i + j * j == k * k && isCoprimeNumber(i, j, k))
  40. count++;
  41. }
  42. }
  43. }
  44. cout << count << endl;
  45. return 0;
  46. }

2、红黑积木求和

  1. 红黑积木求和 - 后台开发工程师
  2. 时间限制:C/C++语言 1000MS;其他语言 3000MS
  3. 内存限制:C/C++语言 65536KB;其他语言 589824KB
  4. 题目描述:
  5. 有红黑两种颜色的方块积木,红色代表正数A,黑色代表负数B。选出17块积木排成一排,使得任意相邻7块积木之和都小于0。如何挑选才能使17块积木之和最大,最大值是多少?
  6. 输入
  7. 正数A,负数B
  8. AB绝对值小于10000
  9. 输出
  10. 积木之和的最大值
  11. 样例输入
  12. 10 -61
  13. 样例输出
  14. 28
  15. ## 解题思路
  16. 1、找出7个数之和 < 0 且尽可能大的组合
  17. 2、将17个数分为 7 7 3 ,使3的组合最大,即正数尽可能多
  18. Tips:也可以维持一个长度为7的滑动窗口实现,窗口7个数之和 < 0 且尽可能大。
  19. ## 题解
  20. #include <iostream>
  21. using namespace std;
  22. int main() {
  23. int a, b;
  24. // a为正,b为负
  25. cin >> a >> b;
  26. // 正数尽可能多
  27. int i;
  28. for (i = 1; i <= 7; ++i) {
  29. if (a * (7 - i) + b * i < 0)
  30. break;
  31. }
  32. // 7 7 3,让3中的正数尽可能多
  33. int res;
  34. if (7 - i >= 3)
  35. res = a * 3 + (a * (7 - i) + b * i) * 2;
  36. else
  37. res = a * (7 - i) + (3 - (7 - i)) * b + (a * (7 - i) + b * i) * 2;
  38. cout << res << endl;
  39. return 0;
  40. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注