xinyin025/learn.lianglianglee.com
1
0
Fork 0
mirror of https://github.com/zhwei820/learn.lianglianglee.com.git synced 2025-09-17 08:46:40 +08:00
Code Issues Actions Packages Projects Releases Wiki Activity
master
learn.lianglianglee.com/专栏/程序员的数学课/14 程序的循环：如何利用数学归纳法进行程序开发？.md.html
周伟 0f006e4e9b add
2022-05-11 18:57:05 +08:00

1287 lines
29 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!DOCTYPE html>
<!-- saved from url=(0046)https://kaiiiz.github.io/hexo-theme-book-demo/ -->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1.0, user-scalable=no">
<link rel="icon" href="/static/favicon.png">
<title>14 程序的循环：如何利用数学归纳法进行程序开发？.md.html</title>
<!-- Spectre.css framework -->
<link rel="stylesheet" href="/static/index.css">
<!-- theme css & js -->
<meta name="generator" content="Hexo 4.2.0">
</head>
<body>
<div class="book-container">
<div class="book-sidebar">
<div class="book-brand">
<a href="/">
<img src="/static/favicon.png">
<span>技术文章摘抄</span>
</a>
</div>
<div class="book-menu uncollapsible">
<ul class="uncollapsible">
<li><a href="/" class="current-tab">首页</a></li>
</ul>
<ul class="uncollapsible">
<li><a href="../">上一级</a></li>
</ul>
<ul class="uncollapsible">
<li>
<a href="/专栏/程序员的数学课/00 开篇词 数学，编程能力的营养根基.md.html">00 开篇词 数学，编程能力的营养根基.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/01 从计数开始，程序员必知必会的数制转换法.md.html">01 从计数开始，程序员必知必会的数制转换法.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/02 逻辑与沟通，怎样才能讲出有逻辑的话？.md.html">02 逻辑与沟通，怎样才能讲出有逻辑的话？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/03 用数学决策，如何规划好投入、转化和产出？.md.html">03 用数学决策，如何规划好投入、转化和产出？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/04 万物可数学，经典公式是如何在生活中应用的？.md.html">04 万物可数学，经典公式是如何在生活中应用的？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/05 求极值：如何找到复杂业务的最优解？.md.html">05 求极值：如何找到复杂业务的最优解？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/06 向量及其导数：计算机如何完成对海量高维度数据计算？.md.html">06 向量及其导数：计算机如何完成对海量高维度数据计算？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/07 线性回归：如何在离散点中寻找数据规律？.md.html">07 线性回归：如何在离散点中寻找数据规律？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/08 加乘法则：如何计算复杂事件发生的概率？.md.html">08 加乘法则：如何计算复杂事件发生的概率？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/09 似然估计：如何利用 MLE 对参数进行估计？.md.html">09 似然估计：如何利用 MLE 对参数进行估计？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/10 信息熵：事件的不确定性如何计算？.md.html">10 信息熵：事件的不确定性如何计算？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/11 灰度实验：如何设计灰度实验并计算实验的收益？.md.html">11 灰度实验：如何设计灰度实验并计算实验的收益？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/12 统计学方法：如何证明灰度实验效果不是偶然得到的？.md.html">12 统计学方法：如何证明灰度实验效果不是偶然得到的？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/13 复杂度：如何利用数学推导对程序进行优化？.md.html">13 复杂度：如何利用数学推导对程序进行优化？.md.html</a>
</li>
<li>
<a class="current-tab" href="/专栏/程序员的数学课/14 程序的循环：如何利用数学归纳法进行程序开发？.md.html">14 程序的循环：如何利用数学归纳法进行程序开发？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/15 递归：如何计算汉诺塔问题的移动步数？.md.html">15 递归：如何计算汉诺塔问题的移动步数？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/16 二分法：如何利用指数爆炸优化程序？.md.html">16 二分法：如何利用指数爆炸优化程序？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/17 动态规划：如何利用最优子结构解决问题？.md.html">17 动态规划：如何利用最优子结构解决问题？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/18 AI 入门：利用 3 个公式搭建最简 AI 框架.md.html">18 AI 入门：利用 3 个公式搭建最简 AI 框架.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/19 逻辑回归：如何让计算机做出二值化决策？.md.html">19 逻辑回归：如何让计算机做出二值化决策？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/20 决策树：如何对 NP 难复杂问题进行启发式求解？.md.html">20 决策树：如何对 NP 难复杂问题进行启发式求解？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/21 神经网络与深度学习：计算机是如何理解图像、文本和语音的？.md.html">21 神经网络与深度学习：计算机是如何理解图像、文本和语音的？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/22 面试中那些坑了无数人的算法题.md.html">22 面试中那些坑了无数人的算法题.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/23 站在生活的十字路口，如何用数学抉择？.md.html">23 站在生活的十字路口，如何用数学抉择？.md.html</a>
</li>
<li>
<a href="/专栏/程序员的数学课/24 结束语 数学底子好，学啥都快.md.html">24 结束语 数学底子好，学啥都快.md.html</a>
</li>
</ul>
</div>
</div>
<div class="sidebar-toggle" onclick="sidebar_toggle()" onmouseover="add_inner()" onmouseleave="remove_inner()">
<div class="sidebar-toggle-inner"></div>
</div>
<script>
function add_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.add('show')
}
function remove_inner() {
let inner = document.querySelector('.sidebar-toggle-inner')
inner.classList.remove('show')
}
function sidebar_toggle() {
let sidebar_toggle = document.querySelector('.sidebar-toggle')
let sidebar = document.querySelector('.book-sidebar')
let content = document.querySelector('.off-canvas-content')
if (sidebar_toggle.classList.contains('extend')) { // show
sidebar_toggle.classList.remove('extend')
sidebar.classList.remove('hide')
content.classList.remove('extend')
} else { // hide
sidebar_toggle.classList.add('extend')
sidebar.classList.add('hide')
content.classList.add('extend')
}
}
function open_sidebar() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.add('show')
overlay.classList.add('show')
}
function hide_canvas() {
let sidebar = document.querySelector('.book-sidebar')
let overlay = document.querySelector('.off-canvas-overlay')
sidebar.classList.remove('show')
overlay.classList.remove('show')
}
</script>
<div class="off-canvas-content">
<div class="columns">
<div class="column col-12 col-lg-12">
<div class="book-navbar">
<!-- For Responsive Layout -->
<header class="navbar">
<section class="navbar-section">
<a onclick="open_sidebar()">
<i class="icon icon-menu"></i>
</a>
</section>
</header>
</div>
<div class="book-content" style="max-width: 960px; margin: 0 auto;
overflow-x: auto;
overflow-y: hidden;">
<div class="book-post">
<p id="tip" align="center"></p>
<div><h1>14 程序的循环：如何利用数学归纳法进行程序开发？</h1>
<p>我们在上一讲提到程序有<strong>顺序、选择、循环</strong>这三大基本结构，而在这其中，循环是处理复杂运算最有效的一种结构。</p>
<p><strong>循环结构</strong>可以用短短几行代码，执行成千上万次的运算。从计算机编程的视角来看，循环结构又有三种实现方法，分别是 for 循环、while 循环和 do while 循环；而从数学视角来看，循环结构很像是<strong>数学归纳法</strong>。</p>
<p>所以这一讲，我们就从数学的视角来重新看待循环结构。</p>
<h3>从“多米诺骨牌”看循环归纳思想</h3>
<p>在多米诺骨牌的游戏中，游戏者手动推倒第一个骨牌，接着第一个骨牌就会撞倒第二个骨牌，第二个骨牌还会撞倒第三个骨牌。以此类推，即使骨牌数量再多，也会逐一被放倒。</p>
<p>我们对多米诺骨牌全部放倒的结果进行剖析，你会发现它成立的条件有以下两个：</p>
<ul>
<li>第一，对于任意第 <strong>i</strong> 个骨牌而言，它的倒下能带动第 <strong>i+1</strong> 个骨牌倒下；</li>
<li>第二，有一个参与游戏的人手动推倒第一个骨牌。</li>
</ul>
<p>只要这两个条件都满足，就能让全部的骨牌都倒下。</p>
<p>“循环”的思想也存在我们的古文化中，《愚公移山》的“虽我之死，有子存焉。子又生孙，孙又生子；子又有子，子又有孙；子子孙孙无穷匮也。”简而言之就是，我有儿子，我儿子也有儿子，我儿子的儿子也会有儿子。以此类推，子子孙孙无穷尽。</p>
<p>在这其中不难发现，子子孙孙无穷匮的条件也有两个：</p>
<ul>
<li>第一，任意一代男子（或者说是儿子），都要再生至少一个儿子；</li>
<li>第二，愚公有个儿子。</li>
</ul>
<p>只要这两个条件都满足，就可以做到子子孙孙无穷匮也。</p>
<h3>数学归纳法</h3>
<p>对这两个例子的两个条件进行抽象，你会发现这就是高中学习的数学归纳法，下面我们用数学语言描述一下。</p>
<p>最简单常见的数学归纳法是，用来证明当 n 等于任意一个自然数时某个命题成立，其证明步骤可以分下面两步：</p>
<ul>
<li>第一，当 n=1 时，命题成立；</li>
<li>第二，假设对于任意一个数字 i 命题成立，可以推导出在对于 <strong>i+1</strong>，命题依然成立。</li>
</ul>
<p>只要这两个条件都满足，命题就得证。</p>
<p>例如，要证明所有的多米诺骨牌能倒下，也就是要证明游戏者手动推倒第一个骨牌，且任意一个骨牌倒下能带动下一个骨牌倒下。又比如，要证明愚公子孙无穷匮，也就是要证明愚公有儿子，愚公任意一代后代，至少有一个儿子。</p>
<p>接下来，我们利用数学归纳法来处理两个真实的数学问题。</p>
<p>【例 1】证明对于任意一个正整数 n，它的 2n 是偶数。</p>
<ul>
<li>第一步，当 n=1 时，2n = 2×1 = 2 是偶数。</li>
<li>第二步，假设对于某个正整数 i 而言，2i 是偶数，则 2(i+1)=2i+2。其中 2i 为偶数，2 为偶数，两个偶数之和也是偶数，因此 2(<strong>i+1</strong>) 也是偶数。</li>
</ul>
<p>根据数学归纳法可以知道，对于任意一个正整数 n，2n 是偶数，原命题得证。</p>
<p>【例 2】求证 1+3+5+...+(2k-1) = k2，我们依然可以用数学归纳法的思路来证明。</p>
<ul>
<li>第一步，当 k=1 时，1=12 成立。</li>
<li>第二步，假设对于任意一个正整数 i 而言，1+3+5+...+(2i-1) = i2，则 1+3+5+...+(2i-1)+[2(i+1)-1] = i2+[2(i+1)-1] = i2+2i+2-1 = i2+2i+1 = (<strong>i+1</strong>)2 原命题依然成立。</li>
</ul>
<p>因此 1+3+5+...+(2k-1) = k2 这一原命题成立。</p>
<p>综上这两个例子，你会发现它们都是要证明“下一张多米诺骨牌”能够倒下，也就是在证明“i 推进到 i+1 的过程”。具体而言，这两个例子的第二步都分别在求证 2(<strong>i+1</strong>) 是偶数，以及 (<strong>i+1</strong>)2 成立，这种数学归纳的思想在循环结构中可以得以体现。</p>
<h3>循环结构</h3>
<p>程序中的循环结构完全可以用来表达数学归纳法，利用数学归纳法来处理的数学问题，可以被无缝迁移到一个循环结构的程序中。</p>
<p>我们在大学 C 语言的课程中曾经学过，循环结构的实现方法有三种，分别是 for 循环、while 循环和 do-while 循环。为了简洁，下面我们定义 s1 是初始表达式，s2 是条件表达式，s3 叫作末尾循环体，s4 是中间循环体，并将其代入这三个循环结构中，对比学习它们之间的联系与不同。</p>
<h4>1.for 循环</h4>
<p>for 循环的代码结构如下：</p>
<pre><code>for(s1;s2;s3)
{
s4;
}
</code></pre>
<p>如刚刚所定义的，s1 是初始表达式，s2 是条件表达式，s3 叫作末尾循环体，s4 是中间循环体。
for 循环的执行顺序是 s1、(s2,s4,s3)、(s2,s4,s3)、...、(s2,s4,s3)、s2。</p>
<p>例如，求解 1 到 50 所有整数之和，可以用 for 循环这样编写代码：</p>
<pre><code>int result = 0;
for(int i= 1; i &lt;= 50; i++)
{
result += i;
}
</code></pre>
<p>这段代码的 i=1 对应的是 s1 初始表达式，i≤50 对应的是 s2 条件表达式，i++对应的是 s3 末尾循环体，最后第 4 行运算对应的是 s4 中间循环体。
这段代码的执行顺序如下：</p>
<ul>
<li>先执行 i=1，再判断 i≤50 与否，如果为真，则执行第 4 行的运算，最后执行 i++；</li>
<li>接着循环，再判断 i≤50 与否，如果为真，则执行第 4 行的运算，最后执行 i++；</li>
<li>经过多次循环后，再判断 i≤50 与否，直到结果为假，跳出循环结束。</li>
</ul>
<p>for 循环还有很多变种，具体而言就是 s1、s2 和 s4 都可以被省略或部分省略。围绕上面的例子，s1 的定义可以单独抽出来放在第 2 行；而 for 循环语句中，可以空出 s1 的部分，这样新的代码可以写作：</p>
<pre><code>int result = 0;
int i= 1;
for(; i &lt;= 50; i++)
{
result += i;
}
</code></pre>
<p>根据代码执行的顺序，可以发现 s3 的执行永远是在 s4 之后。因此，可以把 s3 和 s4 写在一起，再把 s4 的位置空出来，这样新的代码可以写作：</p>
<pre><code>int result = 0;
int i= 1;
for(; i &lt;= 50; )
{
result += i;
i++;
}
</code></pre>
<p>同样，s2 的执行永远在 s4 之前，也就意味着s2 可以被放在循环体中的 s4 之前，而把 for 语句中 s2 的位置空闲出来。但最后一次的 s2 执行，还肩负着结束循环的任务，因此需要结合 if 条件判断语句和 break 语句，完成最后跳出循环的实现，这样新的代码可以写作：</p>
<pre><code>int result = 0;
int i= 1;
for(; ; )
{
if (i &gt; 50){
break;
}
result += i;
i++;
}
</code></pre>
<h4>2.while 循环</h4>
<p>循环的另外一个实现方式是 while 循环，while 循环的代码结构如下：</p>
<pre><code>while (s2)
{
s4;
}
</code></pre>
<p>如刚刚所定义的，s2 是条件表达式，s4 是中间循环体。</p>
<p>while 循环的执行顺序是 (s2,s4)、(s2,s4)...(s2,s4)、s2。具体而言，是首先判断 s2 是否成立，如果为真，则执行 s4；继续循环判断 s2 是否成立，如果为真，则执行 s4；如此循环多次后，直到 s2 不再成立，跳出循环结束。</p>
<p>我们继续使用 while 循环来实现 1～50 所有整数求和，代码如下：</p>
<pre><code>int i = 0;
int result = 0;
while (i &lt; =50)
{
result += i;
}
</code></pre>
<p>同样地，如 for 循环一样，while 循环也有一些变种。具体而言，s2 也是可以被省略而用其他方法实现。从循环执行的顺序可以发现，s2 的执行总是在 s4 之前；而最后一次 s2 的执行，需要肩负起跳出循环的任务。</p>
<p>这就需要 if 条件语句和 break 语句了，这样变形之后的代码为：</p>
<pre><code>int i = 0;
int result = 0;
while (1)
{
if (i &gt; 50){
break;
}
result += i;
}
</code></pre>
<h4>3.do while 循环</h4>
<p>最后一种循环实现的方法是 do while 循环，do while 循环的基本结构如下：</p>
<pre><code>do {
s4;
}while(s2);
</code></pre>
<p>如刚刚所定义的，s2 是条件表达式，s4 是中间循环体。</p>
<p>do while 循环与 while 循环相比，区别就是执行顺序的调整。do while 循环中，无论 s2 是真是假，都会至少执行一次 s4。这样它的执行顺序就是 (s4,s2)、(s4,s2)...(s4,s2)。</p>
<p>具体而言就是：先执行s4，再来判断 s2 是真是假，如果为真，则执行 s4；再来判断 s2 是真是假，如果为真，则执行 s4；再来判断 s2 是真是假……如此循环多次之后，直到 s2 为假，跳出循环结束。</p>
<p>我们仍以 1～50 所有整数求和为例，看一下 do while 语句实现的代码：</p>
<pre><code>int i = 1;
int result = 0;
do {
result += i;
}while(i &lt;= 49);
</code></pre>
<p>do while 循环也有一些变种，其 s2 语句也可以被调整到其循环体中，可以考虑用 if 条件语句和 break 语句实现：</p>
<pre><code>int i = 1;
int result = 0;
do {
result += i;
if (i &gt; 49){
break;
}
}while(1);
</code></pre>
<h4>4.三种循环结构的区别</h4>
<p>这三个循环的基本代码结构如下图所示，我们总结一下这三种循环结构的本质不同。</p>
<p><img src="assets/Ciqc1F_PUXeARk9hAAIZa2CbM-w333.png" alt="Lark20201208-180948.png" /></p>
<p>从代码执行的顺序来看，while 循环与 for 循环都是先判断条件，再执行循环体。在极端情况下，第一次判断条件就不成功，循环体就有可能一次也不被执行；而 do while 循环则相反，它先执行循环体，再判断条件，因此循环体至少会被执行一次。</p>
<p>从编码的视角来看，while 循环和 do while 循环，在条件判断的括号中只需要写循环条件；而 for 循环则循环变量赋初值、循环条件、循环变量改变方式都写在一起。</p>
<p>最后，从功能上来看，这三个循环结构完全一致，是可以彼此切换的。你可能会有这样的困惑：do while 循环至少会执行一次循环体，它如何能被其他循环结构替代呢？这就要借助 break 语句提前跳出循环体了，具体如何切换，我接下来就要讲解。</p>
<h3>三种循环实现的切换</h3>
<p>在不考虑代码结构的美观时，这三种循环语句可以在功能上实现彼此之间的切换，我们以 for 向 while 和 do while 的切换为例。</p>
<p>如下是任意一个<strong>for 循环</strong>语句：</p>
<pre><code>for(s1;s2;s3)
{
s4;
}
</code></pre>
<p>其执行顺序为 s1、(s2,s4,s3)、(s2,s4,s3)...(s2,s4,s3)、s2。</p>
<p>它可以用下面的 <strong>while 循环</strong>语句来实现其功能：</p>
<pre><code>s1;
while(s2)
{
s4;
s3;
}
</code></pre>
<p>根据 while 语句的执行顺序可知，这段代码的执行顺序为 s1、(s2,s4,s3)、(s2,s4,s3)...(s2,s4,s3)、s2，因此可以得知，两段代码的功能结果完全一致。</p>
<p>而如果非要采用 <strong>do while 循环</strong>，可以按照如下方式实现：</p>
<pre><code>s1;
do {
if(!s2)
{
break;
}
s4;
s3;
}while(1);
</code></pre>
<p>在这里，我们补充一下 break 语句的知识。break 语句的作用是，终止并跳出循环，继续执行循环语句后续的代码。</p>
<p>以上面的代码为例，一旦第 3 行的条件判断通过，则需要执行 break 语句。break 语句会帮助程序跳出当前循环，这样程序就会从第 4 行跳转至第 10 行继续执行。基于 break 语句，再根据 do while 语句的执行顺序可知，这段代码的执行顺序为 s1、(s2,s4,s3)、(s2,s4,s3)...(s2,s4,s3)、s2，因此可以得知两段代码的功能结果完全一致。</p>
<p>这里要给大家提个醒：如果是在技术面试时，<strong>千万不要说某某功能的开发，只能用 for 循环、while 循环或 do while 循环，这一定是错的</strong>。因为，功能上这三种循环的实现是完全可以实现互换的；只不过，三者在代码美观上可能是有所区别。</p>
<h3><strong>数学归纳法与循环结构</strong></h3>
<p>数学归纳法和循环结构有很多相似之处，它们都是<strong>从某个起点开始，不断地重复执行某个或某组相似的动作集合</strong>。</p>
<p>不过，二者也有一些区别：</p>
<ul>
<li>数学归纳法<strong>不关注归纳过程的结束</strong>，它就是用一种重复动作，由有穷尽朝着无穷尽的方向去前进；</li>
<li>而循环结构作为一种程序开发逻辑，则<strong>必须要关注循环过程的结束</strong>，否则就会造成系统陷入死循环或死机。</li>
</ul>
<p>接下来，我们试着把一个数学归纳法的计算过程，用循环结构改写。为了让二者没有区别，我们对数学归纳法的问题增加一个截止条件的限制，那就是 k 小于 100 时。</p>
<p>这道例题是：证明在 k&lt;100 时，1+3+5+... +(2k-1) = k2 成立。</p>
<p>我们说过，用数学归纳法来证明这个问题需要两个步骤，分别是：</p>
<ul>
<li>证明 k=1 时等式成立；</li>
<li>假设 k=i 时等式成立后，k=i+1 等式依然成立。</li>
</ul>
<p>我们把这两个步骤进行拆解。</p>
<p>令 s1 为 k=1，s4 为等式成立，s3 为 k=i 或 k=i+1，再补充题目的终止条件 k&lt;100 为 s2。这样，根据 for 循环执行的逻辑，把这些动作按照 s1、(s2,s4,s3)、(s2,s4,s3)...(s2,s4,s3)、s2 串联起来，就得到了基本的 for 循环代码框架。</p>
<ul>
<li>在这个框架中，最开始的 s1、s2、s4，即为当 k=1 时等式成立，对应数学归纳法的第一步。</li>
<li>在这个框架中，任意相邻的两组(s2,s4,s3)、(s2,s4,s3)，就是假设 k=i 时等式成立后，k=i+1 等式依然成立，对应数学归纳法的第二步。</li>
</ul>
<p>也就是说，此时的数学归纳法证明和 for 循环实现，在功能上是等价的，我们给出 for 循环的代码如下：</p>
<pre><code>int left = 0;
int left_temp = 0;
int right = 0;
for (int k = 1; k &lt; 100; k++) // s1;s2;s3
{
//s4
left_temp = 2 * k - 1;
left += left_temp;
right = k * k;
if (left == right)
{
printf(&quot;%d is right!\n&quot;,k);
}
}
</code></pre>
<p>我们对代码进行走读：</p>
<ul>
<li>代码的前三行定义了 3 个变量，分别是 left、left_temp 和 right，其中 left 和 right 分别用来存储等式两边的结果，left_temp 用来存储公式中每轮增加的一项；</li>
<li>第 4 行，进入 for 循环，得到对应的 s1、s2 和 s3；</li>
<li>第 6 行，计算出当前一轮的 left_temp 值；</li>
<li>第 7 行，把 left_temp 作为增量，增加到 left 的值中；</li>
<li>第 8 行，计算等式右侧的 k2 的值；</li>
<li>第 9 行，对等式左边和等式右边是否相等做出判断；</li>
<li>第 10～12 行进行判断，如果等式相等，打印结果，代码的部分执行结果如下图。</li>
</ul>
<p><img src="assets/Ciqc1F_PUaGAODzCAADYB9oMxQI862.png" alt="Lark20201208-180945.png" /></p>
<p>可见原命题得到证明。</p>
<h3>小结</h3>
<p>这一讲我们学习了数学归纳法的理论知识，以及循环结构的代码开发知识。然后我们从原理上分析了数学归纳法和循环结构的异同，介绍了 for 循环、while 循环和 do while 循环这三种循环结构的实现方法。</p>
<p>最后我们留一个练习题：本讲最后一个例题用 for 循环实现了等式的证明，请你试着分别用 while 和 do while 循环再次实现这段代码的功能。</p>
</div>
</div>
<div>
<div style="float: left">
<a href="/专栏/程序员的数学课/13 复杂度：如何利用数学推导对程序进行优化？.md.html">上一页</a>
</div>
<div style="float: right">
<a href="/专栏/程序员的数学课/15 递归：如何计算汉诺塔问题的移动步数？.md.html">下一页</a>
</div>
</div>
</div>
</div>
</div>
</div>
<a class="off-canvas-overlay" onclick="hide_canvas()"></a>
</div>
<script defer src="https://static.cloudflareinsights.com/beacon.min.js/v652eace1692a40cfa3763df669d7439c1639079717194" integrity="sha512-Gi7xpJR8tSkrpF7aordPZQlW2DLtzUlZcumS8dMQjwDHEnw9I7ZLyiOj/6tZStRBGtGgN6ceN6cMH8z7etPGlw==" data-cf-beacon='{"rayId":"70997bdc5d6e3cfa","version":"2021.12.0","r":1,"token":"1f5d475227ce4f0089a7cff1ab17c0f5","si":100}' crossorigin="anonymous"></script>
</body>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-NPSEEVD756"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag() {
dataLayer.push(arguments);
}
gtag('js', new Date());
gtag('config', 'G-NPSEEVD756');
var path = window.location.pathname
var cookie = getCookie("lastPath");
console.log(path)
if (path.replace("/", "") === "") {
if (cookie.replace("/", "") !== "") {
console.log(cookie)
document.getElementById("tip").innerHTML = "<a href='" + cookie + "'>跳转到上次进度</a>"
}
} else {
setCookie("lastPath", path)
}
function setCookie(cname, cvalue) {
var d = new Date();
d.setTime(d.getTime() + (180 * 24 * 60 * 60 * 1000));
var expires = "expires=" + d.toGMTString();
document.cookie = cname + "=" + cvalue + "; " + expires + ";path = /";
}
function getCookie(cname) {
var name = cname + "=";
var ca = document.cookie.split(';');
for (var i = 0; i < ca.length; i++) {
var c = ca[i].trim();
if (c.indexOf(name) === 0) return c.substring(name.length, c.length);
}
return "";
}
</script>
</html>
Reference in New Issue View Git Blame Copy Permalink