滚动硬币的启示

《不要大惊小怪》是本有趣的小册子,引言中的例子就引人深思。题目虽然很容易,但抽取出背后的想问题的动机和方法却需要过去有一定量的实践和反思。原文的题目问:有两枚一模一样的硬币,它们半径相等,并排靠在一起,其中一枚固定不动。开始时一枚硬币上的箭头向上,将它沿着另一枚硬币的边缘无滑动地滚动,一直滚到这枚固定硬币的另一侧。那么现在滚动过来的硬币上那个箭头是向上还是向下?直觉上想起来转了半圈,那应该是向下吧 … 继续阅读

图灵停机问题的两种符号表述

年中在读《量子计算与量子信息原理》的时候,写了一篇《图灵停机问题的一个简单论述》的阅读笔记,对大学时没学明白的图灵停机问题有了一些基本认识。今天在读《复杂》的时候,里面采用了另外一种等价的说法,在符号形式上看起来略有差异,如今记录一下加深印象。回顾量子一书中的描述,先假设存在算法A具有判定任意算法是否能够停止运算的能力,用符号表述也就是对于算法T输入mh,可以停止运算时,A回答是A(T(mh))= … 继续阅读

求数组的子数组之和的最大值

——尾递归的应用这是《编程之美》中2.14节提出的一个问题,问题的描述为一个有N个整数元素的一维数组(A[0], A[1], …, A[n-2], A[n-1]),这个数组有很多子数组,那么子数组之和的最大值是什么?以往遇到这种问题的第一种思维模式也像书中的第一种解法一样去枚举出所有的子数组,对每个子数组内部元素求和,然后找出所有和中最大的。这是一种分解问题的思路,但所分解的子问题已经 … 继续阅读

尾递归的启示

——读《计算机程序的构造和解释》第一章第二小节所想尾递归是指在过程调用中,递归调用过程本身的操作始终是过程的最后一步。举例来讲,计算阶乘的方法,根据定义,直接翻译成递归形式为def factorial(n):  if n == 1:    return 1  else:    return n * factorial(n-1)这个递归中,最后一步操作是乘法,而非调用过程本身,因而不是尾递归。转换成 … 继续阅读