【具体数学 Concrete Mathematics】1.1 递归问题 讲义

2024-08-22 13:20

本文主要是介绍【具体数学 Concrete Mathematics】1.1 递归问题 讲义,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【具体数学 Concrete Mathematics】1.1 递归问题 导入

本节(1.1、1.1.1-1.1.3)主要围绕《具体数学》第一章 递归问题(Recurrent Problems)讲义部分的三个问题展开,分别是汉诺塔、平面上的直线以及约瑟夫问题。下面简单介绍一下递归问题和数学归纳法,做一个简单的导入,具体的递归应用可以在三个例子(1.1.1-1.1.3)中获得更好的体现:

1. 递归问题:

递归问题的主要思想是将大的问题分解成小的问题,然后只要提供最小的问题的具体解决方案即可。这样实际上递归方案并没有给出原问题的具体解决方案,而是给了一个解决问题的步骤。
一个典型的例子是《线性代数》中计算行列式的值 D = ∑ j = 1 n A i j D=\sum_{j=1}^n A_{ij} D=j=1nAij。这里就是将计算 n n n维行列式 D D D分解成 n n n n − 1 n-1 n1维行列式 A i j A_{ij} Aij的计算。最后可以展开到 1 1 1维行列式 ∣ x ∣ = x |x|=x x=x。整个过程中直接计算的只有最小的问题模块—— 1 1 1维行列式,其他维度都是直接根据递归方案来计算的。
通过这个小例子我们也可以看到递归方案只有到最后一步才真正解决具体问题,此前我们都假设更小的问题答案已知,如 D = ∑ j = 1 n A i j D=\sum_{j=1}^n A_{ij} D=j=1nAij中,我们假设 A i j A_{ij} Aij都已知,但是其实 A i j A_{ij} Aij的值还需要进一步递归直到 1 1 1维行列式才能计算出具体值。
如果这个例子没能理解,请看下面三个具体的例子,然后再回来看这个小例子,相信读者会有新的理解。
DAij

2. 数学归纳法

数学归纳法是证明某个命题 P P P对所有满足 n ≥ n 0 n\ge n_0 nn0的整数 n n n都成立的一种方法。
首先我们在 n = n 0 n=n_0 n=n0时,证明 P ( n 0 ) P(n_0) P(n0)成立,这一步称为基础(Basis);
接着对于 n > n 0 n>n_0 n>n0,假设 n 0 n_0 n0 n − 1 n-1 n1之间(包含两端)的所有值都证明成立,即 P ( n 0 ) , … , P ( n − 1 ) P(n_0),\dots,P_(n-1) P(n0),,P(n1)都被证明成立,在此基础上证明 P ( n ) P(n) P(n)成立,这一步称为归纳(Induction)。
由此可以证得命题 P P P对所有满足 n ≥ n 0 n\ge n_0 nn0的整数 n n n都成立。
下面举两个例子:

例子1: 证明 P ( n ) : 1 + 2 + ⋯ + n = n ( n + 1 ) 2 P(n):1+2+\cdots+n=\frac{n(n+1)}{2} P(n):1+2++n=2n(n+1)对任意 n ≥ 1 n\ge 1 n1成立。
证明:
Basis: P ( 1 ) = 1 = 1 + 2 2 P(1)=1=\frac{1+2}{2} P(1)=1=21+2
Induction:当 n > 1 n>1 n>1时,假设 P ( n − 1 ) P(n-1) P(n1)成立,则有 P ( n − 1 ) = 1 + 2 + ⋯ + n − 1 = ( n − 1 ) n 2 P(n-1)=1+2+\cdots+n-1=\frac{(n-1)n}{2} P(n1)=1+2++n1=2(n1)n
那么 P ( n ) = 1 + 2 + ⋯ + ( n − 1 ) + n = P ( n − 1 ) + n = ( n − 1 ) n 2 + n = n ( n + 1 ) 2 P(n)=1+2+\cdots+(n-1)+n=P(n-1)+n=\frac{(n-1)n}{2}+n=\frac{n(n+1)}{2} P(n)=1+2++(n1)+n=P(n1)+n=2(n1)n+n=2n(n+1)
由此原命题得证。

例子2(习题1): 证明所有的马都是同样的颜色。
证明:假设有 n n n匹马,下面证明 P ( n ) : P(n): P(n): n n n匹马都是同样的颜色对任意 n ≥ 1 n\ge 1 n1成立。
Basis: P ( 1 ) P(1) P(1)只有1匹马,显然其与自身有相同的颜色。
Induction:当 n > 1 n>1 n>1时,假设 P ( n − 1 ) P(n-1) P(n1)成立,则有任意 n − 1 n-1 n1匹马都是相同的颜色。
那么根据归纳假设可知, 1 ∼ ( n − 1 ) 1\sim (n-1) 1(n1)号马颜色相同, 2 ∼ n 2\sim n 2n号马颜色相同,而处于中间位置标号 2 ∼ ( n − 1 ) 2\sim (n-1) 2(n1)的马在不同的马群中不可能改变颜色,因为这是马,不是变色龙。故而根据传递性可知,标号 1 ∼ n 1\sim n 1n的马颜色相同。
由此原命题得证。

例子2的证明其实是存在问题的,读者能发现吗?
这个证明绕开了2匹马的情况,因为根据归纳证明,当 n = 2 n=2 n=2时, 1 1 1 2 2 2之间不存在任何中间标号的马匹,由此可知Induction在 n = 2 n=2 n=2时不成立。

这篇关于【具体数学 Concrete Mathematics】1.1 递归问题 讲义的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1096388

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)