文章列表
一.准备工作
“工欲善其事必先利其器。”
1.电脑不一定要配置高，但是双屏是必须的，越大越好，能一个横屏一个竖屏更好。一个用来查资料，一个用来写代码。总之要显得信息量很大，效率很高。
2.椅子不一定要舒 ...
- 2012-05-05 22:08
- 浏览 660
- 评论(0)
一，算法策略应用
1）关于背包问题
按与利润关系划分
•与利润无关的背包问题
•与利润有关的背包问题
按物体装入背包的多少
•部分背包问题
•0-1背包问题
2）背包问题的求解策略，根据不同的需求
•贪心法、回溯法、分支限界法、动态规划
• 递归或非递归求解
二，背包问题展示
1）背包问题1
•
问题描述：给定n种物品，从中选出m件，使其重量之和与T之差的绝对值为最小。
例如：n=9，m=3，T=500克。
• 问题分析1：采用三重循环，枚举法。
数据变化过程：
(1,2,3) (1,2,4) …(1,2,9)
( ...
- 2012-05-05 21:45
- 浏览 679
- 评论(0)
一，贪心算法的设计思想
•从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策,尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法停止。
二，贪心算法的基本性质
1）贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心法与动态规划法的主要区别。
2）最优子结构性质
该问题解的整体最优性依赖于其局部子问题解的最优性。这种性质是可以采用贪心算法解决问题的关键特征。例如，活动安排问题，在选择了一项活动后，它必须是最优的，否则不 ...
- 2012-05-04 17:08
- 浏览 869
- 评论(0)
一，问题描述
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
二，分析
采用逐步试探的方式，先从一个方向往前走，能进则进，不能进 ...
- 2012-05-04 16:49
- 浏览 621
- 评论(0)
一，问题由来
货郎担问题也叫旅行商问题，即TSP问题（Traveling Salesman Problem），是数学领域中著名问题之一。
二，问题描述
1）货郎担问题提法：有n个城市，用1，2，…，n表示，城i,j之间的距离为dij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短？
2）旅行商问题的提法：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
三，问题 ...
- 2012-05-04 15:25
- 浏览 1032
- 评论(0)
一 ，问题描述：
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
所谓01背包，表示每一个物品只有一个，要么装入，要么不装入。
二，解决方案：
考虑使用dp问题 求解，定义一个递归式 opt[i][v] 表示前i个物品，在背包容量大小为v的情况下，最大的装载量。
opt[i][v] = max(opt[i-1][v] , opt[i-1][v-c[i]] + w[i])
解释如下：
opt[i-1][v] 表示第i件物品不装入背包中，而opt[i-1][v-c[i]] + w[i] 表示第i件物品装入背 ...
- 2012-05-03 23:40
- 浏览 718
- 评论(0)
•
问题描述：
残缺棋盘是一个有2k×2k（k≥1）个方格的棋盘，其中恰有一个方格残缺。如图给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。
• 残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：
1）两个三格板不能重叠
2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。
小格子数（2k×2k -1）三格板中小格子数3。所以所需要的三格板总数为(2k×2
- 2012-05-03 18:51
- 浏览 856
- 评论(0)
一，迭代与递推
1）迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。迭代算法一般用于数值计算。迭代法应该是我们早已熟悉的算法策略，程序设计语言课程中所学的累加、累乘都是迭代算法 ...
- 2012-05-03 16:55
- 浏览 795
- 评论(0)
一，概述
算法策略和算法是有区别的,它们是算法设计中的两个方面，算法策略是面向问题的,算法是面向实现的；
但二者又是不可分的,首先是通过算法策略才找出解决问题的算法，其次对于用不同算法求解的问题算法策略是自然不同的。
二，算法策略
1）递推策略：“递推法”和贪心算法一样也是由当前问题的逐步解决从而得到整个问题的解，只是依赖的是信息间本身的递推关系，每一步不需要策略参与到算法中，它们更多地用于计算。
2）递归策略：递归法是利用大问题与其子问题间的递归关系来解决问题的。每次找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问 ...
- 2012-05-03 09:51
- 浏览 704
- 评论(0)
一，词法分析器的作用
词法分析是编译的第一阶段。词法分析器主要任务是读入源程序的输入字符、将他们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素。
分析部分：词法分析、语法分析（简化编译器设计、提高编译器效率、增强编译器可移植性）
1）词法单元：词法单元名和可选的属性值组成。关键字、操作符……
2）模式：词法单元词素可能具有的形式，当词法单元是关键字时，模式就是这个关键字的字符序列
3）词素：源程序中的一个字符序列，它和某个词法单元模式匹配。
4）词法错误：识别出某个错误词素，继续判断下一个词素
二，输入缓冲
...
- 2012-05-02 11:03
- 浏览 815
- 评论(0)
一，题目：
有n个长为m+1的字符串，如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
二，分析： 将各个字符串作为一个节点，首尾链接就好比是一条边，将两个节点连接起来，于是问题就变成一个有关图的路径长度的问题。链接所得的字符串最长长度即为从图的某个节点出发所能得到的最长路径问题，与最短路径类似，可以应用弗洛伊德算法求解。对于循环，即可认为各个节点通过其他节点又回到自己，反应在路径长度上，就表示某个节点到自己节点的路径大于零（注：初始化个节点到自己的长度为零）。
三，源码
- 2012-05-01 23:14
- 浏览 644
- 评论(0)
一，词法分析器
作用：读取源程序的输入字符、将他们组成词素，生成并输出一个词法单元序列
二，设计原理
1）C程序语言的符号分类：关键字、标识符、常数、运算符、界符
2）词法分析器的二元输出：<单词种别，单词符号属性值>
3）正规式和状态转换图
4）程序说明：
1>main 中打开源码文件，从第一个字符流读取
2>如果第一个是字符，则交给letterprocess(str); 处理
3>如果第一个是数字，则交给numbe ...
- 2012-05-01 21:36
- 浏览 617
- 评论(0)
一，语法定义
1）文法：对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”），而未
涉及语义问题。
例：有一句子：“我是大学生” 。这是一个在语法、语义上都正确的句子， ...
- 2012-05-01 17:44
- 浏览 829
- 评论(0)
组合数学中的全排列生成算法历来是组合数学考试的重要考察点，因此在这里我简单的介绍一下6种全排列生成算法的详细过程，并借此比较它们之间的优劣之处。
不论是哪种全排列生成算法，都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。其中中介数依据算法的不同会的到递增进位制数和递减进位制数。关于排列和中介数的一一对应性的证明我们不做讨论，这里仅仅给出了排列和中介数的详细映射方法。相信熟练掌握了方法就可以顺利通过这部分的考察。
递增进位制和递减进位制数
所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见到的都是固定进制数字，如2进制 ...
- 2012-04-28 15:28
- 浏览 1181
- 评论(0)
一，语言处理器
1）一个集成的软件开发环境，其中包括很多种类的语言处理器，比如编译器、解释器、汇编器、连接器、加载器、调试器以及程序概要提取工具。
2）编译器：把源程序的每一条语句都编译成机器语言,并保存成 ...
- 2012-04-26 22:00
- 浏览 649
- 评论(0)