《像程序员一样思考》

引言

  《像程序员一样思考》是一本训练程序员编程思想的指导书。本书以向个经典难题开篇,提出一些编程中常用的思想方法,如重述、类比、划分、消减等。同时也提供一些具体的技巧,如利用数组、指针动态内存、类解决问题。着重提出了大递归的思想,以及善假于外物的思路。本书注重程序员自信心的培养,提倡利用现有方法解决未知问题的同时,也鼓励探索式自主学习新技术。

三个经典难题

狐狸、鹅和玉米过河问题:用重形式化的方式重述问题,更好地洞察问题。以程序化方式列出所有的操作,从而发现“被隐藏的”的可能操作,将这些方法操作进行自由组合得到目标结果。认识到思考问题很可能与思考解决方案具有相同的工作效率,甚至更胜一筹。

瓷砖滑块移动问题:无法规划完整的解决方案并不意味着就无法采取策略或技巧系统性地解决问题。可以将问题进行细分,划分成细小部分,对其简单版问题进行研究发现一种常用技巧(“串列”),解决简单版后依次增加难度还原问题步步解决。

数独填词问题:“最大约束变量”。寻找问题约束性最强的部分,虽然约束条件往往使问题难以着手,但它们也可以消除很多选择、简化思路。如数独填词中搜索那些可能出现的值最少的空格。如果问题的某个部分具有很强的约束条件,很可能应该从这一部分开始着手,就不用担心把时间花在将来可能会返工的任务上了。

基本的问题解决技巧

制订计划:事先必须制订计划,而不是直接进行漫无方向的尝试。

重述问题:用不同的方式或术语阐述,重新审视问题,发现新思路。

划分问题(分治法):找到一种方式把一个问题的解决方案划分为几个步骤或几个阶段,可以使问题更容易解决。

从自己所知的开始:在编程在解决问题时,尽量从自己知道的部分开始着手。当用自己所掌握的技巧对一个问题进行研究时,可以更好地理解这个问题本身以及它的最终目标。

消减问题:当面临一个无法解决问题时,通过消减可以消减问题的范围。可以添加或取消约束条件,产生一个自己知道如何解决的问题。消减后的问题与原问题仍有相当多的共性,会使我们向最终的解决方案更进一步。消减问题允许我们准确地理解剩余的难点位于何处。

寻找类比:类比就是一个当前问题和一个已经解决的问题之间的相似性。其前提是已经拥有大量的解决方案可供参考。

试验:试验是一种可控的过程。我们假设当某些代码执行时将会发生什么,然后对它进行实验,观察自己的假设是否正确,根据这些观察,可以获得一些信息,帮助自己解决原先的问题。另一种形式的试验与调试相似。

避免陷入挫折感:挫折感会不断恶化,很可能一开始轻度焦虑变成最终难以遏制的烦躁。方法:首先制订计划;其次,可以休息一会儿。

用数组、指针、类解决问题

什么时候使用数组:一维数组还是多维数组;数组最大长度是否确定;是否需要多次处理数据;是否有大量的随机访问。

什么时候使用指针:具有如下优点,运行时确定长度的数据结构,可改变长度的数据结构,内存共享。当需要利用指针一个或多个优点的时候才应该使用它。

:封装、代码利用、问题细分、信息隐藏、可读性、表达能力。

用递归解决问题

大递归思路:如果在编写代码时采用某种约定,可以假装并没有发生递归。最好应用于难以用迭代解决方案的场合,如回溯。编写调度器就遵循两个规则,(1)调度器必须完整地处理最简单的情况,而无需再调用迭代函数;(2)当调度器调用迭代函数时,必须向它传递问题的更简单版本。

对树和图这样的分支结构的遍历在本质上是递归的,处理像数组和链表这样的线性数据结构则通常不需要使用递归,但是也有例外。

常见错误

  • 过多的参数:程序员常常陷入到尾递归模式上。关递归技巧可以减少递归调用所传递的数据量,而尾递归可能导致向递归调用传递额外的数据。
  • 全局变量:在递归函数中,只要有可能,应该尽量避免使用全局变量。全局变量会使代码不容易理解和不容易维护。

递归应用于动态数据结构

递归常常应用于像链表、树和图这样的动态数据结构。数据结构越复杂,递归解决方案在简化代码方面所发挥的的作用也就越大。处理复杂的数据结构常常类似于在迷宫中寻找一条正确的出路。

递归和链表

单链表的递归处理通用计划如下,假设有一个链表L和一个问题Q:

  1. 如果L是最小情况,就直接设置一个默认值。否则……
  2. 使用一个递归调用为链表L的“剩余部分”(从L的第2个节点开始)产生Q的答案。
  3. 检查L的第1个节点的值。
  4. 使用前两个步骤的结果为整体的L产生Q的答案。

递归和二叉树

二叉树的递归处理通用计划如下,假设有一个树T和一个问题Q:

  1. 如果树T为最小规模,直接设置一个默认值。否则……
  2. 执行一个递归调用,为T的左子树回答问题Q。
  3. 执行一个递归调用,为T的右子树回答问题Q。
  4. 检查T的根节点的值。
  5. 使用上面的3个步骤的结果,为整体的T回答问题Q。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏怀英的自我修炼

Java漫谈5

吴军老师有在他的《硅谷来信》中分享过他对于人工智能的看法,吴老师就认为,人工智能不会发展成黑客帝国的那种恐怖境地,原因是当初科学家在创立计算机之前先把人类要解决...

3499
来自专栏张俊红

Python面向对象编程

1735
来自专栏程序员互动联盟

【面试宝典】谈谈面向对象

面试官:知道面向对象吧。 小白:嗯,知道,面想对象就是封装继承多态呀。 面试官:回答了一部分,还能谈谈除了封装、继承、多态之外的吗,比如说怎么抽象,抽象的思想是...

3818
来自专栏游戏开发那些事

【python游戏编程之旅】第七篇---pygame中的冲突检测技术

本系列博客介绍以python+pygame库进行小游戏的开发。有写的不对之处还望各位海涵。

871
来自专栏前端新视界

一道看似非常难的面试算法题

这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等(感谢博友提供的关于该问题的相关资料 划分问题)。由于时间仓促,加之面试时头昏脑涨,这道题...

2078
来自专栏申龙斌的程序人生

参加steemit数学x程式大赛(第八回)

前一段时间参加了Steemit社区的两个活动,比如“接龙”创作大赛,五个人根据几张图片素材编出一篇小说,事先没有任何沟通,人员报名之后,顺序是随机指定的,我第一...

2916
来自专栏C语言及其他语言

【优秀题解】1443:[蓝桥杯][历届试题]数字游戏 (C++)

2.第一次主角的数是1,那么sum=1,经过n次计数得到的数是主角的第二个数,再次经过n次计数得到的是主角的第三个数。第二个同学首先是+1然后得到自己的数,第三...

362
来自专栏CDA数据分析师

开工大吉:几个让你月薪3万+的excel神技能

来源:运营圈信息流广告 职场中经常会用到哪些函数? IF函数、SUMIF函数、VLOOKUP函数、SUMPRODUCT函数...... 小编总结了8个在工作中常...

3636
来自专栏一个会写诗的程序员的博客

用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

854
来自专栏C语言及其他语言

【每日一题】1443 [蓝桥杯][历届试题]数字游戏

每日一题,一年365天,想不成为大神都难! 题目描述 栋栋正在和同学们玩一个数字游戏。 游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数...

2965

扫码关注云+社区