中图版信息技术选修一第二单元程序设计基础 课件 (共60张PPT)

课件60张PPT。程序设计基础目录程序设计概述
算法基础
程序设计的输入输出形式
C++文件操作
输入输出格式控制
排序
简单应用程序设计概述给定一个可以通过计算机来解决的问题，编程就是编制一个程序解决这个问题的活动。这样的程序告诉计算机做什么，而计算机通过执行该程序做用户叫它做的事情，并且产生用户所需要的结果。
编程阶段：
规格说明：用自然语言对设计的程序的目的和功能进行描述。
分析与算法：将规格说明用准确的术语进行刻化，通过分析逐渐将问题转化为算法。
编程：用编程语言将算法翻译成程序。即用某种编程语言编写程序源代码，然后进行编译，调试。如果有错，则改进算法或修改源代码，重新编译，调试。假如不再有错误出现，程序就可以运行了。程序设计概述问题初始化分析算法编码程序与程序语言无关与程序语言相关自然语言算法语言程序语言图：编程进程生命周期算法基础算法定义：算法是应用于一组有限输入数据集的有限个规则的集合，这些规则规定了解决某一问题的一个运算序列，以便在有限步中得到希望的结果。算法厨师的菜谱工厂的生产流程定义一系列操作
以达到所要的结果算法基础算法的特性：
有限性：求解问题的运算规则序列，必须在有限步后停止。
确定性：每一条规则都是明确、无二义的。
输入：算法开始执行之前指定初始值作为输入（有０个或多个输入）
输出：产生与输入有关的结果（至少一个）
可行性：每一条规则都是基本的、可实现的。
算法基础----算法的复杂性算法的复杂性体现在算法所需的计算机资源的量上，所需的资源越大，其复杂性越高。
计算机中的资源：最重要的是时间和空间。
复杂性主要有时间复杂性和空间复杂性。
时间复杂性就是算法所需的时间资源的量，空间复杂性就是算法所需空间资源的量。
目的：通过复杂性分析，选择最佳算法或接近最佳的算法。
考虑三种典型的复杂性：最坏情况，最好情况和平均情况下的复杂性。
算法基础在分析时间复杂性时，应明确被分析算法的“关键操作”是什么。
如：排序，“关键”的是待排序元素之间的“比较”次数，或待排序元素的“移动”次数
查找：“关键”的是待查找值X与数据元素之间的“比较”次数
矩阵乘法：元素之间的乘法，元素之间的加法算法基础----演绎方法的使用构造算法的常用方法是演绎方法。
该方法的操作步骤如下：
需明确问题的输入数据和结果的规格要求，这些信息是以问题本身的术语方式逐渐表示出来的。
将原问题分解成若干个子问题，每个子问题比原问题更易求解。重复这个分解过程，直到所有的子问题可以被某个已知的或易于给出的算法加以解决。这个过程中，常引入一些中间量来刻划子问题。
合并子问题的算法成为稍大问题的算法
得到整个问题的算法。
算法基础----演绎方法的使用算法设计中所做的算法描述如下：
数据（Data）：对输入数据取名
结果（Resule）：对结果取名
词汇（Lexicon）：对输入数据、结果和有关临时量进行简短描述
方法（Method）：用自然语言、数学公式、递推关系、算法语言等对所用计算进行描述
子问题（Subproblems）：给出一组确定的子问题
一个算法可采用如下形式表示：
输出素数
问题描述：素数是大于1并且只能被1和其本身整除的整数。给定正整数N，输出1~N之间的所有素数。
算法设计：对于一个不超过N的正整数m,如果对于大于1但小于m的所有正整数都不能整除m,那么m是素数。算法基础----演绎法算法设计举例算法基础----演绎法算法设计练习问题描述：计算矩阵与列向量的乘积
a11 a12 ….a1n x1 b1
a21 a22 ….a2n x2 = b2
… …. …. …. X3 b3
am1 am2... amn x4 b4
记A=（aij）m*n为矩阵，X=（xj）n与B=（bi）m为列向量原问题的算法设计：
数据： A=（aij）m*n，X=（xj）n
结果：B=（bi）m
词汇：输入矩阵A和列向量X，结果是B
方法：对每一个i,(1<=i<=m),计算列向量B的每个元素bi
子问题：计算每个元素bi
算法描述中所给方法表明，可以对不同的数据用m次同样的计算
本问题中的方法描述可用自然语言描述如下：
for i from 1 to m do
calculate element bi of vector B
end for
子问题（对元素bi的计算）的算法设计如下：
数据：（ai1,ai2,…,ain）,X= (xj)n
结果：bi
词汇：输入是矩阵A的第i行和n元列向量X，结果是B的第i个元素bi
方法：计算bi=∑aijxj(1<=j<=n)
子问题：无算法基础----演绎法算法设计练习原问题的算法过程：
Lexicon: A,X,B
Result:B
for i from 1 to m do
calculate element bi of vector B
EndFor
Data: A,X算法基础----演绎法算法设计练习子问题的算法过程：
Lexicon:矩阵A的第i行，X，bi
Result: bi
d=0
for k from 1 to n do
d?d+aik*Xk
End do
bi?d
Data: ai1,ai2,ai3,…,ain, X程序设计的输入输出形式ACM/ICPC竞赛题一般要求程序处理多组测试数据，而测试数据是用文本文件存储的，所以选手必须熟悉输入形式，能熟练地处理文本文件。
文本的输入可能是多输入格式，而输入的结束方式可能有：
预先确定长度，无结束符。
标志文本（如0或-1）
EOF文件结束符（C/C++中的符号常量，代表-1，表示文件的末尾。）程序设计的输入输出形式正确读入数据是编程成功的第一步，一定要了解若干种输入方式的描述形式。一定要根据题目输入描述，对每组数据分别读入，然后马上处理，而不是将文件的所有数据一下子读入进来。其实一下读入进来的方式是不可取的，有时也是不现实的。程序设计的输入输出形式cin从标准输入设备（键盘）获取数据，变量通过流提取符>>从流中提取数据。
输出一般到标准输出（也有输出到文件的）。cout将数据输出到标准输出设备（屏幕），变量通过流操作<<从流中提取数据。另外，应熟练使用操作算子进行格式控制，特别是精度和宽度控制。输出时要特别注意输出格式：行尾是否有空格，一组数据输出后是否有空行，等等。程序设计的输入输出形式---几种典型的输入形式（1）输入有若干行。每行有一个整数，它是一个测试数据。
int n;
….
While(cin>>n)
{
处理关于n 的信息；
}程序设计的输入输出形式---几种典型的输入形式（2）输入有若干行。每行两个整数a和b，之间有一个空格隔开。直到文件输入结束。
int a,b;
….
While(cin>>a>>b)
{
处理关于a,b的信息；
}程序设计的输入输出形式---几种典型的输入形式（3）输入有若干组测试数据。每组测试数据由两行构成，第一行有一个正整数n，第二行有n个整数，之间用一个空格隔开。
const int MAXN=1000;
…
int n,I,a[MAXN];//假定输入个数n<=MAXN
while(cin>>n)
{
for(i=0;i cin>>a[i];
处理关于数组a的信息；
}程序设计的输入输出形式---几种典型的输入形式（4）输入的第一行有一个整数T，表示测试数据的组数。接下来有T行，每行是一个含有空格的字符串。
const int MAXM=1000;
….
int T;
char str[MAXM];
cin>>T;
cin.getline(str,10);//吸收数据T所在行尾部的信息
while(cin.getline(str, MAXN))
{
处理关于str的信息；
}程序设计的输入输出形式---几种典型的输入形式（5）输入若干行，每行是一个含有空格的字符串。
const int MAXN=1000;
….
char str[MAXN];
while(cin.getline(str, MAXN))
{
处理关于str的信息；
}程序设计的输入输出形式---几种典型的输入形式（6）输入的第一行是一个整数T，表示T组测试数据。接着是这T组测试数据的描述。每组测试数据有3行，其第一行是2个整数m,n,第二行有m个整数，第三行有n个整数，每行的整数之间有一个空格。两组测试数据之间有一空行。int T,m,n,i;
int *a,*b;
cin>>T;
while(cin>>T)
{
cin>>m>>n;
a = new int[m+1];
b = new int[n+1];
for(i=0;i>a[i];
for(i=0;i>a[i];
处理关于数组a和b的信息；
}程序设计的输入输出形式---几种典型的输入形式（7）输入的第一行有一个整数T，表示测试数据的组数。接下来有T行，每行有若干个整数。C++文件操作 程序设计的数据是通过文件输入、文件输出的。
文件通常指：磁盘文件与标准输入、标准输出。
cin：（标准输入流对象）从键盘输入数据；
cout：（标准输出流对象）向屏幕输出。在ACM程序设计中，使用文件的两种情况：
1．ACM程序设计竞赛本身的要求：某次竞赛可能要求数据是从磁盘文件读入或将数据输出到磁盘文件。
2．调试阶段调试程序的需要。 控制台输入与输出在流文件输入的所有地方改为控制台输入，如
cin>>n;
cin.getline(source,200);
（注：这里source[200]是字符数组）。
所有流文件输出的地方改为控制台输出，如cout< cout< 在C++中进行文件处理，在程序中应包括头文件，头文件中包括流类ifstream(从文件输入)、ofstream(向文件输出)和fstream(从文件输入，输出)的定义。生成这些流类的对象即可打开文件。
C/C++中打开文本文件读取方式 以磁盘文件data.in和data.out为例：
C++中读取文件有三种方式，打开文件以便输入：
方式1: ifstream fin( “data.in” );
方式2: ifstream fin( “data.in”, ios::in );
方式3: ifstream fin;
fin.open(“data.in”，ios::in)； C/C++中打开文本文件输出方式C++中打开文件以便输出，数据输出到文件中
方式1: ofstream fout( “data.out” );
方式2: ofstream fout( “data.out”, ios::out );
方式3: ofstream fout;
fout.open(“data.out”，ios::out)； 在程序前部加库文件和关联性语句 #include
#include
#include
#include ifstream fin("data.in"); //读取文件中的数据，顺序访问
ofstream fout("data.out");//输出数据到文件中 采用ISO C++，1998 标准，应用下列语句：
#include
#include
#include
#include
using namespace std;
ifstream fin("data.in"); //读取文件中的数据，顺序访问
ofstream fout("data.out"); //输出数据到文件中 文件操作举例例：从文件中读入若干个整数对a，b，并调用求a，b的最大公因数的函数gcd(a,b)，并输出到文件：
ifstream fin("data.in");
ofstream fout("data.out");
void print(){
int a,b,d;
while(fin>>a>>b){
int d=gcd(a,b);
fout<<"("< }
}重定义语句的使用ifstream fin("data.in");
ofstream fout("data.out");
#define cin fin //重定义cin
#define cout fout //重定义cout
后面程序中可采用标准输入、输出的语句
void print(){
int a,b,d;
while(cin>>a>>b){
int d=gcd(a,b);
cout<<"("< }
} 实现文件输入、文件输出目的，与前页作用相同输入、输出格式控制 引入：初次做网上判题系统的题目，因为格式不对而不能ACCEPT。
输入输出
C++中，通过调用该操作系统的I/O库来实现的，C++是使用iostream流库
iostream流是一组C++类，用于实现面向对象模型的输入输出。
cout流对象控制向控制台（显示器）的标准输出，cin控制从控制台（键盘）输入。
常用的流类
ofstream 输出文件流类
ifstream 输入文件流类
iostream 普通输入输出流类和用于其它输入输出流的基类流基类ios层次图 普通输入流类输入文件流类用于cin的输入流类输入串流类用于标准输入输出
文件的输入输出类非格式化抽取 istream有三个从流中进行非格式化抽取的成员函数：
get()、getline()和read()。成员函数getline()的用法 格式
istream& getline(char*,int,char)
含义：
从流中抽取字符直到终止符（缺省为'n'），或者抽取字符达到参数给定的数量，或者已到文件尾，将其存储在第一个参数指定的字符数组里。如果发现终止符，它从流中提取终止符，但只是抛弃掉，并不把它存在结果缓冲区里。操纵算子操纵算子是插入到流中或从流中抽取出来，影响流的格式状态的函数或对象。流的格式状态由ios类定义，其中包括指定数据对象的基数，如十进制、八进制、十六进制，还有输出宽度、精度、填充字符等。
使用无参数操纵算子应包含iostream头文件，带参数操纵算子应包含iomanip头文件。操纵算子举例 endl 输出换行符并刷新流
dec //数值转化为十进制
hex //数值转化为十六进制 ，还有oct
setiosflags(fmtflags n) //设置由n指定的格式标志
setbase(base n) //把基数改成n
setfill(char n) //把填充字符改成n
setprecision(int n) //把小数精度设成n位
setw(int n) //把域宽改成n 使用带参数操纵算子时，应包含头文件iomanip.h 格式算子 举例setiosflags(ios::uppercase) //设置16进制数大写输出
resetiosflags(ios::uppercase) //取消16进制数大写输出
setiosflags(ios::fixed) //用定点方式表示实数
setiosflags(ios::scientific) //用科学记数法表示浮点数
setiosflags(ios::left) //左对齐；如改为right，则为右对齐
setiosflags(ios::showpoint) //强制显示小数点和无效0
setiosflags(ios::pos) //强制显示正数符号 格式控制注意要点 cout<<进制<<宽度<<精度<<数值;
setw(n) 只对紧跟其后的待输出数据有效，它用来输出欲留空间格数。若空间多余，则右对齐；若空间不够，则按数据长度输出。
cout<setiosflags(ios::fixed)与setprecision(n)合用，控制小数点右边的数字个数为n，当小数位截位显示时，进行四舍五入处理。 简单应用 转换十六进制数
颠倒原文
指定个数的整数求和
不指定个数的整数求和转换十六进制数问题描述：
给定一个十六进制非负整数n，输出其八进制、十进制、十六进制表现形式。
输入：
输入数据仅有一行，该行有一个非负十六进制整数。
输出：
输出该整数的八进制（Oct），十进制（Dec）及十六进制（Hex）形式（使用uppercase），换行。逗号后有一个空格。
输入样例
1a
输出样例
32(Oct), 26(Dec), 1A(Hex) 参考程序#include
#include
using namespace std;
int main(){
long n;
cin>>hex>>n;
cout< < return 0;
} 使用操纵算子应包含iomanip头文件 颠倒原文问题描述：在许多语言中，文字是从左到右书写的，也有一些是从右到左读写的。你的任务是编制一个程序改变文字的方向，即将从左到右书写的语言自动改变为从右到左书写的语言。
输入：从输入文件reverse.in中读取数据，它有多组测试数据。第一行有一个整数n，它是测试数据组数，（n≤10）。接下来有n行，每行至多有70个字符。但是，每一行末尾处的换行字符不能作为这一行的内容。
输出：将数据输出到文件reverse.out。对每一组测试数据，输出一行，输出的内容是输入行颠倒次序后的文本。 输入样例与输出样例输入样例
3
Frankly, I don't think we'll make much
money out of this scheme.
madam I'm adam
输出样例
hcum ekam ll'ew kniht t'nod I ,ylknarF
.emehcs siht fo tuo yenom
mada m'I madam分析本题的目的是熟悉文件的输入输出操作。
操作磁盘文件，需要在头文件中加入#include
输入文件的流指针
ifstream fin("reverse.in");
输出文件的流指针
ofstream fout("reverse.out");
字符串读入采用getline() 注意 用fin将测试数据组数读入n后，文件指针并没有转入下一行，故在其后面加入一个语句“fin.getline(line,80);”，也可用“fin.get();”，吸收行尾部符号，顺利实现转入下一行。
对文件操作，如果没有这个句子，那么结果是错误的。 参考程序#include
#include
using namespace std;
char line[80];
int len;
int main (){
int i,j, n;
cin>>n;
cin.getline(line,80);
//吸收第1行的尾部结束标志 for (i=0; i cin.getline(line,80);
j=strlen(line)-1;
for ( ; j>=0; --j){
cout< }
cout< }
return 0;
}指定个数的整数求和 问题描述：给定一系列整数，计算其总和。
输入：有若干组测试数据。每组测试数据有2行，第一行有一个正整数n；第二行有n个整数。
输出：对每组测试数据，先输出要整数的个数n，再输出逗号及计算结果，换行。输入样例
2
8 10
5
1 2 3 4 5输出样例
2,18
5,15
分析本题从标准输入文件输入数据、标准输出，用cin、cout。
用while(cin>>n)形式的循环可解决数据读入结束问题。 参考程序 #include ??
using?namespace?std; ?
int?main(){ ??
????unsigned?int?n; ??
????int?a; ??
????while(cin>>n)
{ ??
???? int?sum=0; ? for(int?i=0;i>a; ??
???????? sum+=a; ??
??? ?} ??
cout< < }
???? return?0; ??
}不指定个数的整数求和 问题描述：
对于给定的若干个整数，要求计算它们的和。
输入：
输入的第一行有一个整数n，表示测试数据的组数。接下来有n行，每行有若干个整数a1，a2，…，am,（-10000<=a1，a2，…,am, <=10000，m<=1000）。
输出：
对于每组测试数据，先输出“Case #:”（#为序号，从1开始），然后空一格后输出该组中整数的个数，后跟逗号，再空一格后输出这些数据的和。 输入样例与输出样例输入样例
2
20 1 8 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5
1 –2
输出样例
Case 1: 20, 200
Case 1: 2, -1 分析本题中每组测试数据的个数是不确定的，因此本题的难点在于如何读取一行的数据，如何判断一行输入的结束。 方法1依次读一个整数，再读一个字符，判断该字符是否为换行符。如是，则输出结果，再处理下一行；如为空格字符，则继续读数。
语句：ch=cin.get();
if(ch==10) break;
读取一个字符，并判定是否为换行 #include
using namespace std;
int main(){
int x, n,i=0;
long sum;
char line[1000],ch;
cin>>n;
cin.getline(line,1001);
//吸收第1行的尾部结束标志
while(cin>>x){
// 先读取一数
sum=x;
n=1;
while(1){ ch=cin.get();
if(ch==10)
//遇到换行符跳出内循环
break;
cin>>x;
sum+=x;
n++;
}
cout << "Case " << ++i << ": "<< n << " " << sum << endl;
}
return 0;
}
方法2用串流类解决本问题：
为定义一个串流类对象，在头文件中增加
#include
定义串类型line：string line;
用getline()函数读取一行数据：getline(cin,line)；
然后定义一个串流类istringstream的对象iss对line中的数据进行分离 程序实现
#include
#include
#include
// 需要定义一个串流类对象
using namespace std;
int main(){
int x, n,i=0;
long sum;
string line;
cin>>n;
getline(cin,line); while(getline(cin,line)){
istringstream iss(line);
// 定义一个串流类的对象
sum = 0; n = 0;
while(iss >> x){
// 从串流类中读取数据
sum += x;
n++;
}
cout << "Case " << ++i << ": "<< n << " " << sum << endl;
}
return 0;
}