首页 > 代码库 > 算法竞赛入门经典习题2-6 排列(permutation)

算法竞赛入门经典习题2-6 排列(permutation)

暴力解法:

 1 #include <stdio.h> 2 #include <stdlib.h> 3  4 int compare(const void *a, const void *b); 5  6 int main(int argc, char **argv){ 7     int i,j,k; 8     int arr[9]; 9     for(i=100;i<333;i++){10     for(j=200;j<666;j++){11         for(k=300;k<1000;k++){12         arr[0] = i/100;13         arr[1] = (i/10)%10;14         arr[2] = i%10;15         arr[3] = j/100;16         arr[4] = (j/10)%10;17         arr[5] = j%10;18         arr[6] = k/100;19         arr[7] = (k/10)%10;20         arr[8] = k%10;21         qsort(arr, 9, sizeof(int),compare);22         int m;23         for( m = 0; m<9; m++){24             if(arr[m] != m+1){25             break;26             }27         }28         if(m == 9){29             if(k%i==0 && j%i == 0 && k/i == 3 && j/i == 2){30             printf("%d %d %d\n",i,j,k);31             }32         }33         }34     }35     }36     return 0;37 }38 int compare(const void *a, const void *b){39     return *(int*)a - *(int*)b;40 }

 vs.

 1 #include <stdio.h> 2 #include <stdlib.h> 3  4 int compare(const void *a, const void *b); 5  6 int main(int argc, char **argv){ 7     int arr[9]; 8     int abc, def, ghi; 9     for(abc = 100; abc <334; abc++){10     def = 2 * abc;11     ghi = 3 * abc;12     arr[0] = abc/100;13     arr[1] = (abc/10)%10;14     arr[2] = abc%10;15     arr[3] = def/100;16     arr[4] = (def/10)%10;17     arr[5] = def%10;18     arr[6] = ghi/100;19     arr[7] = (ghi/10)%10;20     arr[8] = ghi%10;21     qsort(arr, 9, sizeof(int), compare);22     int m;23     for( m = 0; m<9; m++){24         if(arr[m] != m+1){25         break;26         }27     }28     if(m == 9){29         printf("%d %d %d\n",abc, def, ghi);30     }31     }32     return 0;33 }34 35 int compare(const void *a, const void *b){36     return *(int*)a - *(int*)b;37 }

 

算法竞赛入门经典习题2-6 排列(permutation)