0.前言   

     二叉树（Binary Tree）的递归定义如下：二叉树要么为空，要么由根结点（root）、左子树（left subtree）和右子树（right subtree）组成，而左子树和右子树分别是一棵二叉树。

    树（tree）和二叉树类似，区别在于每个结点不一定只有两棵子树。比如树的目录，根结点有12棵子树：第1章，第2章，第3章，。。。、第12章，而第一章又有5棵子树：1.1，1.2，1.3，。。。1.5。

1.二叉树的编号

    【例题】6-6 小球下落

    【题目描述】

     有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右编号为1，2，3，。。。，2D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关，初始全部关闭。每当有小球落在一个开关上时，状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点。如下图所示

一个小球从结点1开始依次下落，最后一个小球将会落在哪里？输入叶子深度D和小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D<=20。输入最多包含1000组数据。

【样例输入1】

4 2  3 4  10 1  2 2  8 128  16 12345

【样例输出1】

12  7  512  3  255  36358

【题目描述】

给出一个长度位n的序列a,选出其中连续且非空的一段使得这段和最大

【输入描述】

第一行是一个整数，表示序列的长度n。

第二行有n个整数，第i个整数表示序列的第i个数字ai

【输出描述】

输出一行一个整数表示答案。

【样例输入】

7  2 -4 3 -1 2 -4 3

【样例输出】

4

【题目描述】

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设Wij 是 

从供应商j处购得的部件i的重量，Cij 是相应的价格。 

试设计一个算法，给出总价格不超过c的最小重量机器设计。 

′编程任务： 

对于给定的机器部件重量和机器部件价格，编程计算总价格不超过d的最小重量机器设 

计。

【输入描述】

第一行有 3 个正整数 n ，m和 d。接下来的 2n 行，每 

行m个数。前n行是c，后n行是w。

【输出描述】

将计算出的最小重量，以及每个部件的供应商输出。

【样例输入】

3 3 4   1 2 3   3 2 1   2 2 2   1 2 3   3 2 1   2 2 2

【样例输出】

4   1 3 1

1.问题描述及状态定义

数字三角形问题：有一个非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示：

从第一行开的数开始走，每次可以往下或右走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和最大?

【题目描述】

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1X1)子矩阵。

比如,如下4 x 4的矩阵

0    -2    -7    0

9    2    -6    2

-4    1    4    1

-1    8    0    -2

的最大子矩阵是

9    2

-4    1

-1    8

这个子矩阵的大小是15。

【输入描述】

输入是一个N x N的矩阵。输入的第一行$N(0<N<=100)$。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数...)给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127,127]。

【输出描述】

最大子矩阵的大小

【样例输入】

4   0 -2 -7  0   9  2 -6  2  -4  1 -4  1  -1  8  0 -2

【样例输出】

15

【题目描述】

      设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。

       例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213； 

       又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613

【输入】

       两行，第一行n。表示有n个数。

       第二行是 n个数。

【输出】

连接成的多位数

【输入样例】

3  13 312 343

【输出样例】

34331213