以图明志

计算机数学与基础

把数学踢出高考,那么谁家的孩子该学数学?

追求纯粹知识和理性
上一个月,网络上先是在讨论“把英语踢出高考”,但有人说,英语比数学重要,学好英语才好出国,好移民,语云,“英语记不牢,终身在天朝”。后来话题就转换成“把数学踢出高考”了。后者获得的响应比前者高。还有网站搞了个投票,投票的结果是七成在“踢数学”。“除了数钱,一辈子没有再用到数学”,这个说法很有感染力,“踢数学”本身会带来快乐,可以发泄另外的情绪。

编程思想

再谈PHP、Python与Ruby

语言选择问题
编程语言非常重要,不要认为他们都图灵等价,用起来都一样。实际上,好的语言,带给你的东西是超乎想像的。优雅的抽象胜于简单的堆砌: 这意味着你的代码是最简洁而又充满设计感的,面向对象,容易的闭包,一切都是表达式等等,而最好的抽象是语言本身能够分层,既能够书写语言的语言,比如 DSL 能力强弱是个指标。

编程思想

开始学习函数式编程后对编程的一些新感受

工具与方法
最近开始学习函数式编程,打算深入进去,掌握函数式编程的思路。具体学习足迹可以看看 现代魔法学院的《编程范式篇》。以后关于技术类的东西,大部分都会整理成专题,章节,发布在学院中,而博客则回归更为轻松随意的状态。我们绝大多数程序员都是用命令式编程,因为学校教的编程就是命令式的,什么C、Java等等(当然他们也可以用函数式编程)。

编程思想

编程范式,程序员的编程世界观

编程范式的重要性
编程范式(Programming Paradigm)是某种编程语言典型的编程风格或者说是编程方式。随着编程方法学和软件工程研究的深入,特别是OO思想的普及,范式(Paradigm)以及编程范式等术语渐渐出现在人们面前。面向对象编程(OOP)常常被誉为是一种革命性的思想,正因为它不同于其他的各种编程范式。编程范式也许是学习任何一门编程语言时要理解的最重要的术语。

编程思想

常见编程语言对REPL支持情况小结

REPL(Read-eval-print-loop)
最近跟一个朋友聊起编程语言的一些特性,他有个言论让我略有所思:“不能REPL的都是渣”。当然这个观点有点偏激,但我们可以探究一下,我们常用的编程语言里面,哪些支持REPL,哪些不支持,还有REPL的一些概况。在一般的脚本语言中,有REPL是常态,因为REPL非常的方便。

面向对象技术

为什么会有面向对象编程的产生?

从结构化编程说起
很久以前,软件开发的世界还是一片浑浑噩噩,不管开发什么软件都面临着复杂性这个问题,代码里面到处是goto语句,程序的流程随意跳转。众生写代码时,越写到后面越不知道自己写的是什么。这时候出现一位巨人,它就是结构化编程。

计算机数学与基础

计算机是怎么启动起来的?

一个非常复杂的过程
从打开电源到开始操作,计算机的启动是一个非常复杂的过程。我一直搞不清楚,这个过程到底是怎么回事,只看见屏幕快速滚动各种提示...... 最早的时候,工程师们用它来比喻,计算机启动是一个很矛盾的过程:必须先运行程序,然后计算机才能启动,但是计算机不启动就无法运行程序!

计算机算法

快速排序里的学问:随机化快排

选择随机数作为枢纽元
一般来说随机选取枢纽元这种策略非常安全,除非随机数生成器有问题(这不像你所想象的那么罕见),因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面,随机数的生成一般是昂贵的,根本减少不了算法其余部分的平均运行时间。算法与前面《算法导论》里的例子差不多,只是在调用分割Partition时加入一个随机数,具体可以参看程序。

计算机算法

快速排序里的学问:枢纽元选择与算法效率

枢纽元选择也有学问
通常的、没有经过充分考虑的选择是将第一个或最后一个元素用作枢纽元。如果输入是随机的,那么这是可以接受的,但是如果输入是预排序的或者是反序的,那么这样的枢纽元就产生一个劣质的分割,因为所有的元素不是被划入S1就是被划入S2。更有甚者,这种情况发生在所有的递归调用中。

计算机算法

快速排序里的学问:霍尔快排的实现

霍尔快排的C语言实现
专题的前一篇讲了快速排序的始祖——霍尔快排,那么这里就简单地实现以下霍尔快排。补充说明下,快排的一个核心步骤是选取枢纽元,通常的做法是将第一个元素用作枢纽元,《算法导论》里的快排例子和Hoare快排都是这种枢纽元选择。排序的思路是,选定一个枢纽元,比枢纽元大的全部丢到右边,比枢纽元小的全部丢到左边。

计算机算法

快速排序里的学问:霍尔与快速排序

再次深入理解快速排序
霍尔 (Sir Charles Antony Richard Hoare) 是一位英国计算机科学家,他是著名的快速排序 (QuickSort) 的发明者。在平均状况下,排序 n 个项目要Ο(n log n) 次比较,而且通常明显比其他Ο(n log n) 演算法更快。所以它是一个被广泛使用的算法。在一次采访中,霍尔谈到了发明这个算法的背景。

计算机算法

快速排序里的学问:快速排序的过程

理解快速排序的工作机制
通过前面问题以及引入了“信息熵”的概念,我们可以重新来理解排序的本质:一组未排序的N个数字,它们一共有N!种重排,其中只有一种排列是满足题意的(譬如从大到小排列)。换句话说,排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”,这就相当于猜数字游戏里面的一个问句。

计算机算法

编程之美2.3笔记:寻找发帖“水王”

降低问题规模的思想
抽象就是从问题中提取有用的,本质的特征,然后将问题用一个简洁但包含同样信息的模型表示出来。复杂的问题经抽象后,可能会变成一个简单的问题,也可能会变成一个曾经遇到的问题,当然也可能仍然是复杂的问题。不管抽象后得到的结果是哪一种,看着抽象后的问题,想出解的可能性必然比直接看原题想的可能性大。

计算机算法

快速排序里的学问:信息熵

从信息熵角度去理解问题
信息是个很抽象的概念。人们常常说信息很多,或者信息较少,但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年,香农提出了“信息熵”的概念,才解决了对信息的量化度量问题。一条信息的信息量大小和它的不确定性有直接的关系。比如说,我们要搞清楚一件非常非常不确定的事,或是我们一无所知的事情,就需要了解大量的信息。

计算机算法

快速排序里的学问:再看看称球问题

根据问题选择N分法
12个小球,其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。这个问题是一道流传已久的智力题。网络上也有很多讲解,还有泛化到N个球的情况下的严格证明。也有零星的一些地方提到从信息论的角度来看待最优解法。本来我一直认为这道题目除了试错之外没有其它高妙的思路了,只能一个个方法试,然后看看哪种方案最少。

计算机算法

快速排序里的学问:从猜数字开始

猜数字里的算法思想
我们先来玩一个猜数字游戏:我心里默念一个1~64之间的数,你来猜(你只能问答案是“是”或“否”的问题)。为了保证不论在什么情况下都能以尽量少的次数猜中,你应该采取什么策略呢?很显然,二分。先是猜是不是位于1~32之间,排除掉一半可能性,然后对区间继续二分。
1 / 22 首页 < Prev 1 2 3 4 5 Next > 尾页 页码: