第1日—Lgorithm-learning

数据类型范围(int,long long int,用于解决数值溢出问题)

有符号整数类型

类型名称 字节数 取值范围
signed char 1 -2^7(-128) ~ 2^7-1(127)
short int 或 short 2 -2^15(-32 768) ~ 2^15-1(32 767)
int 4 -2^31(-2 147 483 648) ~ 2^31-1(2 147 483 647)
long int 或 long 4 -2^31(-2 147 483 648) ~ 2^31-1(2 147 483 647)
long long int 或 long long 8 -2^63(-9.2233720368548e+18) ~ 2^63-1(9.2233720368548e+18)

无符号整数类型

类型名称 字节数 取值范围
unsigned char 1 0 ~ 2^8-1(255)
unsigned short int 或 unsigned short 2 0 ~ 2^16-1(65 535)
unsigned int 4 0 ~ 2^32-1(4 294 967 295)
unsigned long int 或 unsigned long 4 0 ~ 2^32-1(4 294 967 295)
unsigned long long int 或 unsigned long long 8 0 ~ 2^64-1(1.844674407371e+19)

浮点类型

类型名称 字节数 取值范围
float 4 -/+3.4e38(精确到6位小数)
double 8 -/+1.7e308(精确到15位小数)
long double 12 -/+1.19e4932(精确到18位小数)

原文请查看:https://blog.csdn.net/weixin_42856843/article/details/81989737

计算时输入溢出

例如:P22 例题2-2 3n+1

解题方法:将 int 改为 long long / long long int

(注意:在使用long long int /long long 时输入应当改为%lld)

计算时结果溢出

例如:P25 例题2-4 阶乘之和

解题方法:每步计算都对n进行取余,每步取模运算

(要计算只包含加法,减法和乘法的整数表达式除以正整数n的余数,可以在每步计算之后对n取余,结果不变

常量定义

const int MOD = 1000000; #引自P24 例题2-4

改善程序的可读性,方便修改

如何迅速判断程序是否溢出

通过“输入中间变量”法来验证

计时函数clock()

头文件:#include<time.h>

输出:printf(“Time used = %.2f\n”,(double)clock() / CLOCKS_PER_SEC);

说明:该函数返回程序目前为止运行的时间,这个时间除以常数CLOCKS_PER_SEC之后得到的值以“秒”为单位。

clock()计时函数

clock()是C/C++中的计时函数,而与其相关的数据类型是clock_t。在MSDN中,查得对clock函数定义如下:
clock_t clock(void) ;
简单而言,就是该程序从启动到函数调用占用CPU的时间。这个函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单元(clock tick)数,在MSDN中称之为挂钟时间(wal-clock);若挂钟时间不可取,则返回-1。其中clock_t是用来保存时间的数据类型。
在time.h文件中,我们可以找到对clock_t()的定义:

#ifndef _CLOCK_T_DEFINED

typedef long clock_t;

#define _CLOCK_T_DEFINED
#endif

很明显,clock_t是一个长整形数。在time.h文件中,还定义了一个常量CLOCKS_PER_SEC,它用来表示一秒钟会有多少个时钟计时单元,其定义如下:
#define CLOCKS_PER_SEC ((clock_t)1000)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 1 //计算一段程序运行的时间
2 #include<iostream>
3 #include<ctime>
4 using namespace std;
5 int main()
6 {
7 clock_t startTime,endTime;
8 startTime = clock();//计时开始
9 for (int i = 0; i < 2147483640; i++)
10 {
11 i++;
12 }
13 endTime = clock();//计时结束
14 cout << "The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
15 system("pause");
16 return 0;
17 }
18 //注释在:VC++6.0中可以用CLK_TCK替换CLOCKS_PER_SEC。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 1 //计算整个程序运行的时间
2 #include<iostream>
3 #include<time.h>
4 using namespace std;
5 int main()
6 {
7 for (int i = 0; i < 2147483640; i++)
8 {
9 i++;
10 }
11 cout << "The run time is:" << (double)clock() /CLOCKS_PER_SEC<< "s" << endl;
12 system("pause");
13 return 0;
14 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   //两个写在一起
1 #include<iostream>
2 #include<ctime>
3 using namespace std;
4 int main()
5 {
6 clock_t startTime,endTime;
7 for (int i = 0; i < 2147483640; i++)
8 {
9 i++;
10 }
11 startTime = clock();//计时开始
12 for ( i = 0; i < 2147483640; i++)
13 {
14 i++;
15 }
16 endTime = clock();//计时结束
17 cout << "The run time is:" <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
18 cout << "The run time is:" << (double)clock() /CLOCKS_PER_SEC<< "s" << endl;
19 system("pause");
20 return 0;
21 }

部分内容引自:https://www.cnblogs.com/didiaodidiao/p/9194702.html

C语言输出格式要求

例如题目让输出 025,而有时候系统默认输出 25,此时我们可以用 %03d或%.3d 使 25 输出为 025。

算法竞赛中的输入输出框架

例:P27 例题 2-5 数据统计

由于整数的个数是不确定的,我们得解决这个问题。

直接上代码:while(scanf("%d",&x) == 1)

解释:scanf函数是有返回值的,它返回的是成功输入的变量个数,当输入结束时,scanf函数无法再次读取x,将返回0.

但是细心的小伙伴运行程序后肯定会发现按下“Enter”键后未显示结果。并不是程序运行太慢,其实程序是在等待输入。scanf函数的输入格式:空格,TAB和回车符都是无关紧要的,所以按下Ente键并不意味着输入的结束。那么我们该如何告诉程序输入结束了呢?

提示:在Windows下,输入完毕后先按下Enter键,再按Ctrl+Z键,最后再按Enter键,即可结束输入。在Linux下,输入完毕后按Ctrl+D键即可结束输入。

文件输入输出讨论

​ 相信在上一节我提到的scanf函数的使用方式后,大家也会发现每次调试程序的时候并不方便,尤其是上面的例题中程序值是溢出的,那也就意味着我们会进行多次的调试。

​ Good means:用文件——把输入数据保存在文件中,输出数据也保存在文件中。这样,事先把输入的数据保存在命令行中,就不必每次重新输入了;

使用方法

最简单的方法是使用输入输出重定向,只需在main函数的入口处加入以下两条语句:

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

上面两条语句使得scanf从文件input.txt读入,printf写入文件output.txt。

(注意:参赛之前仔细阅读文件读写的相关规定,有的竞赛只允许访问文件,但不允许用freopen这样的重定向方式读写文件)