北戴河网站建设,西安网站建设动力无限,网站运营策划ppt,保洁网站模板n皇后问题
在nn格的国际象棋上摆放n个皇后#xff0c;使其不能互相攻击#xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上#xff0c;问有多少种摆法。
算法设计 回溯法
在包含问题的所有解的解空间树中#xff0c;按照深度优先搜索的策略#xff0c;从根…n皇后问题
在n×n格的国际象棋上摆放n个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜线上问有多少种摆法。
算法设计 回溯法
在包含问题的所有解的解空间树中按照深度优先搜索的策略从根结点出发深度探索解空间树。当探索到某一结点时要先判断该结点是否包含问题的解如果包含就从该结点出发继续探索下去如果该结点不包含问题的解则逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法。
若用回溯法求问题的所有解时要回溯到根且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时只要搜索到问题的一个解就可以结束。 简单来说就是通过递归将所有可能的情况都列出来最后找到符合要求的情形。 判断皇后是否能在该位置
/*** 判断皇后是否能在该位置*/
int place(int* paraSolution, int paraT){int j;for (j 1; j paraT; j ){if ((abs(paraT - j) abs(paraSolution[j] - paraSolution[paraT])) || (paraSolution[j] paraSolution[paraT]))return false;}return true;
} 回溯法具体实现
/*** 回溯法*/
void backtracking(int* paraSolution, int paraN, int paraT){int i;if (paraT paraN){for (i 1; i paraN; i )printf(%d , paraSolution[i]);printf(\r\n);}else{for (i 1; i paraN; i ){paraSolution[paraT] i;if (place(paraSolution, paraT))backtracking(paraSolution, paraN, paraT 1);}}
}n皇后问题
/*** n皇后问题*/
void nQueen(int paraN){int i;int* solution (int*)malloc((paraN 1) * sizeof(int));for (i 1; i paraN; i )solution[i] 0;backtracking(solution, paraN, 1);
} 测试结果 1 3 5 2 4 1 4 2 5 3 2 4 1 3 5 2 5 3 1 4 3 1 4 2 5 3 5 2 4 1 4 1 3 5 2 4 2 5 3 1 5 2 4 1 3 5 3 1 4 2 输出结果从左至右表明第i个皇后所在i行的第几列每一行代表一个问题解法。 完整代码
#include stdio.h
#include malloc.h
#include math.h
#define false 0
#define true 1
/*** 判断皇后是否能在该位置*/
int place(int* paraSolution, int paraT){int j;for (j 1; j paraT; j ){if ((abs(paraT - j) abs(paraSolution[j] - paraSolution[paraT])) || (paraSolution[j] paraSolution[paraT]))return false;}return true;
}/*** 回溯法*/
void backtracking(int* paraSolution, int paraN, int paraT){int i;if (paraT paraN){for (i 1; i paraN; i )printf(%d , paraSolution[i]);printf(\r\n);}else{for (i 1; i paraN; i ){paraSolution[paraT] i;if (place(paraSolution, paraT))backtracking(paraSolution, paraN, paraT 1);}}
}/*** n皇后问题*/
void nQueen(int paraN){int i;int* solution (int*)malloc((paraN 1) * sizeof(int));for (i 1; i paraN; i )solution[i] 0;backtracking(solution, paraN, 1);
}
/*** 程序入口*/
int main(){nQueen(5);return 1;
}哈夫曼树
哈夫曼树给定一组具有确定权值的叶子结点带权路径长度最小的二叉树。 实现哈夫曼编码的算法可分为两大部分
根据所给各个元素所占的权重值构造哈夫曼树在哈夫曼树上求每个叶结点的编码
例如给定某 7 个字符出现的权值分别为 3、12、7、4、2、8、11由权重值建立的哈夫曼树为 通过哈夫曼树我们可以轻松获取每个叶子结点元素的哈夫曼编码如权重值为 4 的元素的哈夫曼编码为000。 对于给定的哈夫曼树求其所有叶结点的实现方式有两种
从叶子结点一直找到根结点逆向记录途中经过的结点的权重值。从根结点出发一直到相应叶子结点记录途中经过的所有结点的权重值。 头函数和结构体
#include stdio.h
#include string.h
#include stdlib.h#define MaxSize 1024 // 读入文件的上限
#define OK 1
#define ERROR 0
typedef int Status;typedef struct wordcnt{ // 统计字符和对应的次数 char ch;int cnt;
}Count;typedef struct NumCount{ // 统计次数的外部封装 Count count[MaxSize];int length;
}NumCount;typedef struct HTree{ // 哈夫曼树结构 char data; int weight;int parent,lchild,rchild;
}HTNode,*HuffmanTree; typedef struct HCode{ // 编码结构 char data;char* str;
}*HuffmanCode;
读入文件及记录出现次数 /** 读入文件*/
Status ReadData(char *source) {FILE *r fopen(input.txt, r);//读取本文件夹下的input文件if (r NULL) {return ERROR;}fgets(source, MaxSize, r);fclose(r);return OK;
}Status WordCount(char *data, NumCount *paraCnt) {int flag;// 标识是否已经记录int len strlen(data);for (int i 0; i len; i) {flag 0;for (int j 0; j paraCnt-length; j) {if (paraCnt-count[j].ch data[i]) { // 若已有记录直接paraCnt-count[j].cnt;flag 1;break;}}if (!flag) { // 没有记录则新增paraCnt-count[paraCnt-length].ch data[i];paraCnt-count[paraCnt-length].cnt;paraCnt-length;}}return OK;
}Status Show(NumCount *paraCnt) {printf(------------The length is------------\n);for (int i 0; i paraCnt-length; i) {printf(The character %c appears %d \n, paraCnt-count[i].ch, paraCnt-count[i].cnt);}return OK;
} 哈夫曼树构建
Status CreateHuffmanTree(HuffmanTree HT,int length,NumCount cntarray){if(length1)return ERROR;int s1,s2;int mlength*2-1;HT(HuffmanTree)malloc((m1)*sizeof(struct HTree));for(int i 1;i m;i) // 初始化 {HT[i].parent 0;HT[i].lchild 0;HT[i].rchild 0;}for(int i 1;i length;i) {HT[i].data cntarray.count[i-1].ch;HT[i].weight cntarray.count[i-1].cnt;}for(int i length 1;i m;i){select(HT,i-1,s1,s2); // 从前面的范围里选择权重最小的两个节点 HT[s1].parent i;HT[s2].parent i;HT[i].lchild s1;HT[i].rchild s2;HT[i].weight HT[s1].weight HT[s2].weight; // 得到一个新节点 }return OK;
}Status select(HuffmanTree HT,int top,int *s1,int *s2)
{int min INT_MAX;for(int i 1;i top;i) // 选择没有双亲的节点中权重最小的节点 {if(HT[i].weight min HT[i].parent 0){min HT[i].weight;*s1 i;}}min INT_MAX;for(int i 1;i top;i) // 选择没有双亲的节点中权重次小的节点 {if(HT[i].weight min i ! *s1 HT[i].parent 0){min HT[i].weight;*s2 i;}}return OK;
}Status CreateHuffmanCode(HuffmanTree HT,HuffmanCode HC,int length)
{HC (HuffmanCode)malloc((length1)*sizeof(struct HCode));char* cd (char*)malloc(sizeof(char) * length); // 存储编码的临时空间 cd[length-1] \0; // 方便之后调用strcpy函数 int c,f,start;for(int i 1;i length;i){start length-1; // start表示编码在临时空间内的起始下标由于是从叶子节点回溯所以是从最后开始 c i;f HT[c].parent;while(f ! 0){--start; // 由于是回溯所以从临时空间的最后往回计 if(HT[f].lchild c)cd[start] 0;else cd[start] 1;c f;f HT[c].parent;}HC[i].str (char*)malloc(sizeof(char) * (length - start)); // 最后实际使用的编码空间大小是length-start HC[i].data HT[i].data;strcpy(HC[i].str,cd[start]); // 从实际起始地址开始拷贝到编码结构中 }return OK;
}
编码解码
Status Encode(char *data,HuffmanCode HC,int length)
{FILE *w fopen(code.txt, w);for(int i 0;i strlen(data);i) // 依次读入数据查找对应的编码写入编码文件 {for(int j 1;j length;j){if(data[i] HC[j].data){fputs(HC[j].str,w);}}}fclose(w);printf(the code txt has been written\n);return OK;
}Status Decode(HuffmanTree HT,int length)
{char codetxt[MaxSize*length];FILE *r fopen(code.txt, r);fgets(codetxt, MaxSize*length, r);fclose(r);FILE *w fopen(output.txt, w);int root 2*length-1; // 从根节点开始遍历 for(int i 0;i strlen(codetxt);i){if(codetxt[i] 0) root HT[root].lchild; //为0表示向左遍历 else if(codetxt[i] 1) root HT[root].rchild; //为1表示向右遍历 if(HT[root].lchild 0 HT[root].rchild 0) // 如果已经是叶子节点输出到输出文件中然后重新回到根节点 {putc(HT[root].data,w);root 2*length-1;}}fclose(w);printf(the output txt has been written\n);return OK;
}
程序入口 int main(){char data[MaxSize];NumCount Cntarray;Cntarray.length0;ReadData(data); //读入数据WordCount(data,Cntarray); //统计次数Show(Cntarray);//查看每个单词出现的对应次数HuffmanTree tree;CreateHuffmanTree(tree,Cntarray.length,Cntarray);//建树HuffmanCode code; CreateHuffmanCode(tree,code,Cntarray.length); // 创建编码 Encode(data,code,Cntarray.length); // 生成编码文件 Decode(tree,Cntarray.length); // 解码 printf(Please view the generated TXT file to check the result);return 0;
} input.txt: Life is full of confusing and disordering Particular time,a particular location,Do the arranged thing of ten million time in the brain,Step by step ,the life is hard to avoid delicacy and stiffness No enthusiasm forever,No unexpected happening of surprising and pleasing So,only silently ask myself in mind Next happiness,when will come? codefile.txt: 011100010001001111011010000101101100111111010010001010100111001110111111100111100100111111010101000110011101110110001100100101011001000001010011111001001011011110000011001110111010111001010001110001100001111111111010010100011100101011000011110011011110101000101011111000111000110000111111111101001010001110010100100011111111100001100000011110011101001110000001110101100100111011011000111001110010001100111011110110010101011001001000110011101110100111001110101101101110010111110000000100010000001111001010110000111100110110100011001010110010011101101111110111110010000001100111010111110100110110101111101111110110111011010101011011010111110111101001100100111011010010000100111101101000010110101001100011100100101010110001110110000100000001100010010101100101101001000011111110001111110111011011000110010010101010101100001001110011110011010101010110111111000011101110111000110010011111010101000100001011111001011001100111110011010100000110111100111010111110000111011111011100110101000100111111011111110110110110010101010011000011110111111011100000110011101110100111001110101011111011110001111111000000101000110011101110110001100100101010111100101101100001010001100111011101111110100011111010001111000010011101101010100000101101110001100010011101101100001010111001110111110001110101011101001010011101000110010111110000011001001010111111001101010001001101010100110000111101111000110011010101010111101001000010100111011100101010000100000100010101111111001111110011010100011101000110 output.txt: Life is full of confusing and disordering Particular time,a particular location,Do the arranged thing of ten million time in the brain,Step by step ,the life is hard to avoid delicacy and stiffness No enthusiasm forever,No unexpected happening of surprising and pleasing So,only silently ask myself in mind Next happiness,when will come?
