第一讲 程序设计基础

程序的构成

1. 只要会循环和判断，就会编程了！
2. 关于函数？
   将统一的操作封装到一起，方便使用
3. 关于数组和指针？
   对数据的存储操作

4. 关于输入输出？
   由硬件提供简单的指令

5. 程序的主要意义：
   通过大量的重复执行某些指令，能够快速得到人力无法在有生之年得出的结果。

   1. 从上亿条信息中，找出规律：“买婴儿尿布的人多半会买啤酒”。
   2. 判断2^57885161 - 1是否为素数。
   3. 使用“必胜策略”下五子棋

程序的编写过程

• 设计：由总自分

• 编码：由总自分，由分自总

  例一：有一机器人，有4种操作指令，每类指令机器人会执行一系列操作（详细略）。编写程序，模拟用户输入指令后，机器人执行操作的过程。
  例二：公司内部有多级职务，每一级职务的任务就是把所接收的任务拆分并交给下一级，直到最底层职员。请编写程序模拟该过程。

ACM竞赛中涉及的输入方式

• 读入一个数n,并读入接下来的n个数据

  5 1 2 3 4 5

  scanf(“%d”, &n);
  for (i = 0; i < n; ++i) {
  scanf("%d", &arr[i]);
  }

• 按行读入数据,需要能够确定行内数据的个数

  1 2 3 4 5
  6 7 8

  char str[100];
  while(gets(str)) {
  int i = 0, l, p = 0;
  sscanf(str+p, “%d%n”, &arr[i++], &l) != EOF) {
      p += l;
  }
  }

• 读入文本中所有的以<>括起来的内容

  < html>< body>kasjdflkja<1>sdas<2>s

  char ans[]
  int cnt = 0;
  while (scanf("%c", &ch) != EOF) {       //输入不为文件末尾
      if (ch == '<') {
          while (1) {
              scanf("%c", &ch);
              if (ch == '>') {break;}
           else {ans[cnt++] = ch;}
          }
      }
  } //边读边处理

  char buf[10000];
  while (scanf(”%*[^<]<%[^>]>", buf) != EOF) {
  …                                               
  }

• 读入一个数字
  

  scanf (“%d”, &num);
  scanf (“%f”, &num);
  scanf (“%lf”, &num);
  scanf (“%s”, num);

• 读入时间

  2014_01_02 12:30:45

  int year, month, date, h, m, s;
  scanf("%d-%d-%d %d:%d:%d", &year, &month, &date, &h, &m, &s);

• 依次读入多个字符,字符以空格隔开

  a f d

  scanf("%c%*c%c%*c%c", &a, &b, &c);
  //%*c忽略一个字符

竞赛中使用的输入方法

• c++方式未来再介绍，如：iostream, sstream之流
• getchar() getch()，在竞赛中禁用！！！！
• gets()，用于读入整行数据。(结束标志为 回车'\n')

• scanf()，用于读入以不可见字符分隔的数据结束

  %d %I64d或%lld
  %lf 或 %f    
  %s %n
  %c 尽量少用
  %[] 正则表达式
  %*c

输入结束方式

• 根据题目给出的数据组数判断

  • 输入第一行为k,表示有k组测试数据

    int k;
    scanf("%d", &k);
    while(k--){
        scanf(XXX);
        ...
    }

  • 输入仅有一组数据

    scanf(XXX);

• 读入直到文件结束

  • 输入包含多组数据, 每数组据包含XXX内容
    如 每组测试数据包括 两个数 m n. 0 0表示输入结束

    while(scanf("%d%d", &x, &y) && !(x==0 && y == 0)){
        ...
    }

  • 输入以EOF结束

    while(scanf(...)!=EOF);

竞赛中使用的输出方法

• 一般情况下，仅用printf与cout进行输出
• printf与cout不能混用
• 仅用printf进行输出
  %d与%lld
  %f与%lf
  %s与%c
  %3.3lf
  %03d
  %5s

• 输出时间，格式要求：yyyy-MM-dd hh:mm:ss

  2013-01-01 01:01:01

  printf(“%04d-%02d-%02d %02d:%02d:%02d\n”, …);

• 小数点后3位，四舍五入
  printf(“%.3lf\n”, f);

• 小数点后3位，进一法
  printf(“%.3lf\n”, f+0.0005);

字符串的使用

字符串的读入：scanf , gets , fgets.

• 结束标志
  scanf()的结束标志为 回车'\n',Tab'\t' 和空格' '.
  fgets(), gets()的结束标志为 回车'\n'.

  //对于输入文本 "hello world!" 回车.
  scanf("%s", string); // srting的内容为 "hello"
  gets(string);        // string的内容为 "hello world"

• 回车字符\n
  scanf从stdin流，即终端输入，遇回车‘\n’停止，但‘\n’还在输入流中。
  gets, fgets 输入时会连同回车'\n'一同读入,但不会存入数组中.

  //对于输入文本 "hello" 回车 'c' 回车.
  scanf("%s", str); ch = getchar();   //ch读入的字符为 '\n'.
  gets(str); ch = getchar();          //ch读入的字符为 'c'.

• 安全

  gets使用时要注意，gets函数格式gets（a）；不检查内存空间，容易溢出。

  fgets相对gets而言要安全点，格式fgets（*s，size，stdin），*s为地址，size为要读取的长度，stdin是从终端读取。

常用字符串函数

strlen(测量字符串长度)
strstr(一个字符串中搜索另一个字符串)
strcmp(字符串比较)
strcpy与strncpy(字符串的复制)
sscanf与sprintf(从字符串格式化读入,向字符串格式化写入)
memset 这是一个内存初始化函数，初始化字符串可用初始值只能为0 和 -1

memset(str,0, sizeof(str));

atoi, itoa, atof, atol，禁用！！！！！

高精度计算

为什么要使用高精度?

计算下面这个结果：

32767+32767

计算下面这个结果:

327673276732767+327673276732767

计算下面这个结果：

327673276732767327673276732767 + 327673276732767327673276732767

整数(int)数据范围为-2^32~2^32-1,长整数（long long）数据范围为-2^64~2^64-1,如果十进数超过20位就不能胜任了。这时就要用到高精度数的运算了。

高精度储存

int w[100];一般为w[0]存储该数的位数，w[1]存个位，w[2]存十位，….
如整数“120”，按高精度数存储：w[0]=3;w[1]=0;w[2]=2;w[3]=1。
注意这里是倒着保存数的。这样做的目的在于进行运算时方便数位对齐。
但由于是高精度数的运算可以多次用到，所以我们定义成函数形式方便使用。为了让函数能直接返回值，所以可以定义成结构体。

struct hp
{
  int w[10005];//   w[0]用于存储这个数的位数
};

高精度计算

1. 加法

高精度数相加实际上就是模拟我们自己计算加法的过程。
步骤 1.对应位相加 2.进位.高精度加法类似

hp jia(hp a, hp b)
{
    hp c;
    memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
    c.w[0] = a.w[0] > b.w[0] ? a.w[0] : b.w[0];//初步估算位数
    for(int i = 1; i <= c.w[0]; i++){
        c.w[i] = a.w[i]+b.w[i];    //对应位相加
    }
    for(int i = 1; i <= c.w[0]; i++){
        if(c.w[i] >= 10){
            c.w[i] %= 10;
            c.w[i+1] += 1;  //进位
        }
    }
    if(c.w[c.w[0]+1] != 0)c.w[0]++;
    return c;
}

2. 乘法

高精度乘法也是模拟计算乘法
步骤 1.对应位相乘 2.进位

hp cheng(hp a, hp b)
{
    hp c;
    memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
    c.w[0] = a.w[0] + b.w[0] - 1;   //初步估算结果的位数
    for(int i = 1; i <= a.w[0]; i++){
        for(int j = 1; j <= b.w[0]; j++){
            c.w[i+j-1] += a.w[i] * b.w[j];  //每一位相乘
        }
    }
    for(int i = 1; i <= c.w[0]; i++){
        if(c.w[i] >= 10){
            c.w[i+1] += c.w[i] / 10;
            c.w[i] %= 10;
        }
    }
    if(c.w[c.w[0]+1] != 0)c.w[0]++; // 计算精确位数
    return c;
}

高精度的输出

高精度的输出方式为从最高位输出到最低位

void print(hp c)
{
    for(int i = c.w[0]; i >= 1; i--){   //输出
    printf("%d", c.w[i]);
    }
    printf("\n");
}

高精度的输入

因为高精度的数已经不能用int 和 long long来储存.所以自然也不能用scanf("%d%lld")来输入.
输入方法为:
1. 将高精度数储存到字符串中
2. 把字符串转化为 struct hp 变量,用于之后的计算

输入数据 123456789123456789

hp input()
{
    hp a;
    memset(a.w, 0, sizeof(a.w))
    char str[100];
    scanf("%s", str);       //将数字用数组保存
    int len = strlen(str);
    a.w[0] = len;
    for(int i = len-1; i >= 0; i--){
        a.w[len- i] = str[i] - '0';     //通过位置关系构建高精度数.
    }
    return a;
}

第一章的内容就讲完啦.来,完成我们的第一题!!
Bull Math
Input

输入包括两行 每一行是一个不超过40位的数字

Output

输出这两个数的乘积

代码:

#include <cstdio>
#include <cstring>
struct hp
{
    int w[100];
};
hp cheng(hp a, hp b)
{
    hp c;
    memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
    c.w[0] = a.w[0] + b.w[0] - 1;   //初步估算结果的位数
    for(int i = 1; i <= a.w[0]; i++){
        for(int j = 1; j <= b.w[0]; j++){
            c.w[i+j-1] += a.w[i] * b.w[j];  //每一位相乘
        }
    }
    for(int i = 1; i <= c.w[0]; i++){
        if(c.w[i] >= 10){
            c.w[i+1] += c.w[i] / 10;
            c.w[i] %= 10;
        }
    }
    if(c.w[c.w[0]+1] != 0)c.w[0]++; // 计算精确位数
    return c;
}
void print(hp c)
{
    for(int i = c.w[0]; i >= 1; i--){   //输出
    printf("%d", c.w[i]);
    }
    printf("\n");
}
hp input()
{
    hp a;
    memset(a.w, 0 ,sizeof(a.w));
    char str[100];
    scanf("%s", str);
    int len = strlen(str);
    a.w[0] = len;
    for(int i = len-1; i >= 0; i--){
        a.w[len- i] = str[i] - '0';
    }
    return a;
}
int main()
{
    hp a, b;
    a = input();    // 输入a
    b = input();    // 输入b
    hp c = cheng(a, b);     // 计算 a * b
    print(c);   //输出结果c
    return 0;
}