04 | 数学归纳法：如何用数学归纳提升代码的运行效率？

精选留言(67)

• 

  oddrock

  递归把计算交给计算机，归纳把计算交给人，前者是拿计算机的计算成本换人的时间，后者是拿人的时间换计算机的计算成本

  作者回复: 精辟的总结👍

  2018-12-18

  

   145
• 

  cafu_chino

  老师下次可以提供Python的代码示例吗？对Java的使用不是很熟练
  

  作者回复: 可以，后期会整理出来

  2018-12-17

  

   24
• 

  恋恋

  项目中还没碰到，但在以前做编程题时经常碰到找规律的问题，这时候只需抽象出一个公式即可。
  另外可否给老师提个建议，就是在github上建一个仓库，这样我们可以fork下来，用自己熟悉的编程语言把老师讲的思路写进代码里push上去，方便大家相互学习 ^_^

  作者回复: 这是个好建议，我先问下是否版权问题

  2018-12-17

  

   12
• 

  陈诚

  个人觉得有时候虽然用迭代和递归都能解决问题，但是使用递归时，由于有数学归纳法保证递归关系的正确性，所以只要专注于解决2个相邻层的关系就可以了，然后使用数学归纳法的基本情况作为递归出口。当然，在实际编程中，递归会增加函数调用栈的开销，也是要考虑的一方面

  2018-12-17

  

   12
• 

  陈诚

  我觉得加深学习数学效果的方式，就是自己实现一遍，我这里用C语言实现了一下递归求麦粒总数的问题以求抛砖引玉
  #include <stdio.h>
  #include <stdlib.h>
  
  struct result {
  long cur_grid_wheat;
  long sum_of_wheat;
  };
  
  struct result wheat(int grid)
  {
  struct result rst;
  
  if (grid == 1) {
  rst.cur_grid_wheat = 1;
  rst.sum_of_wheat = 1;
  } else {
  struct result last_rst;
  last_rst = wheat(grid - 1);
  rst.cur_grid_wheat = last_rst.cur_grid_wheat * 2;
  rst.sum_of_wheat = last_rst.sum_of_wheat + rst.cur_grid_wheat;
  }
  
  return rst;
  }
  
  int main(int argc, char *argv[])
  {
  struct result rst;
  int grid_index = 0;
  
  if (argc != 2) {
  printf("Usage: %s grid_index\n", argv[0]);
  return -1;
  }
  grid_index = atoi(argv[1]);
  
  rst = wheat(grid_index);
  
  printf("grid_index: %d\ncur_grid_wheat: %ld\nsum_of_wheat: %ld\n",
  grid_index, rst.cur_grid_wheat, rst.sum_of_wheat);
  
  return 0;
  }
  
  

  2018-12-19

  

   9
• 

  mikukuma

  数据归纳法通俗易懂的说法就是一个个经典的数学公式的证明。我们要去证明这个公式是否正确，需要根据两个步骤，1：n=1时，公式是否正确；2: 假设n = k-1成立，那么去证明n=k公式是成立的。就跟数学做证明题一样的思路。然后我们去做这些算法题的时候，就可以直接根据已经证明的公式，很快就能得到我们需要的答案。

  2018-12-17

  

   7
• 

  WL

  老师我感觉递归和归纳法还是有些区别的, 递归是自顶向下的拆解问题, 直到终止条件后再一层层返回结果, 但是归纳法好像没有自顶向下拆解问题的这个环节.

  2018-12-17

  

   6
• 

  予悠悠

  可以给老师提个建议吗？课程里提到的关键概念可不可以加上英文名呢？例如这篇里提到的迭代，递归，正向递推，逆向递推

  作者回复: 好，后面会加注，感谢建议

  2019-01-19

  

   5
• 

  鱼鱼鱼培填

  用Python实现数学归纳法，一开始使用math.pow()函数发现不对，Python中该函数会使用科学技术法导致结果出错
  #-*- coding:UTF-8 -*-
  class result(object):
  wheatNum = 0
  wheatTotalNum = 0
  
  class getWheatTotalNum(object):
  '''
  函数说明：使用递归嵌套， 进行数学归纳法证明
  Param： k - 表示放到第几格 result - 表示当前格子的麦粒数
  Return: boolean - 放到第K格时是否成立
  '''
  def prove(self, k, result):
  if k == 1:
  if (2 ** 1 - 1) == 1:
  result.wheatNum = 1
  result.wheatTotalNum = 1
  return True
  else:
  return False
  
  else:
  proveOfPreviousOne = self.prove(k - 1, result)
  result.wheatNum *= 2
  result.wheatTotalNum += result.wheatNum
  proveOfCurrentOne = False
  if result.wheatTotalNum == (2 ** k - 1):
  proveOfCurrentOne = True
  if (proveOfPreviousOne & proveOfCurrentOne):
  return True
  else:
  return False
  
  
  if __name__ == '__main__':
  grid = 64
  result = result()
  g = getWheatTotalNum()
  print(g.prove(grid, result))

  作者回复: 研究了细节，很赞👍

  2018-12-19

   1

   5
• 

  田野

  关于这节课讲的内容在编程中具体的应用能这样理解不？ 迭代法在实际应用中，如果迭代层次过深 ，会导致各种问题(耗时\内存占用等) ，遇到这种情况可以总结规律， 使用数学归纳法将其简化。(代码中不再使用迭代 使用数学归纳总结出来的结果)

  作者回复: 是的，特别是递归的实现比较耗资源

  2018-12-17

  

   5
• 

  失火的夏天

  个人觉得动态规划就是归纳法思想的处理，一个问题分解为多个字问题的最优解

  2018-12-17

  

   4
• 

  lkj

  递归还有一个就是搜索目录文件，编程递归第一个练习就是这个
  递归过程判断事目录还是文件，目录就继续递归，文件就根据缩进打印，最终打印出目录结构

  作者回复: 是的👌

  2019-05-25

  

   3
• 

  microsnow

  <?php
  
  class Result
  {
      public $wheatNum = 0;
      public $wheatTotalNum = 0;
  }
  
  class Lession4_2
  {
  
      public $result = NULL;
  
      public function __construct()
      {
          $this->result = new Result();
      }
  
      public function getResult()
      {
          return $this->result;
      }
  
      public function prove($n)
      {
          if ($n == 1) {
              if ((pow(2, 1) - 1) == 1) {
                  $this->result->wheatNum = 1;
                  $this->result->wheatTotalNum = 1;
                  return true;
              } else {
                  return false;
              }
          } else {
              $proveOfPreviousOne = $this->prove($n - 1);
              $this->result->wheatNum *= 2;
              $this->result->wheatTotalNum += $this->result->wheatNum;
              $proveOfCurrentOne = false;
              if ($this->result->wheatTotalNum == (pow(2, $n) - 1)) $proveOfCurrentOne = true;
              if ($proveOfCurrentOne && $proveOfPreviousOne) {
                  return true;
              } else {
                  return false;
              }
          }
      }
  }
  
  $a = new Lession4_2();
  $result = $a->prove(13);
  $result = $a->getResult();

  作者回复: 我对php语言不熟悉，你能否贴一下运行的结果？

  2018-12-29

   1

   3
• 

  未明。

  数字全变成了math_progress_error了

  2018-12-17

  

   3
• 

  仁

  老师~我没有学习JAVA，只学了C++和python。。。请问能否多发几种语言的代码哈

  作者回复: 好的 后面我会统一加上

  2019-01-06

  

   2
• 

  fcb的鱼

  每节课后可以多留一些编程题，每节课就2个例子感觉不过瘾！

  2018-12-25

  

   2
• 

  十指流玉

  老师您好！如果有一些程序我们自己归纳出了规矩，那如何快速的应用到程序中呢，还是说程序中本身就有一些函数就是归纳法的体现？

  作者回复: 这里你说的“有一些程序我们自己归纳出了规律”，具体是指什么？

  2018-12-25

  

   2
• 

  zh

  想起罗斯的故事，1-100 的所有数求和，罗斯的方法就是数学归纳法的简单应用。平时还没有需要用到归纳法，递归方法也很少用。

  作者回复: 你是说高斯的故事吧😀

  2018-12-24

  

   2
• 

  zack

  数据格式有问题 不知道是老师写错了还是给出了不兼容格式

  作者回复: 请问具体是哪个数据格式？

  2018-12-20

  

   2
• 

  TryTs

  老师，您讲这些数学知识的时候能不能更加深入一点，最好能够结合工程项目或者一些著名的库函数呢？

  作者回复: 后面会结合更多实际的项目。至于你说的库函数，具体是指哪方面？能否举个例子？

  2018-12-19

  

   2