Re: [理工] [資結]-程式設計

[qazwsxee (小堯)]

※ 引述《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
推 FRAXIS:那就看他說不能改變 是說計算中途不能改變
→ FRAXIS:還是說 計算前和計算後一樣即可
計算後 原Stack的內容值 沒改變即可
※ 編輯: qazwsxee        來自: 114.39.210.24        (01/28 19:10)
推 nonagoner:感謝解答第一題很清楚 不過第二題不知道有沒有辦法算高
→ nonagoner:用遞迴寫出呢?
{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)
推 FRAXIS:第二題應該可以不用編號 直接用遞迴判斷
演算法寫法有很多種~不同人寫出來有不同的樣子~~考試時可以想得出來即可囉
推 nonagoner:http://tinyurl.com/yd6wcp8 這裡有寫一個不過看不懂...
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)