博文
连通问题(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-44-9 4-98-0 8-02-3 2-35-6 5-62-9 &n......
用空间换时间---对处理大量数据问题的一点思考(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 500unsigned long UglyNumber(int n){ unsigned long lib[MAX] = {1,};//用来存储丑陋数表 unsigned long i, num; int k = 1; for (i=2; k<MAX; n++) { &n......
手机拼音输入法头文件和主函数(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中逆序查找#号，直到找到#号或遇到buf的第一个元素为止。 若找到#号，则把#号之后的合法字符（数字）复制到value； 若未找到#号，则把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. 汉字选择状态： 进入本状态，如果所选的拼音组合包含对应汉字。则可以选择汉字。否则回到状态1，并且此时不输出任何汉字。每页最多有10个汉......
求围圈问题的详细算法和程序集锦(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 N = 2000000; //被分析的数的最大值，若执行Sushu_3()，N不能超过1000000 &nb......
汉诺塔非递归算法(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 _WIN32using 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); int TotalMoves = (1 << height) - 1; for (i=1; i <= TotalMoves; 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 = 12 = 23 = 3 = 1+24 = 4 = 1+3
5 = 2+3 = 1+46 = 2+4 = 1+2+37 = 3+4 = 1+2+48 = 1+3+49 = 2+3+410 = 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)#define hashsize (1<<16)#define hashmask (0xffff)using namespace std;
const long MAX = 20;
typedef struct node1{ long key; &nbs......
第六次编程比赛第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 = 12 = 23 = 3 = 1+24 = 4 = 1+35 = 2+3 = 1+46 = 2+4 = 1+2+37 = 3+4 = 1+2+48 = 1+3+49 = 2+3+410 = 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 MAX = 20;
bool IsNew(long array[], long len, long data);void solve(const long data[], bool lib[], long a[], long len, long pos, lo......
求行列式的值(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]){ int i, j; for(i=0; i<N; i++) for(j=0; j<N; j++) H[i][j] = rand()......