第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 | 1 //计算一段程序运行的时间 |
1 | 1 //计算整个程序运行的时间 |
1 | //两个写在一起 |
部分内容引自: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这样的重定向方式读写文件)