Welcome-球速体育编程算法新手自学手册

　　球速体育

　　已经毕业了，我正在为应聘做准备。今天看当地报纸的招聘版时，一条感兴趣的招聘启示展现在我眼前：

　　Wisdom：“对，投简历是进入职场的开始，面试成功后将拉开读者们职场的序幕。而作为本书的内容，接下来将开始讲解9大算法思想，也拉开了本书核心内容学习的序幕。”

　　枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。

　　我国古代数学家在《算经》中有一道题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”意为：公鸡每只5元，母鸡每只3元，小鸡3只1元。用100元钱买100只鸡，问公鸡、母鸡、小鸡各多少？

　　算法分析：很显然，可以使用枚举法解决这个问题。我们以三种鸡的个数为枚举对象（分别设为mj,gj,xj），以三种鸡的总数（mj+gj+xj）和买鸡用去的钱的总数(gj*5+mj*3+xj/3)为判定条件，穷举各种鸡的个数。

　　在下面的算式中，添加“+”、“—”、“×”、“÷”四个运算符，使等式成立。

　　算法分析：上述算式由5个数字构成，一共需要填入4个运算符，并且每两个数字之间的运算符有四种选择，分别是“+”、“—”、“×”、“÷”。在编程中，可以通过循环来填入各种运算符，然后再判断算式是否成立。并且保证当填入除号时，其右侧的数不能是0，并且“×”、“÷”运算符的优先级高于“+”、“—”。

　　用枚举法解题的最大的缺点是运算量比较大，解题效率不高。如果枚举范围太大（一般以不超过两百万次为限），因为效率低的问题会在时间上难以承受。但枚举算法的思路简单，无论是程序编写和还是调试都很方便。所以如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。

　　递推算法是一种简单的算法，功能是通过已知某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止。

　　（1）顺推法：是指从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。

　　（2）逆推法：是从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

　　斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。

　　母亲为儿子小Sun的4年大学准备了一笔存款，方式是整存零取，规定小Sun每月月底取下一个月的生活费。现在假设银行的年利息为1.71%，请以计算机的方式计算母亲最少需要存入多钱？

　　递归算法是一种直接或者间接地调用自身的算法。在计算机编程应用中，递归算法对解决一大类问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。

　　（3）递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。

　　学校里有三个柱子，第一个有64个盘子，从上往下盘子越来越大。老师要求学生A1把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。

　　阶乘(factorial)是基斯顿·卡曼(ChristianKramp，1760–1826)于1808年发明的运算符号。阶乘也是数学里的一种术语。阶乘指从1乘以2乘以3乘以4持续乘到所要求的数。

　　分治算法是指，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。我们只要求出子问题的解，就可得到原问题的解。

　　使用递归求解：12×45，求得12×45的解果左移两位补0右边，因为实际上是120×450。

　　1和4：交叉相乘并将结果相加，1×4左移两位为400，1×5左移一位为50，2×4左移一位为80，2×5不移为10。

　　算法思想：根据分治算法思路，将所有参赛队伍分为两半，则n队的比赛日程表可以通过n/2个队的比赛日程来决定。然后继续按照上述一分为二的方法对参赛队进行划分，直到只剩余最后2队时为止。

　　假设n队的编号为1，2，3，……，n，比赛日程表制作为一个二维表格，每行表示每队所对阵队的编号。

　　设有编号为0，1，…，n-1的n种物品，体积分别为v0，v1，…，vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0≤i＜n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装下这些n种物品的箱子数要尽量少。

　　编写一段程序实现超市找零方案，只需输入需要补给顾客的金额，然后通过程序计算该金额可以由哪些面额的人民币组成。

　　八皇后问题是一个古老而著名的问题，是试探法的典型例题。该问题由十九世纪数学家高斯1850年手工解决：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

　　假设有一种彩票，每注由7个1~29的数字组成，且这7个数字不能相同，编写程序生成所有的号码组合。

　　根据时空的特点，将复杂的问题划分为相互联系的若干个阶段，在选定系统行进方向之后，逆向从终点向始点计算，逐次对每个阶段寻找某种决策，使整个过程达到最优，所以又称为逆序决策过程。

　　所谓字符序列的子序列，是指从给定字符序列中随意去掉若干个字符后所形成的字符序列，这里的若干可能一个也不去掉。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。

　　迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

　　在C语言中，通常使用srand()和rand()函数生成随机数。其中函数srand()用于初始化随机数发生器，然后使用函数rand()来生成随机数。如果要使用上述两个函数，则需要在源程序头部包含time.h文件。

　　用计算机实现一个随机1-100之间的数字，然后由用户来猜这个数，根据用户猜测的次数分别给出不同的提示。

　　要求根据用户输入骰子数量和参赛人数，然后由计算机随机生成每一粒骰子的数量，再累加得到每一个选手的总点数。

　　（1）事后统计法：缺点是必须在计算机上实地运行程序，容易被其他因素掩盖算法本质；

　　（2）事前分析估算法：优点是可以预先比较各种算法，以便均衡利弊而从中选优。

　　面试是进入职场的必经步骤，程序员也不例外。面试结果直接决定了你能否进入应聘公司，所以也决定了你的前途。既然面试这么重要，本文将介绍一些程序员面试过程中的经验和技巧，希望对广大读者有用。