算法+数据结构=程序
数据结构:对数据的描述。在程序中要指定用到哪些数据,以及这些数据的类型和数据的组织形式。
算法:对操作的描述。即要求计算机进行操作的步骤
什么是算法?
广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。 对同一个问题,可以有不同的解题方法和步骤。 为了有效地进行解题,不仅需要保证算法正确,还要考虑算法的质量,选择合适的算法。
分为数值运算算法和非数值运算算法
数值运算算法:数值运算的目的是求数值解。 由于数值运算往往有现成的模型,可以运用数值分析方法,因此对数值运算的算法的研究比较深入,算法比较成熟。
非数值运算算法:计算机在非数值运算方面的应用远超在数值运算方面的应用。 非数值运算的种类繁多,要求各异,需要使用者参考已有的类似算法,重新设计解决特定问题的专门算法。
简单算法举例
1、求1×3×5×7×9×11
S1: 令p=1,或写成1=>p(表示将1存放在变量p中)
S2: 令i=3,或写成=>i(表示将3存放在变量i中)
S3: 使p与i相乘,乘积仍放在变量p中,可表示为: p*i=>p
S4: 使i的值加2,即i+2=>i
S5: 如果i不大于11,返回重新执行S3及其后的步骤S4和S5;否则,算法结束。
2、有50个学生,要求输出成绩在80分以上的学生的学号和成绩
【n:表示学生学号,ni:表示第i个学生的学号,g:表示学生的成绩,gi:表示第i个学生的成绩】
S1: 1=>i
S2: 如果gi≥80,则输出ni和gi,否则不输出
S3: i+1=>i
S4: 如果i≤50,返回到S2,继续执行,否则,算法结束。
3、判定2000年——2500年中每一年是否为闰年,并将结果输出
S1: 2000=>year
S2: 若year不能被4整除,则输出year 的值和“不是闰年”。然后转到S6,检查下一个年份
S3: 若year能被4整除,不能被100整除,则输出year的值和“是闰年”。然后转到S6
S4: 若year能被400整除,输出year的值和“是闰年” ,然后转到S6
S5: 输出year的值和“不是闰年”
S6: year+1=>year
S7: 当year≤2500时,转S2继续执行,否则算法停止
4、求1-1/2+1/3+···+1/99-1/100
【sign:表示当前项的数值符号,term:表示当前项的值,sum:表示当前项的累加和,deno:表示当前项的分母】
S1: sign=1
S2: sum=1
S3: deno=2
S4: sign=(-1)*sign ;分母为二时符号为-,后一项与前一项符号相反
S5: term=sign*(1/deno)
S6: sum=sum+term
S7: deno=deno+1
S8: 若deno≤100,则返回S4;否则算法结束。
5、给出一个大于或等于3的正整数,判断它是不是一个素数
解题思路: 所谓素数(prime),是指除了1和该数本身之外,不能被其他任何整数整除的数。
S1: 输入n的值
S2: i=2(i作为除数)
S3: n被i除,得余数r
S4: 如果r=0,表示n能被i整除,则输出n“不是素数”,算法结束;否则执行S5
S5: i+1=>i
S6: 如果i≤n-1,返回S3;否则输出n的值以及“是素数”,然后结束
(S6可改进为i≤√n,返回S3,···)
算法的特性
- 有穷性:一个算法应包含有限的操作步骤,而不能是无限的
- 确定性:算法中的每一个步骤都应当是确定的,而不应当是含糊的、模棱两可的
- 有零个或多个输入:所谓输入是指在执行算法时需要从外界取得必要的信息
- 有一个或多个输出:算法的目的是为了求解,“解” 就是输出
- 有效性:算法中的每一个步骤都应当能有效地执行,并得到确定的结果
算法的表示
- 自然语言
- 传统流程图
- 结构化流程图
- 伪代码
用流程图表示算法
1、求1×3×5×7×9×11
2、有50个学生,要求输出成绩在80分以上的学生的学号和成绩
3、判定2000年——2500年中每一年是否为闰年,并将结果输出
4、求1-1/2+1/3+···+1/99-1/100
5、给出一个大于或等于3的正整数,判断它是不是一个素数
三种基本结构
三种基本结构的特点
- 只有一个入口
- 只有一个出口
- 结构内的每一部分都有机会被执行到
- 结构内不存在“死循环”
用N-S流程图表示算法
用伪代码表示算法
伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章一样,自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号,因此书写方便,格式紧凑,修改方便,容易看懂,也便于向计算机语言算法(即程序)过渡。
1、求5!,用伪代码表示。
算法分析:
S1: 1=>p
S2: 2=>i
S3: p*i=>p
S4: i+1=>i
S5: 如果i≤5,则返回S3;否则结束
伪代码表示:
begin (算法开始)
1=>p
2=>I
while i≤5
{ p*i=>p
i+1=>I
}
print p
end (算法结束)
计算机语言(C语言)表示:
#include <stdio.h>
int main()
{
int i,p;
p=1;
i=2;
while(i<=5)
{
p=p*i;
i=i+1;
}
printf(″%d\n″,p);
return 0;
}
2、求1-1/2+1/3+···+1/99-1/100
算法分析:
【sign:表示当前项的数值符号,term:表示当前项的值,sum:表示当前项的累加和,deno:表示当前项的分母】
S1: sign=1
S2: sum=1
S3: deno=2
S4: sign=(-1)*sign ;分母为二时符号为-,后一项与前一项符号相反
S5: term=sign*(1/deno)
S6: sum=sum+term
S7: deno=deno+1
S8: 若deno≤100,则返回S4;否则算法结束。
伪代码表示:
begin (算法开始)
1=>sign
1=>sum
2=>deno
while deno≤100
{ (-1)*sign=>sign
sign*(1/deno)=>term
sum+term=>sum
deno+1=>deno
}
print sum
end (算法结束)
计算机语言(C语言)表示:
#include <stdio.h>
int main()
{
int sign=1;
double deno=2.0,sum=1.0,term;
while(deno<=100)
{
sign=-sign;
term=sign/deno;
sum=sum+term;
deno=deno+1;
}
printf(″%f\n″,sum);
return 0;
}
结构化程序设计方法
- 自顶而下
- 逐步细化
- 模块化设计
- 结构化编码