tianshuai11
- 浏览: 143574 次
-
最新评论
文章列表
一，组合数学问题
1）排列定义
• 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。
•排列的全体组成的集合用P(n,r)表示。当r=n时称为全排列。
组合定义
• 定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。
- 2012-05-06 21:08
- 浏览 508
- 评论(0)
题目：设计一个高效算法，求两个等长为L的升序序列A和B
的中位数。
例如：S1=（11,13,15,17,19）
S2=（2,4,6,8,20）
则S1和S2的中位数是11。
1）问题分析1：
简单的算法是将两个升序序列归并排序，然后求其中位数
算法的时间复杂度和空间复杂度均为0(n)
2）问题分析2
- 2012-05-06 16:56
- 浏览 588
- 评论(0)
一，例题：找出n个自然数(1,2,3,…,n)中r个数的组合。
•例如，当n=５,r=3时，所有组合为：
12 3 1 2 4
12 5 13 4
13 5 14 5
23 4 23 5
24 5 34 5
total=10 {组合的总数}
•算法设计
1）n个数中r的组合，其中每r个数中，数不 ...
- 2012-05-06 16:12
- 浏览 655
- 评论(0)
面试过程中，面试官会向应聘者发问，而应聘者的回答将成为面试官考虑是否接受他的重要依据。对应聘者而言，了解这些问题背后的“猫腻”至关重要。
问题一：“请你自我介绍一下”
思路：
1、这是面试的必考题目。
2、介绍内容要与个人简历相一致。
3、表述方式上尽量口语化。
- 2012-05-06 14:09
- 浏览 594
- 评论(0)
一，问题由来
货郎担问题也叫旅行商问题，即TSP问题（Traveling Salesman Problem），是数学领域中著名问题之一。
二，问题描述
1）货郎担问题提法：有n个城市，用1，2，…，n表示，城i,j之间的距离为dij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短？
2）旅行商问题的提法：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
三，问题 ...
- 2012-05-04 15:25
- 浏览 659
- 评论(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
- 浏览 570
- 评论(0)
•
问题描述：
残缺棋盘是一个有2k×2k（k≥1）个方格的棋盘，其中恰有一个方格残缺。如图给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。
• 残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求：
1）两个三格板不能重叠
2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。
小格子数（2k×2k -1）三格板中小格子数3。所以所需要的三格板总数为(2k×2
- 2012-05-03 18:51
- 浏览 1885
- 评论(0)
一，词法分析器的作用
词法分析是编译的第一阶段。词法分析器主要任务是读入源程序的输入字符、将他们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素。
分析部分：词法分析、语法分析（简化编译器设计、提高编译器效率、增强编译器可移植性）
1）词法单元：词法单元名和可选的属性值组成。关键字、操作符……
2）模式：词法单元词素可能具有的形式，当词法单元是关键字时，模式就是这个关键字的字符序列
3）词素：源程序中的一个字符序列，它和某个词法单元模式匹配。
4）词法错误：识别出某个错误词素，继续判断下一个词素
二，输入缓冲
...
- 2012-05-02 11:03
- 浏览 658
- 评论(0)
一，词法分析器
作用：读取源程序的输入字符、将他们组成词素，生成并输出一个词法单元序列
二，设计原理
1）C程序语言的符号分类：关键字、标识符、常数、运算符、界符
2）词法分析器的二元输出：<单词种别，单词符号属性值>
3）正规式和状态转换图
4）程序说明：
1>main 中打开源码文件，从第一个字符流读取
2>如果第一个是字符，则交给letterprocess(str); 处理
3>如果第一个是数字，则交给numbe ...
- 2012-05-01 21:36
- 浏览 963
- 评论(0)
组合数学中的全排列生成算法历来是组合数学考试的重要考察点，因此在这里我简单的介绍一下6种全排列生成算法的详细过程，并借此比较它们之间的优劣之处。
不论是哪种全排列生成算法，都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。其中中介数依据算法的不同会的到递增进位制数和递减进位制数。关于排列和中介数的一一对应性的证明我们不做讨论，这里仅仅给出了排列和中介数的详细映射方法。相信熟练掌握了方法就可以顺利通过这部分的考察。
递增进位制和递减进位制数
所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见到的都是固定进制数字，如2进制 ...
- 2012-04-28 15:28
- 浏览 1379
- 评论(0)
一，最大子矩阵问题：
给定一个n*n(0<n<=100)的矩阵，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最大，输出这个最大的值。
Example：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
其中左上角的子矩阵：
9 2
-4 1
-1 8
此子矩阵的值为9+2+(-4)+1+(-1)+8=15。
二，分析
子矩阵是在矩阵选取部份行、列所组成的新矩阵。
例如
- 2012-04-23 17:13
- 浏览 583
- 评论(0)
一，题目：
最大子段和：
给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的和sum＝a[i]+a[i+1]+……+a[j]最大，其中i>=0,i<n,j>=i,j<n
例如：31 -41 59 26 -53 58 97 -93 -23 84
子矩阵59+26-53+58+97=187为所求的最大子数组。
二，源码
第一种：直接穷举法:
#include <iostream>
using namespace std;
int main()
{
int a[10]={31, -41, 59, ...
- 2012-04-23 15:13
- 浏览 629
- 评论(0)
一，题目：
生产者消费者线程演示 一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列
二，分析：
这一个，为操作系统上的一个经典例子，以下是july给出的解答
三，源码：
- 2012-04-22 23:14
- 浏览 544
- 评论(0)
序言：大家是不是莫名其妙，我怎么什么都搀和上两脚。搞起这个高深的COM编程来了。呵呵……这是帮同学做的一个小东西，由于以前拿这个比赛过，今天由于业务需要又用上了，所以又拉我来做一下这个。都是兄弟，放下手中的活帮哥们做了。
需求：在IE菜单中，添加右键。点击右键调用javaScript，执行相应功能。
步骤：以管理员身份打开VS2005，新建ATL工程，
动态获取当前位置，并写入注册表中
void OnChange()
{
WCHAR buf[128];
GetCurrentDirectory(128,(LPTSTR)buf);
...
- 2012-04-22 15:45
- 浏览 668
- 评论(0)
一，题目
给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
例如：1******3***2 ,12*****3这些都要找出来 生活中，比如输入：法你轮和功 会被和谐的
二，分析： 自然匹配就是对待匹配的每个字符挨个匹配，设你的待匹配字串长度位n,模式字符串长度位m。对于待匹配字符串中的任意一个字符最坏情况下要匹配m次，也就是说这个字符不在模式字符串中。所以最坏情况下总共是m*n此匹配，时间复杂度就是O(m*n)
倘若使用hash表对待字符串进行hash处理O(n)的
- 2012-04-22 15:34
- 浏览 776
- 评论(0)