tianshuai11
- 浏览: 143396 次
-
最新评论
文章列表
【0-1背包】 问题描述：n件物品，第i件物品价值 v[i] 元，重w[i] 磅。希望用 W磅的书包 拿走总价值最贵的物品。(物品不可以分割故称为0-1背包)
【部分背包】问题描述：n件物品，第i件物品价值 vi 元，重wi 磅。希望用 W磅的背包 拿走最重的物品。第i件物品可以都拿走，也可以拿走一部分。（物品可以分割所以称为部分背包）
注意：0-1背包不能用贪心算法求解。
原因：按照贪心算法，每一次拿的都是每磅最贵的物品。由于物品大小不同，有可能每磅最贵的不是最合适大小的。最坏的情况可能导致，背包没有装满，而且当前装的也不是最优的。
例如：10磅 A 价值60￥ ； 20磅 ...
- 2011-11-29 23:23
- 浏览 806
- 评论(0)
平摊分析种类
1），聚集分析：n个操作所构成的序列的总时间在最坏情况下为T(n) 平摊代价为：T(n)/n
2），记账法:平摊代价高的操作，当做存储，用来补偿平摊代价低得操作。
3），势能法：平摊代价=实际代价+i点的势能-（i-1）点的势能
平摊分析总结
平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通过对所有操作求平均后，平均代价还是很小的。平摊分析与平均情况分析的不同之处在于它不牵涉到概率。这种分析保证了在最坏情况下每个操作具有平均性能。
- 2011-11-29 23:22
- 浏览 726
- 评论(0)
IP数据包也叫IP报文分组，传输在ISO网络7层结构中的网络层，它由IP报文头和IP报文用户数据组成，IP报文头的长度一般在20到60个字节之间，而一个IP分组的最大长度则不能超过65535个字节。
下图为IP分组的报文头格式，报文头的 ...
- 2011-11-29 23:22
- 浏览 1667
- 评论(0)
【1】 解决汉字输入法的问题
打开终端 sudo apt-get install scim-pinyin
sudoim-switch -s scim -z all_ALL #因为我用的英文local，所以要将scim设置为所有的locale的默认输入法
im-switch -s scim -z all_ALL#注意：不加sudo然后重启系统，生效。
【2】汉化系统菜单
1，打开屏幕上方的“system”(系统)，里面有个“Administration”(系统管理)，选择“Snaptic Package Manager”(软件包管理器)，打开，输入密码后进入软件包管理器，在里面找到Lan ...
- 2011-11-29 23:18
- 浏览 535
- 评论(0)
首先：++i效率高点。
原因是：++i 只是本身加1没有额外开辟空间，而i++需要建立额外对象。
前提：编译器没有做优化。
- 2011-11-29 23:18
- 浏览 339
- 评论(0)
一富豪到华尔街银行借了5000元贷款，借期为两周，银行贷款须有抵押，富豪用停在门口的劳斯莱斯做抵押。银行职员将他的劳斯莱斯停在地下车库里，然后借给富豪5000元。两周后富豪来还钱，利息共15元，银行职员发现富豪帐上有几百万，问为啥还要借钱，富豪说：15元两周的停车场，在华尔街是永远找不到的。
- 2011-11-29 23:17
- 浏览 438
- 评论(0)
微软面试试题可分为1 迷语2 算法3 应用程序4 智力等等
1.为什么下水道的盖子是圆的
第一，井口设在大路上，每天走路的人来人往，设计时就要注意行人的安全，盖儿不能掉到井里。如果设计成三角形或者正方形的，盖儿虽然比井口大一些，但还是有掉下去的可能。而如果是圆形的，由于圆的直径相等，所以，盖儿只要大一点点，就不会掉下去。
第二，由于井有时需要人工梳理或架线等，这时候又要求井的面积尽可能地大。在这些图形中，当它们的周长相等时，圆形的面积最大。同时圆形又符合我们的体型，便于工作人员进进出出。
第三，三角形或正方形的边由直的线段组成，构成的角较尖，如果在修理时碰到很容易使人受伤。而圆形的边是一 ...
- 2011-11-29 23:17
- 浏览 471
- 评论(0)
1， 管理方式：对于栈来讲，是由编译器自动管理，无需我们手工控制；对于堆来说，释放工作由程序员控制，容易产生memory leak。 （指针用栈，数组用堆）
2，空间大小：一般来讲在32位系统下，堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的。但是对于栈来讲，一般都是有一定的空间大小的，例如，在VC6下面，默认的栈空间大小是1M（好像是，记不清楚了）。当然，我们可以修改：
打开工程，依次操作菜单如下：Project->Setting->Link，在Category 中选中Output，然后在Reserve中设定堆栈的最大值和commit。
...
- 2011-11-29 23:16
- 浏览 636
- 评论(0)
1，“常量”与“只读变量”的区别
常量是编译器放在内存中的只读区域，“只读变量”在内存中开辟一个区域存放它的值，编译器限定不允许修改。
2，const与 define的区别
const:限定一个“变量”不允许被改变。可以提高程序安全性、可靠性。const编译时进行安全类型检查。“意味着只读” 错误：“意味着常量”
define 用来定义“常量”，编译结束后就消失了，不开辟内存空间。define 没有类型检查，只是单纯的替换，所以不够安全。
例子：const int n=5; int a[n]; 是不对的，原因是：数组长度必须要定义成常量。而const 修饰的是一个变量。但是 const ...
- 2011-11-29 23:16
- 浏览 333
- 评论(0)
<wbr> 1、什么是const?<br>
常类型是指使用类型修饰符const说明的类型，常类型的变量或对象的值是不能被更新的。（当然，我们可以偷梁换柱进行更新：）</wbr>
2、为什么引入const？
const 推出的初始目的，正是为了取代预编译指令，消除它的缺点，同时继承它的优点。
3、cons有什么主要的作用？
（1）可以定义const常量，具有不可变性。
例如：
const int Max=100;
int Array[Max];
（2）便于进行类型检查，使编译器对处理内容有更多了解，消除了一些隐患。
例如：
void ...
- 2011-11-29 23:15
- 浏览 587
- 评论(0)
内存分成5个区，他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
1，栈，就是那些由编译器在需要的时候分配，在不需要的时候自动清除的变量的存储区。里面的变量通常是局部变量、函数参数等。
2 ...
- 2011-11-29 23:15
- 浏览 587
- 评论(0)
现在流行的进程线程同步互斥的控制机制，其实是由最原始最基本的4种方法实现的：<wbr><wbr><wbr> 1临界区:通过对多线程的串行化,来访问公共资源或一段代码，速度快，适合控制数据访问。 <wbr><br>
2互斥量:为协调共同对一个共享资源的单独访问而设计的。 <wbr><br>
3信号量:为控制一个具有有限数量,用户资源而设计。 <wbr><br>
4事件:用来通知线程有一些事件已发生，从而启动后继任务的开始。<br><wbr><b ...
- 2011-11-29 23:14
- 浏览 595
- 评论(0)
常见的不不能声明为虚函数的有：普通函数(非成员函数);静态成员函数;内联成员函数;构造函数;友元函数。
1、为什么C++不支持普通函数为虚函数?
普通函数(非成员函数)只能被overload，不能被override，声明为虚函数也没有什么意思，因此编译器会在编译时邦定函数。
2、为什么C++不支持构造函数为虚函数?
这个原因很简单，主要是从语义上考虑，所以不支持。因为构造函数本来就是为了明确初始化对象成员才产生的，然而virtual function主要是为了再不完全了解细节的情况下也能正确处理对象。另外，virtual函数是在不同类型的对象产生不同的动作，现在对象还没有 ...
- 2011-11-29 23:14
- 浏览 350
- 评论(0)
1.static有什么用途？（请至少说明两种）
1)函数体内，声明为static的变量，在函数调用中其值不变。
2) 在同一个文件内（但在函数体外），声明为静态的变量，可被本文件内所有函数访问，但不能被模块外其它函数访问。它是一个本地的全局变量。
3) 在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是，这个函数被限制在声明它的模块的本地范围内使用
2.引用（ &）与指针（*）有什么区别？
1) 引用必须被初始化，指针不必。
2) 引用初始化以后不能被改变，指针可以改变所指的对象。
3) 不存在指向空值的引用，但是存在指向空值的指针。
4） 引用没有 ...
- 2011-11-29 23:13
- 浏览 688
- 评论(0)
POJ上的一些水题(可用来练手和增加自信)
(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)
初期:
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj ...
- 2011-11-29 23:12
- 浏览 589
- 评论(0)