[关闭]
@Chobi15 2015-07-18T12:02:58.000000Z 字数 5365 阅读 1591

第一讲 程序设计基础-1

ACM简介

ACM程序设计大赛是大学级别最高的脑力竞赛,素来被冠以"程序设计的奥林匹克"的尊称。大赛自1970年开始至今已有40年历史,是世界范围内历史最悠久、规模最大的程序设计竞赛。比赛形式是:经过校级和地区级选拔的参赛组,于指定的时间、地点参加世界级的决赛,由3个成员组成的小组应用一台计算机解决6到8个生活中的实际问题。竞赛结束后,参赛各队以解出问题的多少进行排名,若解出问题数相同,按照总用时的长短排名。

Online Judge

Online Judge系统(简称OJ)是一个在线的判题系统。用户可以在线提交程序多种程序(如C、C++、Pascal)源代码,系统对源代码进行编译和执行,并通过预先设计的测试数据来检验程序源代码的正确性。

今后我们做题都会在OJ上面进行,以下是几个推荐的OJ网址
1. 北京师范大学OJ(BNUOJ)集训的题目都会挂在这个OJ上
2. 北京大学OJ(POJ)
3. 杭州电子科技大学OJ(HDUOJ)
4. CODEFORCES(俄罗斯的一个OJ,基本每周都会举行个人赛)

国内外OJ还有很多,这里不进行一一列举

ACM题目

题目包含的内容

  1. 题目描述
  2. 输入格式
  3. 输出格式要求(输出格式必须完全符合题目要求)
  4. 样例输入(给你一组测试数据,便于你理解题意)
  5. 样例输出
  6. 提示

程序的提交

当你完成题目后,点击submit(提交),选择你使用编译语言(C++,C, Java等),在代码栏内粘贴上你的代码,点击submit按钮,就提交了你的代码了.

试着完成自己的第一道题吧:A + B Problem

程序的运行结果

一个用户提交的程序在Online Judge系统下执行时将受到比较严格的限制,包括运行时间限制,内存使用限制和安全限制等。用户程序执行的结果将被Online Judge系统捕捉并保存,然后再转交给一个裁判程序。该裁判程序或者比较用户程序的输出数据和标准输出样例的差别,或者检验用户程序的输出数据是否满足一定的逻辑条件。

最后系统返回给用户一个状态:
1. 通过(Accepted,AC)
2. 答案错误(Wrong Answer,WA)
3. 超时(Time Limit Exceed,TLE)
4. 超过输出限制(Output Limit Exceed,OLE)
5. 超内存(Memory Limit Exceed,MLE)
6. 运行时错误(Runtime Error,RE)
7. 格式错误(Presentation Error,PE)
8. 无法编译(Compile Error,CE )

注意: 比赛中每一次提交若未能AC,一般是要罚时20分钟的,所以提交请慎重

ACM竞赛中涉及的输入方式

竞赛中使用的输入方法

输入结束方式

竞赛中使用的输出方法

字符串的使用

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

常用字符串函数

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

  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。
注意这里是倒着保存数的。这样做的目的在于进行运算时方便数位对齐。
但由于是高精度数的运算可以多次用到,所以我们定义成函数形式方便使用。为了让函数能直接返回值,所以可以定义成结构体。

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

高精度计算

1. 加法

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

  1. hp jia(hp a, hp b)
  2. {
  3. hp c;
  4. memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
  5. c.w[0] = a.w[0] > b.w[0] ? a.w[0] : b.w[0];//初步估算位数
  6. for(int i = 1; i <= c.w[0]; i++){
  7. c.w[i] = a.w[i]+b.w[i]; //对应位相加
  8. }
  9. for(int i = 1; i <= c.w[0]; i++){
  10. if(c.w[i] >= 10){
  11. c.w[i] %= 10;
  12. c.w[i+1] += 1; //进位
  13. }
  14. }
  15. if(c.w[c.w[0]+1] != 0)c.w[0]++;
  16. return c;
  17. }

2. 乘法

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

  1. hp cheng(hp a, hp b)
  2. {
  3. hp c;
  4. memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
  5. c.w[0] = a.w[0] + b.w[0] - 1; //初步估算结果的位数
  6. for(int i = 1; i <= a.w[0]; i++){
  7. for(int j = 1; j <= b.w[0]; j++){
  8. c.w[i+j-1] += a.w[i] * b.w[j]; //每一位相乘
  9. }
  10. }
  11. for(int i = 1; i <= c.w[0]; i++){
  12. if(c.w[i] >= 10){
  13. c.w[i+1] += c.w[i] / 10;
  14. c.w[i] %= 10;
  15. }
  16. }
  17. if(c.w[c.w[0]+1] != 0)c.w[0]++; // 计算精确位数
  18. return c;
  19. }

高精度的输出

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

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

高精度的输入

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

输入数据 123456789123456789

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

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

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

Output

输出这两个数的乘积

代码:

  1. #include <cstdio>
  2. #include <cstring>
  3. struct hp
  4. {
  5. int w[100];
  6. };
  7. hp cheng(hp a, hp b)
  8. {
  9. hp c;
  10. memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
  11. c.w[0] = a.w[0] + b.w[0] - 1; //初步估算结果的位数
  12. for(int i = 1; i <= a.w[0]; i++){
  13. for(int j = 1; j <= b.w[0]; j++){
  14. c.w[i+j-1] += a.w[i] * b.w[j]; //每一位相乘
  15. }
  16. }
  17. for(int i = 1; i <= c.w[0]; i++){
  18. if(c.w[i] >= 10){
  19. c.w[i+1] += c.w[i] / 10;
  20. c.w[i] %= 10;
  21. }
  22. }
  23. if(c.w[c.w[0]+1] != 0)c.w[0]++; // 计算精确位数
  24. return c;
  25. }
  26. void print(hp c)
  27. {
  28. for(int i = c.w[0]; i >= 1; i--){ //输出
  29. printf("%d", c.w[i]);
  30. }
  31. printf("\n");
  32. }
  33. hp input()
  34. {
  35. hp a;
  36. memset(a.w, 0 ,sizeof(a.w));
  37. char str[100];
  38. scanf("%s", str);
  39. int len = strlen(str);
  40. a.w[0] = len;
  41. for(int i = len-1; i >= 0; i--){
  42. a.w[len- i] = str[i] - '0';
  43. }
  44. return a;
  45. }
  46. int main()
  47. {
  48. hp a, b;
  49. a = input(); // 输入a
  50. b = input(); // 输入b
  51. hp c = cheng(a, b); // 计算 a * b
  52. print(c); //输出结果c
  53. return 0;
  54. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注