分类
Python

Ackermann函数

Ackermann函数的历史

1920年代后期,数学家大卫·希尔伯特的学生Gabriel Sudan和威廉·阿克曼,当时正研究计算的基础。Sudan发明了一个递归却非原始递归的Sudan函数。1928年,阿克曼又独立想出了另一个递归却非原始递归的函数。
他最初的念头是一个三个变量的函数A(m,n,p),使用康威链式箭号表示法是m→n→p。阿克曼证明了它是递归函数。希尔伯特在On the Infinite猜想这个函数不是原始递归函数。阿克曼在On Hilbert’s Construction of the Real Numbers证明了这点。
后来Rózsa Péter和拉斐尔·米切尔·罗宾逊定义了一个类似的函数,但只用两个变量。

Ackermann函数的递归定义

Ackermann函数的意义

似乎直接看定义的话看不出这个函数有多“恐怖”。
Ackermann函数可以看成关于n的一个函数序列,其中第0个函数返回n+1,而第m个函数则是将第m-1个函数对1迭代n+1遍。
如果我们定住其中一个变量(比如m),试着推一下通项公式:
Ackermann(0,n)=n+1
Ackermann(1,n)=n+2
Ackermann(2,n)=2*n+3
Ackermann(3,n)=2^(n+3)-3
Ackermann(4,n)=2^2^2^……^2-3,乘幂中共有n+3个2。
当m≥4,Ackermann函数的增长快得惊人。
Ackermann(4,0)=13,
Ackermann(4,1)=65533,
Ackermann(4,2)=2^65536-3有19729位,
而Ackermann(4,3)则即使是位数也不易估计。
Ackermann(5,0)=65533,
Ackermann(5,1)=Ackermann(4,65533)……

可以发现,Ackermann函数的增长异常恐怖,只要我们数几个数(1,2,3,4,5)它就已经爆炸了…几乎瞬间超出了宇宙中的原子数,这,就是迭代的威力
当然,万事万物都有它的反面。我是说,如果Ackermann函数增长得太快,那么什么是增长地比较慢的呢?
Ackermann^-1(x)!
(我特意用了中文感叹号来表示这不是阶乘的意思)
实际上,在带路径压缩的并查集(DisjointSet)中,这个数据结构的时间复杂度中就引入了阿克曼函数的反函数(更准确地说,单次操作的均摊成本是O(alpha(n)),其中n为元素个数,alpha()是阿克曼函数的反函数,这个数字在本世纪应该都不会达到5,在渐近意义上是要优于O(log2(n))对数复杂度的)

Ackermann函数的递归计算中间过程输出

用Python弄了个递归计算Ackermann函数中间过程的函数(以数学可读的方式)
Code:(Python3.6.7)

def Ackermann(expr):
print("=", expr.replace("(", " A(")) # 以人可读的方式输出
l = expr.rfind("(") # 找到左括号
r = expr.find(")") # 找到右括号
if l == -1 or r == -1: # 没找到说明当前表达式即是答案,递归终止
return
args = expr[l : r + 1] # 若找到
mid = args.find(",") # 由','隔开的两边分别读为m和n
m = int(args[1:mid])
n = int(args[mid + 1 : r - l])
if m == 0: # Ackermann函数的计算方式
new = str(n + 1) # 并将之格式化以继续递归
elif n == 0:
new = "(" + str(m - 1) + ",1)"
else:
new = "(" + str(m - 1) + ",(" + str(m) + "," + str(n - 1) + "))"
Ackermann(expr.replace(args, new)) # 每次替换后继续计算

while 1:
m = input("input m:") # 输入m,n
n = input("input n:")
expr = "(" + m + "," + n + ")"
Ackermann(expr) # 实测当m,n稍微大一些(大于5)的时候递归层数就过多了

测试:

input m:2
input n:1
= A(2,1)
= A(1, A(2,0))
= A(1, A(1,1))
= A(1, A(0, A(1,0)))
= A(1, A(0, A(0,1)))
= A(1, A(0,2))
= A(1,3)
= A(0, A(1,2))
= A(0, A(0, A(1,1)))
= A(0, A(0, A(0, A(1,0))))
= A(0, A(0, A(0, A(0,1))))
= A(0, A(0, A(0,2)))
= A(0, A(0,3))
= A(0,4)
= 5
分类
Visual Studio

VS2017中”This function or variable may be unsafe”警告的解决方法

警告原因

C语言标准输入函数scanf / gets等在设计的时候都没有考虑到写入内存越界的问题,导致有时候会发生玄学错误(当然这大多数时候都是使用函数的人写挫了的问题,C语言并不会限制你干很多也许并不正确的事情)。
为了解决这个问题,VS(大概是2013及以后的版本)中提供了C语言这些标准输入函数的替代品:scanf_s / get_s等,通过额外参数限制内存读写范围来确保你的输入函数不会做可怕的事情,关于这些函数不是这篇blog讲解的范围,具体可见这里

解决

当然,我推荐你听从VS的建议,使用scanf_s等更加“安全”的函数,不过如果是那样的话你大概不会点进这篇blog。
通过分析报错信息,我们可以找到关于这个警告的错误信息的宏定义:

"crtdefs.h"
#define _CRT_INSECURE_DEPRECATE(_Replacement) _CRT_DEPRECATE_TEXT("This function or variable may be unsafe. Consider using " #_Replacement " instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.")

那么根据这条宏定义的提示,我们只需要在源代码前面(理论上是在所有代码之前)定义这个_CRT_SECURE_NO_WARNINGS变量就好了

//在你的程序开头加入这句话
#define _CRT_SECURE_NO_WARNINGS
...

如果不想在自己的代码最前面加入这句话怎么办呢…
那就让VS帮你加上!

在项目属性设置中的预处理器定义部分的参数末尾加上_CRT_SECURE_NO_WARNINGS就好了
以VS2017为例:

分类
Git

Git基础(一)Git概述

Git基础

为什么要使用Git?

试想一下你(或你的团队)正在维护一个较大的项目,项目代码每天都有很多的修改(当然,有时候这也可能不只是因为甲方不停地修改需求)。有一天,你突然发生了以下几种情况:
– 不小心删除了某文件或者某部分代码
– 发现之前的某个版本的某部分代码可以拿来给当前版本用
– 发现自己修bug结果却修出了更多bug,你想要撤回自己的操作

当然,也许可以通过每次一更改就保存一个备份来解决这些问题(或者通过脑子记下来,但这并不推荐),这样显然会造成冗余——特别是当修改操作特别频繁或项目文件特别庞大的时候,十分浪费宝贵的硬盘空间。
我们所能想到的最好的方式就是保存更改过的所有文件的版本——只需要知道每次修改的部分是哪个文件(并且通过文件比对知道改了什么)就好了。这就是我们为什么要使用Git。
请注意,我是说,Git并不是存储的增量(例如记录小A今天加了一句话或者删了一句话,事实上如果这样子做反而很麻烦),而是如果这个文件改过了,直接将这个文件全部保存一份。当然,对于没有更改过的文件,就记录一个指针指向没改过的原来的那个文件就好了(这样来达成一个效率上的优势)。

Git的诞生

回想当年社区共同维护Linux的时候,Linus本人在很长一段时间内都是将开发者贡献的代码手动添加到Linux源码中(是的,这听起来一点都不像Linus)。直到后来,Linus花了2周时间用C写了个工具来管理项目源代码——这就是Git的诞生。

基本概念

  • 工作区: 一般就是本地项目文件目录
  • 暂存区(stage/index): 暂时存放文件的地方,一般存放在 “.git目录下” 下的index文件(.git/index)中
  • 版本库: 工作区下的隐藏目录.git

简单地描述Git的工作原理:

工作区是我们直接编辑修改的地方
每当我们想形成一个新版本(修复了若干bug)的时候,就可以将修改了的文件先放到缓存区,然后一起提交。(因为我们想要所有这些修改构成一次版本的更新,而不是n次,所以先一起存起来)
最后一起将缓存区的文件更新到版本库,生成一个船新版本
如果想要回退到某个版本,只需要到版本库中找到对应的版本并替换工作区的文件就好了

安装Git

如果你是Windows用户,你可以到Git官网上下载最新版本的Git或者到Github上下载源代码并编译
如果你是Linux/Mac OS用户,我相信你应该会自己安装
对于以上三种系统的用户的安装教程,可以参考这篇Git安装教程
安装完成后,运行Git Bash
对于Windows用户,打开Git Bash后,会出现一个黑洞洞的命令行窗口,这就是Git
随后,对于所有系统的用户,启动了Git后,在命令行输入:

$ git config --global user.name "Your Name"
$ git config --global user.email "email@example.com"

这里的$是命令提示符,将Your Name和email@example.com替换成你自己的用户名和邮箱。
毕竟要考虑到,多人协作时,要能够追溯出这个新(b)功(u)能(g)是谁写出来的吧,所以需要一个用户名来标识你自己。

分类
essay

Hello World!

To see the world, things dangerous to come to.
To see behind walls, to draw closer.
To find each other and to feel.
That is the purpose of life.