Posts Tagged CLRS
关于给定数组元素的随机化排列
Posted by kingsamchen in PROGRAMMING on 2010 年 07 月 23 日
前几天在看CLRS的时候，碰到这样一个题目，题目描述从下
Description：给定一个有序数组（升序/降序），数组大小为n，且包含满足[1,n]的整数，例如A[4]={1,2,3,4}
请设计一个算法，使得该算法能够将数组A中的元素随机化排列，例如算法作用后，数组A[4]={4,2,3,1}
算法应该能够接受数组作为参数，且效率尽可能高（这点是自己加的，个人觉得这样的算法应该包含在一个函数中）
问题初看之下似乎有点无聊，但是仔细分析后可以发现，这种算法可以作为很多游戏随机初始化的模型，比如纸牌游戏的初始化
这道问题的重点在于，如何正确并且有效的利用原有的数据生成均匀随机排列（uniform random permutation）
但是很不幸，很多我们能够想到并且认为是对的算法并不能生成真正的均匀随机排列。他们虽然能够产生看上去随机的排列，但是这些排列只能算是made in china
接下来，我们会针对几种有效或者是容易产生误区的算法做一些简单分析
首先我们要确定最基础的一点，即如何产生满足[min, max)的随机数
很多人看完上面之后，可能都会不屑的认为，既然是随机化数组，那么范围根本用不着上面那个范围，而应该是[0,nCount)，那么只需要简单的
srand(static_cast<int>(time(NULL))); int nRand = rand() % (nCount - 1);
我们先不讨论应该用哪个范围的问题，先说说这段代码，这段代码的结果的确能返回[0,nCount)的随机数，但是这些随机数显然不是均匀的，思考一下rand()返回的范围，很容易发现，不同随机数出现的概率是不同的
Read the rest of this entry »
一到弱智算法题
Posted by kingsamchen in PROGRAMMING on 2010 年 07 月 16 日
本来是希望丢在CFAN活跃气氛的，但是目前而言效果未达预期
题目很弱智，很简单，难度几乎没有～
题目描述:有一个数组A[0...n]含有从0到n的所有整数，但由于某些不明真相的原因，致使其中一个整数不存在于数组中，另一个整数发生了重复
例：A[5] = {0, 1, 3, 4, 4, 5}
(a).请设计一个算法，该算法能够在O(n)的复杂度内找到缺失的整数
(b).请设计一个算法，该算法能够在O(n)的复杂度内找到重复的整数
以上两个算法都接受数组和数组大小两个作为参数
后来在我发帖几分钟后，LA童鞋给出了他的答案
//[厦门一中] leap.ahead
#include <iostream>
using namespace std;
int length = 0;
long int t = 0;
short hash[100000] = { 0 };
int main()
{
cin >> length;
for(int i = 0; i < length; i++)
{
cin >> t;
if(hash[t] != 1)
{
hash[t] = 1;
}
else
{
cout << t;
return 0;
}
}
return 0;
}
和另一题的答案
Read the rest of this entry »
主定理和递归式复杂度分析
Posted by kingsamchen in PROGRAMMING on 2010 年 07 月 14 日
几个约定：文中为了方便，用logn代替log2n.
由于文章公式用LaTeX处理，所以不排除出现漏打，错打等情况，如您发现，麻烦通知，thx
1.前情提要
众所周知，递归是算法的一个重要表现形式，不仅作用大，而且其复杂度的分析也比其他方式要繁杂。
但是，如果抛开某些很NB，很强大，很邪恶的递归式不谈，如果不能有效的确定普通递归式和一些典型算法递归式的复杂度，那么这个人显然不是合格的Coder。
由于递归式复杂度的难以确定，所以目前常用的方法有这么几种：代换猜测法、递归树法、主定理、直接数学分析法
代换猜测法通常和递归树法合用，利用递归树法得到一个大概正确的结果，然后利用数学归纳法对其验证。
直接的数学分析法相对很直接，很强大，但是对数学要求很高，尤其是碰到一些BT的表达式
主定理是最常用的方法，也是我们今天的主题～
主定理通常可以解决如下的递归表达式：
[latex]T\left(n\right)=aT\left (\frac{n}{b} \right )+f\left(n \right)[/latex]
上面的递归式描述的是将规模为n的问题划分为a个子问题，并且每个子问题的规模是n/b，这里a和b是正常数。划分原问题和合并结果的代价有函数f(n)描述。
Read the rest of this entry »
吐几个槽
Posted by kingsamchen in CODE LIFE on 2010 年 07 月 14 日
CLRS很不容易的看到了第四章，递归式的复杂度分析，真是说有多牛X就有多牛X，很多证明的我直接skip。主定理乍看之下也是莫名其妙，无尽的杯具啊
给TPL（TopLanguageGroup）发了封申请mail，并以主定理的一个问题作为申请条件，结果到现在都没有一个明确的reply，估计直接被Deny了，又是一个杯具
第三个杯具是，这文章本来是应该昨晚写的，但是Blog的新服务器似乎很不稳定，动不动就宕，老子刚换服啊….
如果能稳定点，速度还是可以令人满意的，我就怕不稳定～
嗯，就是这么多了
LICENCE
COMMENTS