浙江省诸暨市高二信息技术《算法考试记忆部分》知识点整理.doc

浙江省诸暨市高二信息技术《算法考试记忆部分》知识点整理
截取整数X的各个位：(X\K)mod10(k=1,10,100,1000……)
用随机函数RND取[a，b）的整数：int(Rnd*(b-a)+a)
A为B的倍数：AmodB=0
A为奇数：Amod2=1
冒泡排序1(有n个元素的数组，将其从小到大排序)
Fori=1ton-1‘用于控制排序的趟数
Forj=1ton-i‘用于控制每趟的比较次数
Ifa(j)>a(j+1)then
Temp=a(j) ‘第三者插足法交换数据
a(j)=a(j+1)
a(j+1)=temp
endif
next
next
冒泡排序2(有n个元素的数组，将其从小到大排序)
Fori=1ton-1‘用于控制排序的趟数
Forj=ntoi+1step-1‘用于控制每趟的比较次数
Ifa(j)<a(j-1)then
Temp=a(j) ‘第三者插足法交换数据
a(j)=a(j-1)
a(j-1)=temp
endif
next
next

选择排序1(有n个元素的数组，将其从小到大排序)
Fori=1ton-1‘用于控制排序的趟数
Forj=i+1ton‘用于控制每趟的比较次数
Ifa(i)>a(j)then
Temp=a(j) ‘第三者插足法交换数据
a(j)=a(i)
a(i)=temp
endif
next
next

选择排序2(有n个元素的数组，将其从小到大排序){改进型}
Fori=1ton-1‘用于控制排序的趟数
max=i
Forj=i+1ton‘用于控制每趟的比较次数
Ifa(max)>a(j)thenmax=j
endif
next
ifmax<>ithen
Temp=a(max) ‘第三者插足法交换数据
a(max)=a(i)
a(i)=temp
endif
next

顺序查找（对于一个数组a共有n个元素，找到其个数key）
i=1:found=false
dowhilei<=nandnotfound
ifa(i)=keythen‘当前项不所要找的则让下一项来测试
found=true
else
i=i+1
endif
loop

对分查找（对于一个有序数组a共有n个元素，如为从小到大，找到其个数key）
i=1:j=n:found=false
dowhilei<=jandnotfound
m=int((i+j)/2)
ifkey=a(m)then
found=true
elseifkey>a(m)then
i=m+1
else
j=m-1
endif
loop

穷举法（枚举法）有二个方程式求三个未知量，其方程式如下：
X+y+z=a
K1*x+k2*y+K3*z=bx,y，z属于自然数
Forx=x1tox2‘x的取值范数为x1至x2
Fory=y1toy2‘y的取值范数为y1至y2
Z=a-y-b
IfK1*x+k2*y+K3*z=bandz>0then
得到一组解用list控件输出
Endif
Next
Next

递归算法：如一个台阶20个其上台阶的方法有上一个台阶，也可上一个台阶的，求20个台阶的上法
Functionf(nasinteger)asinteger
Ifn=1then‘递归的结束条件
F=1
Elseifn=2then‘递归的结束条件
F=2
Else
F=f(n-1)+f(n-2)‘递归的公式
Endif
Endfunction

求N！。N！=N*（N-1）！（N-1）！=（N-1）*（N-2）！……1！=0，0！=1
Functionfa(nasinteger)aslong
Ifn<=1then‘递归的结束条件
fa=1
Else
fa=n*fa(n-1)
Endif
Endfunction

函数的调用如调用上例中的N！y=fa(n)