projecteuler No.77 Prime summations

发布时间:2016-12-11 12:29:20 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"projecteuler No.77 Prime summations",主要涉及到projecteuler No.77 Prime summations方面的内容,对于projecteuler No.77 Prime summations感兴趣的同学可以参考一下。

原文题目链接: http://projecteuler.net/problem=77 翻译题目链接: http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/78-77 通过人数:9126 题目分析: 用大脑估算了一下,1000的2、3、5分解的数目就在5000以上,此题答案远小于1000,内存足够,考虑使用动态规划。 构建基本状态点为n的分解成大小不超过m的质数和的数目。打算先试一下普通的递归,如果不行的话考虑优化,如果再不行的话考虑记忆化搜索或者动态规划(实际上这道题只要普通的递归就可以秒解了~所以说后面的步骤我也没有尝试。) 解题过程(代码仅供参考,因为偷懒,代码风格什么的实在不好意思...): 一、1000以内的质数打表备用: for (int i = 2; i < 1000; i++) { for (int j = 2; j * j <= i; j++) { if (i % j == 0) goto next; } p[l] = i; l++; next:; }l表示目前意境存进去的质数数目,初始为0. 这么写未必是最快的写法,也未必是最短的写法,只是比较朴素而已,毕竟只求1000以内的质数花不了多少时间,懒得用什么花招(或者确切的说:一些计算质数的经典算法) 二、递归计算m的分解成大小不超过n的质数和的数目 int count(int m, int n) { if (n > m) return count(m, m); if (m == 0) return 1; if (n < 2) return 0; int t; for (int i = 0;; i++) { if (p[i] > n) { t=p[i - 1]; break; } } int r = 0; while(m >= 0) { r+=count(m, t-1); m -= t; } return r; }没什么可说的~ 三、计算输出结果: int mm[1000]={0}; for (int i = 2;i<1000;i++) { mm[i]=count(i,i); if (mm[i]>5000) { printf("%d\n",i); break; } }最后发现很快地就在i=71的时候突破了5000.于是就没有再做任何优化。把中间计算数值存进mm[i]中,方便debug。 分析:没有想象的难,毕竟71就到了,如果改成5000万的话或许会比较有意思...不过发现如果把5000改成50000000的话,直接递归还是可以做...数值是237(其分解成质数和的方法数为50909577)...所以说还是要改成5万亿左右吧~ 以上只是我做题时的解法。 如果有更好的解法、更好的思路,欢迎评论讨论~O(∩_∩)O~

上一篇:Win8使用感受
下一篇:顶级投资者的21条箴言(组图)

相关文章

相关评论