#include #include /* program to generate all cutting-sticks problems for a given n */ #ifdef DEBUG #define DEBUG_P1(S,P1) printf(S, P1) #define DEBUG_P4(S,P1,P2,P3,P4) printf(S, P1, P2, P3, P4) #else #define DEBUG_P1(S,P1) #define DEBUG_P4(S,P1,P2,P3,P4) #endif #define K_ALL 1 #define K_LIM 2 #define K_PART 3 #define MAX_K 100 #define MAX_N 50 int option_p_a_sol = 0; int g_n; int g_a[MAX_K]; int g_lb; int g_k; void (*g_doit)(); void fill_sol(int i, int tl, int h) { DEBUG_P4("%*s fill_sol tl: %d h: %d\n", i, "", tl, h); if (i == g_k - 1) { if (tl <= h && tl >= g_lb) { g_a[i] = tl; (*g_doit)(); } } else if (tl >= g_lb * (g_k - i)) { int t; for (t = h; t >= g_lb; t--) { g_a[i] = t; fill_sol(i + 1, tl - t, t); } } } void gen_all_l(int k, int kind, void (*doit)()) { DEBUG_P1("gen_all_k %d\n", k); if (k > MAX_K) { printf("nr sticks > %d\n", MAX_K); return; } g_k = k; g_doit = doit; switch(kind) { case K_PART : g_lb = 1; fill_sol(0, g_n * (g_n + 1)/2, g_n * (g_n + 1)/2); break; case K_ALL : g_lb = g_n; fill_sol(0, g_n * (g_n + 1)/2, g_n * (g_n + 1)/2); break; case K_LIM : g_lb = g_n + 1; fill_sol(0, g_n * (g_n + 1)/2, 2 * g_n - 2); break; } } void gen_all(int n, int kind, void (*doit)()) { int k; int max_k = (kind == K_PART) ? n * (n + 1) / 2 : (n+1)/2; g_n = n; for (k = 1; k <= max_k; k++) gen_all_l(k, kind, doit); } void print_sol() { int i; for (i = 0; i < g_k; i++) printf("%d ", g_a[i]); printf("\n"); } int total = 0; void count_sol() { total ++; } int g_a_eq[MAX_K]; char g_c[MAX_K][MAX_N + 1]; int nr_sol; int low_nr_sol; void select(int up, int low) { /***** printf("%*sselect(%d, %d) : ", g_n - up + low, "", up, low); { int i; for (i = 0; i < g_k; i++) printf("%d ", g_a[i]); printf("\n"); } *****/ if (up < low) { nr_sol++; if (option_p_a_sol) { int i, j; printf(" "); for (i = 0; i < g_k; i++) { int first = 1; for (j = g_n; j > 0; j--) if (g_c[i][j] == 1) { printf("%s%d", first ? " " : "+", j); first = 0; } } printf("\n"); } } else { int i, nlow = 0, p; for (i = 0; i < g_k; i++) if (g_a[i] == low) if (++nlow > 1) return; else p = i; if (nlow == 1) { g_c[p][low] = 1; g_a[p] -= low; select(up, low + 1); g_a[p] += low; g_c[p][low] = 0; } else for (i = 0; i < g_k; i++) if ( ( g_a[i] == up || g_a[i] >= up + low) && g_a_eq[i] == 0) { int eq = g_a_eq[i+1]; g_a_eq[i+1] = 0; g_c[i][up] = 1; g_a[i] -= up; select(up - 1, low); g_a[i] += up; g_c[i][up] = 0; g_a_eq[i+1] = eq; } } } void test_sol() { int i, j, nr_perm; for (i = 0; i < g_k; i++) for (j = 0; j < g_n; j++) g_c[i][j] = 0; nr_perm = 1; j = 1; g_a_eq[0] = 0; for (i = 1; i < g_k; i++) if (g_a[i - 1] == g_a[i]) { nr_perm *= ++j; g_a_eq[i] = 1; } else { j = 1; g_a_eq[i] = 0; } nr_sol = 0; for (i = 0; i < g_k; i++) printf("%d ", g_a[i]); if (option_p_a_sol) printf("\n"); select(g_n, 1); if (low_nr_sol == 0 || nr_perm * nr_sol < low_nr_sol) low_nr_sol = nr_perm * nr_sol; printf(" sol: %d * %d = %d\n", nr_perm, nr_sol, nr_perm * nr_sol); } void main(int argc, char *argv[]) { int option_count = 0; int option_find = 0; int kind = K_LIM; int i; if (argc == 1) { printf("Usage: %s [-all | -part] [-count | -find [-print]] \n", argv[0]); printf("\n"); printf("The program tries all sets of sticks:\n"); printf(" -all : larger equal n.\n"); printf(" -part : with no limitation\n"); printf(" : between n and 2n-1\n"); printf("\n"); printf(" -count : count possible sets of sticks\n"); printf(" -find : find solutions for each set of sticks\n"); printf(" -print : also print the solutions\n"); printf(" : just print sets of sticks\n"); printf("\n"); } option_p_a_sol = 0; for (i = 1; i < argc; i++) { char *arg =argv[i]; if (!strcmp(arg, "-all")) kind = K_ALL; else if (!strcmp(arg, "-part")) kind = K_PART; else if (!strcmp(arg, "-count")) option_count = 1; else if (!strcmp(arg, "-find")) option_find = 1; else if (!strcmp(arg, "-print")) option_p_a_sol = 1; else if (atoi(arg) > 0) { total = 0; low_nr_sol = 0; gen_all(atoi(arg), kind, option_find ? test_sol : option_count ? count_sol : print_sol); if (option_count || option_find) printf("number solutions: %d\n", total); if (option_find) printf("low nr solution per set sticks: %d\n", low_nr_sol); } else printf("Error: ignored: `%s'\n", arg); } }