2010年11月29日 星期一

演算法 - 背包問題

包問題在演算法中為一經典題型,是一種最佳化的問題,而解決最佳化的問題,就需要用到「動態規劃」來解決,它是利用遞迴特性來拼湊出最佳解答。

以下就用 ACM 624 作為範例題目( 中文翻譯 ACM 624 ),提供解法並且解釋它是如何解決問題。

input:
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

output:
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

不過這裡將題目改一改,不是 CD 的問題,將 CD 改為背包,而每首歌的時間長度改為物品的公斤重,在背包最大限制重量下,最多能拿幾公斤。

以下為 C# 程式碼,首先需要宣告幾個全域變數:
static int[] item_kg_array; // 每件物品的公斤重
static bool[] record_item_isTake_array; // 紀錄臨時物品是否拿取
static bool[] best_item_isTake_array; // 紀錄最佳物品是否拿取
static int max_kg; // 背包公斤限制
static int item_count; // 物品數量
static int record_max_kg; // 紀錄目前最大公斤數
在程式開頭,讀取相關資料:
string line = Console.ReadLine();
string [] value = line.Split(new string[]{" "},
StringSplitOptions.RemoveEmptyEntries );

max_kg = Convert.ToInt32(value[0]);
item_count = Convert.ToInt32(value[1]);

item_kg_array = new int[item_count];
record_item_isTake_array = new bool[item_count];
best_item_isTake_array = new bool[item_count];

for (int i = 2; i < item_count + 2; i++)
item_kg_array[i - 2] = Convert.ToInt32(value[i]);

record_max_kg = 0;
接著就是重點程式碼,以下程式碼為一函式,函式傳入索引 index 與目前公斤重 now_kg,函式一開始就先判斷 now_kg 是否大於目前最大公斤重 record_max_kg 且 now_kg 小於背包公斤限制 max_kg,如果條件成立,則紀錄 record_max_kg 為 now_kg 且紀錄最佳拿取方式 best_item_isTake_array 為 record_item_isTake_array。
再來判斷 index 使否小於物品數量 item_count,如條件成立,則先將目前索引是否拿取設置成 true 後再次呼叫自己傳入索引值加 1 及目前公斤數加上物品在索引值位置的公斤重兩數,如不成立,將目前索引是否拿取設置成 false 後再次呼叫自己傳入索引值加 1 及目前公斤數。如此一來,程式就會像「二元樹」一樣,依照 index 索引值分別來展開拿與不拿此物品的樹,而答案就會呼之欲出了。
static void knapsack(int index, int now_kg)
{
if (now_kg <= max_kg && now_kg > record_max_kg)
{
record_max_kg = now_kg;
for (int j = 0; j < index; j++)
best_item_isTake_array[j] = record_item_isTake_array[j];
}
if (index < item_count)
{
record_item_isTake_array[index] = true;
knapsack(index + 1, now_kg + item_kg_array[index]);
record_item_isTake_array[index] = false;
knapsack(index + 1, now_kg);
}
}
最後在主程式最後呼叫並且印出:
knapsack(0, 0);
for (int i = 0; i < item_count; i++)
if (best_item_isTake_array[i]) Console.Write("{0} ", item_kg_array[i]);
Console.WriteLine("sum:{0}", record_max_kg);


回首頁

2010年11月24日 星期三

演算法 - 老鼠走迷宮

鼠走迷宮為演算法中較基本的題型,給一迷宮圖形,畫出起點到終點的解法與解法數量,亦或是算出解法步數,都可以利用以下程式算出。

與大部分的演算法相同,老鼠走迷宮是利用遞迴的特性,使得老鼠能判斷上下左右是否有路,並且走到死路能回頭再找別的路走。
以下例子為左上走到右下的迷宮。
input:
8 7
..XXXXXX
X......X
X.X.XX.X
X.X.X..X
XXX.XXXX
X......X
XXXXXX..

output:
--XXXXXX
X---...X
X.X-XX.X
X.X-X..X
XXX-XXXX
X..----X
XXXXXX--

以C#為例子,用String.Split讀取 row 與 col:
string line = Console.ReadLine();
string[] value = line.Split(new string[]{" "},
StringSplitOptions.RemoveEmptyEntries);
int col = Convert.ToInt32(value[0]);
int row = Convert.ToInt32(value[1]);
接著宣告一個 char 二維陣列,讀入迷宮的資料:
int eRowIndex = row - 1;
int eColIndex = col - 1;

char[,] maze = new char[row, col];
for (int i = 0; i < row; i++)
{
char[] mazeTmp = Console.ReadLine().ToCharArray();
for (int j = 0; j < mazeTmp.Length; j++)
maze[i, j] = mazeTmp[j];
}
Console.WriteLine();
接下來是遞迴函式就是在模擬老鼠走法,每一步老鼠會做記號 ( 改為 '-' ) 並且判斷是否已經到了終點,如果未到終點,老鼠會嘗試上下左右是否有路,如果有路,接著往有路的方向呼叫函式;如果沒有路,就將此點記號取消 ( 改為 '.' ),如此一來,所有走到死路的走法都會回頭到岔路繼續往別的方向嘗試,最後,就會走到終點。
static void visit(int nRI, int nCI, int eRI, int eCI, char[,] maze)
{
maze[nRI, nCI] = '-';
if (nRI == eRI && nCI == eCI)
print(maze);

if (!(nRI - 1 < 0) && maze[nRI - 1,nCI] == '.') // 上
visit(nRI - 1, nCI, eRI, eCI, maze);
if (!(nCI - 1 < 0) && maze[nRI, nCI - 1] == '.') // 左
visit(nRI, nCI - 1, eRI, eCI, maze);
if (nRI + 1 <= eRI && maze[nRI + 1, nCI] == '.') // 下
visit(nRI + 1, nCI, eRI, eCI, maze);
if (nCI + 1 <= eCI && maze[nRI, nCI + 1] == '.') // 右
visit(nRI, nCI + 1, eRI, eCI, maze);

maze[nRI, nCI] = '.';
}

static void print(char[,] maze)
{
for (int i = 0; i < maze.GetLength(0); i++)
{
for (int j = 0; j < maze.GetLength(1); j++)
Console.Write(maze[i, j]);
Console.WriteLine();
}
Console.WriteLine();
}
最後,只要傳入起點位置與終點位置與迷宮陣列,即能將解法輸出:
visit(0, 0, eRowIndex, eColIndex, maze);

回首頁

2010年11月19日 星期五

XSS 跨站指令碼 ( Cross-Site Scripting )

XSS 為跨站指令碼,針對任何網站出現的安全性漏洞加以攻擊,小從惡作劇大到個人資料外洩,駭客 ( hacker ) 更可能取得管理者的權限,做出一些不可預期的事情。

一般論壇、留言板、...等,都有可能會產生這種情況。假設駭客 ( hacker ) 在某論壇上留了一篇文章並且有一段 script 碼導向到他的網頁,駭客的網頁是分析 cookie 內資訊並且紀錄。而網友甲在打上帳號和密碼登入某論壇,注意了,只要是保持登入狀態就會記錄 cookie。而網友甲瀏覽到駭客的文章並且點擊駭客的連結,此時網友甲的 cookie 會被帶到駭客的網頁,如此一來,網友甲的資料就會被竊取。

其實只要能讓駭客在文章上留下 script 碼,接下來就是等網友點擊,最後駭客所該做的就是分析 cookie 內的資訊,再來只能任他為所欲為了。

回首頁

2010年11月15日 星期一

Button Click 進行導向 ( Direct ) 頁面

篇教大家「如何按下按鈕後,查詢所輸入資料,並且導向到詳細資料頁面。」,查詢介面為 Default.aspx,而導向頁面為 Default2.aspx。






Default.aspx
<%@ Page Language="VB" AutoEventWireup="false" CodeFile="Default.aspx.vb" Inherits="_Default" %>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" >
<head runat="server">
<title>輸入姓名</title>
</head>
<body>
<form id="form1" runat="server">
<div>
<asp:TextBox ID="txtName" runat="server"></asp:TextBox>
<asp:Button ID="btnConfirm" runat="server" Text="確定" /><br/>
<font color="red"><asp:Label ID="lblMessage" runat="server" Text=""></asp:Label></font>
</div>
</form>
</body>
</html>
Default.aspx.vb
Imports System.Data.SqlClient

Partial Class _Default
Inherits System.Web.UI.Page

Protected Sub btnConfirm_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles btnConfirm.Click

Dim Name As String = txtName.Text

If String.IsNullOrEmpty(Name) <> True Then

Dim connString As String = ConfigurationManager.ConnectionStrings("dbMember").ConnectionString
Dim connection As New SqlConnection(connString)
Dim command As New SqlCommand("SELECT * FROM Member WHERE Name='" + Name + "'", connection)

connection.Open()
Dim reader As SqlDataReader = command.ExecuteReader()

If (reader.Read()) Then
Response.Redirect("Default2.aspx?ID=" + Convert.ToString(reader.GetInt32(0)))
Else
lblMessage.Text = "Not Find!"
End If
connection.Close()

End If

End Sub
End Class


而 Member 資料表內資料如下圖:
Default2.aspx
<%@ Page Language="VB" AutoEventWireup="false" CodeFile="Default2.aspx.vb" Inherits="Default2" %>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" >
<head runat="server">
<title>導向頁面</title>
</head>
<body>
<form id="form1" runat="server">
<div>
<asp:Label ID="lblID" runat="server" Text="-"></asp:Label> /
<asp:Label ID="lblName" runat="server" Text="-"></asp:Label>
</div>
</form>
</body>
</html>
Default2.aspx.vb
Imports System.Data.SqlClient

Partial Class Default2
Inherits System.Web.UI.Page

Protected Sub Page_Load(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.Load

Dim ID As String = Request.QueryString("ID")
If String.IsNullOrEmpty(ID) <> True Then

Dim connString As String = ConfigurationManager.ConnectionStrings("dbMember").ConnectionString
Dim connection As New SqlConnection(connString)
Dim command As New SqlCommand("SELECT * FROM Member WHERE MemberID=" + ID, connection)

connection.Open()
Dim reader As SqlDataReader = command.ExecuteReader()

If (reader.Read()) Then
lblID.Text = Convert.ToString(reader.GetInt32(0))
lblName.Text = Convert.ToString(reader.GetString(1))
End If
connection.Close()

End If
End Sub
End Class
執行後如下兩圖:

回目錄
回首頁

2010年11月14日 星期日

Regular Expression 與 C# Regex 教學

Regular Expression 稱為「正規表達式」,但我都稱它為「字串篩選條件」,Regular 有「正規」、「常態」之意,在此處為「規則」的意思。它為敘述一句符合某段句法規則之字串的字串,通常用來找尋與驗證或替換符合規則的字串,是個強大的字串匹配的類別。

Visual C# 中為 Regex 類別,在此就使用它為基礎做介紹。

Regex 建構函式有二:
  • Regex regex = new Regex(string pattern);
  • Regex regex = new Regex(string pattern, RegexOptions options);

以上 string pattern 為規則字串,RegexOptions options 為字串比對選項,是一個列舉型別,以下為它所有列舉值的成員與說明:
編號成員名稱說明
1Compiled指定規則運算式要編譯為組件,這將產生較快速的執行,但會增加啟動時間。
2CultureInvariant指定忽略語言中的文化差異。
3ECMAScript啟用運算式的 ECMAScript 相容行為,這個值只能結合 IgnoreCase、Multiline 和 Compiled 值使用,將這個值與任何其他值一起使用都將導致例外狀況。
4ExplicitCapture指定唯一有效的擷取為明確命名的或編號的,格式為 (?…) 的群組。這允許未命名的括號充當非擷取群組,而避免運算式 (?:…) 的語法不便。
5IgnoreCase指定區分大小寫的比對。
6IgnorePatternWhitespace從模式排除未逸出的泛空白字元 (White Space),並啟用以 # 標記的註解。不過,IgnorePatternWhitespace 值不會影響或排除字元類別中的泛空白字元。
7Multiline多行模式,變更 ^ 和 $ 的意義以致它們分別在任何一行的開頭和結尾做比對,而不只是整個字串的開頭和結尾。
8None指定無選項設定。
9RightToLeft指定搜尋將由右至左,而非由左至右。
10Singleline指定單行模式,變更點 (.) 的意義以至於它符合一切字元 (而不是 \n 之外的一切字元)。
以上表格轉自:http://msdn.microsoft.com/zh-tw/library/system.text.regularexpressions.regexoptions%28v=VS.80%29.aspx

通常我用 1、5、10 就夠了,其他的列舉成員我鮮少在用。
所以宣告時,要加入這些比對選項的列舉值,可以如以下宣告 ( pattern 為規則字串 ):
  • 單一比對列舉值宣告 - Regex regex = new Regex(pattern, RegexOptions.IgnoreCase);
  • 多個比對列舉值宣告 - Regex regex = new Regex(pattern, RegexOptions.IgnoreCase | RegexOptions.Compiled | RegexOptions.Singleline );

接下來就開始介紹 Regular Expression 的語法規則:
































編號字元描述
1\將下一個字元標記為一個特殊字元、或一個原義字元、或一個向後參照、或一個八進制轉義符。例如,「n」匹配字元「n」。「\n」匹配一個換行符。序列「\\」匹配「\」而「\(」則匹配「(」。
2^匹配輸入字串的開始位置。如果設定了RegExp物件的Multiline屬性,^也匹配「\n」或「\r」之後的位置。
3$匹配輸入字串的結束位置。如果設定了RegExp物件的Multiline屬性,$也匹配「\n」或「\r」之前的位置。
4*匹配前面的子運算式零次或多次。例如:Gooo*gle 能匹配 Google、Goooooogle。* 等於 {0,}。
5+匹配前面的子運算式一次或多次。例如:Gooo+gle 能匹配 Gooogle、Goooooogle,但不能匹配 Google。+ 等於 {1,}
6?匹配前面的子運算式零次或一次。例如:Gooo?gle 只能匹配 Gooogle 和 Google。? 等於 {0,1}
7{n}n是一個非負整數。匹配確定的n次。例如:o{3} 能匹配 Gooogle 的 ooo,但不能匹配 Google。
8{n,}n是一個非負整數。至少匹配n次。
9{n,m}m和n均為非負整數,其中n<=m。最少匹配n次且最多匹配m次
10?當該字元緊跟在任何一個其他限制符(*,+,?,{n},{n,},{n,m})後面時,匹配範式是非貪婪的。非貪婪範式儘可能少的匹配所搜尋的字串,而預設的貪婪範式則儘可能多的匹配所搜尋的字串。
11.匹配除「\n」之外的任何單個字元。要匹配包括「\n」在內的任何字元,請使用像「[.\n]」的範式。
12(pattern)匹配pattern並獲取這一匹配。( ... ) 有群組的意思。例如:(ab) 能匹配 abc 中的 ab,但不能匹配 acc。
13(?:pattern)匹配pattern但不獲取匹配結果,也就是說這是一個非獲取匹配,不進行儲存供以後使用。例如:run(?:n|ning) 能匹配 running 整個字串,並且從此字串後繼續比對。
13(?=pattern)正向預查,在任何匹配pattern的字串開始處匹配尋找字串。這是一個非獲取匹配,也就是說,該匹配不需要獲取供以後使用。例如:Office(?=2003|2007|2010) 能匹配 Office2003 中的 Office,但不能匹配 Office2005 中的 Office,而從 Office 字串後繼續比對。
14(?!pattern)負向預查,在任何不匹配pattern的字串開始處匹配尋找字串。這是一個非獲取匹配,也就是說,該匹配不需要獲取供以後使用。例如:Office(?!2003|2007|2010) 能匹配 Office2005 中的 Office,但不能匹配 Office2010 中的 Office,而從 Office 字串後繼續比對。
15x|y匹配x或y。
16[xyz]字符集合。匹配所包含的任意一個字元。
17[^xyz]負值字符集合。匹配未包含的任意字元。
18[a-z]字元範圍。匹配指定範圍內的任意字元。
19[^a-z]負值字元範圍。匹配任何不在指定範圍內的任意字元。
20\b匹配一個單詞邊界,也就是指單詞和空格間的位置。
21\B匹配非單詞邊界。
22\cx匹配由x指明的控制字元。例如,\cM匹配一個Control-M或Enter符。x的值必須為A-Z或a-z之一。否則,將c視為一個原義的「c」字元。
23\d匹配一個數位字元。\d 等於[0-9]。
24\D匹配一個非數位字元。\D 等於[^0-9]。
25\f匹配一個換頁符。\f 等於\x0c和\cL。
26\n匹配一個換行符。\n 等於\x0a和\cJ。
27\r匹配一個Enter符。\r 等於\x0d和\cM。
28\s匹配任何空白字元,包括空格、製表符、換頁符等等。\s 等於[\f\n\r\t\v]。
29\S匹配任何非空白字元。\S 等於[^\f\n\r\t\v]。
30\t匹配一個製表符。\t 等於\x09和\cI。
31\v匹配一個垂直製表符。\v 等於\x0b和\cK。
32\w匹配包括底線的任何單詞字元。\w 等於「[A-Za-z0-9_]」。
33\W匹配任何非單詞字元。\W 等於「[^A-Za-z0-9_]」。
34\xn匹配n,其中n為十六進制轉義值。十六進制轉義值必須為確定的兩個數位長。例如,「\x41」匹配「A」。「\x041」則等價於「\x04&1」。正則運算式中可以使用ASCII編碼。
35\num匹配num,其中num是一個正整數。對所獲取的匹配的參照。例如,「(.)\1」匹配兩個連續的相同字元。
36\n標識一個八進制轉義值或一個向後參照。如果\n之前至少n個獲取的子運算式,則n為向後參照。否則,如果n為八進制數位(0-7),則n為一個八進制轉義值。
37\nm標識一個八進制轉義值或一個向後參照。如果\nm之前至少有nm個獲得子運算式,則nm為向後參照。如果\nm之前至少有n個獲取,則n為一個後跟文字m的向後參照。如果前面的條件都不滿足,若n和m均為八進制數位(0-7),則\nm將匹配八進制轉義值nm。
38\nml如果n為八進制數位(0-3),且m和l均為八進制數位(0-7),則匹配八進制轉義值nml。
39\un匹配n,其中n是一個用四個十六進制數位表示的Unicode字元。例如,\u00A9匹配版權符號(©)。
以上表格轉自:http://zh.wikipedia.org/zh-tw/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F

小弟所寫的另一篇文章 Regular expression 常用驗證 中有常用的驗證規則字串,供大家參考。

以下為一 Regex 使用的方法:
string input = "The men's soft tennis team captured the first gold medal for Taiwan " + 
"yesterday in the 2010 Asian Games in Guangzhou, China, while their " + 
"female counterparts garnered a silver for Taiwan, which is competing " + 
"as Chinese Taipei at the regional sport games."; // 原始字串
string pattern = @"(?<word>\sc[\w]*)"; // 規則字串
Regex regex = new Regex(pattern, RegexOptions.IgnoreCase); // 宣告 Regex 忽略大小寫
MatchCollection matches = regex.Matches(input); // 將比對後集合傳給 MatchCollection
int index = 0;
foreach (Match match in matches) // 一一取出 MatchCollection 內容
{
// 將 Match 內所有值的集合傳給 GroupCollection groups
GroupCollection groups = match.Groups;
// 印出 Group 內 word 值
Console.WriteLine( ++ index + ": " + groups["word"].Value.Trim()); 
}
上面程式碼執行結果為下:
1: captured
2: China
3: counterparts
4: competing
5: Chinese

回目錄
回首頁

2010年11月11日 星期四

Google 關鍵字監控工具

近為了測試某網站針對指定關鍵字的排名,而關鍵字有 33000 多筆,馬上我就寫了一個工具去找尋 ( 利用小弟寫的一篇文章 模擬人為使用搜尋引擎 的概念 ) 所有指定關鍵字的排名。






不過執行不久便出現以下畫面:其實這對時常在網頁探勘的人已經見怪不怪了,除此之外,google 還會請你輸入驗證碼,證明「你是人,不是機器」。

哇銬,這都被它發現了,這樣我還玩個屁阿!

後來發現,每做一個網頁轉換的動作太快了,所以我每做一個網頁轉換的動作會停個兩秒,果然,目前做了兩個小時多都沒被擋下來,哈哈,又有得玩了。

而我 google 了一下,找到一個工具也是與我寫的工具做類似的事情,在此就稍微介紹一下那個工具。
Free Monitor for Google ,字面上的意思就是 免費 Google 監控,不過它就是如同我的工具所說,找出「某網站針對指定關鍵字的排名」。( 網址有提供下載點,可先下載並照以下步驟使用 )

  • 安裝步驟請照以下框紅線按鈕點擊。

  • 開啟工具若是第一次使用就會請你決定基本設定。Search Depth 即表示網站要搜尋到第幾排名為止。

  • 開啟工具後,可以找到新增網址的地方,如圖新增

  • 再來編輯關鍵字,如圖新增

  • 最後只需按下右上搜尋鈕,稍等一會兒,就會找出搜尋結果,列出網站在關鍵字下最好的排名。



回首頁

2010年11月10日 星期三

javascript 子視窗關閉,重新整理母視窗

於資料更新的關係,不得不利用子視窗來幫忙新增一筆資料,再將母視窗的資料更新。
母視窗為查詢介面,而由母視窗開啟子視窗後,子視窗新增一筆資料後關閉,隨即重新整理母視窗查詢資料。

其實程式碼也只有少少幾行,卻好像被我說的很複雜,這表示我說屁話的功力更上一層樓。

只適用於 GET 傳遞參數網頁。
只要在子視窗下加上一段 javascript:
<script type="text/javascript">
function unLoad()
{
window.opener.location.href = window.opener.location.href;
}
</script>
如果此時使用 window.opener.location.reload(),可能會跳出詢問視窗。
最後,在 body tag 加上 onunload="unLoad();",就可以在關閉子視窗後重新整理母視窗。

回目錄
回首頁

2010年11月9日 星期二

javascript 取得參數值

利用以下程式碼加入 header 區塊,再去呼叫 QueryString 函式,即可取得參數值。
<script type="text/javascript">
function QueryString(item){
var svalue = location.search.match(new RegExp("[\?\&]" + item + "=([^\&]*)(\&?)","i"));
return svalue ? svalue[1] : svalue;
}
</script>


回目錄
回首頁

ASP.NET 留言版 寄送Email (VB)

先,建好一個留言版的表格,按下送出Button,將填寫內容寄發Email送到管理者信箱,告知是誰來留言了。

建立四個TextBox,分別代表 暱稱, email, 主題, 內容,最後在加上一個Button為送出,如下圖所示:



程式碼如下:
Imports System.Net.Mail
Partial Class contacts
Inherits System.Web.UI.Page

Protected Sub Button1_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim strName As String = TextBox1.Text
Dim strEmail As String = TextBox2.Text
Dim strSub As String = TextBox3.Text
Dim strBody As String = TextBox4.Text

Dim eMail As New MailMessage()
Dim mSender As New MailAddress(strEmail, strName)'strEmail=email帳號本身, strName=在email帳號上顯示的文字

eMail.From = mSender'寄件者
eMail.To.Add("abc@aaa.com")'收件者
eMail.Subject = strSub'寄送email主旨
eMail.Body = strBody'寄送email內容
eMail.IsBodyHtml = True
Dim smtp As New System.Net.Mail.SmtpClient()
smtp.Host = "127.0.0.1"
smtp.Port = 25
smtp.DeliveryMethod = System.Net.Mail.SmtpDeliveryMethod.PickupDirectoryFromIis
smtp.Send(eMail)
End Sub


回目錄
回首頁

JQuery 讀取 ASP.NET 傳遞 Json 格式資料

JSON (JavaScript Object Notation) 為一傳遞資料的格式,ajax 傳遞資料皆使用 Json 格式,維基 (wiki) 上稱它為一種輕量級的資料交換語言,易於閱讀。與 xml 最大的不同就是,xml 有絕佳的延展性,Json 目的在於資料的交換。




若 xml 資料為以下結構:
<item>
<ID>1</ID>
<Name>DavidKuo</Name>
</item>
而Json 資料結構就為:
{
item:{
id:1,
name:'DavidKuo'
}
}
提供大家一個 xml 轉換 Json 的網址 http://www.thomasfrank.se/xml_to_json.html
此次要提供的就是「從資料表製作一個 Json 格式資料,使用 JQuery 函式 .getJSON() 讀取回傳資料並顯示在網頁上」。基於 google 搜尋引擎的幫助,很快就找到了參考網址,約略1 ~ 2小時漸有融會貫通的感覺,這表示我網頁爬文功力更上一層樓。
  • 首先,網頁只需留下<%@ Page Language="C#" AutoEventWireup="true" CodeFile="Default.aspx.cs" Inherits="_Default" %> 等字樣,其餘皆不要存在。

  • 下達 SQL 查詢指令將資料塞進 DataTable,並將 DataTable 轉換成 Json 字串。
    假設資料庫為有下圖資料:而程式碼中,ID 為參數,若無參數,則全部列出:
    using System;
    using System.Data;
    using System.Configuration;
    using System.Data.SqlClient;
    using System.Text;

    public partial class _Default : System.Web.UI.Page
    {
    protected void Page_Load(object sender, EventArgs e)
    {
    string connString = ConfigurationManager.ConnectionStrings["Member.Properties.Settings.ConnectionString"].ConnectionString;
    DataTable dt = new DataTable();

    if (!string.IsNullOrEmpty(Request.QueryString["id"]))
    {
    string id = Request.QueryString["id"];
    SqlDataAdapter adapter = new SqlDataAdapter(new SqlCommand("SELECT * FROM Member WHERE id=" + id, new SqlConnection(connString)));
    adapter.Fill(dt);
    }
    else
    {
    SqlDataAdapter adapter = new SqlDataAdapter(new SqlCommand("SELECT * FROM Member", new SqlConnection(connString)));
    adapter.Fill(dt);
    }

    Response.Write(DataTableToJsonString(dt));
    }

    public string DataTableToJsonString(DataTable dt)
    {
    StringBuilder JsonString = new StringBuilder();

    if (dt != null && dt.Rows.Count > 0)
    {
    JsonString.Append("{");
    JsonString.Append(@"""item"":[");

    for (int i = 0; i < dt.Rows.Count; i++)
    {
    JsonString.Append("{");
    for (int j = 0; j < dt.Columns.Count; j++)
    {
    JsonString.Append(string.Format(@"""{0}"":""{1}""", dt.Columns[j].ColumnName, Convert.ToString(dt.Rows[i][j])));
    if (j != dt.Columns.Count - 1) JsonString.Append(",");
    }
    JsonString.Append("}");
    if (i != dt.Rows.Count - 1) JsonString.Append(",");
    }
    JsonString.Append("]}");
    }
    return JsonString.ToString();
    }

    }
    網頁開啟後如同下圖:
  • 最後建立另依 *.apsx 頁面,匯入 jquery 的 js 檔,使用 .getJSON() 函式將資料一筆一筆讀出。程式碼如下:
    <%@ Page Language="C#" AutoEventWireup="true" CodeFile="Default2.aspx.cs" Inherits="Default2" %>

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

    <html xmlns="http://www.w3.org/1999/xhtml" >
    <head runat="server">
    <title>未命名頁面</title>
    <script type="text/javascript" src="jquery-1.4.3.min.js"></script>
    <script type="text/javascript" src="App_Data/jquery-1.2.6.pack.js"></script>
    <script type="text/javascript">
    $(document).ready(function() {
    $.getJSON("Default.aspx?id=1",
    function(data){
    $.each(data.item, function(i,item){
    $("#member").append(item.ID + ' / ' + item.Name + '<br />');

    });
    });
    });

    </script>
    </head>
    <body>
    <form id="form1" runat="server">
    <div id="member"></div>
    </form>
    </body>
    </html>
    最後執行後頁面圖:

參考網址:http://chrisbalboa.pixnet.net/blog/post/30161616
http://zh.wikipedia.org/zh/JSON

回目錄
回首頁

2010年11月4日 星期四

DataTable 轉換成 CSV 與 CSV 轉換成 DataTable

取資料庫內的資料,可能希望匯出成檔案方便記錄與查詢。以下就提供以 DataTable 轉成 CSV 檔,以及用 OleDb 套件讀取 CSV 轉成 DataTable。
DataTable 轉成 CSV 檔函式程式碼如下:
public void CreateCSVFile(DataTable dt, string strFilePath) // strFilePath 為輸出檔案路徑 (含檔名)
{
StreamWriter sw = new StreamWriter(strFilePath, false);

int intColCount = dt.Columns.Count;

if (dt.Columns.Count > 0)
sw.Write(dt.Columns[0]);
for (int i = 1; i < dt.Columns.Count; i++)
sw.Write("," + dt.Columns[i]);

sw.Write(sw.NewLine);
foreach (DataRow dr in dt.Rows)
{
if (dt.Columns.Count > 0 && !Convert.IsDBNull(dr[0]))
sw.Write(Encode(Convert.ToString(dr[0])));
for (int i = 1; i < intColCount; i++)
sw.Write("," + Encode(Convert.ToString(dr[i])));
sw.Write(sw.NewLine);
}
sw.Close();
}

public string Encode(string strEnc)
{
return System.Web.HttpUtility.UrlEncode(strEnc);
}
讀取 CSV 轉成 DataTable 函式程式碼如下:
public DataTable ReadCSVFile(string strFilePath, string strFileName) // strFilePath 為檔案所在資料夾,strFileName 為檔案名稱
{
OleDbConnection connection = new OleDbConnection(string.Format(@"Provider=Microsoft.Jet.OLEDB.4.0;Data Source={0}; Extended Properties=""text;HDR=Yes;FMT=Delimited"";", strFilePath));
OleDbCommand command = new OleDbCommand("SELECT * FROM " + strFileName, connection);
OleDbDataAdapter adapter = new OleDbDataAdapter(command);
DataTable dt = new DataTable();

adapter.Fill(dt);

return dt;
}


回目錄
回首頁

2010年10月30日 星期六

DataGridView 的連結顯示以及連結網址設定

近用到 windows form 內的 DataGridView 控制項,裡面有一欄位型態 DataGridViewLinkColumn,用來連結或處理資料之用,但是用的時候,設定欄位 Text 為「連結網址」,執行後,卻無字樣。例如以下所示:
程式碼:
private void Form1_Load(object sender, EventArgs e)
{
((DataGridViewLinkColumn)dataGridView1.Columns["gvRGoogleLink"]).Text = "連結網頁";
dataGridView1.Rows.Add("C語言", "");
dataGridView1.Rows.Add("程式設計筆記", "");
}
執行後截圖:上圖所示,在 Google Link 欄位並無連結字樣。但是加上
((DataGridViewLinkColumn)dataGridView1.Columns["gvRGoogleLink"]).UseColumnTextForLinkValue = true;
這行程式碼,即可將連結字樣顯示。
加入此行程式碼執行後截圖:連結字樣就會出現了,接下來就是設定連結的事件。
而連結事件所要利用到 CellClick 事件,當點擊某一欄位時,觸發 CellClick 事件,將此行 Keywoed 轉換編碼導向 Google 搜尋頁面。
程式碼如下:
private void dataGridView1_CellClick(object sender, DataGridViewCellEventArgs e)
{
/* 確認欄位型態 */
if (dataGridView1.Columns[e.ColumnIndex] is DataGridViewLinkColumn)
{
/* 確認欄位名稱 */
switch (dataGridView1.Columns[e.ColumnIndex].Name)
{
case "gvRGoogleLink": /* 觸發事件 */
string keyword = Convert.ToString(dataGridView1.Rows[e.RowIndex].Cells["gvRKeyword"].Value);
string encKeyword = encKeyword = System.Web.HttpUtility.UrlEncode(keyword);

string url = string.Format("http://www.google.com.tw/search?q={0}", encKeyword);
System.Diagnostics.Process.Start(url);
break;
}
}
}


回目錄
回首頁

2010年10月28日 星期四

利用 XElement 類別擷取 IP 所在之國家 ( Country )

引用網址:http://byteblocks.com/post/2009/06/01/Convert-IP-To-Location-and-Address-To-Location.aspx

首先,利用 WebClient 類別下載網頁原始碼那是必需的,但最重要的是要有網頁能提供 IP 查詢國家所在,所以找到了 http://ipinfodb.com/ip_query.php 這網頁,此網頁不吃參數時,預設會找出你電腦 IP 的相關資料( 包含電腦所在國家 ),但若吃 ip 參數時,就會列出此 ip 相關參數,例如:
http://ipinfodb.com/ip_query.php?ip=61.219.38.89
此 ip 為中華電信之 IP。

所以若要以 IP 找出相關資料,可利用以下程式擷取出來。
static void Main(string[] args)
{
string Ip = "61.219.38.89"; /* 中華電信 IP */
string Url = string.Format("http://ipinfodb.com/ip_query.php?ip={0}", Ip);
string Content = GetUrlContent(Url);

StringReader sr = new StringReader(Content);
XElement xe = XElement.Load(sr);
string strStatus = Convert.ToString(xe.Element("Status").Value);

if (string.Compare(strStatus, "OK", true) == 0)
{
Console.WriteLine(Convert.ToString(xe.Element("CountryName").Value));
}
}

static string GetUrlContent(string Url)
{
string content = string.Empty;
WebClient client = new WebClient();
try
{
content = client.DownloadString(Url);
}
catch (WebException we)
{
content = we.Message;
}
return content;
}
最後,只要依據 IP 的不同,就能擷取出 IP 的相關資料。

回目錄
回首頁

2010年10月12日 星期二

Repeater 取得 Header 區控制項

Repeater 控制項中,不像 RadGrid 有 .MasterTableView.GetItems 方法可以使用,此時就需要將 Repeater 內的所有控制項全部掃過一次,在找出屬於 Header 區的控制項。

例如要找出位於 Header 區中 ID 為 control_1 的 Label 控制項,將它的屬性 Text 改為字串 HaHa。
以下為 *.aspx 內範例程式碼:
<asp:Repeater ID="Repeater1" runat="server">
<HeaderTemplate>
<asp:Label ID="control_1" runat="server"></asp:Label>
</HeaderTemplate>
</asp:Repeater>

接著要在 *.cs 內 寫入以下程式:
foreach (Control c in Repeater1.Controls)
{
RepeaterItem item = (RepeaterItem)c;
if (item.ItemType == ListItemType.Header)
{
Label headerItem = (Label)item.FindControl("control_1");
headerItem.Text = "HaHa";

}
}


回目錄
回首頁

2010年10月8日 星期五

兩段時間 ( DateTime ) 的時間差

在做日期相減時,可以使用 DateTime 設定兩段欲相減的時間,再使用 TimeSpan 算出兩段時間的間隔,總共是多少天數( Day )、多少小時( Hour )、多少毫秒( TotalMillisecond )、多少分鐘( Minute )抑或是多少秒( Second )。

以下例子就是以現在的時間,距離 2010 年 1 月 1 日 0 時 0 分 0 秒的時間差。
DateTime dt = DateTime.Now;
DateTime _dt = new DateTime(2010, 1, 1, 0, 0, 0);
TimeSpan ts = dt.Subtract(_dt);
Console.WriteLine(ts.TotalDays + " Days.");
Console.WriteLine(ts.TotalHours + " Hours.");
Console.WriteLine(ts.TotalMilliseconds + " Milliseconds");
Console.WriteLine(ts.TotalMinutes + " Minutes");
Console.WriteLine(ts.TotalSeconds + " Seconds");


回目錄
回首頁

2010年10月7日 星期四

RSS Reader

可以在 http://www.geekpedia.com/tutorial147_Creating-an-RSS-feed-reader-in-Csharp.html 下載到 vs 2005 winForm 寫的 RSS 讀取器,但只能讀取特定格式的 RSS。

以下為此檔案的程式碼內容,核心部份會用紅色標起來。
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.IO;
using System.Xml;

namespace RSS_Reader
{
public partial class frmMain : Form
{
XmlTextReader rssReader;
XmlDocument rssDoc;
XmlNode nodeRss;
XmlNode nodeChannel;
XmlNode nodeItem;
ListViewItem rowNews;

public frmMain()
{
InitializeComponent();
}

private void btnRead_Click(object sender, EventArgs e)
{
lstNews.Items.Clear();
this.Cursor = Cursors.WaitCursor;
// Create a new XmlTextReader from the specified URL (RSS feed)
rssReader = new XmlTextReader(txtUrl.Text);
rssDoc = new XmlDocument();
// Load the XML content into a XmlDocument
rssDoc.Load(rssReader);

// Loop for the <rss> tag
for (int i = 0; i < rssDoc.ChildNodes.Count; i++)
{
// If it is the rss tag
if (rssDoc.ChildNodes[i].Name == "rss")
{
// <rss> tag found
nodeRss = rssDoc.ChildNodes[i];
}
}

// Loop for the <channel> tag
for (int i = 0; i < nodeRss.ChildNodes.Count; i++)
{
// If it is the channel tag
if (nodeRss.ChildNodes[i].Name == "channel")
{
// <channel> tag found
nodeChannel = nodeRss.ChildNodes[i];
}
}


// Set the labels with information from inside the nodes
lblTitle.Text = "Title: " + nodeChannel["title"].InnerText;
lblLanguage.Text = "Language: " + nodeChannel["language"].InnerText;
lblLink.Text = "Link: " + nodeChannel["link"].InnerText;
lblDescription.Text = "Description: " + nodeChannel["description"].InnerText;

// Loop for the <title>, <link>, <description> and all the other tags
for (int i = 0; i < nodeChannel.ChildNodes.Count; i++)
{
// If it is the item tag, then it has children tags which we will add as items to the ListView
if (nodeChannel.ChildNodes[i].Name == "item")
{
nodeItem = nodeChannel.ChildNodes[i];


// Create a new row in the ListView containing information from inside the nodes
rowNews = new ListViewItem();
rowNews.Text = nodeItem["title"].InnerText;
rowNews.SubItems.Add(nodeItem["link"].InnerText);
lstNews.Items.Add(rowNews);
}
}


this.Cursor = Cursors.Default;
}

private void lstNews_SelectedIndexChanged(object sender, EventArgs e)
{
// When an items is selected
if (lstNews.SelectedItems.Count == 1)
{
// Loop through all the nodes under <channel>
for (int i = 0; i < nodeChannel.ChildNodes.Count; i++)
{
// Until you find the lt;itemgt; node
if (nodeChannel.ChildNodes[i].Name == "item")
{
// Store the item as a node
nodeItem = nodeChannel.ChildNodes[i];
// If the <title> tag matches the current selected item
if (nodeItem["title"].InnerText == lstNews.SelectedItems[0].Text)
{
// It's the item we were looking for, get the description
txtContent.Text = nodeItem["description"].InnerText;
// We don't need to loop anymore
break;
}
}
}
}
}

private void lstNews_DoubleClick(object sender, EventArgs e)
{
// When double clicked open the web page
System.Diagnostics.Process.Start(lstNews.SelectedItems[0].SubItems[1].Text);
}
}
}


回目錄
回首頁

2010年10月6日 星期三

Ini 檔案的讀取與寫入類別

Ini 檔案又稱設定檔,無固定格式,僅以簡單的結構與文字組成,許多程式都會將它當作初始化之檔案。
此篇文章提供程式碼中,可以將 key 和 value 寫到同一個 section,或者將某一個 section 指定 key 的 value 讀出,又或者可以將某個 section 讀出,而我參考 http://www.codeproject.com/KB/cs/cs_ini.aspx 後,寫成以下類別,方便大家引用。
using System;
using System.Runtime.InteropServices;
using System.Text;
using System.IO;

namespace Ini
{
public class IniFile
{
public string path;

[DllImport("kernel32")]
private static extern long WritePrivateProfileString(string section,
string key, string val, string filePath);
[DllImport("kernel32")]
private static extern int GetPrivateProfileString(string section,
string key, string def, StringBuilder retVal,
int size, string filePath);
[DllImport("kernel32")]
private static extern int GetPrivateProfileSection(string section, IntPtr lpReturnedString,
int nSize, string lpFileName);

// INIPath 為檔案路徑,isDel 為是否覆蓋原檔
public IniFile(string INIPath, bool isDel)
{
if (!isDel)
{
if (!File.Exists(INIPath))
File.Create(INIPath);
}
else
{
FileStream fs = new FileStream(INIPath, FileMode.Create);
fs.Close();
}
this.path = INIPath;
}

// 寫入指定 Section,指定 Key,指定 Value。
public void IniWriteValue(string Section, string Key, string Value)
{
WritePrivateProfileString(Section, Key, Value, this.path);
}

// 讀取指定 Section,指定 Key 的 Value。
public string IniReadValue(string Section, string Key)
{
StringBuilder temp = new StringBuilder(255);
int i = GetPrivateProfileString(Section, Key, "", temp,
255, this.path);
return temp.ToString();

}

// 讀取指定 Section 所有的 Value。
public string[] ReadSection(string section)
{
const int bufferSize = 2048;

StringBuilder returnedString = new StringBuilder();

IntPtr pReturnedString = Marshal.AllocCoTaskMem(bufferSize);
try
{
int bytesReturned = GetPrivateProfileSection(section, pReturnedString, bufferSize, path);

//bytesReturned -1 to remove trailing \0
for (int i = 0; i < bytesReturned - 1; i++)
returnedString.Append((char)Marshal.ReadByte(new IntPtr((uint)pReturnedString + (uint)i)));
}
finally
{
Marshal.FreeCoTaskMem(pReturnedString);
}

string sectionData = returnedString.ToString();
return sectionData.Split('\0');
}
}
}


回目錄
回首頁

利用 gmail 寄信

以下程式碼可以使 DavidKuo's Mail 寄信給 A's Mail,信件標題為 subject,內文為 body。

要匯入 System.Net 和 System.Net.Mail 兩套件。
string fromEmail = "DavidKuo'sMail@gmail.com"; // 寄信人
string fromName = "DavidKuo"; // 寄信人姓名

MailAddress from = new MailAddress(fromEmail, fromName, Encoding.UTF8);

string toEmail = "A'sMail@gmail.com"; // 收信人

MailMessage mail = new MailMessage(from, new MailAddress(toEmail));

string subject = "subject";
mail.Subject = subject;
mail.SubjectEncoding = Encoding.UTF8;

string body = "body";
mail.Body = body;
mail.BodyEncoding = Encoding.UTF8;
mail.IsBodyHtml = false; // 是否為 Html 格式
mail.Priority = MailPriority.High; // 信件優先權

SmtpClient client = new SmtpClient();
client.Host = "smtp.gmail.com";
client.Port = 587;
client.Credentials = new NetworkCredential("DavidKuo'sMail@gmail.com", "DavidKuo'sMailPassword");
client.EnableSsl = true;
client.DeliveryMethod = SmtpDeliveryMethod.Network;

client.Send(mail); // 寄信


參考網址:http://www.dotblogs.com.tw/chhuang/archive/2008/03/18/1815.aspx

回目錄
回首頁

2010年10月5日 星期二

清空資料 ClearTextBox()

在按下送出鍵後, 需要清空TextBox內容,
(1)方法, 要一個一個對欄位增加。
(2)方法, 是只要下ClearTexBox(), 就可以清空所有欄位的內容。

(1)
TextBox1.Text = ""
(2)

Private Sub ClearTextBox()
For Each control As System.Web.UI.Control In Me.Controls
For i As Integer = 0 To control.Controls.Count - 1
If TypeOf control.Controls(i) Is System.Web.UI.WebControls.TextBox Then
Dim tbx As System.Web.UI.WebControls.TextBox = DirectCast(control.Controls(i), System.Web.UI.WebControls.TextBox)
tbx.Text = ""
End If
Next
Next
End Sub

回目錄
回首頁

2010年10月3日 星期日

使用 FolderBrowserDialog 決定資料夾路徑

上次取得檔案路徑,此篇文章將提供取得資料夾路徑之程式碼,

FolderBrowserDialog fbd = new FolderBrowserDialog();
fbd.Description = "Please select one folder";

fbd.ShowNewFolderButton = false;
// fbd.RootFolder = Environment.SpecialFolder.MyDocuments;

if (fbd.ShowDialog() == DialogResult.Cancel)
return;
textBox1.Text = fbd.SelectedPath;


以上程式碼之中,並沒有明訂根目錄位置,如果未定義,桌面即為根目錄。
還有以下幾種設定:
  1. Environment.SpecialFolder.ApplicationData
    表示做為目前漫遊使用者的應用程式特定資料之通用儲存機制的目錄。
  2. Environment.SpecialFolder.CommonApplicationData
    表示做為所有使用者使用的應用程式特定資料之通用儲存機制的目錄。
  3. Environment.SpecialFolder.LocalApplicationData
    表示做為目前非漫遊使用者使用的應用程式特定資料之通用儲存機制的目錄。
  4. Environment.SpecialFolder.Cookies
    表示做為網際網路 Cookie 通用儲存機制的目錄。
  5. Environment.SpecialFolder.Desktop
    邏輯的 [桌面],而不是實體的檔案系統位置。
  6. Environment.SpecialFolder.Favorites
    表示做為使用者的我的最愛項目之通用儲存機制的目錄。
  7. Environment.SpecialFolder.History
    表示做為網際網路記錄項目通用儲存機制的目錄。
  8. Environment.SpecialFolder.InternetCache
    表示做為網際網路暫存檔通用儲存機制的目錄。
  9. Environment.SpecialFolder.Programs
    包含使用者程式群組的目錄。
  10. Environment.SpecialFolder.MyComputer
    [我的電腦] 資料夾。
  11. Environment.SpecialFolder.MyMusic
    [我的音樂] 資料夾。
  12. Environment.SpecialFolder.MyPictures
    [我的圖片] 資料夾。
  13. Environment.SpecialFolder.Recent
    包含使用者最近使用之文件的目錄。
  14. Environment.SpecialFolder.SendTo
    包含 [傳送到] 功能表項目的目錄。
  15. Environment.SpecialFolder.StartMenu
    包含 [開始] 功能表項目的目錄。
  16. Environment.SpecialFolder.Startup
    對應至使用者 [啟動] 程式群組的目錄。
  17. Environment.SpecialFolder.System
    System 目錄。
  18. Environment.SpecialFolder.Templates
    表示做為文件樣板 (Template) 通用儲存機制的目錄。
  19. Environment.SpecialFolder.DesktopDirectory
    表示用來實際儲存桌面上檔案物件的目錄。
  20. Environment.SpecialFolder.Personal
    表示做為文件通用儲存機制的目錄。
  21. Environment.SpecialFolder.MyDocuments
    [我的文件] 資料夾。
  22. Environment.SpecialFolder.ProgramFiles
    Program Files 目錄。
  23. Environment.SpecialFolder.CommonProgramFiles
    表示在應用程式間共享的元件的目錄。


參考網址:Environment.SpecialFolder 列舉型別

回目錄
回首頁

2010年10月1日 星期五

DateTime 取得常用時間

引用網址:http://www.cnblogs.com/sekihin/archive/2008/03/27/1124446.html
以上引用網址為 VB 語法,以下提供 C# 語法。
DateTime Now = DateTime.Now; // 當前時間。
DateTime StartWeek =
Now.AddDays(1 - Convert.ToInt32(Now.DayOfWeek.ToString("d"))); // 禮拜一日期
DateTime EndWeek = StartWeek.AddDays(6); // 禮拜日日期
DateTime StartMonth = Now.AddDays(1 - Now.Day); // 月初
DateTime EndMonth = StartMonth.AddMonths(1).AddDays(-1); // 月末

DateTime StartQuarter = Now.AddMonths(0 - (Now.Month - 1) % 3).AddDays(1 - Now.Day); // 本季初
DateTime EndQuarter = StartQuarter.AddMonths(3).AddDays(-1); // 本季末
DateTime StartYear = new DateTime(Now.Year, 1, 1); // 年初
DateTime EndYear = new DateTime(Now.Year, 12, 31); // 年末


回目錄
回首頁

2010年9月26日 星期日

ACM 442 - Matrix Chain Multiplication

#include <stdio.h>
#include <ctype.h>

struct matrix
{
char ch;
int row;
int col;
int count;
};
struct matrix m[26], stack[200];

int main()
{
int n, row, col, i;
char ch, str[200];
scanf("%d", &n);
getchar();
for (i = 0; i < n; i ++)
{
scanf("%c %d %d", &ch, &row, &col);
getchar();
int index = ch - 'A';
m[index].ch = ch, m[index].row = row, m[index].col = col;
}
while (gets(str))
{
int count = 0, error = 0, index = 0;
int row = 0, col = 0;
for (i = 0; (ch = str[i]); i ++)
{
if (ch == '(') stack[index ++].ch = ch;
if (isupper(ch))
{
int s = ch - 'A';
row = m[s].row, col = m[s].col;
if (isupper(stack[index - 1].ch))
{
if (stack[index - 1].col != row)
{ error = 1; break; }
stack[index - 1].count += stack[index - 1].row * row * col;
stack[index - 1].col = col;
}
else
{
stack[index].ch = ch;
stack[index].row = row;
stack[index].col = col;
stack[index].count = 0;
index ++;
}
}
if (ch == ')')
{
if (index - 1 < 0) { error = 1; break; }
if (stack[index - 1].ch == '(') index --;
if (index - 2 >= 0 &&
isupper(stack[index - 1].ch) && stack[index - 2].ch == '(')
{
stack[index - 2].ch = stack[index - 1].ch;
stack[index - 2].row = stack[index - 1].row;
stack[index - 2].col = stack[index - 1].col;
stack[index - 2].count = stack[index - 1].count;
index --;
if (isupper(stack[index - 2].ch))
{
row = stack[index - 1].row;
col = stack[index - 1].col;
count = stack[index - 1].count;

if (stack[index - 2].col != row)
{ error = 1; break; }
stack[index - 2].count += (count + stack[index - 2].row * row * col);
stack[index - 2].col = col;
index --;
}
}
}

}

if (error == 0) printf("%d\n", stack[0].count);
else if (error) printf("error\n");

}
return 0;
}

回目錄
回首頁

ACM 424 - Integer Inquiry

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

#define NUMLEN 200

struct AddNum
{
int num[NUMLEN];
int length;
};

struct AddNum AN1, AN2;
char numStr[101];

int main()
{
int i, j;
while (gets(numStr))
{
if (numStr[0] == '0') break;
AN2.length = strlen(numStr) - 1;
for (i = AN2.length, j = 0; i >= 0; i --, j ++)
AN2.num[j] = numStr[i] - '0';
for (i = 0; i < NUMLEN; i ++)
{
AN1.num[i] += AN2.num[i];
if (AN1.num[i] >= 10)
AN1.num[i + 1] ++, AN1.num[i] %= 10;
}
}
for (i = NUMLEN - 1; ; i --)
if (AN1.num[i] > 0)
break;
for (; i >= 0; i --)
printf("%d", AN1.num[i]);
printf("\n");
return 0;
}

回目錄
回首頁

ACM 375 - Inscribed Circles and Isosceles Triangles

#include <stdio.h>
#include <math.h>
double B, H, SL, S, area, r, HSub2R, cycleLen;

int main()
{
double PI = 2*acos(0.0);
int n, i;
scanf("%d", &n);
for (i = 0; i < n; i ++)
{
cycleLen = 1e-12;
scanf("%lf %lf", &B, &H);
B += 1e-15; H += 1e-15;
SL = (double)sqrt( (H*H) + (B*B/4) );
area = B * H / 2;
r = 2 * area / (SL+SL+B);
while (r >= 0.000001)
{
cycleLen += 2 * r * PI;
HSub2R = H - 2 * r;
r *= HSub2R / H;
H = HSub2R;
}
if (i != 0) printf("\n");
printf("%13.6lf\n", cycleLen);
}
return 0;
}

回目錄
回首頁

ACM 374 - Big Mod

#include <stdio.h>
int f(int m,int n, int mod)
{
long long int mul = m;
long long int r = 1;
while(n){
if(n % 2 == 1){r *= mul;r %= mod;}
mul *= mul;
mul %= mod;
n >>= 1;
}
return r;
}
int main()
{
int B,P,M;
while(scanf("%d%d%d",&B,&P,&M)==3)
printf("%d\n",f(B,P,M));
return 0;
}

回目錄
回首頁

ACM 344 - Roman Digititis

#include <stdio.h>

struct RomanNum
{
int i;
int v;
int x;
int l;
int c;
};

struct RomanNum RN[101];

void adder(int index, int n)
{
if (n == 0) return;
if (n >= 40 && n <= 49)
RN[index].l ++, RN[index].x ++, n -= 40;
if (n >= 90 && n <= 99)
RN[index].c ++, RN[index].x ++, n -= 90;
if (n % 10 == 4)
RN[index].v ++, RN[index].i ++, n -= 4;
if (n % 10 == 9)
RN[index].x ++, RN[index].i ++, n -= 9;
if (n / 100 > 0)
RN[index].c += (n/100), n %= 100;
if (n / 50 > 0)
RN[index].l += (n/50), n %= 50;
if (n / 10 > 0)
RN[index].x += (n/10), n %= 10;
if (n / 5 > 0)
RN[index].v += (n/5), n %= 5;
if (n / 1 > 0)
RN[index].i += (n/1), n %= 1;
}

int main()
{
int i, n;
for (i = 0; i < 100; i ++)
{
adder(i, i + 1);
RN[i + 1].i = RN[i].i, RN[i + 1].v = RN[i].v, RN[i + 1].x = RN[i].x;
RN[i + 1].l = RN[i].l, RN[i + 1].c = RN[i].c;
}

while (1)
{
scanf("%d", &n);
if (n == 0) break;
n -= 1;
printf("%d: %d i, %d v, %d x, %d l, %d c\n", n+1, RN[n].i, RN[n].v, RN[n].x, RN[n].l, RN[n].c);
}
return 0;
}

回目錄
回首頁

2010年9月23日 星期四

DateTable 的 Top n 取得

常都是寫一段 SQL 語法後執行才能將所查詢的資料的 Top N 取出,可是如果還想再用這些原始資料做別的事情,就要用另外一種方法取出。用以下 C# 程式碼,能將 DataTable 的 Top N 取出。
DataTable DataTableTopN(DataTable dt, int rowCount)
{
DataTable dtn = dt.Clone();
for (int i = 0; i < rowCount; i++)
{
dtn.ImportRow(dt.Rows[i]);
}
return dtn;
}


回目錄
回首頁

2010年9月19日 星期日

ACM 340 - Master-Mind Hints

#include <stdio.h>

struct Ans
{
int ansInt;
int isComp;
};

int main()
{
int n, i, m, isZero, A, B, j, index = 0;
while (scanf("%d", &n) == 1)
{
if (n == 0) break;
printf("Game %d:\n", ++ index);
struct Ans a[n];
for (i = 0; i < n; i ++)
{
scanf("%d", &m);
a[i].ansInt = m;
a[i].isComp = 0;
}
struct Ans b[n];
while (1)
{
isZero = 1, A = 0, B = 0;
for (i = 0; i < n; i ++)
{
scanf("%d", &m);
if (m != 0) isZero = 0;
b[i].ansInt = m;
b[i].isComp = 0;
a[i].isComp = 0;
}
for (i = 0; i < n; i ++)
if (a[i].ansInt == b[i].ansInt)
A ++, a[i].isComp = 1, b[i].isComp = 1;
for (i = 0; i < n; i ++)
for (j = 0; j < n; j ++)
{
if (i != j && a[i].isComp == 0 && b[j].isComp == 0 && a[i].ansInt == b[j].ansInt)
B ++, a[i].isComp = 1, b[j].isComp = 1;
}
if (isZero) break;
else printf(" (%d,%d)\n", A, B);
}

}
return 0;
}

回目錄
回首頁

ACM 350 - Pseudo-Random Numbers

#include <stdio.h>

int PseRand(int Z, int I, int M, int L)
{
return (Z * L + I) % M;
}

int main()
{
int Z, I, M, L, caseNum = 1;

while (1)
{
scanf("%d %d %d %d", &Z, &I, &M, &L);
if (Z == 0 && I == 0 && M == 0 && L == 0) break;
int isTrue[10000] = {0}, len[10000] ;
printf("Case %d: ", caseNum++);
int count = 0;
while (!isTrue[L])
{
isTrue[L] = 1, len[L] = count ++;
L = PseRand(Z, I, M, L);
}
printf("%d\n", count - len[L]);
}

return 0;
}

回目錄
回首頁

ACM 299 - Train Swapping

#include <stdio.h>
#include <malloc.h>
int *S, size;

int bubbleSort ()
{
int i, j, tmp, count = 0;
for (i = 0; i < size; i ++)
{
for (j = 0; j < size - i - 1; j ++)
{
if (S[j] > S[j + 1])
{
tmp = S[j];
S[j] = S[j + 1];
S[j + 1] = tmp;
count ++;
}
}
}
return count;
}

int main()
{
/*freopen("111.txt", "r", stdin);
freopen("111w.txt", "w", stdout);*/
int n, i, j;
scanf("%d", &n);
for (i = 0; i < n; i ++)
{
scanf("%d", &size);

S = (int *)malloc(sizeof(int)*size);
for (j = 0; j < size; j ++)
scanf("%d", &S[j]);
printf("Optimal train swapping takes %d swaps.\n", bubbleSort());
free(S);
}
}

回目錄
回首頁

2010年9月18日 星期六

ACM 333 - Recognizing Good ISBNs

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main()
{
char str[82];
int i, numCount, s, e;
while (gets(str))
{
if (strlen(str) == 0) { printf(" is incorrect.\n"); continue; }
numCount = 0;
int per = 0;
int tsum = 0;
int sum[9] = {0}, wrong = 0, d = 0, isX = 0, g = 0;
for (s = 0; str[s] == ' ' || str[s] == '\t' || isalpha(str[s]) ; s ++)
if (str[s] == 'X') break;
for (e = strlen(str) - 1; str[e] == ' ' || str[e] == '\t' || isalpha(str[e]); e --)
if (str[e] == 'X') break;
for (i = s; i <= e; i ++)
{
if (str[i] == '-') continue;
else if (isdigit(str[i]))
{
numCount ++;
per += str[i] - '0';
tsum += per;
}
else if (str[i] == 'X')
{
if (numCount != 9) { wrong = 1; break;}
else
{
per += 10;
tsum += per;
numCount ++;
}
}
else { wrong = 1; break;}
}
for (i = 0; str[i] == ' ' || str[i] == '\t'; i ++) ;
s = i;
for (i = strlen(str) - 1; str[i] == ' ' || str[i] == '\t'; i --) ;
e = i;
for (i = s; i <= e; i ++)
putchar(str[i]);
if (wrong) printf(" is incorrect.\n");
else if (numCount >= 10 && tsum % 11 == 0) printf(" is correct.\n");
else printf(" is incorrect.\n");

}
return 0;
}

回目錄
回首頁

ACM 332 - Rational Numbers from Repeating Fractions

#include <stdio.h>
#include <string.h>

int gcd(int a,int b)
{
if (a % b == 0){ return b;}
return gcd(b , a % b);
}

int pow10(int n)
{
int i, sum = 1;
for (i = 0; i < n; i ++)
sum *= 10;
return sum;
}

char str[20];

int main()
{
int j, i, k, h, g, d, s, caseNum = 1;
while(scanf("%d", &j) == 1 && j != -1)
{
scanf("%s", str);
char ch;
int len = strlen(str);
if (j != 0) d = pow10(len - 2) - pow10(len - 2 - j);
else d = pow10(len - 2);
k = 0, h = 0;
for (i = 2, g = 0; i < len; i ++, g ++)
{
ch = str[i];
if (g < (len - 2 - j)) h = h * 10 + (ch - '0');
k = k * 10 + (ch - '0');
}
if (j != 0)
{
s = gcd(k - h, d);
printf("Case %d: %d/%d\n", caseNum ++, (k - h) / s, d / s);
}
else
{
s = gcd(k, d);
printf("Case %d: %d/%d\n", caseNum ++, k / s, d / s);
}


}

return 0;
}

回目錄
回首頁

ACM 326 - Extrapolation Using a Difference Table

#include <stdio.h>

int a[50];

int main() {
int n, i, j, k;
scanf("%d", &n);
while (n)
{
for (i=0; i<n; i++)
scanf("%d", &a[i]);
scanf("%d", &k);
for (j=n-1; j>0; j--)
for (i=0; i<j; i++)
a[i] = a[i+1] - a[i];
for (i=0; i<k; i++)
for (j=1; j<n; j++)
a[j] += a[j-1];
printf("Term %d of the sequence is %d\n", n+k, a[n-1]);
scanf("%d", &n);
}
return 0;
}

回目錄
回首頁

ACM 311 - Packets

#include <stdio.h>

int residual[6], packets[6];

int main()
{
while (1)
{
int i, isZero = 1, total = 0;
for (i = 0; i < 6; i ++)
{
scanf("%d", &packets[i]);
residual[i] = 0;
if (packets[i] != 0)
isZero = 0;
}
if (isZero) break;
total += packets[5]; /* 6*6一人一個盒子 */
total += packets[4]; /* 5*5一人一個盒子,剩餘 11 個 1*1 空間 */
residual[0] += packets[4] * 11;
total += packets[3]; /* 4*4一人一個盒子,剩餘 5 個 2*2 空間 */
residual[1] += packets[3] * 5;

total += packets[2] / 4; /* 3*3 之處理方式 */
packets[2] %= 4, residual[2] = packets[2];
if (residual[2] == 1)
residual[2] = 0, residual[0] += 7, residual[1] += 5, total ++;
else if (residual[2] == 2)
residual[2] = 0, residual[0] += 6, residual[1] += 3, total ++;
else if (residual[2] == 3)
residual[2] = 0, residual[0] += 5, residual[1] += 1, total ++;

if (residual[1] >= packets[1]) /* 2*2 之處理方式 */
residual[1] -= packets[1], packets[1] = 0;
else
packets[1] -= residual[1], residual[1] = 0;
total += packets[1] / 9;
packets[1] %= 9;
if (packets[1] > 0)
residual[0] += 36 - packets[1] * 4, packets[1] = 0, total ++;
else residual[0] += residual[1] * 4, residual[1] = 0;

if (residual[0] >= packets[0]) /* 1*1 之處理方式 */
residual[0] -= packets[0], packets[0] = 0;
else
packets[0] -= residual[0], residual[0] = 0;
total += packets[0] / 36;
packets[0] %= 36;
if (packets[0] > 0)
total ++;
printf("%d\n", total);
}
return 0;
}

回目錄
回首頁

ACM 300 - Maya Calendar

#include <stdio.h>
#include <string.h>

char hMonthStr[19][8] = {"pop", "no", "zip", "zotz",
"tzec", "xul", "yoxkin", "mol",
"chen", "yax", "zac", "ceh",
"mac", "kankin", "muan", "pax",
"koyab", "cumhu", "uayet"};
char tMonthStr[20][10] = {"imix", "ik", "akbal", "kan",
"chicchan", "cimi", "manik", "lamat",
"muluk", "ok", "chuen", "eb",
"ben", "ix", "mem", "cib",
"caban", "eznab", "canac", "ahau"};
char dStr[6], mStr[8];
int main()
{
int hDay, hMonth, hYear, tDay, tMonth, tYear;
int n, days, i;
scanf("%d", &n);
printf("%d\n", n);
while (n --)
{
char *d;
scanf("%s %s %d", dStr, mStr, &hYear);
d = strtok(dStr, ".");
sscanf(d, "%d", &hDay);
for (i = 0; i < 19; i ++)
{
if (strcmp(hMonthStr[i], mStr) == 0)
{ hMonth = i; break; }
}
days = hDay + hMonth * 20 + hYear * 365;
tYear = days / 260;
days %= 260;
tMonth = days % 20;
tDay = days % 13 + 1;

printf("%d %s %d\n", tDay, tMonthStr[tMonth], tYear);
}
return 0;
}

回目錄
回首頁

ACM 272 - TEX Quotes

#include <stdio.h>

int main()
{
int style = 0;
char c;
while (1){
c = getchar();
if (c == EOF) break;
if (c == '\"')
{
if (style == 0)
{
printf("``");
style = 1;
}
else
{
printf("''");
style = 0;
}
}
else putchar(c);
}
return 0;
}

回目錄
回首頁

ACM 264 - Count on Cantor

#include<stdio.h>    
#include<stdlib.h>
#include<string.h>
#include<math.h>
main()
{
int n,a,b,c,d;
while(scanf("%d",&n)==1)
{
for(d=1,c=n;c>d;d++) c=c-d;
if ( d%2==1 ) a=d-c+1;
else a=c;
b=d+1-a;
printf("TERM %d IS %d/%d\n",n,a,b);
}
return 0;
}
以上程式轉自:http://mypaper.pchome.com.tw/iustlovefish/post/1311842753
稍微說明一下程式碼,先看以下圖形:標紅色部分,依照每斜行遞增,所以 d=1, c=n 初始化後,用一迴圈每做一次 c 減掉 d 而做完後 d 累加一,所以這一部份是做算出 n 是在第 d 斜行的第 c 個位置。
而這個圖表有一個特性,請看以下表:
x - 1 / y - 1x - 1 / yx - 1 / y + 1
x / y - 1x / yx / y + 1
x + 1 / y - 1x + 1 / yx + 1 / y + 1
只要 d 在奇數它是往左下走,偶數則往右上走,而只要 d 在奇數則該斜行的第一個位置為 1 / d,偶數為 d / 1,最後再依照它的位置算出正確答案。

此提與 ACM 10182 Bee Maja 頗像,我是用圖法煉鋼的方法寫出,但似乎比上面的程式碼還慢,所以還是參考他的做法。

回目錄
回首頁

ACM 256 - Quirksome Squares

#include <stdio.h>

int main( void )
{
int i, n, j;
while (1)
{
if (scanf("%d", &n) < 1) break;
if (n == 2)
{
for (i = 0; i < 10; i ++)
for (j = 0; j < 10; j ++)
{
if ( i + j >= 10) break;
if ((i + j)*(i + j) == (i*10 + j))
printf("%02d\n",(i*10 + j));
}
}
if (n == 4)
{
for (i = 0; i < 100; i ++)
for (j = 0; j < 100; j ++)
{
if ( i + j >= 100) break;
if ((i + j)*(i + j) == (i*100 + j))
printf("%04d\n",(i*100 + j));
}
}
if (n == 6)
{
for (i = 0; i < 1000; i ++)
for (j = 0; j < 1000; j ++)
{
if ( i + j >= 1000) break;
if ((i + j)*(i + j) == (i*1000 + j))
printf("%06d\n",(i*1000 + j));
}
}
if (n == 8)
{
for (i = 0; i < 10000; i ++)
for (j = 0; j < 10000; j ++)
{
if ( i + j >= 10000) break;
if ((i + j)*(i + j) == (i*10000 + j))
printf("%08d\n",(i*10000 + j));
}
}
}
return 0;
}

回目錄
回首頁

ACM 253 - Cube painting

#include <stdio.h>

char str[15] = {"\0"};
struct Cube
{
char ch1;
char ch2;
int isComp;
};

struct Cube c[6];

int main()
{
while (gets(str))
{
int isTurn = 0, i, j;
c[0].ch1 = str[0], c[0].ch2 = str[5], c[0].isComp = 0;
c[1].ch1 = str[1], c[1].ch2 = str[4], c[1].isComp = 0;
c[2].ch1 = str[2], c[2].ch2 = str[3], c[2].isComp = 0;
c[3].ch1 = str[6], c[3].ch2 = str[11], c[3].isComp = 0;
c[4].ch1 = str[7], c[4].ch2 = str[10], c[4].isComp = 0;
c[5].ch1 = str[8], c[5].ch2 = str[9], c[5].isComp = 0;
for (i = 0; i < 3; i ++)
for (j = 3; j < 6; j ++)
{
if (c[i].isComp == 0 && c[j].isComp == 0)
{
if (c[i].ch1 == c[j].ch1 && c[i].ch2 == c[j].ch2 ||
c[i].ch1 == c[j].ch2 && c[i].ch2 == c[j].ch1)
{
c[i].isComp = 1, c[j].isComp = 1;
break;
}
}
}
for (i = 0; i < 6; i ++)
if (c[i].isComp == 0)
isTurn = 1;
if (isTurn)
printf("FALSE\n");
else printf("TRUE\n");
}
return 0;
}

回目錄
回首頁

2010年9月17日 星期五

ACM 202 - Repeating Decimals

#include <stdio.h>
#include <memory.h>

#define MAX 5000
#define DISPLAY_LIMIT 50
#define MAX_INT 3000

int min (int a , int b){
return a > b ? b : a;
}


int main()
{
int digits[MAX + 1], remainderExist[MAX_INT], remainderPos[MAX_INT];
while (1)
{
int numerator, denominator, oNumerator, quotient, remainder, recode, i;

if (scanf("%d", &numerator) < 1) break;
oNumerator = numerator;
scanf("%d", &denominator);

memset (remainderExist, 0, sizeof(remainderExist));
memset (remainderPos, 0, sizeof(remainderPos));

quotient = numerator / denominator;
remainder = numerator % denominator;

recode = quotient;
int n = 0, isCycle = 0, cyclePos = MAX, cycleLen = 0;

while ( n <= MAX && !isCycle)
{
if (remainderExist[remainder] )
{
cyclePos = remainderPos[remainder];
cycleLen = n - cyclePos;
isCycle = 1;
}
else
{
remainderExist[remainder] = 1;
remainderPos[remainder] = n;
}
numerator = remainder * 10;

quotient = numerator / denominator;
remainder = numerator % denominator;
digits[n] = quotient;
n ++;
}
printf("%d/%d = %d.", oNumerator, denominator, recode);
int limit = min(cyclePos, DISPLAY_LIMIT);

for (i = 0; i < limit; ++i )
printf("%d", digits[i]);

if (cyclePos < DISPLAY_LIMIT)
{
printf("(");
limit = min(n - 1, DISPLAY_LIMIT);
for (i = cyclePos; i < limit; ++i )
printf("%d", digits[i]);
if (n > DISPLAY_LIMIT)
printf("...");
printf(")");
}
printf("\n");
printf(" %d = number of digits in repeating cycle\n\n",cycleLen );

}
return 0;
}

回目錄
回首頁

HTML 程式設計筆記目錄

  1. float 蓋到另一區塊 ( div ) 的解決方法
  2. javascript 取得參數值
  3. javascript 子視窗關閉,重新整理母視窗
  4. 跑馬燈(marquee)使用方法
  5. javascript 取得參數 key 和 value 轉存陣列
  6. Javascript UrlEncode、UrlDecode、SetCookie、GetCookie、DelCookie 的函數
  7. AJAX學習筆記
  8. jquery ui for bootstrap 的使用
  9. Jquery 子母頁面間的 json 參數傳遞



float 蓋到另一區塊 ( div ) 的解決方法

些時候,寫 html 語法時會碰到需要用 float 屬性調整格式,但 float 屬性會蓋到其他區塊,例如:div、pre、.....等等。此時,就需要利用到 clear 屬性幫你解決覆蓋到其他區塊使用 float 的元素。

float 屬性中,left 使元素浮動在左,而 right 使元素浮動在右,none 則不會有任何效果。

clear 屬性中,left 會解除左側元素的浮動,right 會解除右側元素的浮動,both 會解除兩側元素的浮動,none 則不會有任何效果。

ACM 11799 - Horror Dash

#include <stdio.h>

int getInt()
{
char ch;
int n = 0;
while( ch = getchar())
if(ch != ' ' && ch != '\n') break;
n = ch - 48;
while( ch = getchar())
{
if(ch == ' ' || ch == '\n') break;
n = n * 10 + ch - 48;
}
return n;
}

int main()
{
int caseNum, i, n, m, max, j;
caseNum = getInt();

for (i = 1; i <= caseNum; i ++)
{
n = getInt();
max = 0;
while (n --)
{
m = getInt();
if (m > max) max = m;
}
printf("Case %d: %d\n", i, max);
}
return 0;
}


回目錄
回首頁

ACM 11805 - Bafana Bafana

#include <stdio.h>

int getInt()
{
char ch;
int n = 0;
while( ch = getchar())
if(ch != ' ' && ch != '\n') break;
n = ch - 48;
while( ch = getchar())
{
if(ch == ' ' || ch == '\n') break;
n = n * 10 + ch - 48;
}
return n;
}

int main()
{
int i, caseNum, N, K, P, j;
caseNum = getInt();
for (i = 1; i <= caseNum; i ++)
{
N = getInt(), K = getInt(), P = getInt();
j = (K + P) % N;
if (j == 0) j = N;
printf("Case %d: %d\n", i, j);
}
return 0;
}


回目錄
回首頁

ACM 10589 - Area

#include <stdio.h>

int main()
{
double N, a, x, y, i, in;
while (1)
{
scanf("%lf %lf", &N, &a);
if (N == 0 && a == 0) break;
in = 0;
for (i = 0 ; i < N; i++)
{
scanf("%lf %lf", &x, &y);
if (x*x + y*y < a*a && x*x + (a-y)*(a-y) < a*a &&
(a-x)*(a-x) + (a-y)*(a-y) < a*a && (a-x)*(a-x) + y*y < a*a)
in ++;
}
printf("%.5lf\n", (in/N)*a*a);
}
return 0;
}


回目錄
回首頁

ACM 10583 - Ubiquitous Religions

#include <stdio.h>
#include <memory.h>
int n, m;

int getInt()
{
char ch;
int n = 0;
while( ch = getchar())
if(ch != ' ' && ch != '\n') break;
n = ch - 48;
while( ch = getchar())
{
if(ch == ' ' || ch == '\n') break;
n = n * 10 + ch - 48;
}
return n;
}

int main()
{
int caseNum = 1, s, i, j, religionID, count, tmp, replace;
while ((n = getInt()) && (m = getInt()))
{
int student[n + 1];
religionID = 1, count = 0;
memset(student, 0, sizeof(student));
while (m --)
{
i = getInt(), j = getInt();
if (student[i] == 0 && student[j] == 0)
{
student[i] = religionID, student[j] = religionID;
religionID ++;
count ++;
}
else if((student[i] != 0 && student[j] == 0) ||
(student[i] == 0 && student[j] != 0))
{
tmp = student[i] < student[j] ? student[j] : student[i];
student[i] = tmp, student[j] = tmp;
}
else if (student[i] != student[j])
{
tmp = student[j];
replace = student[i];
for (s = 1; s <= n; s ++)
if (student[s] == tmp) student[s] = replace;
count --;
}
}
/* for (i = 1; i <= n; i ++)
printf("%d ", student[i]);
printf("\n"); */
for (i = 1; i <= n; i ++)
if (student[i] == 0) count ++;
printf("Case %d: %d\n", caseNum ++, count);

}
return 0;
}


回目錄
回首頁

ACM 10608 - Friends

#include <stdio.h>
#include <memory.h>
#define SIZE 30000

int getInt()
{
char ch;
int n = 0;
while( ch = getchar())
if(ch != ' ' && ch != '\n') break;
n = ch - 48;
while( ch = getchar())
{
if(ch == ' ' || ch == '\n') break;
n = n * 10 + ch - 48;
}
return n;
}

int main()
{

int caseNum, a, b, s, n, m, count, groupID, tmp, replace;
caseNum = getInt();
while (caseNum --)
{
n = getInt(), m = getInt();
int friends[n + 1], record[n + 1], max = 0;
count = 0, groupID = 1;
memset(friends, 0, sizeof(friends));
memset(record, 0, sizeof(record));
while (m --)
{
a = getInt(), b = getInt();
if (friends[a] == 0 && friends[b] == 0)
{
friends[a] = groupID, friends[b] = groupID;
record[groupID] = 2;
if (max < record[groupID]) max = record[groupID];

groupID ++;
count ++;
}
else if((friends[a] != 0 && friends[b] == 0) ||
(friends[a] == 0 && friends[b] != 0))
{
tmp = friends[a] < friends[b] ? friends[b] : friends[a];
friends[a] = tmp, friends[b] = tmp;
record[tmp] ++;
if (max < record[tmp]) max = record[tmp];
}
else if (friends[a] != friends[b])
{
tmp = friends[b];
replace = friends[a];
record[tmp] = 0;
for (s = 1; s <= n; s ++)
if (friends[s] == tmp) friends[s] = replace, record[replace] ++;
if (max < record[replace]) max = record[replace];
count --;
}
/* for (s = 1; s <= n; s ++)
printf("%d ", record[s]);
printf("\n"); */
}
printf("%d\n", max);
}

return 0;
}


回目錄
回首頁