算法竞赛入门经典算法实现pdf,算法笔记和算法竞赛入门经典
目录
第2章循环结构编程2.1对于循环程序2-1输出1,2,3,…,n的值例2-1 aabb。2-2 7744题(1) 2-3 7744题(2)
2.2循环结构编程例题2-2 3n 1问题程序2-4 3n 1问题例题2-3阶乘和。程序2-5的阶乘和(1)程序2-6的阶乘和(2)
2.3文件操作示例2-4数据统计。程序2-7数据统计(错误)程序2-8数据统计(重定向版)程序2-9数据统计(fopen版)2.4总结与练习2.4.1输出技巧2.4.2浮点陷阱2.4.3输入输出2 . 4 . 5 64位整数中的ACM主题2.4.4 C I/O 1 .ACM主题特征2。基本输入3。基本产出4。初学者常见问题5。5提交代码后的提示。OJ 6。学习风格2.4.6总结2.4.7练习2-1位数练习2-2水仙花练习2-3韩信(韩熙)练习2-4倒三角形扩展1:用for循环编程绘制下图:扩展2:输出下图:扩展3:输出下图:扩展4:输出下图:练习2-5统计(stat)[分析1][分析2:统计1][分析3:统计2的变式]练习2-6和声、练习2-7逼近、练习2-8子序列的子序列、练习2-9
第二章循环结构编程【相关章节的学习内容】
2.1for循环2.2循环结构编程2.3文件操作
2.4总结和练习
[学习目标]
(1)掌握for循环的使用;
(2)掌握while循环的使用;
(3)学会使用计算器和累加器;
(4)通过输出中间结果学会调试;
(5)学会用计时功能测试程序效率;
(6)通过重定向学习读写文件;
(7)通过fopen学习如何读写文件;
(8)了解算法竞赛对文件读写方法和命名的严格性;
(9)记住变量赋值前的值是不确定的;
(10)学会使用条件编译指令构建本地运行环境。
[学习要求]
掌握for循环的使用;掌握while循环的使用;掌握fopen、fclose、fprintf、fscanf等几种常用的文件操作库函数。
[学习总结]
在一些程序中,有些语句需要重复执行。简单的复制N条相同的语句会让程序变得不合理的冗长,所以高级语言提供了循环控制语句,支持程序重复执行某个程序。相关语句有:for、while、do while、break、continue等。
您可以从文件中读取数据或向文件中写入数据。在读写文件之前,首先打开文件。读写文件后,关闭文件。C/C提供了一系列的库函数,在stdio.h中声明,用于文件操作。下面是一些常用的文件操作库函数fopen、fclose、fprintf、fscanf等。
【学习的重点和难点】
学习重点:
(1)掌握for循环的使用;
(2)掌握while循环的使用;
(3)掌握单据的操作;
(4)条件编译。
学习困难:
(1)掌握for循环的使用;
(2)掌握while循环的使用;
[课时表(共2小时)]
2.1for循环2.2循环结构编程2.3文件操作2.4总结和练习
2.1 for循环
请使用for循环输入正整数N并打印1,2,3,…,10,每一行占一行。该过程如下:
程序2-1输出1,2,3,…,n的值#include。
int main(){
int i,n;
scanf(%d ,
for(I=1;我我)
printf(%d\n ,I);
返回0;
}提示2-1:for循环的格式:for(初始化;条件;调节)循环体;
技巧2-2:虽然for循环重复执行相同的语句,但是这些语句的执行效果往往每次都不一样。
技巧2-3:写程序时,要特别注意“当前行”的跳转和变量的变化。
使用for循环,可以解决一些简单的问题。
实施例2-1 aabb。以aabb形式输出所有四位平方数(即前两位相等,后两位相等)。
[分析]
分支和循环结合在一起的时候特别强大:你可以枚举所有可能的aabb,然后判断它们是否是完全正方形。请注意,a的范围是从1到9,但b可以是0。主要程序如下:
for(a=1;答答)
for(b=0;b b)
If(aabb是完整的平方数)printf(%d\n ,AABB);注意:(1)以上不是真实的程序。这种代码称为伪代码(psedocode)。
(2)上面使用了循环的嵌套:for循环的循环体本身就是一个循环。技巧2-4:建议使用伪代码来思考和描述算法。
技巧2-5:将伪代码改写成代码时,一般情况下,选择较容易完成的任务先完成。
2-2 7744个问题(1)#包括
#包括
int main(){
int a,b,n;
双m;
for(a=1;答答)
for(b=0;b b ) {
n=a * 1100 b * 11
m=sqrt(n);
if(floor(m 0.5)==m) printf(%d\n ,n);
}
返回0;
}说明:函数floor(x)返回x的整数部分,之所以用floor(m 0.5)==m,是因为浮点数的运算(和函数)可能会有错误。
提示2-6:浮点运算可能会有错误。比较浮点数时,应考虑浮点误差。
四位完整平方数的另一个思路是枚举平方根x,这样可以避免平方根运算。
2-3 7744个问题(2)#包括
int main(){
int x,n,hi,lo;
for(x=1;x ) {
n=x * x
如果(n 1000)继续;
如果(n 9999)破;
hi=n/100;
lo=n % 100
if(hi/10==hi洛/10==lo) printf(%d\n ,n);
}
返回0;
}描述:本程序中使用了break和continue语句。Break是直接跳出当前循环,continue是结束当前循环,而不是跳出当前循环进入下一个循环。
2.2循环结构编程
例2-2 3n 1问题猜想:对于任意大于1的自然数,如果n是奇数,就把n换成3n 1,否则就是n的一半,经过几次这样的变换,n一定会变成1。比如3105168421。
n,输出转换的次数。n109 .
样本输入:3
样本输出:7
[分析]
从3n 1问题可以看出,N不是一个“递增”的循环,循环的个数是不确定的,非常适合用while循环来实现。
2-4 3n 1问题#包括
int main(){
int n,count=0;
scanf(%d ,
while(n 1) {
if(n % 2==1)n=n * 3 ^ 1;
else n/=2;
数数;
}
printf(%d\n ,count);
返回0;
}技巧2-7:while循环的格式是:“while (condition)循环体;”。
从程序2-4中,while循环和for循环可以相互转换。这个程序中的Count相当于一个计算器,编程中经常会遇到。
技巧2-8:当你需要计算某物的数量时,你可以用一个变量作为计算器。
技巧2-9:不要忘记测试。一个看似正确的程序可能隐含着错误。
技巧2-10:当你无法通过观察发现错误时,你可以使用“输出中间结果”的方法来检查错误。
例2-3阶乘的和。输入n,计算S=1!2!3!… n!的后6位(不包括前导0)。n106 .这里,n!表示前n个正整数的乘积。
示例输入:10
示例输出:37913
[分析]
使用s变量来累加阶乘的和。核心算法只有一句话:for(I=1;i i ) S=i!C语言没有阶乘运算符,所以需要一个循环来求I!for(j=1;j j)阶乘*=j;
代码如下:
程序2-5(1)#的阶乘和包括
int main(){
int i,j,n,S=0;
scanf(%d ,
for(I=1;i i ){
int factorial=1;
for(j=1;j j)
阶乘*=j;
S=阶乘;
}
printf(%d\n ,S % 1000000);
返回0;
}注意:每次执行循环体,都要重新声明乘数阶乘,并初始化为1(因为是乘积,所以初始化为1。如果初始化为0,循环后的阶乘等于I!=0)。
提示2-11:在循环体开始定义的变量将在每次循环体执行时被重新声明和初始化。
技巧2-12:要计算一个只包含加减乘除的整数表达式除以正整数N的余数,可以在每个计算步骤后取N的余数,结果不变。
程序2-6阶乘和(2)#包括
#包括
int main(){
const int MOD=1000000
int i,j,n,S=0;
scanf(%d ,
for(I=1;i i ){
int factorial=1;
for(j=1;j j)
阶乘=(阶乘* j % MOD);
S=(S阶乘)% MOD
}
printf(%d\n ,S);
printf(使用的时间=%.2lf\n ,(double)clock()/CLOCKS _ PER _ SEC);
返回0;
}说明:(1)这个程序真正特别的地方是计时函数clock()的使用。这个函数返回程序到目前为止的运行时间,以毫秒为单位。这样在程序结束前调用它就可以得到整个程序的运行时间。将该时间除以常数CLOCKS_PER_SEC得到的值以秒为单位。
(2)在VC 6.0中,time.h下宏定义的常量CLOCKS_PER_SEC的值为1000。在VC 6.0中,这个符号常量定义如下:#define CLOCKS_PER_SEC 1000
对于CLOCKS_PER_SEC,它用来表示一秒钟内有多少个时钟计数单位。时钟计数单位长度为1ms,clocks ()/clocks _ per _ sec是将毫秒转换为秒。
提示2-13:可以使用time.h和clock()函数获取程序运行时间。常数CLOCKS_PER_SEC与操作系统有关。请不要直接使用clock()的返回值,一定要用CLOCKS_PER_SEC除。
提示2-14:很多程序的运行时间与标度n之间存在着近似的简单关系,这种关系可以通过计时函数找到或验证。
本节中的两个示例展示了计数器和累加器的使用,以及循环结构编程中两个最常见的问题:算术溢出和低程序效率。另外,本节介绍的两个工具——,输出中间结果和计时功能,都是相当实用的。
2.3文件操作
例2-4数据统计。输入一些整数,求它们的最小值、最大值和平均值(保留3位小数)。确保这些数字都是不超过1000的整数。
样本输入:2 8 3 5 1 7 3 6
样本输出:1 8 4.375
[分析]
如果你先输入整数N,再输入N个整数,我相信你能写出一个程序。关键是整数个数不确定。给出了以下程序:
2-7数据统计(错误)#包括
int main(){
int x,n=0,min,max,s=0;
while(scanf(%d ,x)==1) {
s=x;
if(x min)min=x;
if(x max)max=x;
n;
}
printf(%d %d %.3lf\n ,min,max,(double)s/n);
返回0;
}说明:(1)1)scanf函数的返回值是成功输入的变量个数。输入完成后,scanf无法再次读取x,将返回0。
(2)在测试过程中,输入2 8 3 5 1 7 3 6,按Enter后没有输出结果,所以此时按Enter并不代表输入结束。
2-15:Windows下,输入完毕后,按Enter,再按Ctrl Z,最后按Enter完成输入。在Linux下,按Ctrl D键完成输入。
通过提示2-15,可以完成输入。但是这个程序的运行结果是不确定的。
提示2-16:变量在赋值前的值是不确定的。特别是不一定等于0。
上述程序运行结果不正确的解决方法是在变量使用前给变量赋初值。因为min保存的是最小值,所以它的初始值应该是一个非常大的数;反之,max的初始值应该是一个很小的数。一种方法是定义一个非常大的常数,比如INF=1000000000,然后让max=INF,min=-INF,另一种方法是先读取第一个整数x,然后让max=min=x。
另一个好方法是用file ——把输入数据保存在文件中,输出数据也保存在文件中。实际上,几乎所有算法竞赛的输入数据和标准答案都保存在文件中。
使用文件最简单的方法是使用I/O重定向。只需在主函数的入口处添加以下两条语句:
freopen(input.txt , r ,stdin);
freopen(output.txt , w ,stdout);它会让scanf从文件input.txt读取,printf写到文件output.txt但是并不是所有的算法竞赛都允许用程序读写文件。有些比赛甚至允许访问文件,但不允许重定向如freopen读写文件。参赛前请仔细阅读文件读写相关规定。
提示2-17:赛前请了解文件读写的相关规定:是标准输入输出(也叫标准I/O,即直接键盘读取和屏幕写入)还是文件输入输出?如果是文件输入/输出,是否禁止通过重定向访问文件?
这些年来,无数玩家因为文档相关问题损失了大量积分。一个放之四海而皆准的原则就是:认真阅读比赛规则,严格遵守。
举个例子,如果题目指定程序名为test,输入文件名为test.in,输出文件名为test.out,只要不犯以下错误就行。
错误:程序另存为t1.c(应该改成test.c)。
错误:从input.txt读取数据(应该从test.in读取)。
3:错误:从tset.in读取数据(拼写错误,应该是从test.in读取)。
错误:数据写入test.ans(扩展名不对,应该是test.out)。
错误:数据被写入c:\contest\test.out(您不能添加路径,即使它是相对路径。文件名应该只有8个字符:test.out)。
提示2-18:在算法竞赛中,参赛选手应严格遵守竞赛的文件名规定,包括程序文件名和输入输出文件名。不要搞错大小写,不要拼错文件名,不要用绝对路径或者相位路径。
使用文件是一种很好的自测方法,但是如果比赛要求标准的输入输出,自测结束后必须删除重定向语句。
这里有一个方法,可以在原生测试的时候用文件重定向,但是一旦提交给比赛,重定向声明就会自动“删除”。代码如下:
程序2-8数据统计(重定向版本)#定义本地
#包括
#定义INF 1000000000
int main(){
#ifdef本地
freopen(data.in , r ,stdin);
freopen(data.out , w ,stdout);
#endif
int x,n=0,min=INF,max=-INF,s=0;
while(scanf(%d ,x)==1) {
s=x;
if(x min)min=x;
if(x max)max=x;
/*
printf(x=%d,min=%d,max=%d\n ,x,min,max);
*/
n;
}
printf(%d %d %.3lf\n ,min,max,(double)s/n);
返回0;
}以上是典型的竞赛代码,包含几个特殊的地方:
(1)重定向部分写在#ifdef和#endif中。这意味着只有在定义了符号LOCAL时,才会编译两个freopen语句。
(2)输出中间结果的printf语句写在注释3354中。它不应该出现在程序的上一个版本中,但是又舍不得删除(万一发现新的bug,又需要用来输出中间信息)。对其进行注释的好处是,一旦需要,可以移除注释者。
上面的代码在程序头中定义了符号LOCAL,所以它在原生测试中使用重定向来读写文件。如果比赛要求读写标准输入输出,提交前删除#define LOCAL即可。更好的方法是在编译选项中定义这个局部符号,而不是在程序中定义,这样程序在提交前就不需要修改了。
如果竞赛需要文件输入和输出,但禁止重定向,则过程如下:
2-9数据统计(fopen版本)#包括
#定义INF 1000000000
int main(){
FILE *fin,* fout
fin=fopen(data.in , Rb );
fout=fopen(data.out , WB );
int x,n=0,min=INF,max=-INF,s=0;
while(fscanf(fin, %d ,x)==1) {
s=x;
if(x min)min=x;
if(x max)max=x;
n;
}
fprintf(fout, %d %d %.3lf\n ,min,max,(double)s/n);
fclose(fin);
fclose(fout);
返回0;
}描述:(1)这个程序先声明变量fin和fout,将scanf改为fscanf,第一个参数是fin;将printf改为fprintf,第一个参数是fout,最后执行fclose关闭两个文件。
(2)重定向和fopen的区别。重定向方法写起来简单自然,但是不能同时读写文件和标准输入输出;fopen的写法有点繁琐,但是比较灵活。如果想把程序的fopen版本改成读写标准输入输出,只需赋值fin=stdin;fout=stdout就是不想调用fopen和fclose。
2.4总结和练习
2.4.1输出技能首先是输出技能。对程序2-1做个小改动,实现2,4,6,8的输出,2n,每行。为方便起见,程序复制如下:
#包括
int main()
{
int i,n;
scanf(%d ,
for(I=1;我我)
printf(%d\n ,I);
返回0;
}任务1:修改第7行,而不是第6行。
回答:
将第7行修改如下:
printf(%d\n ,2i);
任务2:修改第6行,但不修改第7行。
回答:
将第6行修改如下:
for(I=2;i=2ni=2)
浮点陷阱
"!="运算符表示“不相等”,下面的程序运行结果是什么?
#包括
int main()
{
双I;
for(I=0;我!=10;i=0.1)
printf(%.1lf\n ,I);
返回0;
}解释:对于I,可以达到10.0,但绝不会等于10,所以for循环是一个无限循环。==还有!不能直接用于float和dobule类型的数据!=比较大小,即不要测试精确的浮点值,而是用精度比较来测试一个可接受的值范围。教材P85有这样的说明。举个例子,
if(fabs(销售税-0.065)=0.0001)
.
64位整数
题目:输入一个正整数N,并计算其正因数的个数。n1012 .例如,当n=30时,输出应为8。
[分析]
(1)如果I是n的除数,那么n/i也是n的除数.所以你可以从1枚举到。
(2)n过大(n1012),超出了int类型的范围(-231 ~ 231-1,略宽于-2 29 ~ 2 29)。
(3)还有一种比int更大的类型,叫做long long,它的表示范围是-263 ~ 263-1,比-1019 ~-1019略窄。在VC6.0中(没有long long数据类型),如果要定义一个long long数据类型的变量a(64位整数),应该定义如下:
_ _ int 64 a;
使用%I64d进行输入,例如:
scanf(%I64d ,
printf(%I64d ,a);
这个问题的过程如下:
#包括
#包括
int main()
{
__int64 n,/*注意,int64前面有两个下划线(_) */
x,count=0;/*假设x是n的因子,count是计数器*/
scanf(%I64d ,
for(x=1;x=(_ _ int 64)sqrt(n);x ){
if(n % x==0)count=2;/* 2,因为x和n/x都是n的因子*/
if(n/x==x)count=count-1;
}
printf(%I64d\n ,count);
返回0;
}
2 . 4 . 4 C中的I/O
“A B”问题:输入几对整数,输出每对的和。通过经典的“A B”问题,我们可以用C语言来研究输入和输出。
(1)方法1
#include //的功能与C中的stdio.h接近,但略有不同。
使用命名空间std
int main()
{
int a,b;
while(scanf(%d%d ,a,b)==2) printf(%d\n ,a b);
返回0;
}上面的C程序和C程序很像。唯一不同的是,原来的stdio.h被改成了cstdio,并且多了一条使用名称空间std的语句。这是一个普遍规律。——要在C程序中使用C语言头文件,请删除扩展名。h并在前面加上小写字母C。例如,stdio.h在C中的新名称是cstdio。另外,第一行以//开头的“单行注释”是c所特有的,它可以与c中的传统注释(/和/)混合使用。
(2)方法2(不要记住烦人的占位符如%d和%lf)
#include //头文件iostream包含了iostream的定义。
使用命名空间std
int main(){
int a,b;
接下来,使用输入和输出文件流来修改方法2。该过程如下:
#包括
使用命名空间std
ifstream fin( APL USB . in );
of stream fout( APL USB . out );
int main(){
int a,b;
While(fin a b) fout描述:(1)在C中,数据从一个对象到另一个对象的流动抽象地称为“流”。文件是数据流,其输入和输出对象是外部文件。输出文件流是从内存流向外部文件的数据,输入文件流是从外部文件流向内存的数据。每个文件流都有一个与之对应的内存缓冲区。
在C的I/0类库中,定义了几个文件类,专门用于磁盘文件的输入输出操作。文件操作有三个文件类:
(1) ifstream (inputfilestream)类,该类是从istream类派生的。用于支持从磁盘输入文件,即从硬盘到内存。
您可以通过以下方式创建输入文件流对象:
ifstream fin( APL USB . in );
其中fout是ofstream类(输出文件流类)的对象。
ofstream(输出文件流)类,由ostream类派生而来。用来支持文件输出到磁盘,也就是从内存输出到硬盘。
您可以通过以下方式创建输出文件流对象:
of stream fout( APL USB . out );
其中fout是ofstream类(输出文件流类)的对象。
fstream类,派生自iostream类,用于支持磁盘文件的输入输出。
(2)文件流和文件的概念区别文件流不是由几个文件组成的流,文件流本身也不是文件,而是输入输出对象都是文件的流。如果要输入输出磁盘文件,必须通过文件流来实现。
(3)文件流中的两个重要操作符:
提取器()从流中输入数据。比如这个程序中有一个输入流(fin),fin a b就是从输入流中读取两种指定类型(即变量A和B的类型)的数据。
插入器()将数据输出到流。例如,这个程序有一个输出流(fout),fout a b \ n将表示b和换行符( \n )的值输出到fileoutputstream fout。
如果要再次使用cin和cout,是否要将程序中的所有fin和fout逐一替换为cin和cout?不用麻烦,只需删除fin和fout的声明语句并添加两行,如下所示:
#定义fin cin
#定义fout cout
2 . 4 . 5 ACM主题中的I/O
1.ACM问题的特点。因为ACM竞赛题的输入数据和输出数据通常有多组(不确定),格式多种多样,如何处理问题的输入和输出是每个人的基本要求。这也是困扰初学者的一大难题。刚接触ACM在线测试系统的同学经常抱怨“为什么我连OJ(在线评委)简单的A B都过不了?”
首先举一个竞赛的例子:
题目:投入产出实务A B(一)
链接地址:http://acm.hdu.edu.cn/showproblem.php? PID=1089
时间限制:1秒内存限制:32768K
问题描述
你的任务是计算一个b。
太容易了?当然啦!我专门为acm初学者设计的问题。
你一定发现了一些问题和这个问题有相同的标题,是的,所有这些问题都是为了同一个目的而设计的。
投入
输入将由一系列由空格分隔的整数对a和b组成,每行一对整数。
输出
对于每一对输入整数a和b,你应该在一行中输出a和b的和,并且在输入中每行有一行输出。
样本值输入
1 5
10 20
抽样输出
六
30
初学者很常见的写法:
#包括
void main()
{
int a,b;
scanf("%d %d ",a,
printf("%d ",a b);
}但是上面的代码提交到OJ就不能通过了。原因是什么?这是下面需要解决的问题。下面就分门别类的介绍一下吧。
2.基本输入(1)类型I输入
输入没有指出有多少输入块,以EOF作为结束标记,例如上面的例子。
源代码如下:
#包括
int main()
{
int a,b;
while(scanf(%d %d ,a,b)!=EOF) printf(%d\n ,a b);
}这类问题的输入方案是:
C语法
while(scanf(%d %d ,a,b)!=EOF)
{
.
} C语法
而(cin)
{
.
}描述:
scanf函数的返回值是读取的变量个数,如scanf(%d %d ,a,b);
如果只有一个整数输入,返回值为1;如果有两个整数输入,返回值为2;如果没有,返回值为-1。
EOF是预定义的常数,等于-1。
(2)第二类输入
在输入开始时,会说有n个输入块,接着是n个输入块的输入。
参见HDOJ _ 1090(http://acm.hdu.edu.cn/showproblem.php?pid=1090).
源代码如下:
#包括
int main()
{
int n,I,a,b;
scanf(%d ,
for(I=0;这类问题的输入方案是:
C语法
scanf(%d ,
for(I=0;I2C语法
CIN n;
for(I=0;I(3)第三类输入
输入并不表示有多少个输入块,但一个特殊的输入是结束标记。
见HDOJ _ 1091(http://acm.hdu.edu.cn/showproblem.php?pid=1091).
源代码如下:
#包括
int main()
{
int a,b;
while(scanf(%d %d ,a,b) (a!=0 b!=0))
printf(%d\n ,a b);
}上面的程序有什么问题?
这类问题的输入方案是:
C语法
while(scanf("%d ",n)!=EOF n!=0 )
{
.
} C语法
而(cin n n!=0 )
{
.
} (4)第四类输入
对于以上情况的结合,可以参考以下网页进行计算机实验。
http://acm.hdu.edu.cn/showproblem.php? PID=1092
http://acm.hdu.edu.cn/showproblem.php? PID=1093
http://acm.hdu.edu.cn/showproblem.php? PID=1094
(5)类型5输入
输入一整行字符串。
见hdoj _ 1048(http://acm.hdu.edu.cn/showproblem.php?pid=1048).
这类问题的输入方案是:
C语法
char buf[20];
gets(buf);
C语法
如果使用字符串buf要保存,使用语句getline( cin,buf);
如果使用char buf[ 255];要保存,使用语句cin.getline( buf,255);
解释:scanf(%s%s ,str1,str2),用一个或多个空格分隔多个字符串;
如果使用gets函数,应该是gets(str 1);gets(str 2);字符串由回车符分隔。
一般情况下,scanf函数用于短字符,gets函数用于长字符。
getchar函数一次只接受一个字符,c=getchar()经常这样用。
CIN . getline的用法
Getline是一个函数,它可以接受用户输入的字符,直到达到指定的数字或用户输入特定的字符。其函数声明形式(函数原型)如下:
istream getline(char line[],int size,char end char= \ n );
不管它的返回类型是什么,都要关心它的三个参数:
第[]行是一个字符数组,用户输入的内容将存储在这个数组中。
Int size表示最多接受多少个字符?任何超过用户大小的输入都不会被接受。
Endchar是指当用户输入字符指定char endchar时,会自动结束。是默认的回车符。
结合后两个参数,可以方便地实现getline:用户最多可以输入指定数量的字符。如果超过指定的数量,只有前面指定数量的字符才有效。如果没有超过指定的数目,用户可以通过输入。
字符名称[4];
cin.getline(name,4, \ n );
由于endchar默认已经是 \n 了,下面这一行也可以写成:cin.getline(name,4);
思考:下面这个题目属于哪种类型的输入?
http://acm.hdu.edu.cn/showproblem.php?pid=1018
http://acm.hdu.edu.cn/showproblem.php?Pid=10133。基本输出(1)第一种输出
输入块对应于输出块,输出块之间没有空行。
见hdoj _ 1089(http://acm.hziee.edu.cn/showproblem.php?pid=1089).
这类问题的输出方案是:
C语法
{
.
printf(%d\n ,ans);
} C语法
{
.
cout ans endl
} (2)第二种输出
一个输入块对应一个输出块,每个输出块后面都有一个空行。
见HDOJ _ 1095(http://acm.hdu.edu.cn/showproblem.php?pid=1095).
源代码如下:
#包括
int main()
{
int a,b;
while(scanf(%d %d ,a,b)!=EOF) printf(%d\n\n ,a b);
}解决方案如下:
C语法
{
.
printf(%d\n\n ,ans);
} C语法
{
.
cout ans endl endl
} (3)第三种输出
一个输入块对应一个输出块,输出块之间有空行。
见hdoj _ 1096(http://acm.hdu.edu.cn/showproblem.php?pid=1096).
源代码如下:
#包括
int main()
{
int icase,n,I,j,a,sum
scanf(%d ,icase);
for(I=0;一、解决方案如下:
C语法
for(k=0;知识语法
同样,只需更改输出语句。
思考:
以下题目属于哪种输出?
http://acm.hdu.edu.cn/showproblem.php? PID=1016 http://acm.hdu.edu.cn/showproblem.php? PID=1017
4.初学者常见问题(1)编译错误
主函数必须返回int类型(正式竞争);
不要在for语句中定义类型;
如果__int64不支持,可以用long long代替;
使用中文标点符号;
itoa不是标准的C函数。它可以将整数转换成字符串,这是Windows独有的。如果编写跨平台程序,请使用与ANSI标准兼容的sprintf()函数。
int num=100
char str[25];
sprintf(str, %d ,num);
另外,复制程序容易出错。
(2)C语言处理“混合数据”的问题
见hdoj _ 1170(http://acm.hdu.edu.cn/showproblem.php?pid=1170).
通用代码:
……
scanf(%d\n ,icase);
for(I=0;(printf和cout的混合使用
下面的程序输出什么?
#包括
#包括
int main()
{
int j=0;
for(j=0;j j)
{
cout j=
printf(%d\n ,j);
}
返回0;
}程序输出是
0
一个
2
三
j=j=j=j=j=j=j=.
为什么?因为一个有缓冲输出(cout),另一个没有缓冲输出(printf)。
5.在OJ上提交代码后出现的提示。在OJ上提交代码后,会弹出处理页面,然后点击处理页面上的状态链接,会弹出状态页面。
状态页面显示一些信息,如运行ID、提交时间、法官状态、问题ID、语言、运行时间、运行内存和用户名。法官身份一般有以下几个条件。
接受:祝贺你,是的。
演示错误:输出格式错误。
错误答案:答案错误。
运行时:程序运行时出错,主要是因为数组访问越界。
超过时间限制:超级内存错误,运行的程序使用的内存超过了限制的内存使用量。
编译错误:编译错误,源代码中的语法错误。
6.学习风格(1)通过练习-总结-实践-总结的过程.我可以提高自己的编程水平;
(2)可以在http://acm.hdu.edu.cn或其他网站多加练习;
(3)可以去杭电ACM论坛或者其他ACM论坛,与他人分享经验;
(4)如有疑问,可在谷歌、百度上搜索。
总结
现在,本章介绍的循环总结如下:
(1)介绍编程中的一些经验,如使用计算器、累加器和“当前最小值/最大值”等中间变量。使用printf输出一些关键的中间变量,可以有效的帮助我们理解程序执行的过程,发现错误。
(2)遇到问题,需要自己分析设计。可以先写“伪代码”,然后转换成程序。伪代码是为了让思路更清晰,突出主要矛盾。
(3)程序写好之后,测试很重要。和前面的例子一样,几乎都有陷阱:运算结果溢出、运算时间过长等。海量的输入输出问题可以通过文件来缓解。
(4)再次强调:编程不是用来看书或者听课的,而是用来练习的。
2.4.7在计算机上练习
注意,本章中的主题需要通过文件进行输入和输出。如果标题代码是abc,那么输入文件是abc.in,输出文件是abc.out如果不熟悉文件操作,请同时尝试fopen和freopen方法。
练习2-1位数(digit)输入一个不超过109的正整数,并输出其位数。比如12735的位数是5。请不要用任何数学函数,只用四则运算和循环语句。
[分析]
采取的策略是连续除以10,检查商是否大于10。
该过程如下:
#包括
void main() {
无符号长n;/*无符号长整数,占用4个字节的存储空间*/
int digit=1;/*位数*/
scanf(%ld ,
for(;n ) {
n=n/10;
数字=数字1;
}
printf(%d ,数字);
返回;
}练习2-2水仙花输出从100到999的所有水仙花号。如果3位数的ABC=A2 B2 C2,则称为水仙花的数量。比如153=13 53 33,那么153就是水仙花的数量。
[分析]
采取的策略是穷尽100到999的所有数据,检查是否符合题目要求。
该过程如下:
#包括
void main() {
int n,
甲、乙、丙;/* n的百位数、十位数和位数*/
for(n=100;n=999n=n ^ 1){
a=n/100;
b=(n-a * 100)/10;/*也可以写成b=(n ^ 0)/10;*/
c=n % 10
If (n==a*a*a b*b*b c*c*c) /*算术运算优先于逻辑运算*/
printf(%d\n ,n);
}
返回;
}练习2-3韩信笔下的韩熙据说是个才华横溢的人。韩信从来不直接统计自己的兵力。他只需要让士兵们三个五个七个一排的改变队形,每次只瞥一眼队伍的尾部就知道总数。输入三个非负整数a、b、c,表示每个编队结束时的人数(a 3、b 5、c 7),输出总人数的最小值(或报无解)。已知总人数不少于10人,不超过100人。
样本输入:2 1 6
样本输出:41
样本输入:2 1 3
示例输出:无答案
[分析]
采用的策略是用穷举法解决问题;总人数(10,100人)。
该过程如下:
#包括
void main () {
Int,/*一排三个人,剩下的是一个*/
B,/*一排五个人,其余都是B人*/
C,/*七人一排,其余C人*/
总和;/*总人数*/
scanf(%d%d%d ,a,b,
for(sum=10;sum=100sum=sum 1) {
if((总和%3==a)(总和%5==b)(总和%7==c)) {
printf(%d ,sum);
打破;
}
}
if (sum 100) printf(无答案);
返回;
}练习2-4倒三角形(三角形)输入正整数n20,输出n层倒三角形。例如,当n=5时,输出如下:
#########
#######
#####
###
#[分析]
这个图总共有N条线。这一次,在每一行中,首先应该输出一些空格。因此,它的外环是:
for(I=1;i i ){
输出几个空格。
输出几个#
换行
}
下面在第I行列出,空格数和#字符数与I的关系为:
I .行中的空格数#字符数
1 0 2n-1
2 1 2n-3
…
i i-1 2n-2i 1
…
n-1 n-2 3
n n-1 1
即第I行空格数为i-1,#字符数为2n-2i 1。#你是怎么得到字符数2n-2i 1的?如果该行从第n行到第一行被标记,并且从第n-1行到第二行被标记,…,则原来的第I行现在被标记为第n-i1行。现在第1行的#字符数为1,第2行的#字符数为3=2*2-1,那么原来的第I行现在记录为第n-i 1行,输出的#字符数为2(n-i 1)-1=2n-2i 1。
所以在第I行输出空格和#字符的内部循环是:
for(j=1;j=I-1;j)
printf(“”);
for(j=1;j=2n-2i 1;j)
printf(%c , # );合在一起,就构成了一个完整的程序。
该过程如下:
#包括
void main () {
Int,/*输出n行;n=20 */
I,/*打印第I行*/
j;
scanf(%d ,
for(I=1;i i=i 1) {
/*在第I行,打印(i-1)个空格*/
for(j=1;j=I-1;j=j 1)printf();
/*在第I行,打印(2*n-2*i 1) # */
for(j=1;j=(2 * n-2 * I 1);j=j 1)printf( # );
printf( \ n );/*在输出后换行,否则所有#号将在同一行输出*/
}
返回;
}扩展1:用于循环编程绘制下图:M
梅智节拍器
嗯
嗯
嗯嗯
我恨
MMMMMMM
嗯嗯嗯
嗯嗯嗯
MMMMMMMMMM[分析]
该图形共有10行,每行添加一个字符。所以要循环10次,每次输出一行。循环模式是:
for(I=1;i i ){
输出线I
换行
}
输出行I是for循环中的一个小循环。每次执行“输出第I行”时,其长度是不同的,但长度的变化正好与循环变量I同步,所以可以依赖于I,注意第I行中m个字符的个数与I的关系。
线路i M号
1 1 1
2 2 2
3 3 3
…
10 10 10
因此,您可以得到如下“输出行I”的循环:
for(j=1;j)printf(" % c ", m )的完整程序如下:
#包括
main(){
int i,j;
for(I=1;i i ){
for(j=1;j j)
printf(“% c”,“M”);
printf( \ n );
}
}注意:处理这种字符图,一般采用双循环,外循环遍历所有行,内循环遍历一行中的每个字符。
2:输出以下数字:mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
嗯嗯嗯嗯嗯
嗯嗯嗯嗯嗯
嗯嗯嗯嗯
嗯嗯嗯
嗯嗯嗯
MMMMMMM
嗯嗯
嗯
m[分析]
这张图表总共有10条线。这一次,在每一行中,首先应该输出一些空格。参考文献
}下面第I行列出,空格数和m、I数的关系为:
线路i M号
1 0 19
2 1 17
3 2 15
4 3 13
…
10 9 1
也就是说,第I行的空格数是i-1,m的个数是21-2i。也就是说,在第I行输出空格和M个字符的内部循环是:
for(j=1;j=I-1;j)
printf(" ");
for(k=1;k=21-2i;k)
printf("%c ", M );合在一起,就构成了一个完整的程序。
完整的过程如下:
#包括
int main()
{
int i,j,k;
for(I=1;我我)
{
for(j=1;j =i-1;j++)
printf(" ");
for(k=1;k =21-2*i;k++)
printf("%c",M);
printf("\n");
}
return 0;
}引申3:输出下列图形:A
ABC
ABCDE
ABCDEFG
ABCDEFGHI
ABCDEFGHIJK
ABCDEFGHIJKLM
ABCDEFGHIJKLMNO
ABCDEFGHIJKLMNOPQ
ABCDEFGHIJKLMNOPQRS【分析】
该图形一共有10行,这次要考虑每行中,先输出若干个空格,所以,其外循环为:
for( i=1;i i++){
输出若干个空格
输出若干字符
换行
}如果要输出A起头依序的n(n 27)个字母,可以为:
for(ch=A;ch A+n;++ch)
printf("%c",ch);下面分析每一行中的空格数与字符数与第i行之间的关系:
行 i M数
1 9 1
2 8 3
3 7 5
4 6 7
…
10 0 19
即第i行的空格数据为10-i个,字符数为2i-1。因此,输出空格数和字符数的内循环分别为:
for(j=1;j =10-i;++j) /输出空格数/
printf(" ");
for(ch=A;ch A+2*i-1;++ch)
printf("%c",ch);
合起来,构成一个完整程序。
完整程序如下:
#include
int main()
{ int i,j;
char ch;
for(i=1;i i++)
{
for(j=1;j =10-i;++j) /*输出空格数*/
printf(" ");
for(ch=A;ch A+2*i-1;++ch) /*输出字符*/
printf("%c",ch);
printf("\n");
}
return 0;
}引申4:输出下列图形:*
***
*****
*******
*****
***
*上面的图形可以分成两部分:
(1)
*
***
*****
*******与引申3的分析一样,输出空格数和字符数的内循环分别为:
for(j=1;j =4-i;++j) /*输出空格数*/
printf(" ");
for(k=1;k =2*i-1;++k) /*输出“*”号*/
printf("*");(2)
*****
****与引申2的分析一样,输出空格数和字符数的内循环分别为:
for(j=1;j ++j) /*输出空格数*/
printf(" ");
for(k=1;k =7-2*i;++k) /*输出“*”号*/
printf("*");合起来,构成一个完整程序。
完整程序如下:
#include
main()
{ int i,j,k;
for(i=1;i i++)
{
for(j=1;j =4-i;++j) /*输出空格数*/
printf(" ");
for(k=1;k =2*i-1;++k) /*输出“*”号*/
printf("*");
printf("\n");
}
for(i=1;i i++)
{
for(j=1;j ++j) /*输出空格数*/
printf(" ");
for(k=1;k =7-2*i;++k) /*输出“*”号*/
printf("*");
printf("\n");
}
}
习题2-5 统计(stat)
输入一个正整数n,然后读取n个正整数a1,a2,…,an,最后再读一个正整数m。统计a1,a2,…,an中有多少个整数的值小于m。提示:如果重定向和fopen都可以使用,哪个比较方便?【分析一】在没有学习过“数组”概念以前,想要做出本题,需要扫描2次输入文件。第一次是为了读到m;第二次是为了读出n个输入。
输入文件:stat.in.txt。
文件格式描述如下:
每行一个正整数,各行分别是:n, a1, a2, ..., an, m;例如:
n
a1
a2
...
an
m
输出文件:stat.out.txt程序如下:
#include
void main() {
int m,n,i,
newData, /*新读到的数据*/
count; /*计数器*/
freopen("stat.in.txt","r",stdin);
freopen("stat.out.txt","w",stdout);
scanf("%d",
for (i=1; i i=i+1) scanf("%d", newData); /*跳过n个输入数据*/
scanf("%d",
/*秘诀就在这里:再次打开输入文件,再次向程序输入数据*/
freopen("stat.in.txt","r",stdin);
scanf("%d",
count=0;
for (i=1; i i=i+1) {
scanf("%d", newData);
if (newData【分析二:统计的变种1】如果没有学习过“数组”的相关知识,那么本题实难解答。因此稍稍修正一下题目。
题目修改如下:
读入一个正整数m,再读入一个正整数n;然后读取n个正整数a1,a2,...,an,统计a1,a2,...,an,中有多少个整数的值小于m。
这是使用键盘输入的版本。本题主要考察循环语句的使用,以及读入大量数据的操作。
程序如下:
#include
void main () {
int n,i,m,
newData, /*新输入的数据*/
count; /*计数器*/
scanf("%d",
scanf("%d",
count=0;
for (i=1; i i=i+1) {
scanf("%d", newData);
if (newData【分析三:统计的变种2】如果没有学习过“数组”的相关知识,那么本题实难解答。因此稍稍修正一下题目。
题目修改如下:
读入一个正整数m,再读入一个正整数n;然后读取n个正整数a1,a2,...,an,统计a1,a2
,...,an中有多少个整数的值小于m。
这是使用重定向输入/输出的版本。
输入数据文件:统计的变种.in.txt。
输出数据文件:统计的变种.out.txt。
本题主要考察循环语句的使用,以及读入大量数据的操作。
程序如下:
#include
void main () {
int n,i,m,
newData, /*新输入的数据*/
count; /*计数器*/
freopen("统计的变种.in.txt","r",stdin);
freopen("统计的变种.out.txt","w",stdout);
scanf("%d",
scanf("%d",
count=0;
for (i=1; i i=i+1) {
scanf("%d", newData);
if (newData习题2-6 调和级数(harmony)输入一个正整数n,输出H(n)=!的值,保留3位小数。例如n=3时答案为1.833。
【分析】
本题主要考察循环语句的使用。秘诀是要从绝对值最小的项开始向绝对值大的项累加。
程序如下:
#include
void main () {
unsigned int n; /*我们认为int已经足够表达所谓的“正整数”范围*/
double sum=0;
scanf("%u",
for (; n n=n-1) {
sum=sum+1.0/n;
}
printf("%.3f",sum);
return;
}习题2-7 近似计算(approximation)计算,直到最后一项小于10-6。
【分析】
本题主要考察循环语句的使用。秘诀是要从绝对值最小的项开始向绝对值大的项累加。
程序如下:
#include
void main () {
int n;
double sum=0;
int symbol;
n=1000001; /*显然,1/1000001小于0.000001*/
for (; n n=n-2){
if ((n+1)/2%2==1) symbol=1;
else symbol=-1;
sum=sum+symbol*(1.0/n);
}
printf("%.20lf",sum);
return;
}习题2-8 子序列的和(subsequence)输入两个正整数n m 106,输出#,保留5位小数。例如,n=2,m=4时答案是0.42361;n=65536,m=655360时答案为0.00001。注意:本题有陷阱。
【分析】
本题主要考察循环语句的使用。秘诀是要从绝对值最小的项开始向绝对值大的项累加。所谓的陷阱,是指m的平方可能会导致整数溢出。所以,另一个秘诀是,把m和n定义为double。
程序如下:
#include
void main () {
double m,n;
double sum=0;
scanf("%lf%lf", n, /* 假设用户输入的n总是不大于m */
for (; m m=m-1) {
sum=sum+1.0/(m*m); /*注意,不能写成 sum=1/m*m */
}
printf("%.5lf",sum);
return;
}习题2-9 分数化小数(decimal)输入正整数a,b,c,输出a/b的小数形式,精确到小数点后c位。a,b≤106,c≤100。例如a=1,b=6,c=4时应输出0.1667。
【分析】
注意到a,b,c均为正整数,所以输出结果的小数点后至少会有1位。另外,从本题的示例输出中可以感知到,小数的最后一位,是要考虑到四舍五入进位的。
采取的策略是模拟整数除法的过程,利用整除所得的余数,不断地对目标结果求精。
程序如下:
#include
void main() {
unsigned int a,b,c, x, y; /* 小数点后的位数 */
scanf("%d%d%d", a, b,
x=a/b;
printf("%d.",x);
x=a%b;
y=1;
for (; y y=y+1) {
x=x*10;
if (y!=c)
printf("%d",x/b);
else {
/* 输出小数的最后一位时,考虑到下一位的数值是否会产生四舍五入的进位 */
if (x%b*10/b =5)
printf("%d",x/b+1);
else
printf("%d",x/b);
}
x=x%b;
}
return;
}习题2-10 排列(permutation)用1,2,3,…,9组成3个三位数abc,def和ghi,每个数字恰好使用一次,要求abc:def:
ghi=1:2:3。输出所有解。提示:不必太动脑筋。
【分析】
采用的策略是穷举法解题。尽管说“不必太动脑筋”,但也不意味着“一点儿都不用动脑筋”。如果说三个三位数是abc, def, ghi,比率是1:2:3,那么显然d =(2a)并且g =3a。所以,1 =a =3,d =2a,g =3a;这些论断,都可以减少电脑穷举所需扫描的范围,提高运行速度。
如果还能够提出更加精确的论。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。