2011年4月19日 星期二

[Java] 計算質數的效率

計算質數的題目應該是每個人程式入門都會碰到的
當然這個題目以現今的電腦來說應該沒有什麼效率的問題
只是前陣子因為上了學校很弱的Java課,寫到這種題目
突然又想來實驗一下,小小的寫法差異會帶來怎樣的效率差別?
一般常見的的思考方法是用for迴圈,起始為除數2,一直除到N-1為止
簡單的程式碼會如下:
for(int i=0;i<=N-1;i++){
    if(N % i ==0){
        xxxx;
    }
}
我之前有想過,如果當N很大時,迴圈一直run到N-1豈不很費時?
因為最小的除數是2,換句話說最大的除數一定不會大於N除以2
例:假設N是100,100最大的除數就是100/2的50,
而如果N是99,最大的除數也不可能超過99/2
如果是這樣的情況,當N是質數時,可以少跑一半的迴圈
不過後來我去查了一下資料,其實/2的想法還不夠聰明 XD
最直接的方法是除到把N開根號為止
因為超過根號N之後可能的除數就皆已出現過
以下就是實作看看執行時間上的差異,用迴圈跑求65537是否是質數跑五千次
首先是用N-1方法跑:

public class Test {
    public static void main(String[] args) {
        boolean ans = true;
        long in_num = 65537;
        long time1, time2;
        time1 = System.currentTimeMillis();
        for (int k = 0; k <= 5000; k++) {
            for (long i = 2; i <= in_num - 1; i++) {
                if (in_num % i == 0) {
                    ans = false;
                    break;
                }
            }
            if (ans) {
                //System.out.println("是質數");
            }
        }
        time2 = System.currentTimeMillis();
        System.out.println((double) (time2 - time1) / 1000);
    }
}
N-1的版本跑五千次總共花了24.312秒(數據皆以公司爛爛的老賽揚上跑的)
那再來就是根號N的版本

public class Test {
    public static void main(String[] args) {
        boolean ans = true;
        long in_num = 65537;
        long time1, time2;
        time1 = System.currentTimeMillis();
        for (int k = 0; k <= 5000; k++) {
            for (long i = 2; i <= Math.pow(in_num, 0.5); i++) {
                if (in_num % i == 0) {
                    ans = false;
                    break;
                }
            }
            if (ans) {
                //System.out.println("是質數");
            }
        }
        time2 = System.currentTimeMillis();
        System.out.println((double) (time2 - time1) / 1000);
    }
}
利用Java的Math.pow去求出根號N
這個版本只跑了1.329秒
雖然比N-1快上了18.2倍,但是根號N法好像也沒有想像的快?
因為測驗的N越大,根號N法的優勢就越大
當我們把N換成比較小的質數1937跑五萬次時,根號N法跑了0.516秒
而N-1法卻只跑了0.063秒,N-1法反倒快了8.1倍
這樣的結果還令人覺得滿吃驚的
這邊我想到一個問題,會不會是因為For判斷式中的Math.pow每次都要重新計算呢?
於是我將開根號的動作另外用一個變數先存,變數的宣告與賦值都包含在計時範圍內
結果這個版本的根號N只花了0.015秒,成功的在小質數上也勝過了N-1
於是我們再回頭去實驗三種情況的大質數,結果出爐
N=65537,圈數五千。N-1法:24.312秒,根號N法:1.329秒,新根號N法:0.094秒

結論:使用迴圈時常習慣判斷式用function去寫而不額外建變數,
但這樣其實對效能而言可能並不一定是正面的,只是寫的時候方便
要說匿名宣告省記憶體?我覺得難說,說不定反而多耗,
或者是就算有省,那一個變數也差不了多少‧‧‧‧

2011年4月18日 星期一

[Java] 期中考

一整個很悲哀的期中考
我配到的那台電腦沒裝NetBeans
用JECrxxx那套一整個不習慣
而且還當機,寫好沒錯的程式碼就是不會動
把程式關掉重開貼上去又好了?!
浪費了我一堆時間
兩題都沒寫好,真是人生一大敗筆
不過不管怎麼說都是自己不夠熟練又不夠冷靜的問題
要改進啊....唉

第一題:用For迴圈讓程式跑出1+1+2+3+5+8.....=xxxx (加到最後一個數小於等於1000為止)

嗯....費式數列的變相考法
可能真的太久沒寫了,我在這題上面耍了很多寶
除了浪費了很多時間以外,最後寫出來的程式不算很漂亮
現在鞭打自己好好重寫 T__T
public class NewClass {
    public static void main(String[] args){
        int n1=0,n2=0,n3=1,sum=0;
        for(int i=0;n3<=1000;i++){
            if(i != 0){
                System.out.print("+");
            }
            System.out.print(n3);
            sum += n3;
            n1 = n2;
            n2 = n3;
            n3 = n1+n2;
        }
        System.out.print("=" + sum);
    }
}

第二題:輸入四位數西洋年判斷是否為閏年(閏年為可以被4整除,但不可被100整除,又可以被400整除)

題目很簡單,問題是老師很白痴。
他直接把題目從課本照抄也不先自己仔細看一下或寫一下
看看題目後面寫的閏年判斷準則,會不會詭異?
以我看到的,我會認為它是說要同時滿足可以被4與400整除,又不可被100整除。
這不用說,邏輯上就有問題直接打槍了。世界上沒有數字可以被400整除卻不能被100整除的。
我跟老師反應後他也想了老半天,還跟我說是完全沒改從課本抄來的
(這是怎樣?就算題目有錯也先推給課本嗎?)
結果被他浪費掉的時間也不還給我,害我最後寫的時間嚴重不足
其實正確的表示法應該要把「又可以被400整除」,改成「除非它也可以被400整除」
拜托....身為台灣人,這樣才是正確的中文表達方法好嗎
好啦,在正確的表達後不難看出條件
程式碼如下:
import java.io.*;
public class NewClass1 {
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int in_y;
        System.out.print("請輸入四位數西洋年:");
        in_y = Integer.parseInt(in.readLine());
        if((in_y%4==0 &&in_y%100!=0)||(in_y%100==0&&in_y%400==0)){
            System.out.print(in_y + "為閏年");
        }else{
            System.out.print(in_y + "不是閏年");
        }
    }
}

2010年12月2日 星期四

[C#] 將二進位資料寫入資料庫

這兩天在研究如何對資料庫操作二進位的資料
最基本的應用就是把圖片存進資料庫,而不是只存圖片路徑
以撰寫應用程式的層面來看
大致上就是
1.「將已存在於電腦上的圖片讀入pictureBox」
2.「將該圖片寫入資料庫」
3.「從資料庫讀出圖片至pictureBox」
這三個主要的動作
在Access上是使用OLE物件為該圖片欄位的資料型態
而Oracle則是Blob

第一個算是控制項操作基礎也沒啥好講的了
2跟3倒是費了我不少時間,尤其是在Oracle方 Orz
圖片寫入資料庫的流程概念:
1.將圖片轉存為記憶體串流
2.將記憶體串流轉為byte陣列
(此步驟是因為有一些特別的圖片格式無法直接轉成byte陣列)
3.將byte陣列寫入資料庫

從資料庫讀出圖片就是反向:
1.從資料庫將圖片讀出存放在byte陣列
2.將byte陣列轉換為記憶體串流
3.把記憶體串流做為pictureBox的顯示圖片

再來就來看看實做的Code吧
假設今天Access資料庫為test.mdb,img資料表
有兩個欄位,id與pics
先看寫入資料庫的部份
MemoryStream st = new MemoryStream();
pBox.Image.Save(st, pBox.Image.RawFormat);
byte[] by = st.ToArray();
string strDbConn = "Provider=Microsoft.Jet.OLEDB.4.0;Data Source=" + Application.StartupPath + "\\test.mdb";
OleDbConnection OdbConn = new OleDbConnection(strDbConn);
OdbConn.Open();
OleDbCommand OdbCmd = new OleDbCommand("update img set pics = ? where id = 1", OdbConn);
OleDbParameter parameter = new OleDbParameter("pics", System.Data.OleDb.OleDbType.Binary);
parameter.Size = by.Length;
parameter.Value = by;
OdbCmd.Parameters.Add(parameter);
OdbCmd.ExecuteNonQuery();
OdbCmd.Dispose();
OdbConn.Close();
OdbConn.Dispose();

再來是從資料庫讀出圖片
string strDbConn = "Provider=Microsoft.Jet.OLEDB.4.0;Data Source=" + Application.StartupPath + "\\test.mdb";
OleDbConnection OdbConn = new OleDbConnection(strDbConn);
OdbConn.Open();
OleDbCommand OdbCmd = new OleDbCommand("select pics from img where id = 1", OdbConn);
byte[] by = (byte[])OdbCmd.ExecuteScalar();
MemoryStream st = new MemoryStream(by, 0, by.Length);
pBox.Image = Image.FromStream(st);
OdbCmd.Dispose();
OdbConn.Close();
OdbConn.Dispose();

Oracle的部份雖然有實作成功
不過跟我所找到的一些國外的文件在做法上有差異
等我把他搞清楚整個機制再來po

2010年11月25日 星期四

[VB] 作業 - 購物機

購物機?大概吧,管他的
反正就是一個從課本範例去改的程式
這種作業對出題老師而言應該算是很輕鬆
不用自己想題目,還可以稍加變更多加條件進去

完成圖大概如下


這種題目其實只有一個重點
那就是要記得把計算總價另外寫副程式
然後不管是更改數量、更改選取與否或是更改運送法
都直接call副程式去運算就好了

撰寫上的差異大概就是
你要手動把每個事件分開寫
還是把所有同類事件寫一起
例如所有的TextChange只寫一個事件
分開寫跟一起寫其實差異不大
只不過一起寫看起來比較省字、比較高明
(但是原始碼是自己在看的,高不高明意義好像也不大
省字卻又不一定快,因為分開寫可以複製貼上再小小改過即可)
反正就是....見仁見智吧
只是,當今天有動態控制項或是控制項超多的時候
如果只會一個個分開寫大概會死人吧

剩下的....沒了
這種基礎程式沒啥難度可言

2010年11月18日 星期四

[C#] 作業 - 點餐機

題目跟之前的一樣
不過這次改用C#來認真寫了一下

C#版本多了甜點跟飲料單點功能
而且利用dataGridView加上comboBox
讓更改已經點了的菜單更加簡單也合理化
(之前VB版要改一個人就要所有人全部重點)

至於結帳明細
我是覺得內容列表出已經出來了
其實也就是一種結帳明細了
何況題目本來就是舉例一種做法
沒有強制規定一定要用○○○xN的方法來做
我覺得像這樣直接用表格做更好看也方便

完成圖兩張~

2010年11月8日 星期一

[C#] 限制textBox只能輸入數字

這個其實在學校教程式設計的時候常不會去講到
在入門來講,textBox當輸入介面是必然的事
不過當你辛苦的寫了一個簡單的四則運算程式後
你發現你只要不小心打了一個不是數字的字進textBox就會出錯
這是多麼令人傷心啊(咦?)

好啦,這不是重點
其實程式設計就是這樣
要先將會使用的人想成是電腦白癡之外
還要假設他們看不懂中文
明明就叫你輸入數字了,你偏要打英文甚至是中文字進去是怎樣 XD
所以寫程式的人就要在這種小細節用心 囧rz
private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
{
    if ((int)e.KeyChar < 48 | (int)e.KeyChar > 57)
    {
        e.Handled = true;
    }
}
這樣就可以讓該textBox無法輸入數字以外的字
不過問題來了
你會發現連Backspace也不能用了
對寫程式的人來說覺得沒差
不過竟然發現了就改進一下吧 XD
private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
{
    if (((int)e.KeyChar < 48 | (int)e.KeyChar > 57) & (int)e.KeyChar!=8)
    {
        e.Handled = true;
    }
}

2010年11月3日 星期三

[VB] 跟IIf說再見~

VB.Net在VS2005有個函數叫IIf
簡單舉例用法如下:
Dim age As Integer = 18
MsgBox(IIf(age >= 18, "可看限制級", "不可看限制級"))
此例即是輸出判斷式為真的"可看限制級"

不過IIf其實在VS2008是不建議使用的
建議改以效率較佳的If替代
因為IIf不論判斷式為真或假,皆會去運算後面的兩個內容
這樣除了效率較差,亦有可能會產生錯誤
而If則只運算符合判斷式的內容
舉個例子最快~
Dim a As Integer = 4
Dim b As Integer = 0
MsgBox(If(True, a, a \ b))
Dim a As Integer = 4
Dim b As Integer = 0
MsgBox(IIf(True, a, a \ b))
前者用If,因為判斷式為true,所以不會去運算後面的 4 \ 0
而IIf即便為true,也一樣會去運算 4 \ 0而導致發生錯誤