作者enthos (影斯)
看板CodeJob
標題Re: [發案] 徵求程式設計高手 (有關排列組合)
時間Tue Oct 20 12:46:41 2009
// 我不會 matlib
// 資料用字串方式, 方便改成其他格式如:
// {"Z_YAHO", "Y_MOMO", "X_WAWA", "W_VIVO", "V_OUCH", }
// 如果印出 "X" 表示程式寫錯了.
// 這種問題是兩個陣列(資料、數值)和雙層 for loop 的小作業.
// 跟排列組合關係不大. (當然如果不印資料, 直接用 n, k 算出總數,
// 就是排列組合的問題, 要轉 Math 版.)
// gcc -o print_sort_num.bin print_sort_num.c
// print_sort_num.c
#include <stdio.h>
#include <stdlib.h>
char data[][2] = {"1", "2", "3", "4", "5", "X", "X", "X"};
int n = 5;
int k = 3;
int main()
{
int i, j;
int wrap=0;
int all[k];
int quit;
for(i=0; i<k; i++)
all[i] = 0;
quit = 0;
while(quit == 0) {
for(i=0; i<k; i++)
printf(" %s", data[all[i]]);
printf(",");
for(i=k-1; i>=0; i--) {
if (all[i] < n-1) {
all[i]++;
for(j=i+1; j<k; j++)
all[j] = all[i];
break;
}
}
quit = 1;
for(j=0; j<k; j++)
if (all[j] < n-1)
quit = 0;
wrap++;
if ((wrap+1)%8==0)
printf("\n");
}
for(i=0; i<k; i++)
printf(" %s", data[all[i]]);
printf("\n");
printf("count is %d\n", wrap+1);
return 0;
}
// ./print_sort_num.bin
1 1 1, 1 1 2, 1 1 3, 1 1 4, 1 1 5, 1 2 2, 1 2 3,
1 2 4, 1 2 5, 1 3 3, 1 3 4, 1 3 5, 1 4 4, 1 4 5, 1 5 5,
2 2 2, 2 2 3, 2 2 4, 2 2 5, 2 3 3, 2 3 4, 2 3 5, 2 4 4,
2 4 5, 2 5 5, 3 3 3, 3 3 4, 3 3 5, 3 4 4, 3 4 5, 3 5 5,
4 4 4, 4 4 5, 4 5 5, 5 5 5
count is 35
diff -u1 print_sort_num.c print_sort_num5.c
--- print_sort_num.c
+++ print_sort_num5.c
@@ -6,3 +6,3 @@
int n = 5;
-int k = 3;
+int k = 4;
@@ -36,3 +36,3 @@
wrap++;
- if ((wrap+1)%8==0)
+ if ((wrap+1)%4==0)
printf("\n");
// gcc -o print_sort_num5.bin print_sort_num5.c
1 1 1 1, 1 1 1 2, 1 1 1 3,
1 1 1 4, 1 1 1 5, 1 1 2 2, 1 1 2 3,
1 1 2 4, 1 1 2 5, 1 1 3 3, 1 1 3 4,
1 1 3 5, 1 1 4 4, 1 1 4 5, 1 1 5 5,
1 2 2 2, 1 2 2 3, 1 2 2 4, 1 2 2 5,
1 2 3 3, 1 2 3 4, 1 2 3 5, 1 2 4 4,
1 2 4 5, 1 2 5 5, 1 3 3 3, 1 3 3 4,
1 3 3 5, 1 3 4 4, 1 3 4 5, 1 3 5 5,
1 4 4 4, 1 4 4 5, 1 4 5 5, 1 5 5 5,
2 2 2 2, 2 2 2 3, 2 2 2 4, 2 2 2 5,
2 2 3 3, 2 2 3 4, 2 2 3 5, 2 2 4 4,
2 2 4 5, 2 2 5 5, 2 3 3 3, 2 3 3 4,
2 3 3 5, 2 3 4 4, 2 3 4 5, 2 3 5 5,
2 4 4 4, 2 4 4 5, 2 4 5 5, 2 5 5 5,
3 3 3 3, 3 3 3 4, 3 3 3 5, 3 3 4 4,
3 3 4 5, 3 3 5 5, 3 4 4 4, 3 4 4 5,
3 4 5 5, 3 5 5 5, 4 4 4 4, 4 4 4 5,
4 4 5 5, 4 5 5 5, 5 5 5 5
count is 70
diff -u1 print_sort_num.c print_sort_num20.c
--- print_sort_num.c
+++ print_sort_num20.c
@@ -4,5 +4,16 @@
-char data[][2] = {"1", "2", "3", "4", "5", "X", "X", "X"};
-int n = 5;
-int k = 3;
+char data[][3] = {"1", "2", "3", "4", "5",
+ "6", "7", "8", "9", "10",
+ "11", "12", "13", "14", "15",
+ "16", "17", "18", "19", "20",
+ "21", "22", "23", "24", "25",
+ "26", "27", "28", "29", "30",
+ "31", "32", "33", "34", "35",
+ "36", "37", "38", "39", "40",
+ "41", "42", "43", "44", "45",
+ "46", "47", "48", "49", "50",
+ "X", "X", "X"
+ };
+int n = 50;
+int k = 20;
@@ -36,3 +47,3 @@
wrap++;
- if ((wrap+1)%8==0)
+ if ((wrap+1)%1==0)
printf("\n");
# mkdir /ram
# mount -t tmpfs none /ram
# date > post_date.txt; ./print_sort_num20.bin > /ram/gogo.log \
date >> post_date.txt
# df /ram
Filesystem 1K-blocks Used Available Use% Mounted on
none 1005168 1005168 0 100% /ram
# tail -3 /ram/gogo.log
1 1 1 1 1 1 1 1 1 1 1 1 1 1 12 13 16 25 38 48,
printf("\n");
# mkdir /ram
# mount -t tmpfs none /ram
# date > post_date.txt; ./print_sort_num20.bin > /ram/gogo.log \
date >> post_date.txt
# df /ram
Filesystem 1K-blocks Used Available Use% Mounted on
none 1005168 1005168 0 100% /ram
# tail -3 /ram/gogo.log
1 1 1 1 1 1 1 1 1 1 1 1 1 1 12 13 16 25 38 48,
1 1 1 1 1 1 1 1 1 1 1 1 1 1 12 13 16 25 38 49,
1 1 1 1 1 1 1 1
# date>null.txt; ./print_sort_num20.bin>/dev/null; date >> null.txt
# 跑不完... 我設定 CPU 降速讓風扇靜音.
# cat /proc/cpuinfo
model name : AMD Athlon(tm) 64 X2 Dual Core Processor 4200+
cpu MHz : 1000.000
cache size : 512 KB
bogomips : 2010.85
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.22.98
1F：→ DigiPrince:你有抓到點嗎？大家都知道 implementation 不難啊... 10/20 15:46
2F：→ DigiPrince:就算你沒抓到點，在 CodeJob PO 這篇文的用意又是什麼? 10/20 15:48
3F：推 Topi:........ Orz 10/20 18:18
4F：→ xvid:show off 10/21 00:01
5F：→ kule:運算就很久了,這裡用到printf的次數如此高,完成時間將更可觀 10/22 00:06
6F：→ arrack:你大概沒算過實際上跑完要多久? 10/23 17:10