博文

以空间换时间算法集锦(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的字符数组就可以了,代码如下: ......

阅读全文(4466) | 评论:0

好玩的猜数游戏(新)(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();//核实超级......

阅读全文(2669) | 评论:1

人民币大小写转换的程序(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--)
    {
  ......

阅读全文(2266) | 评论:0

高精度计算(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......

阅读全文(4244) | 评论:3

看灌水(倒酒)问题有感(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.注意......

阅读全文(3103) | 评论:1

平分七筐鱼(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; //累计分配方案的数量
 ......

阅读全文(2428) | 评论:1

精益求精---让你的程序效率更高一些(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)式成立的自然数......

阅读全文(3154) | 评论:2

数独计算器(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。经过上面三个步骤以后,一般的数独题目都可以解决了。
  若通过前面三种方法还不能确定全部位置,则调用杀手锏---穷举法。
  因为经过前面三个步骤以后,未知位置已经不多了,而且未知位置的可能值也不多了,这时候只要
  猜中某一个位置,则可能得到答案。
  因此可以遍历所有未知位置,穷举某一个(注意不是每一个)位置的可能值,再由它得到其他位置的值,
  如果出错或不能得到最终结果(确定全部位置),则分析下一个位置。
  注意:这里不是采用回溯的方法----因为回溯所需空间太大,而是利用只要猜中某一个位置,
  则可得到答案的原理,遍历所有未知位置。这样只需要一个辅助空间,花费很小。......

阅读全文(10350) | 评论:18

修剪花卉---一道竞赛题的解答(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 ......

阅读全文(3181) | 评论:0

爱因斯坦的思考题(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 <......

阅读全文(2346) | 评论:0