算法竞赛入门第4章

函数和递归

4-1 在算法竞赛中，总是让main函数返回0. main函数是整个程序的入口，有一个其他程序来调用这个main函数，如操作系统，IDE，调试器甚至自动评测系统。这个0代表正常结束，即返回给调用者。
4-2 为了使用方便，往往用typedef struct {域定义}类型名;的方式定义一个新类型名。这样，就可以像原生数据类型一样使用这个自定义类型。
4-3 对复杂表达式进行化简，不仅可以减少计算量，还能减少甚至避免中间结果溢出。
4-4 floor(sqrt(n) + 0.5) 如果sqrt将某个本应是整数的值变成了xxx.99999，也将得到修正；但是如果直接写sqrt(n)，.99999会被直接截掉。
4-5 函数的形参和函数内声明的局部变量都是该函数的局部变量。无法访问其它函数的局部变量。局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放，其中的值无法保留到下次使用。在函数外声明的变量是全局变量，可以被任何函数使用。操作全局变量有风险，应谨慎使用。
4-6 C语言调用栈来描述函数之间的调用关系。调用栈由栈帧组成，每个栈帧对应一个未运行完的函数。
4-7 C语言的变量都是放在内存中的，而内存中的每个字节都有一个称为地址的编号。每个变量都占有一定数目的字节（可用sizeof运算符得到），其中第一个字节的地址称为变量的地址。
4-8 用int* a声明的变量a是指向int型变量的指针。赋值a=&b的含义是把变量b的地址存放在指针a中，表达式*a代表a指向的变量，既可以放在赋值符号的左边也可以放在赋值符号的右边。
4-9 以数组为参数调用函数时，实际上只有数组首地址传递给了函数，需要另加一个参数表示元素个数。把数组作为指针传递给函数时，数组内容是可以修改的。
4-10 C语言支持递归，即函数可以直接或间接地调用自己。但是要注意为递归函数编写终止条件，否则将产生无限递归。
4-11 在C语言的函数中，调用自己和调用其他函数并没有任何本质的区别，都是新建栈帧，传递参数并修改当前代码行。函数执行完毕后删除栈帧，处理返回值并修改当前代码行。
4-12 “段”是指二进制文件内的区域，所有某种特定类型信息都被保存在里面。可以用size命令得到可执行文件中各个段的大小。在可执行文件中，
正文段（Text）用于存储指令，数据段（Data）用于存储已初始化的全局变量，BSS段（BSS）用于存储未赋值的全局变量所需的空间。
4-13 调用栈并不存储在可执行文件中，而是运行时创建。调用栈所在的段称为堆栈段。和其他段一样，堆栈段也有自己的大小，不能被越界访问，否则就会出现段错误。
4-14 栈空间的大小和操作系统有关。在Linux中，栈大小并没有存储在可执行文件中，只能用ulimit命令修改；在Windows系统中，栈大小存储在可执行程序中，用gcc编译时可以通过-Wl,--stack=<byte count>指定。
4-15 把较大的数组放在main函数外的原因：局部变量是放在调用栈中的，调用栈位于堆栈段。所以栈溢出不一定是递归调用太多，也可能是局部变量太大。只要总大小超过了允许的范围，就会产生栈溢出。
uva 133 救济金发放 约瑟夫环问题

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int n,k,m;
int a[20];
//从p开始，每次走d，走t步。返回最终走到的位置
int step(int p, int d, int t)
{
    while(t--)
    {

        if(p+d<=0) p=p+d+n;
        else p=(p+d)%n;
        if(p==0) p=n;  //p+d==n情况
        //p=(p+d+n-1)%n+1; //两种写法等同
        if(a[p]==0)
            t++;  //相当于这一步白走
    }
    return p;
}

int main()
{
    while(cin>>n>>k>>m && (n+k+m)!=0)
    {
        for(int i=0;i<=n;i++)
            a[i]=i;
        int p1=n, p2=1;
        int lef=n; //还剩下的人数
        while(lef)
        {
            p1=step(p1,1,k);
            p2=step(p2,-1,m);
            printf("%3d",p1);
            lef--;
            if(p2!=p1)
            { printf("%3d", p2); lef--;}
            a[p1]=a[p2]=0;
            if(lef)
                cout<<",";
        }
        cout<<endl;
    }
    return 0;
}

uva213 信息解码 此题对多行字符的处理以及二进制的处理恰到好处

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

/*
 *code[len][value]保存编码长度为len,编码对应的十进制值为value
 *的01编码对应的编码头的字符
*/
int code[8][1<<7];

//多处用到跨行读字符
int readchar() {
    for(;;)
    {
        int ch = getchar();
        if(ch!='\n' && ch!='\r') return ch; //一直读到非换行符
    }
}

int readcodes()
{
    memset(code,0,sizeof(code));
    code[1][0] = readchar();   //注意要用readchar()

    for(int len=2;len<=7;len++){
        for(int i=0; i< (1<<len)-1; i++){
            int ch=getchar();
            if(ch==EOF) return 0; //如果输入结束会读到EOF
            if(ch=='\n' || ch=='\r') return 1;  //编码头读完
            code[len][i]=ch;
        }
    }
    return 1;
}

int readint(int c)  //读到一个字符*2
{
    int v=0;
    while(c--) v=v*2 + readchar() - '0'; //编码文本有多行，要用readchar()
    return v;
}

int main()
{
    while(readcodes())  //无法读取更多编码头时退出
    {
        //开始解码
        for(;;){
            int len =readint(3); //读取前3个数字组成的编码长度
            if(len == 0) break;
            for(;;){
                int v=readint(len);
                if(v==(1<<len)-1) break;
                putchar(code[len][v]);
            }
        }
        putchar('\n');
    }
    return 0;
}