实习笔试——C语言（一）

周一的时候参加了一个C/C++的笔试，一共六道题，一道智力题，一道数据库题，六道程序题，这次先拿出程序题中的两道说下。
题目1：下面的代码输出什么结果？
     char *p ;
     strcpy( p, "Hello" );
     printf( "%sn", p );
     delete p;
     if( p != NULL )
         strcpy( p, "Ok" );
     printf( p );
这道题大概原本想考的是，当指针p被delete后的指向问题。但是，在复制字符串前，只声明了指针p，并没有初始化，即指针p没有指向任何一块内存，因此程序在运行阶段会报如下错误：Run-Time Check Failure #3 – The variable ‘p’ is being used without being initialized。
那么，排除掉这个未初始化的问题后，这道题接下来需要讨论的重点就是，指针被delete后的情形。（我原来以为delete是C中的关键字，结果delete是C++中的关键字，C中使用free()来释放内存）
以下是Bjarne Stroustrup’s C++ Style and Technique FAQ中的内容：
Why doesn't delete zero out its operand?
Consider
       delete p;
       // ...
       delete p;
If the ... part doesn't touch p then the second "delete p;" is a serious error that a C++ implementation cannot effectively protect itself against (without unusual precautions). Since deleting a zero pointer is harmless by definition, a simple solution would be for "delete p;" to do a "p=0;" after it has done whatever else is required. However, C++ doesn't guarantee that.
One reason is that the operand of delete need not be an lvalue. Consider:
       delete p+1;
       delete f(x);
Here, the implementation of delete does not have a pointer to which it can assign zero. These examples may be rare, but they do imply that it is not possible to guarantee that ``any pointer to a deleted object is 0.'' A simpler way of bypassing that ``rule'' is to have two pointers to an object:
       T* p = new T;
       T* q = p;
       delete p;
       delete q;  // ouch!
C++ explicitly allows an implementation of delete to zero out an lvalue operand, and I had hoped that implementations would do that, but that idea doesn't seem to have become popular with implementers.
If you consider zeroing out pointers important, consider using a destroy function:
       template<class T> inline void destroy(T*& p) { delete p; p = 0; }
Consider this yet-another reason to minimize explicit use of new and delete by relying on stadard library containers, handles, etc.
Note that passing the pointer as a reference (to allow the pointer to be zero'd out) has the added benefit of preventing destroy() from being called for an rvalue:
       int* f();
       int* p;
       // ...
       destroy(f());    // error: trying to pass an rvalue by non-const reference
       destroy(p+1);  // error: trying to pass an rvalue by non-const reference
在C++中delete指针前不用进行指针是否为空的判断，因为delete的实现已经做了这件事情！使用delete来delete已释放的指针是一个严重的错误，因此要在delete完一个指针后手动把它置空。因为delete空指针是安全的。
到此为止，C++的delete操作就基本清楚了，那么C中的free()操作呢，是否也和C++中的delete一样？把题目中的delete p改为free(p)，然后重新运行，得出的结论是，它们两者的操作和注意事项是完全相同的。所以，以后用C的内存释放free()完一个指针后，也需要手动把它置空。
另外一个小的问题，对于字符串指针p，打印其指向的字符串可以这样写printf(p)。我原先认为这样的写法肯定不可以，结果实验证明是可以的，具体原因的话，大概要找C标准库看看了。这种打印方法仅限于字符串指针，如果用于其它类型指针则报错，用于字符串数组则会打印出垃圾数据。而且，当指针为空时，该方法也会报错；但如果使用printf(“%s”, p)打印的话，会打印出非常人性化的“(null)”出来。因此我个人觉得还是写成后一种方式比较好。
题目2：随机数算法。
这道题目不是太会，上网查了些资料，CVS如下：
1、线性同余算法：
      现在用得最广泛的伪随机数产生算法就是所谓的线性同余算法。其随机数序列{Xn}由方程：Xn+1 = ( aXn + c ) mod m得到，其中m>0称为模数，0≤ a <m称为乘数，0≤c <m称为增量，0≤X0<m称为初始值或种子，当m、a、c、X0都是整数时，通过这个方程就能产生一系列[0，m)范围内的整数了。
很明显，对一个线性同余随机产生算法来说，最重要的是m、a、c的选择。我们希望产生的序列足够长，能包含[0，m)内所有的数，并且产生的数是随机的，最好能用32bit算术高效实现。于是乎为了有足够的空间产生足够长的队列，我们会使m足够大；为了使序列足够完整，足够像随机序列，我们会发现当m是素数，c为0时就可以使序列的周期（即序列不重复的长度）对于一定的a达到m-1；要能用32bit算术高效实现，我们的m当然不能超过32bit，幸好刚好有一个满足上述条件的很方便的素数2^31-1给我们用，于是产生函数就变成了Xn+1 = ( aXn) mod ( 2^31 – 1 )。在超过20亿个a的可选取值中，只有很少的几个可以满足上述所有条件，其中之一就是a = 7^5 = 16807。于是我们可以实现如下：
unsigned myrand()
     {
         return (seed = (seed * 10807L) & 0x7fffffffL);
     }
这种产生器得到了广泛的使用和比其它产生器都彻底的测验，其产生的随机数有在分布上有很好的特性，但是却不具备良好的不可预测性。所以我们在使用时往往会以系统时钟（模m）或系统时钟与随机数的和（模m）作为种子来重新启动序列，这也是现在绝大多数随机数产生器的做法。
另一种产生伪随机数序列的方法就是使用加密逻辑，通过加密算法的雪崩效应，输入的每一位改变就会造成输出的巨大改变，并且假如密钥被妥善保存的话从序列中前面的数推出后面的数在计算上是不可行的，于是我们可以使用一个简单的累加器作为输入，得到的随机序列可以直接使用（当然也可以把系统时间等等因素考虑进去作为输入来产生更随机的序列，不过这通常是没有必要的），这种方法常常用来产生会话密钥或是现时。具体采用的加密逻辑和运算方式有很多，这里就不一一介绍了，大家感兴趣可以找本密码学的书来看看。
在密码学领域里比较流行的一种产生安全的伪随机数的方法是BBS产生器，它用其研制者的名字命名（Blum Blum Shub，不是我们经常灌水的那个BBS），它的密码编码强度据说具有最强的公开证明。首先，我们找两个大素数p和q，要求它们被4除都余3，令n = p×q，再选择一个随机数s，使s与n互素，然后我们通过如下算法产生一系列比特Bi：
X0 = (s^2)mod n，
for i = 1 to ∞
Xi = (Xi-1^2)mod n
Bi = Xi mod 2
每次迭代都只取出最低位的bit。可以看出BBS产生随机数的过程非常复杂，运算量很大，嗯，这就是为安全性付出的代价。
2、平方截取法：
找一个大数,如123456789
平方,得15241578750190521
取中段157875019
把它平方,得24924521624250361
取中段452162425
平方.......
这样能得一个伪随机序列
123456789
157875019
452162425 
3、C语言算法示例：
/*1.从同一个种子开始*/
#include <stdio.h>
#include <conio.h>
static unsigned long int next=1;
int rand0(void)
{
next=next*1103515245+12345;
return (unsigned int)(next/65536)%32768;
}
int main(void)
{
int count;
for(count=0;count<5;count++)
    printf("%hdn",rand0());
getch();
return 0;
}

/*2.重置种子*/
#include <stdio.h>
#include <conio.h>
static unsigned long int next=1;

int rand1(void)
{
next=next*1103515245+12345;
return (unsigned int)(next/65536)%32768;
}

void srand1(unsigned int seed)
{
next=seed;
}

int main(void)
{
int count;
unsigned int seed;
printf("please input seed:");
scanf("%u",&seed);
srand1(seed);
for(count=0;count<5;count++)
    printf("%hdn",rand1());
getch();
return 0;
}

/*3.利用利用时钟产生种子
ANSI C程序库提供了rand()函数来产生随机数；
ANSI C程序库提供了srand()函数来产生种子；
ANSI C程序库提供了time()函数返回系统时间。
*/
#include <time.h>
#include <stdio.h>
#include <dos.h>
#include <conio.h>
#include <stdlib.h>
int main(void)
{
   int i;
   time_t t;
   clrscr();
   t = time(NULL);
   srand((unsigned) t);
   for(i=0; i<10; i++) printf("%dn", rand()%10);
   getch();
   return 0;
}
随机数算法应该还有很多种，回头找些书看看再说。

PS: 本篇文章作者为chenhao727，由于技术原因造成作者显示错误，请您谅解，谢谢。