博文
算法设计之枚举法(1)(2007-09-20 08:37:00)
摘要：算法设计之枚举法
枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。
采用枚举算法解题的基本思路：
（1）确定枚举对象、枚举范围和判定条件；
（2）一一枚举可能的解，验证是否是问题的解
下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。
例1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡一只3元,母鸡一只5元,小鸡3只1元,试求用100元买100只鸡,各为多少才合适?
算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为cock, hen, chick）,以三种鸡的总数（cock + hen + chick）和买鸡用去的钱的总数(COCKPRICE*cock + HENPRICE*hen + chick/CHICKS)为判定条件，枚举各种鸡的个数。
注：我这里用了一个自定义函数Function()来解三种鸡的百钱买百鸡问题。函数提供了两个参数int money, int chooks，分别表示总钱数和总鸡数，除了把她们都赋值100外，还可以赋任意正整数值，解决x钱买y鸡问题。
#include<stdio.h>
const int COCKPRICE = 3; //一只公鸡的价格
const int HENPRICE = 5; //一只母鸡的价格
const int CHICKS = 3; //一元钱能买的小鸡数量
void Function(int money, int chooks);//计算并输出三种鸡的数量各是多少
int main()
{
int money = 100;//钱的总数
int chooks = 100;//鸡的总数
Function(money, chooks);//计算并输出三种鸡的数量各是多少
getchar();
&......
我学c++Builder系列(3)(2007-06-25 14:50:00)
摘要：三 C＋＋ Builder中构件的属性
1．Align属性。
Align属性的取值
数值
说明
alBottom
构件与父窗口的底部对齐，例如状态条就与主窗口底部对齐alClient构件展开成填充父窗口客户区。如果客户区中有其它构件，则这构件填充客户区余下部分。例如Memo构件、Image构件和RichEdit构件
alLeft
构件与父窗口的左边对齐。例如垂直工具条就是个左对齐构件
alNone
构件按指定方法放置，与父窗口无特别关系，是大多数构件的缺省设置
alRight
构件与父窗口的右边对齐
alTop
构件与父窗口的顶边对齐，例如工具条就采用这种对齐方法
2．Name属性。
将构件放在窗体上时，C＋＋ Builder在后台工作。C＋＋ Builder所做的工作之一是生成构件的指针和赋予Name属性为变量名。例如，假设将Edit构件放在窗体上，并将其Name属性变为MyEdit。则C＋＋Builder会在窗体头文件中放上下列语句：TEdit* MyEdit;
C＋＋ Builder在生成事件处理器名时也使用Name属性。假设要响应Edit构件的OnChange事件。通常，双击OnChange事件旁边的Value列，C＋＋ Builder即会产生这个事件的事件处理器。C＋＋ Builder根据构件的Name属性和所处理的事件生成缺省函数名。这里，C＋＋ Builder生成函数MyEditChange()。
Name属性可以随时改变，但只能通过对象观察器改变。设计时改变构件Name属性时，C＋＋ Builder遍历前面生成的所有代码，改变指针名和所有事件处理函数名。换句话说，C＋＋ Builder会负责修改所写的代码，但你自己所写的代码要你自己修改和维护。一般来说，开始将构件放在窗体上时应改变Name属性，此后则保持不动。
警告：不要在运行时改变Name属性名，别在代码编辑器中手工改变构件名（C＋＋ Builder指定的构件指针名）和事件处理器名，否则C＋＋ Builder无法跟踪这些构件，结果肯定不理想，甚至无法装入窗体。Name属性只能通过对象观察器改变。
建议：尽快将构件Name属性从缺省名变为有意义的名称；运......
我学c++Builder系列(2)(2007-06-25 09:00:00)
摘要：二 C＋＋ Builder中的菜单
菜单是大多数Windows程序的重要部分，有些Windows程序没有菜单，但大多数Windows程序都有。C＋＋ Builder的菜单设计器使菜单设计非常方便。菜单设计器特性如下：
可以生成主菜单和弹出菜单。
可以立即访问代码编辑器，处理菜单项目的OnClick事件。
可以从模板或资源文件中插入菜单。
可以将自定义菜单存为模板。
菜单设计器的所有命令都可以通过菜单设计器弹出菜单或对象检查器访问。
在窗体中加进主菜单：
1． 先要在窗体中加进MainMenu构件，并将其Name属性变为MainMenu，注意MainMenu构件有几个属性，但没有事件，菜单的各个工作都在各个菜单项目中完成。
2． 双击MainMenu图标打开菜单设计器。
3． 从模板插入菜单。在菜单设计器中单击右键选择弹出菜单中的Insert From TempLate（从模版插入），Insert Template对话框显示了一列可以选择的模板，你可以选择自己需要的模版。这里我们要加进Edit菜单，所以选择Edit Menu并单击OK，菜单设计器中立即加进了整个Edit菜单。
4．加进Help菜单。单击Edit菜单右边的空白弹出菜单占位符，再次选择Insert From TempLate并插入Help菜单（但别选择ExpandedHelp Menu）。注意新菜单项目加入时，主窗体更新显示。
删除菜单项目：
生成Windows应用程序的过程是活的，很难一次性到位，而经常会出现需要更新菜单的情形。例如，前面插入的Edit菜单太长，其中有几个用不上的项目，所以要将其删除：
1．单击Edit菜单。
2．单击Repeat<command>项目。
3．按键盘上的Delete或选择菜单设计器弹出菜单中的Delete将其删除，这个项目即消失。
4．同法删除Pas......
我学c++Builder系列(1)(2007-06-18 07:45:00)
摘要：一 C＋＋ Builder中的对话框
在C＋＋ Builder中，对话框只是个窗体。生成对话框与生成主窗口窗体和其它窗体是一样的。为了防止缩放对话框，可以将BorderStyle属性变为bsDialog或bsSingle。
生成对话框：
1. 生成新窗体（单击工具条上的New Form按钮）。
2. 设置Name和Caption属性。例如将Name属性变为AboutBox，将Caption属性变为About Box。
3. 找到Caption属性上方的BorderStyle属性，将其变为bsDialog。
4. 然后给About框加进三个文本标题。编辑标题，即在Caption属性中输入文本。可以使用C＋＋ Builder为文本标题的Name属性生成的缺省名。Name属性用不上，所以不需要具有说明意义的名称。
下面进行About框的修饰：
1. 找到构件板Additional标签中的Bevel按钮并单击它。
2. 移到窗体上，单击窗体并在三个文本标题周围拖动框。拖动停止时，出现Bevel构件，构件可以调整尺寸和位置。
3. 找到Shape属性并将其变为bsFrame，这样就在静态文本周围有了三维帧。
下面要在About框中加进图标：
1. 单击构件板上的Additional标签并选择Image构件，将构件放在窗体上文本左边。
2. 找到Image构件的AutoSize属性并将其变成true。
3. 找到Picture属性......
第53次编程比赛题目研究 (2007-05-25 17:39:00)
摘要：题目:
产生指定长度的无连续重复部分的字符串(所有元素都由'1','2','3'这三个字母构成)
输入: 指定的长度n
输出: 无
函数接口:
void unoverlap(int n, char *p)//p是已经分配好了的,不用担心溢出.
例如:
输入5
输出 p中的内容应为12312(或满足条件的其它串)
(不能输出12323,因为23和23是连在一起的并且相同)
当然只要输出一个满足条件字符串的就可以了。
最容易想到的是回溯法，每放一个数字判断是否会产生重复，按'1','2','3'的顺序放置，
如果都不满足，则回退一个。
代码1如下：（取材于poorb的代码）
bool Cover(char *base, int top)//判断是否有连续重复序列
{
int p;
int k = (top + 1) / 2;
for (int step=1; step<=top; step++)
{
for (p=0; p<step; ++p)
{
if (base[top-p] != base[top-step-p])
break;
}
if (p == step)//产生重复
&nbs......
以空间换时间算法集锦(4)(2007-04-20 14:42:00)
摘要：5．士兵站队
题目：训练场上n(1≤n≤50000)个高矮都不相同的士兵从左到右排成一行，依次编号为1，2，…，n。
第i个士兵的身高H(i)，由于采用特殊单位，H(i)满足1≤H(i)≤2000000000。
设第i个士兵右侧最近的比他个高的士兵编号为j，则第i个士兵可看到在他的右侧比他矮的士兵的个数S(i)=j-i-1。（不考虑客观因素，比如视力范围等-,-）
求S(1)+S(2)+…+S(n)。
输入：
标准输入。
第一行为整数n，表示士兵的个数。
第二行n个整数，用一个空格隔开。分别表示编号为1,2。。。n的士兵的身高
输出：
S(1)+S(2)+…+S(n)的结果
例：
输入
6
10 3 7 4 12 2
输出
5
主函数：
#include <iostream>
#include <time.h>
using namespace std;
int Sum(int h[], int n);
int main(void)
{
time_t startTime;
time_t endTime;
const int n = 50000;
int h[n] = {0};
int temp, p;
//获取互不相同的一组数列
for (int i=0; i<n; i++)
h[i] = i + 1;
for (int i=n-1; i>0; i--)//洗牌，使得数的大小随机排列
{
p = rand()%i;
&......
以空间换时间算法集锦(3)(2007-04-20 14:41:00)
摘要：4．满足条件的m的个数
给出一个数字n和k，请找出有多少个不同的整数m满足：
1） m<2^n
2） m>=0
3） |f(m,n)|<=k
其中f(x,n)的定义如下：
f(0,n)=n;
f(x,n)=f([x/2],n),x为偶数
f(x,n)=f([x/2],n)-2,x为奇数
Input
每组一行，分别给定n,k(1<=n<=62,2<=k<=5)
Output
每组一行，给出满足条件的m的个数
Sample Input
1 2
4 3
Sample Output
2
14
主函数：
#include <iostream>
#include <time.h>
using namespace std;
int Fun(int n, int k);
int main()
{
time_t startTime;
time_t endTime;
time(&startTime);
for (int i=1; i<=20; i++)
for (int j=2; j<=5; j++)
cout << i << "," << j << ": " << Fun(i, j) << "\t";
cout << endl;
time(&endTime);
c......
以空间换时间算法集锦(2)(2007-04-20 14:39:00)
摘要：3．丑陋数
题目来自http://acm.pku.edu.cn/JudgeOnline/problem?id=1338，我做了一点小改动。
丑陋数是指质因数只包含2，3，5的自然数，例如前十个丑陋数依次为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12。
给定一个自然数n (n <= 1500)，请你求出对应的第n个丑陋数。
函数接口：unsigned long UglyNumber(int n);
输入输出示例：
n = 2， 返回 2； n = 5， 返回 5；n = 7， 返回 8； n = 11， 返回 15；
解决此问题的一种思路就是先建立一个丑陋数表，把前1500个丑陋数全部求出来存储到数组lib[]中，这样只要返回lib[n-1]就好了。
本文分析一些建立丑陋数表的方法。
方法一：很容易想到判断一个数是否为丑陋数的方法，那就是判断它的因子是否只包含2，3，5。最简单的方法就是依次判断各个自然数，直到找齐1500个丑陋数为止。
代码如下：
#define MAX 500
unsigned long UglyNumber(int n)
{
unsigned long lib[MAX] = {1,};//用来存储丑陋数表
unsigned long i, num;
int k = 1;
for (i=2; ......
以空间换时间算法集锦(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();//核实超级......