我们在大学扎根,成长,受教育;我们也在这个时候开始审视自己,审视大学的意义究竟何在。我想树的生长必定要经过风吹雨打,日晒甘霖。因此对我来说,我一直信奉一种理念:大学即生活。大学除了充实我们的学识之外,更重要的是教会我们如何生活,以及如何看待学习、工作、友情 、爱情……我想一个人的大学无论失去哪一方面,都是不完整的,就像树只遇风不经雨,就必将会夭折。

但也不要忘记,当我们在经历蜕变时,我们仍旧青春。我们的青春让我们在清晨的第一束阳光的照耀下,背起书包走向教室、走向讲学堂,去聆听教授们激情澎湃的讲演。我们的青春在图书馆的木质桌椅上,教会了我们享受流淌的时间。我们的青春在那个黄昏的远眺,教会了我们深邃的思绪。我们的青春在那场演出中,无拘无束地宣泄;也在那个深情的拥抱中,让我们想起曾有那么一句话回荡在属于我们的大学时代——

植此四年,今昔一念。

师大带给我的,更多是一种平和的心态,认真踏实的学习态度,还有简单的生活方式。或许你不屑一顾,但我觉得,这样就很好。

1.数制转换 各进制数之间的转换规则:整数部分除基取余,逆序排列 小数部分乘基取整,顺序排列(乘到小数部分为0,8位即可存在误差) 证明从定义出发 Keywords:权 2.带符号数 1负 0正 最高位为符号位 对数的处理一般8bit一组,不够补0 浮点数机制就是科学计数法:最高位符号位 8位指数位 其余数值位 定点数小数点固定 3.反码 补码 反码求法:正数反码即为原码 负数反码保留符号位,其余位取反 补码求法:正数的补码即原码 负数的补码是其反码加1 二进制数补码运算加减 Step1:把A与B(-B)均转化为补码 Step2:两补码相加,符号位也参与运算 Step3:舍弃溢出位 Step4:得到结果的补码 反码补码运算规则: X反反=X X补补=X X反+Y反=(X+Y)反 循环进位 X补+Y补=(X+Y)补 舍弃进位

注意补码加法的进位

补码相加符号位也参与运算 如果当前补码位数不足以满足相加运算后的数,则产生的进位为溢出 如果当前补码位数可以满足相加运算后的数,则产生的进位舍弃

字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”ABCDABD”? 许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。 这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。 1. 首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。 2. 因为B与A不匹配,搜索词再往后移。 3. 就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。 4. 接着比较字符串和搜索词的下一个字符,还是相同。 5. 直到字符串有一个字符,与搜索词对应的字符不相同为止。 6. 这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。 7. 一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,继续把它向后移,这样就提高了效率。 8. 怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。 9. 已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数: _  移动位数 = 已匹配的字符数对应的部分匹配值_ 因为 6 – 2 等于4,所以将搜索词向后移动4位。 10. 因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 – 0,结果为 2,于是将搜索词向后移2位。 11. 因为空格与A不匹配,继续后移一位。 12. 逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 – 2,继续将搜索词向后移动4位。 13. 逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 – 0,再将搜索词向后移动7位,这里就不再重复了。 14. 下面介绍《部分匹配表》是如何产生的。 首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。 15. “部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例, _  - ”A”的前缀和后缀都为空集,共有元素的长度为0;_ - ”AB”的前缀为[A],后缀为[B],共有元素的长度为0 - ”ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0 - ”ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0 - ”ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1 - ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2 - ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0 16. “部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置。

#include <stdio.h>

#include <string.h>
int findnext(char data[],int next[],int nkey);
int main()
{
char data[1001];
char key[1001];
memset(data,sizeof(data),’\0’);
memset(key,sizeof(key),’\0’);
int ndata,nkey,i,position;
while(scanf(“%s”,data)!=EOF)
{
position=0;
scanf(“%s”,key);
ndata=strlen(data);
nkey=strlen(key);
int next[nkey];
for(int z=0;z<nkey;z++)
next[z]=0;
findnext(key,next,nkey);
while(position<=ndata)
{
for(i=0;i<nkey;i++)
if(data[position+i]!=key[i])
break;
if(i==nkey && key[i-1]==data[position+i-1])
{
printf(“Position:%d\n”,position+1);
position=position+i-next[i-1];
}
else if (i!=0)
{
position=position+i-next[i-1];
}
else if (i==0)
position++;
}
printf(“Done!\n”);
}
}
int findnext(char data[],int next[],int nkey)
{
int pin,i,j,suc,flag;
next[0]=0;
for(pin=1;pin<nkey;pin++)
{
for(i=0;i<=pin-1;i++)
{
suc=pin-i;
flag=1;
for(j=0;j<=i;j++)
{
if(data[j]!=data[suc+j])
{
flag=0;
break;
}
}
if(flag==1)next[pin]=i+1;
}
}
return 1;
}

findnext()函数的作用为生成部分匹配表next[],在此函数中,使用变量pin来控制当前字串切片位置,suc为后缀起始点,通过suc+j来控制后缀起始点,通过j++来比对前缀和后缀的各位字符。注意:i为数组索引值,而i+1才为实际比对字符数。 KMP算法的时间复杂度为O(n)

先Copy一下什么是全错位排序:

全错位排列:即被著名数学家欧拉(Leonhard Euler,1707-1783)称为组合数论的一个妙题的“装错信封问题”。

“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli,1667-1748)的儿子丹尼尔·伯努利(DanidBernoulli,1700-1782)提出来的,大意如下:

一个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多少种?

递推公式

瑞士数学家欧拉按一般情况给出了一个递推公式:

用A、B、C……表示写着n位友人名字的信封,a、b、c……表示n份相应的写好的信纸。把错装的总数为记作f(n)。假设把a错装进B里了,包含着这个错误的一切错装法分两类:

(1)b装入A里,这时每种错装的其余部分都与A、B、a、b无关,应有f(n-2)种错装法。

(2)b装入A、B之外的一个信封,这时的装信工作实际是把(除a之外的)(n-1 )份信纸b、c……装入(除B以外的)n-1个信封A、C……,显然这时装错的方法有f(n-1)种。

总之在a装入B的错误之下,共有错装法f(n-2)+f(n-1)种。a装入C,装入D……的n-2种错误之下,同样都有f(n-2)+f(n-1)种错装法,因此:

f(n)=(n-1) {f(n-1)+f(n-2)}

公式可重新写成 f(n)-nf(n-1)=-[f(n-1)-(n-1)f(n-2)] (n>2)

很显然,比如在10对儿里面有3对儿排错了,3C6选出3对儿再乘以3对儿的错排可能—>AC!

#include <stdio.h>

#include <math.h>

#include <string.h>
long long int combination(int a,int b);
long long int fac(int num);
int main()
{
int m,n,e;
long long int data[21];
memset(data,sizeof(data),0);
data[1]=0;data[2]=1;data[3]=2;
for(int i=4;i<=20;i++)
data[i]=(i-1)(data[i-2]+data[i-1]);
scanf(“%d”,&e);
for(int z=1;z<=e;z++)
{
scanf(“%d%d”,&n,&m);
if(m==n)
printf(“%lld\n”,data[n]);
else
printf(“%lld\n”,combination(n,m)
data[m]);
}
return 0;
}
long long int combination(int a,int b)
{
int i,j;
long long int ans=1;
for(i=a;i>=a-b+1;i–)
ans=ansi;
return ans/fac(b);
}
long long int fac(int num)
{
int i;
long long int out=1;
for(i=1;i<=num;i++)
out=out
i;
return out;
}

Giving up, why should I I’ve come to far to forget We’re beautiful, we just got lost Somewhere along the way So much was missing when you went away Let’s start from here, lose the past Change our minds, we don’t need a finish line Let’s take this chance don’t think too deep Of all those promises we couldn’t seem to keep I don’t care where we go Let’s start from here Standing here face to face A finger on your lips Don’t say a word don’t make a sound Silence surrounds us now Even when you were gone I felt you everywhere Let’s start from here, lose the past Change our minds, we don’t need a finish line Let’s take this chance don’t think too deep Of all those promises we couldn’t seem to keep I don’t care where we go Let’s start from here Let’s start from here I’ve never been the one to open up But you’ve always been the voice within The only warmth from my cold heart Let’s start from here, lose the past Change our minds, we don’t need a finish line Let’s take this chance don’t think too deep Of all those promises Let’s start from here, lose the past Change our minds, we don’t need a finish line Let’s take this chance don’t think too deep Of all those promises we couldn’t seem to keep I don’t care where we go Let’s start from here Let’s start from here Let’s start from here Let’s start from here

欢迎使用WordPress。这是系统自动生成的演示文章。编辑或者删除它,然后开始您的博客!

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×