计算机科学论坛--显示贴子

以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『算法理论与分析』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  请教高手三个关于算法的问题!  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=62006)

--  作者：lanyuandong
--  发布时间：4/29/2008 10:44:00 PM

--  请教高手三个关于算法的问题!

第一个题目:

给出一个求两个矩阵乘积并对结果矩阵元素从小到大排序的算法.要求时间和空间复杂度尽可能好,分析算法的时间复杂度.

第二个题目:

图G是两个C4k(4k是下标)的卡氏积图,G的V={(x1,x2)|x1,x2属于C4k}(x1,x2)和(y1,y2)相邻当x1=y1且x2和y2在C4k中相邻,或者x2=y2且x1和y1在C4k中相邻,要求G中任意两点的最短路径和所有最短路径中的最大值(用k的函数表示),其中C4k是4k个结点的圈.

第三个题目:

交换树T1的某些结点的左右子树得到T2,这样我们就说T1和T2同构,写一个算法来判断两棵树是否同构

希望给出解答的高手们,说得详细点
非常感谢!

--  作者：冬天的农夫
--  发布时间：4/30/2008 3:10:00 PM

--
对于第一个问题：
题目中没有说是不是稀疏矩阵，于是考虑一般性，将两个矩阵都以二维数组的方式存储起来。
根据行列计算出结果需要多大的空间。使用堆排序，将每个行列相乘的结果放入堆中。乘完之后再输出。假设两个矩阵的大小分别是l1*r1, l2*r2, 则时间复杂度为O(l1*r2*log(l1*r2))。空间复杂度为O(l1*r2)
第二题没有看明白，是哪本书上的？
第三题：
我这样写，不知道对不对，请大大们看看：
bool Isomorphic(BST *root1, BST *root2)
{
   if (root1->num() == 0|| root2->num() == 0)
      return true;
   if (root1->left->num() == root2->left->num() &&
       root1->right->num() == root2>right->num() &&
       root1->left->num() != root1->right->num() )
       return Isomorphic(root1->left, root2->left) && Isomorphic(root1->right, root2->right) ;
   else if (root1->left->num() == root2->left->num() &&
       root1->right->num() == root2>right->num() &&
       root1->left->num() == root1->right->num() )
      return (Isomorphic(root1->left, root2->left) && Isomorphic(root1->right, root2->right) ) || ( Isomorphic(root1->left, root2->right) && Isomorphic(root1->right, root2->left) );
      else if (root1->left->num() == root2->right->num() &&
       root1->right->num() == root2>left->num() )
      return Isomorphic(root1->left, root2->right) && Isomorphic(root1->right, root2->left) ;
      else
         return false;
}
其中root1->num()返回root的所有子孙节点数。
伪码只反映了我对这个问题解答的思想。

--  作者：lanyuandong
--  发布时间：4/30/2008 10:45:00 PM

--
感谢"冬天的农夫"第一题应该是没问题
第三题我也想出解决的办法
第二题目也是相对最难的一个
是离散数学中图论部分的题目
图G是两个C4k(4k是下标)的卡氏积图,"""G的V={(x1,x2)|x1,x2属于C4k}(x1,x2)和(y1,y2)相邻当x1=y1且x2和y2在C4k中相邻,或者x2=y2且x1和y1在C4k中相邻""",要求G中任意两点的最短路径和所有最短路径中的最大值(用k的函数表示),其中C4k是4k个结点的圈.
三个引号括起来的部分就是对卡氏积图的定义,也就是说G中两个结点之间有边的条件.
希望您能再次回复我，就算不知道如何解答也要告诉我,如何给你100分,哈哈,我还不太知道如何使用.

--  作者：冬天的农夫
--  发布时间：5/4/2008 12:23:00 PM

--
五一回家了。。不好意思。。明白你说的意思了

对于问题二：
所有最短路径中的最大值应该是2K。
因为在一个圈中两个顶点最大的距离会是K
两个圈的积图可以这样考虑取点：
选定<v1,u1>和<vk,uk>则这两个点的距离最大。
因为：通俗的说就是v1和vk最远，u1和uk最远。。。
我可能不是说得很明白，看你能不能理解。

要求G中任意两点的最短路：
|<(Vi, Uj),(Vg, Uh) >| = (i-g+2k)mod2k + (j-h+2k)mod2k;
要是不明白再发帖问吧

还有我开了个离散的答疑帖，可以在上面提问。
http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=61407

--  作者：Logician
--  发布时间：5/4/2008 4:41:00 PM

--
2. 记 V(G) = {<i,j>| 0<=i,j<=4k}，则 E(G) = { (<i,j>,<i+1 mod 4k, j>), (<i,j>,<i,j+1 mod 4k>) | 0<=i,j<4k}

易见，对任意<a,b>,<c,d>属于V(G)，若 max{|c-a|,4k-|c-a|} = x<=2k，max{|d-b|,4k-|d-b|} = y <=2k，那么从<a,b>到<c,d>的最短路长度为x+y。（这个结论的证明依赖于，E(G)中的每一条边只会让<i,j>的某一个坐标模4k增1或模4k减1。）
从而G的直径（即最长的最短路距离）为4k。

--  作者：冬天的农夫
--  发布时间：5/4/2008 10:01:00 PM

--
不好意思，我看错题了，把4k当作2k了
修改一下：
所有最短路径中的最大值应该是4K。
因为在一个圈中两个顶点最大的距离会是2K
两个圈的积图可以这样考虑取点：
选定<v1,u1>和<vk,uk>则这两个点的距离最大。
因为：通俗的说就是v1和vk最远，u1和uk最远。。。
我可能不是说得很明白，看你能不能理解。

要求G中任意两点的最短路：
|<(Vi, Uj),(Vg, Uh) >| = (i-g+4k)mod4k + (j-h+4k)mod4k;

--  作者：lanyuandong
--  发布时间：5/5/2008 9:46:00 AM

--
谢谢大家的解答,我还想问一个问题,这些东西在什么书上能学到,能推荐一本相关的书吗?
因为离散数学上对这个东西只是一带而过
再次谢谢您们

--  作者：冬天的农夫
--  发布时间：5/12/2008 5:01:00 PM

--

以下是引用lanyuandong在2008-5-5 9:46:00的发言：
谢谢大家的解答,我还想问一个问题,这些东西在什么书上能学到,能推荐一本相关的书吗?
因为离散数学上对这个东西只是一带而过
再次谢谢您们

北大有本离散的书很全面

--  作者：kinghere
--  发布时间：5/23/2008 7:16:00 PM

--
。。。。。。。。。。

W 3 C h i n a ( since 2003 ) 旗下站点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》

3,613.281ms