欧拉项目 | 75题 | 整数直角三角形

发表于 2018-02-03 分类于数学，欧拉项目 Disqus：

给定一个整数L，可能可以弯成一个各边都是整数的直角三角形，也可能不可以。如果可以的话，可能只有一种方法，也可能有多种。
比如12，可以组成一个三边都是整数的直角三角形，且只能组出来一个。
比如10，无法弯出一个各边都是整数的直角三角形。
再比如120，有多种组合(30,40,50), (20,48,52), (24,45,51)。

L ≤ 1,500,000，有多少个L恰好有唯一一种方法得到直角三角形。

和Project Euler的很多题目一样，1500000这个值很大，暴力的遍历每个L，然后切分成三段，三段又恰好是直角三角形，这种方法时间复杂度极大，显然不可行。
另辟蹊径，我们先想办法找到所有的周长小于MaxL的直角三角形，然后遍历这些三角形，用一个map记住周长出现的次数，最后统计一次的个数即可。
现在的问题就是如果找到直角三角形呢？三边其实就是方程x^2 + y^2 = z^2的整数解。

现在万事俱备，就差coding了。

var triangles = new List<long>();
for (long a = 1; a < L / 2; a += 2)
{
    for (long b = a + 2; a * b < L / 2; b += 2)
    {
        if (Utils.GetGcd(a, b) == 1)
        {
            for (long k = 1; k * a * b < L / 2; k++)
            {
                long x = k * a * b;
                long y = k * (b * b - a * a) / 2;
                long z = k * (b * b + a * a) / 2;
                if (x + y + z <= L)
                {
                    triangles.Add(x+y+z);
                }
            }
        }
    }
}

var countMapping = new Dictionary<long, int>();
for (int i = 1; i <= L; i++)
{
    countMapping[i] = 0;
}

foreach (var circumference in triangles)
{
    countMapping[circumference]++;
}

return countMapping.Count(p => p.Value == 1);

欧拉项目 | 518题 | 质数三元组和等比数列

发表于 2018-01-27 分类于数学，欧拉项目 Disqus：

518题链接

S(n) = sum(a+b+c)，其中a b c满足以下三个性质：

a b c都是质数
a < b < c < n
a+1, b+1, c+1能组成等比数列

题目中给出了一个例子S(100) = 1035可以用于测试。
求S(10^8)

前一亿个数里面有576万个质数，显然，不可以接受O(n^2)的算法。
为了描述方便，后面a b c是题目中的a+1 b+1和c+1。
a b c能组成等比数列，那么b^2=a*c。
给定一个a，我们不能用遍历的方式去找b，否则会是O(n^2)的算法。我们需要一个更快的方式找到可能的b。
考虑这样一个问题，a的质因数里面有4个p，那么b的质因数里面至少有2个p，那么a和b之间最少也差着p^2；a的质因数里面有5个q，那么b的质因数里面至少有3个q，那么a和b之间最少也差着q^3；同时考虑p和q的话，那么差值是p^2*q^3。有了这个差值，就能够大大减少内层循环的数目。通过计数器发现，内层循环大概是8-9次的。
问题转换到如何得到a的质因数及其次数，这是一个比较简单的问题。

public static List<Tuple<long, int>> TrialDivisioFactor(long n, long[] primes)
{
    var results = new List<Tuple<long, int>>();
    int index = 0;
    while (true)
    {
        if (primes[index] != 0)
        {
            if (primes[n] != 0)
            {
                results.Add(new Tuple<long, int>(n, 1));
                break;
            }

            int count = 0;
            while (n % primes[index] == 0)
            {
                count++;
                n /= primes[index];
            }

            if (count != 0)
            {
                results.Add(new Tuple<long, int>(primes[index], count));
            }

            if (n == 1)
            {
                break;
            }
        }

        index++;
    }

    return results;
}

GenPrimes就是通过筛选法得到质数。
下面是完整的程序。

int end = 100000000;
long sum = 0;
Utils.GenPrimes(end, out long[] primes);
for (int i = 0; i < primes.Length; i++)
{
    if (primes[i] != 0)
    {
        var a = primes[i] + 1;
        var factors = Utils.TrialDivisioFactor(a, primes);
        var step = 1;
        foreach (var f in factors)
        {
            step *= (int)Math.Pow(f.Item1, (f.Item2 + 1) / 2);
        }
        for (long b = a + step; b < end; b += step)
        {
            var c = b * b / a;
            if (c >= end)
            {
                break;
            }

            if (primes[b - 1] != 0 && primes[c - 1] != 0)
            {
                sum += a + b + c - 3;
            }
        }
    }
}

return sum;

2017年的流水账

发表于 2017-12-31 分类于杂 Disqus：

年底了，花几分钟时间写写流水账，回忆下过去，展望下未来。
新年新气象，也给自己的小站搞个头像哈哈。

和燕燕的感情越来越好，沟通的更加充分，也有了未来几年一个模糊的规划。下一年，好的地方继续保持，不好的地方要持续提高，希望一阶导能大一些。

不知不觉回到MS又一年半多了，今年也顺利升了一级，虽说涨薪不多吧，但是事业上还是向上的。下一年稳扎稳打，争取再升一级（蜜汁自信）。

从过年回到家健身到现在，刨除出去休假的日子，共计健身39周，粗略看了下数据，每组个数有10%-30%的提升，有点少了。明年争取建立一套比较合理且完善的提升计划，再有就是把身体围度也量化下，经常拍拍照，争取明年年底搞个gif动画出来震撼下自己（更加蜜汁自信。。。）。

学习方面，年初12个公开课或者书的计划基本上是完成了，不过公开课比例比较大。明年的话，减少一下公开的比例，多读书。再有就是，欧拉项目，多做几个，一月一个问题不大。
1 可汗学院：微观经济学 http://open.163.com/special/Khan/microeconomics.html
2 可汗学院：宏观经济学 http://open.163.com/special/Khan/macroeconomics.html
3 Functional Programming in Scala Specialization

https://www.coursera.org/learn/progfun1/home/welcome
https://www.coursera.org/learn/progfun2/home/welcome
https://www.coursera.org/learn/parprog1/home/welcome
https://www.coursera.org/learn/scala-spark-big-data/home/welcome
https://www.coursera.org/learn/scala-capstone/home/welcome

4 C# in depth 3rd Jon Skeet
5 人类简史（以色列）尤瓦尔·赫拉利（Yuval Noah Harari）
6 物理学基础公开课1 http://open.163.com/special/fundamentalsofphysics/
7 MIT 18.01 https://ocw.mit.edu/courses/mathematics/18-01-single-variable-calculus-fall-2006/
8 数学之旅 - 上海交通大学 http://open.163.com/special/cuvocw/shuxuezhilv.html
9 MIT 18.02 https://ocw.mit.edu/courses/mathematics/18-02-multivariable-calculus-fall-2007/
10 MIT 18.06 https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/index.htm
11 物理学基础公开课2 http://open.163.com/special/opencourse/physicsii.html
12 NCE2 路易斯·乔治·亚历山大，何其莘

人类简史 | Part4 | 科学革命

发表于 2017-12-14 分类于阅读，摘抄&心得 Disqus：

第十四章发现自己的无知

在过去500年间，人类的力量有了前所未有的惊人成长。
人口增加了14倍，生产增加了240倍，消耗的能量增加了115倍。
Leo：我们利用能源的效率只增了一倍？
科幻小说家凡尔纳书中，富有的英国探险家福格已经可以只花80天就环游世界一周。现在不到48小时就能完成。
微生物占了全部有机体大约99.99%，但人类非常晚近，才对微生物有了认识。
我们每个人身上都有数十亿个单细胞生物，而且还不只是搭搭便车的关系。
微生物可以说是我们最好的朋友，也是最致命的敌人。
1945年7月16日上午5点29分45秒，就在这一秒，美国科学家在新墨西哥的阿拉莫戈多引爆了第一颗原子弹。从这时开始，人类不仅有了改变历史进程的能力，更有了结束历史进程的能力。
现代科学与先前的知识体系有三大不同之处：

愿意承认自己的无知
以观察和数学为中心
取得新能力

现代科学愿意承认自己的无知，就让它比先前的知识体系更具活力、更有弹性，也更有求知欲。

吉尔伽美什计划
人类所有看来无法解决的问题里，有一项最令人烦恼、有趣且重要：死亡。
科学革命的一大计划目标，就是要给予人类永恒的生命。
Leo：住哪？吃啥？能量哪里来？
全球人类的平均寿命已经从25-40岁跃升为67岁左右。
死亡军团受到最大的挫败在于儿童死亡率。
书中王室的例子，说明即使当时最有权有势的人，儿童的死亡率依旧很高。爱德华和埃莉诺大约每三年就有一个孩子夭折。这种嗓子丧女之痛，对今天的父母而言简直难以想象。
有几位学者确实认为，到了2050年，就已经能够让某些人达到长生的状态，只要不是因为意外而受到致命性伤害，就能将生命无限延长。

第十五章科学与帝国的联姻

科学革命与现代帝国主义的关系密不可分。
欧洲原本就像是处在世界的一个偏远角落，气候还冻到让人手指僵硬，他们究竟是怎么一跃而出、征服世界的？常常有人认为最大的功臣就是欧洲的科学家。
中国和波斯，缺少的是西方价值观、故事、司法系统和社会政治结构，这些在西方花了数个世纪才形成及成熟，就算想要照抄，也无法在一夕之间内化。
究竟欧洲在现代早期培养了什么潜力，让它能在现代晚期称霸全球？这个问题有两个答案、相辅相成：现代科学和资本主义。
欧洲帝国主义之所以要前往遥远的彼岸，除了为了新领土，也是为了新知识。
郑和下西洋得以证明，当时欧洲并未占有科技上的优势。真正让欧洲人胜出的，是他们无与伦比而又贪得无厌、不断希望探索和征服的野心。
从整个19世纪到20世纪初，英国就征服并统治了全印度大约3亿人口。
帝国之所以资助语言学、植物学、地理学和历史学，并不只是为了实用因素，更一个同样重要的原因，在于科学能够从思想上让帝国合理化。
科学家为帝国提供了各种实用知识、思想基础和科技工具，要是没有他们，欧洲人能否征服世界实在仍是未定之数。至于征服者报答科学家的方式，则是提供各种信息和保护，资助者各种奇特迷人的研究，而且将科学的思考方式传到地球的每一个偏远角落。如果没有帝国的支持，可能能否发展得如此蓬勃，也仍在未定之天。

第十六章资本主义教条

可以说整个现代经济就只是一场骗局。
我们可以看到整个运作就是基于信任着一种想象得未来，银行家和创业者相信面包店能成功，承包商也相信银行未来一定能把钱再还给他。

创业者的困境
没有面包店->没有面包->没有钱->没有承包商->没有面包店
现代经济的奇妙循环
对未来的信任->信用->支付给承包商->新的面包店->能够偿还贷款的面包->对未来的信任

前现代经济
信用信贷少->成长缓慢->对未来的信任少->信用信贷少
现代经济
信用信贷多->成长快速->对未来的信任多->信用信贷多

民间企业的获利正是社会整体财富和繁荣的基础。
人类全体财富的基础，就在于希望增加个人利润的自私心理。
现代资本主义的一大重点：应该把利润拿出来，继续投资生产。
在过去几年，我们看到银行和政府疯狂的印钞票。每个人都担心经济危机让经济停滞不前，于是他们无中生有的印了数亿的美元、欧元和日元，让金融体系凭空出现一大笔便宜信贷，只盼望着科学家、技术人员和工程师能够在经济泡沫破灭之前，设法想出得以力挽狂澜的创世发明或发现。

哥伦布也需要金主
帝国主义的奇妙循环：信贷资助新发现，新发现带来殖民地，殖民地带来利润，利润建立起信任，信任转化为更多的信贷。
荷兰的西印度公司占了个地，名为“新阿姆斯特丹”，遭受原住民威胁，英国人也多次入侵，1664落入英国手中。改民为“纽约”（New York）。西印度公司曾在殖民地筑起了一道墙，用来抵御英国人和美国原住民，这道墙的位置现在成了世界上最著名的街道：华尔街（Wall Street）。
Leo：欧洲人起名字咋就这么没有创意
正如马克思和其他社会批评家所开的玩笑，西方政府几乎就像是资本家的工会。
1840年，英国正式以“自由贸易”为名，向中国宣战。
埃及也同样遭到了英国资本主义的毒手。1881年，埃及民族主义者仍无可忍，起身反抗，单方面宣布废除一切外债。这让维多利亚女王很不高兴。一年后，派大军前往尼罗河，一直到二战结束前，埃及还是英国的“保护国”。
资本和政治两者紧密相拥，对信贷市场有深远的影响。
英国资本家投资高风险海外交易的意愿很高，如果外国债务人拒绝偿还贷款，女王陛下的军队就会为他们讨债。
对自由市场的崇拜。资本家对政府的建议，和老庄思想不谋而合：无为而治，什么都别管。
努力贸易这场灾难的罪魁祸首并不是暴君或是种族主义者，而是不受限制的市场力量。
这是自由市场资本主义美中不足之处。它无法保证利润会以公平的方式取得或者以公平的方式分配。而且相反的是，因为人类有追求利润和经济成长的渴望，就会决定盲目扫除一切可能的阻挠。
经济大饼会无限制变大吗？每块饼都需要原材料和能源。

第十七章工业的巨轮

因为所有能量的转换只能靠人类和动物的身体，当时几乎所有人类活动靠的就是肌肉的力量。
蒸汽机，热能转化为动能了。
内燃机，彻底改革了人类的运输，也让石油变成一种液体的政治权力。数千年前，我们用石油为屋顶防水、替轴轮润滑。
学习如何有效驾驭和转化能量之后，也解决了另一个阻碍经济成长的问题：原料短缺。
工业革命最重要的一点，其实在于它就是第二次的农业革命。
大西洋奴隶贸易并非出于对非洲人的仇恨，而现代畜牧业也同样不是出于对动物的仇恨。这两者背后共同的推手，就是冷漠。
除了物质需求之外，猴子必然还有种种心理需求和欲望，如果未能满足这些需求，就会产生严重的负面影响。
为了确保不管什么新产品都有人买账，就出现了一种新的伦理观：消费主义。
这套理论成功了。我们都成了乖巧的消费者，买了无数种我们并不真正需要的产品，而且有的根本就是昨天才知道的。
各种宗教节日（例如圣诞节）都成了购物节。
Leo：原来西方也这个样
美国每年为了节食所花的钱，已经足以养活其他地方所有正在挨饿的人。
资本主义和消费主义的伦理可以说是一枚硬币的正反两面，将这两种秩序合二为一。有钱人的最高指导原则是“投资”，而我们这些其他人的最高指导原则是“购买”。

第十八章一场永远的革命

事实上，这场生态危机甚至也可能危机智人本身的生存。
很多人称呼这是“自然的毁灭”。然而，这其实并不能算是“毁灭”，而只是“改变”。自然是无法“毁灭”的。
1880年，英国政府立法规定全英国的时刻表都必须以格林尼治时间为准。这是史上第一次有国家采取了全国采取了全国统一的时刻表，要求人民依据人工的时钟来过生活，而不是依据当地的日升日落周期有所调整。
家庭和地方社群崩溃，改由国家和市场取代。
许多过去家庭和社群的功能，现在都被国家和市场取代。
现代高楼公寓，所有人各自锁在自己家里，连每户该付多少清洁费都无法达成共识，又怎么可能一起站起来抵抗国家机器？

前现代循环
国家和市场力量弱->个人力量弱->家庭和社群力量强->国家和市场力量弱
现代循环
国家和市场力量强->个人力量强->家庭和社群力量弱->国家和市场力量强

国家和市场对于权利义务的划分意见不同，个人又抱怨这两者要得太多，又给得太少。
仅仅过去两个世纪，我们就成了互相疏远的个人。这可以说是文化力量的最佳证明。
到了现代，核心家庭并未完全消失，还是留下了一些重要的情感功能。
国家同样也越来越介入家庭关系，特别是父母与子女的关系。
现代所兴起的两大想象社群，就是“民族”和“消费大众”。所谓民族，是国家的想象社群。而所谓的消费大众是市场的想象社群。
这并不是谎言，而是一场想象。
消费者彼此并不认识，但都有同样的消费习惯和兴趣，因此不但相信还定义大家就是同一伙的。
首先，战争的成本大幅上升。其次，正是因为战争的成本飙升，也就代表其利润下降。同时，虽然战争已经不再那么有利可图，但和平却成了一笔越来越划算的生意。最后一项重点，在于全球政治文化也有了结构性的大变动。四大因素形成了良性循环。
现在正面临着全球帝国的形成。而这个帝国与之前的帝国也十分类似，会努力维持着疆域内的和平。正因为全球帝国的疆域就是全世界，所以世界和平也就能得到有效的维持。

第十九章从此过着幸福快乐的日子

首先，得定义要测量得对象。一般对于快乐普遍接受得定义是“主观感到幸福”。
金钱确实会带来快乐，但是有一定限度，超过限度之后的效果就不那么明显。
疾病会短期降低人的幸福感，并不会造成长期的不快。
目前看来，对快乐与否的影响，家庭和社群要比金钱和健康来得重要。
虽然过去两个世纪间人类在物质条件上有了大幅改善，但因为家庭崩溃、社会失调，所以两者的作用很可能互相抵消。如果真是如此，现在的人并不见得比1880年更快乐。甚至是我们现在如此看重的“自由”，也可能是让我们不那么快乐的原因。
就像千年之前，先知、诗人和哲学家也早就说过，重要的是要知足，而不是一直想要得到更多。
不难想象，人类演化的结果，就是不会太快乐，也不会太痛苦。
已婚的人比单身和离婚的人更快乐，但不一定代表是婚姻带来了快乐，也有可能是快乐带来了婚姻。
快乐要看的是某人生命的整体；生命整体有意义、有价值，就能得到快乐。
佛教认为，快乐既不是主观感受到愉悦，也不是主观觉得生命有意义，反而是在于追求主观感受这件事。

第二十章智人末日

如果找出长得最肥的母鸡，再把它与动得最慢得公鸡交配，生出来的后代就会又肥又慢。
经过这样的智慧设计而出现，是因为人而不是神。
Leo：荧光绿的兔子，想想就吓人可怕，也不知道啥变态艺术家这种审美。
有三种方式可能让智慧设计取代自然选择：生物工程、仿生工程与无机生命工程。
许多人都认为，现在人类太快看到太多的机会，手中已经握有基因修改能力，却还无法做出明智、有远见的决定。
虽然我们目前确实还无法创造出超人类，但看来前方的路上也没有什么绝对无法克服的科技障碍。现在真正让人类研究放慢脚步的原因，在于伦理和政治上的争议。
人工视网膜，让盲人重获部分视力。将微芯片植入眼中，光感应器吸收光线，转化为电能，刺激视网膜上未受损的神经细胞，进而刺激大脑，转译为视觉影像。
Leo：现代科技也太发达了吧？仿生技术真心牛。
真正的大巫是吉尔伽美什计划以及未来创造出超人类的可能，将会为人类的伦理、社会和政治秩序带来巨幅改变。
未来科技的真正潜力并不是在于改变什么车辆或武器，而在于改变智人本身，包括我们的情感、我们的欲望。
科学怪人的故事直接向智人提出了挑战，告诉我们智人终结的一天已经不远。
但人类很难接受的一个事实就是，科学家不仅能够改造身体，也能改造心灵，未来创造出来的科学怪人可能就是硬生生比人类优秀不知凡几，他们看着我们，就像是我们看尼安德特人一样带着一种轻蔑和不屑。
如果我们还认为我们能够踩刹车、阻止让人类升级成另一种不同的物种，可能就太天真了。原因就在于，这些计划各有不同，但追根究底还是回到了对长生不死的追求。

欧拉项目 | 491题 | 能整除11的double pandigital number

发表于 2017-12-08 分类于数学，欧拉项目 Disqus：

491题链接

一个数，使用两次0-9这十个数字，被称为double pandigital number，那么有多少个这能被11整除的double pandigital number呢？

首先我们要明白，遍历所有的double pandigital number，然后再看看是否能整除11这种直接的暴力算法肯定是不行的，因为double pandigital number数太多了，大约是20!/(2^10)*0.9。
那怎么办呢？先考虑能被11整除的数的性质，奇位数的数字之和减去偶位数的数字之和，能被11整除。
所以，我们不需要精确的知道数字是多少，只要通过排列组合知识，把满足题意的数字的个数计算出来就好。

从20个里面选择10个数字作为奇位数上的数字，C(20, 10) = 184756，这个量级做循环操作还是能搞定的。
选出了奇位数的数字，很容易就能得到偶位数的数字。
有了这些数字我们就能通过排列组合的知识来计算个数了。
如果没有数字重复，结果是10!，每出现一个数字重复，就除以2（重复数字交换，还是同一个数字）。
这里忽略了两个问题。
一个是0开头的没有被排除，不管怎么折腾，总会有0在第一位，所以把总结果乘以0.9就好了。
第二个问题是，选择出来的奇位数可能重复，因为我们传入的参数有两个0，两个1，等等，对于组合算法来说，选择第一个0和选择第二个0是两种不同的组合，但是对于我们组成数字来说，没有区别，所以我们还需要一个集合，记住那些被计算过了的被选择出来的奇位数。

public static long GetAnswer()
{
    long ret = 0;
    HashSet<string> combinations = new HashSet<string>();
    var allDigits = new List<int> { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 };
    var odds = Utils.Combination(allDigits, 10);

    foreach (var odd in odds)
    {
        int sum = odd.Sum();
        if (sum == 23 || sum == 34 || sum == 45 || sum == 56 || sum == 67)
        {
            string com = string.Join("_", odd);
            if (!combinations.Contains(com))
            {
                combinations.Add(com);
                var even = GetRemainNumbers(odd);
                ret += GetPCount(even) * GetPCount(odd);
            }
        }
    }

    return ret * 9 / 10;
}

private static long GetPCount(IEnumerable<int> source)
{
    long ret = Factorial10;
    int n = 10 - source.Distinct().Count();
    for (int i = 0; i < n; i++)
    {
        ret /= 2;
    }
    return ret;
}

private static IEnumerable<int> GetRemainNumbers(IEnumerable<int> subtracter)
{
    var bits = new bool[20];
    foreach (var bit in subtracter)
    {
        if (bits[bit * 2])
        {
            bits[bit * 2 + 1] = true;
        }
        else
        {
            bits[bit * 2] = true;
        }
    }

    var ret = new List<int>();
    for (int i = 0; i < bits.Length; i++)
    {
        if (!bits[i])
        {
            ret.Add(i / 2);
        }
    }

    return ret;
}

欧拉项目 | 77题 | 分解成质数之和

发表于 2017-11-04 分类于数学，欧拉项目 Disqus：

77题链接

一个数，能够写成一些质数的和。比如，10可以写成下面五种不同的形式。

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

第一个能被写成大于5000种形式的数是都少呢？

退一步，给定一个数n，如何计算有多少种分解形式呢？这类似于经典的硬币有多少种找法。
硬币倒着排序对解题很有用，参考这种想法，可以先得到一堆质数，然后从小往大的排。
然后呢，找到小于等于n的质数，利用找硬币的算法得到次数。

private static int Count(int sum)
{
    int index = Array.BinarySearch(primes, sum);
    if (index < 0)
    {
        index = ~index;
    }

    return Count(sum, index);
}

private static int Count(int sum, int index)
{
    if (sum == 0)
    {
        return 1;
    }

    if (sum < 0 || index >= primes.Length)
    {
        return 0;
    }

    return Count(sum - primes[index], index) + Count(sum, index + 1);
}

这里利用了Array.BinarySearch的一个性质，如果没找到，返回的是应该在的位置取反，那么，如果n是质数，那么直接得到了index，如果不是质数，能够得到小于n的质数的位置。

有了Count函数，只需要从小往大遍历，找到第一个超过5000种分解形式的数。

private static int[] primes;
private static readonly int Max = 5000;

public static int GetAnswer()
{
    primes = Utils.GenPrimes(Max).Reverse().Select(l => (int)l).ToArray();
    for (int i = 2; i < Max; i++)
    {
        int count = Count(i);
        if (count >= Max)
        {
            return i;
        }
    }

    return 0;
}

2017 Q3 阅读计划总结

发表于 2017-10-22 分类于阅读 Disqus：

距离上次总结过去了2个月零十天，变化基本不大。

阅读，物理学基础公开课2和可汗宏观积极学两个公开课有条不紊的进行，男人来自金星女人来自火星貌似没有看哈哈。
计划：基本不变，男人女人，物理学基础公开课2，可汗宏观，有一个小变化是，安装了Kindle手机版/iPad版，有事没事可以看看以前买的电子书啥的。按照计划，物理学基础公开课2，可汗宏观是要完成的。

计算机，CLRS看到了13.3小节，然后切换到了SICP，从头开始，把之前没有做的习题弥补一下，速度还可以，很快就进入到了2.2小节。这里明确下，在未来很长的时间，CLRS，SICP和龙书（或者相关书籍）是焦点。
计划：SICP

数学，18.06学到了lecture 25，总共35课，按计划到11月能完成。
计划，完成18.06，之前18.01的配套课本，再就是该安排下2018的计划？

英语，单词在坚持，NEC2的homework完成到了76课（第三单元之后了），NEC3的预习也按期到了43课，也比进度快一点，主要是Global English过期且无法续期了，MS给换了一个平台，rosettastone，测试了下水平，居然蒙了8.1/10，系统推荐的一些课程，半年内(有效期)能学多少是多少吧。
计划，NEC2完成homework，NEC3预习完成，rosettastone。

顺便多说一句，又做了一道Project Euler上的问题，好开心啊，好假，以后有时间可以多思考。

不用临时变量交换两个数

发表于 2017-10-17 分类于计算机，算法 Disqus：

编写一个函数，不用临时变量，直接交换两个数。

很经典的一道题目，先直接给代码，然后再证明。

static void Swap(ref int a, ref int b)
{
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}

因为是bit操作，所以我们针对每个bit证明即可，不妨设a和b只有1个bit，总共只有4种可能性，使用穷举法来证明。

原始a	原始b	第一行a 第二行b	第三行a
0	0	0	0	0
0	1	1	0	1
1	0	1	1	0
1	1	0	1	1

可以看出来，原始a和第二行左边的b是一样的，也就是最后的b值和初始的a值一样；原始b和第三行左边的a是一样的，也就是最后的a值和最初的b值一样。
综上，交换了a和b的值。

但是，这个解法有个bug，如果传入的是同一个地址呢？位异或操作后得到了0！

欧拉项目 | 187题 | 两个素数乘积

发表于 2017-10-15 分类于数学，欧拉项目 Disqus：

187题链接

一个合数可以分解成至少两个质数的乘积，很多合数只能分解成两个质数的乘积，比如9 = 3 * 3，10 = 2 * 5，小于10^8次方的数字中，有多少个能分解成两个质数相乘？9和10就是满足题意的，而12 = 2 * 2 * 3就是不满足题意的。

分解质因数是比较复杂的，但是给两个质数，得到乘积，看是否小于MAX还是很简单的。
进一步，我们没必要用两层for循环得到所有满足题意的数，只要知道有几个就可以了。
比如我们有一个质数p，得到比MAX/p小的质数的个数就可以了。
先生成一个系列的质数，二分查找得到MAX/p所在的位置即可。
下面是代码

public static long GetAnswer()
{
    var primes = Utils.GenPrimes(MAX / 2);
    long count = 0;
    foreach (var p in primes)
    {
        long m = MAX / p;
        int index = Array.BinarySearch(primes, m);
        if (index >= 0)
        {
            count += index + 1;
        }
        else
        {
            count += ~index;
        }
    }

    count += ~Array.BinarySearch(primes, (long)Math.Sqrt(MAX));

    return count / 2;
}

对于非完全平方数，我们在foreach里面计算了2次，对于完全平方数，我们只计算了一次，于是乎，再加一次完全平方数的个数，最后统一的除以2。

打印合法的括号组合

发表于 2017-10-13 分类于计算机，算法 Disqus：

实现一个算法，打印所有的合法的n对括号的组合。比如两对括号，(()) | ()()，两组解，三对括号，(()()) | ((())) | ()(()) | (())() | ()()()，共计五组解。

很明显，这是一个递归问题。每一次递归，我们向字符串中添加一个字符，左括号或者是右括号。如何决定添加的是左括号还是右括号呢？只要还有剩余的左括号，总是可以往里面添加的；至于右括号则不然，只有当前字符串中左括号的数量比右括号大的时候，才能插入右括号，对应剩余的可插入括号来说，就是剩余的右括号比左括号的数量多。
我们使用两个参数来记录剩余的左括号和右括号数量，初始值都是N，用以表示上面分析的各个状态。

下面是实现代码：

static void AddParen(List<string> result, int leftRem, int rightRem, char[] str, int index)
{
    if (leftRem < 0 || rightRem < leftRem) // invalid state
    {
        return;
    }

    if (leftRem == 0 && rightRem == 0)
    {
        result.Add(new string(str));
    }
    else
    {
        if (leftRem > 0)
        {
            str[index] = '(';
            AddParen(result, leftRem - 1, rightRem, str, index + 1);
        }

        if (rightRem > leftRem)
        {
            str[index] = ')';
            AddParen(result, leftRem, rightRem - 1, str, index + 1);
        }
    }
}

static List<string> GenerateParens(int n)
{
    char[] str = new char[n * 2];
    var result = new List<string>();
    AddParen(result, n, n, str, 0);
    return result;
}

第十四章 发现自己的无知

第十五章 科学与帝国的联姻

第十六章 资本主义教条

第十七章 工业的巨轮

第十八章 一场永远的革命

第十九章 从此过着幸福快乐的日子

第二十章 智人末日