Project Euler

Working is not boring, Earning money is boring. 自己做的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的。基本上可以暴力求解的都是直接暴力求的。 Problem 1:Multiples of 3 and 5 暴力遍历，能整除3或者5的话累加 int problem1() { long num = 0; for (int i = 0; i < 1000; i++) { if (i % 3 == 0 || i % 5 == 0) num += i; } return num; } Problem 2:Even Fibonacci numbers 把4000000以下的 fib 数列都求出来，再遍历一般累加奇数。 这里其实 fib 数列的奇偶性是有规律的，按照 奇-奇-偶 的形式无限循环，所以也可以用数列的第几项是否能被3整除来判断。 int problem2() { long num = 0; vector<int> fib; fib.push_back(1); fib.push_back(2); while (fib.back() < (4000000)) { fib.push_back(fib.at(fib.size() - 1) + fib.at(fib.size() - 2)); } for (auto f : fib) { if (f < 4000000) { cout << f << endl; if (f % 2 == 0) num += f; } } cout << endl; return num; } Problem 3:Largest prime factor 从小打到大找因数，当找到一个因数之后将原始数字除以这个因数，再继续判断。 long long problem3() { vector<long long > nums; long long num = 600851475143; long long n = 2; while (n <= num) { if (num % n == 0) { nums.push_back(n); num = num / n; } else { n++; } cout << n << endl; } cout << endl << endl; for (auto i : nums) cout << i << endl; cout << endl << endl; return nums.back(); } Problem 4:Largest palindrome product 暴力遍历，判断是回文数后记录最大值。 ...

问题 暴力求解 解答分析 对于循环次数 对于判断范围 若不是因为爱着你，怎么会夜深还没睡意。每个念头都关于你，我想你 想你 好想你。 若不是因为爱着你，怎会不经意就叹息。有种不完整的心情，爱你 爱你 爱着你。 问题 最近做了一些 Project Euler 的题目。目前只做了前十题，感觉和一般的编程题目比还是挺有意思的，单一案例，不限时间，不限做法，只要做出来的就可以，你愿意的话暴力求解，手动去算都可以，还是挺有意思的。 前面有几道关于质数 (Prime Number) 的题目，需要判断一个数是否是质数，也就是这次的问题了。 Problem 7. 10001st prime By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number? Problem 10. Summation of primes The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. ...

[TOC] 继续上一次的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的，思路也是没问题的。这次是11~20题。 Problem 11:Largest product in a grid 在一个20x20的表格内在横竖斜四个方向上找连续四个数字的最大乘积。 暴力遍历就对了，输入直接复制过来通过文本输入，给一个二维的 vector<vector<int>> ，开始可劲的遍历，计算四个方向。为了避免边界条件判断，这里分成了两部分，一部分向右，下，右下遍历，一部分向左上遍历，同样能遍历所有情况，同时避免了边界条件判断。 void problem11() { int out = 0; string input ="08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\ 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\ 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\ 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\ 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\ 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\ 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\ 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\ 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\ 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\ 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\ 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\ 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\ 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\ 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\ 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\ 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\ 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\ 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\ 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"; vector<int> nums; stringstream ss; ss << input; int n; while (ss >> n) { nums.push_back(n); } for (int i = 0; i < 15; i++) { for (int k = 0; k < 15; k++) { int nn = nums.at(i + k * 20) * nums.at(i + k * 20 + 21) * nums.at(i + k * 20 + 2 * 21) * nums.at(i + k * 20 + 3 * 21); out = MAX(out, nn); nn = nums.at(i + k * 20) * nums.at(i + k * 20 + 20) * nums.at(i + k * 20 + 2 * 20) * nums.at(i + k * 20 + 3 * 20); out = MAX(out, nn); nn = nums.at(i + k * 20) * nums.at(i + k * 20 + 1) * nums.at(i + k * 20 + 2 * 1) * nums.at(i + k * 20 + 3 * 1); out = MAX(out, nn); } } for (int i = 0; i < 15; i++) { for (int k = 3; k < 19; k++) { int nn = nums.at(i + k * 20) * nums.at(i + k * 20 - 19) * nums.at(i + k * 20 - 2 * 19) * nums.at(i + k * 20 - 3 * 19); out = MAX(out, nn); } } cout << out << endl;; } Problem 12:Highly divisible triangular number 题目写的挺绕的，按步骤做就好了，先是一个1 ~ n的等差数列的和，我这里用的方法麻烦了，在每个周期上加i就可以了。然后计算1 ~ sqrt(k)之间的能被整除的数字数量，乘以二就是因数数量，这边没有单独判断k是平方数的情况（因为这种情况根本不存在，k=i*(i+1)/2），最后判断一下数量大于500输出结果即可。 ...

[TOC] 继续上一次的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的，思路也是没问题的。这次是21~30题。 Problem 21:Amicable numbers 对于x，除自己以外的因数的和定义为d(x)，求出1000以下的所有满足d(a)=d(b) && a!=b的数对并求和。 遍历->求所有因数->求和记录->遍历判断并求和 void problem21() { map<int, int> mm; int out = 0; for (int i = 1; i < 10000; i++) { int sum = 0; for (int k = 1; k <= (i / 2); k++) { if (i % k == 0) sum += k; } mm.insert({ i, sum }); //cout << i << " " << sum << endl; } for (auto i : mm) { if (mm[i.second] == i.first && i.first != i.second) { cout << i.first << endl; out += i.first; } } cout << out << endl; } Problem 22:Names scores 有一群名字，要求排序，排序之后每个名字的数字和乘以位数再求和。 emmmmm，这个题似乎做得有一点点抄近路，直接STL排序，然后遍历求和即可。 void problem22() { string trianglefilename = "p022_names.txt"; ifstream fin; fin.open(trianglefilename, ios::in); vector<string> lines; string s; while (getline(fin, s)) { lines.push_back(s); } fin.close(); long out = 0; lines = split(lines.at(0), ','); for (int i = 0; i < lines.size(); i++) { lines.at(i) = lines.at(i).substr(1, lines.at(i).size() - 2); } sort(lines.begin(), lines.end()); for (int i = 0; i < lines.size(); i++) { int sum = 0; for (int i : lines.at(i)) { sum += i - 64; } out += sum * (i + 1); } cout << out << endl; } Problem 23:Non-abundant sums 完美数，除了本身以外的因数的和等于自身。 deficient，因数和小于自身；abundant，因数和大于自身。 这题太难解释了，直接题目抄过来自己看题目吧。 ...

罗马不是一天建成的，你也不会一下成为梦想中的人，但是只要在学习在努力，就是越来越接近的。 继续上一次的Project Euler的题解，不见得最优，也不见得优雅，但是答案是对的，思路也是没问题的。这次是31~40题。 (奇怪，这人怎么又开始用python写了 Problem 31: Coin sums 嗯。。挺经典挺常见的完全背包DP问题，但是我满脑子不知道在想什么，愣是没做出来，后来看了看别人的提示才想到应该按照硬币种类去循环。一直在想怎么去处理重复的情况。 这里是这道题的详细解释 这里是完全背包、01背包、多重背包的比较的参考资料（我没看 def pro31(): # 完全背包DP coin = [1, 2, 5, 10, 20, 50, 100, 200] methods = [0]*300 methods[0] = 1 for k in coin: for i in range(1, 210): if i >= k: methods[i] += methods[i-k] print(methods[200]) Problem 32: Pandigital products 很蠢的一个做法，每一个去遍历判断的 def pro32(): out = [] for i in range(10, 10000): numl = [] k = i while k != 0: if k % 10 not in numl: numl.append(k % 10) k = k//10 else: break if k == 0: for j in range(2, int(math.sqrt(i))): if i % j == 0: numll = [] k = j while k != 0: if (k % 10 not in numl) and (k % 10 not in numll): numll.append(k % 10) k = k//10 else: break if k == 0: k = i//j while k != 0: if (k % 10 not in numl) and (k % 10 not in numll): numll.append(k % 10) k = k//10 else: break if (k == 0) and (len(numl)+len(numll) == 9) and (0 not in numl) and (0 not in numll): print("%d %d %d" % (i, j, i//j)) if i not in out: out += [i] print(sum(out)) Problem 33: Digit cancelling fractions 这个问题第一次考虑的时候考虑错了，以为分子和分母相同的数字肯定一个在十位一个在个位的，导致一开始答案是错误的。其实可以在外层循环增加一些判断，这样速度会快一些。。。 ...