燈泡開關 與 遇見一株樹 (C語言)

//===============================================================
// 20090605 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1009060510662
// 附件: http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1106
// 發問者 :(ARX-7 ) http://tw.knowledge.yahoo.com/my/my?show=AC04610971
//===============================================================

這有兩個題目: (1)燈泡開關 與 (2)遇見一株樹
而這類題目都假定提供的數據都是正確的, 而求得 輸出結果.

(1) 燈泡開關 的程式碼 --

#include <stdio.h>
#include <stdlib.h>

const int Max=100000;
const unsigned int MaxNo = (unsigned int)1<<31; 
// === 主程式 ===
int main()
{
  int N, i, l, use;     // use : 亮燈的數量
  unsigned int bulbNo;  // 因燈號可達 2^31, 故需用無號int (32bits)
  unsigned int Light[Max];   // 燈亮紀錄; 實際只要 Max/2+1 即可
  FILE *file = fopen( "bulb.txt", "r");
  if (file==NULL) file=stdin;    // 若無bulb.txt 則人工輸入(Ctrl+Z結束)
  while(fscanf(file, "%d", &N)==1 && N>0 && N<=Max)  // 取得筆數
  {
     for(use=0, i=0; i<N; i++)  // 用迴圈來取得 N 筆資料
     {
        if (fscanf(file, "%u", &bulbNo)!=1 || bulbNo > MaxNo) break;
        for(l=0; l<use && Light[l]!=bulbNo; l++);  // 是否為燈亮?
        if (l<use) Light[l]=Light[--use];  // 是!! 滅燈(挪最後燈來蓋掉紀錄)
        else Light[use++]=bulbNo;   // 否!! 在末端紀錄燈亮
     }
     if (i<N || use!=1) break;  // 資料有誤--資料取得有誤 或 未剩一盞燈
     printf("%u\n", Light[0]);
  }
  if (file!=stdin) fclose(file);
  return 0;
}
//==============

bulb.txt 檔案內容範例 :
5
1 2 3 2 1
7
0 0 0 777 0 0 0


(2) 遇見一株樹 的程式碼 --

#include <stdio.h>
#include <stdlib.h>

const int Max=100001;   //樹的長度不超過100,000個字元, 多保留一位讀字串補\0

int ParseTree(char *tree, int *leaf, int *depth, int *ary, int d)
{ // d: 傳入的深度
  int p, a;  // p:字串處理位置  a:項次數
  for(p=0, a=0; tree[p]=='*' || tree[p]=='('; p++, a++)
  {
     if(tree[p]=='*') *leaf+=1;  // 統計葉子數量
     else p+= ParseTree(tree+p+1, leaf, depth, ary, d+1);  // '(' 遞迴
  }
  if (d>*depth) *depth=d;     // 傳回最深深度
  if (d>1 && a>*ary) *ary=a;  // 傳回子項(深度大於1)中,最大項次數
  return p+1;  // 回傳所處理的位置(長度)
}
// === 主程式 ===
int main()
{
  char tree[Max];
  int leaf, depth, ary;
  FILE *file = fopen( "tree.txt", "r");
  if (file==NULL) file=stdin;   // 若無tree.txt 則人工輸入(Ctrl+Z結束)
  while(fgets(tree, Max, file)!=NULL)  
  {
     leaf=depth=ary=0;
     ParseTree(tree, &leaf, &depth, &ary, 1);  // 解析 字串樹
     printf( "%d %d %d\n", leaf, depth, ary);
  }
  if (file!=stdin) fclose(file);
  return 0;
}
//==============

tree.txt 檔案內容範例 :
*
((((((*))))))
(*******)
(*(**)(*))