5361人阅读
数据结构/算法（33）
求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，
优化时间空间杂度。
计算一个二叉树的最大距离有两个情况:
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
首先算出经过根节点的最大路径的距离，其实就是左右子树的深度和；然后分别算出左子树和右子树的最大距离，三者比较，最大值就是当前二叉树的最大距离了。
代码如下：
/*-----------------------------
Copyright by yuucyf.
------------------------------*/
#include &stdafx.h&
#include &iostream&
#include &assert.h&
typedef struct tagSBTreeNode
tagSBTreeNode *psL
tagSBTreeNode *psR
tagSBTreeNode()
psLeft = psRight = NULL;
nValue = 0;
nMaxLeft = nMaxRight = 0;
void AddTreeNode(S_TreeNode *&psTreeNode, int nValue)
if (NULL == psTreeNode)
psTreeNode = new S_TreeN
assert(NULL != psTreeNode);
psTreeNode-&nValue = nV
else if (psTreeNode-&nValue & nValue)
AddTreeNode(psTreeNode-&psRight, nValue);
AddTreeNode(psTreeNode-&psLeft, nValue);
int MaxDepth(const S_TreeNode *psTreeNode)
int nDepth = 0;
if (NULL != psTreeNode)
int nLeftDepth = MaxDepth(psTreeNode-&psLeft);
int nRightDepth = MaxDepth(psTreeNode-&psRight);
nDepth = (nLeftDepth & nRightDepth) ? nLeftDepth : nRightD
int MaxDistance(const S_TreeNode *psRootNode)
int nDistance = 0;
if (NULL != psRootNode)
nDistance = MaxDepth(psRootNode-&psLeft) + MaxDepth(psRootNode-&psRight);
int nLeftDistance = MaxDistance(psRootNode-&psLeft);
int nRightDistance= MaxDistance(psRootNode-&psRight);
nDistance = (nLeftDistance & nDistance) ? nLeftDistance : nD
nDistance = (nRightDistance & nDistance) ? nRightDistance : nD
int _tmain(int argc, _TCHAR* argv[])
S_TreeNode *psRoot = NULL;
AddTreeNode(psRoot, 9);
AddTreeNode(psRoot, 6);
AddTreeNode(psRoot, 4);
AddTreeNode(psRoot, 8);
AddTreeNode(psRoot, 7);
AddTreeNode(psRoot, 15);
AddTreeNode(psRoot, 13);
AddTreeNode(psRoot, 16);
AddTreeNode(psRoot, 18);
cout && &任意两个节点间的最大距离为:& && MaxDistance(psRoot) &&
思路一不是效率最高的，因为在计算二叉树的深度的时候存在重复计算。但应该是可读性比较好的，同时也没有改变原有二叉树的结构和使用额外的全局变量。这里之间给出代码，因为代码的注释已经写的非常详细了。
代码如下：
int g_nMaxLeft = 0;
void MaxDistance_2(S_TreeNode *psRoot)
// 遍历到叶子节点，返回
if (NULL == psRoot)
// 如果左子树为空，那么该节点的左边最长距离为0
if (psRoot-&psLeft == NULL)
psRoot-&nMaxLeft = 0;
// 如果右子树为空，那么该节点的右边最长距离为0
if (psRoot-&psRight == NULL)
psRoot -& nMaxRight = 0;
// 如果左子树不为空，递归寻找左子树最长距离
if (psRoot-&psLeft != NULL)
MaxDistance_2(psRoot-&psLeft);
// 如果右子树不为空，递归寻找右子树最长距离
if (psRoot-&psRight != NULL)
MaxDistance_2(psRoot-&psRight);
// 计算左子树最长节点距离
if (psRoot-&psLeft != NULL)
int nTempMax = 0;
if (psRoot-&psLeft-&nMaxLeft & psRoot-&psLeft-&nMaxRight)
nTempMax = psRoot-&psLeft-&nMaxL
nTempMax = psRoot-&psLeft-&nMaxR
psRoot-&nMaxLeft = nTempMax + 1;
// 计算右子树最长节点距离
if (psRoot-&psRight != NULL)
int nTempMax = 0;
if(psRoot-&psRight-&nMaxLeft & psRoot-&psRight-&nMaxRight)
nTempMax = psRoot-&psRight-&nMaxL
nTempMax = psRoot-&psRight-&nMaxR
psRoot-&nMaxRight = nTempMax + 1;
// 更新最长距离
if (psRoot-&nMaxLeft + psRoot-&nMaxRight & g_nMaxLeft)
g_nMaxLeft = psRoot-&nMaxLeft + psRoot-&nMaxR
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：217119次
积分：2686
积分：2686
排名：第10062名
原创：50篇
转载：24篇
评论：82条
(2)(1)(2)(1)(1)(12)(2)(5)(14)(6)(8)(10)(1)(2)(2)(4)(1)答案：略解析：
(1)结果越来越小，趋向于0；
(2)结果越来越大，但也趋向于0．
请在这里输入关键词：
科目：初中数学
任意找一个正数，比如1234，利用计算器对它进行开平方，再对得到的平方根进行开平方……如此进行下去，你有什么发现？
科目：初中数学
来源：2012年浙教版初中数学七年级上3.4用计算器进行数的开方练习卷（解析版）
题型：解答题
任意找一个正数，利用计算器对它进行不断的开算术平方根运算，你发现了什么？
科目：初中数学
题型：解答题
任意找一个正数，利用计算器对它进行不断的开算术平方根运算，你发现了什么？
科目：初中数学
来源：四川省期末题
题型：单选题
任意找一个正数，比如2007，利用计算器对它进行开平方，再对得到的平方根进行开平方……如此进行下去，你发现的结果是
[&&&& ]A．-1 B．0 C．1 D．每次开平方的结果逐渐减小，并趋近于1
精英家教网新版app上线啦！用app只需扫描书本条形码就能找到作业，家长给孩子检查作业更省心，同学们作业对答案更方便，扫描上方二维码立刻安装！《数据结构与算法分析:C语言描述_原书第二版》CH2算法分析_课后练习_部分解答 - 数据结构与算法当前位置:& &&&《数据结构与算法分析:C语言描述_原书第二版》CH2算《数据结构与算法分析:C语言描述_原书第二版》CH2算法分析_课后练习_部分解答&&网友分享于：&&浏览：0次《数据结构与算法分析:C语言描述_原书第二版》CH2算法分析_课后习题_部分解答对于一个初学者来说，作者的Solutions Manual把太多的细节留给了读者，这里尽自己的努力给出部分习题的详解:
不当之处，欢迎指正。
1、& 按增长率排列下列函数：N，&2，N1.5，N2，NlogN， NloglogN，Nlog2N，Nlog(N2)，2/N，2N，2N/2，37，N2logN，N3。指出哪些函数以相同的增长率增长。
　　 答：排列如下2/N & 37 & &2 & N & NloglogN & NlogN & Nlog(N2) & Nlog2N & N1.5 & N2 & N2logN & N3 & 2N/2 & 2N。
　　&其中，NlogN&与 Nlog(N2) 的增长率相同，均为O(NlogN)。
　　 补充说明：a) 其中 Nlog2N&与 N1.5，&N3&与 2N/2大小关系的判定，可以连续使用洛必达法则（N-&&时，两个函数比值的极限，等于它们分别求导后比值的极限）。当然，更简单的是两边直接求平方。
&　　　　　　　b) 同时注意一个常用法则：对任意常数k，logkN = O(N)。这表明对数增长得非常缓慢。习题3中我们会证明它的一个更严格的形式。
2、& 函数NlogN 与 N1+&/&logN (&&0) 哪个增长得更快？
　　 分析：我们首先考虑的可能是利用洛必达法则，但是对于第二个函数其上下两部分皆含有变量，难以求导（当然也不是不行，就是麻烦些，如果你愿意设y = N1+&/&logN ，然后对两边取对数的话）。这里我们将利用反证法：
　　 要证NlogN&& N1+&/&logN ，即证 logN & N&/&logN。既然用反证法，那么我们假设 N&/&logN & logN。两边取对数有 &/&logN logN & loglogN。即 &&logN & loglogN。设t = logN，则 &&t & logt &=& &2t & log2t，这显然与连续1中b)矛盾，因此假设 N&/&logN & logN 不成立。因此函数 N1+&/&logN增长得更快。
3、& 证明对任意常数k，logkN = o(N)。
　　 解：要证明命题成立，只需证limn-&&(logkN / N) = 0即可。证明如下：
　　 首先，如果k1 & k2，显然有 logk1N = o(logk2N) 。且k = 0时，logkn = 1。应用洛必达法则，limn-&&(logiN / N) = limn-&&(ilogi-1N / Nln2) = limn-&&(logi-1N / N)&。（说明：这里舍弃常数是因为我们假设函数最终的比值为0，否则不可简单的丢弃常数。当然如果比值不为零的话，我们需要返回到这里另行处理，其实证明过程也是不断尝试、调整的，此路不通，另行它法嘛:）就是说，通过不断地规约，最终极限的比值等于零，命题得证。
&4、 求两个函数 f(N) 和 g(N)，使得 f(N)&& O(g(N)) 且 g(N) & O(f(N))。
　　 一个显然的例子是函数 f(N) = sinN，g(N) = cosN。
&5、 假设需要生成前N个自然数的一个随机置换。例如，{4，3，1，5，2} 和 {3，1，4，2，5} 就是合法的置换，但 {5，4，1，2，1} 却不是，因为数1出现两次而数3却没有出现。这个程序常常用于模拟一些算法。我们假设存在一个随机数生成器 RandInt(i, j)，它以相同的概率生成 i 和 j 之间的一个整数。下面是三个算法：
　　 1) 如下填入从 A[0] 到 A[N-1] 的数组 A：为了填入 A[i]，生成随机数直到它不同于已经生成的 A[0]，A[1]，... ，A[i-1]，再将其填入 A[i]。
　　 2) 同算法1)，但是要保存一个附加的数组，称之为 Used(用过的)数组。当一个随机数 Ran 最初被放入数组 A 的时候，置 Used[Ran] = 1。这就是说，当用一个随机数填入 A[i] 时，可以用一步来测试是否该随机数已经被使用，而不是像的一个算法那样（可能）进行 i 步测试。
　　 3) 填写该数组使得 A[i] = i + 1。然后：
　　for(i = 1; i & N; i++)
　　　　 Swap(&A[i], &A[RandInt(0, i)]);
　　 对每一个算法给出你能够得到的尽可能准确的期望的运行时间分析（用大O）。
　　 解：分析，对于1)，容易写出如下算法：
　for(i = 0; i & N; i++){
　　A[i] = RandInt(1, N);
　　for(j = 0; j & j++)
if(A[j] == A[i])
　　if(j == i)
　　 调用一次随机数字生成函数与前面已经生成的随机数（存放在A数组中的）不同的概率为&(N-i) / N，那么理论上经过&N / (N-i) 次随机数的生成我们可以确定其与已生成的概率为 1。因此该算法的期望运行时间为
当然，也可以对分子放大的同时对分母缩小，不过这样求得的时间界限为O(N2)，显然不如上面的做法精确。这里需要注意的一点是调和级数的前N项和，它是发散的，在计算机科学中的使用频率要远比在在数学等其它科目中使用得多。下面给出调和和：
其近似误差r = 0.，这个值称为欧拉常数（Euler&s constant）。
　　 对于2)，容易写出如下算法：　
for(i = 0; i & N; i++){
A[i] = RandInt(1, N);
if(Used[i] == 0){
Used[i] = 1;
　　 同1)的分析，其运行时间界限显然为O(NlogN)。
　　 对于3)，运行时间为O(N)，不消多说。
6、& 记录一个称为Horner法则的算法，该算法用于计算 F(X) = &Si=0~nAiXi的值。
for(i = N; i &= 0; i--)
Poly = X * Ploy + A[i];
&7、& 给出一个有效的算法来确定在整数 A1& & A2 & A3 & ... & AN 的数组中是否存在整数 i ，使得 Ai = i。你的算法的运行时间是多少？
　　& 分析：类似二分查找，直接上代码：
int(int[] a, int N){
int low = 0, high = N - 1;
while(low &= high){
middle = ((high-low) && 1) +
if(a[middle]) & middle + 1)
low = middle + 1;
// 搜索右空间
else if(a[middle] & middle + 1)
high = middle - 1; // 搜索做空间
return -1;
　　& 易知该算法的运行时间为O(logN)。
&8、& 如果7题中的语句 low = middle + 1 更该为 low = middle ，那么这个程序还能正确运行吗？
　　& 答：不能，设 low = n，high = n + 1，则 middle = n，程序陷入死循环。
&9、& a.编写一个程序来确定正整数N是否是素数，你的程序在最坏的情形下的运行时间是多少（用N表示）？（你应该能够写出O(&N)的算法程序）。
　　& b.令B等于N的二进制表示法中的位数。B的值是多少？
　　& c.你的程序在最坏情形下的运行时间是什么（用B表示）？
　　& d.比较确定一个20（二进制）位的数是否是素数和确定一个40（二进制）位的数是否是素数的运行时间。
　　& e.用 N&还是 B 来给出运行时间更合理，为什么？
　　& 解：对于a，由于 &N * &N = N，因此分解 N 时必有一个整数小于 &N。高效的算法思路是：首先，测试N是否能被2整除，不能的话测试N是否能被3，5，7，...，&N整除。编码如下（是素数返回1，不是返回0）：&
int IsPrime(int N){
if(N == 1)
if(N % 2 == 0)
for(i = 3; i &= int(sqrt(w) + 0.5); i += 2)
if(N % i == 0)
　　& 对于b，显然有，B = O(logN)。
　　& 对于c，由于B = O(logN)，则2B = O(N)，即2B/2 = O(&N)，所以用B表示的最坏情况下的运行时间是：O(2B/2)
　　& 对于d，后者的运行时间是前者运行时间的平方，由c中的解答易知。
　　& 对于e，Wiss说：B is the better measure because it more accurately represents the size of the input.
All Rights Reserved.
Author：海峰:)
Copyright & xp_jiang.
转载请标明出处：
&参考资料：Data Structures and Algorithm Analysis in C(second edition) Solutions Manual_Mark Allen Weiss_Florida International University.
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有双数乘双数的快速算法!看见一个快速算法,但是忘了,就是2位数乘2位数的快速算法技巧.谢谢
对于任意的两位数相乘,可以表示为(10a+b)×(10c+d),例如28×57=（10×2+8）×（10×5+7）展开得100ac+bd+10(ad+bc),可见是十位数a、c相乘（放在百位上）,加上个位数b、d相乘（放在个位）,再加上第三项就行了.前两项相加只要一秒钟,如上例的28×57,显然前两项分别为2×5=10,8×7=56,连上得1056.关键是第三项如何算得快.(ad+bc)表示十位和个位上的数交叉相乘再相加,（口诀：先乘后加.）“10”表示把计算结果的个位放在前两项和的十位上.还是拿上例来说,28×57的第三项是,2×7+8×5=14+40=54,这三项相加得最后结果,即6.第三项如能具有某些特征,就能算得更快.以下是几种算得更快的类型.一、如果个位或十位上的数相同此时第三项可以提取那个相同的数（公因子）,剩下的两个数相加后乘公因子即可.（口诀：加异乘同.）例如23×26=418+20×（3+6）=418+180=598；再如34×54=1516+40×（3+5）=1836.二、如果个位上的数相同,十位上的数相加等于10此时第三项就是把个位上那个相同的数放到百位上就行了.例如67×47=9.（口诀：十十尾进二.）三、如果十位上的数相同,个位上的数相加等于10此时把十位上的数乘上比其大1的数放在百位上,个位上的数相乘放在个位上即可.例如76×74,百位上的数是7×8=56,个位上的数是6×4=24,所以有76×74=5624.四、如果乘数（或被乘数）个位和十位上的数相同（例如22、77等）此时也是将这个相同的数字（公因子）提出来,另一数的两个数字相加,然后乘公因子.（口诀：加异乘同.）例如22×78=1416+20×（7+8）=6五、如果十位上的数和个位上的数都相等,就是求平方的问题了
为您推荐：
其他类似问题
有人问过了，这是网址，很具体的，自己打开看吧。/question/.html
ab * cd= (10a +b)*(10c+d)= 100*a*c + 10*b*c + 10*a*d + b*d= 100*a*c + 10*(b*c + a*d) + b*d百位 = a * c
十位*十位十位 = b * c + a * d
十位*个位+十位*个位个位 = b * d
个位*个位如果两位数，加到下个位置
扫描下载二维码int BitCount5(unsigned int n) {& & unsigned int&tmp = n - ((n &&1) &) - ((n &&2) &);
& & return ((tmp + (tmp &&3)) &) %63;}
最喜欢这个，代码太简洁啦，只是有个取模运算，可能速度上慢一些。区区两行代码，就能计算出1的个数，到底有何奥妙呢？为了解释的清楚一点，我尽量多说几句。
第一行代码的作用
先说明一点，以0开头的是8进制数，以0x开头的是十六进制数，上面代码中使用了三个8进制数。
将n的二进制表示写出来，然后每3bit分成一组，求出每一组中1的个数，再表示成二进制的形式。比如n = 50，其二进制表示为110010，分组后是110和010，这两组中1的个数本别是2和3。2对应010，3对应011，所以第一行代码结束后，tmp = 010011，具体是怎么实现的呢？由于每组3bit，所以这3bit对应的十进制数都能表示为2^2 * a + 2^1&* b + c的形式，也就是4a + 2b + c的形式，这里a,b,c的值为0或1，如果为0表示对应的二进制位上是0，如果为1表示对应的二进制位上是1，所以a + b + c的值也就是4a + 2b + c的二进制数中1的个数了。举个例子，十进制数6（0110）= 4 * 1 + 2 * 1 + 0，这里a = 1, b = 1, c = 0, a + b + c = 2，所以6的二进制表示中有两个1。现在的问题是，如何得到a + b + c呢？注意位运算中，右移一位相当于除2，就利用这个性质！
4a + 2b + c 右移一位等于2a + b
4a + 2b + c 右移量位等于a
然后做减法
4a + 2b + c&&(2a + b)&& a = a + b + c，这就是第一行代码所作的事，明白了吧。
第二行代码的作用
在第一行的基础上，将tmp中相邻的两组中1的个数累加，由于累加到过程中有些组被重复加了一次，所以要舍弃这些多加的部分，这就是&的作用，又由于最终结果可能大于63，所以要取模。
需要注意的是，经过第一行代码后，从右侧起，每相邻的3bit只有四种可能，即000, 001, 010, 011，为啥呢？因为每3bit中1的个数最多为3。所以下面的加法中不存在进位的问题，因为3 + 3 = 6，不足8，不会产生进位。
tmp + (tmp && 3)-这句就是是相邻组相加，注意会产生重复相加的部分，比如tmp = 659&= 001 010 010 011时，tmp && 3 = 000 001 010 010，相加得
001 010 010 011
000 001 010 010
---------------------
001&011&100 101
011 + 101 = 3 + 5 = 8。（感谢网友指正。）注意，659只是个中间变量，这个结果不代表659这个数的二进制形式中有8个1。
注意我们想要的只是第二组和最后一组（绿色部分），而第一组和第三组（红色部分）属于重复相加的部分，要消除掉，这就是&所完成的任务（每隔三位删除三位），最后为什么还要%63呢？因为上面相当于每次计算相连的6bit中1的个数，最多是111111 = 77（八进制）= 63（十进制），所以最后要对63取模。
感谢网友&提供
struct _byte
unsigned a:1;
unsigned b:1;
unsigned c:1;
unsigned d:1;
unsigned e:1;
unsigned f:1;
unsigned g:1;
unsigned h:1;
long get_bit_count( unsigned char b )
struct _byte *by = (struct _byte*)&b;
return (by-&a+by-&b+by-&c+by-&d+by-&e+by-&f+by-&g+by-&h);
感谢网友&提供
使用微软提供的指令，首先要确保你的CPU支持SSE4指令，用Everest和CPU-Z可以查看是否支持。
unsigned int n =127 ;unsigned int bitCount = _mm_popcnt_u32(n) ;
References