博文
田忌赛马(2009-03-28 20:13:00)
摘要：// http://acm.hdu.edu.cn/showproblem.php?pid=1052
/*
Here is a famous story in Chinese history.
"That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others."
"Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser."
"Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian's. As a result, each time the king takes six hundred silver dollars from Tian."
"Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match."
"It was a rather simple trick. Using his regular cl......
求第n个回文数(2008-04-14 11:24:00)
摘要：// 本程序可以求出第n（n<=10^500000000）个回文数
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
template <class T>
void Swap(T &a, T &b)
{
T temp;
temp = a;
a = b;
b = temp;
}
void Palindrome(char *n, char *result)
{
long n_len;
n_len = strlen(n);
if(n_len == 1)
{
result[0] = n[0] + '0';
result[1] = '\0';
return;
}
long i, j;
for(i=0; i<n_len/2; ++i)
{
n[i] -= '0';
&nb......
一个另类的Hanoi塔程序(2007-01-08 14:18:00)
摘要：void Hanoi(int n)
{
char pole[3][101];
char pole_id[4] = {"xyz"};
int count[3]; // 每个塔上的盘子数
int i;
count[0] = n; // 初始0号塔n个盘子
count[1] = 0;
count[2] = 0;
for(i=1; i<=n; ++i)
{
pole[0][i] = n-i+1;
pole[1][i] = 0;
pole[2][i] = 0;
}
int p1 = 0; // 指向最小盘子所在的塔号
int aim1 = n&1?2:1; // 最小盘子移动的目标塔号
int p = 3 - aim1; // 剩下的塔号
int inc = n&1?-1:1; // 目标塔移动的增量
while(count[2] < n-1)
{
Move(1, pole_id[p1], pole_id[aim1]); // 最小盘子从p1塔移到aim1塔
--count[p1], ++count[aim1];
// 除aim1塔（最小盘子刚移到上面）外，剩下两个塔能怎么移动就怎么移动
if(count[p1] == 0)
{
Move(pole[p][count[......
生成n阶螺旋方阵(2006-07-17 11:09:00)
摘要：void Matrix(int n)
{
int row = 0, col = 0; // 当前位置所在的行列
int left = -1, right = n, top = -1, bottom = n; // 当前的边界
int irow = 0, icol = 1; // 当前的前进方向（初始时往右）
int arr[20][20];
for(int i=0; i<n*n; ++i)
{
arr[row][col] = i+1;
// 根据当前的前进方向获得下一个位置的行列号
row += irow;
col += icol;
if(col == right)
{
// 下一个位置是右边界时，往下。
irow = 1;
icol = 0;
// 此时，顶边界往下一格
top += 1;
// 改变下一个位置
row += 1;
col -= 1;
}
if(row == bottom)
{
// 下一个位置是底边界时，往左。
irow = 0;
icol = -1;
// 此时，右边界往左一格
right -= 1;
&nb......
求从m个数据中任取n个数据的所有组合(2006-06-15 16:03:00)
摘要：// 求从m个数据中任取n个数据的所有组合
// [in]chars -- 存放m个数据
// [in]m -- 数据个数
// [in]n -- 需要从m个数中取的数据的个数
// [out]set -- 存放所有的组合
// [inout]row -- 组合个数
// [in]col -- 当前取到第几个数据
// 思路：每次从集合中按顺序选择1个，然后进入递归取下一个；下一个数据只能从当前数据的后面的数据中任取一个
// 为了降低实际复杂度，当后面的数据个数不够时就不再取（通过for循环控制）。由于后面的组合与前面
// 的组合存在一定的同构性，因此，在获得一个组合后，直接把该组合的前面若干数据复制作为下一个组合的数据
template <class T>
void GetCombination(T *data, long m, long n, T *set[], long &row, long col)
{
long i, j;
if(n == 0)
{
++row;
// 直接把该组合的前面col-1个数据复制作为下一个组合的数据
for(j=0; j<col-1; ++j)
set[row][j] = set[row-1][j];
return;
}
for(i=0; i<=m-n; ++i)
{
set[row][col++] = data[i];
GetPermutation(data+i+1, m-1-i, n-1, set, row, col);
--col;
}
}
......
浮点数是怎样炼成的(2006-05-24 22:18:00)
摘要：12345678900（十进制）＝>
1011011111110111000001110000110100（34位精确值，整型格式）
========>浮点格式（32位）
符号位:0
+127
指数:33(100001=>00100001 =====> 10100000
原码 阶码（移码）
尾数:1.01101111111011100000111(取24位，尾数规定为23位，加隐含的1位，共24位）
=>（注意：前面的1在实际存放时为了多存放一位而隐含，即浮点数的尾数的最高位永远隐含为1）
0 10100000 01101111111011100000111（实际放了尾数后面的23位）
指数 尾数
最后结果就是01010000001101111111011100000111
现在再把它还原成整数：
（1）取尾数23位：01101111111011100000111
（2）在前面加上隐含的1，变成：101101111111011100000111
（3）取指数8位：1010000......
四则运算表达式求值(2006-05-05 21:09:00)
摘要：int Calc(int a, int b, char oprt)
{
switch(oprt)
{
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
}
}
int expr(char a[])
{
char ch, last_oprt;
int c, d;
CStack<int> oprd;
CStack<char> oprt;
while(ch=*a++)
{
if(ch == '(')
{
oprt.Push(ch);
}
else if(ch == ')')
{
while(oprt.IsEmpty() == false)
{
last_oprt = oprt.Pop();
if(last_oprt == '(') // 遇到匹配的左括号退出
break;
d = oprd.Pop();
c = oprd.Pop();
oprd.Push(Calc(c, d,......
筛选素数(2005-12-09 18:26:00)
摘要：本程序改编自intfree写的pascal程序。
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
__int64 maxn = 1000000000L;
const long maxlen = 100000;
long m = 5;
const long dots = 80;
BYTE *mask;
long primes[maxlen+2], mprimes[maxlen+2], ans[maxlen+2];
long bits[256];
long len, r;
void solve(long a, long b, long c, long &x, long &y)
{
if(a == 0)
{
x = 0;
y = c/b;
}
else
{
solve(b%a, a, c, y, x);
x -= b/a*y;
}
}
// primes数组从下标1开始存放素数，例如primes[1]为2
void init()
{
long p, k;
k = 2;
len = 0;
// 求待求范围的平凡根范围内的素数
do
{
++len;
primes[len] = k;
do
{
++k......
大数阶乘(2005-11-10 20:12:00)
摘要：// 可以计算1～20000的阶乘。在PIII 1.13G CPU上计算20000！约需2.2秒。
#define nRadix 100000
#define MAXSIZE 16000
long in[MAXSIZE]= {0};
void fact(long n)
{
long m_nPrecision = 1;
long temp;
long carry = 0;
int i;
for(i=0; i<MAXSIZE; ++i)
in[i] = 0;
in[0] = 1;
for(i=2; i<=n; ++i)
{
for(long j=0; j<m_nPrecision; j++)
{
temp = in[j]*i+carry;
carry = temp / nRadix;
in[j] = temp - carry * nRadix;
}
temp = carry;
while(temp > 0)
{
carry = temp / nRadix;
in[m_nPrecision++] = temp-carry*nRadix;
temp = carry;
}
}
}......
Divisibility(2005-11-06 20:11:00)
摘要：（题目来自http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1745）
#include <stdio.h>
#include <math.h>
long abs_sum(long nums[], long nCount);
bool Knap(long nums[], long nCount, long k)
{
if(nCount == 0)
{
if(k == 0)
{
return true;
}
else
{
return false;
}
}
else
{
bool bRet = Knap(nums, nCount-1, k - nums[nCount-1]);
if(bRet == true)
{
return true;
}
else
{
bRet = Knap(nums, nCount-1, k + nums[nCount-1]);
if(bRet)
{
nums[nCount-1] *= -1;
}
return bRet;
}
}
}
long abs_sum(long nums[], long nCount)
{......