作者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)