ProjectEuler 的一道简单题目.md

###ProjectEuler 的一道简单题目

[ProjectEuler](http://projecteuler.net) 上的第六题是比较简单的一道习题,复述题目如下:

> The sum of the squares of the first ten natural numbers is,

> 1^2+ 2^2 + ... + 10^2 = 385

>The square of the sum of the first ten natural numbers is,

>(1 + 2 + ... + 10)^2 = 55^2 = 3025

>Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

>Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

####  重述题目

所述的意思是计算平方和与和的平方的差异,题目中举出了一个例子.就是分别计算自然数1到10的平方和与和的平方,然后做减法,所得的结果 2640 就是所求的结果. 题目要求计算自然数 1 到 100  的计算结果.

####分析题目

如果直接进行计算,可以利用计算机直接循环,分别直接计算出平方的和与和的平方,然后做差,就得到题目要求的结果. 显而易见的是,这样的方法比较简单粗鲁,但是计算过程中做了许多不需要的工作.<br/>

 简化计算的方法是提前化简出通项公式,然后带入项数获得答案.问题的关键就是如何化简公式

####平方和的计算

大家都知道 $1+2+\cdots +n = \frac{n(n+1)}{2}$ ,但是如何计算 $1^2 + 2^2 + 3^2 + \cdots + n^2$ 根据数学定理可知 计算的结果是一个关于 $n$ 的三次表达式,一次我们只需求出这个多项式的四个参数,我们就获得了平方和计算的表达式;$$\begin{bmatrix}1&1&1&1\\2^3&2^2&2&1\\3^3&3^2&3&1\\4^3&4^2&4&1\end{bmatrix} \times \begin{bmatrix}a\\b\\c\\d\end{bmatrix}=\begin{bmatrix}1\\5\\14\\30\end{bmatrix}$$获得矩阵的解即为平方和多项式的系数,所以平方和通项表达式为$$1^2+2^2+3^2+\cdots +n^2=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$$

####和的平方

因为$$1+2+3+\cdots+n=\frac{n(n+1)}{2}$$,所以$$(1+2+3+\cdots+n)^2=\frac{n^2(n+1)^2}{4}$$.

####求差

将两个多项式做差,结果为$$\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}-\frac{n^2(n+1)^2}{4}=-\frac{n^4}{4}-\frac{n^3}{6}+\frac{n^2}{4}+\frac{n}{6}$$

####求解

直接将 $n=100$ 带入,获得解为 25164150. 这样问题就解决了.(偷个懒,不想写长的代码,直接在 chrome  浏览器下运行js算出结果.)

```javascript

var n =100;

Math.pow(n,4)/4 +Math.pow(n,3)/6-n*n/4-n/6;

```

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,658评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,482评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,213评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,395评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,487评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,523评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,525评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,300评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,753评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,048评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,223评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,905评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,541评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,168评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,417评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,094评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,088评论 2 352

推荐阅读更多精彩内容