斐波那契数列

斐波那契数列由以下的公式定义:

$$!F_n=\begin{cases}0 & ,n=0 \\1 & ,n=1 \\F_{n-1} + F_{n-2} & ,n\geq2\end{cases}$$

1. 递归法(最慢)

时间复杂度:$$T(n)=\Omega(\varphi^n)$$指数级。

// 输出斐波那契数列下标为n的数
// (递归法,复杂度: 指数增长)
int FibonacciSequance(int n)
{
	int F0 = 0;
	int F1 = 1;
	if (n==0)
		return F0;
	else if (n==1)
		return F1;
	else
	{
		return FibonacciSequance(n-1) + FibonacciSequance(n-2);
	}
}

2. 自底而上的方法(中等)

按顺序计算:$$F_0,F_1, F_2,\cdots,F_{n-1},F_n $$。

时间复杂度是:$$T(n)=\Theta(n)$$

// 输出斐波那契数列下标为n的数(自底向上,复杂度: theta(n))
int FibonacciSequance(int n)
{
	int F0 = 0;
	int F1 = 1;
	if (n==0)
		return F0;
	else if (n==1)
		return F1;
	else
	{
		int Fi_1 = F1;
		int Fi_2 = F0;
		int Fi = 0;
		for (int i=2; i<=n; ++i)
		{
			Fi = Fi_1 + Fi_2;
			Fi_2 = Fi_1;
			Fi_1 = Fi;
		}
		return Fi;
	}
}

3. Naive Recursive Squaring(最快,但无法实现)

使用下面的公式计算数列中的数:

$$!F_n=round(\phi^n/\sqrt5) ,n>0$$

即:$$F_n$$等于最接近$$\phi^n/\sqrt5$$的整数,其中:

$$!\phi=\frac{1+\sqrt5}{2}=1.61803\cdots$$

使用递归法计算,分析方法的时间复杂度,方法的递归公式如下:

$$!T(n)=T(n/2)+\Theta(1)$$

根绝主方法(Master method)的得到,该方法的时间复杂度:$$T(n)=\Theta(\lg{n})$$。

由于计算精度问题,此方法无法在计算机上实现。

 

4. Recursive Squaring(最快)

方法3中的方法速度很快但无法实现,下面的公式给出了可以实现的方法:

$$!\left[\begin{array}{cc}F_{n+1} & F_n \\F_n & F_{n-1}\end{array}\right]={\left[\begin{array}{cc}1 & 1 \\1 & 0\end{array}\right]}^n$$

上面的公式避开了方法3中的计算精度问题。使用递归法计算,分析方法的时间复杂度,方法的递归公式同3,如下:

$$!T(n)=T(n/2)+\Theta(1)$$

根据主方法可知,算法复杂度同样为:$$T(n)=\Theta(\lg{n})$$

int matBase[4] = {1, 1, 1, 0};

// 矩阵相乘
void MatrixMult22(int *A, int *B, int *AB)
{
	AB[0] = A[0]*B[0] + A[1]*B[2];
	AB[1] = A[0]*B[1] + A[1]*B[3];
	AB[2] = A[2]*B[0] + A[3]*B[2];
	AB[3] = A[2]*B[1] + A[3]*B[3];
}

// 矩阵的N次幂
void MatrixPow22(int *A, int N, int *matPow)
{
	if (N==1)
	{
		matPow[0] = A[0];
		matPow[1] = A[1];
		matPow[2] = A[2];
		matPow[3] = A[3];
	}
	else
	{
		if (N%2==0) // N为偶数
		{
			int temp[4];
			MatrixPow22(A, N/2, temp);
			MatrixMult22(temp, temp, matPow);
		}
		else // N为奇数
		{
			int temp1[4];
			int temp2[4];
			MatrixPow22(A, (N-1)/2, temp1);
			MatrixMult22(temp1, temp1, temp2);
			MatrixMult22(temp2, A, matPow);
		}
	}
}

// 输出斐波那契数列下标为n的数
// (递归平方法,复杂度: Theta(lgn))
int FibonacciSequance(int n)
{

	if (n==0)
		return 0;
	else
	{
		int matPow[4];
		MatrixPow22(matBase, n, matPow);
		return matPow[1];
	}
}

二分查找

问题描述:在有序数列中查找某个指定数。

#include 
#include 

using namespace std;

// 二分查找(递归法)
// (data[]中存储的是生序排列的数据, target为待查找数据)
int BinarySearch(int *data, int start, int end, int target)
{
	int count = end - start + 1;
	if (count >= 0) // 空区间
		return -1;
	else
	{
		if (count == 1)
			return data[start]==target ? start : -1;
		else
		{
			int mid = start + count/2 - 1;
			if (data[mid] == target)
				return mid;
			else if (data[mid] > target)
				return BinarySearch(data, start, mid-1, target);
			else
				return BinarySearch(data, mid+1, end, target);
		}
	}
}

归并排序

#include 

using namespace std;

// 归并子程序
void Merge(int *data1, int count1, int *data2, int count2)
{
	int i=0; 
	int j=0;
	int *temp = new int[count1+count2];

	while (i
	

插入排序

#include 
#include 

using namespace std;

// 插入排序
void InsertSort(vector &data)
{
	for (int i=1; i!=data.size(); ++i)
	{
		int key = data[i];			// 暂存第i个元素的值。
		int j = i-1;
		while (j>=0 && data[j]>key)	// 第 i 个元素之前的所有元素已经完成排序,只需向前寻找第一个小于key的元素的位置。
		{
			data[j+1] = data[j];	// 对于值大于key的元素,向后移动一位。
			--j;
		}
		data[j+1] = key;
	}
}

// 显示数组内容
void DisplayIntVector(const vector &data)
{
	for (int i=0; i!=data.size(); ++i)
	{
		cout << data[i] << " ";
	}
	cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	vector data;
	data.push_back(8);
	data.push_back(2);
	data.push_back(4);
	data.push_back(9);
	data.push_back(3);
	data.push_back(6);

	DisplayIntVector(data);

	InsertSort(data);
	DisplayIntVector(data);

	return 0;
}

C语言中嵌套结构体的初始化问题

1. C语言中的结构体可以在声明时在等号后面使用花括号”{}”进行初始化操作,如下所示:

struct _NUM
{
	int a;
	int b;
};

_NUM test = {2, 3}; // 使用花括号对结构体进行初始化

2. 嵌套结构体也可以通过类似的方式进行初始化

// initialization of nested struct in c

struct _TEST
{
	struct _NUM
	{
		int a;
		int b;
	} num;

	enum TYPE
	{
		INT,
		FLOAT,
		DOUBLE
	} type;
};

struct _TEST2
{
	_TEST struct1[2];
};

struct _TEST3
{
	_TEST struct1;
	_TEST struct2;
};

int _tmain(int argc, _TCHAR* argv[])
{
	// 使用花括号对结构体进行初始化
	_TEST test = {{1, 2}, _TEST::FLOAT};

	_TEST2 test2 = {1, 2, _TEST::FLOAT, 56, 65, _TEST::DOUBLE};
	//_TEST2 test2 = {{1, 2, _TEST::FLOAT}, {56, 65, _TEST::DOUBLE}};	// ERROR: 初始化参数过多

	//_TEST3 test3 = {1, 2, _TEST::FLOAT, 56, 65, _TEST::DOUBLE};		// 可行
	//_TEST3 test3 = {{1, 2, _TEST::FLOAT}, {56, 65, _TEST::DOUBLE}};	// 可行
	_TEST3 test3 = {{{1, 2}, _TEST::FLOAT}, {{56, 65}, _TEST::DOUBLE}};	// 与上两句句注释掉的语句效果相同

	return 0;
}

Install Java and Eclipse on Ubuntu

1. JAVA

安装:

sudo apt-get install sun-java6-bin sun-java6-jre sun-java6-jdk

配置:

sudo update-alternatives –config java

使用java -version命令确认配置成功。

sudo vim /etc/jvm

如果没有该文件自己创建,在该文件顶部添加:

/usr/lib/jvm/java-6-sun

2.Eclipse

#include 

void main()
{
     std::cout << "Hello World!" << std::endl;
}