RT

好久没写Blog，写一篇凑凑数。

来自某个很无聊的“作业”，最初是让写一个简易科学计算器，为了避免做UI的麻烦，直接选择表达式求解的方式实现。

算法原型来自Lieo，经过部分改进后，支持负数和多重括号。

因为只是expression-evaluate的一个demo，所以没有写得太详细。

不支持小数，没有异常处理，包括除数为零。

这里说下算法：

首先需要有两个堆栈或者支持FILO性质的线性表（我用的是vector，便于调试时观察内部元素是否正确），分别保存操作数和操作符。

负数通过额外的符号位实现，并规定，操作符后面跟着的“-”表示负号，符号位逻辑求反。

遍历表达式时，如果碰到操作数，直接入操作数栈。碰到操作符op，先和操作符栈顶的元素比较优先级，如果优先级大于栈顶元素，入栈（如果操作符栈为空，直接入栈），否则取出操作符栈顶元素和操作数进行计算，一直到操作符栈空或者栈顶元素优先级小于操作符op。

对于括号特殊处理：

碰到“(”，直接入栈，碰到“)”，取出操作符栈和操作数栈计算，直到操作符栈中弹出“(”。

为了简化算法，表达式尾部需要有#符号充当哨兵元素，并规定#符号的优先级最小。

提供核心代码，全部代码请翻看SRC

#define pop(x) x.back(); \
				x.pop_back();

struct NumData
{
	NumData() : signal(false), pos(0)
	{
		wmemset(sz, L'\0', NUM_LEN);
	}

	enum{NUM_LEN = 10};
	wchar_t sz[NUM_LEN];
	bool signal;
	unsigned int pos;
};

int EvaluateExpression(wchar_t* pszExpression)
{
	stackOperand oprand;
	stackOperator oprator;
	bool isNumbericMode = true;
	NumData data;

	for (wchar_t* p = pszExpression; *p != NULL; ++p)
	{
		if (*p >= L'0' && *p <= L'9')
		{
			data.sz[data.pos++] = *p;
			isNumbericMode = false;
		}
		else if (L'-' == *p && isNumbericMode)
		{
			data.signal = !data.signal;
		}
		else	// pure operators
		{
			isNumbericMode = true;

			if (L'(' == *p)
			{
				oprator.push_back(*p);
			}
			else if (L')' == *p)
			{
				int num;

				if (data.pos)
				{
					num = FormatNumtoInt(data);
				}
				else
				{
					num = pop(oprand);
				}

				do
				{
					wchar_t op = pop(oprator);

					if (L'(' == op)
					{
						oprand.push_back(num);
						break;
					}
					else
					{
						int num2 = pop(oprand);
						num = Calculate(num2, num, op);
					}

				} while (true);
			}
			else	// operators except ( and )
			{
				int num;

				if (data.pos)
				{
					num = FormatNumtoInt(data);
				}
				else
				{
					num = pop(oprand);
				}

				do
				{
					if (oprator.empty() || (GetPriority(*p) > GetPriority(oprator.back())))
					{
						oprand.push_back(num);
						oprator.push_back(*p);

						break;
					}
					else
					{
						int num2 = pop(oprand);
						wchar_t op = pop(oprator);

						num = Calculate(num2, num, op);
					}

				} while (true);
			}

			//DumpStack(oprand);
		}
	}

	return oprand.back();
}

int FormatNumtoInt(NumData& data)
{
	assert(data.pos);

	int num = _wtoi(data.sz);
	num = data.signal ? -num : num;

	wmemset(data.sz, L'\0', NumData::NUM_LEN);
	data.pos = 0;
	data.signal = false;

	return num;
}

Download EvaluateExpression SRC

回家前在图书馆碰到了刘汝佳的《算法竞赛入门经典》，于是便借回来随手翻翻

个人实在不太喜欢这类风格的书，但是觉得某些题目不错，就随手做做，权当练习

1、位数

描述：输入一个不超过10^9的正整数（由输入者负责保证），输出它的位数。例如12735的位数是5.不要使用任何数学函数，只使用四则运算。

思路1：设接受的的n位整数为N，让i从1取到9（事实上，只要不发生溢出，可以取到上限），并令 k = N / 10^i，当k == 0时，则所求位数为i。算法复杂度为O(n)

int QueryDigit(int nNum)
{
    int nDigit, nDiv;

    for (nDigit = 1, nDiv = 10; nNum / nDiv; ++nDigit)
    {
        nDiv *= 10;
    }

    return nDigit;
}

思路2：查表法。很容易想到，每个数所在的位数区间都是确定的。比如12735在10000～99999这个区间范围内。而这个区间范围内的数都是5位。查表法需要写较多的代码，但是运行起来速度会快得多，不过只有在要查询的数字比较多的情况下才能体现。易知，复杂度为O(1)

int QueryDigit(int nNum)
{
    int DigitTable[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int nDigit;

    // a long long if statement
    if (0 <= nNum && nNum < 10)
    {
        nDigit = DigitTable[0];
    }
    else if (10 <= nNum && nNum < 100)
    {
        nDigit = DigitTable[1];
    }
    else if (100 <= nNum && nNum < 1000)
    {
        nDigit = DigitTable[2];
    }
    else if (1000 <= nNum && nNum < 10000)
    {
        nDigit = DigitTable[3];
    }
    else if (10000 <= nNum && nNum < 100000)
    {
        nDigit = DigitTable[4];
    }
    else if (100000 <= nNum && nNum < 1000000)
    {
        nDigit = DigitTable[5];
    }
    else if (1000000 <= nNum && nNum < 10000000)
    {
        nDigit = DigitTable[6];
    }
    else if (10000000 <= nNum && nNum < 100000000)
    {
        nDigit = DigitTable[7];
    }
    else
    {
        nDigit = DigitTable[8];
    }

    return nDigit;
}

2、韩信点兵

描述：相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只要掠一眼排尾的人数就知道总人数。输入3个非负整数a,b,c，表示每种队形排尾人数（a<3,b<5,c<7），输出总人数的最小值。

思路1：题目实质是求x=3*k1+a = 5*k2 + b = 7*k3 + c。可以通过令x从1开始进行尝试，第一个符合的数就是所求的数。分析可知，算法的复杂度是O(n)，这里的n只与所求数有关。

但事实上，存在复杂度为O(1)的算法。因为此题可以通过公式计算得到。

思路2：这道题在数论上颇有名气，其本质是求线性同余方程组的解。解法最早由宋朝秦九韶提出，并被国外数学家冠以“中国剩余定理”

ps：这本号称入门级的算竞赛辅导书（似乎还是面向中学生）居然会出现线性同余方程组求解的问题，表示这让我很诧异。

关于“中国剩余定理”的详细说明和分析将在未来几天内（起码得等我到家）完成。

由“中国剩余定理”可以得到韩信点兵问题的通解公式

知道了公式，代码就显得极其简单
Read the rest of this entry »

散列表（Hash Table）又称哈希表，是一种仅支持少数几种字典操作的表。其支持的操作有：Insert、Delete和Find

使用散列表的原因在于，对散列表中元素进行查找的期望效率很高，通常复杂度在O(1)

一、直接寻址表

在介绍散列表前，我们先介绍一种更高效的表：直接寻址表（Direct Addressing Table，DAT）

DAT查找的高效性在于采用的直接寻址技术（Direct Addressing），可以看作散列表的前身

设存在一些取自全域U的关键字元素k，即

此时n是一个不大的数，且规定

可以建立一个直接寻址表T[0...n-1]（可利用数组实现）。若关键字k在表中，则必有T[k]=k，否则T[k]=NIL

易知，DAT的各种操作效率很高，时间复杂度可以达到O(1)，但是局限性比较大

二、散列表

对于DAT来说，如果关键字全域U很大，那么实现一个大小为|U|的DAT就不太现实，且如果用到的关键字域|K|<<|U|，就会造成巨大的空间浪费

而利用散列表（Hash Table，HT），则可以保持查找期望复杂度为O(1)的情况下，是空间复杂度降低至O(|K|)

在DAT中，关键字k被存在T[k]中，而在HT中，关键字k保存在T[h[k]]中。其中，h(k)被称为散列函数（hash function），h(k)称为散列值(hash code)

散列函数h(k)利用关键字k,计算出k在HT中的位置，进而存储k

在HT中，有时会发生不同的关键字k得到相同的散列值的情况，即

这一情况称为碰撞（collision），后文对碰撞和解决碰撞的方法进行分析

三、散列函数

事实上，散列函数的好坏直接决定了散列表的性能，因为好的散列函数可以很大程度上降低碰撞发生的概率

在理想情况下，一个好的散列函数应满足每个关键字元素k映射到表的n个位置中是等可能发生的，且关键字之间各自独立，这个称为一致散列假设

但在实际情况中，这个假设很难成立，我们只能构造某些近似满足的情况

（1）求模取余散列法

使用求模取余散列法可能首先需要利用准备函数p(k),将关键字转化为自然数k

通过对关键字k进行模m操作来计算散列值（m为散列表大小），表达式为

此处h(k)应注意对m值的选取，由众多科学家及数学家的分析推导，m应取与2的整数次幂不太接近的一个素数
Read the rest of this entry »