博文
以空间换时间算法集锦(1)(2007-04-20 14:36:00)
摘要： 以前看过一篇文章“优化C代码常用的几招”，作者提到的第一招就是“以空间换时间”，还举了一个例子，由于比较经典，引用一下：
计算机程序中最大的矛盾是空间和时间的矛盾，那么，从这个角度出发逆向思维来考虑程序的效率问题，我们就有了解决问题的第1招--以空间换时间。比如说字符串的赋值：
方法A：通常的办法
#define LEN 32
char string1 [LEN];
memset (string1,0,LEN);
strcpy (string1,"This is a example!!");
方法B：
const char string2[LEN] ="This is a example!";
char * cp;
cp = string2;
使用的时候可以直接用指针来操作。
从上面的例子可以看出，A和B的效率是不能比的。在同样的存储空间下，B直接使用指针就可以操作了，而A需要调用两个字符函数才能完成。B的缺点在于灵活性没有A好。在需要频繁更改一个字符串内容的时候，A具有更好的灵活性；如果采用方法B，则需要预存许多字符串，虽然占用了大量的内存，但是获得了程序执行的高效率。
笔者在编程练习过程中也遇到了不少可以用空间换时间的算法，把它们收集起来，以便初学者学习查阅。
1．桶式排序算法
最经典的应用是“桶式排序算法”。数组的排序算法很多，其中快速排序是在实践中最快的已知排序算法，它的平均运行时间是O（NlogN），堆排序算法在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，但是它需要一个记录大小供交换用的辅助存储空间-----其实这也是用空间换时间的表现。但是，当数组的元素是一些较小的整型数据（小于1000000）时，用“桶式排序算法”可以使时间复杂度降到O（N），可以很快地对年龄，成绩等整型数据进行排序。此外还可以使用桶式排序的方法求素数表。
“桶式排序算法”的代码也很简单，只要建立一个长度为max的字符数组就可以了，代码如下：
......
好玩的猜数游戏(新)(2007-04-15 19:31:00)
摘要：两年前写了这个小游戏,昨天又看了一下代码,真的很烂----那时侯倒是挺觉得挺不错的,因为刚学,把书上的一个改编了一下.索性重写了一个,虽然算不上很好,但是从程序的结构来看比以前的要好,现在记录起来,做个比较.
/*猜数游戏*/
/*程序产生一个随机数，游戏者输入数据进行猜测。管理员可输入密码，
其中普通管理员只能获得答案，超级管理员获得答案并能修改普通管理员密码*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define MAX 85
#define BACKSPACE 8
const char ADMCODES[] = "nihao";//超级管理员个人身份密码
const int SUPERADM = -110; //超级管理员密码
const int WRONG = 0;
const int RIGHT = 1;
const int QUIT = -1;
const int EASY = 1;
const int COMMON = 2;
const int HARD = 3;
int commonAdm = 0; //普通管理员密码
int CreateKey(int *range);//显示游戏规则并创建一个随机数
int Quit();/*放弃后可再来一次*/
int Guess(int range);//玩家猜测一个数
int Judge(int key, int answer);//判断答案是否正确
void Congratulation(int n);//恭喜答对
void SuperAdministrators(int key);//处理超级管理员
int AdmMenu();//超级管理员管理菜单
int Check();//核实超级......
人民币大小写转换的程序(2007-04-15 14:00:00)
摘要：原来写过一个,但是有BUG,现在贴一个新的
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int main(void)
{
double money;
char pZH[40];
puts("输入一个数:");
scanf("%lf", &money);
double ZH = floor(money);
gcvt(ZH, 35, pZH);
char *num[10] = {"零", "壹", "贰", "叁", "肆", "伍", "陆", "柒", "捌", "玖"};
char *RMB[] ={"圆","拾","佰","仟","萬","拾","佰","仟","億", "十", "百", "千", "万", "億"};
int n = 0;
while (pZH[n] != '.')
n++;
n--;
//输出整数部分
puts("你输入了:");
int flag = 0;
int i;
for (i=0; pZH[i]!='.'; i++, n--)
{
......
高精度计算(2007-04-11 14:56:00)
摘要： 前几天写的高精度的基本运算,包括整数和浮点数加减乘除,乘方和整数的阶乘.乘法和除法,以及乘方和阶乘都是以加法为基础,调用了加法的函数.写得很简陋,但是功能还可以,希望各位网友试用,如找到BUG请留言,谢谢!/*用数组存储数字，可以超越数据类型的限制，实现超长整型，高精度基本运算 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 200
int Compare(const char *a, const char *b);
void IntAddition(char *augend, char *addend, char *sum);
void IntSubtration(char *minuend, char *subtrahend, char *difference);
void IntMultiplication(char *multiplicand, char *multiplier, char *product);
void IntDivision(char *dividend, char *divisor, char *quotient, char *remainder);
int Radix(char *toStr, char *fromStr);
void FloatAddition(char *augend, char *addend, char *sum);
void FloatSubtration(char *minuend, char *subtrahend, char *difference);
void FloatMultiplication(char *multiplicand, char *multiplier, char *product);
void FloatDivision(char *dividend, char *divisor, char *quotient, int precision);
void Insert(char s[], int l......
看灌水（倒酒）问题有感(2007-04-10 10:37:00)
摘要：昨日在“三思小百科” http://www.oursci.org/ency/math/002.htm看到一篇好文章。该文较详细的介绍了灌水（倒酒）问题的一般解法。根据文章提示的算法，我写了一个程序。
问题和算法简介：
倒水问题的经典形式是这样的：
“假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。”
当然题外是有一些合理的限制的，比如从池塘里灌水的时候，不管壶里是不是已经有水了，壶一定要灌满，不能和另一个壶里的水位比照一下“毛估估”（我们可以假设壶是不透明的，而且形状也不同）；同样的，如果要把水从壶里倒进池塘里，一定要都倒光；如果要把水从一个壶里倒进另一个壶里，也要都倒光，除非在倒的过程中另一个壶已经满了；倒水的时候水没有损失（蒸发溢出什么的）等等等等。
算法介绍：“灌水定理”：
“如果有n个壶容积分别为A1，A2，……，An（Ai均为大于0的整数）设w为另一大于0的整数。则用此n个壶可倒出w升水的充要条件为：
1) w小于等于A1+A2+......+An；
2) w可被(A1,A2,......,An)（这n个数的最大公约数）整除。”
这两个条件都显然是必要条件，如果1)不被满足的话，你连放这么多水的地方都没有。2)的道理和上面两个壶的情况完全一样，因为在任何步骤中，任何壶中永远只有(A1,A2,......,An)的倍数的水。
如果A1，A2，……，An是n个整数，(A1,A2,......,An)=s，那么存在整数U1，U2，……，Un，使得
U1A1 + U2A2 + ...... + UnAn = s. (*)
在代数学上称此结果为“整数环是主理想环”。
回头看“灌水定理”。w是(A1,A2,......,An)的倍数，根据上节的公式(*)，两边乘以这个倍数，我们就有整数V1，V2，……，Vn使得 V1A1 + V2A2 + ...... + VnAn = w.注意......
平分七筐鱼(2007-03-08 15:57:00)
摘要：甲、乙、丙三位鱼夫出海打鱼，他们随船带了21只箩筐。当晚返航时，他们发现有七筐装满了鱼，还有七筐装了半筐鱼，另外七筐则是空的，由于他们没有秤，只好通过目测认为七个满筐鱼的重量是相等的，7个半筐鱼的重量是相等的。在不将鱼倒出来的前提下，怎样将鱼和筐平分为三份？
*问题分析与算法设计
根据题意可以知道：每个人应分得七个箩筐，其中有3.5筐鱼。采用一个3*3的数组a来表示三个人分到的东西。其中每个人对应数组a的一行，数组的第0列放分到的鱼的整筐数，数组的第1列放分到的半筐数，数组的第2列放分到的空筐数。由题目可以推出：
。数组的每行或每列的元素之和都为7；
。对数组的行来说，满筐数加半筐数=3.5，但为了便于进行关系运算，将其乘以2变成整数7；
。每个人所得的满筐数不能超过3筐；
。每个人都必须至少有1 个半筐，且半筐数一定为奇数
对于找到的某种分鱼方案，三个人谁拿哪一份都是相同的，为了避免出现重复的分配方案，可以规定：甲、乙、丙分到的满筐数依次减少，相应的，分到的半筐数依次增多
* 运行结果
It exists possible distribution plans:
No.1 Full basket Semi--basket Empty
fisher A: 3 1 3
fisher B: 2 3 2
fisher C: 2 3 2
No.2 Full basket Semi--basket Empty
fisher A: 3 1 3
fisher B: 3 1 3
fisher C: 1 5 1
*思考题
晏会上数学家出了一道难题：假定桌子上有三瓶啤酒，癣瓶子中的酒分给几个人喝，
但喝各瓶酒的人数是不一样的。不过其中有一个人喝了每一瓶中的酒，且加起来刚好是一瓶，
请问喝这三瓶酒的各有多少人？
(答案：喝三瓶酒的人数分别是2人、3人和6人)
*/
#include<stdio.h>
int main()
{
int a[3][3] = {0};//用来存储三个人分得的各种筐的数量，每行表示一个人，每列表示一种筐
int count = 0; //累计分配方案的数量
......
精益求精---让你的程序效率更高一些(2007-01-24 16:16:00)
摘要：精益求精---让你的程序效率更高一些
问题背景：
英国大数学家哈代(G.H.Hardy,1877-1947)曾经发现过一种有趣的现象:
153=1^3 + 5^3 + 3^3
371=3^3 + 7^3 + 1^3
370=3^3 + 7^3 + 0^3
407=4^3 + 0^3 + 7^3
他们都是三位数且等于各位数字的三次幂之和,这种巧合不能不令人感到惊讶.更为称奇的是,一位读者看过哈代的有趣发现后,竟然构造出其值等于各位数字四(五,六)次幂之和的四(五,六)位数:
1634=1^4 + 6^4 + 3^4 + 4^4
54748=5^5 + 4^5 + 7^5 + 4^5 + 8^5
548834=5^6 + 4^6 + 8^6 + 8^6 + 3^6 + 4^6
注:3位3次幂回归数又称位“水仙花数”
像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.本文只讨论这种回归数,故简称为回归数,人们自然要问:对于什么样的自然数 n 有回归数?这样的 n 是有限个还是无穷多个?对于已经给定的 n ,如果有回归数,那么有多少个回归数? 1986年美国的一位数学教师安东尼.迪拉那(Anthony Diluna)巧妙地证明了使 n 位数成为回归数的 n 只有有限个.
设 An 是这样的回归数,即:
An=a1a2a3...an=a1^n+a2^n+...+an^n (其中 0<=a1,a2,...an<=9)
从而 10^n-1<=An<=n9^n 即 n 必须满足 n9^n>10^n-1 也就是 (10/9)^n<10n (1)
随着自然数 n 的不断增大,(10/9)^n 值的增加越来越快,很快就会使得(1) 式不成立,因此,满足(1)的 n 不能无限增大,即 n 只能取有限多个.进一步的计算表明:
(10/9)^60=556.4798...<10*60=600 (10/9)^61=618.3109...>10*61=610
对于 n>=61,便有 (10/9)^n>10n
由此可知,使(1)式成立的自然数......
数独计算器(2006-12-06 23:02:00)
摘要：前一段时间写的数独计算器,由于代码太长,这里只贴出算法思路和用到的功能函数,以及主函数.有感兴趣的可以向我索要完整的源代码.
/*
Name: 数独
Copyright: 自由软件
Author: goal00001111
Date: 02-12-06 17:00
Description: 版本号3.0 对2.0版本进行了优化，使输出更合理，并能输出多个解
算法思想：1。利用不重复原理（即每个数字在每行，列，小九宫中只能出现一次），根据已确定位置，
排除与其同行，同列和同小九宫位置不能取的值。
2。根据完备性原理（即每个数字在每行，列，小九宫中必须出现一次），
若某个数字只能在某行，列，小九宫中的一个位置出现，则该位置的确定值就为该数字。
3。根据双隐数对方法，即同一行，列，小九宫中，若有两个位置都有且仅有两个相同的可能值，
则同一行，列，小九宫中的其他位置不能取该两个值。或在同一行，列，小九宫中，若某两个数字
存且仅存在于两个位置中，则这两个位置只可能取这两个值。
4。经过上面三个步骤以后，一般的数独题目都可以解决了。
若通过前面三种方法还不能确定全部位置，则调用杀手锏---穷举法。
因为经过前面三个步骤以后，未知位置已经不多了，而且未知位置的可能值也不多了，这时候只要
猜中某一个位置，则可能得到答案。
因此可以遍历所有未知位置，穷举某一个（注意不是每一个）位置的可能值，再由它得到其他位置的值，
如果出错或不能得到最终结果（确定全部位置），则分析下一个位置。
注意：这里不是采用回溯的方法----因为回溯所需空间太大，而是利用只要猜中某一个位置，
则可得到答案的原理，遍历所有未知位置。这样只需要一个辅助空间，花费很小。......
修剪花卉---一道竞赛题的解答(2006-12-06 22:59:00)
摘要：/*
Name: 修剪花卉
Copyright:
Author:
Date: 26-11-06 22:29
Description:
修剪花卉
内存限制：32M
问题背景：
ZZ对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。
一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。
于是当日课后，ZZ就向老师提出了这个问题：
一株奇怪的花卉，上面共连有N朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。
每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，
说明这朵花看着都让人恶心。
所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。
经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。
老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），
使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。
老师想了一会儿，给出了正解（交大的老师是很牛的~）。ZZ见问题被轻易攻破，
相当不爽，于是又拿来问你。
输入说明：
第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N朵花。
第二行有N个整数，第I个整数表示第I朵花的美丽指数。
接下来N-1行每行两个整数a,b，表示存在一条连接第a朵花和第b朵花的枝条。
输出说明：
一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。
样例输入：
7
-1 -1 -1 1 1 1 0
1 4
2 5
3 6
4 7
5 7
6 7
样例输出：
3
数据范围：
对于60%的数据， 保证N≤1,000
对于100%的数据，保证N≤16,000
*/
/*
算法：先把所有的花进行分组，把连在一起的花合并到一组，那么问题就转化为求每一组中数据之和的最大值。
合并花的算法借鉴了连通问题。
*/
#include <iostream>
using namespace ......
爱因斯坦的思考题(2006-12-06 22:40:00)
摘要：/*爱因斯坦的思考题
在网上看到了个有趣的逻辑推理题，爱因斯坦声称世界上只有2%的人能解出：
有五个具有五种不同颜色的房间排成一排；
每个房间里分别住着一个不同国籍的人；
每个人都在喝一种特定品牌的饮料，抽一特定品牌的烟，养一特定的宠物；
没有任意两个人在抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物。
问题：谁在养鱼作为宠物？
爱因斯坦给出如下线索：
英国人住在红色的房子里；
瑞典人养狗作为宠物；
丹麦人喝茶；
绿房子紧挨着白房子，在白房子的左边；
绿房子的主人喝咖啡；
抽Pall Mall牌香烟的人养鸟；
黄色房子里的人抽Dunhill牌香烟；
住在中间那个房子里的人喝牛奶；
挪威人住在第一个房子里面；
抽Blends牌香烟的人和养猫的人相邻；
养马的人和抽Dunhill牌香烟的人相邻；
抽BlueMaster牌香烟的人喝啤酒；
德国人抽Prince牌香烟；
挪威人和住在蓝房子的人相邻；
抽Blends牌香烟的人和喝矿泉水的人相邻。
国籍 颜色 宠物 饮料 香烟
挪威 黄色 猫 矿泉水 Dunhill
丹麦 蓝色 鱼 茶 Blends
英国 红色 猫 牛奶 Pall Mall
德国 绿色 鱼 咖啡 Prince
瑞典 白色 狗 啤酒 BlueMaster
*/
/*
算法思路：
以房子的位置为主序，把国籍，颜色，宠物，饮料，香烟都作为该房子的一个成员，每一个成员都有可能
处在任何位置，为所有成员穷举每一个位置，再根据已知条件进行适当剪枝，找到唯一的解
*/
#include <iostream>
#include <string>
#include <......