青少年编程知识记录 codecoming

C++中的溢出

一、编程中的溢出   溢出是C++语言中最常见的漏洞。最常见的溢出包括数组溢出、数溢出、缓冲区溢出、指针溢出以及栈溢出。二、数组溢出      数组溢出是最常见的一种溢出。因为在C++语言中，含N个元素的数组下标是从0开始，到N-1结束，而且C++语言没有提供数组越界检查的机制。  也就是说，一个含有n个元素的数组，其遍历元素的方式为：      
作者:亿万年的星光 分类:C++知识 浏览:

STL入门——容器3：map

一、定义    Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。map是一类关联式容器。它的特点是增加
作者:亿万年的星光 分类:C++知识 浏览:

深搜剪枝技巧

一、什么是剪枝

     首先应当明确的是，“剪枝”的含义是什么。我们知道，搜索的进程可以看作是从树根出发，遍历一棵倒置的树——搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是坚强搜索树中的某些“枝条”，故称剪枝。

    我们在编写搜索程序的时候，一般都要考虑剪枝。显而易见，应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留。设计好的剪枝判断方法，往往能够使程序的运行时间大大缩短；否则，可能适得其反。



二、剪枝的原则

    1.正确性：

    我们知道，剪枝方法之所以能够优化程序的执行效率，正如前文所述，是因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。

    2.准确性：

    在保证正确性的基础上 ，对剪枝判断的第二个要求就是准确性，即能够尽可能多地剪去不能通向正确的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。

    3.高效性：

    一般来说，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然是有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的

效率提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性之外，经常还需要提高判断操作本身的时间效率。

    然而这就带来了一个矛盾：我们为了加强优化效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能降低、甚至完全抵消

提高判断准确性所能带来的优化效果，这恐怕会得不偿失。很多情况下，能否较好地解决这个矛盾，往往成为搜索算法优化的关键。

    综上所述:我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。

三、深度优先搜索的优化技巧

    1.优化搜索顺序

     在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。

    2.排除等效冗余

      在搜索过程中，如果我们能够判断从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。

    3.可行性剪枝

        在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界就及时回溯。这就好比我们在道路上行走时，远远看到前方是一个死胡同，就应该立即折返，走到路的尽头再返回。

某些题目条件的范围限制是一个区间，此时可行性剪枝也被称为上下界。

    4.最优性剪枝

在最优化问题的搜索过程中，如果当前花费的代价已经超过当前搜到的最优解，那么取多么优秀的策略到达递归边接，都不可能更新答案，此时可以停止对当前分支的搜索回溯。

    5.记忆化

可以记录每个状态的搜索结果，在重复遍历一个状态时直接搜索并返回。这好比我们进行深度优先遍历时，标记一个节点是否已经被访问过。



四、例题



【问题描述】

将整数n分成k份，且每份不能为空，问有多少种不同的分法？当n=7，k=3时，下面三种分法是被认为是相同的：1，1，5；

1，5，1；5，1，1。

【输入格式】

输入文件只有一行，为两个整数n和k。（6<n<=200， 2<=k<=6）

【输出格式】

输出文件仅有一行，为一个整数，即不同的分法数。

【样例输入】

7 3

【样例输出】

4

【样例解释】

四种分法为：1，1，5；1，2，4；1，3，3；2，2，3；

【数据规模】

对100%的数据，6<=n<=200, 2<=k<=6
作者:亿万年的星光 分类:C++知识 浏览:

如何计算一个程序的运行时间（防止超时）

再一些OJ系统中，做题的时候常常会超时，但是很多人不知道自己的程序是否会超时，不知道如何检查自己的程序。这篇文章主要介绍几种监测自己程序运行时间的程序。头文件<time.h>   2.用法1：#include<stdio.h> #include<stdlib.h> #include<time.h> int main() { int n,s=0; for ( int&
作者:亿万年的星光 分类:C++知识 浏览:

C++中双冒号（：：）的用法

一、作用域符号前面一般是类名称，后面一般是该类的成员名称，C++为例避免不同的类有名称相同的成员而采用作用域的方式进行区分如：A,B表示两个类，在A,B中都有成员member。那么A::member就表示类A中的成员memberB::member就表示类B中的成员member 二、是C++里的“作用域分解运算符比如声明了一个类A，类A里声明了一个成员函数voidf()，但没有在类的声明里给出f的定义，那么在类外定义f时，就要写成voidA::f()，表示这个f()函数是类A的成员函数。
作者:亿万年的星光 分类:C++知识 浏览:

STL入门——容器2：set

一、简单介绍    set是STL中一个很有用的容器，用来存储同一种数据类型的数据结构（可以称之为K的模型），基本功能与数组相似。set与数组不同的是，在set中每个元素的值都是唯一的。而且set插入数据时，能够根据元素的值自动进行排序。set中数元素的值并不能直接被改变。二、set底层（1）set的底层是红黑树，是红黑树里面K的模型；K模型：表示只能存放同一种数据类型KV模型：表示能存放两种数据类型（2）map的底层也是红黑树，而它是KV模型。（3）se
作者:亿万年的星光 分类:C++知识 浏览:

STL入门——容器1：vector (不定长度数组)

一、定义     vector是一个不定长度数组。不仅如此，它把一些常用操作“封装”在了 vector 类型内部。      vector 是一个模板类，所以需要用 vector<int> a 或者 vector<double> b 这样的方式来声明一个 vector 。vector<int> 是一个类似于 int a[] 的整数数组，而 vector<s
作者:亿万年的星光 分类:C++知识 浏览:

STL入门——简单介绍

一、STL是什么？    STL(Standard Template Library)即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。    STL的一个重要
作者:亿万年的星光 分类:C++知识 浏览:

c++ 如何用链表存取数据

由于单链表的每个结点都有一个数据域和一个指针域。所以，每个结点可以定义成一个记录。

其中，DATA数据元素，可以为你想要储存的任何数据格式，可以是数组，可以是int，甚至可以是结构体（这就是传说中的结构体套结构体）

NEXT为一个指针，其代表了一个可以指向的区域，通常是用来指向下一个结点，链表的尾部NEXT指向NULL（空），因为尾部没有任何可以指向的空间了

#include<iostream>  using namespace std;  struct Node{  	int data;  	Node *next;  };  Node *head, *p, *r;  //r指向链表的当前最后一个结点，可以称为尾指针   int x;  int main(){  	cin>>x;  	head=new Node;  //申请头结点  	r=head;    	while(x!=-1){  //读入的数非-1   		p=new Node;  //否则，读入一个新结点   		p->data=x;  //把数据放入数据域   		p->next=NULL; // 先把当前这个结点的指针域变为NULL  		r->next=p;  //把新结点链接  接到前面的链表中（p可以认为是一个结点的头指针），   		r=p; //尾指针后移一个  		cin>>x;   	}   	return 0;   }





【写法2】

//声明节点结构  typedef struct Link{  int  elem;//存储整形元素  struct Link *next;//指向直接后继元素的指针  }link;  //创建链表的函数  link * initLink(){  link * p=(link*)malloc(sizeof(link));//创建一个头结点  link * temp=p;//声明一个指针指向头结点，用于遍历链表  //生成链表  for (int i=1; i<5; i++) {  //创建节点并初始化  link *a=(link*)malloc(sizeof(link));  a->elem=i;  a->next=NULL;  //建立新节点与直接前驱节点的逻辑关系  temp->next=a;  temp=temp->next;  }  return p;  }
作者:亿万年的星光 分类:C++知识 浏览: