运城市住房与城乡建设厅网站,黄骅贴吧二手房,西安企业模板网站建设,深圳seo教程Project_Euler-44 题解 题目 思路
题目给出了一个性质#xff0c;让我在对应性质的数据中找出目标值#xff0c;这种问题首先想到的就是枚举。
我们可以枚举 P k P_k Pk #xff0c;对于每一个 P k P_k Pk #xff0c;我们再枚举 P j P_j Pj#xff0c; P j P_…Project_Euler-44 题解 题目 思路
题目给出了一个性质让我在对应性质的数据中找出目标值这种问题首先想到的就是枚举。
我们可以枚举 P k P_k Pk 对于每一个 P k P_k Pk 我们再枚举 P j P_j Pj P j P_j Pj 从 P k − 1 P_k - 1 Pk−1 开始倒着往回枚举在枚举的过程中判断他们的和差是否均为五边形数。如果是再与之前的已经找到的答案进行比较如果比答案更小说明可以取。
还有一个问题 P k P_k Pk枚举的范围怎么确定
假设我们枚举两个相邻的五边形数 P k P_k Pk 和 P k − 1 P_{k-1} Pk−1 会发现他们的差值随着 k k k 的增大而不断增大而我们的 P j P_j Pj 又是从 P k − 1 P_{k - 1} Pk−1 开始向前枚举的因此如果相邻的 P k P_k Pk 和 P k − 1 P_{k-1} Pk−1 已经大于目前已知的 D D D那么我们再枚举就没有意义了因为后面找到的答案一定大于 D D D。
对于内层循环其实也可以使用类似的原理来做优化如果 P k − P j D P_k - P _ j D Pk−PjD 那么也不用继续枚举了因为 P k − P j P_k - P_j Pk−Pj 只会越来越大。
代码
#include stdio.h
#include stdlib.h
#include math.h
#include string.h
#include time.h
#include inttypes.htypedef long long ll;ll pentagonal(ll n) {return (n * (3 * n - 1)) 1;
}ll is_pentagonal(ll x, ll n) {ll head 1, tail n, mid;while (head tail) {mid (head tail) 1;if (pentagonal(mid) x) return 1;if (pentagonal(mid) x) head mid 1;else tail mid - 1;}return 0;
}int main() {ll ans INT32_MAX;ll i 1, j 1;while (pentagonal(i 1) - pentagonal(i) ans) {i 1;j i - 1;for (; j 1 pentagonal(i) - pentagonal(j) ans; j--) {if (!is_pentagonal(pentagonal(i) pentagonal(j), 2 * i)) continue;if (!is_pentagonal(pentagonal(i) - pentagonal(j), 2 * j)) continue;printf(%lld -- %lld\n, pentagonal(j), pentagonal(i));ans pentagonal(i) - pentagonal(j);}}printf(MIN D is %lld\n, ans);return 0;
}
