博文
统计并输出能被3整除或能被5整除或能被7整除的所有三位数(2005-11-06 20:01:00)
摘要：long Div357_m(long m, long n)
{
long count = 0;
int start, end;
static int inc[16] = {0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8};
int i;
start = (m/3+1)*3;
for(i=start; i<=n; i+=3)
{
++count;
}
start = (m/15+1)*15+1;
end = n/15*15;
for(i=start; i<=end; i+=15)
{
count += 2;
}
long temp = start - m;
if(temp <= 5)
;
else if(temp <= 10)
{
......
求若干个整数的最小公倍数(2005-10-28 13:43:00)
摘要：#include <assert.h>
template <class T>
__inline void Swap(T &a, T &b)
{
T t;
t = a;
a = b;
b = t;
}
// 辗转相除法求最大公约数
template <class T>
__inline T GCD(T m, T n)
{
assert(m >= 0 && n >= 0);
if(m == 0)
return n;
if(n == 0)
return m;
if(m < n)
{
Swap(m, n);
}
T d = m % n;
while(d > 0)
{
m = n;
n = d;
d = m % n;
}
return n;
}
#include <stdio.h>
#include <time.h>
#include <conio.h>
int main()
{
long x[100];
long n;
printf("Input the number of numbers: ");
scanf("%d", &n);
printf("Input %d numbers: ", n);
for(int i=0; i<n; ++i)
scanf("%d", x+i);
......
如何创建一个集合的幂集(2005-10-05 13:30:00)
摘要：void PowerSet(List a, List b)
{
if(a.IsEmpty())
{
Output(b);
}
else
{
Element e = RemoveHead(&a);
InsertHead(&b, e); // 元素e放入超集
PowerSet(a, b);
RemoveHead(&b); // 元素e不放入超集
PowerSet(a, b);
}
}
......
在一个函数中求最大最小值(2005-10-05 13:27:00)
摘要：// 本算法比1.5n次的比较次数的算法略快
void MaxMin(int values[], int n, int &max, int &min)
{
int i;
max = values[0];
min = values[0];
for(i=1; i<n; ++i)
{
if(values[i] > max)
{
max = values[i];
}
else if(values[i] < min)
{
min = values[i];
}
}
}......
在一个函数中求最大最小值，要求比较次数为1.5n次(2005-10-05 13:25:00)
摘要：void MaxMin(int *values, int n, int &max, int &min)
{
int nHalf = n>>1;
int i;
// 通过n/2次交换，使得前半部分总体上小于后半部分，
// 即最小值肯定在前半部分，最大值肯定在后半部分
for(i=0; i<nHalf; ++i)
{
if(values[i] > values[i+nHalf])
Swap(values[i], values[i+nHalf]);
}
// 如果n为奇数，则最后剩下一个没有比较，
// 这时让它与第一个比较，如果比第一个更小，则交换，否则不动，作为最大的部分
if( (n&1) != 0)
{
if(values[0] < values[n-1])
Swap(values[0], values[n-1]);
}
// 在前半部分找最小值
min = values[0];
for(i=1; i<nHalf; ++i)
{
if(values[i] < min)
min = values[i];
}
// 在前半部分找最大值
max = values[nHalf];
for(i=nHalf+1; i<n; ++i)
{
if(values[i] > max)
max = values[i];
}
}
......
顺序栈的模板类定义(2005-09-27 15:19:00)
摘要：/////////////////////////////////////////////////////////////////////////
// Definition of class CStack //
// CStack.h //
////////////////////////////////////////////////////////////////////////////
const int INITSIZE = 100;
const int INCREMENT= 10;
template <class T>
class CStack
{
public:
CStack()
{
entry = new T[INITSIZE];
assert(entry);
nSize = INITSIZE;
nTop = -1;
}
CStack(int nInitSize)
{
entry = new T[nInitSize];
assert(entry);
nSize = nInitSize;
nTop = -1;
}
~CStack()
{
if(entry != NULL)
{
delete []entry;
}
nSi......
八皇后问题的非递归写法(2005-09-26 22:06:00)
摘要：int x[SIZE]; // 某一行上皇后的放置位置
int up_free[2*SIZE-1]; // 斜列是否空闲
int down_free[2*SIZE-1];// 斜行是否空闲
int col_free[SIZE]; // 列是否空闲
// 求解（国际象棋）皇后问题
// i － 当前的行号
// n － 总的皇后数
void Queen(int n)
{
int i, j;
Stack st;
Element elem;
InitStack(&st);
// 初始位置入栈
elem.x = 0;
elem.y = -1;
Push(&st, elem);
while(!IsStackEmpty(st))
{
Pop(&st, &elem); // 弹出上一行的皇后位置
i = elem.x;
j = elem.y;
/* 恢复原状 */
if(j != -1)
{
x[i] = 0;
col_free[j] = TRUE;
up_free[i+j] = TRUE; /* 向上的斜列 */
down_free[i-j+n-1] = TRUE; /* 向下的斜列 */
}
找出1到1000内 能被7或11整除 但不能被7和11同时整除的数(2005-09-20 11:42:00)
摘要：#include <stdio.h>
#include <assert.h>
void Find(int *a, int *n)
{
assert(a != NULL && n != NULL);
int i;
int nCount=0;
for(i=7; i<1000; i+=7)
{
if(i%11 != 0)
a[nCount++] = i;
}
for(i=11; i<1000; i+=11)
{
if(i%7 != 0)
a[nCount++] = i;
}
*n = nCount;
}
// 下面是根据网友留言重新更改的函数，循环次数减少10％左右，但由于没有使用除法运算，所以整体速度提升了好几倍
void Find1(int *a, int *n)
{
assert(a != NULL && n != NULL);
int i, j;
int nCount=0;
int temp;
for(i=0; i<=1000/77; ++i)
{
temp = 77 * i;
for(j=1; j<7; ++j)
{
a[nCount++] = temp+7*j;
a[nCount++] = temp+11*j;
}
for(j=7; j<11; ++j)
a[n......
找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(......