数据结构和算法

迭代法求平方根和立方根

迭代法求值在数值计算中是一种常用的方法,思路也很简单:首先得有一个迭代公式,比如 $$ z = z - \frac{z^2-x}{2z} $$, 然后给一个初值比如 z = 1.0, 然后不断滴代入公式, 然后结果会不断滴趋近于要求的值,这里就是 x 的平方根。 下面是一些求平方根和立方根的迭代公式,这些公式是某些大家一不小心找出来的或是创造出来的,至于肿么找的或是创造的,这不是 me 关心的事,O__O"…

Newton 算法

平方根 : $$ z = z - \frac{z^2-x}{2z} $$

Babylonian 算法

平方根 : $$z = (z + \frac{x}{z})\cdot\frac{1}{2} $$

立方根 : $$z = (2z + \frac{x}{z^2})\cdot\frac{1}{3} $$

Tags: 

手工开平方

手工开平方

现在有了计算器就是好,掏出计算器开平方完全不在话下,而且是高精度。比如 windows 下的 $$ \sqrt{3} $$= 1.7320508075688772935274463415059 。不过这里要介绍的是一种手工开平方的方法,可能以后永远都不会用上,但是方法就在那里,会不会不是方法的问题。

先回顾一下试除法计算商,比如 $$ \frac{71}{3} = $$ ? 对齐位置,比如用 3 去除 7, 试着商 2, 余 1。余数添上后一位变成 11,然后除以 3, 试商 3, 余 2。再添加 0,变成 20, 除以 3, 商 6 ,... 所以,$$ \frac{71}{3} = 23.6... $$

Tags: 

并查集(union-find-set)

并查集

并查集,即为 union find set,实际上就是说对于集合 set,只有两个操作, 查找 find 和合并 union。它是一种典型的数据结构,用在一些典型的地方。比如说有一些人,他们之间有些人是朋友关系,假设“朋友的朋友也是自己朋友”,那么这些人就可以分成若干伙儿,现在给出一些朋友关系,让给出有多少伙,以及每一伙儿都有哪些人。类似的问题还有很多,比如:

Tags: 

剑指offer上的另外一些题目

基本都是数据结构和算法的小题目,可以帮助 me 们锻炼一下编程能力,实际上更多的是分析和解决(小)问题的能力,而编程只是把已有的想法用编程语言描述了一下而已。前面的一些题目也只是描述了大致的思路而已,有些题目程序 me 也还么有写,不能认为这是无关紧要的,“眼高手低”的事情,谁都遇到过,u and me !不过现在时间有限,先把题目罗列一下,然后描述下思路才是当务之急。

Tags: 

剑指offer上的一些题目

me 发现实验室真不是学习的地方,至少 me 在实验室几乎都上网了,O__O"…。昨天去图书馆借了本剑指 offer,看了一个小时,看到了一些题目,有的题目已经见过,他上面说的解题方法也已经知道了,有些么见到。题目要么是语言有关的,要么是数据结构有关的,要么是算法有关的,赶脚都很不错,所以,写下来,围观一下。对了,不要迷信答案,比如前不久微软面试题上面有个 char *p="hello", *q="hello"; 问,p == q 吗?实际上,这是 undefined behavior !but,剑指 offer 上是说 p 和 q 相等,也就是 "hello" 只保存一份!再次说明,不一定!是一份还是两份,至少语言层面没有限定,某个编译器可以只当一份保存,另外一个编译器也可以保存两份!(如果说介对 me 们有神马启发的话,me 赶脚是多看点东西还是比较好点,一家之言难免有错,me 亦如此。)

Tags: 

链表

“今日事,今日毕。”貌似小学就听说了这句名言,本身也挺有道理,然而去做的话,却不是那么容易的事。很久之前,有多久呢?腾讯笔试貌似是上个月 13 号一个周六的事,me 记得,前一天,me 就要写一篇 blog 记录一下链表的程序,然而错过了,介个一错就是大半个月(现在都五月三号勒!)。

问题起因于一个问题:肿么判断两个链表 A 和 B,有没有交点;如果有的话,找到交点位置。

分析

如果说两个链表 A 和 B 有交点 inode 的话,那么,inode 后面的结点便是 A 和 B 共有的结点,而 inode 是最初的一个。所以呢,只需要判断 A 中是不是有一个结点在 B 链表中就可以判断了。如果要找交点位置的话,只需要找到 A 中结点在链表 B 中的第一个结点就可以。如果我们顺序滴遍历 A 中的每个结点,然后搜寻是否在 B 中,就可以一下子完成这两个任务。

Tags: 

快速排序和寻找中位数

介个,肿么说,第一句话要肿么说才好,O__O"…。腾讯实习生笔试中有一道题目,问求 n 个数的最大值和最小值,需要的最少比较次数是多少?问题绝不是简单滴 2n-2 或是 n-1 就算彻底解决了。me 怀疑它的答案可能是 3n/2。为嘛,这里不多说。(因为这本是个引子而已,并不是现在要讨论的东西。)现在 me 们关心的问题是,求 n 个数中的中位数,肿么求?有神马比较好的求法嚒?

Tags: 

Dijkstra最短路径算法

闲逛贴吧,看到一个童鞋问一个图的 Dijkstra 最短路径算法,me 思考了片刻,打算自己写一写,看看水平是不是下降勒,O__O"…,程序写的相对来说比较顺利,但是也遇到了若干个问题,比如如何表示无穷大、如何消除有无穷大的加法、如何保存路径信息、如何输出结果和如何使得开始节点可以调节(而不是硬编码写死)等,最后就有了这篇 blog。先看看人家给的图:

Tags: 

Catalan数

me 一个童鞋跟 me 提过一个问题:说1-12 这 12 个数,分成 2 组,然后每组按大小排序,其中一组中的数总是比另外一组中对应顺序的数要大,问有多少种情况?me 还真做不出来,他告诉 me 说这是Catalan数。即使他这么说,me 貌似还是不太明白。不过这不影响,me 简单搜索一下这个数(其实me以前就有所耳闻),有好几个用处,简单罗列一下。

平衡括号

平衡括号:在一个合法的算术表达式中可以出现的括号都是平衡括号,更专业一点的说法应该是“所有的左括号和右括号可以建立一对一的对应关系,并且左括号在对应的右括号左侧”。像()(), (())(), (()())(()) 都是平衡括号,但是(()))(, ()())() 就不是平衡括号。

观察一下特点,判断所给的一个括号串是不是平衡很容易:设置一个计数器,初始值为 0,然后从左向右数,遇到左括号 +1,遇到右括号 -1,在过程中不出现负数,并且最终的计数器还是 0,那么就是平衡括号;除此之外就是非平衡括号。

现在的问题是,如果有 n 对括号,问平衡的情况有多少种?暂时可以数一下 n = 1, 2, 3, 4 时的情况:

Tags: 

最大以及最小连续子序列

一个序列,比如 3、6、-2、4、-7、5 的最大连续子序列是 3、6、-2、4,和是 11。求最大的序列值,方法有好几种。最简单的方法是,我们找出来所有的子序列,求和,然后找到它们的最大值。如果序列长度为 n,那么子序列应该有 C(2,n) = n*(n-1)/2 种,然后计算和并找出最大值,复杂度应该是 O(n^3)。

如果我们写代码的话,结构应该基本如下:

Tags: