博文
找12个球中的异常球(2005-09-16 14:15:00)
摘要：题目：12个球，大小、颜色和形状完全一样，除一个球外其他11个球的质量也是完全一样，该球不知道比其他11个球轻还是重。现给一个无砝码的天平，要求只称三次找出这个异常球来。
解法如下：
1。分成3等份，随便取两份放在天平上，如果平衡，则异常球必在剩下的一份（4个）当中；否则在这8个中。
2.1。如果在4个中，则那8个是正常的，此时把4个分成两等份，任取1份放在天平上，再从正常球中任取两个放天平上，这时候判断显然很容易了。
2.2。如果在8个中（那另外四个就是正常的），则可以从轻的一份中任取3个球放在一边，从重的一份中拿3个球放在轻的一份中，从正常的一份中拿3个球放到重的一份中。再称一次。
2.2.1。如果平衡，则说明异常球必在拿出去的3个球中，并且异常球必定是轻的。转3.1
2.2.2。如果原来轻的一份还是轻，说明异常球就在原来轻的一份中留下来的一个和原来重的一份中留下来的一个这两个球之中。转3.2
2.2.3。如果原来轻的一份现在变重了，说明异常球必在从原来重的一份拿到轻的一份中的3个球当中，并且异常球必定是重的。转3.3
3.1。剩下3个，并且知道异常球是轻的，就很容易了。分成3等份，任取两个称一次就够了。
3.2。剩下两个，虽然还是不知轻重，但随便取一个跟正常的比较一下就可以了。
3.3。剩下3个，并且知道异常球是重的，也很容易。分成3等份，任取两个称一次就够了。
......
判断某棵二叉树是否二叉排序树(2005-09-16 13:15:00)
摘要：根据二叉排序树的定义，递归实现即可。
bool Judge(PBinTree pbt)
{
PBinTreeNode pLeft, pRight;
bool bLeft = false, bRight=false, bRootl=false, bRootr=false;
if(pbt == NULL)
return true;
// 判断根节点
pLeft = pbt->left;
pRight = pbt->right;
if(pLeft && pLeft->data <= pbt->data)
{
bRootl = true;
}
else
{
return false;
}
if(......
已知二叉树的前，中遍历结果，求后序遍历结果(2005-09-16 13:13:00)
摘要：// pre -- 先序
// in -- 中序
void Post(List *pre, List *in)
{
Element e;
POSITION pos;
List *lin, *rin;
List *lpre,*rpre;
e = GetFront(pre); // 取得先序表中的第一个元素（必定为二叉树的根节点）
pos = FindElement(in, e); // 根节点必定把中序分成左右两部分，
//左半部为左子树序列，右半部为右子树序列
lin = GetLeft(in, pos); // 以pos为界取得中序的左半部分
rin = GetRight(in, pos); // 取得右半部分
lpre = FindLeft(pre, lin); // 从先序中找到左子树部分
rpre = FindRight(pre，rin); // 从先序中找到右子树部分
Post(lpre, lin); ......
编写程序将数组的前m个元素与后n个元素交换(2005-09-16 13:09:00)
摘要：/************************************************************************
长度确定的数组大小为m＋n（m、n各自大小不确定），
编写程序将前m个元素与后n个元素交换，要求空间复杂度
降到最小，时间复杂度尽量最小。
************************************************************************/
#include
#include
template
void Swap2(T &x, T &y)
{
T temp;
temp = x;
x = y;
y = temp;
}
// 把values数组的前nCount个元素与从nPos位置开始的nCount个元素交换位置
template
void SwapN(T values[], int nPos, int nCount)
{
int i;
for(i=0; i......
不查日历怎么知道任何一天是星期几2 ( 转载）(2005-09-10 14:13:00)
摘要：（声明一下，本文不是我的原创，只是我从网上搜下来的，如果原作者认为不合适，请告诉我删除）
假如，我们再变通一下，把1月和2月当成是上一年的“13月”和“14月”，不仅仍然符合这个公式，而且因为这样一来，闰日成了上一“年”（一共有14个月）的最后一天，成了d的一部分，于是平闰年的影响也去掉了，公式就简化成：
D = [ 13 * (M+1) / 5 ] - 7 + (M-1) * 28 + d． （3≤M≤14） (4)
上面计算星期几的公式，也就可以进一步简化成：
W = (Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + [ 13 * (M+1) / 5 ] - 7 + (M-1) * 28 + d．
因为其中的-7和(M-1)*28两项都可以被7整除，所以去掉这两项，W除以7的余数不变，公式变成：
W = (Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + [ 13 * (M+1) / 5 ] + d．
(5)
当然，要注意1月和2月已经被当成了上一年的13月和14月，因此在计算1月和2月的日子的星期时，除了M要按13或14算，年份Y也要减一。比如，2004年1月1日是星期四，用这个公式来算，有：
W = (2003-1) + [(2003-1)/4] - [(2003-1)/100] + [(2003-1)/400] + [13*(13+1)/5] + 1
= 2002 + 500 - 20 + 5 + 36 + 1
= 2524；
2524 / 7 = 360……4．这和实际是一致的。
公式(5)已经是从年、月、日来算星期几的公式了，但它还不是最简练的，对于年份的处理还有改进的方法。我们先来用这个公式算出每个世纪第一年3月1日的星期，列表如下：
年份： 1(401,801,…,2001) 101(501,901,…,2101)
----......