作者qazwsxee (小尧)
看板Grad-ProbAsk
标题Re: [理工] [资结]-程式设计
时间Thu Jan 28 17:45:45 2010
※ 引述《nonagoner (哈)》之铭言：
: 1.Write a function to check whether the contents of two stacks have the same
: number of elements. Neither stack should be changed.
写个函数出来~确认2个stack的有相同数目的元素个数~两个堆叠都不能被改变
(最後函式结束时~stack的内容不变)
function check_stack(stack_1 , stack_2)
{
string x,array[n]; ///定义字串型别 x与一个ㄧ维阵列
int y=0,z=0;
while(stack_1 != null)
{
x = pop(stack_1); /// 不断取出stack的Top端的内容
y++; /// 并y=y+1纪录个数(y= 1 ~ stack个数)
array[y] = x; /// 把这些内容依序存入阵列[1],[2],[3]....[y]
}
for(int i=y;i>=1;i--)
{
Push(stack_1,array[i]) /// 知道个数後，开始把阵列的值由
/// [y],[y-1],...[2],[1]反向放回去
} ///至此stack_1不变，但得到y=【stack_1元素个数】
while(stack_2 != null) ///stack_2同上 最後取得z = 【stack_2元素个数】
{
x = pop(stack_2);
z++;
array[z] = x;
}
for(int i=z;i>=1;i--)
{
Push(stack_2,array[i])
}
if(y==z) ///最後判断y跟z的数字(各自的元素个数)有没有相符
{ ///就可知道 要传回true或false了
return true;
}
else
{
return false;
}
}
: 2.Write an algorithm that determines whether a binary tree is complete.
: 想不太出来要怎麽写 有高手可以解答吗~谢谢
设node数有n个
树高:h
为每一个node做编号
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
由上层到下层，由左到右，对每个node 依序编号
第一层 (root)编号1
第二层 编号2，编号3
...
..
第i层
编号2^(i-1),编号2^(i-1)+【1】,编号2^(i-1)+【2】,...,编号2^(i-1)+【2^(i-1)-1】
直到最後ㄧ个node做完结束。
开始 由上到下，由左往右找
去对每ㄧ个node做以下判断
//注: [A/2]就是 A除2 取整数
假设这个node编号是A
if( (这个node的父点的编号是 [A/2]) &&
[(node编号为偶数&&是父点的左子点) || (node编号为奇数&&是父点的右子点)] )
{
那麽此 binary tree is complete 。
}
else
{
那麽此 binary tree is not complete 。
}
eg
1
/ \
2 3
\ / \
4 5 6
node编号4 => 父点编号 = 2 = [4/2]
5 => 父点编号 = 3 != [5/2] //这个node违反，故此tree is not complete
6 => 父点编号 = 3 = [6/2]
1
/ \
2 3
\
4
编号4的node =>编号为偶数，但却是父点的右子点!
违反!
1
/ \
2 3
/
4
编号4的node => 父点为编号3，不是正确编号2。
违反!
----------
ㄧ起讨论看看吧~有疑虑请跟我说
演算法跟函数不难写
写法有很多种~不同人写出来有不同的样子~~
--
◤ ╭
● 嫂子 叫我胡子就好了 ＿(
▁)
▁
◤龙▃▄▅▄ 我会很有礼貌的 ( ﹎﹎ )
§ ● ● ╯ ＝ ＝ │
◣ ︶ ◣─ ◢
─ ◥◤) ψmroscar ╰斗╯
◢ | |
三明书局-你所不知道的关二哥 ◥
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.39.210.24
1F：推 FRAXIS:那就看他说不能改变 是说计算中途不能改变 01/28 18:35
2F：→ FRAXIS:还是说 计算前和计算後一样即可 01/28 18:36
计算後 原Stack的内容值 没改变即可
※ 编辑: qazwsxee 来自: 114.39.210.24 (01/28 19:10)
3F：推 nonagoner:感谢解答第一题很清楚 不过第二题不知道有没有办法算高 01/28 20:22
4F：→ nonagoner:用递回写出呢? 01/28 20:22
{F(n) = log n +1
{ 2
{f(1)=1 //f(1)=>ㄧ个节点=> 就是root =>我设此树的高度【由1开始】
1~h
若【由0开始】F(n)就不用多+1
有几个节点~就可知道高为多少~
※ 编辑: qazwsxee 来自: 114.39.210.24 (01/28 20:35)
5F：推 FRAXIS:第二题应该可以不用编号 直接用递回判断 01/28 20:45
演算法写法有很多种~不同人写出来有不同的样子~~考试时可以想得出来即可罗
height(t) = if (t==NULL) then 0 ///若为空=>下方没有子树，回传0
else 1+ max(height(t.left),height(t.right))
//若不为空，比较(t的左子树高度)和(t的右子树高度)取较大值
//然後 1+那个Max值 即是树高
这是递回的程式写法~
若n=1 (只有root点)
height(n) => height(n)不为空 => 比较(t的左子树高度)和(t的右子树高度)取较大值
=>height(t的左子树高度) =NULL(空) ，回传0
=>height(t的右子树高度) =NULL(空) ，回传0
height(n) = 1 + Max(0,0)= 1 => 高度就是1罗
※ 编辑: qazwsxee 来自: 114.39.210.24 (01/28 21:54)