泡沫排序.....

請問誰會泡沫排序阿...??教一下好不好 還是幫我弄一個出來 感恩

2 Answers

Rating
  • Anonymous
    2 decades ago
    Favorite Answer

    之前有個匿名要人寫樂透的也有問過, 可能稱為超級樂透問題可能比較恰當. 我比較訝異的是您不知道怎麼算出每一筆怎麼就已經能夠理解共有幾筆的算法...?

    這個問題是屬於 Computational Mathematics, 您可以找 Combinatorial Enumeration 這個 topic 的 Set Enumeration. 一般來說是要從 size=0 開始一直跑到 size=|set|, 但為了樂透就直接給它 size=6 吧.

    這題有兩種求法. 一種是依觀念把 {1,2,3,4,5,6,7,8} 中拿掉兩個不同的號碼, 每次拿掉的號碼必需不一樣. 另一種是完全以 enumeration 方式處理: given 一個 set, 找出下一個 set. 在此我用這種方式, 因為求出來的答案是由大到小排好的.

    首先定義一個 score 或是 value, 用來做比較大小的依據. 採用 polynomial 方式, {1,2,3,4,5,6} = x^5 + 2x^4 + 3x^3 + 4x^2 + 5x + 6, 其中 x 值大於 set 中任何數值. 因此最的數字是最高位數, 最右是最低位數, 好比十進位的 123456 < 123457.

    還有每個 set 只採用它最小的表示法, 例如不用 {6,5,4,3,2,1} 因為裡面六個數字 {1,2,3,4,5,6} 都有, 但 654321 > 123456.

    接下來用現有的 set 要找下一個 set. 找法很簡單, 從最低位開始找看看有沒有哪個數字可以被替換成大它一號的 set. 在此我使用另一個排序過的 free set 裝可以換上去的數字.

    {1,2,3,4,5,6} {7,8,9} -> 發現 6th, 7>6

    {1,2,3,4,5,7} {6,8,9} -> 發現 6th, 8>7

    {1,2,3,4,5,8} {7,8,9} -> 發現 6th, 9>8

    換到 free set 最大的數字被用掉後一定得進位. 進位後也是一樣的動作, 只是加上了要處理 "尾巴" (剩下的低位數要歸到最小). 其實尾巴很好做, 上一位數字加一就是. 在程式中我為了維持 free set 的正確性所以還是笨笨的用 swap 方式而不是直接填.

    {1,2,3,4,5,9} {6,7,8} -> 找不到 6th 任何數>9 進一位; 發現 5th, 6>5; 6 後面最小的一定是 7.

    {1,2,3,4,6,7} {5,8,9} -> 找到 6th, 8>7

    {1,2,3,4,6,8} {5,7,9} .... 依此類推下去可以一直找到下一組剛好大一點.

    到最後會有找不到可以替換的現像, 那時就是結束了.

    {4,5,6,7,8,9} {1,2,3} 沒東西>4, 沒得換了便可結束.

    底下給你一個上次求樂透的解答. 可惜那篇才回完就被砍了. 其實一找到就 print 即可, 不需要把每筆都存起來.

    #include <time.h>

    #include <stdio.h>

    #include <stdlib.h>

    #define MIN_VAL 1

    #define MAX_VAL 42

    /* Lotto entry structure (6 numbers) */

    struct entry {

    int val[6];

    struct entry *next;

    };

    void swap(int *i, int *j){

    int n;

    n=*i;

    *i=*j;

    *j=n;

    }

    /* bubble sort array of size sz */

    void sort(int *arr, int sz){

    int i,j;

    for(i=0; i<sz-1; i++)

    for(j=i+1; j<sz; j++)

    if(arr[i]>arr[j])

    swap(&arr[i], &arr[j]);

    }

    /* Read 6 numbers from stdin */

    int entry_input(struct entry *e){

    if(!e) return -1;

    e->next=NULL;

    scanf("%d %d %d %d %d %d",

    &e->val[0], &e->val[1], &e->val[2],

    &e->val[3], &e->val[4], &e->val[5]);

    sort(e->val, 6);

    if(e->val[0]<MIN_VAL || e->val[6]>MAX_VAL) return -1;

    return 0;

    }

    /* Randomly generate entry */

    int entry_generate(struct entry *e){

    int i, min=MIN_VAL;

    if(!e) return -1;

    e->next=NULL;

    srand(time(NULL));

    for(i=0; i<6; i++){

    int r; /* randomly chosen value */

    r=min+(int)((MAX_VAL-min+i-5.0)*rand()/(RAND_MAX+1.0));

    min=r+1;

    e->val[i]=r;

    }

    return 0;

    }

    /* Given one number combination, find next */

    int next(int *num, int nc, int *free, int fc){

    int i,j;

    for(i=nc-1; i>=0; i--){

    for(j=0; j<fc; j++){

    if(num[i]<free[j]){

    swap(&num[i], &free[j]);

    sort(free, fc);

    i++;

    while(i<nc){

    for(j=0; j<fc && num[i-1]>free[j]; j++);

    if(j<fc) swap(&num[i], &free[j]);

    sort(free, fc);

    i++;

    }

    return 1;

    }

    }

    }

    return 0;

    }

    /* Generate set of combinations from given numbers */

    struct entry *set_generate(int num[], int count){

    struct entry *root, *step;

    int pool[]={0,1,2,3,4,5}, free[]={6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

    int i, fc=count-6;

    int loopcount=0;

    if(!num || count<7 || count>20) return NULL;

    sort(num, count);

    root=(struct entry *)malloc(sizeof(struct entry));

    step=root;

    for(i=0; i<6; i++)

    step->val[i]=num[pool[i]];

    while(next(pool, 6, free, fc)){

    if(loopcount>10000)

    printf("Endless loop!\n");

    step->next=(struct entry *)malloc(sizeof(struct entry));

    step=step->next;

    for(i=0; i<6; i++)

    step->val[i]=num[pool[i]];

    }

    step->next=NULL;

    return root;

    }

    void entry_print(const struct entry *e){

    const struct entry *step=e;

    printf("%02d %02d %02d %02d %02d %02d\n",

    step->val[0], step->val[1], step->val[2],

    step->val[3], step->val[4], step->val[5]);

    while(step->next){

    step=step->next;

    printf("%02d %02d %02d %02d %02d %02d\n",

    step->val[0], step->val[1], step->val[2],

    step->val[3], step->val[4], step->val[5]);

    }

    }

    /* Free allocated memory */

    void entry_free(struct entry *e){

    struct entry *step;

    step=e->next;

    free(e);

    while(step->next){

    step=step->next;

    free(step);

    }

    }

    /* Test above functions */

    int main(int argc, char *argv[]){

    int nums[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

    // int nums[]={5, 10, 15, 20, 25, 30, 35, 40};

    int n;

    struct entry *e;

    e=(struct entry *)malloc(sizeof(struct entry));

    /*

    printf("Enter lotto numbers: ");

    if(entry_input(e)) printf("Error reading");

    else entry_print(e);

    printf("\n\n");

    printf("Generate lotto numbers\n");

    if(entry_generate(e)) printf("Error generating");

    else entry_print(e);

    printf("\n\n");

    */

    if(argc<2 || (n=atoi(argv[1]))<=6 || n>20) n=8;

    printf("Generate lotto numbers for 8 number-combo\n");

    if(!(e=set_generate(nums, n))) printf("Error generating");

    else entry_print(e);

    if(e!=NULL) entry_free(e);

    return 0;

    }

    輸出結果: (有多印一行字所以 wc 算出來的組數要 -1)

    linux~/c$ ./lotto 8

    Generate lotto numbers for 8 number-combo

    01 02 03 04 05 06

    01 02 03 04 05 07

    01 02 03 04 05 08

    01 02 03 04 06 07

    01 02 03 04 06 08

    ....

    linux~/c$ ./lotto 8 | wc

    29 174 546

    linux~/c$ ./lotto 9 | wc

    85 510 1554

    linux~/c$ ./lotto 10 | wc

    211 1266 3822

    linux~/c$ ./lotto 15 | wc

    5006 30036 90132

    Source(s): 知識+
    • Commenter avatarLogin to reply the answers
  • 2 decades ago

    // 假設 int a[10]; 已經有 data, 需要排序

    int tmp;

    for (int i=0;i<(10-1);i++) {

    for (int j=0;j<10;j++) {

    // must a[i] <= a[j]

    if (a[i] > a[j]) {

    // swap a[i], a[j]

    tmp= a[i]; a[i]= a[j]; a[j]= tmp;

    }

    }

    }

    // 以上的 code 未經測試,應該不會錯

    Source(s): me
    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.