具体数学第一章笔记及习题解答

作者: 古剑诛仙 | 来源:发表于2019-08-05 15:19 被阅读0次

具体数学第一章笔记及习题解答
具体数学第二章笔记及习题解答
具体数学第三章笔记及习题解答
使用ArrayList构建帕斯卡三角
验证一组数字是否magic square
第一章~编程练习解答
高等数学(第七版)(上册)课后习题答案
中学英语会读会说难答题，主要问题是没梳理——初中英语语法归纳解析
QS1065宇轩乌市第三次课程《思维导图巧解题》
上海市高中基础物理知识竞赛001

本章主要探讨了三个问题汉诺塔，直线切分平面，约瑟夫问题，这三个问题都是典型的递归问题，之后介绍了解决递归式的成套方法。

汉诺塔

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着n片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。要求出需要移动多少次圆盘。

image.png

题解：
假设有1，2，3号柱子，i个圆盘都在from号柱子上，假设从from号柱子移动到to号柱子。最优移动轨迹需要重复以下步骤：

要把序号为1~i-1的圆盘从from移动到mid柱子上，如果i=1，则直接把圆盘移动到to柱子上
把序号为i的圆盘从from移动到to柱子（移动1次）
把序号1~i-1的圆盘从mid移动到to柱子上。（3和1移动次数相同）

显然根据递推关系，有 $T_{n}=2T_{n-1}+1,n>0且T_{1}=1$
构建等比数列后计算得 $T_{n}=2^{n}-1,n>=0$

理解以上内容后，看一下进阶的问题，给定一个int数组arr，数组元素的值为1,2,3中的一个，代表所有圆盘的位置序号，arr[i]的值代表i+1个圆盘的位置，比如arr=[1,1,3,2]代表1~4号圆盘（由小到大）分别在1号，1号，3号，2号柱子上，如果arr数组代表的状态是最优移动轨迹的状态，则返回arr是经过最少几次移动变成的，如果不是最优移动轨迹，则返回-1。

举例：

arr=[1,1]。两个圆盘都在1号柱子上，也就是初始状态，返回0。
arr=[2,1]。1号圆盘在2号柱子上，2号圆盘在1号柱子上，移动一次即可达到，返回1。
arr=[2,2]。两个圆盘都在2号柱子上，这并不是最优移动轨迹中的一步，所以返回-1。

分析：
对于arr[i-1]代表第i个圆盘在哪个柱子上，就可分为如下情况：

圆盘i在from号柱子上，递归检查其余圆盘即arr[i-2],arr[i-3]...的情况，对每次递归检查的结果，如果符合情况1，则不加步数（注意每次递归中，from,mid,to传入的值会发生变化，目标为从from到mid）
圆盘i在to号柱子上，说明步骤1已完成，且步骤2已完成，步骤3中移动了多少次需要查看1~i-1号圆盘位置来确定，所以至少经过了 $2^{i-1}$ 步（因为已知 $T_{i-1}=2^{i-1}-1$ ，这是步骤1的步数，再加上步骤2的一步，可得），递归检查arr[i-2],arr[i-3]...的情况，对每次递归检查的结果，如果符合情况2，则加相应 $2^{i-1}，2^{i-2}...$ 步数（from,mid,to也会发生变化，目标为从mid到to）
在每次递归中，发现圆盘i,i-1,i-2...在mid号柱子上，这不是最优移动轨迹的情况，直接返回-1

具体代码如下：

public class TowerOfHanoi {
    static int []arr={3,3,3,3,3};
    public static int count1(int []arr,int i,int from,int mid,int to){
// 这里作为防止数组越界的终止条件，要在递归调用第一句写出，不然会发生当i=-1时，对arr[i]的访问
        if(i==-1){
            return 0;
        }
// 首先作为最优移动轨迹的判断条件
        if(arr[i]!=from&&arr[i]!=to){
            return -1;
        }
        if(arr[i]==from){
// 注意这里和下面的递归中，from,mid,to的值会发生变化
            return count1(arr,i-1,from,to,mid);
        }
        else{
// rest保存i-1个圆盘移动的步数
            int rest=count1(arr,i-1,mid,from,to);
// 在递归中一旦发现非最优移动轨迹，则返回-1
            if(rest==-1){
                return -1;
            }
// 将rest和第i个圆盘移动的步数相加
            return (1<<i)+rest;
        }
    }

    public static int count2(int []arr){
        if(arr==null||arr.length==0){
            return -1;
        }
        int from=1;
        int mid=2;
        int to=3;
        int i=arr.length-1;
        int ans=0;
        int temp=0;
        while (i>=0){
            if(arr[i]!=from&&arr[i]!=to){
                return -1;
            }
            if(arr[i]==to){
                ans+=1<<i;
                temp=from;
                from=mid;
            }
            else {
                temp=to;
                to=mid;
            }
// 在上面把新的mid值用temp保存下来，在循环体结束前统一对mid赋值
            mid=temp;
            i--;
        }
        return ans;

    }
    public static void main(String[] args) {
        System.out.println("需要的步数为"+count1(arr,arr.length-1,1,2,3));
        System.out.println("需要的步数为"+count2(arr));
    }
}

分析以上代码，发现其实函数调用总共只进行了N次，所以时间复杂度为 $O(N)$ ，但空间复杂度由于递归需要函数栈的关系，为 $O(N)$ ，采用非递归形式，可以将空间复杂度降低到 $O(1)$

直线划分平面

先看一个简单的例子，N条直线最多可以将平面划分为多少个部分？

分析：
第n条直线使得区域个数增加了k个，当且仅当它对k个已有区域进行了分割，而显然直线必须穿越前面k-1个部分才能实现。第n条直线与前面n-1条直线相交最多有n-1个不同的交点，也就是说k<=n，故而有上界： $L_{n}=L_{n-1}+n,n>0且L_{0}=1$
从而有
$L_{n}=L_{n-1}+n=L_{n-2}+n-1+n=...=L_{0}+1+2+...+n-1+n=n(n-1)/2+1$

下面看几个变形：

如果用n条V字型的折线分割平面，划分区域的个数，如下图

image.png
可以看到V字形的折线如果将每个折线两条线反向延长，其实就是两条相交的直线，有理由相信，在使得每条直线交于不同点情况下 $V_{n}=L_{2n}$ ，然而因为是V型的，所以两条反向延长线去掉之后，都会把三个部分合成一个部分，所以，对于每一个V，反向延长线去掉之后，平面分割的部分数目就要减去2，而总共有n个V型的线，故 $V_{n}=L_{2n}-2n=2n(2n-1)/2+1-2n=2n^2-n+1$
如果用n条Z字型的线分割平面，可以当做两条平行线和一条与平行线相交的直线的组合。两条平行线会使得区域数目减1，然后把三条线的延长线去掉，数目减去4，一共减去5，则有 $Z_{n}=L_{3n}-5n=3n(3n-1)/2-5n+1=(9n^2-7n+2)/2$

约瑟夫问题

下面是本章重点与难点——约瑟夫问题
首先从最简单的情况入手， $n$ 个人围成一个圈，每隔一个人杀死一个人，问最后谁会活下来。
举例：
一共5个人，1号跳过，2号死，3号跳过，4号死，5号跳过，1号死，3号跳过，5号死，最后剩下3号。

分析：
有n个人时，我们设幸存者号码为 $J(n)$
假设开始一共有2n个人，经过第一轮后，剩下的人是

image.png

此时 $J(2n)$ 在经过一轮之后，显然对应n个人开始的情形，只不过号码是 $J(2n)=2J(n)-1,n>0$ ，即

image.png

而当人数为奇数即2n+1个人时，标号为1的人恰好在标号为2n的人后面被排除，于是剩下的人是：

image.png
同上面分析相同，与n个人时情况相对比，有

image.png
只不过这时号码是，综上，可得对于的递归式：

$J(1)=1$
$J(2n)=2J(n)-1,n>0$
$J(2n+1)=2J(n)+1,n>0$

有了以上递归式，显然能够计算出n为任意值时， $J(n)$ 的结果，但这样的递归式计算效率还是不让人满意，我们希望得出一个封闭式（注：指仅仅显式包含了加减乘除和对指幂运算的算式），通过递归式，我们对 $J(n)$ 的值做出一张表，试图找出其值的规律：

image.png

可以明显的看到，通过我们对 $J(n)$ 的值做一个分组，具体为按照2的幂将表中的数据分组（在表中用竖线分隔开），在每一组的开始总是等于1，并且组里的数据每次递增2．因此，如果我们将n写为 $n=2^m+l，2^m$ 是不超过n的2的最大次幂， $l$ 是剩余的值，则有

image.png

可以从图中得出
$J(2^m+l)=2l+1$
对上面结论的证明可以通过数学归纳法推出，这里就略过了。

得出以上数学上的结论后，我们试图从计算机视角，也就是二进制去思考这个问题。n可以通过二进制展开为 $n=（b_{m}b_{m-1}...b_{1}b_{0})_{2}$ ，即 $n=b_{m}2^m+b_{m-1}2^{m-1}+...+b_12+b_0$
显然有 $b_m=1,其余b_i为0或1$
故有以下几个式子：

········ $n=（1b_{m-1}...b_{1}b_{0})_{2}$
········· $l=（0b_{m-1}...b_{1}b_{0})_{2}$
······· $2l=（b_{m-1}...b_{1}b_{0}0)_{2}$
$2l+1=（b_{m-1}...b_{1}b_{0}1)_{2}$
$J(n)=（b_{m-1}...b_{1}b_{0}b_{m})_{2}$

也就是说我们把n的二进制值向左循环位移1位即可得到 $J(n)$ ，但需要注意的是，对 $J((1011)_2)=(111)_2$ ，而非 $(0111)_2$ 。也就是说一旦循环位移后首位变成了0，就要把这个0舍弃掉，只有保证首位一定是左数第一个1，这样才能保证结果的正确性（保证J(n)<=n）。

当然，我们现在只是处理了隔1个人的情况，如果隔2个人，3个人，k个人呢，本章中我们使用的方法就不够通用了，到第三章会给出这个问题的通解。下面介绍解决递推关系很方便的一种方法。

成套方法（待定系数法）

此部分具体数学课本中写的不够详尽，参考自Geoffrey Matthews教授在讲义中关于成套方法的讲解。
对于形如以下递推式

image.png

将上式可以化为

image.png

可以看到 $r_n$ 都可以化作 $A(n),B(n),C(n)$ 的组合的形式，问题的关键在于求解这三个值，与这三个值对应的 $\alpha,\beta,\gamma$ 值
更确切说

image.png

需要注意的是， $\alpha,\beta,\gamma$ 取不同值时，比如为1；0；0，带入递推关系则 $A(n),B(n),C(n)$ 的值中显然 $A(n)$ 可以唯一确定。同样的 $\alpha,\beta,\gamma$ 取0；1；-3时，显然 $A(n),B(n),C(n)$ 的值中 $B(n),C(n)$ 之间是线性组合的关系。

我们解题的方向就是先把唯一确定的值求出来，然后把其余值通过确定的值表示出来，即可得到最终的递归表达式

有了以上思路后，下面我们做出一些尝试：

image.png

通过假定 $r_n=1$ ，可以很轻松通过 $r_0$ 得到 $\alpha$ 的值，并将 $r_n$ 化为更简略的形式，下面再做出类似的尝试

image.png

此时只剩下未知的 $B(n)$

image.png

这里需要注意，因为 $r_n=r_{n-1}+...$ 中， $r_{n-1}$ 的系数是1，所以假设 $r_n=n^2$ 后，对 $n^2=(n-1)^2+...$ 化简时，会把 $n^2$ 消去，而如果系数不为1，显然是做不到这点的，那就需要变换对于 $r_n$ 的假设了，后面有个例子会讲到。
对上式化简

image.png

可以看到我们通过唯一确定的 $A(n),C(n)$ 将 $B(n)$ 也唯一的表示出来了，再将我们求出来的三个值带入即可得到递推的表达式

image.png

也就是说，形如下面所示的 $r_n$ 其通项公式可以表示为

image.png

对下面递推式做一个检验

$r_0=1$
$r_n=r_{n-1}+3n+5$
image.png

我们随便带入几个值，显然是正确无误的。

同时，显然一些和式，也符合这个规律，只需要将和式做一些小的变化：

image.png

显然结果是正确的：

image.png

下面看一下上文中提到的特殊的情况（通过这个例子提醒我们灵活选取 $r_n$ 的值）

image.png

到这里就出现问题了，需要把系数2考虑进去，使得 $r_n$ 与 $2r_{n-1}$ 间可以消去不易于计算的部分，显然在对 $n$ 的几种选择（多项式，指数，对数）中，选择以2为底的指数是最合适的

image.png

image.png
于是经过以上步骤，我们就可以得到通解

image.png

将具体的 $\alpha,\beta,\gamma$ 带入，即可得到特解

image.png

总结：
对上面问题做一个更简略的计算过程（如果 $r_{n-1}$ 的系数发生变化，则第三步假设的内容也要发生相应变化）

image.png

在介绍完成套方法后，可以看到其主要解决形如 $r_n=\alpha r_{n-1}+\beta n+\gamma$
形式的问题。然后约瑟夫问题面临的是形如 $r(dn+j)=cr(n)+b_{j},0<=j<d$ 的问题，试试我们的方法

image.png

image.png
注意到这里解题，是通过找规律的方式，猜想出的值，然后用数学归纳法证明它，之后用成套方法分别代入，求出剩余两个未知量

image.png

经过以上分析，我们可以给出以具有下形式的递推式的解：

$f(j)=a_{j},1<=j<d$
$f(dn+j)=cf(n)+b_{j},0<=j<d$

设 $n=(c_mc_{m-1}...c_1c_0)_d$ ，也就是将n化为d进制后各位的值用 $c_i$ 保存下来
则递推式有 $f( n)=f((c_mc_{m-1}...c_1c_0)_d)=(a_{c_m}b_{c_{m-1}}b_{c_{m-2}}...b_{c_{1}}b_{c_{0}})_c$
看起来很绕，举例说明一下，如果有递推式：

$f(1)=34$
$f(2)=5$
$f(3n)=10f(n)+76,n>=1$
$f(3n)=10f(n)-2,n>=1$
$f(3n)=10f(n)+8,n>=1$

计算 $f(19)$ ，则有 $a_{i}=\{34,5\}(i>0)$ ， $b_i=\{76,-2,8 \}(i>=0)，c=10,d=3$ ，
$f(19)=f((201)_3)=(a_{2}b_0b_1)_{10}=(5,76,-2)_{10}=5*100+76*10-2=1258$

习题解答

热身题

image.png

解答：

很明显这道题在数论第一章对于数学归纳法的介绍中提到过，由于当n=1,2,3..中，1,2间不是连续的关系，所以无法直接采用数学归纳法，如果要想使用，必须起点从n=2开始。

image.png

作业题

image.png

解答：

image.png

考试题：

image.png

解答：

image.png

附加题：

image.png

解答：

image.png

具体数学第一章笔记及习题解答
本章主要探讨了三个问题汉诺塔，直线切分平面，约瑟夫问题，这三个问题都是典型的递归问题，之后介绍了解决递归式的成套方...
具体数学第二章笔记及习题解答
第二章我们把目光放在很常用但很少详细叙述其技巧的和式上，也就是形如这两种都表示相同的内容，前一种在连加符号上部分写...
具体数学第三章笔记及习题解答
离散数学是跟整数有关的数学，也是计算机科学的基础，本章就着重于讲述如何将分数转化为整数的技巧底和顶我们使用以下...
使用ArrayList构建帕斯卡三角
以下是「Core Java for the Impatient」一书第一章的第15道习题及解答。题目： Write...
验证一组数字是否magic square
以下是「Core Java for the Impatient」一书第一章的第14道习题及解答。题目： Write...
第一章~编程练习解答
第一章的友好度还是相当滴习题解答 1.2习题 1.2认为最大的收获： 1.4习题~(循环与不定量数据读入) 最后~...
高等数学(第七版)(上册)课后习题答案
高等数学上同济第七版课后题解答线性代数同济第六版课后题解答书名：高等数学(第七版)(上册)课后习题答案作...
中学英语会读会说难答题，主要问题是没梳理——初中英语语法归纳解析
摘要：超强归纳，语法easily get！本章内容系统讲解12个复合不定代词的注意点及5大易错点！习题习题解答视频
QS1065宇轩乌市第三次课程《思维导图巧解题》
第三次作业，解答孩子数学课本里的课后习题，孩子进行了临摹，他说很有收获！
上海市高中基础物理知识竞赛001
尝试写一写物理习题的习题解答：