线段树入门(zz)
Posted on 2010-08-29 21:22 MiYu阅读(184) 评论(0)编辑收藏引用所属分类: ACM_资料、ACM ( 数据结构)从简单说起，线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡，和静态二叉树一样，都是提前已经建立好的树形结构。针对性强，所以效率要高。这里又想到了一句题外话：动态和静态的差别。动态结构较为灵活，但是速度较慢；静态结构节省内存，速度较快。
接着回到线段树上来，线段树是建立在线段的基础上，每个结点都代表了一条线段[a , b]。长度为1的线段成为元线段。非元线段都有两个子结点，左结点代表的线段为[a , (a + b ) / 2]，右结点代表的线段为[( a + b ) / 2 , b]。
图一就是一棵长度范围为[1 , 10]的线段树。
长度范围为[1 , L] 的一棵线段树的深度为log ( L - 1 ) + 1。这个显然，而且存储一棵线段树的空间复杂度为O（L）。
线段树支持最基本的操作为插入和删除一条线段。下面已插入为例，详细叙述，删除类似。
将一条线段[a , b] 插入到代表线段[l , r]的结点p中，如果p不是元线段，那么令mid＝（l＋r）/2。如果a
插入（删除）操作的时间复杂度为O （ Log n ）。
上面的都是些基本的线段树结构，但只有这些并不能做什么，就好比一个程序有输入没输出，根本没有任何用处。
最简单的应用就是记录线段有否被覆盖，并随时查询当前被覆盖线段的总长度。那么此时可以在结点结构中加入一个变量int count；代表当前结点代表的子树中被覆盖的线段长度和。这样就要在插入（删除）当中维护这个count值，于是当前的覆盖总值就是根节点的count值了。
另外也可以将count换成bool cover；支持查找一个结点或线段是否被覆盖。
例题1（ZJU1610 Count The Colors线段树基本应用题目）给出在线段[0,8000]上的若干次涂色，问最后能看见哪些颜
色，并统计能看到多少段。
解析
就这个题目而言，方法很多，而且数据范围不大，但我们由线段树的角度来解决这个问题。
建立一棵代表线段[0,8000]的线段树，涂色操作就是将[a , b]涂成颜色c。最后做统计。
结构如下：
struct TNode {
int left , right;
int col;
TNode *LeftChild , *RightChild;
};
col 有几种情况，如果col为－1，代表了尚未涂色，－2代表了是混和色，就是说这条线段并不是单一的颜色。其他情况，便是这条线段都是这个颜色的了。
全部程序见附录1。
线段树的第一种变化
基本的线段树代表的是线段，如果我们把线段离散成点来看，那么线段树可以变化成一种离散类型线段树。
这里可以有两种理解。一种离散关系可以是连续的线段的点，比
方说在一条直线上放置的连续小球的着色问题；另一种则是完全将线段离散化分成若干小段，对每一段小段做为元线段来建立线段树，这种线段树可以支持实数划分类型的线段。
例题2（ZJU2451 Minimizing maximizer ）
Andy想要得到一组数中的最大值。会有一系列的操作Sorter(i[1], j[1]), ...,Sorter (i[k], j[k])。作用是将数组中的第i[k]个数字到第j[k]个数字排序。按照输入给出的顺序，你可以选择要不要执行这个操作。问题是最少需要多少步操作，可以求出这个最大值。题目保证可以求出。
多组数据。
第一行为两个数字N，M。表示N个数，M个操作。
接下来M行，每行描述一个操作i[k] , j [k]。
对于每组数据，输出最少需要多少次操作分离得到最大值。
每组数据一行。
解析
由于要将最大的数字分离到最后的一位，如果我们考虑将数组看成一条[1,n]的线段，而每项操作也看成是从[i[k],j[k]]的线段，那么就是要求按照输入的顺序，将线段[1,n]从左到右依次覆盖掉，问题变成求最小的覆盖线段总数。
考虑最基本的规划方法，用Opt [k] 表示覆盖掉 [1,k]的线
段最少需要的步数，那么状态转移方程为：
Opt [k] = min { Opt [d] + 1 | j [p] = k && d >= i [p] && d <= j [p] && k > 1 }
Opt [1] = 0;
最后的答案就是Opt [n]了，但是考虑时间复杂度，是O（m^2）级别的，m最大为500000，超时无疑。但是这里我们看到了规划的决策集合是一条连续的线段，是要在这条线段上面取得最小值，那么线段树的结构就正好适合在这里应用了。
由于这里最小的单位是一个点，所以我们采取线段树的第一种变化，把元线段设置为单位点，即[k,k]。在规划的时候维护线段树即可。
线段树结点结构中，需要加入的元素是int minstep 代表最少需要用到的覆盖线段数目可以覆盖到当前结点所代表的线段中。
全部程序见附录2。
例题3（PKU2104K-th Number）
给出一个大小为n的数组A[]，给出m个问题（1 <= n <= 100 000, 1 <= m <= 5 000）。问题格式为Q（i，j，k），询问从A[i]到A[j]第k大的元素是什么。A[]中的数各不相同。
解析
由于仍旧是离散的整数问题，我们依旧采取第一种变化。看到题
目，最基本的想法就是排序然后求第k个数了，但是时限上不能满足要求。
线段树的最强大方面就是将一组数（一条线段）放到一起处理。每层树需要的线段数目不会超过4，而深度为logn，所以最后操作的复杂度会是O(logn)。
但是仅仅应用线段树还是不够的，即使我们知道了需要处理的线段是那些，但是由于线段过多，也无法准确求出第k个元素究竟是什么。这里二分策略就派上了用场。我们用二分枚举第k个数字P，然后再在所要的线段中找到枚举的P所在的位置，同样是用二分的策略。所以复杂度是O(mlognlognlogn)。
我们在找P所在的位置的时候需要用到二分策略，也就是说，我们需要将线段所代表的结点排序，这里可以将每一层的所有数放到一起，统一成一个数组SortArray[depth][]。其实也可以理解成将归并排序的每个步骤记录下来。
全部程序见附录3。
线段树的第二种变化（树状数组）
在结构上对线段树进行改变，可以得到线段树的另一种变化。
用O（n）的一维数组构造出线段树，无其他附加空间。比方说，一棵从[0,L]的线段树表示为TNode Tree[L];
这里应用二进制将树进行划分。将整数R的二进制表示中的最后一个1换成0，得到数L。Tree[R]代表的线段就是[L,R]。例如：
6的二进制表示为（110）2将最后一个1换成0即为（100）2＝4，所以Tree[6]代表的线段就是[4,6]。
析出数R的最后一位1的方法是：LowBit（R）＝R^~R。
包含点L的一系列数为x1,x2,……，这里x1=R，x2=x1+LowBit (x1)，x3=x2+LowBit(x2)，……
这种线段树的优点在于：
1．节省空间。完全线段长度的空间，无需左右指针，无需左右范围。
2．线段树查找严格log(R)，因为二进制的每位查找一遍。
3．状态转移快，操作简单。
4．扩展到多维较为容易。
缺点：
1．随意表示线段[a,b]较为困难。
这种线段树适用于：
1．查找线段[0,L]的信息。
2．求线段[a,b]的和（应用部分和做差技术）。
// problem zju 1610
// Segment Tree
#define NoColor -1
#define MulColor -2
#include
#include
int Len;
struct TNode {
int left , right;
int col;
TNode *LeftChild , *RightChild;
void Construct ( int , int );
void Insert ( int , int , int );
void Calculate ();
} Tree [16000] , *Root = &Tree [0];
int CalColor [8001] , Many [8001];
void TNode :: Construct ( int l , int r )
{
left = l; right = r;
if ( l + 1 == r ) { LeftChild = NULL; RightChild = NULL; return; }
int mid = ( l + r ) >> 1;
LeftChild = &Tree [Len ++];
RightChild = &Tree [Len ++];
LeftChild->Construct( l , mid );
RightChild->Construct( mid , r );
}
void TNode :: Insert ( int l , int r , int c ) {
if ( col == c ) return;
if ( l == left && r == right ) { col = c; return; } int mid = ( left + right ) >> 1;
if ( col != MulColor ) { LeftChild -> col = col; RightChild -> col = col; }
col = MulColor;
if ( r <= mid ) { LeftChild -> Insert ( l , r , c ); return; }
if ( l >= mid ) { RightChild -> Insert ( l , r , c ); return; }
LeftChild -> Insert ( l , mid , c );
RightChild -> Insert ( mid , r , c );
}
void TNode :: Calculate ()
{
if ( col != MulColor && col != NoColor ) {
int i;
for ( i = left; i < right; i ++ ) CalColor [i] = col;
}
if ( col == MulColor ) { LeftChild -> Calculate (); RightChild -> Calculate (); }
}
main ()
{
int Total , a , b , c , i , t;
Len = 1; Tree [0].Construct( 0 , 8000 );
// printf ( "After Construct the Tree , Len = %d\n" , Len );
while ( scanf ( "%d" , &Total ) != EOF ) {
Tree [0].col = NoColor;
while ( Total ) {
scanf ( "%d %d %d" , &a , &b , &c );
Root -> Insert( a , b , c );
Total --;
}
memset ( CalColor , 0xff , sizeof ( CalColor ) ); memset ( Many , 0 , sizeof ( Many ));
Root -> Calculate ();
t = -1;
for ( i = 0; i <= 8000; i ++ ) {
if ( CalColor [i] == t ) continue;
t = CalColor [i];
if ( t != -1 ) Many [t] ++;
}
for ( i = 0; i <= 8000; i ++ ) if ( Many [i] ) printf ( "%d %d\n" , i , Many [i] );
printf ( "\n" );
}
}
// Problem zju2451
// DP with Segment Tree
#include
#define MAX 50000
int Len;
struct TNode {
int left , right;
int minstep;
TNode *LeftChild , *RightChild;
void Construct ( int , int );
void Insert ( int , int );
int GetRank ( int , int );
} STree [MAX * 2 + 2] , *Root = &STree [0];
int N , M;
void TNode :: Construct ( int l , int r )
{
left = l; right = r; minstep = 999999;
if ( l == r ) { LeftChild = NULL; RightChild = NULL; return; }
int mid = ( l + r ) >> 1;
LeftChild = &STree [Len ++];
RightChild = &STree [Len ++];
LeftChild->Construct ( l , mid );
RightChild->Construct( mid + 1 , r );
}
void TNode :: Insert ( int p , int x )
{
if ( x < minstep ) minstep = x;
if ( left == right ) return;
if ( p <= ( left + right ) >> 1 ) LeftChild->Insert( p , x );
else RightChild->Insert( p , x );
}
int TNode :: GetRank ( int l , int r )
{
if ( l == left && r == right ) return minstep;
int mid = ( left + right ) >> 1;
if ( r <= mid ) return LeftChild->GetRank( l , r );
if ( l > mid ) return RightChild->GetRank( l , r ); int ret1 , ret2;
ret1 = LeftChild->GetRank( l , mid );
ret2 = RightChild->GetRank( mid + 1 , r ); return ret1 < ret2 ? ret1 : ret2;
}
main ()
{
int i , a , b , p;
while ( scanf ( "%d %d" , &N , &M ) != EOF ) { Len = 1; Root->Construct( 1 , N );
Root->Insert ( 1 , 0 );
for ( i = 0; i < M; i ++ ) {
scanf ( "%d%d" , &a , &b );
if ( a < b ) {
p = Root->GetRank ( a , b - 1 );
Root->Insert ( b , p + 1 );
}
}
printf ( "%d\n" , Root->GetRank( N , N ) ); }
}
// PKU 2104
// Segment Tree && Binnary Search
#include
#define MAX 100000
int len;
struct TNode {
int left , right;
char depth;
TNode *LeftChild , *RightChild;
void construct ( int , int , int );
int GetRank ();
} Node [2 * MAX + 2];
int SortArray [18] [MAX + 2];
int Key , ls , rs;
void TNode :: construct ( int l , int r , int dep ) {
left = l; right = r; depth = dep;
if ( left == right ) {
scanf ( "%d" , &SortArray [dep] [l] );
return;
}
int mid = ( l + r ) >> 1;
LeftChild = &Node [len ++];
LeftChild->construct( l , mid , dep + 1 );
RightChild = &Node [len ++];
RightChild->construct( mid + 1 , right , dep + 1 );
int i = left , j = mid + 1 , k = left;
while ( i <= mid && j <= r ) {
if ( SortArray [dep + 1] [i] < SortArray [dep + 1] [j] )
SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];
else
SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];
}
while ( i <= mid ) SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];
while ( j <= right ) SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];
}
int TNode :: GetRank ()
{
if ( ls <= left && right <= rs ) {
if ( SortArray [depth] [left] >= Key ) return 0;
if ( SortArray [depth] [right] < Key ) return right - left + 1;
if ( SortArray [depth] [right] == Key ) return right - left;
int low = left , high = right , mid;
while ( low + 1 < high ) {
mid = ( low + high ) >> 1;
if ( SortArray [depth] [mid] < Key ) low = mid;
else high = mid;
}
return low - left + 1;
}
int ret = 0;
if ( ls <= LeftChild->right ) ret += LeftChild->GetRank();
if ( RightChild->left <= rs ) ret += RightChild->GetRank();
return ret;
}
main ()
{
int N , Q , i;
int low , high , mid , Index;
scanf ( "%d%d" , &N , &Q );
len = 1; Node [0].construct( 0 , N - 1 , 0 );
for ( i = 0; i < Q; i ++ ) {
scanf ( "%d%d%d" , &ls , &rs , &Index );
ls --; rs --;
low = 0; high = N;
while ( low + 1 < high ) {
mid = ( low + high ) >> 1;
Key = SortArray [0] [mid];
if ( Node [0].GetRank() >= Index ) high = mid; else low = mid;
}
printf ( "%d\n" , SortArray [0] [low] );
}
}
POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:
造价师案例辅导：决策树(法)概念考试试卷 一、单项选择题（共25题，每题2分，每题的备选项中，只有1个事最符合题意） 1、工程竣工后，由于洪水等不可抗力造成的损坏，承担包修费用的单位是__。A．施工单位 B．设计单位 C．建设单位 D．监理单位 2、在国产离心泵的型号表示法中，100D45×8表示__。 A．泵的流量100m3/h，单级扬程45m水柱，8级分段多级离心水泵 B．泵的流量为45×8=360m3/h，扬程为100m的多级式离心水泵 C．泵的入口直径为100mm，单级扬程为45m水柱，8级分段式多级离心水泵D．泵的入口直径为100mm，总扬程为45m水柱，8段多级离心水泵 3、解决价值工程的研究对象这个问题是在价值工程活动中__环节完成。 A．对象选择和收集资料 B．对象选择和功能定义 C．功能定义和功能整理 D．收集资料和功能定义 4、安全阀的阀座内径应（）。 A．视情况确定 B．等于25mm C．大于25mm D．小于25mm 5、根据《建设工程施工合同(示范文本)》的规定，工程进度款支付内容包括合同中规定的__。 A．初始收入 B．初始收入加因合同变更构成的收入 C．初始收入加因合同变更、索赔、奖励等构成的收入 D．初始收入加因合同变更、索赔、奖励等构成的收入减应扣回的预付款 6、关于施工组织设计表述正确的是（）。 A．施工组织设计主要用于项目管理 B．施工组织设计由设计单位编制 C．“标后设计”由企业管理层在合同签订之前完成 D．“标前设计”是规划性设计，由项目管理层编制 7、功能评价的目标是（）。 A．找出低价值功能区域 B．找出高价值功能区域 C．找出产品使用功能 D．找出产品美学功能 8、__是指技术工种劳动定额内不包括而在预算定额内又必须考虑的用工。A．额外用
决策树ID3算法在高校教师教育技术培训中的应用研究 摘要: 高校教师教育技术培训存在培训形式单一、内容安排不够合理、评价体系不够健全等问题。针对参训教师在知识层次、学科背景、思想意识等方面存在的差异,应坚持“先分类后培训”的思想,以学校教师历年参训情况构造ID3决策树,利用分类技术从中挖掘出一些潜在的、隐藏的知识,为将来参训教师的分类、培训的具体实施做好充分的准备工作。实验表明,该方法具有一定的可行性。 关键词:高校教师教育技术培训;决策树ID3算法;应用 信息技术的迅猛发展引起了教育的深刻变革。为此,提高教师的信息素养已成为推动我国高等教育信息化建设的必由之路。高教司于2000年发出的《关于开展高校教师教育技术培训工作的通知》(高教司【2000】79号)[1]中指出,“教育技术培训”是“新世纪教改工程”和“现代远程教育工程”的重要组成部分,是深化教学改革、提高教学质量的重要举措。 常熟理工学院自2001年6月开始,对教师进行教育技术培训,2003年1月起申报江苏省教育技术培训点,次年申报成功。2007年,学校正式下发的《常熟理工学院讲师等中级职称资格条件》(常理工[2007]73号)第二章第七条规定:教师申报教学系列、思政系列的中级职称应参加学校现代教育技术培训并取得合格证书。近几年来,学校先后举办了十期教师教育技术中级培训班,共400多名中青年教师参加了培训,极大地提高了教师的多媒体教学水平,加快了学校信息化建设的步伐。 一、高校教师教育技术培训存在的问题 教师教育技术培训的研究对象是教学过程与教学资源,研究范畴包括对教学过程的设计以及教学资源的开发、应用、管理与评价。目前,各高校的教师教育技术培训工作虽已取得了一定的成绩,但从培训的实际效果来看,仍存在着一些问题,主要表现在以下三个方面。 1.培训时间安排不够合理 目前,教师教育培训基本采用集体面授的方式。由于参训教师自身所承担的教学工作和科研任务比较繁重,很难抽出一段相对集中的时间来参加教育技术培训。为解决上述矛盾,高校通常会选择利用寒暑假时间安排培训,这需要牺牲培训教师和参训教师的许多休息时间,容易引发不满情绪,严重影响了教师参训的积极性,极大地降低了培训效果。 2.培训内容安排不科学 由于培训内容是根据全校教师需求统一安排的,基本没有考虑到参训教师自身所具备的知识层次、学科背景、思想意识等方面的差异,因此很难体现学科差别。各学科教师混合在一起集中学习,导致理论知识讲解过多而与教学实际联系较少,参训教师难以从根本上真正掌握教育技术。 3.考核方式单一,培训评价体系不健全 目前,高校教师培训采取的考核方式往往比较单一,通常以参加理论考试或者提交相关论文、作业等作为培训的最终考核结果。此外,各级培训机构大多未能及时地对培训过程做出评价,同时缺少参训教师的自我评价环节,因而不利于教育技术培训工作的后续支持和进一步开展。如此看来,建立和完善培训评价体系显得尤为重要,这也是建立教师培训长效机制的关键所在。 二、分类技术与决策树ID3 算法的相关理论
复赛算法模块 信息学奥赛组 对于NOIP，基础是相当重要的，在3个小时之内做完4道题，那么就要求我们有相当快的速度。特别是对于一些简单的、常用的算法模块，一定要要熟练掌握并灵活运用。由于NOIP是一个比较基础的比赛，因此基本算法的掌握尤为重要，所以要求能够把这些基本的模块快速、准确的移植到不同的程序中，才能在稳中取胜 基本算法模块中最重要的是基本程序框架，也就是说，要养成适合于自己的程序风格，这样对于程序编写的速度与程序的准确度都有较大的提高。
小议竞赛的准备和考试技巧 1、良好的心态。无论竞赛多么重要，都不要在考试的时候考虑考试之前或以后的事，这很重要…… 2、充足的睡眠和营养。竞赛之前睡好觉，吃好饭，多吃甜食（据我们老师说在吃甜食后15分钟和2小时会各出现一次血糖高峰，会有比较好的竞技状态）。还有，宁可撒尿也不要口渴……口渴会严重影响思路……而尿素有兴奋作用，有利无害…… 3、正确的时间安排。一般来说应该先想完所有的题再开始做，但有的题想不出来的时候一定要给想出来的题留出时间。 4、算法的学习。一般的DFS/BFS、贪心、各种DP、二分法、排序、lr论文中的各种奇特算法、最短路、最长路、图的DFS/BFS、最大匹配，最大最小匹配、最佳匹配、差分限制系统、最长不xx子序列、高斯消元、数论算法…… 5、数据结构的学习。Hash、并查集、邻接表、边表、堆、树状数组和线段树及它们的多维形式、链表、单词查找树…… 6、关于混分：超时的搜索/DP往往能比错误的贪心得到更多的分。 7、数学很重要。比如母函数…… 8、专用的方法胜于通用的方法。 9、好的题目往往不能直接用经典算法解决。 10、真正难题的标程往往很短。 11、如果n很大，用汇编写的O(n^2)的程序绝对不如用QB写的O(n)的程序快。 12、如果n很小，利用压缩存储提高速度的O(n^2)的算法有可能比一般的O(n)算法快。 13、如果一个数学问题很复杂，那么看结果找规律有可能比数学推导快。 14、不要总把logn忽略掉。 15、即使是多项式算法，有时也可以加入很有效的剪枝。 16、做一道好题胜过做n道烂题，但如果不做烂题，可能会影响做好题的速度。
3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”，
树状数组 武钢三中 吴豪【引言】 在解题过程中，我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]。但是不难发现，如果我们修改了任意一个A[i],S[i]、S[i+1]...S[n]都会发生变化。可以说，每次修改A[i]后，调整前缀和S[]在最坏情况下会需要O(n)的时间。当n非常大时，程序会运行得非常缓慢。因此，这里我们引入“树状数组”，它的修改与求和都是O(logn)的，效率非常高。 【理论】 为了对树状数组有个形 象的认识，我们先看下面这张图。 如图所示，红色矩形表示的数组C[]就是树状数组。 这里，C[i]表示A[i-2^k+1]到A[i]的和，而k则是i在二进制时末尾0的个数，或者说是i用 2的幂方和表示时的最小指数。( 当然，利用位运算，我们可以直接计算出2^k=i&(i^(i-1)) ）同时，我们也不难发现，这个k就是该节点在树中的高度，因而这个树的高度不会超过logn。所以,当我们修 改A[i]的值时，可以从C[i]往根节点一路上溯，调整这条路上的所有C[]即可，这个操作的复杂度在最坏情况下就是树的高度即O(logn)。另外，对于求数列的前n项和，只需找到n以前的所有最大子树，把其根节点的C加起来即可。不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开 成2的幂方和时的项数,因此，求和操作的复杂度也是O(logn)。 接着，我们考察这两种操作下标变化的规律： 首先看修改操作： 已知下标i，求其父节点的下标。我们可以考虑对树从逻辑上转化：
如图，我们将子树向右对称翻折，虚拟出一些空白结点（图中白色），将原树转化成完全二叉树。 有图可知，对于节点i，其父节点的下标与翻折出的空白节点下标相同。 因而父节点下标 p=i+2^k (2^k是i用2的幂方和展开式中的最小幂，即i为根节点子树的规模)即 p = i + i&(i^(i-1)) 。 接着对于求和操作： 因为每棵子树覆盖的范围都是2的幂，所以我们要求子树i的前一棵树，只需让i减去2的最小幂即可。即 p = i - i&(i^(i-1)) 。 至此，我们已经比较详细的分析了树状数组的复杂度和原理。 在最后，我们将给出一些树状数组的实现代码，希望读者能够仔细体会其中的细节。 【代码】 求最小幂2^k: in t L o wb i t(in t t) { retur n t & ( t ^ ( t - 1 ) ); } 求前n项和： in t S um(in t e n d) { in t sum = 0; wh il e(e n d> 0) {
https://www.doczj.com/doc/0815718087.html, 决策树归纳的理论介绍_光环大数据培训 光环大数据培训机构了解到，什么是分类？ 银行贷款员需要分析数据，以便搞清楚哪些贷款申请者是“安全”那些是“有风险”的。销售经理需要数据分析，以便帮助他猜测哪些顾客会购买计算机。再或者医学研究人员需要分析乳腺癌数据，以便预测病人应当接受三种治疗中的哪一种。在上面的例子中，数据分析任务都是分类，都需要构造一个模型来预测一个类别型数据。譬如安全或者不安全、会购买与不会购买、那种治疗都是类别型。分类是一种重要的数据分析形式，它提取刻画重要数据类的模型，用来预测（离散的、无序的）类标号。 决策树是一种类似于流程图的树结构，其中，每个内部节点(非树叶节点）表示在一个属性上的测试，每个分支代表该测试的一个输出，而每个树叶节点（或终端节点）存放一个类标号。树的最顶层节点是根节点。 比如我们想要决定要不要给一个用户贷款，第一个分裂准则可以定义为age 年龄，年龄底下有三个分枝，Youth，middle_aged和Senior。年轻人中再以是否为大学生作为一个分裂节点，如果是学生就给贷款，yes就是这条枝子上的叶子节点，也就是最后的类标号。 数据分类过程：a) 学习，及建立树的阶段。用分类算法分析训练数据，学
https://www.doczj.com/doc/0815718087.html, 习的模型以分类规则（Splitting criterian）或者叫属性选择度量形式提供； b) 分类。检验数据用于评估分类规则的准确率，如果准确率是可以接受的，则规则用于新的数据元组分类。 属性选择度量是一种选择分裂标准，把给定类标记的训练元组的数据分区D “最好地”划分成单独类的启发方式，比如量——信息增益、增益率和基尼指数。 1、用信息增益进行决策树归纳 看不懂公式可以直接看下面例子 该度量基于Claude Shannon在研究消息的值或“信息内容”的信息论方面的先驱工作。设计节点N代表或存放分区D的元组。选择具有最高信息增益的属性作为节点N的分裂属性。该属性使结果分区中对元组分类所需要的信息量最小，并反映这些分区中的最小随机性或“不纯性”。这种方法使得对一个对象的分类所需要的期望测试数目最小，并确保找到一颗简单的（但不必是最简单的）树。 现在我们假设要按某属性A划分D中的元组，其中属性A根据训练数据的观测具有v个不同的值｛a1,a2, …, av｝。理想情况下我们希望该划分产生的元组的准确分类，即我们希望每个分区都是纯的。然而这些分区多半是不纯的（例如，分区可能包含来自不同类而不是来自单个类的元组）。为了得到准确的分类，我们需要下式度量：
计算几何入门题(转) 原来在文章里转的，现在放到计算几何专题中来： 计算几何题的特点与做题要领： 1.大部分不会很难，少部分题目思路很巧妙 2.做计算几何题目，模板很重要，模板必须高度可靠。 3.要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。如果代码一片混乱，那么会严重影响做题正确率。 4.注意精度控制。 5.能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。因为整数不用考虑浮点误差，而且运算比浮点快。 一。点，线，面，形基本关系，点积叉积的理解 POJ 2318 TOYS（推荐） https://www.doczj.com/doc/0815718087.html,/JudgeOnline/problem?id=2318 POJ 2398 Toy Storage（推荐） https://www.doczj.com/doc/0815718087.html,/JudgeOnline/problem?id=2398 一个矩形，有被若干直线分成N个格子，给出一个点的坐标，问你该点位于哪个点中。
知识点：其实就是点在凸四边形内的判断，若利用叉积的性质，可以二分求解。POJ 3304 Segments https://www.doczj.com/doc/0815718087.html,/JudgeOnline/problem?id=3304 知识点：线段与直线相交，注意枚举时重合点的处理 POJ 1269 Intersecting Lines https://www.doczj.com/doc/0815718087.html,/JudgeOnline/problem?id=1269 知识点：直线相交判断，求相交交点 POJ 1556 The Doors （推荐） https://www.doczj.com/doc/0815718087.html,/JudgeOnline/problem?id=1556 知识点：简单图论＋简单计算几何，先求线段相交，然后再用Dij求最短路。POJ 2653 Pick-up sticks https://www.doczj.com/doc/0815718087.html,/JudgeOnline/problem?id=2653 知识点：还是线段相交判断 POJ 1066 Treasure Hunt https://www.doczj.com/doc/0815718087.html,/JudgeOnline/problem?id=1066
rpart包的rpart函数 Iris数据集 library(rpart) #加载rpart包 head(iris) #看看iris数据集里有哪些变量 iris以鸢尾花的特征作为数据来源，数据集包含150个数据，分为3类，每类50个数据，每个数据包含4个属性分别是花萼长度、花萼宽带、花瓣长度、花瓣宽度 用gini度量纯度 iris.rp1=rpart(Species~.,data=iris,method="class",parms=list(split="g ini")) # rpart(formula, data, method, parms, ...)得到决策树对象，其中（1）formula是回归方程的形式，y~x1+x2+…，iris一共有5个变量，因变量是Species,自变量是其余四个变量，所以formula可以省略为 Species~. （2）data是所要学习的数据集 （3）method根据因变量的数据类型有如下几种选择：anova（连续型），poisson （计数型），class（离散型），exp（生存型），因为我们的因变量是花的种类，属于离散型，所以method选择class （4）parms可以设置纯度的度量方法，有gini（默认）和information（信息增益）两种。 plot(iris.rp1, uniform=T, branch=0, margin=0.1,main="Classification Tree\nIris Species by Petal and Sepal Length") #plot的对象是由rpart得到的决策树对象，可以把这课决策树画出来，其中 （1） uniform可取T，F两个值，T表示图形在空间上均匀分配 （2） branch刻画分支的形状，取值在0和1之间，branch=0是倒v型，branch=1是直角型，而当branch属于（0,1）时是梯形
线段树完全版 ~by NotOnlySuccess 很早前写的那篇线段树专辑至今一直是本博客阅读点击量最大的一片文章,当时觉得挺自豪的,还去pku 打广告,但是现在我自己都不太好意思去看那篇文章了,觉得当时的代码风格实在是太丑了,很多线段树的初学者可能就是看着这篇文章来练习的,如果不小心被我培养出了这么糟糕的风格,实在是过意不去,正好过几天又要给集训队讲解线段树,所以决定把这些题目重新写一遍,顺便把近年我接触到的一些新题更新上去~;并且学习了splay 等更高级的数据结构后对线段树的体会有更深了一层,线段树的写法也就比以前飘逸,简洁且方便多了. 在代码前先介绍一些我的线段树风格: ? maxn 是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn 的最小2x 的两倍 ? lson 和rson 分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的表示 ? 以前的写法是另外开两个个数组记录每个结点所表示的区间,其实这个区间不必保存,一边算一边传下去就行,只需要写函数的时候多两个参数,结合lson 和rson 的预定义可以很方便 ? PushUP(int rt)是把当前结点的信息更新到父结点 ? PushDown(int rt)是把当前结点的信息更新给儿子结点 ? rt 表示当前子树的根(root),也就是当前所在的结点 整理这些题目后我觉得线段树的题目整体上可以分成以下四个部分: ? 单点更新:最最基础的线段树,只更新叶子节点,然后把信息用PushUP(int r)这个函数更新上来 o hdu1166 敌兵布阵 题意:O(-1) 思路:O(-1) 线段树功能:update:单点增减 query:区间求和 ?View Code CPP 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include
Java基础常见英语词汇(共70个) ['?bd?ekt]['?:rientid]导向的['pr??ɡr?m??]编程 OO: object-oriented ,面向对象OOP: object-oriented programming,面向对象编程[d?'vel?pm?nt][k?t]工具箱['v??tj??l]虚拟的 JDK:Java development kit, java开发工具包JVM:java virtual machine ,java虚拟机 ['d?ɑ?v?][m?'?i?n]机器 [k?m'pa?l] Compile:编绎Run:运行 ['ve?r??b(?)l] [?p?'re??(?)n] [p?'r?m?t?] variable:变量operation:操作,运算parameter:参数 ['f??(k)?(?)n] function:函数member-variable:成员变量member-function:成员函数 [d?'f??lt] ['?kses] ['p?k?d?] [?m'p??t] ['st?t?k] default:默认access:访问package:包import:导入static:静态的 [v?id] ['pe?r(?)nt] [be?s] ['sju?p?] void:无(返回类型) parent class:父类base class:基类super class:超类 [t?a?ld] [di'raivd] [??v?'ra?d] [??v?'l??d] child class:子类derived class:派生类override:重写,覆盖overload:重载['fa?n(?)l] ['?mpl?m(?)nts] final:最终的,不能改变的implements:实现 [r?n'taim] [?riθ'metik][ik'sep??n] Runtime:运行时ArithmeticException:算术异常 [?'rei]['indeks] [baundz][ik'sep??n] [n?l] ['p?int?]指针ArrayIndexOutOfBoundsException:数组下标越界异常Null Pointer Exception:空引用异常ClassNotFoundException:类没有发现异常 ['n?mb?]['f?:m?t] NumberFormatException:数字格式异常(字符串不能转化为数字) [θr?uz] Throws: (投掷)表示强制异常处理Throwable:(可抛出的)表示所有异常类的祖先类 [l??]['l??ɡwid?][ju'til] [,dis'plei] [?'rei] [list] Lang:language,语言Util:工具Display:显示ArrayList:(数组列表)表示动态数组[h??][m?p] HashMap: 散列表,哈希表 [swi?] ['?bstr?kt] ['wind?u] ['tu:lkit] Swing:轻巧的Awt:abstract window toolkit:抽象窗口工具包 [freim] ['p?nl] ['leiaut] [skr?ul] ['v?:tik?l] Frame:窗体Panel:面板Layout:布局Scroll:滚动Vertical:垂直 ['h?ri'z?nt?l] ['leibl] [tekst] ['fi:ld] Horizontal:水平Label:标签TextField:文本框 ['ε?ri?] ['b?t?n] [t?ek] [b?ks] TextArea:文本域Button:按钮Checkbox:复选框
·AVL树·红黑树·伸展树·树堆·节点大小平衡树 ·B+树·B*树·B x树·UB树·2-3树·2-3-4·(a,b)-树·Dancing tree ·H树 ·基数树 ·八叉树·k-d树·vp-树·R树·R*树·R+树·X ·线段树·希尔伯特R树·优先R树
并且左右两个子树都是一棵平衡二叉树。构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。 堆（二叉堆） ---------------------------------------------------------------------------------------------------------- ----- 堆是一种完全二叉树，效率很高，常用的排序算法、Dijkstra算法、Prim算法等都要用堆（优先级队列）优化。一般的二叉堆不能进行有效查找和堆之间的合并。 （插入，获得及删除最小值） 可并堆 可以在O(logN)时间内完成两个堆的合并操作的二叉堆。如左偏堆，二项堆，斐波那契堆。 最优二叉树（哈夫曼树） ---------------------------------------------------------------------------------------------------------- -------
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 字典树 ---------------------------------------------------------------------------------------------------------- ------ 又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。 AVL树 ---------------------------------------------------------------------------------------------------------- --------- 是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 伸展树
计算题 一 1.为生产甲产品，小行星公司设计了两个基本方案：一是建大工厂，二是建小工厂。如果销路好，3年以后考虑扩建。建大工厂需投资300万元，建小工厂需投资160万元，3年后扩建另需投资140万元。扩建后可使用7年，其年度损益值与大工厂相同。每种自然状态的预测概率及年度损益值如下表： 前 3 年 后 7 年 根据上述资料试用决策树法做出决策。 四、计算题（15分）
答：建大厂收益=581-300=281 建小厂收益=447-160=287 所以应选择建小厂方案。 二 山姆公司的生产设备已经落后，需要马上更新。公司有人认为，目前产品销路增长，应在更新设备的同时扩大再生产的规模。但也有人认为，市场形势尚难判断，不如先更新设备，3年后再根据形势变化考虑扩大再生产的规模问题。这样，该公司就面临着两个决策方案。决策分析的有关资料如下： A、现在更新设备，需投资35万元， 3年后扩大生产规模，另需投资40万元。 B、现在更新设备的同时扩大再生产的规模，需投资60万元。 C、现在只更新设备，在销售情况良好时，每年可获利6万元；在销售情况不好时，每年可获利4、5万元。 D、如果现在更新与扩产同时进行，若销售情况好，前3年每年可获利12万元；后7年每年可获利15万元；若销售情况不好，每年只获利3万元。 E、每种自然状态的预测概率如下表
前 3 年 后 7 年 根据上述资料试用决策树法做出决策。 答案：
结点7收益值=0、85×7 × 15+0、15 ×7 ×3=92、4（万元）
结点8收益值=0、85×7 ×6+0、15 ×7 ×4、5=40、4（万元） 结点9收益值=0、1×7 × 15+0、9 ×7 ×3=29、4（万元） 结点10收益值=0、1×7 × 6+0、9 ×7 ×4、5=32、6（万元） 结点1收益值=0、7×[52、4+（3 × 6）]+0、3 ×[32、6+（3 × 4、5）]=63、1（万元） 结点2收益值=0、7×[92、4+（3 × 12）]+0、3 ×[29、4+（3 × 3）]=101、4（万元） 答：用决策树法进行决策应选择更新扩产方案，可获得收益41、4万元。 三 某厂准备生产Y种新产品，对未来的销售前景预测不准，可能出现高需求、中需求、低需求三种自然状态。组织有三个方案可供选择：新建一个车间；扩建原有车间；对原有车间的生产线进行局部改造。三个方案在5年内的经济效益见下表（单位：万元）： 0 1 请分别用悲观决策法、乐观决策法、最大最小后悔决策法做出决策。 悲观决策法指当存在几种自然状态的情况下，宁可把情况估计得坏一 些，从中选择一个收益最大的方案，决策稳妥可靠。按此准则，在低需求的自然状态下，5年内新建方案亏损160万，扩建方案保本，改造方案获利80万。改造方案最佳。 乐观决策法： 新建E=（0、7X600）+（1-0、7）X（-160）=372（万元） 扩建E=（0、7X400）+ （1-0、7）X0=280 （万元） 改造E=（0、7X300）+ （1-0、7）X80=234 （万元） 比较结果，新建方案最佳。 最大最小后悔决策，是用后悔值计算表进行计算的： 后悔值计算表
杭电acm 1001这个就不用说了吧 1002简单的大数 1003DP经典问题，最大连续子段和 1004简单题 1005找规律（循环点） 1006感觉有点BT的题，我到现在还没过 1007经典问题，最近点对问题，用分治 1008简单题 1009贪心 1010搜索题，剪枝很关键 1011 1012简单题 1013简单题（有个小陷阱） 1014简单题 1015可以看作搜索题吧 1016经典的搜索 1017简单数学题 1018简单数学题 1019简单数学题 1020简单的字符串处理 1021找规律的数学题 1022数据结构的题（栈的应用） 1023特殊的数（CatalanNumber） 1024经典DP，最大M子段和 1025经典DP，最长递增子序列（要用NLogN的方法过）1026搜索 1027数学题（或用STL） 1028经典问题，整数拆分，用母函数做 1029简单题（一般方法容易超时） 1030简单题，可用模拟过 1031简单题 1032简单题 1033模拟题 1034CandySharingGame 1035模拟题 1036简单题 1037简单题，不是一般的简单 1038简单题 1039字符串处理 1040简单题，排序 1041简单题，用大数 1042大数 1043经典搜索题，八数码问题
1044稍微有点麻烦的搜索题 1045搜索题，可用匹配做 1046简单题 1047简单的大数 1048简单字符串处理 1049简单题 1050贪心 1051经典贪心，也可以用DP 1052贪心 1053贪心，关于Huffman编码 1054二分匹配 1055二分匹配 1056简单题 1057模拟题 1058经典问题，丑数，DP 1059经典问题，可以用母函数或DP（不针对题目优化都会超时）1060数学题 1061数学题 1062简单字符串处理 1063模拟大数 1064简单题 1065简单题 1066数学题，找规律 1067 1068经典二分匹配 1069经典DP 1070简单题 1071简单数学题 1072搜索 1073字符串处理 1074DP 1075字典树 1076简单题 1077 1078DP 1079博弈（DP） 1080DP 1081经典DP 1082简单题 1083二分匹配 1084简单题 1085母函数 1086简单几何题 1087简单DP
（计算机编程英语词汇） 算法常用术语中英对照 Data Structures 基本数据结构 Dictionaries 字典 Priority Queues 堆 Graph Data Structures 图 Set Data Structures 集合 Kd-Trees 线段树 Numerical Problems 数值问题 Solving Linear Equations 线性方程组 Bandwidth Reduction 带宽压缩 Matrix Multiplication 矩阵乘法 Determinants and Permanents 行列式 Constrained and Unconstrained Optimization 最值问题Linear Programming 线性规划 Random Number Generation 随机数生成 Factoring and Primality Testing 因子分解/质数判定Arbitrary Precision Arithmetic 高精度计算Knapsack Problem 背包问题 Discrete Fourier Transform 离散Fourier 变换Combinatorial Problems 组合问题 Sorting 排序 Searching 查找 Median and Selection 中位数 Generating Permutations 排列生成 Generating Subsets 子集生成 Generating Partitions 划分生成 Generating Graphs 图的生成 Calendrical Calculations 日期 Job Scheduling 工程安排 Satisfiability 可满足性 Graph Problems -- polynomial 图论-多项式算法Connected Components 连通分支 Topological Sorting 拓扑排序 Minimum Spanning Tree 最小生成树 Shortest Path 最短路径 Transitive Closure and Reduction 传递闭包Matching 匹配 Eulerian Cycle / Chinese Postman Euler 回路/中国邮路Edge and Vertex Connectivity 割边/割点 Network Flow 网络流 Drawing Graphs Nicely 图的描绘 Drawing Trees 树的描绘
机器学习--决策树(ID3)算法及案例 1基本原理 决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。一般情况下，决策树由决策结点、分支路径和叶结点组成。在选择哪个属性作为结点的时候，采用信息论原理，计算信息增益，获得最大信息增益的属性就是最好的选择。信息增益是指原有数据集的熵减去按某个属性分类后数据集的熵所得的差值。然后采用递归的原则处理数据集，并得到了我们需要的决策树。 2算法流程 检测数据集中的每个子项是否属于同一分类： If 是，则返回类别标签； Else 计算信息增益，寻找划分数据集的最好特征 划分数据数据集 创建分支节点（叶结点或决策结点） for 每个划分的子集 递归调用，并增加返回结果到分支节点中
return 分支结点 算法的基本思想可以概括为： 1）树以代表训练样本的根结点开始。 2）如果样本都在同一个类．则该结点成为树叶，并记录该类。 3）否则，算法选择最有分类能力的属性作为决策树的当前结点． 4 ）根据当前决策结点属性取值的不同，将训练样本根据该属性的值分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。匀针对上一步得到的一个子集，重复进行先前步骤，递归形成每个划分样本上的决策树。一旦一个属性只出现在一个结点上，就不必在该结点的任何后代考虑它，直接标记类别。 5）递归划分步骤仅当下列条件之一成立时停止： ①给定结点的所有样本属于同一类。 ②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布[这个主要可以用来剪枝]。 ③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类生成叶子节点。 算法中2)步所指的最优分类能力的属性。这个属性的选择是本算法种的关键点，分裂属性的选择直接关系到此算法的优劣。 一般来说可以用比较信息增益和信息增益率的方式来进行。 其中信息增益的概念又会牵扯出熵的概念。熵的概念是香农在研究信息量方面的提出的。它的计算公式是： Info(D)=-p1log(p1)/log(2.0)-p2log(p2)/log(2.0)-p3log(p3)/log(2.0)+...-pNlog(pN) /log(2.0) (其中N表示所有的不同类别)
STL | 全排列函数next_permutation STL 中专门用于排列的函数（可以处理存在重复数据集的排列问题） 头文件：#include