必背经典算法(pascal)

具体计算过程如下： S1： K = 4 有 F4（D1）= 3， F4（D2）= 4， F4（D3）= 3； S2： K = 3 有 F3（C1）= MIN{ D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2）} = MIN{ 5+3，6+4 } = 8 F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8 F3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11 F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6 S3： K = 2 有 F2（B1）= MIN{ D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2）， D2（B1，C3）+ F3(C3)} = MIN{ 1+8,6+8,3+11} = 9 F2（B2）= MIN{ D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4）} = MIN{ 8+8，4+6 } = 10 S4： K = 1 有 F1（A）= MIN{ D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2）} = MIN{ 5+9，3+10} = 13 因此由A点到E点的全过程最短路径为A→B2→C4→D3→E；最短路程长度为13。 从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距离 当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。 在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策 依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的， 故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。

100
trunc(-100.5) -100
trunc(-100.4) -100
結果 2.75
2 3
單元減法~
將負號放在數字前的運算稱為否定，這種運算只需要一 個操作數。 例如:-7的意思是7的負數
運算的優先順序~
優先次序 最高 高 低
運算符 - (單元減法或否定)
* / div mod +-
1~較高優先次序的運算會在較低的運算之前執行 2~具有相同優先次序的運算符會從左至加順序執行 3~括號可以改變運算的次序，括號內的表達式會首先運算~
運算 加法 減法或單元減法 乘法 實數除法 整數除法 模數
加法和減法~
由普通的加號[+]和減號[-]來表示，運算的方式與 數學的相同。
乘法~
乖法時，必須使用[*]，例子:A乘B時應寫成A*B [+]~ [-]~ [*]可以在實數或整數數據中使用，當所
有操作數都是整數時，結果亦是整數。另外， 當操作數是實數，結果也是實數。
我們可以將In和exp組成一條公式，以計算答案。
Xy:=exp(y*In(x))
其中x必須是正的實數或整數
函數調用
結果
trunc (x) 截斷函數trunc回送實數變元的整數部份， 並以整數表示，任合小部份都會被截去。 變元實際上會被捨入至最接近零的整數。
trunc (100.5但是即使在無需要時,我們亦可以使用拾號~ 目的只是為了使優先次序更清晰，但不會改變這次序~
●~賦值語句~○
語法----<變量> := <表達式>
<變量>是用來表示值的標識符。 <表達式>可以是(1)常量值
(2)已經貯有值的另一個變量 (3)將要計算的公式 [:=]稱為賦值符號,意思是[取其值]，而在兩個符號中間是沒有空格的。 在一句賦值語句中，被賦值的變量必須放在賦值符號的左邊，放在友邊 的表達式會被首先運算，然後結果會貯在左邊的變量中。 例子: A:=5;

算法设计初步与典型试题枚举搜索 (4)1、枚举数字 (5)3、百钱买百鸡 (5)4、分书问题 (6)逻辑判断 (7)5、谁是小偷 (7)6、质量评比 (7)7、谁获冠军 (8)8、四大淡水湖 (9)递推法 (10)9、【菲波纳葜数列】 (10)10、递推关系的应用“杨辉三角” (10)11、蜜蜂爬行 (11)13、铺骨牌（2000年全国联赛初赛） (12)倒退 (13)14、贮油点 (13)枚举素数 (14)15、素数 (14)16、歌德巴赫猜想 (15)17、计算真因子 (16)筛法 (17)18、求素数（95年，全国联赛初赛） (17)19、用筛法统计楼梯级数 (18)最大公约数与最小公倍数 (19)20.求两个正整数的最大公约数 (19)21、求两个正整数的最小公倍数 (19)进制转换 (21)22、十进制转换为n进制 (21)23. N进制数转化为十制数 (22)循环问题 (23)24、猴子选大王 (23)25、狐狸捉兔子 (24)26、约瑟环 (25)数组 (25)27、求递增和递减子序列 (27)28、马鞍数 (28)29、数学黑洞6174 (29)方阵填数 (30)30、方阵填数 (30)31、蛇形矩阵： (31)字符数组与字符串 (32)一、定义 (32)二、字符串的常用内部函数和过程 (33)三、字符数组与字符串应用 (33)36、寻找单词 (36)37、【题目】从键盘输入一个长度不超过40的字符串,按要求进行删除. (37)数组与字符串应用 (38)38、高精度加法程序 (38)39、回文算术 (39)递归算法 (41)40、利用递归调用手段编程计算N!。

(42)41、利用递归调用技术求菲波纳葜数列的第N项。

(42)42、输入一串以‘.’结束的字符，按逆序输出。

(44)43、用递归函数求最大公约数 (44)44、汉诺塔 (45)嵌套 (47)45、三齿轮问题 (47)搜索算法（回溯、深度优先） (48)46、八皇后问题 (48)47、求N个数的全排列 (49)48、跳马问题（骑士遍历） (50)49、深度优先搜索解分书问题 (53)50、四色问题。

pascal三角形选法-回复什么是[pascal三角形选法]？Pascal三角形选法是一种用于组合数学中的计算方法，以法国数学家布莱兹·帕斯卡（Blaise Pascal）的名字命名。

这个方法可以用来计算组合数，即从一个给定的集合中选取固定数量元素的方式数目。

在Pascal三角形中，每一行的数字都是通过相邻上一行的数字计算得到的。

具体计算方法为，每个数字等于上一行对应位置数字与它的左上方数字之和。

这样，Pascal三角形便呈现出一种对称的形状，每一行的数字在从左到右和从右到左的数值分布上都是对称的。

该选法可以通过直接查找Pascal三角形中的数字来计算组合数。

例如，如果要计算从一个集合中选取3个元素的组合数，可以在第4行（从0开始计数）中找到对应位置的数字，并将其作为结果。

如何应用[pascal三角形选法]？首先，要利用这个选法，我们需要构建一个Pascal三角形。

构建Pascal 三角形的方法是，将上一行的相邻两个数字相加，将其和作为下一行相应位置的数字。

开始时，我们可以将第一行的数字设置为1，并依次计算后续行的数字。

这样，我们就可以得到一个完整的Pascal三角形。

接下来，我们可以使用构建好的Pascal三角形来计算组合数。

假设我们要计算从一个集合中选取r个元素的组合数。

我们可以在Pascal三角形中的第r+1行（从0开始计数）找到对应位置的数字，这个数字就是我们要的结果。

举个例子来说明。

假设我们有一个集合{1, 2, 3, 4, 5, 6, 7, 8}，我们要从中选取3个元素的组合数。

首先，我们构建一个Pascal三角形。

第一行：1第二行：1 1第三行：1 2 1第四行：1 3 3 1由于我们要选择3个元素，所以我们需要查找Pascal三角形中的第4行。

从左往右数第3个数字是3，所以从给定集合中选取3个元素的组合数为3。

这就是Pascal三角形选法的基本思想和应用方法。

为什么要使用[pascal三角形选法]？Pascal三角形选法提供了一种简洁且高效的计算组合数的方法。

• 高精度运算的思想就是运用字符串和一维数组的方式 模拟运算 • 口诀就是:用字符串读入数据，转化数据类型,用数组 存储数据,并加以运算：
高精度运算涉及到的问题：
1、数据的输入。 2、数据的存储。
3、数据的运算：进位。
4、结果的输出：小数点的位置、处理多余的0等。
高精度加法
题目要求： 输入： 第一行：正整数a。 第二行：正整数b。已知：a和b（<10240）。
思考、高精度减法运算
问题表述： 输入a，b（<10240）两个数，输出a-b的值。
样例1输入： 456 409 样例1输出： 47
样例2输入： 999 1000 样例2输出： -1
F(i):第i个月后共有的兔子对数。 F(1)=1; F(2)=1; f(3)=2; f(4)=3; f(5)=5; f(6)=8;
F(i)=f(i-2)+f(i-1)
{N<=93} var f:array[1..100] of longint; var n,i:integer; begin readln(n); f[1]:=1; f[2]:=1; for i:=3 to n do f[i]:=f[i-2]+f[i-1]; writeln(f[n]); end.
处理进位： for i:=1 to len do begin c[i+1]:=c[i+1]+c[i] div 10; c[i]:=c[i] mod 10; end;
４、结果的输出：数组c。
if c[len+1]>0 then len:=len+1; for i:=len downto 1 do write(c[i]);
继续思考
a,b:array[1..maxn] of integer; 在前面的运算中我们定义数组中的数字为 integer类型的值，但是我们知道integer的 值数字可以表示-32000到+32000之间的数 字，是否有些浪费？

//求无向图割顶的算法，割顶：若在图的dfs树上，i 存在儿子节点 s ，使得 s 及 s 的所有子孙的后向边不指向 i 的祖先（可以指向i），输出的是一个点I，尝试写成过程，然后找到其应用
ary(多进制2-16转十进制).pas
program ary;
var a:array [1..10000] of longint;
program ary;
var a:array [1..10000] of longint;
k:array [1..10000] of char;
s,j,b,t:longint;
begin
readln(s);
readln(b);
while s<>0 do
begin
'B':a[j]:=11;
'C':a[j]:=12;
'D':a[j]:=13;
'E':a[j]:=14;
'F':a[j]:=15;
end;
inc(j);
end;
for i:=1 to j do
if a[i]>=b then
for k:=1 to n do if (i<>k)and(j<>k)then
if (a[i,j]<>maxlongint)and(d[i]<>maxlongint)and(d[j]>d[i]+a[i,j])then
d[j]:=d[i]+a[i,j];
for i:=1 to n do
begin
case a[j] of

begin readln(n); readln(m); count:=0; for i:=1 to n div 2 do begin k:=1; a[1]:=i; try(n-i); end; end.
算法的缺点？ 改进优化？
5、骑士的游历
设有下图所示的一个棋盘，在棋盘上的A(0,0)点有一个中国象棋马，并 约定马走的规则： 1、马只向右走； 2、马走“日“字。 找出所有从A到B的路径。 3
var n,m,k,i,count:integer; a:array[1..100] of integer; procedure print(i,x:integer); var j:integer; begin inc(count); write(count,':',n,'='); for i:=1 to k do write(a[i],'+'); writeln(x); end; procedure try(x:integer);{x是第k+1项} var i,j:integer; begin if k<=m-1 then print(k,x); if k>=m then exit;{剪枝优化} for j:=a[k] to x div 2 do if (j>=a[k])and(x-j>=j) then begin inc(k); a[k]:=j; try(x-j); dec(k); end; end;
4、输出解： procedure print; var j:integer; begin count:=count+1; write(count,':'); for j:=1 to n-1 do write(x[j],' '); writeln(x[n]); end;

算法：
算法是程序的基础。

有了一个好的算法，再进行编码，把算法转换成任何一个程序设计语言所表示的程序。

算法就是解题步骤。

例题：求1——100这一百个相继整数的和S。

解法一：s=1+2+3+……+100 【需要100-1次加法】
解法二：s=（1+100）*50 【需要加法、乘法、除法各一次】不同的算法，对计算的工作量造成重大影响，还要考虑算法对精确度的影响。

程序质量的高低，主要取决于算法。

结构化程序特点：
1按功能相对独立原则划分若干模块。

2 单入口、单出口。

3 强调三种基本结构组成（顺序、选择、循环性）。

4 书写格式清晰。

5 不包含无限循环（即执行时间是有限的）
6 没有死语句（即程序中所有语句都能得到执行的机会）
设计结构化程序方法：
1 自顶向下
2 逐步细化。

3 按“功能单一”原则划分模块。

program maopaosort;
可见，其时间复杂度也是O(n2)
const mx=10000; var
d:array[1..mx]of longint;
的。不难发现，如果某趟排序 中没有发生交换，就意味着任
n,i,j,k:longint; begin
readln(n);
意两个相邻元素都是有序的， 那么全部元素就已经有序了。
此时第n个数据已经是最大的了，下面对前N-1个数据重复 这个过程，又将次大的数据放到了第n-1个位置。一般地，第i 趟冒泡排序是对第1个到第n-i+1个数据进行操作，选出原序列 第i大的数据放到数组的第n-i+1位置。重复这个过程，直到i=n1为止。
初始关键字：[225 220 41 190 242 185 42 231] 第一趟排序后：[220 41 190 225 185 42 231] 242 第二趟排序后：[41 190 220 185 42 225] 231 242 第三趟排序后：[41 190 185 42 220] 225 231 242 第四趟排序后：[41 185 42 190] 220 225 231 242 第五趟排序后：[41 42 185] 190 220 225 231 242 第六趟排序后：[41 42] 185 190 220 225 231 242 第七趟排序后：[41] 42 185 190 220 225 231 242
排序算法
1、选择排序 2、冒泡排序 3、插入排序 4、快速排序
什么是排序？ 排序是处理数据过程中一种很常用的运算，是将一
组原本无序的数据元素，通过一定的方法，按照某个域 的值（关键字）递增或递减的次序重新排列的过程。
下面主要讨论几种常见的内排序算法： 选择排序、冒泡排序、插入排序、快速排序。

第九讲 分治算法一、分治思想分治思想融入于常见算法的各个角落，简单点说，所谓的分治,实际上是将一个问题拆成若干个小问题,将它们分别解决后,就等价于解决了整个问题。

二、快速幂算法与分治思想(底下部分的^表示乘方)求2^233(mod 1,000,000,007)这个问题我们可以这么考虑2^233 = 2^116 * 2^116 * 2那么原来问题就转化为求2^116(mod 1,000,000,007)就这样下去,我们只要求得2^52即可,也就是说2^26即可换句话说,我们求得2^13即可,也就是说2^6 * 2^6 * 22^6 = 2^3 * 2^32^3 = 2^1 * 2^1 * 2 = 8所以2^6 = 8*8=642^13 = 2^6 * 2^6 * 2 = 64 * 64 * 2 = 8192就这样…我们逐步回推,可以得到2^233当然注意要取模*你可以说这个算法是递归,但是这个也可以说是”拆成若干个小问题”*三、一道NOIP2007的例题本题摘自NOIP 2007 普及组初赛(完善程序第二题) 大家可以暂时思考一下本题中,我们只要求构造一种方案所以,这个题我们可以采取分治的策略来解决首先,我们思考一下,这一题的特殊条件1,我们用的是2的k次方*2的k次方的格子2,这一题中,有一个”-1”的存在那么,我们就可以用一种特殊的策略首先,如果k=0,那么……就不用构造了,皆大欢喜所以,我们想办法将2^k改为2^(k-1)即可我们可以将原来的正方形切成四个,如右图所以,这时候,我们可以将三个”1”当作-1,带入到右上,右下,左下处理,将”-1”依旧留在左上角这样,问题就转化成了一个2^(k-1)规模的然后..(本图中为了较为清晰的显示,将13~16与18~21略去了)所以,这样就将原来问题分治出来了那么,这一个问题就得到了解决四、一道来自codeforces的例题这一题摘自Codeforces 321C题面:英文版:C. Ciel the Commandertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputNow Fox Ciel becomes a commander of Tree Land. Tree Land, like its name said, has n cities connected byn - 1 undirected roads, and for any two cities there always exists a path between them.Fox Ciel needs to assign an officer to each city. Each officer has a rank — a letter from 'A' to 'Z'. So there will be 26 different ranks, and 'A' is the topmost, so 'Z' is the bottommost.There are enough officers of each rank. But there is a special rule must obey: if x and y are two distinct cities and their officers have the same rank, then on the simple path between x and y there must be a city z that has an officer with higher rank. The rule guarantee that a communications between same rank officers will be monitored by higher rank officer.Help Ciel to make a valid plan, and if it's impossible, output "Impossible!".InputThe first line contains an integer n (2 ≤ n ≤ 105) — the number of cities in Tree Land.Each of the following n - 1 lines contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) — they mean that there will be an undirected road between a and b. Consider all the cities are numbered from 1 to n.It guaranteed that the given graph will be a tree.OutputIf there is a valid plane, output n space-separated characters in a line — i-th character is the rank of officer in the city with number i.Otherwise output "Impossible!".Examplesinput41 21 31 4outputA B B Binput101 22 33 44 55 66 77 88 99 10outputD C B A D C B D C DNoteIn the first example, for any two officers of rank 'B', an officer with rank 'A' will be on the path between them. So it is a valid solution.中文题意:给你n个点,求构造一个方案,使得每个点存在一个’A’到’Z’的权值任意两个权值为x(x从’A’到’Z’)的点之间,一定存在至少一个权值比x大的点如果无解,输出”Impossible!”注意:’A’比’B’~’Z’大,’B’比’C’~’Z’大……’Y’比’Z’大如果不懂,可以观察样例所以,这道题我们该怎么做呢?我们仔细观察‘A’是最大的,也就是说,最多只有一个’A’那么我们每次选一个点,将它当作最大的点,然后,将它的其他部分”解离”也就是说,将它的其他部分分开处理这样,就可以解决了这题红点为A,然后将绿色点当B/C*但是,怎么找这个点呢*我们可以在这个树里面,随机一个点,但是是有可能得出无解我们这时候,只要找出”树的重心”即可这个树的重心可以百度得到……。

（迭起来有：望有界：1function CPAIR2(S);beginif |S|=2 then δ:=S中这2点的距离else if |S|=0then δ:=∞else begin1. m:=S中各点x坐标值的中位数;构造S1和S2，使S1={p∈S|px≤m}和S2={p∈S|px>m}2. δ1:=CPAIR2(S1);δ2:=CPAIR2(S2);3. δm:=min(δ1,δ2);4. 设P1是S1中距垂直分割线l的距离在δm之内的所有点组成的集合，P2是S2中距分割线l的距离在δm之内所有点组成的集合。

将P1 和P2中的点依其y坐标值从小到大排序，并设P1*和P2*是相应的已排好序的点列;5. 通过扫描P1*以及对于P1*中每个点检查P2*中与其距离在δm之内的所有点(最多6个)可以完成合并。

当P1*中的扫描指针逐次向上移动时，P2*中的扫描指针可在宽为2δm的一个区间内移动。

设δl是按这种扫描方式找到的点对间的最小距离;6. δ=min(δm,δl);end;return(δ);end;下面我们来分析一下算法CPAIR2的计算复杂性。

设对于n个点的平面点集S，算法耗时T(n)。

算法的第1步和第5步用了O(n)时间，第3步和第6步用了常数时间，第2步用了2T(n/2)时间。

若在每次执行第4步时进行排序，则在最坏情况下第4步要用O(n log n)时间。

这不符合我们的要求。

因此，在这里我们要作一个技术上的处理。

我们采用设计算法时常用的预排序技术，即在使用分治法之前，预先将S中n个点依其y坐标值排好序，设排好序的点列为P*。

在执行分治法的第4步时，只要对P*作一次线性扫描，即可抽取出我们所需要的排好序的点列P1*和P2*。

然后，在第5步中再对P1*作一次线性扫描，即可求得δl。

因此，第4步和第5步的两遍扫描合在一起只要用O(n)时间。

这样一来，经过预排序处理后的算法CPAIR2所需的计算时间T(n)满足递归方程：显而易见T(n)=O(n log n)，预排序所需的计算时间为O(n1og n)。

1.快排procedure quicksort(l,r:longint);{从L到R排序}vari,j,mid:longint;begini:=l;{首标记}j:=r;{尾标记}mid:=a[ (l+r) div 2];{中间值}repeatwhile a[i]<mid do inc(i);{找到不合顺序的a[i]}while a[j]>mid do dec(j);{找到不合顺序的a[j]}if i<=j then begin{交换}swap(a[i],a[j]);inc(i);dec(j);end;until i>j;if l<j then quicksort(l,j);{递归，排L到j之间的数}if i<r then quicksort(i,r);{递归，排L到j之间的数}end;2.高精度加法：typehp=array[0..200] of longint;procedure g_jia_g(a,b:hp;var c:hp);varlen,i:longint;beginfillchar(c,sizeof(c),0);if a[0]>b[0] then len:=a[0] else len:=b[0];{len=答案的长度}for i:=1 to len do{加的过程}beginc[i]:=a[i]+b[i]+c[i];if c[i]>=10 then begin{进位}c[i]:=c[i]-10;c[i+1]:=c[i+1]+1;end;end;c[0]:=len+1;{判断最高位是否进位}f c[len+1]=0 then c[0]:=c[0]-1;end;3.压位高精度加法typehp=array[0..200] of longint; {每个单位存100000000之内的数（1*10^8，即1后8个0）}procedure init;{读入的过程}begina[0]:=(l1-1) div 8+1;{第一个加数的长度}b[0]:=(l2-1) div 8+1;{第二个加数的长度}for i:=1 to l1 do{读入加数a的过程}a[(l1-i) div 8+1]:= a[(l1-i) div 8+1]*10+ord(s1[i])-48;for i:=1 to l2 do{读入加数b的过程}b[(l2-i) div 8+1]:=b[(l2-i) div 8+1]*10+ord(s2[i])-48;end;procedure hiadd(a,b:hp;var c:hp);beginfillchar(c,sizeof(c),0);if a[0]>b[0] then c[0]:=a[0] else c[0]:=b[0];{加数长度}for i:=1 to c[0] do{加的过程}c[i]:=c[i]+a[i]+b[i];for i:=1 to c[0] do{进位}begininc(c[i+1],c[i] div 100000000);c[i]:=c[i] mod 100000000;end;if c[c[0]+1]>0 then inc(c[0]);{判断最高位是否有进位}end;procedure print;{输出过程}beginwrite(c[c[0]]);{输出最高位}for i:=c[0]-1 downto 1 dobeginif c[i] div 10000000=0 then write(0);if c[i] div 1000000=0 then write(0);if c[i] div 100000=0 then write(0);if c[i] div 10000=0 then write(0);if c[i] div 1000=0 then write(0);if c[i] div 100=0 then write(0);if c[i] div 10=0 then write(0);write(c[i]);end;end;4.高精度乘法typehp=array[0..200] of longint;procedure g_cheng_g(a,b:hp;var c:hp);varlen,i,j:longint;beginfillchar(c,sizeof(c),0);for i:=1 to a[0] do{累乘+进位过程}for j:=1 to b[0] dobeginc[i+j-1]:=c[i+j-1]+a[i]*b[j];c[i+j]:=c[i+j]+c[i+j-1] div 10;c[i+j-1]:=c[i+j-1] mod 10;end;len:=a[0]+b[0]+1;{结果长度}while (c[len]=0) and (len>1) do dec(len);{判断最高位是否为零} c[0]:=len;end;5.压位高精度乘法typehp=array[0..200] of longint;procedure init;{读入过程}begina[0]:=(l1-1)div 4+1;{加数a的长度}b[0]:=(l2-1)div 4+1;{加数b的长度}for i:=1 to l1 do{读入a}a[(l1-i)div 4+1] :=a[(l1-i)div 4+1]*10+ord(s1[i])-48;for i:=1 to l2 do{读入b}b[(l2-i)div 4+1] :=b[(l2-i)div 4+1]*10+ord(s2[i])-48;end;procedure yacheng(a,b:hp;var c:hp);beginfillchar(c,sizeof(c),0);for i:=1 to a[0] do{累乘+进位过程}for j:=1 to b[0] dobeginc[i+j-1]:=c[i+j-1]+a[i]*b[j];c[i+j]:=c[i+j]+c[i+j-1] div 10000;c[i+j-1]:=c[i+j-1] mod 10000;end;c[0]:=a[0]+b[0]-1;{最高位是否进位}while c[c[0]+1]>0 dobegininc(c[0]);c[c[0]+1]:=c[c[0]+1]+c[c[0]] div 10000;c[c[0]]:=c[c[0]] mod 10000;end;end;procedure print;{输出过程}beginwrite(c[c[0]]);for i:=c[0]-1 downto 1 dobeginif c[i] div 1000=0 then write(0);if c[i] div 100=0 then write(0);if c[i] div 10=0 then write(0);write(c[i]);end;end;6.二分法查找procedure found(x,top,last:longint);{从top与last之间找x（a数组必须有序）} beginif top<=last thenbeginmid:=(top+last) div 2;{中间的下标}if x=a[mid] then writeln(mid){找到了}else if x<a[mid] then found(x,top,mid-1){在前面}else found(x,mid+1,last);{在后面} endelse writeln('not found');{a中没有x}end;7.斐波那契数列function f(x:longint):longint;{输出斐波那契中的第x项}beginif x=0 then f:=0else if x=1 then f:=1else if x=2 then f:=1else f:=f(x-1)+f(x-2);end;8.判断素数function pdss(x:longint):boolean;vari:longint;beginif (x=0) or (x=1) then exit(false);{0和1不是素数}if (x=2) or (x=3) then exit(true);{2和3是素数}for i:=2 to trunc(sqrt(x)) doif x mod i =0 then exit(false);exit(true);end;9.分解质因数成表格形式{2——2 3——1 5——1 =2*2*3*5=60}procedure fat(x:longint;var a:arr;var s:longint);begini:=1; {最小的因子}s:=0;repeatinc(i);{因子加1}if x mod i=0 thenbegininc(s);{标记加1}a[s,1]:=i;{因子}a[s,2]:=0;{因子个数清零}while x mod i=0 do begin inc(a[s,2]); x:=x div i; end;{去除该因子} end;until x=1;end;10.十进制化二进制procedure s_e(n:longint);{除2取余法}vari:longint;begin{1770}read(n);i:=0;while n<>0 dobegina[i]:=n mod 2;i:=i+1;n:=n div 2;end;end.11.最大公约数function gcd(a,b:integer):integer;beginif b=0 then gcd:=aelse gcd:=gcd (b,a mod b);{辗转相除法}end;12.最小公倍数function lcm(a,b:integer):integer;beginif a<b then swap(a,b);lcm:=a;while lcm mod b>0 do inc(lcm,a);end;13.全排列procedure solve(dep:integer);var i:integer;beginif dep=n+1 thenbeginwriteln(s);exit;end;for i:=1 to n doif not used[i] thenbegins:=s+chr(i+ord('0'));used[i]:=true;solve(dep+1);s:=copy(s,1,length(s)-1);used[i]:=false;end;end;14.背包DPprogram bb2;varxk,n,i,j:longint;w,c:array[1..100] of longint;f:array[0..101,0..100001] of longint;function max(x,y:longint):longint;beginif x>y then exit(x) else exit(y);end;beginassign(input,'bb2.in');assign(output,'bb2.out');reset(input);rewrite(output);readln(xk,n);for i:=1 to n doreadln(w[i],c[i]);{f[i,j] 第i个物品，重量是j 的最大价值}fillchar(f,sizeof(f),0);for i:=1 to n dofor j:=1 to xk doif j>=w[i] then f[i,j]:=max( f[i-1,j] , f[i-1,j-w[i]]+c[i] )else f[i,j]:=f[i-1,j];write(f[n,xk]);close(input);close(output);end.。

end;
3、归并排序
program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
i:integer;
procedure merge(r:arr;l,m,n:integer;var r2:arr);
a[i+d]:=t;
end;
end;
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
程序2:(子序列是冒泡排序)
program xepx;
const n=7;
type
arr=array[1..n] of integer;
while (i<n) and bool do
begin
bool:=false;
for j:=n downto i+1 do
if a[j-1]<a[j] then
begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t;bool:=true end;
for i:=1 to n do write(a[i]:6);
writeln;
end.
i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
writeln;
for i:=2 to n do
begin
k:=a[i];j:=i-1;

Pascal经典教程（1—3章）⽆论做任何事情，都要有⼀定的⽅式⽅法与处理步骤。

计算机程序设计⽐⽇常⽣活中的事务处理更具有严谨性、规范性、可⾏性。

为了使计算机有效地解决某些问题，须将处理步骤编排好，⽤计算机语⾔组成“序列”，让计算机⾃动识别并执⾏这个⽤计算机语⾔组成的“序列”，完成预定的任务。

将处理问题的步骤编排好，⽤计算机语⾔组成序列，也就是常说的编写程序。

在Pascal语⾔中，执⾏每条语句都是由计算机完成相应的操作。

编写Pascal程序，是利⽤Pascal语句的功能来实现和达到预定的处理要求。

“千⾥之⾏，始于⾜下”，我们从简单程序学起，逐步了解和掌握怎样编写程序。

程序结构和基本语句在未系统学习Pascal语⾔之前，暂且绕过那些繁琐的语法规则细节，通过下⾯的简单例题，可以速成掌握Pascal程序的基本组成和基本语句的⽤法，让初学者直接模仿学习编简单程序。

[例1.1]编程在屏幕上显⽰“Hello World!”。

Pascal程序：Program ex11;BeginWriteln(‘Hello World!’);ReadLn;End.这个简单样例程序，希望⼤家的程序设计学习能有⼀个良好的开端。

程序中的Writeln是⼀个输出语句，它能命令计算机在屏幕上输出相应的内容，⽽紧跟Writeln语句后是⼀对圆括号，其中⽤单引号引起的部分将被原原本本地显⽰出来。

[例1.2]已知⼀辆⾃⾏车的售价是300元，请编程计算a辆⾃⾏车的总价是多少？解：若总售价⽤m来表⽰，则这个问题可分为以下⼏步处理：①从键盘输⼊⾃⾏车的数⽬a；②⽤公式 m=300*a 计算总售价；③输出计算结果。

Pascal程序：Program Ex12; {程序⾸部}Var a,m : integer; {说明部分}Begin {语句部分}Write(‘a=’);ReadLn(a); {输⼊⾃⾏车数⽬}M := 300*a; {计算总售价}Writeln(‘M=’,m); {输出总售价}ReadLn; {等待输⼊回车键}End.此题程序结构完整，从中可看出⼀个Pascal 程序由三部分组成:(1)程序⾸部由保留字Program开头，后⾯跟⼀个程序名(如:Exl1)；其格式为:Program 程序名；程序名由⽤户⾃⼰取，它的第⼀个字符必须是英⽂字母，其后的字符只能是字母或数字和下划线组成，程序名中不能出现运算符、标点符和空格。

图20 倒推到第二步
为了在I=2处贮藏1000公升汽油，卡车至少从I=3处开三趟满载油的 车至I=2处。所以I=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。 加上I=2至I=3处的二趟返程空车，合计5次。路途耗油亦应500公升，即 d23=500/5， Way[3]=Way[2]+d23=Way[2]+500/5； 此时的状况如图21所示。
(1 n) * (1 m) * n * m s=(1+2+┉┉+n)*( 1+2+┉┉+m)= 4
3.长宽不等的长方形个数s2 显然，s2=s-s1
(1 n) * (1 m) * n * m = 4
min{m, n}1 i 0
(n i ) * (m i )
由此得出算法： program ex7_3; var m,n,m1,n1,s1,s2:longint; begin readln(m,n); m1:=m;n1:=n; s1:=m1*n1; while (m1<>0)and(n1<>0)do begin m1:=m1-1;n1:=n1-1; s1:=s1+m1*n1; end; s2:=((m+1)*(n+1)*m*n) div 4-s1; writeln(s1,' ',s2); end.
//计算正方形的个数s1
// 计算长方形的个数s2
【例4】贮油点
一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油 能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途 建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？ 每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？（结 果保留小数点后两位） 编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存 油量。格式如下： No. Distance(k.m.) Oil(litre)

四、穷举法应用
穷举法
begin e:=15-a-b-c-d;b0:=(e<>2) and (e<>3); m:=bton(e=1)+bton(b=2)+bton(a=5)+bton(c<>1)+bton(d=1); b0:=b0 and (m=-2); b1:=(e=1) and (a<>2); b1:=b1 or (a=5) and(c<>1) and(c<>2); b1:=b1 or (c<>1) and (d<>1) and (d<>2); b1:=b1 or (d=1) and (e<>2); b0:= ; if b0 then writeln('a=',a:2,' b=',b:2,' c=',c:2,' d=',d:2,' e=',e:2); x[d]:=true; end;
穷举法
算法分析：程序只能采用穷举法,一一验证范围内的数是否阿姆斯特朗数,若是则打印之。
一、引入
算法描述： for I:=100 to 9999999 do begin 验证是否是阿姆斯特朗数，若是则输出； end;
穷举法
一、引入
实例二：从键盘输入一个正整数N，验证其是否为质数，若是则输出“YES”，否则输出“NO”。
五、如何优化穷举算法
穷举法
实例五：邮票面值。 问题描述：邮局发行一套票面有四种不同值的邮票，如果每封信所贴邮票张数不超过三枚，存在整数Ｒ，使得用不超过三枚的邮票，可以贴出连续的整数１、２、３，…，Ｒ来，找出这四种面值数，使得Ｒ值最大。

动态规划（一）
• 0-1背包 • 完全背包 • 乘法问题 • 数塔问题 • 装箱问题
动态规划（二）
• 最长上升序列（LIS） • 最长公共子串（• 归并排序 • 最近点对问题 • 求最大子序列和的O(nlogn)算法 • Hanoi塔问题及其变种 • 棋盘覆盖问题 • 循环赛日程表问题
贪心
• 最优装载问题 • 部分背包问题 • 独立区间的选择 • 覆盖区间的选择 • 区间的最小点覆盖 • 点的最小区间覆盖
递推
• Fibonacci数的若干应用 • Catalan数的若干应用 • 拆分数 • 差分序列
数据结构（二）
• ★平衡二叉树 • ★树状数组 • ★线段树 • ★块状链表
排列与组合
• 生成所有排列 • 生成所有组合 • 生成下一个排列 • 生成下一个组合
计算几何（一）
• 计算斜率 • 计算点积 • 计算余弦 • 计算平面两点的距离 • 计算空间两点的距离 • ★计算广义空间两点的距离 • 判断三点是否共线
语言与计算机
• 递归调用 • 向前引用 • 随机化 • 指针类型 • 按位运算
排序（一）
• 冒泡排序（起泡排序） • 选择排序 • 插入排序 • ★ Shell排序 • 快速排序
排序（二）
• 线性时间排序 • 查找第k大元素 • 带第二关键字的排序
数论（一）
• 素性判断 • 筛选建立素数表 • 分解质因数 • 进制转换 • 二分取幂 • ★二分求解线性递推方程
图论：二分图
• 验证二分图 • 匈牙利算法 • ★KM算法 • ★稳定婚姻系统
树
• 求树的最短链 • 二叉树的四种遍历 • 已知先序中序求后序 • 已知中序后序求先序 • ★已知先序后序求中序 • ★LCA问题的Tarjan离线算法 • ★Huffman编码