回龙观手机网站开发服务,terry tao.wordpress,企业品牌推广营销方案,新浪云怎么做淘宝客网站文章目录 11.字串核对12.双色、三色河内塔13.背包问题#xff08;Knapsack Problem#xff09;14.蒙地卡罗法求 PI15.Eratosthenes筛选求质数 11.字串核对
说明#xff1a;今日的一些高阶程式语言对于字串的处理支援越来越强大#xff08;例如Java、Perl等#xff09;Knapsack Problem14.蒙地卡罗法求 PI15.Eratosthenes筛选求质数 11.字串核对
说明今日的一些高阶程式语言对于字串的处理支援越来越强大例如Java、Perl等不过字串搜寻本身仍是个值得探讨的课题在这边以Boyer- Moore法来说明如何进行字串说明这个方法快且原理简洁易懂。 解法字串搜寻本身不难使用暴力法也可以求解但如何快速搜寻字串就不简单了传统的字串搜寻是从关键字与字串的开头开始比对例如 Knuth-Morris-Pratt 演算法 字串搜寻这个方法也不错不过要花时间在公式计算上Boyer-Moore字串核对改由关键字的后面开始核对字串并制作前进表如果比对不符合则依前进表中的值前进至下一个核对处假设是p好了然后比对字串中p-n1至p的值是否与关键字相同。 如果关键字中有重复出现的字元则前进值就会有两个以上的值此时则取前进值较小的值如此就不会跳过可能的位置例如texture这个关键字t的前进值应该取后面的3而不是取前面的7。 #include stdio.h
#include stdlib.h
#include string.h void table(char*); // 建立前进表
int search(int, char*, char*); // 搜寻关键字
void substring(char*, char*, int, int); // 取出子字串 int skip[256]; int main(void) {
char str_input[80];
char str_key[80];
char tmp[80] {\0};
int m, n, p;
printf(请输入字串);
gets(str_input);
printf(请输入搜寻关键字);
gets(str_key);
m strlen(str_input); // 计算字串长度
n strlen(str_key);
table(str_key);
p search(n-1, str_input, str_key); while(p ! -1) {
substring(str_input, tmp, p, m);
printf(%s\n, tmp);
p search(pn1, str_input, str_key);
} printf(\n);
return 0;
} void table(char *key) {
int k, n;
n strlen(key);
for(k 0; k 255; k)
skip[k] n;
for(k 0; k n - 1; k)
skip[key[k]] n - k - 1;
} int search(int p, char* input, char* key) {
int i, m, n;
char tmp[80] {\0};
m strlen(input);
n strlen(key); while(p m) {
substring(input, tmp, p-n1, p);
if(!strcmp(tmp, key)) // 比较两字串是否相同
return p-n1;
p skip[input[p]];
}
return -1;
} void substring(char *text, char* tmp, int s, int e) {
int i, j;
for(i s, j 0; i e; i, j) mp[j] text[i];
tmp[j] \0;
}12.双色、三色河内塔
说明双色河内塔与三色河内塔是由之前所介绍过的河内塔规则衍生而来双色河内塔的目的是将下图左上的圆环位置经移动成为右下的圆环位置
而三色河内塔则是将下图左上的圆环经移动成为右上的圆环
解法无论是双色河内塔或是三色河内塔其解法观念与之前介绍过的河内塔是类似的同样也是使用递回来解不过这次递回解法的目的不同我们先来看只有两个盘的情况这很简单只要将第一柱的黄色移动至第二柱而接下来第一柱的蓝色移动至第三柱。 再来是四个盘的情况首先必须用递回完成下图左上至右下的移动
接下来最底层的就不用管它们了因为它们已经就定位只要再处理第一柱的上面两个盘子就可以了。那么六个盘的情况呢一样首先必须用递回完成下图左上至右下的移动
接下来最底层的就不用管它们了因为它们已经就定位只要再处理第一柱上面的四个盘子就可以了这又与之前只有四盘的情况相同接下来您就知道该如何进行解题了无论是八个盘、十个盘以上等都是用这个观念来解题。 那么三色河内塔呢一样直接来看九个盘的情况首先必须完成下图的移动结果
接下来最底两层的就不用管它们了因为它们已经就定位只要再处理第一柱上面的三个盘子就可以了。
双色河内塔 C 实作
#include stdio.hvoid hanoi(int disks, char source, char temp, char target) {if (disks 1) {printf(move disk from %c to %c\n, source, target);printf(move disk from %c to %c\n, source, target);} else {hanoi(disks-1, source, target, temp);hanoi(1, source, temp, target);hanoi(disks-1, temp, source, target);}
}void hanoi2colors(int disks) {char source A;char temp B;char target C;int i;for(i disks / 2; i 1; i--) {hanoi(i-1, source, temp, target);printf(move disk from %c to %c\n, source, temp);printf(move disk from %c to %c\n, source, temp);hanoi(i-1, target, temp, source);printf(move disk from %c to %c\n, temp, target);}printf(move disk from %c to %c\n, source, temp);printf(move disk from %c to %c\n, source, target);
}int main() {int n;printf(请输入盘数);scanf(%d, n);hanoi2colors(n);return 0;
} 三色河内塔 C 实作
#include stdio.hvoid hanoi(int disks, char source, char temp, char target) {if (disks 1) {printf(move disk from %c to %c\n, source, target);printf(move disk from %c to %c\n, source, target);printf(move disk from %c to %c\n, source, target);} else {hanoi(disks-1, source, target, temp);hanoi(1, source, temp, target);hanoi(disks-1, temp, source, target);}
}void hanoi3colors(int disks) {char source A;char temp B;char target C;int i;if(disks 3) {printf(move disk from %c to %c\n, source, temp);printf(move disk from %c to %c\n, source, temp);printf(move disk from %c to %c\n, source, target);printf(move disk from %c to %c\n, temp, target);printf(move disk from %c to %c\n, temp, source);printf(move disk from %c to %c\n, target, temp);;}else {hanoi(disks/3-1, source, temp, target);printf(move disk from %c to %c\n, source, temp);printf(move disk from %c to %c\n, source, temp);printf(move disk from %c to %c\n, source, temp);hanoi(disks/3-1, target, temp, source);printf(move disk from %c to %c\n, temp, target);printf(move disk from %c to %c\n, temp, target);printf(move disk from %c to %c\n, temp, target);hanoi(disks/3-1, source, target, temp);printf(move disk from %c to %c\n, target, source);printf(move disk from %c to %c\n, target, source);hanoi(disks/3-1, temp, source, target);printf(move disk from %c to %c\n, source, temp);for (i disks / 3 - 1; i 0; i--) {if (i1) {hanoi(i-1, target, source, temp);}printf(move disk from %c to %c\n,target, source);printf(move disk from %c to %c\n,target, source);if (i1) {hanoi(i-1, temp, source, target);}printf(move disk from %c to %c\n, source, temp);}}
}int main() {int n;printf(请输入盘数);scanf(%d, n);hanoi3colors(n);return 0;
} 13.背包问题Knapsack Problem
说明假设有一个背包的负重最多可达8公斤而希望在背包中装入负重范围内可得之总价物品假设是水果好了水果的编号、单价与重量如下所示 0 李子 4KG NT$4500 1 苹果 5KG NT$5700 2 橘子 2KG NT$2250 3 草莓 1KG NT$1100 4 甜瓜 6KG NT$6700
解法背包问题是关于最佳化的问题要解最佳化问题可以使用「动态规划」Dynamic programming从空集合开始每增加一个元素就先求出该阶段的最佳解直到所有的元素加入至集合中最后得到的就是最佳解。
以背包问题为例我们使用两个阵列value与itemvalue表示目前的最佳解所得之总价item表示最后一个放至背包的水果假设有负重量 18的背包8个并对每个背包求其最佳解。
逐步将水果放入背包中并求该阶段的最佳解 放入李子 背包负重 1 2 3 4 5 6 7 8 value 4500 4500 4500 4500 9000 item 放入苹果 背包负重 1 2 3 4 5 6 7 8 value 4500 5700 5700 5700 9000 item 1 1 1 放入橘子 背包负重 1 2 3 4 5 6 7 8 value 2250 2250 4500 5700 6750 7950 9000 item 2 2 1 2 2 放入草莓 背包负重 1 2 3 4 5 6 7 8 value 1100 2250 3350 4500 5700 6800 7950 9050 item 3 2 3 1 3 2 3 放入甜瓜 背包负重 1 2 3 4 5 6 7 8 value 1100 2250 3350 4500 5700 6800 7950 9050 item 3 2 3 1 3 2 3 由最后一个表格可以得知在背包负重8公斤时最多可以装入9050元的水果而最后一个装入的 水果是3号也就是草莓装入了草莓背包只能再放入7公斤8-1的水果所以必须看背包负重7公斤时的最佳解最后一个放入的是2号也就 是橘子现在背包剩下负重量5公斤7-2所以看负重5公斤的最佳解最后放入的是1号也就是苹果此时背包负重量剩下0公斤5-5无法 再放入水果所以求出最佳解为放入草莓、橘子与苹果而总价为9050元。
实作
#include stdio.h
#include stdlib.h #define LIMIT 8 // 重量限制
#define N 5 // 物品种类
#define MIN 1 // 最小重量 struct body { char name[20]; int size; int price;
}; typedef struct body object; int main(void) { int item[LIMIT1] {0}; int value[LIMIT1] {0}; int newvalue, i, s, p; object a[] {{李子, 4, 4500}, {苹果, 5, 5700}, {橘子, 2, 2250}, {草莓, 1, 1100}, {甜瓜, 6, 6700}}; for(i 0; i N; i) { for(s a[i].size; s LIMIT; s) { p s - a[i].size; newvalue value[p] a[i].price; if(newvalue value[s]) {// 找到阶段最佳解 value[s] newvalue; item[s] i; } } } printf(物品\t价格\n); for(i LIMIT; i MIN; i i - a[item[i]].size) { printf(%s\t%d\n, a[item[i]].name, a[item[i]].price); } printf(合计\t%d\n, value[LIMIT]); return 0;
} 14.蒙地卡罗法求 PI
说明蒙地卡罗为摩洛哥王国之首都该国位于法国与义大利国境以赌博闻名。蒙地卡罗的基本原理为以乱数配合面积公式来进行解题这种以机率来解题的方式带有赌博的意味虽然在精确度上有所疑虑但其解题的思考方向却是个值得学习的方式。 解法蒙地卡罗的解法适用于与面积有关的题目例如求PI值或椭圆面积这边介绍如何求PI值假设有一个圆半径为1所以四分之一圆面积就为PI而包括此四分之一圆的正方形面积就为1如下图所示
如果随意的在正方形中投射飞标点好了则这些飞标点有些会落于四分之一圆内假设所投射的飞标点有n点在圆内的飞标点有c点则依比例来算就会得到上图中最后的公式。
至于如何判断所产生的点落于圆内很简单令乱数产生X与Y两个数值如果X2Y2等于1就是落在圆内。
#include stdio.h
#include stdlib.h
#include time.h #define N 50000 int main(void) { int i, sum 0; double x, y; srand(time(NULL)); for(i 1; i N; i) { x (double) rand() / RAND_MAX; y (double) rand() / RAND_MAX; if((x * x y * y) 1) sum; } printf(PI %f\n, (double) 4 * sum / N); return 0;
} 15.Eratosthenes筛选求质数
说明除了自身之外无法被其它整数整除的数称之为质数要求质数很简单但如何快速的求出质数则一直是程式设计人员与数学家努力的课题在这边介绍一个着名的 Eratosthenes求质数方法。 解法首先知道这个问题可以使用回圈来求解将一个指定的数除以所有小于它的数若可以整除就不是质数然而如何减少回圈的检查次数如何求出小于N的所有质数
首先假设要检查的数是N好了则事实上只要检查至N的开根号就可以了道理很简单假设AB N如果A大于N的开根号则事实上在小于A之前的检查就可以先检查到B这个数可以整除N。不过在程式中使用开根号会精确度的问题所以可以使用 ii N进行检查且执行更快。 再来假设有一个筛子存放1N例如 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 … N 先将2的倍数筛去 2 3 5 7 9 11 13 15 17 19 21 … N 再将3的倍数筛去 2 3 5 7 11 13 17 19 … N 再来将5的倍数筛去再来将7的质数筛去再来将11的倍数筛去…如此进行到最后留下的数就都是质数这就是Eratosthenes筛选方法Eratosthenes Sieve Method。 检查的次数还可以再减少事实上只要检查6n1与6n5就可以了也就是直接跳过2与3的倍数使得程式中的if的检查动作可以减少。 #include stdio.h
#include stdlib.h #define N 1000 int main(void) { int i, j; int prime[N1]; for(i 2; i N; i) prime[i] 1; for(i 2; i*i N; i) { // 这边可以改进 if(prime[i] 1) { for(j 2*i; j N; j) { if(j % i 0) prime[j] 0; } } } for(i 2; i N; i) { if(prime[i] 1) { printf(%4d , i); if(i % 16 0) printf(\n); } } printf(\n); return 0;
}
