第一讲 简单程序设计
- 格式：doc
- 大小：198.00 KB
- 文档页数：19
1 第一讲 简单程序设计
一、计数器
1—100内有多少个奇数或偶数等等。
二、累加器
求1+2+„n等。
三、累乘器
求1*2*„n。
四、变量值的交换
1、引入第三个变量
2、迭代法
五、素数判断
判断某数是否为素数，哥德巴赫猜想等
六、最大公约数
1、根据定义求最大公约数
2、辗转相除法（迭代法）
七、最小公倍数
1、根据定义求解
2、最大公约数和最小公倍数的关系：2个自然数的最大公约数与最小公倍数的乘积等于这2个数的乘积。
八、平方数的表示
x:=trunc(sqrt(n));
if x*x=n then writeln('yes') else write('No');
九、数制转换
1、十进制数转换成其他进制数
2、其他进制数转换成十进制数。
实战练习：
1、有一个自然数被3,4,5除都余1,被7除余2,此数最小是几? [ 121 ]
2、求1+5+9+13+„101的和。
3、有一个两位数,加6后再把个位数与十位数互换,得到一个新的两位数,这样加6再互换共三次后,又得到了原来的两位数,求原来的两位数. [ 19, 52, 85 ]
4、把一个六位平方数截成两个三位数时,这两个三位数之差的绝对值是1(如573^2=328329),问这样的六位平方数共有哪些? [183184,328329,528529,715716 ]。
5、1994名同学按编号从小到大顺序排成一列，令奇数号（1，3„„）上的同学离队，余下的同学按原顺序不变，但进行重新编排成1，2，3„„的序号，再令其中站在新编号奇数号位上的同学离队，依次重复上面的要求，那么最后留下的同学在一开始是排在第几号位上。
6、市赛21届第一题
求出1000以内的整数，使其数字之和为13，每行输出8个数。
例如：数85，其数字之和为8+5=13数373，其数字之和为3+7+3=13
VIJOS上的题目： 2 第二讲 排序算法
一、选择排序
算法思想：把八个数（任意个）待排序的数存在A（1）——A（n）中，先从这几个数中找出一个值最小的数，然后将其与A（1）中的值进行互换，于是这几个数中的最小数就已经按“升序”排列的要求放在了其应放的位置A（1）中，接着再在余下的几个数中找出它们中的最小数放入A（2）中，依次类推，直到第七个数选择出来后剩下的第八数就是最大的数，这样从A（1）到A（n）已经按“升序”排列好。
二、冒泡排序
算法思想：
对1至n个记录，先将第n个和第n-1个记录的键值进行比较，如r[n].key
三、插入排序
算法思想：
类似于整理扑克牌。
1、先将第1张牌抓在手中，这时手上只有一张牌，显然它是有序的；
2、接着再抓入下一张牌，并使手中的两张牌保持有序（升序）；
3、以此类推，不断地抓入新牌并使所有牌保持有序直到全部抓完。
任务分解：
1、抓牌（第I张牌）
2、找插入点
3、插入点到第I张牌之间牌全部后移（腾出位置）
4、插入抓来的牌
四、希尔排序
算法思想：
先取一个步长STEP，使要排序数据按此步长STEP有序，然后步长STEP减半，再使要排序数据按此步长排序，直至步长为1有序。
未排数据：44 55 12 42 94 18 6 67
步长STEP=4
3
五、快速排序
快速排序是冒泡排序的改进，这是目前所有排序方法中速度最快的一种，在冒泡排序中数据的比较和交换是在相邻单元中进行，每次的交换吸上移或下移一个单元，因而总的比较次多，在快速排序中，数据的比较和交换是从两端向中间进行的，一次就可以交换定位两个单元的数据，总的比较次数和交换次少。
它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数 4 据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。
具体实现过程描述如下：
1）设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）重复第3、4步，直到I=J；
例如：待排序的数组A的值分别是：（初始关键数据X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
进行第一次交换后： 27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找
进行第二次交换后： 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )
进行第三次交换后： 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后： 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )
此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于49的数全部在49的后面，所有小于49的数全部在49的前面。
程序实现：
const n=10;
var a:array[1..n]of integer;
k,l.m:integer;
procedure qsort(l,r:integer);
var i,j,x,y:integer;
begin
I:=L;j:=r;x:=a[(L+r) div 2];
repeat
while a[i]
while a[j]>x do dec(j);
if I<=j then begin
y:=a[i];a[i]:=a[j];a[j]:=y;inc(i);dec(j); end; 5 until I>j;
if L
if I
End;
begin
for m:=1 to n do read(a[m]);
k:=0;L:=0;
qsort(1,n);
for m:=1 to n do write(a[m],’ ’);
writeln;
readln
end.
六、计数排序
算法描述：
计数排数的思想是若待排序的记录的关键字在一个明显的有限范围内（整型）时，可设计一个数组，出现与数组下标值一样的数，该下标的数组元素值加1（用于统计某个数出现的次数），最后扫描整个数组，根据统计的信息输出一个有序数列。
例：输入n个0~100之间的不相同整数，由小到大排序输出。
const n=7;
var b:array[0..100]of integer;
k:0..100;
i:integer;
begin
for i:=0 to 100 do b[i]:=0;{初始化}
for i:=1 to n do
begin
read(k);
b[k]:=b[k]+1;{将关键字等于K的值统计到数组b[k]中}
end;
for i:=0 to 100 do
while b[i]>0 do {某个数出现几次就输几个}
begin
write(i:4);
b[i]:=b[i]-1;
end;
writeln;
end.
七、归并排序
所谓归并排序是指将二个或二个以上有序的数列，合并成一个仍然有序的数列。这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。
基本思想：
1、假设已经有二个有序数列，分别存放在二个数组s，r中；并设有i，j分别为指向数组的第一个单元的下标；s有n个元素，r有m个元素；
2、再设另一个数组a，k指向该数组的第一个单元下标； 6 3、把s，r中的数据按顺序放入数组a中。
程序实现：
procedure merge(s,r,a,i,j,k);
begin
i1:=i;j1:=j;k1:=k;
while (i1
if s[i1]<=r[j1] then
begin a[k]:=s[i1];inc(i1);inc(k); end
else
begin a[k]:=r[j1];inc(j1);inc(k);end;
while i1<=n do begin a[k]:=s[i1];inc(i1);inc(k);end;
while j1<=m do begin a[k]:=r[j1];inc(j1);inc(k);end;
end;
实战练习：
题目：允许并列的排名
在我们参加的各种竞赛中，允许并列的排名方式是经常遇到的。
例如有四名选手的成绩分别为50、80、50、30分，则80分的选手为第一名，50分的两名选手均为第二名，30分的选手为第四名。
请编写一个程序，计算一个选手在这种排名方式之下的名次（分数高的选手排前面）。
输入格式 Input Format
文件名：RANK.IN
文件第一行为一个整数N，表示参赛的选手数，1≤N≤100 ，第二行为N个整数，表示每位选手的成绩，第三行为一个整数m，表示要查询名次的选手的成绩。
输出格式 Output Format
文件名：RANK.OUT
文件中只有一个整数，表示该选手的名次。
样例输入 Sample Input
4
50 80 50 30
50
样例输出 Sample Output
2
