c程序:
#include <stdio.h> #define CENTER 2 #define MARGIN 5 void star(line){ int left, right, i; char ret[CENTER+MARGIN+1]; for (i=0; i < CENTER+MARGIN+1; ++i) { ret[i]=' '; } if (line > MARGIN){ return; } left = CENTER - MARGIN + line; right= CENTER + MARGIN - line; for (i=0; i <= right; i++){ if (i==left || i==right){ ret[i]='*'; } else{ ret[i]=' '; } } printf("%s\n", ret); } int main(void){ int i; for (i = 0; i< 8; ++i) { star(i); } }
输出:
* * * * * * * *
重新写的程序。每次洗出一张,放在最后,剩下的牌重新洗,直至最后一张。代码如下:
#include<stdio.h> #include<time.h> int N=54; char * pk[]={"黑桃A","黑桃2","黑桃3","黑桃4","黑桃5","黑桃6","黑桃7","黑桃8","黑桃9","黑桃10","黑桃J","黑桃Q","黑桃K","红桃A","红桃2","红桃3","红桃4","红桃5","红桃6","红桃7","红桃8","红桃9","红桃10","红桃J","红桃Q","红桃K","草花A","草花2","草花3","草花4","草花5","草花6","草花7","草花8","草花9","草花10","草花J","草花Q","草花K","方块A","方块2","方块3","方块4","方块5","方块6","方块7","方块8","方块9","方块10","方块J","方块Q","方块K","大王","小王"}; main() { int a[N]; int i; int temp; int p; int ten=0; unsigned int time1,time2; int m=0; for (i=0;i<N;i++) { a[i]=i; } srand((unsigned)time(NULL)); for (m=0;m<100000;m++){ for (i=N-1;i>0;i--) { temp= rand() % i; p=a[i]; a[i]=a[temp]; a[temp]=p; }} for (i=0;i<N;i++) { printf("%02d:%-5s ",i+1,pk[a[i]]); ten++; if (ten==10) { printf("\n"); ten=0; } } printf("\n"); }
贴图:
在火车上看人打扑克,想做个洗牌算法。我的思路用c语言实现,是这样的:
/*本程序是洗牌算法的c语言实现. 原理是,生成52个随机数;每生成一个,记录在数组中,同时记下该数已经生成.下次再生成随机数,如果 已经成生过,则重新生成一个随机数.生成与否,该信息记录在另一个数组中.例如,如果数字15已经成生,则 array[15]=1; */ #include<stdio.h> #include<time.h> #include<stdlib.h> #define N 52 int poker[N]; //用来记录生成的扑克代码 int back[N]; //用来记录"hash"信息 init_back() { //初始化hash数组 int i=0; for (i=0;i<N;i++) { back[i]=0; } } //辅助函数,用来打印数组,每10个一行. print_array(int * array) { int i=0,m=0; for (i=0;i<N;i++) { printf("%d ",array[i]); if ((i+1) % 10 ==0 && i) { printf("\n"); } } printf("\n"); } //生成随机数. rand_back() { int i=0; int counter=0; //用来测试一共生成了多少次随机数.计算效率. srand((unsigned)time( NULL ) );//用来初始化随机函数,以便生成不同的随机数. for (i=0;i<N;i++) { ++counter; int p=rand()%N; if (!back[p]) { poker[i]=p; back[p]=1; } else { i--; } } printf("the counter is: %d\t,效率是 %f;\n",counter,(52.0/counter)); } int main() { //print_array(poker); init_back(); rand_back(); //print_array(poker); //getchar(); }
生成其中一组随机记录为:
23 8 5 17 48 51 14 49 35 36
38 30 31 24 29 47 34 18 41 11
27 16 26 9 45 43 46 0 3 19
37 13 32 20 6 22 4 33 7 21
40 50 42 1 2 28 39 15 25 12
10 44
不过效率似乎不高。计算所生成的有效随机数与尝试次数之比,结果如下:
c语言提供了几个位操作符,其中:
其结合力是依次递减的。
清华版《离散数学》(9787302130666),第1.2.2的合取、析取,使用c语言实现是:
#include<stdio.h> //条件:设p与q是两个命题,若p则q //只有当p为1,q为0时返回0值,其余返回1. tiaojian(p,q) { return (p && !q)?0:1; } //双条件:设p与q是两个命题,p当且仅当q,p的充分必要条件是q //当且仅当p与q同为0或同为1时返回1,其余返回0 shuangtiaojian(p,q) { return ((p && q)||(!p && !q))?1:0; } main() { int p,q; printf("P\tQ\tP合取Q\t排斥或\t可兼或\t条件\t双条件\n"); for(p=0;p<=1;p++) { for(q=0;q<=1;q++) { printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\n",p,q,p&q,p^q,p|q,tiaojian(p,q),shuangtiaojian(p,q)); } //printf("\n"); } }
输出结果:
我读的紫龙书是机械工业出版社2009.01之第2版。ISBN:978-7-111-25121-7。译者是南京大学的赵建华,邓滔,戴新宇。
该书74页有个错误:
3)串s的子串(substring)是删除s的某个前缀和某个后缀之后得到的串。例如,bnana,nan和e是bnana的子串。
第一感觉这里有问题。翻开英文原书,这样写的:
3. A substring of s is obtained by deleting any prefix and any suffix from s. For instance, banana, nan, and E are substrings of banana.
就应该只是删除子串嘛,不应该是删除0个或多个符号,成为子序列那样。本书的编辑真该打屁股。
另,3.4.5,
该函数的目标是使得b1b2...bf(s)是最长的既是b1b2...bn的真前缀又是b1b2...bs的后缀的子串。
对应英文是:
The objective is that blb2...bf(s) is the longest proper prefix of b1b2...bs, that is also a suffix of b1b2bs.
读过原文之后,才勉强可理解中文翻译。中文之所以费解,是由于将“最长的”三字依英文位置给前置了。私以为放在后面会好理解一些,如:
该函数的目标是使得b1b2...bf(s)既是b1b2...bn的真前缀又是b1b2...bs的后缀的最长的子串。
就此打住,切入正题。说一下失效函数。
原书中,图3-19给出的fail函数,我使用c语言做出来了。要点是原图中的下标是以1-based,翻译为c语言要调整为0-based。程序如下:
#include<stdio.h> #include<string.h> int fail(const char *b) { int n=strlen(b); int t=0; int f[n+1]; f[1]=0; int s; for(s=1;s<=n;s++) { while(t>0 && b[s]!= b[t]) { t=f[t]; } if (b[s]==b[t]) { t++; f[s+1]=t; } else { f[s+1]=0; } } for (s=1;s<=n;s++) { printf("%d ",f[s]); } printf("\n"); } main() { fail("abababaab"); }
运行该程序,解得3.4.3各串的失效函数分别为:
最近在看龙书第1版。第二版的例子有的是以java写的。个人喜欢第一版的c程序。
看到第2.6,上面提供了一个中缀转后缀的C语言程序。不过只支持个位数,加减运算。我修改一下,使之增加对多位正整数、乘、除、小括号的支持。允许数字与操作符之间出现任意空白字符。
理论依据很清晰,就不再写额外的注释了。
#include<stdio.h> #include<ctype.h> /* 中缀表达式 理论依据: expr -> expr + term | expr - term | term term -> term * factor | term / factor | factor factor -> digit | ( expr ) */ int la; //lookahead main() { la=getchar(); expr(); putchar('\n'); } is_space(c) int c; { if (c==' ' || c=='\t') { return 1; } else return 0; } space() { while (la==' ' || la=='\t') { la=getchar(); } } expr() { term(); while(1) { if (la=='+') { putchar(' '); match('+');term();putchar(' ');putchar('+'); } else if (la=='-') { putchar(' '); match('-');term();putchar(' ');putchar('-'); } /* else if (is_space(la)) { space(); } */ else break; } } term() { factor(); while(1) { if (la=='*') { putchar(' '); match('*');factor();putchar(' ');putchar('*'); } else if (la=='/') { putchar(' '); match('/');factor();putchar(' ');putchar('/'); } /* else if (is_space(la)) { space(); } */ else break; } } factor() { space(); if (isdigit(la)) { while (isdigit(la)) { putchar(la); match(la); } } else if (la=='(') { while(la!=')') { la=getchar(); expr(); } la=getchar(); } space(); } match(t) int t; { if (la==t) { la=getchar(); } else error(); } error() { printf("syntax error\n"); }