《像程序员一样思考》

引言

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

三个经典难题

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

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

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

基本的问题解决技巧

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

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

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

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

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

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

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

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

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

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

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

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

用递归解决问题

大递归思路:如果在编写代码时采用某种约定,可以假装并没有发生递归。最好应用于难以用迭代解决方案的场合,如回溯。编写调度器就遵循两个规则,(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 条评论
登录 后参与评论

相关文章

来自专栏C语言C++游戏编程

「C语言」编程学习—控制语句goto语句解析!

C语言共有9种控制语句:if/else,for,while,do-while,switch/case,break,continue,return,goto。

1083
来自专栏大数据文摘

手把手:四色猜想、七桥问题…程序员眼里的图论,了解下?(附大量代码和手绘)

4974
来自专栏牛客网

深信服一面C++

Linux中创建共享内存的方式?共享内存中起始地址是不是按照页的大小对齐?创建共享内存的时候物理页一定分配吗?惰性空间分配的实现方式?

1222
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 复杂度分析

大家都知道数据结构和英语,就如同程序员的两条腿一样;只有不断的积累,学习,拥有了健壮的“双腿”才能越走越远;在数据结构和算法的领域,不得不承认自己就是一只菜...

1363
来自专栏Java帮帮-微信公众号-技术文章全总结

Java案例-贪吃蛇小游戏

Java案例-贪吃蛇小游戏 先来看看,这个游戏的截图。 ? 这里可以自定义难度系数(其实就是蛇自己移动的速度),共分10级。这里后面我会说实现方法,这都可以改...

6097
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列03:逆序打印单链表

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

721
来自专栏程序员的SOD蜜

“法天象而应四时”--茶话软件开发之“抽象”(2)--过程的抽象:函数

本想写这样的一个系列的,无奈一直没有时间,没想到网上已经有人写了类似的文章,说明了我原来的观点: 函数既是过程的抽象! 当然,函数的抽象意义远非如此简单,这里先...

1999
来自专栏TechBox

数据结构与算法系列之绪论前言什么是数据结构算法

1432
来自专栏数说工作室

统计师的Python日记【第八天:数据清洗(2)文本处理】

本文是【统计师的Python日记】第8天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函数、...

5806
来自专栏程序员与猫

使用抽象类和接口的优解

821

扫码关注云+社区