必背经典算法(pascal)

算法设计初步与典型试题枚举搜索 (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——100这一百个相继整数的和S。

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

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

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

2 单入口、单出口。

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

4 书写格式清晰。

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

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

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

二、快速幂算法与分治思想(底下部分的^表示乘方)求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*但是,怎么找这个点呢*我们可以在这个树里面,随机一个点,但是是有可能得出无解我们这时候,只要找出”树的重心”即可这个树的重心可以百度得到……。