我们为什么会这样思考来找到最快的方法？ 问题空间： 我们所观察到的对象 (每个对象的状态及其变化) 第一种方案： 第二种方案： 几乎每次压缩问题空间到一半 几乎每次压缩问题空间到三分之一
我们为什么会这样思考来找到最快的方法？ 第一种方案: 问题空间： 我们所观察到的对象 (每个对象的状态及其变化) 第二种方案: 几乎每次压缩问题空间到一半 几乎每次压缩问题空间到三分之一√
如何表达我们的这个思想？写个程序！ Procedure Findlt(n){ ∥从n个硬币中找出一个较轻的假币 if n=2{ ∥只有两个硬币 天平上翘起的是假币；程序结束； } if n=3{ ∥有三个硬币 任取两个放在天平上： 如果平衡，假币为第三个，否则为翘起的天平端硬币；程序结束； else{ 川有多于三个硬币 将硬币分为几乎数量相同的三堆n1,n2,n3; /其中必定有两堆数量相同 称量其中数量相同的两堆； /不妨假设n1=n2 如果两堆不同重{ /不妨假设n1堆轻 Findlt(n1); else Findlt(n3); }
如何表达我们的这个思想？写个程序！ Procedure FindIt(n) { //从n个硬币中找出一个较轻的假币 if n=2 { //只有两个硬币 天平上翘起的是假币；程序结束； } if n=3 { //有三个硬币 任取两个放在天平上； 如果平衡，假币为第三个，否则为翘起的天平端硬币；程序结束； } else { //有多于三个硬币 将硬币分为几乎数量相同的三堆n1,n2,n3； //其中必定有两堆数量相同 称量其中数量相同的两堆； //不妨假设n1=n2 如果两堆不同重 { //不妨假设n1堆轻 FindIt(n1); } else FindIt(n3); } }
到此为止，这个问题我们解决了吗？ No! 我们还应该至少回答这些问题： 你能证明你的解法是正确的吗？ 你能证明你的解法是最优的吗？ 你能证明你的程序没有错误吗？ 9/24/2015
到此为止，这个问题我们解决了吗？ No！ 我们还应该至少回答这些问题： 你能证明你的解法是正确的吗？ 你能证明你的解法是最优的吗？ 你能证明你的程序没有错误吗？ 9/24/2015
再一个互动游戏： 统计到场人数： 0,所有人都站起来，每个人都握有一个 数字：1 1,每两个人组成一组，将手中数字相加， 并记住。其中一人坐下； •2，重复第一步，直到教室中只有一人； 3,最后一人，大声报出数字；
再一个互动游戏： •统计到场人数： •0，所有人都站起来，每个人都握有一个 数字：1 •1，每两个人组成一组，将手中数字相加， 并记住。其中一人坐下； •2，重复第一步，直到教室中只有一人； •3，最后一人，大声报出数字；
这个游戏，给了我们什么启发？
这个游戏，给了我们什么启发？