在最后的关头奋力一搏,就算没有得到想要的结果也不会遗憾

IT历史

第一台计算机:1946年的埃尼阿克,USA.

计算机作用:计算(废话),数据储存处理,通信,辅助工作

第一个程序员:Ada(女),有以此命名的程序语言

相关奖项:图灵奖(仅姚期智一华人获奖),菲尔兹奖(数学),诺贝尔奖(物化生经济文学核和平)

相关机构:ACM(美国计算机协会),IEEE,CCF($€€￡$)

冯诺依曼计算机结构(储存程序原理)

基本架构,在当下基本没有什么变化

计算机性能指标

字长:指CPU一次性能够处理的数据的长度(32位(4字节)或是64位(8字节))

主频:CPU每秒钟可以进行基本运算的次数,一般以$GHz$为单位(这个单位很大的…)

核心:计算机内部的CPU个数

常见的操作系统,编程语言的分类

操作系统:$windows \ DOS \ UNIX \ Linux \ MacOS \ Android \ iOS \ 鸿蒙$

编程语言:

机器语言:01101101011
汇编语言:指令集,比如这个(luogu P4316程序的汇编版本)

   0x004015f1 <+0>:	push   %ebp
   0x004015f2 <+1>:	mov    %esp,%ebp
   0x004015f4 <+3>:	push   %esi
   0x004015f5 <+4>:	push   %ebx
   0x004015f6 <+5>:	and    $0xfffffff0,%esp
   0x004015f9 <+8>:	sub    $0x20,%esp
   0x004015fc <+11>:	call   0x40d720 <__main>
   0x00401601 <+16>:	mov    0xb723ac,%eax
   0x00401606 <+21>:	mov    %eax,0x8(%esp)
   0x0040160a <+25>:	movl   $0x489000,0x4(%esp)
   0x00401612 <+33>:	movl   $0x489002,(%esp)
   0x00401619 <+40>:	call   0x419ad8 <freopen>
   0x0040161e <+45>:	movl   $0x61aa8,0x8(%esp)
   0x00401626 <+53>:	movl   $0xffffffff,0x4(%esp)
   0x0040162e <+61>:	movl   $0x926080,(%esp)
   0x00401635 <+68>:	call   0x419ae0 <memset>
   0x0040163a <+73>:	movl   $0xc3550,0x8(%esp)
   0x00401642 <+81>:	movl   $0x0,0x4(%esp)
   0x0040164a <+89>:	movl   $0x987b40,(%esp)
   0x00401651 <+96>:	call   0x419ae0 <memset>
   0x00401656 <+101>:	movl   $0xc3550,0x8(%esp)
   0x0040165e <+109>:	movl   $0x0,0x4(%esp)
   0x00401666 <+117>:	movl   $0xa4b0c0,(%esp)
   0x0040166d <+124>:	call   0x419ae0 <memset>
   0x00401672 <+129>:	movl   $0x61aa8,0x8(%esp)
   0x0040167a <+137>:	movl   $0x0,0x4(%esp)
   0x00401682 <+145>:	movl   $0xb0e640,(%esp)
   0x00401689 <+152>:	call   0x419ae0 <memset>
   0x0040168e <+157>:	fld1   
   0x00401690 <+159>:	fstpl  0x987b48
   0x00401696 <+165>:	movl   $0x492040,(%esp)
   0x0040169d <+172>:	call   0x421608 <read<int>(int&)>
   0x004016a2 <+177>:	movl   $0x492044,(%esp)
   0x004016a9 <+184>:	call   0x421608 <read<int>(int&)>
   0x004016ae <+189>:	mov    $0x1,%ebx
   0x004016b3 <+194>:	jmp    0x401715 <main()+292>
   0x004016b5 <+196>:	lea    0x1c(%esp),%eax
   0x004016b9 <+200>:	mov    %eax,(%esp)
   0x004016bc <+203>:	call   0x421608 <read<int>(int&)>
   0x004016c1 <+208>:	lea    0x18(%esp),%eax
   0x004016c5 <+212>:	mov    %eax,(%esp)
   0x004016c8 <+215>:	call   0x421608 <read<int>(int&)>
   0x004016cd <+220>:	lea    0x10(%esp),%eax
   0x004016d1 <+224>:	mov    %eax,(%esp)
   0x004016d4 <+227>:	call   0x421694 <read<long long>(long long&)>
   0x004016d9 <+232>:	mov    0x10(%esp),%eax
   0x004016dd <+236>:	mov    0x14(%esp),%edx
   0x004016e1 <+240>:	mov    0x18(%esp),%esi
   0x004016e5 <+244>:	mov    0x1c(%esp),%ecx
   0x004016e9 <+248>:	mov    %eax,0x8(%esp)
   0x004016ed <+252>:	mov    %edx,0xc(%esp)
   0x004016f1 <+256>:	mov    %esi,0x4(%esp)
   0x004016f5 <+260>:	mov    %ecx,(%esp)
   0x004016f8 <+263>:	call   0x421580 <addl(int, int, long long)>
   0x004016fd <+268>:	mov    0x1c(%esp),%eax
   0x00401701 <+272>:	mov    0xb0e640(,%eax,4),%edx
   0x00401708 <+279>:	add    $0x1,%edx
   0x0040170b <+282>:	mov    %edx,0xb0e640(,%eax,4)
=> 0x00401712 <+289>:	add    $0x1,%ebx
   0x00401715 <+292>:	mov    0x492044,%eax
   0x0040171a <+297>:	cmp    %eax,%ebx
   0x0040171c <+299>:	jle    0x4016b5 <main()+196>
   0x0040171e <+301>:	movl   $0x1,(%esp)
   0x00401725 <+308>:	call   0x401500 <dfs(int)>
   0x0040172a <+313>:	fldl   0xb700e8
   0x00401730 <+319>:	fstpl  0x4(%esp)
   0x00401734 <+323>:	movl   $0x48900d,(%esp)
   0x0040173b <+330>:	call   0x42176c <printf(char const*, ...)>
   0x00401740 <+335>:	mov    $0x0,%eax
   0x00401745 <+340>:	lea    -0x8(%ebp),%esp
   0x00401748 <+343>:	pop    %ebx
   0x00401749 <+344>:	pop    %esi
   0x0040174a <+345>:	pop    %ebp
   0x0040174b <+346>:	ret

高级语言:人能够看得懂的语言,如

$C++ \ Pascal \ Python \ PHP$

高级语言分类:编译性语言($C++ \ C \ Pascal$),解释性语言($Python \ PHP \ Basic \ Java$)

NOI系列历史知识

NOI

首次举办:1984年

举办方:CCF,中国计算机协会

NOIP

存在过的时间:1995-2019(经历了从省一可以保送到省一没任何卵用的过程)

可以带的东西(这也要考…):文具,衣服,水,证件,笔,人(仅限自己),计算器(待定?)

可以使用的语言

(可怜的pascal将会在2022年被noip抛弃)

(但是noip却在这之前已经挂了)

2022年后只能用$C++$

源码,补码,反码

这个是我原来写过的一博客,而且还是阅读量最多的一篇

~~但是读者却没有想到,作者自己都忘了这个东西是怎么一回事了2333~~

复习了一下,其实很简单:源码就是二进制+符号位,反码就是源码除了符号位外取反,补码就是反码＋1,只需要记住这些东西就可以了,因为初赛主要考运算

编码

所有计算机里的数据都是01串

字符编码

ASCII编码

把英文字符映射到0到127这些整数中

GBK编码

存汉字,用两个字节来存贮信息

utf-8编码

使用3个字节,可以存世界上出现过的几乎所有文字(这就是我每次写博客都要用utf-8编码保存的原因?)

像素编码

这个我也是写过博客的,但是我也忘了…

这个首先要复习一下进制关系:

bit,位,最小的内存大小单位,1个bit为一个二进制位

byte,字节,一个byte为8个二进制位,即8个bit,byte简写为B

之后的就好说了:

1KB=1024B

1MB=1024KB

1GB=1024MB

1TB=1024GB

后面的我就背不到了,但后面好像还有五六个单位

~~谁用的到这么大的单位啊~~

然后就是很简单的事情了:

m*n算出有多少个格子

每一个格子的字节数等于位数,然后进行单位换算即可

进制转化

8进制和16进制和二进制

二进制转8/16进制:

凑4/3法,即以小数点为分界线向左/右分别处理出整数或小数的8/16进制表示位,如果位数不够就填够为止

8/16进制转二进制:

为上面过程的逆过程,即把每一位数拆分成对应的二进制数即可

10进制和二进制

10到2

短除法

2到10

按权展开法或二分法

前中后缀转换

中转前后

正解

如A+B*(C−D)−E/F

我们对其建一颗表达式树

这个树是怎么建出来的呢?

先别着急,我们先给这式子加个括号:$(A+(B\times(C-D)))-(E÷F)$

显然,最后被计算的那个就是没有被括号包围的那个减号,因此这个减号放在根节点,然后这个根节点的左子树就是左边那个括号里面的内容,右子树就是右边那个括号里面的内容,递归进行分解就可以写出如上的树

有了这个树之后,问题就变得非常明了了,要求什么遍历就对这个树进行一次什么遍历就可以了(不要告诉我你连前中后序遍历都不知道)

神仙方法:

一个中缀式到其他式子的转换方法(其实是正解的简化版)

这里我给出一个中缀表达式

$a+b*c-(d+e)$

第一步：按照运算符的优先级对所有的运算单位加括号

式子变成：$((a+(b*c))-(d+e))$

第二步：转换前缀与后缀表达式

前缀：把运算符号移动到对应的括号前面

则变成：$-( +(a *(bc)) +(de))$

把括号去掉：-+a*bc+de 前缀式子出现

后缀：把运算符号移动到对应的括号后面

则变成：$((a(bc)* )+ (de)+ )-$

把括号去掉：$abc*+de+-$ 后缀式子出现

发现没有，前缀式，后缀式是不需要用括号来进行优先级的确定的。

前,后转中

显然对于唯一确定的后缀表达式,可能有不同的前中缀表达式

所有这个问题不需要过多探讨,因为假设在选择题里面考到,也不可能不给你中序遍历,既然要给出中序遍历,那么就直接用上面的方法通过答案推条件就行

关于地址总线宽度

32位总线跨度可以寻址$2^{32}B,1GB=2^{30}B;所以2^{32}B=2^2GB=4GB$;

地址总线宽度为32位,一次可以发送的一个数据是32位的，则寻址的单元最大就是32位数据的最大值，就是$2^{32}$B。

地址总线宽度决定了CPU可以访问的物理地址空间，简单地说就是CPU到底能够使用多大容量的内存。

无线通讯技术进展

这部分全是废话

（1）平流层气球通信

1997年1月，在ITU-R SG9会议上，美国SkyStation International公司提出了一种崭新的47/48GHz平流层气球通信技术，设想在离地20～24km高处外型如汽艇的内充氦气的气球之间，以激光或卫星方式连网，建立全球气球平台，覆盖全球，组成高速互联网，将收到的信息中继转发给便携式多媒体终端。

（2）广带无线接入

所谓广带是指网络速率高于10Mbit/s的传输系统，比宽带网络具有更高的系统性能指标。广带无线网际网络接入系统标准是针对微波及毫米波段中新的空中接口标准，它具有高速率、多速率、新频道、多样化、抗干扰性强等特点，能够成功地支持无线接入多媒体数据通信、数据网络、视频、多媒体等结合业务网络的信息传输，同时还兼有灵活机动的特点，适用于商务大楼、热点地区及家庭用户的宽带接入。

（3）蓝牙技术

蓝牙是针对目前近距离的便携式器件之间的红外线链路(Infrared link，简称IrDA)而提出的，是一种无线数据与语音通信的开放性全球规范，它以低成本的近距离无线连接为基础，为固定与移动设备通信环境建立一个特别连接的短程无线电技术。

（4）GSM

GSM/DCS的目标是在移动设备(或任何便携设备)之间提供各种各样的业务，包括语音传输和报文处理业务(X. 400、传真传输、紧急呼叫以及各种类型的数据传输业务)。

（5）CDMA

CDMA中的模拟语音被编码成数字信号，且每个对话都被分配给一个惟一的代码(为每个独立的传输分配一个“签名”)，一个小区内的所有用户使用同一个带宽频谱(而不是该带宽的一部分)。在CDMA接收端，通过使用补码，可以从已编码信号中恢复原始信号。接收机以相干方式把多径接收信号组合起来，这样可以改善信号的质量

（6）无绳系统

CT2 CAI和DECT(欧洲数字无绳通信)一起组成了无绳系统的欧洲标准。CT2可以支持语音和数据业务。作为向第2代无绳电话系统发展的一种方法，DECT标准始于20世纪80年代中期的欧洲邮政和远程通信会议(CEPT)，DECT也被认为是支持大容量PABX系统的合适技术[GRIL93]。DECT工作于1 880～1 990MHz频段，同CT2一样，它用ITU-T G.721推荐标准所规定的ADPCM对语音进行编码，而且，32kbit/s的语音信号按TDMA方式接入。DECT并不限于只传语音信号，它也支持数据应用。

（7）蜂窝数字数据分组系统(CDPD)

几家公共电信运营商已经就现存数据网络的无线扩展制定了规范，称为蜂窝数字数据分组系统(CDPD)规范，其目的是提供到移动通信用户的无线分组数据连接[CDPD93]。开发CDPD的目的是利用现有先进移动电话系统的未用容量以及利用像无连接网络层协议(CLNP)、IP、OSI运输层、TCP等现有的数据通信协议。CDPD的体系结构基于OSI模型，它来自ISO 7498和CCITT的OSI X.200建议。这种体系结构中有两个基本的网络实体：端系统(ES)和中间系统(IS)。ES是一种用户设备，它在因特网中叫做主机，IS是一种互通设备，在因特网中被称作路由器。

（8）第三代移动通信系统

3G系统的研究工作是由欧洲委员会、CCIR和ETSI发起的，这一系统被称为“通用移动通信系统(UMTS)”。这些新系统可能采取的拓扑结构是混合小区体系结构，采用大小可变的小区，可以满足具体的地理区域和业务要求。该技术面临的挑战是手机，它必须能无缝地跨越所有的小区。

（9） i–Mode

i–Mode使用压缩格式HTML，即CHTML(Compact HTML)，在800MHz PDC(Personal Digital Cellular System)分组交换通信网上开通移动因特网业务，内容包括：因特网电子邮件、移动银行服务、航班信息、股票信息、新闻、天气和体育消息，提供证券、银行、生命保险公司、信息卡公司的信息以及移动食谱、房屋租借、日英字典等。

（10）WAP

无线应用协议(WAP，WirelessApplication protocol)其实是一种浏览器，我们平常最熟悉的浏览器莫过于Netscape和IE，可是这两者是运用于计算机、固定电话上网的。而要利用移动电话上网，就要用另一种浏览器WAP。WAP的基本原理是把网站上的内容予以简化，再利用无线网络传到手机上，使其可以利用手机的小屏幕取代计算机屏幕，而成为具有互动性质的工具。WAP的目标是使互联网的内容和各种增值服务适用于手机用户和各种无线设备用户，并能适用于不同的无线网络技术。

（11）GPRS

通用分组无线业务(GPRS，GeneralPacket Radio Service)是移动环境中高速数据传输的解决方案。GPRS技术作为GSM向第三代移动通信发展的过渡技术，由于具备节省建设投资、可充分发挥原有设备作用、建设周期短等多种优点，因此被越来越多的电信运营商青睐。GPRS技术可以充分利用现有GSM系统的设备，为用户提供移动数据传输服务，并可为因特网/ISP和企业内部网提供基于分组的高速、安全的无线接入

（12）LAS-CDMA(大区域同步码分多址联接)

LAS-CDMA技术将成为未来“全IP”系统(3.5G或4G)的自然选择,LAS-CDMA技术具有以下特点：首先是，附加频谱。由于LAS-CDMA可提供比现有2G标准高20多倍的容量以及比cdma2000高3至6倍的容量，所以可最大限度地减少附加网络的建设和开支，从而使电信公司能以较低的成本在市场上竞争，并以最经济的方式向客户提供新颖和优良的服务。其次是，新型的网络结构。从设计角度看，LAS-CDMA技术不仅能够强化当前的2G网络，而且还能为3G提供前所未有的功能，并能成功地推动第四代(4G)无线网络的发展。这些优势可使电信公司获得多方面的利益，其中包括近期和长期利益。这项先进技术在开发中统筹兼顾，可适用于各代无线通信系统的体系结构。电信公司可通过这项技术轻而易举地发展各自的系统而无需在网络结构上做额外的修改，从而大幅度地降低成本、缩短工期。在全球兼容性方面，由于LAS-CDMA与所有现行和未来的标准兼容，故易于现有系统向LAS-CDMA过渡。此外，LAS-CDMA还能顺应各项可进一步提高系统性能和容量的先进技术。作为一项空中接口技术，LAS-CDMA可通过配置使其作为一种增强模式与UTRA、IS-95、IS-2000以及TD-SCDMA等其他现用系统兼容。最后，LAS-CDMA还可显著地改进服务质量。在这方面，LAS-CDMA可通过其专利扩频技术大幅度地消除目前CDMA系统上出现的干扰现象。因为这种现象不仅影响语音服务质量，而且最终也会影响数据服务质量。在LAS-CDMA系统中，所有信号的码间干扰(ISI)和多址干扰(MAI)都可在“无干扰”时间窗口内降为零，相邻蜂窝区干扰(ACI)也可降低到边际水平。因此，LAS-CDMA不仅提高了系统性能和容量，而且也不会在其他CDMA系统上增加任何复杂性。

各种排序

计数排序(选总统)

时间复杂度:$O(a+n)$,a是值域,不基于比较,基于”分位分类”,也就是统计

选择排序

从所有数中选出最小的放到第一个,然后选第二小的放到第二个,…….时间复杂度为$O(n^2)$,不稳定

(注意:稳定的意义不是时间复杂度随数据形式的变化而不变,而是如果两个相同的数一个在前一个在后,排完序后还是在前面的在前面,在后面的在后面)

冒泡排序

时间复杂度为$O(n^2)$,稳定

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

插入排序

时间复杂度为$O(n^2)$,稳定

插入排序的工作方式像许多人排序一手扑克牌：

左手为空，桌子上牌面向下
每次从桌子上拿走一张牌插入左手中正确的位置
为了找到正确位置，从右到左将它与已经在手中的每张牌进行比较，然后插入
重复步骤2~3

归并排序

时间复杂度$O(nlogn)$,稳定,需要额外辅助空间

快速排序

时间复杂度$O(nlogn)$,不稳定,最坏$O(n^2)$

堆排序

时间复杂度$O(nlogn)$,不稳定(优先队列的原理)

贪心

哈夫曼编码

废话不多说,记住这个东西是怎么操作的就行

放个链接

简单DP

一个 1×8 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________种填涂方案。

答案:55种

解法一:DP,很简单的,这里就不提了

解法二:斐波那契

n个方格的填涂分为两种情况。

1、第一个方格为黑色，那么第二个方格一定是白色，所以第一种情况数就是n-2个方格的填涂方案数。

2、第一个方格为白色，那么第二个方格不定。所以第二种情况数就是n-1个方格的填涂方案数。

所以f(n)=f(n-1)+f(n-2)，也就是说这是一个斐波那契数列问题。边界条件是：f(1)=2(黑,白)；f(2)=3(黑白,白白,白黑)。则有：

F(n)=F(8)=f(6)+f(7)=55

算法时间复杂度分析

常用方法:

数列求通项公式

常规内容,应该比较简单的罢(~~但鉴于我常规数学学得渣,还是来一道例题推导一下~~):

【NOIP2015初赛】某算法的计算时间表示为递推关系式：

$T(N)=T(N−1)+N,T(0)=1$,则该算法的时间复杂度为______________________________________________________。

A.$O(log_2{2N})$ B.$O(Nlog_2N)$ C.$O(N)$ D.$O(N^2)$

$T(N)=T(N−1)+N,T(0)=1$

则$T(N)-T(N-1)=N$

$T(N-1)-T(N-2)=N-1$

$……$

$T(1)-T(0)=0$

所有式子加起来得到

$T(N)=\sum_{x=0}^{n}x=\frac{(1+n)\times n}{2}$

因此时间复杂度是$O(N^2)$,选D

主定理

有递推关系式$T(n)=aT(\frac{n}{b})+f(n)$

则当存在常数$e>0$使得$f(n)=O(n^{log_ab-e})$时,$T(n)=O(n^{log_ba})$

当存在常数$k>=0$使得$f(n)=O(n^{log_b^a}log^kn)$时,$T(n)=O(n^{log_ba}log^{k+1}n)$

当存在常数$e>0$使得$f(n)=O(n^{log_ab+e})$时,$T(n)=O(f(n))$

~~关于我的黑暗记背法~~

鉴于这个东西要微积分的知识才能够理解并推导,而我现在又没有时间去学透微积分了,因此我利用当年世界脑力锦标赛训练的方法以如下过程记住了主定理:

将字母和5个符号(加,减,乘方,左括号,右括号)一一映射到1~31这些正整数上去:

a=01 b=02 c=03 d=04 e=05 f=06 g=07 h=08 i=09 j=10
k=11 l=12 m=13 n=14 o=15 p=16 q=17 r=18 s=19 t=20
u=21 v=22 w=23 x=24 y=25 z=26 +=27 -=28 ^=29 (=30 
)=31

然后将上面的公式的关键部分按照电脑的方式打出来(没有缩进和下标,一切标记由符号显示):


n^(logba-e)
n^(logba)
n^(logba)log^kn
n^(logba)log^(k+1)n
n^(logba+e)
f(n)

然后写了一个程序来输出映射关系:

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define ll long long
#define isdegit(r) ((r>='0'&&r<='9'))
template<typename T>void read(T &x){
	x=0;char r=getchar();T neg=1;
	while(!isdegit(r)){if(r==45)neg=-1;r=getchar();}
	while(isdegit(r)){x=(x<<1)+(x<<3)+r-48;r=getchar();}
	x*=neg;
}
char s[100];
int T;
int main(){
	freopen("in.txt","r",stdin);
	read(T);
	while(T--){
		scanf("%s",s);
		int len=strlen(s);
		loop(i,0,len-1){
			if(s[i]>='a'&&s[i]<='z')printf("%.2d ",s[i]-'a'+1);
			else if(s[i]=='+')printf("27 ");
			else if(s[i]=='-')printf("28 ");
			else if(s[i]=='^')printf("29 ");
			else if(s[i]=='(')printf("30 ");
			else if(s[i]==')')printf("31 ");
			else if(s[i]=='=')printf("32 ");
		}printf("\n");
	}
	return 0;
}

然后点击运行键,tada!:

14 29 30 12 15 07 02 01 28 05 31

14 29 30 12 15 07 02 01 31

14 29 30 12 15 07 02 01 31 12 15 07 29 11 14

14 29 30 12 15 07 02 01 31 12 15 07 29 30 11 27 31 14

14 29 30 12 15 07 02 01 27 05 31

06 30 14 31

~~然后,最关键的部分来了…我把这些数字背了下来,明天再默写出来就相当于是可以直接套用主定理了哈哈哈哈~~

不建议他人使用,这是一种降智的操作!

例题:

【NOIP2017初赛】若某算法的计算时间表示为递推关系式：

$T(N)=2T(\frac{N}{2})+NlogN,T(1)=1$,则该算法的时间复杂度为___。

$A.O(N) \ B.O(Nlog_2N) \ C.O(Nlog_2^2N) \ D.O(N^2)$

【解析】套用情况2中的k=1的情况，则$T(n)=O(Nlog_2^2N)$,选C

【NOIP2016初赛】若某算法的计算时间表示为递推关系式：

$T(N)=2T(\frac{N}{4})+\sqrt{N},T(1)=1$,则该算法的时间复杂度为___。

$A.O(N) \ B.O(\sqrt{N}) \ C.O(\sqrt{N}log_2N) \ D.O(N^2)$

【解析】套用情况2中的k=0的情况，则$T(n)=O(\sqrt{N}log_2N)$,选C

特征方程

为了节省时间,直接上图片了

例题:

若$f[0]=0,f[1]=1,f[n+1]=\frac{f[n]+f[n-1]}{2}$,则随着i的增大,$f[i]$将接近于:

解:

设$f[n-1]=x^0,f[n]=x^1,f[n+1]=x^2$

则$x^2=\frac{x+1}{2}$

$2x^2-x-1=0$

解得$x_1=-\frac{1}{2},x_2=1$

因此设原递推式为$a(-\frac{1}{2})^i+b(1)^i$

因为当$i=0$时,值为0,$i=1$时,值为1,故

\begin{cases}

a+b=0\-\frac{1}{2}a+b=1

\end{cases}

解得

\begin{cases}

a=-\frac{2}{3}\b=\frac{2}{3}
\end{cases}

因此原递推式为$f(n)=-\frac{2}{3}(-\frac{1}{2})^n+\frac{2}{3}(1)^n$

当n无限大的时候,有$-\frac{2}{3}(-\frac{1}{2})^n$趋近于0,即原式趋近于$\frac{2}{3}$

(其实我觉得不需要线性代数的知识也可以理解这个知识点~~)

指针

~~鬼畜啊,鬼畜啊~~

先给个链接

这哥们讲的挺好的

然后就是那啥,归纳一下常见的操作和关键点喽,明天看会不会遇到这类题

&i,取 i 变量所在的地址编号
pi = &i;,把 i 地址的编号赋值给 pi
指针变量所存的内容就是内存的地址编号
*pi ,pi 内容所指的地址的内容

结语

update 2019年10月24日15:27:13

成绩出来了,86pts,算是稳进复赛了吧,但是看到比我还努力的一些同学比我这个态度不端正的家伙还考的差的时候,我感到非常不舒服.~~也许用”不舒服”这个词才能够表达出这种怪异的感觉吧~~.没有付出劳动的人能够享受果实,而真正做贡献的人却在吃土…这不就是马克思口中的阶级矛盾嘛,无产阶级受到中产阶级的剥削,最后造成伟大的无产阶级专政,之后进入一个共产主义社会(~~今天中午刚刚重看了苏菲的世界马克思那一章哈哈~~)..

哎呀扯到哪里去了我的妈呀.不管那么多了,进了就进了吧,

面对这种情况,我只好非常不负责任的说:~~这次CSP-S复赛就考着玩吧~~

这张图值得纪念:

捕获.PNG