博文
田忌赛马(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......
第31次编程比赛第2题(2006-06-19 22:07:00)
摘要：题目：
整数变换问题。关于整数i的变换f和变换g的定义如下：f(i)=3i; g(i)=└i/2┘。试设计一个算法，对于给定的两个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15用4次变换为整数4，即4=gfgg(15)。
具体变换如下：g(15)=7 g(7)=3 f(3)=9 g(9)=4
// f函数
inline int f(int i)
{
return 3*i;
}
// g函数
inline int g(int i)
{
return (i>>1);
}
// 函数接口
// [in]n -- 待转换正整数 (0<n<=1000)
// [in]m -- 目标正整数 (0<m<=1000)
// [out]fs -- 存放转换步骤，比如 15=>4 为 "gfgg" （请一定加上字符串结束标志符'\0'）
// [return]-- 转换的最少步数（当无解时，返回INT_MAX）
int transform(int n, int m, char *fs);
// 下面是两种解法
// 1. 对“太没劲了”的程序稍作修改
// 通过f函数和g函数的组合，把n经过若干步转换成m。求最少的转换步数以及转换过程
// [in]n -- 待转换正......
求从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......
世界最快的N皇后算法(2006-05-05 22:11:00)
摘要：/* Jeff Somers
*
* Copyright (c) 2002
*
* jsomers@alumni.williams.edu
* or
* allagash98@yahoo.com
*
* April, 2002
*
* Program: nq
*
* Program to find number of solutions to the N queens problem.
* This program assumes a twos complement architecture.
*
* For example, you can arrange 4 queens on 4 x 4 chess so that
* none of the queens can attack each other:
*
* Two solutions:
* _ Q _ _ _ _ Q _
* _ _ _ Q Q _ _ _
* Q _ _ _ _ _ _ Q
* _ _ Q _ and _ Q _ _
* ......
教授的猜数问题(2006-05-05 21:21:00)
摘要：/********************************************************************
* 文件名： recursion.h
* 文件描述： 一道经典的递归题的具体代码
* 创建人： 陈泽丹, 2006年4月4日 （QQ：82314038）
* 版本号： 1.0
* 修改记录:
********************************************************************/
/*========================================================================
问题描述:
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A,B和C。有一天，
教授给他们三人出了一道题:教授在每个人脑门上贴了一张纸条并告诉他们，每个人
的纸条上都写了一个正整数,且某两个数的和等于第三个.每个学生都能看见贴在另外两个同学头上的整数，但却看不见自已的数。这时，教授先对学生A发问了：“你能猜出自已的数吗？”A回答：“不能。”教授又转身问学生B：“你能猜出你自已的数吗？”B想了想，也回答：“不能。”教授再问学生C同样的问题，C思考了片刻后，摇了摇头：“不能。”接着，教授又重新问A同样的问题，再问B和C，。。。经过若干轮的提问之后，当教授再问某人时，此人突然露出得意的笑容，把贴在自已头上的那个数准确无误的报了出来。
现在告诉你，教授在第N次提问时，轮到回答问题的那个人猜出了贴在自已头上
的数M，你能推断出另外两个学生的头上的贴的是什么数吗？
提示：总是头上贴着最大的那个数的人最先猜出自已头上的数。
解题思路:
&nbs......
求一个集合中任取若干个元素相加和等于目标值最多有多少中取法(2006-05-05 21:14:00)
摘要：// 求一个集合中任取若干个元素相加和等于目标值最多有多少中取法
// 抱歉，忘了作者是谁了
int number(int array[],int length,int target,bool isEmpty=true)
{
assert(length>0);
if(length==1)
{
return (target==array[0])+(!target&&!isEmpty);
}
else
{
return number(array+1,length-1,target-array[0],false)
+number(array+1,length-1,target,isEmpty);
}
}......