博文
连通问题(2006-11-26 15:31:00)
摘要：这是我在阅读<<算法1-4（C++实现）——基础，数据结构，排序和搜索（第三版）>>
([美]Robert Sedgewick 著， 张铭泽 赵剑云 梁勇等 译 中国电力出版社)
时整理的读书笔记,现在贴出来,希望能给初学者一些启发.
/*
Name: 连通问题
Copyright:
Author:
Date: 25-11-06 21:59
Description: 连通问题
假设有一个整数对的序列，每个整数代表某个类型的一个对象，p-q对表示"p连接到q"，
即p和q之间连通。假设连通关系具有传递性--如果p与q连通，q与r连通，那么p与r连通。
我们的目标是写一个过滤出那些不在集合中的对的程序：输入p-q对时，
如果已输入的对的集合中没有隐含这样的对（通过连通关系的传递性），那么程序将输出该对。
如果前面输入的对隐含了p与q的连通，那么程序将忽略p-q，准备输入下一对。
输入输出示例如下：
输入 输出 隐含
3-4 3-4
4-9 4-9
8-0 8-0
2-3 2-3
5-6 ......
用空间换时间---对处理大量数据问题的一点思考(2006-11-11 16:36:00)
摘要：题目来自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 (......
手机拼音输入法头文件和主函数(2006-10-21 20:04:00)
摘要：//*
Name: 手机拼音输入系统头文件
Copyright:
Author:
Date: 20-10-06 07:23
Description:手机拼音输入系统头文件
*/
#define SIZE 500
struct Node{
char data[10];
struct Node *next;
};
typedef struct Node SPELL;
typedef SPELL *LNode;
char *storage[SIZE];
//////////////////////////////////////////////////////////////////////////////////
/*
函数声明：void ReadFile(const char fileName[]);
函数功能：从指定的文件中把所有汉语拼音及对应汉字读入一个指针数组*storage[]（全局变量），
数组的每个元素指向文件中的一行。
输入变量： const char fileName[]，指定的文件名，其中存储了汉字库
输出变量：*storage[]，全局变量，每个元素指向一个包含某拼音组合及其对应汉字的字符串
返回值： 无
*/
void ReadFile(const char fileName[]);
///////////////////////////////////////////////////////////////////////////////
/*
函数声明：void ReadValue(char value[]);
函数功能：读取用户输入的字符串buf，并对其进行适当的转换。
转换规则：先找到结束键'1'，删除结束键之后的字符。
若无结束键'1'，value[i] = '\0';；并结束程序;
然后在buf中逆序查找#号，直......
手机的汉语拼音输入法(2006-10-21 19:58:00)
摘要：系统功能：
手机的汉语拼音输入法很'聪明'，只要用数字键组合，就能够自动找到能组成拼音的字母组合.从2开始分别代表2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz"
键盘布局如图示
+-------+-------+-------+
|1 OK |2 abc |3 def |
+-------+-------+-------+
|4 ghi |5 jkl |6 mno |
+-------+-------+-------+
|7 pqrs |8 tuv |9 wxyz |
+-------+-------+-------+
|#<prep>|0<back>|*<next>|
+-------+-------+-------+
拼音规则：输入时手机有3个状态：
1. 拼音状态： 只接受2至9，和结束键1。按下1则进入状态2，如果候选拼音组合唯一则自动进入状态3（此时拼音不必拼完）；如果无匹配的拼音组合，则一直忽略直到遇到#取消当前拼音。若用户输入非法字符，则自动屏蔽非法字符，只读取合法字符。若只输入结束键1，表示用户选择离开。
2. 选择拼音状态 ： 根据用户输入的数字组合，在屏幕上列出满足条件的拼音组合，每页最多有10个组合，按字母顺序标号由0到9。接受0-9任何一个键则选择对应组合进入状态3。忽略选择不存在组合的位置的数字。接受*则下翻一页。如果已经到达最后一页则忽略*号。接受#则取消当前拼音，并回到状态1。
3. 汉字选择状态： 进入本......
求围圈问题的详细算法和程序集锦(2006-06-24 21:57:00)
摘要：这是以前发在"c语言之家"的一篇文章,今天把它收集到一起来.
17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号。
这个题目的解法很多，我原来就总结了5种，但都不如用数组队列来的简明。
算法如下：
/*求围圈问题的详细算法和程序*/
/*17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号 */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int a[17]={0};
int front=0, rear=16; //因为数据较小，可令队头元素也占一个实用（有数据域）的空间
int i, count=0; //计数器
for (i = 0;i < 17;i++)
a[i] = i + 1; /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
while ((front%17) != (rear%17))//当队列元素还有一个，注意这里不需要队列为空，而是留一个元素
{
if(++count < 3)//若元素非3的倍数，......
求素数表的3种方法(2006-06-08 09:36:00)
摘要：/*
题目描述：求出N内的所有素数，把他们存储到数组sushu[MAX] 中，并返回素数的个数。
算法描述：在下面的程序中我分别使用了常规方法和新方法求素数表，结果新方法所用时间远小于常规方法。
新方法的思路其实不新，只是利用了一个小技巧：一个正整数如果不能被所有不大于它的平方根的素数整除，则它一定是素数。我在判断正整数i是否为素数时，不是让它去整除每一个不大于它的平方根的正整数，而是让它去整除已经得到的素数表中的素数（此时素数表中的素数比i要小），这样就大大地减少了运算量。
注意：另外还有一种类似桶式排序的方法，是把所要分析的正整数作为布尔数组p[N]的下标，
先给布尔数组p[N]赋初值为true。从i=2开始分析，若p[i]==true，则i的所有倍数j=n*i均为非素数，将以j为下标的元素p[j]==false；直到i==N/2结束分析。
遍历布尔数组p[N]，若若p[i]==true，则表示i为素数，将其存入素数表。
这种方法速度也很快，但它需要设置一个长度为N的布尔数组p[N]，当N很大时，会占用过多内存空间，导致程序不能执行。
*/
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;
long Sushu_1(long a[], long n);
long Sushu_2(long a[], long n);
long Sushu_3(long a[], long n);
int main()
{
const long MAX = 150000; //预计素数总的个数
const long......
汉诺塔非递归算法(2006-06-07 18:06:00)
摘要：/*
问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，
可以从上到下用1, 2, ..., n编号。要求借助柱子B，把柱子A上的所有的盘子移动到柱子C上。
移动条件为：1、一次只能移一个盘子；
2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。
*/
/*
递归的算法相信大多数人都知道，非递归算法也有出现过。
如：摘自http://www.programfan.com/club/old_showbbs.asp?id=96548
作者：qq590240
#include <iostream>
#include <stdlib.h>
#ifdef _WIN32
using namespace std;
#endif
static void hanoi(int height)
{
int fromPole, toPole, Disk;
int *BitStr = new int[height],
*Hold = new int[height];
char Place[] = {'A', 'B', 'C'};
int i, j, temp;
for (i=0; i < height; i++)
{
BitStr[i] = 0;
Hold[i] = 1;
}
temp = 3 - (height % 2);
i......
第六次编程比赛第2题的3种解法(2006-06-02 21:23:00)
摘要：/*任给 1<=n<=20 个不同的非零正整数，每个正整数最多使用1次，请问这n个正整数能够加和的结果
共有多少种(不考虑和超出long的最大值的可以),
程序中请实现如下函数。用于计算数组data,中ncount的加和的数量。
long getsumcount(long data[], long count);
程序中可以出现别的辅助函数。或辅助结构等。
例如，
data[] = {1,2,3,4};
ncount = 4;
函数返回 10
分解如下。（0不算）
1 = 1
2 = 2
3 = 3 = 1+2
4 = 4 = 1+3
5 = 2+3 = 1+4
6 = 2+4 = 1+2+3
7 = 3+4 = 1+2+4
8 = 1+3+4
9 = 2+3+4
10 = 1+2+3+4
如上。所以结果是10种可能。
程序可这样安排
//给出程序的大体结构。如何写就随便了。。。。
/////////////////////////////////////////////
// 辅助函数或结构定义。。。可有可无。
......
......
......
///实现
long getsumcount(long data[], long count)
{
}
///主函数。
void main()
{
// 输入数据。
.........
.........
xx = getsumcount(data, count);
// 输出有多少种
.........
}
//////////////////////////////////////////////
*/
#include <iostream>
#include <time.h>
#define libsize (1<<16)
#d......
第六次编程比赛第2题的两种解法(2006-06-01 23:36:00)
摘要：
二、任给 1<=n<=20 个不同的非零正整数，每个正整数最多使用1次，请问这n个正整数能够加和的结果共有多少种(不考虑和超出long的最大值的可以),
程序中请实现如下函数。用于计算数组data,中ncount的加和的数量。
long getsumcount(long data[], long count);
程序中可以出现别的辅助函数。或辅助结构等。
例如，
data[] = {1,2,3,4};
ncount = 4;
函数返回 10
分解如下。（0不算）
1 = 1
2 = 2
3 = 3 = 1+2
4 = 4 = 1+3
5 = 2+3 = 1+4
6 = 2+4 = 1+2+3
7 = 3+4 = 1+2+4
8 = 1+3+4
9 = 2+3+4
10 = 1+2+3+4
如上。所以结果是10种可能。
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <time.h>
#define libsize (1<<16)
#define hashsize (1<<16)
#define hashmask (0xffff)
using namespace std;
typedef struct node{
long data;
struct node *next;
}NODE;
NODE hashtab[hashsize];
const long......
求行列式的值(2006-04-23 22:13:00)
摘要：/*求行列式的值
函数介绍：输入一个行列式，求其值
*/
#include <iostream>
using namespace std;
const int N = 10; //行列式的阶数
void Create1(int H[][N]); //构造一个行列式
void Create2(int H[][N]); //构造一个行列式
void PrintH(const int H[][N]); //输出行列式
int HLS(const int a[][N], int n);//输入一个行列式，求其值
void YZS(int Y[][N], const int a[][N], int len, int a_r);//求行列式当前元素的余子式
int main()
{
int a[N][N] = {0};
// Create1(a); //构造一个行列式
Create2(a); //构造一个行列式
PrintH(a); //输出行列式
cout << HLS(a,N) << endl;
getchar();
return 0;
}
void Create1(int H[][N])
{
int i, j;
printf("请按标准格式输入行列式：每行%d个数值，用空格隔开\n", N);
for (i=0; i<N; i++)
{
for(j=0; j<N; j++)
scanf("%d", &H[i][j]);
fflush(stdin);
}
}
void Create2(int H[][N])
......