Scott_dingg-CSDN博客

原创顺序表操作

顺序表的建立、插入等；

2014-07-11 10:04:04 795

原创二叉树的几个基本性质

性质1：在二叉树的第 i 层上最多只有 2^(i-1) 个结点；性质2：深度为 k 的二叉树至多有 2^k - 1 个结点；性质3：对于任何一课二叉树，结点总数为 n 个，如果其叶子结点数为 n(0) 个，度为1的结点有 n(1) 个，度为2的结点有 n(2) 个，则：n = n(0) + n(1) + n(2) ; （加法原理）若假设B为分支的总数：则有： n

2014-03-14 09:51:21 1810

原创二叉树先序、中序、后续遍历（非递归实现）

二叉树遍历的非递归形式，主要是依靠栈来实现的：对于二叉树的先序遍历，先将根结点压入栈中，然后将树中所有的左子树压入栈中同时访问其值，对于最后一个左子树压入栈中后，它的左子树为NULL ；访问它的右子树，并从栈中将其退出，再以它的右子树为根结点的形式进行访问，当栈中元素第一次全部清空之后，若根结点的右子树不为空，继续进行进栈操作，直到栈再次为空且右子树NULL时结束；#include#

2014-03-12 17:50:36 1270

原创二叉树前序、中序、后续遍历(递归实现)

依照上一篇博文所建立的二叉树，对其进行前序、中序、后续遍历：#include#include#include#includeusing namespace std ;//(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()struct Node { int data ; Node *left ;

2014-03-12 15:31:01 1247

原创二叉树的宽度优先遍历（队列实现）

给出每个子结点到根结点的路径，可以进行输入建树；然后用宽度优先搜索的方法遍历这棵二叉树；宽度优先搜索需要用到队列，队列中头部出来一个，尾部需要进去两个，直到叶子结点为止！#include#include#include#includeusing namespace std ;struct Node { int data ; Node *left ; Node *rig

2014-03-12 15:17:36 2901

原创模拟二叉树 — 纪念植树节……

给定一颗完全二叉树；可知道这棵树有以下特点：1、若父亲结点为k，则其左孩子结点为2*k，右孩子结点为2*k+12、若深度为D，结点最多为(1有一些小球从结点1处依次开始下落，问最后一个小球将会落到哪里？如果遇到这样的问题，肯定不能用深度遍历，原因是，每个小球都要从上往下依次下落。可以用循环来做，但是时空复杂度比较高；#include#includeusing names

2014-03-12 11:01:53 939

原创动态规划——M个子串最大和

输入一个整数n ，表示有n个数据，输入n个数据，求出m个子串最大和；dp[i][j] 表示与第j个数组合时，第i段子串最大和；注意：dp[i][j] 不是前 j 个数，形成 i 段的最大和；不经过优化的代码：#includeusing namespace std ;#define max(x,y) ((x) > (y) ? (x) : (y))int main()

2014-03-11 21:12:45 1213

原创动态规划——求最大子串和

输入一个整数n代表有几个数据，接着输入n个数据，求这n个数据组成的串中，子串和最大；一道求最优解的动态规划问题。dp[ i ] 表示与第i个数组合时，所能得到的最大值；第n个数据（dp[ n ]）有两种年可能：1、当 dp[n-1] 2、当 dp[n-1] >= 0 时，和dp[n-1]相加 (dp[n] = dp[ n-1 ] + a[ n ] ) ;注意：dp

2014-03-11 11:06:03 2654

原创字符串问题汇总

计算一个字符串在另外一个字符串中出现的次数：#include#include#includeusing namespace std ;int main() { int count = 0 ; string s1 = "abcdef" , s2 = "abcdefabcdefaaa" ; int i = 0 ; while((i=s2.find(s1,i)) != string:

2014-03-10 18:13:07 683

原创 C/C++输入，输出汇总

C语言输入输出详解C语言中基本的输入输出：putchar() ; // 把变量中的一个字符常量输出#include int main (){ char c; for (c = 'A' ; c <= 'Z' ; c++) putchar (c); return 0;}只能输出字符型……getchar()； // 从键盘

2014-03-10 16:46:02 1064

原创 HDU(1003)动态规划

这道题虽然有很多种解法，但我一直尝试着用动态规划解，刚入门，用起来很不顺手，其中出现了很多错误，很多的意想不到，希望通过这道题，对动态规划能够更进一步的了解。这道题是典型的也是动态规划中最简单的一道题，求最大子串和的问题。第一步：分解出子问题。本题的子问题是：dp[i] 代表前i个数中最大子串的和；第二步：通过递归或递推求出子问题的最优解。本题中的状态转移方程为：if ( d

2014-03-06 10:13:21 1362

原创我所喜欢的话（不断更新）

1、究竟是我们改变了世界，还是世界改变了？多年后，其实我们才发现是：我们改变不了世界，是世界改变了我们。2、古之成大事者，不惟有超世之才，亦必有坚韧不拔之志。3、故天将降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为，所以动心忍性，曾益其所不能。

2014-03-05 23:23:46 740

原创 HDU(2059)动态规划问题

对于动态规划问题，可以按步骤来做：1、分解出子问题。2、求得子问题的最优解。首先将问题转化为：到达一个站点 i 的最优解。对于每一个站点 i ，我们可以假设在第 j ( 0 (1) 当从第j个站点到第i个的距离大于电动车能够行使的距离时，需要开与骑相结合。(2) 当从第j个站点到第i个的距离小于电动车能够行使的距离时，只需要开到。#include#

2014-03-05 21:23:43 1014

原创动态规划

动态规划和贪心算法相似，都是用来求解最优解的，但是区别也很大，适合动态规划求解的问题，也满足最优子结构性质，却不一定满足贪心的选择的性质，贪心算法是局部最优解，其实在动态规划中，贪心算法被替换成无后效性。动态规划的基本思想动态规划的基本思想源自递归，是一种问题转化策略，基于递归的问题转化策略有限多。例如：有一个由正整数组成的三角形，第一行只有一个数，除了最下行外，每个数的左下方和右下方

2014-03-05 16:50:00 863

原创 HDU(2058)条件限制

刚开始用的是枚举，结果不出意外的超时了，分析了一下，这题主要考察等差数列的运用，看来数学学得扎实，程序才能简洁，才能高效，重视先数学思维，再程序实现，数学好，才是真的好。等差数列求和公式：Sn=(a1+aN)*n/2 =(a1+a1+d(n-1))*n/2 =a1*n+d(n-1)*n/2;若想使N项的和等于M，先看看N的最大值为多少，然后再逐级递减至1，这一步

2014-03-05 11:20:38 777

原创 hdu(2054)

一个字符串处理问题，需要注意的是小数点问题，如果小数点后面有0，则需要将小数点后面的0，去掉，才能相互比较。strstr( s , "." ) 即可查到字符串s中是否有小数点，如果查到，返回小数点在字符串中的位置，如果不存在，则返回NULL#include#include#includeusing namespace std ;char s1[100000] , s2[1000

2014-03-05 10:13:50 660

原创 HDU(2057)十六进制数相加

本来想把十六进制的数先转化为十进制的数相加，然后再转化为十六进制的数输出，网上一搜，原来C语言如此强大，可以直接用十六进制输入，十六进制的数输出。非常气氛学校开学没学C语言，来的就开始学C++；导致C语言中的很多地方都不会用。输入八进制%o输入十进制 %d输入十六进制 %x输出也是一样，同时还提供了进制之间的加、减、乘、除C语言实在是太简便了，有空要多看看C语言运用的细

2014-03-04 21:04:40 1059

原创 HDU(2056)程序中的条件限制

一道很简单的数学题，但还是花了不少时间才给过掉！很遗憾，数学功底太差，希望以后遇到类似题，不会再这么模糊了。解决本题的步骤：1、注意给的对角线不一定是主对角线，但是记住对角线上的点都是单调的，所以很容易就可以给调过来，调成新的四个点坐标。2、还需要判断形成的两个矩形是否有相交的部分，如果没有直接输出0.00，判断条件是第四个点的横坐标、纵坐标都大于第一个点的，且第三个点的横、纵坐标都小

2014-03-04 20:20:44 1168

原创平面分割问题汇总

先看n条直线相交最多可把平面分割为几个部分：设n-1条直线可把平面分割为f(n-1)个部分，则第n条直线需与平面中每一条直线相交才能使得把平面分割的个数达到最多，所以平面中有多增加了n-1个交点，平面又多了n块，f(n) = f(n-1) + n ;若每次添加两条平行直线，则在第n次添加时，前面已经有2*(n-1) 条直线，添加第2*(n-1) + 1 条直线时，可以增加2

2014-03-04 10:54:09 908

原创 hdu(2048)全错位排列

N张票的全排列为N! 种方式，而第N张票的错排有几种：1、当前面N-1个人都拿的不是自己的票，而第N个人拿的是自己的票，只需要把自己的票与前面n-1个人中任何一个人交换，就可以形成前N 张票的错排；2、当前面N-1个人中有一个人拿的是自己的票，而第N个人拿到不是自己的票，只需要把自己的票和那个中奖人的票换一下，就可以形成前N张票的错排，但前N-1个人每个人都有可能拿到自己的票；综上所述

2014-03-04 09:06:13 874

原创递推算法

对待递推类的题目，具体问题，具体分析！递推算法首要问题是为了找到相邻数据项的关系——即递推关系。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了一个若干步连续的简单计算，递推算法也可以看成一种特殊的迭代算法！【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。　 1、一步可沿左斜线向

2014-03-03 20:57:09 1475

原创信息战（一）——加密程序

信息战（一）——加密程序Time Limit: 1000msMemory Limit: 65536KB64-bit integer IO format: %lld Java class name: MainPrev Submit Status Statistics Discuss NextFont Size: + -Ty

2014-03-03 17:44:46 1192

原创 HDU(2047) 递推公式

做了几道关于求递推公式的题，但一直没有总结出什么规律出来：这道题的要求只有一个就是“o”与“o”不能相邻，找出前三个数值出来以后，规律很容易就可以找出来，但究竟是怎样推出来的，还是不知道个所以然来！计数 + 简单限制 = 递推f(n)表示第n个满足要求的涂法个数！如果第n个涂的是“o”，则倒数第二个满足要求的涂法不等于f(n-1)；因为前面一个不能涂“o”，而倒数第三个满足要

2014-03-01 12:04:18 988

原创 HDU(2045)

不容易系列之(3)—— LELE的RPG难题一个公式的推导：当只涂一个格子的时候有3种涂法当涂两个格子的时候有6种涂法当涂三个格子的时候有6种涂法当涂四个格子的时候如果前面三个都涂好了，第四个只有一种涂法，如果是前面两个都涂好了，第四个有两种涂法。第n个格子的涂法如果等于第

2014-02-28 14:56:50 1542

转载 7个顶级心理预言

7个顶级心理预言（一）成长的寓言：做一棵永远成长的苹果树一棵苹果树，终于结果了。第一年，它结了10个苹果，9个被拿走，自己得到1个。对此，苹果树愤愤不平，于是自断经脉，拒绝成长。第二年，它结了5个苹果，4个被拿走，自己得到1个。“哈哈，去年我得到了10％，今年得到20％！翻了一番。”这棵苹果树心理平衡了。但是，它还可以这样：继续成长。譬如，第二年，它结了100个果子，被拿走

2014-02-28 13:37:28 731

原创 HDU(2079)选课时间

又到了选课的时间了，xhd看着选课表发呆，为了想让下一学期好过点，他想知道学n个学分共有多少组合。你来帮帮他吧。（xhd认为一样学分的课没区别）Input输入数据的第一行是一个数据T，表示有T组数据。每组数据的第一行是两个整数n(1 接着有k行，每行有两个整数a(1 Output对于每组输入数据，输出一个整数，表示学n个学分的组合数。

2014-02-28 11:14:56 3744 2

转载母函数详解和史上最通用最高效的母函数模板

2014-02-27 20:06:54 839

原创 HDU(2044)(一只小蜜蜂……)

Problem Description有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。其中，蜂房的结构如下所示。 Input输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0 Output对于每个测试实例，请输出蜜蜂从蜂

2014-02-27 17:42:08 798

原创 HDU(2043) 密码

#include#include#includeusing namespace std ;int main() { int n ; while( cin >> n ) { while( n-- ) { char s[60] ; bool flag = true ; cin >> s ; int len = strlen(s) ; if( len 16

2014-02-27 15:52:23 793

原创 HDU(2041) (超级楼梯)

第一次用递归搞，很高兴结果对了（^_^）悲催的的是提交之后，返回了一个 Time Limit Exceeded 看来递归看似简单，其实相当复杂耗时。递归代码如下：#include#includeusing namespace std ;int count = 0 ;void Search( int m ) { if( m ) { Search( m-1 ) ;

2014-02-27 14:58:00 889

原创 HDU（2037）贪心算法之时间序列

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n Output对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。 Sample Input121 33 40 73 815 1915 2010 158 186 125 104 142 90 Sampl

2014-02-27 11:46:54 1478

原创 HDU(2036) 求多边形面积

这道题只要知道求多边形面积公式即可：把（0,0）点作为原点。求多边形面积公式：S = 0.5 * ( x(0)*y(1) - x(1)*y(0) + x(1)*y(2) - x(2)*y(1) ……x(n)*y(0) - x(1)*y(n) )

2014-02-27 09:29:04 678

原创二分求幂

可用递归实现，也可用非递归实现。方法一（递归实现）：#includeusing namespace std ;int Pow( int n , int m ) { if( m == 0 ) return 1 ; if( m == 1 ) return n ; double P = Pow( n , m >> 1 ) ; P *= P ; if( m % 2 ) P

2014-02-26 20:56:24 651

原创左移（<<）与右移（>>）

左移（i = i 右移（>>）i = i >> n ; 相当于 i = i / ( 2 ^ n )

2014-02-26 20:00:49 769

原创 sort与qsort

sort用在C++语言中，qsort用在C语言中，参数不同。sort函数参数只有两个整型，头文件（#include）而qsort函数参数有四个；头文件（#include）;int a[10] = {0,1,2,3,4,5,6,7,8,9} ;sort( a , a+10 ) ; // 从小到大排序；bool cmp(int a , int b){return a >

2014-02-26 18:35:35 611

原创 alpha函数

运用alpha函数可以方便判断输入的字符类型是否为字母，头文件（#include）#include#include#include#includeusing namespace std ;int main() { char s[] = "C++" ; for( int i = 0 ; i < strlen(s) ; i++ ) if(isalpha(s[i])

2014-02-26 10:41:26 5075

原创 STL 队列

queue（队列）数据结构的基础，一种特殊的线性表，队列就像排队打饭一样先排的先打，后排的后打；只能从前面出，从后面进；queue q ;q.pop()删除第一个元素q.push( x )将 x 添加到最后q.front() 访问第一个元素q.back()访问最后一个元素q.empty()判断队列是否为空q.size()判断队列中元素的个数在

2014-02-21 13:35:45 831

原创 HDU(1753)

Flip GameTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 27202 Accepted: 11803DescriptionFlip game is played on a rectangular 4x4 field with two-sided p

2014-01-08 16:39:07 773

原创 scanf / cin / getchar

#include int main() { char ch1, ch2; scanf("%c", &ch1); scanf("%c", &ch2); printf("%d %d\n", ch1, ch2); return 0; }输入 a a ；输出 97 32 ； #include #includeu

2014-01-08 15:00:56 785

原创 CSDN 报数游戏-双向循环链表实现

通过这道题，对于链表的运用感觉灵活了许多……有n个人编号1-n，按照顺时针方向围成一个圆圈。它们预先定义好两个整数x,y。先从1号顺时针方向开始报数，报到x的人出圈，再从x的逆时针方向的后一个人从1开始报数，报到y的人出圈，再从这个人的顺时针方向后一个人开始从1报数，报到x的人出圈，如此反复，直到最后剩下一个人为止，问最后剩下的那个人是几号？比如n = 10, x = 3, y =

2014-01-06 17:44:09 1881

空空如也

空空如也