Blog » PUNKBALL on iNDIEVOX

2010-08-02 | Uncategorized

<!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” xmlns:fb=”http://www.facebook.com/2008/fbml”>
<head>
<title>facebook auth</title>
</head>
<body>
<script src=”http://static.ak.connect.facebook.com/js/api_lib/v0.4/FeatureLoader.js.php/zh_TW” type=”text/javascript”></script>

FB.init(”your api key”,”/xd_receiver.htm”,{”ifUserConnected”:onConnected,”ifUserNotConnected”:onNotConnected});

function onConnected() {
FB.Facebook.apiClient.fql_query(”select email from permissions where uid = ‘”+FB.Facebook.apiClient.get_session().uid+”‘”,
function(rows) {
var email_permission = rows[0].email;

if(email_permission==0){
FB.Connect.showPermissionDialog(”email, read_stream, publish_stream, offline_access”, checkPermission, true, []);
}else{
document.location=”/facebook_login_action.php?fb_personal_api=”+FB.Facebook.apiClient.get_session().uid;
}
});
}
function onNotConnected() {
FB.Facebook.apiClient.requireLogin();
}
function checkPermission() {
window.location.reload();
}

</script>
</body>
</html>

Original URL: http://fukuball.twbbs.org/?p=139

0 comment(s)

2010-01-15 | Uncategorized

Facebook 是好物!

沒什麼事情~ 只是純粹這樣覺得而已!

0 comment(s)

2009-12-10 | fukuball

Algorithm Gossip: 基數排序法

說明

在之前所介紹過的排序方法，都是屬於「比較性」的排序法，也就是每次排序時，都是比較整個鍵值的大小以進行排序。

這邊所要介紹的「基數排序法」（radix sort）則是屬於「分配式排序」（distribution sort），基數排序法又稱「桶子法」（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些「桶」中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的比較性排序法。

解法

基數排序的方式可以採用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

以LSD為例，假設原來有一串數值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：

0	1	2	3	4	5	6	7	8	9
	81				65				39
			43	14	55			28
			93
		22	73

接下來將這些桶子中的數值重新串接起來，成為以下的數列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接著再進行一次分配，這次是根據十位數來分配：

0	1	2	3	4	5	6	7	8	9
	28	39
	14	22		43	55	65	73	81	93

接下來將這些桶子中的數值重新串接起來，成為以下的數列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。

LSD的基數排序適用於位數小的數列，如果位數多的話，使用MSD的效率會比較好，MSD的方式恰與LSD相反，是由高位數為基底開始進行分配，其他的演算方式則都相同。

實作

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

int main(void) {
    int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};
    int temp[10][10] = {0};
    int order[10] = {0};
    int i, j, k, n, lsd; 

    k = 0;
    n = 1; 

    printf("\n排序前: ");
    for(i = 0; i < 10; i++)
        printf("%d ", data[i]); 

    putchar('\n'); 

    while(n <= 10) {
        for(i = 0; i < 10; i++) {
            lsd = ((data[i] / n) % 10);
            temp[lsd][order[lsd]] = data[i];
            order[lsd]++;
        } 

        printf("\n重新排列: ");
        for(i = 0; i < 10; i++) {
            if(order[i] != 0)
                for(j = 0; j < order[i]; j++) {
                    data[k] = temp[i][j];
                    printf("%d ", data[k]);
                    k++;
                }
            order[i] = 0;
        } 

        n *= 10;
        k = 0;
    } 

    putchar('\n');
    printf("\n排序後: ");
    for(i = 0; i < 10; i++)
        printf("%d ", data[i]); 

    return 0;
}

Java

public class RadixSort {
    public static void sort(int[] number, int d) {
        int k = 0;
        int n = 1;

        int[][] temp = new int[number.length][number.length];
        int[] order = new int[number.length];

        while(n <= d) {
            for(int i = 0; i < number.length; i++) {
                int lsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            } 

            for(int i = 0; i < number.length; i++) {
                if(order[i] != 0)
                    for(int j = 0; j < order[i]; j++) {
                        number[k] = temp[i][j];
                        k++;
                    }
                order[i] = 0;
            } 

            n *= 10;
            k = 0;
        }
    }

    public static void main(String[] args) {
        int[] data =
           {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100}; 

        RadixSort.sort(data, 100);

        for(int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
    }
}

Original URL: http://fukuball.twbbs.org/?p=137

0 comment(s)

2009-12-09 | fukuball