// 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) 燈泡開關 的程式碼 --
bulb.txt 檔案內容範例 :
#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;
}
//==============
5
1 2 3 2 1
7
0 0 0 777 0 0 0
(2) 遇見一株樹 的程式碼 --
tree.txt 檔案內容範例 :
#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;
}
//==============
*
((((((*))))))
(*******)
(*(**)(*))
