文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

今天发现一个问题，已经造成了溢出，需要用到传说中的fflush(stdin);来解决。先看下面的代码：

#include <stdio.h>

int main()
{
char s[10],s1[10],s2[10],s3[10];
scanf("%s",&s);
printf("%s\n",s);
scanf("%s%s%s",&s1,&s2,&s3);
printf("%s %s %s\n",s1,s2,s3);
system("pause");
return 0;
}

程序想达到这样一个目的：两次都输入Slyar is good!，第一次输出Slyar，第二次输出Slyar is good!。但是结果却不是我们期望看到的，而是：

Slyar is good!
Slyar
Slyar is good!
is good! Slyar

其中蓝色是我输入的部分，而红色是程序输出的结果，可以看到第二次程序没有输出Slyar is good!而是输出了is good! Slyar，我们来分析一下。

当我们输入Slyar is good!后，系统会把第一个空白当成结束，也就是输出Slyar，这没错。然后紧接着我们再次输入Slyar is good!，按照一般思维，应该是Slyar给了S1,is给了S2，good!给了S3，但是。。。

你看到的is good! Slyar中的is good!其实是第一次输入Slyar is good!后余留在缓冲区里的那部分！也就是说，当第一次系统截断Slyar以后，剩下的部分就留在了缓冲区，当你第二次输入后，系统就把缓冲区里的is good!分配给了S1和S2。这样，只有第三次输入的Slyar被分配给了S3，所以当我们打印S1、S2、S3时，会出现is good! Slyar

那么怎么解决这个问题呢？这就要用到fflush(stdin);了：stdin是默认的输入流文件，对应输入缓冲，而fflush(stdin);就可以清空整个输入缓冲区，本例中即把缓冲区内的is good!刷掉。所以，我们的代码应该这样写：

#include <stdio.h>

int main()
{
char s[10],s1[10],s2[10],s3[10];
scanf("%s",&s);
printf("%s\n",s);
fflush(stdin);
scanf("%s%s%s",&s1,&s2,&s3);
printf("%s %s %s\n",s1,s2,s3);
system("pause");
return 0;
}

编译运行，没问题！这点需要注意，否则极易造成溢出。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

下午看异或运算符(XOR)时想到的这个东西，先说下作用：

当你输入"SLYar"的时候，程序会将其中的大写字母转换为小写字母，将其中的小写字母转换为大写字母，所以程序会输出"slyAR"。

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main()
{
    int i, len;
    char str[100];
    gets(str);
    len=strlen(str);
    for (i = 0; i < len; i++)
    if (isalpha(str[i]))
    {
        str[i] ^= 32;
    }
    puts(str);
    return 0;
}

其中用到了一个函数isalpha()，作用是判断参数是否为英文字母。当参数为英文字母a-z或A-Z时，返回非零值，否则返回零。这个函数用到的头文件是ctype.h。

下面解释核心部分 " str[i] ^= 32; "

我们知道同一个英文字母大小写的ASCII码相差32。假设我们现在有二个字母"S"和"s"，大写"S"的ASCII码为83，小写"s"的ASCII码为115，我们将32、83、115的二进制码列出来。

83   1010011
32   0100000(最低位为第一位，只有第六位是1，其他位都是0)
115 1110011

我们来回顾一下异或运算符(XOR)的特点：

与0异或时，它的值不变。
与1异或时，它的值相反。

因此，对比上面的竖式，我们可以很清楚地看到，只要将英文字母ASCII码的第6位与1异或，其他位与0异或，即可实现英文字母的大小写互换。也就是让英文字母的ASCII码与32异或即可。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

声明：我决定不更改自己的代码风格。(2008年10月15日)

今天看了《华为编程规范和范例》，决定修改我的代码风格，以使我的代码和国际接轨。。。

其实我蛮喜欢我自己原来的风格的，因为可以少打很多东西，新的风格需要很多空格，需要很多回车，需要很多括号。。。我是懒人，我本不想改。。。但是没办法，现在不改以后就不好改了，我知道我的代码不是只给我自己看，所以，我还是规范一些，修改我自己的风格吧。。。

《华为编程规范和范例》在Slyar的下载基地里有，hwprogram.doc，需要的可以自己下载。

列举一下我需要修改的风格：

1、相对独立的程序块之间、变量说明之后必须加空行。

以前变量之间我是加空行的，不过像if语句段这样的程序块，我是不加空行的，需要修改。

2、if、for、do、while、case、switch、default等语句自占一行，且if、for、do、while等语句的执行语句部分无论多少都要加括号{}

以前像if、for、do、while等语句的执行语句如果只有一行我就会省略{}，需要修改。

3、程序块的分界符(如C/C++语言的大括号‘{’和‘}’)应各独占一行并且位于同一列，同时与引用它们的语句左对齐。在函数体的开始、类的定义、结构的定义、枚举的定义以及if、for、do、while、switch、case语句中的程序都要采用如上的缩进方式。

以前我习惯把"{"写在if、for等语句后面，需要修改。

4、在两个以上的关键字、变量、常量进行对等操作时，它们之间的操作符之前、之后或者前后要加空格；进行非对等操作时，如果是关系密切的立即操作符(如->)，后不应加空格。

(1) 逗号、分号只在后面加空格。
(2)比较操作符, 赋值操作符"="、 "+="，算术操作符"+"、"%"，逻辑操作符"&&"、"&"，位域操作符"<<"、"^"等双目操作符的前后加空格。
(3)"!"、"~"、"++"、"--"、"&"（地址运算符）等单目操作符前后不加空格。
(4)"->"、"."前后不加空格。
(5) if、for、while、switch等与后面的括号间应加空格，使if等关键字更为突出、明显。

5、注释应与其描述的代码相近，对代码的注释应放在其上方或右方(对单条语句的注释)相邻位置，不可放在下面，如放于上方则需与其上面的代码用空行隔开。

以前放上面注释了不加空行，需要修改。

6、注意运算符的优先级，并用括号明确表达式的操作顺序，避免使用默认优先级。

以前如果是默认优先级，就不加括号了，懒。。。需要修改。

7、尽量用乘法或其它方法代替除法，特别是浮点运算中的除法。

8、不要一味追求紧凑的代码，因为紧凑的代码并不代表高效的机器码。

9、过程/函数中申请的（为打开文件而使用的）文件句柄，在过程/函数退出之前要关闭。

分配的内存不释放以及文件句柄不关闭，是较常见的错误，而且稍不注意就有可能发生。这类错误往往会引起很严重后果，且难以定位。

10、时刻注意表达式是否会上溢、下溢。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

下午做题的时候用到了快速排序(QuickSort)，只不过这次换成C语言实现。草草写了一个，感觉很乱，改。。。改完还乱。。。继续改。。。最后结果就是如下这个快速排序(QuickSort)算法的C语言实现。

void qsort(int s[], int l, int r)
{
    int i, j, x;
    if (l < r)
    {
        i = l;
        j = r;
        x = s[i];
        while (i < j)
        {
            while(i < j && s[j] > x) j--; /* 从右向左找第一个小于x的数 */
            if(i < j) s[i++] = s[j];
            while(i < j && s[i] < x) i++; /* 从左向右找第一个大于x的数 */
            if(i < j) s[j--] = s[i];
        }
        s[i] = x;
        qsort(s, l, i-1); /* 递归调用 */
        qsort(s, i+1, r);
    }
}

我的这个算法实现是每次从数组头部取数字作为基准，看起来好理解一些，呵呵~我是这么认为的。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序(QuickSort)的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)，平均时间复杂度为O(nlgn)。快速排序(QuickSort)在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

今天就研究这个"任意位数的高精度阶乘算法"了，通过和大三的一个学长讨论，最终写出了这个还比较满意的算法：

1、利用C语言的动态数组来达到任意位数，但是首先需要知道数组的长度，也就是N!有多少位。

2、求出N!的结果有多少位，这个公式我就不证明了，是log10(1)+log10(2)+···+log10(n) 取整加1。

3、使用万进制来进位，减少空间的利用，提高运算速度。

4、高精度阶乘算法。

5、因为使用万进制，所以输出各位的时候需要补0。

6、最后发现如果N<1000的话结果的首位会出现0，因此单独输出第一位保证首位没有0。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
 
/* 求N!的位数公式 log10(1)+log10(2)+···+log10(n) 取整加1  */
int wei(int n)
{
	int i;
	double sum=0;
	for(i=1;i<=n;i++) sum+=log10((double)i);
	/* 以万为进制，一位可以表示4个数，减少存储空间 */
	return (int)((sum+1)/4+1);
}
 
/* 高精度阶乘核心 */
int main()
{
	int i,j,n,jinwei,weishu=1,temp;
	unsigned int *x;
	scanf("%d",&n);
	/* 依据阶乘位数申请动态数组 */
	x=(unsigned int*) malloc(wei(n)*sizeof(int));
	x[0]=1;
	for(i=2;i<=n;i++)
	{
		jinwei=0;
		for(j=1;j<=weishu;j++)
		{
			temp=x[j-1]*i+jinwei;
			if (temp>=1)
			{
				/* 以万为进制，提高运算速度 */
				x[j-1]=temp%10000;
				jinwei=temp/10000;
			}
		}
		while(jinwei)
		{
			weishu++;
			x[weishu-1]=jinwei%10000;
			jinwei/=10000;
		}
	}
	/* 先输出第一个数，防止首位出现0 */
	printf("%d",x[weishu-1]);
	/* 输出其余的数，因为万进制，需要补0 */
	for(j=weishu-2;j>=0;j--) printf("%04d",x[j]);
	/* 释放申请的内存 */
	free(x);
	system("pause");
	return 0;
}

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

哎，以前都是把下标规定好的，也就没注意这个问题，今天发现这个问题还是在做Vijos的时候。我提交一题的代码时才发现我的数组长度居然少打了一个0，也就是小了10倍。。。我正痛心疾首可怜我的AC率的时候，却发现评测机给出了“Accepted”。。。怀疑、欣喜、不解。。。问Google。。。

原来C/C++是不检查数组下标是否越界的？奇怪的事情。。。不检查下标是否越界可以有效提高程序运行的效率，因为如果你检查，那么编译器必须在生成的目标代码中加入额外的代码用于程序运行时检测下标是否越界，这就会导致程序的运行速度下降，所以为了程序的运行效率，C/C++才不检查下标是否越界。

自己写了一段检测程序测试这个问题，发现如果数组下标越界了，那么它会自动接着那块内存往后写。想了一下明白了，以前说不允许数组下标越界，并不是因为界外没有存储空间，而是因为界外的内容是未知的。也就是说如果界外的空间暂时没有被利用，那么我们可以占用那块内存，但是如果之前界外的内存已经存放了东西，那么我们越界过去就会覆盖那块内存，导致错误的产生。。。

这样就明白了，所以我们还是需要好好规划数组的下标滴。。。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

今天有同学问C语言中for循环里那个 i++ 和 ++i 是否有区别，我告诉他在for循环中是没有区别的，现在具体说一下 i++ 和 ++i 的区别。

我们先用while语句写一下 for(i=1;i<10;i++)

int i=0;
while (i<10){
printf("www.slyar.com");
i++;
}

再用while语句写一下 for(i=1;i<10;++i)

int i=0;
while (i<10){
printf("www.slyar.com");
++i;
}

可以看到，最后i的值都是10，所以在for循环里，i++ 和 ++i 是没有区别的，那么区别在哪里呢？

现在我们再看一段程序：

#include<stdio.h>
int main(){
int i,x;

i=1;
x=1;
x=i++; //这里先让X变成i的值1，然后i加1
printf("%d ",x);

i=1;
x=1;
x=++i; //这里先让i加1，然后让X变成i的值2
printf("%d ",x);

system("pause");
return 0;
}

试着运行一下这段程序，发现结果是 1 2 ，这就是 i++ 和 ++i 的区别了：

i++  ：先引用后增加

++i  ：先增加后引用

具体是什么意思呢？就是

i++  ：先在i所在的表达式中使用i的当前值，后让i加1

++i  ：让i先加1，然后在i所在的表达式中使用i的新值

我想这样说大家就应该明白了。。。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

大学有ACM竞赛，我在考虑要不要参加。今天有空上网我就跑去以前搞OI时常去的Vijos练手，只不过以前用的是Pascal语言，现在要用C语言，本来一开始是打算使用C++语言的，可是考虑到用C++而又不能使用那些强大的函数。。。我还是使用C语言吧。。。

做题很不顺利，找了4道基础题，提交了8次才全部AC，当然问题我也知道，是因为以前拿Pascal做得很顺手，突然换上C语言来做，有些东西会混乱，还是练习太少。。。以后没事就泡Vijos了，把基础题全部AC了转战USACO。。。

至于ACM，大一我应该不会参加，那个东西需要时间的积累。。。

下午听了大学第一堂高等数学课，讲函数，不是很难，不过留了N道作业题。。。我哭。。。

C语言。。。C语言。。。继续学习。。。