#include #include #include int min(int i, int j) { return i < j ? i : j; } int max(int i, int j) { return i > j ? i : j; } const int max_n = 20; class Array { public: Array() : _size(-1), _data(0) {} void init(int size) { _size = size; _data = new int[size]; for (int i = 0; i < _size; i++) _data[i] = -1; } Array& operator=(const Array& rhs) { _size = rhs._size; _data = rhs._data; return *this; } const int operator[](int i) const { if (i < 0 || i >= _size) return -1; return _data[i]; } bool assign_min(int i, int source) { if (i < 0 || i >= _size) { printf("assign [%d] with size = %d\n", i, _size); exit(0); } if (_data[i] == -1 || source < _data[i]) { _data[i] = source; return true; } return false; } int size() { return _size; } private: int _size; int *_data; }; bool assign_min(int &target, int source) { if (target == -1 || source < target) { target = source; return true; } return false; } int max_groups(int x, int y) { return (x * y + 1)/2; } int main(int argc, char *argv[]) { Array smallest[max_n][max_n]; smallest[1][1].init(2); smallest[1][1].assign_min(1, 1); printf("Calculating S for P_n as S(n,1,g) where g is number of groups:\n\n"); for (int n = 2; n < max_n; n++) { int max_g = max_groups(n, 1); Array smallestPn; smallestPn.init(max_g+1); smallest[n][1] = smallestPn; // Extending solution at the end for (int g = 1; g <= max_g && smallest[n-1][1][g] != -1; g++) smallestPn.assign_min(g, smallest[n-1][1][g] + 1); // Combining two smaller solutions with two connecting positions in the middle for (int n1 = 1; n1 < n-2; n1++) { int n2 = n - n1 - 2; for (int g1 = 1; g1 <= n1 && smallest[n1][1][g1] != -1; g1++) for (int g2 = 1; g1 + g2 <= max_g && g2 <= n2 && smallest[n2][1][g2] != -1; g2++) { int moves1 = smallest[n1][1][g1] - g1; int moves2 = smallest[n2][1][g2] - g2; int moves = moves1 > moves2 ? moves1 : moves2; int val = g1 + g2 + moves + 1; int g = g1 + g2; if (smallestPn.assign_min(g, val)) printf("S(1,%d,%d) = %d from S(1,%d,%d) = %d and S(1,%d,%d) = %d and two connection\n", n, g1+g2, smallestPn[g], n1, g1, smallest[n1][1][g1], n2, g2, smallest[n2][1][g2]); } } // Combining two smaller solutions with one connecting position in the middle for (int n1 = 1; n1 < n-1; n1++) { int n2 = n - n1 - 1; for (int g1 = 1; g1 <= n1 && smallest[n1][1][g1] != -1; g1++) for (int g2 = 1; g1 + g2 <= max_g && g2 <= n2 && smallest[n2][1][g2] != -1; g2++) { int moves1 = smallest[n1][1][g1] - g1; int moves2 = smallest[n2][1][g2] - g2; int moves = moves1 > moves2 ? moves1 : moves2; int val = g1 + g2 + moves + 1; int g = g1 + g2; if (smallestPn.assign_min(g, val)) printf("S(1,%d,%d) = %d from S(1,%d,%d) = %d and S(1,%d,%d) = %d and one connection\n", n, g, smallestPn[g], n1, g1, smallest[n1][1][g1], n2, g2, smallest[n2][1][g2]); } } // Print for solution at the end for (int g = 1; g <= max_g && smallest[n-1][1][g] != -1; g++) { if (smallest[n][1][g] == smallest[n-1][1][g] + 1) printf("S(1,%d,%d) = %d from S(1,%d,%d) = %d and one additions\n", n, g, smallest[n][1][g], n-1, g, smallest[n-1][1][g]); } } // Filling S(1,n,1) = n for (int n = 2; n < max_n; n++) { Array smallestPn; smallestPn.init(2); smallest[1][n] = smallestPn; smallestPn.assign_min(1, n); } printf("\n\nResults by number of groups, preceded by 2*sqrt(n) - 2 + 4log(n):\n\n"); for (int n = 2; n < max_n; n++) { printf("%2d: %10lf", n, 2*sqrt(n) - 2 + log(n)/log(4)); for (int g = 1; g <= n && smallest[n][1][g] != -1; g++) printf("%5d", smallest[n][1][g]); printf("\n"); } printf("\n\nResults as sequence:\n\n"); for (int n = 1; n < max_n; n++) { int min = -1; for (int g = 1; g <= n && g < smallest[n][1].size() && smallest[n][1][g] != -1; g++) assign_min(min, smallest[n][1][g]); printf("%d, ", min); } printf("\n\nCalculating S for P_nxm as S(n,m,g) where g is number of groups:\n\n"); for (int nm = 4; nm < 2* max_n; nm++) { for (int n = 2, m = nm - n; m >= 2; n++, m--) if (m < max_n && n < max_n) { int max_g = max_groups(n, m); Array smallestPnm; smallestPnm.init(max_g+1); smallest[n][m] = smallestPnm; // extra column in the middle for (int n1 = 1, n2 = n - n1 - 1; n2 >= 1; n1++, n2--) for (int g1 = 1; smallest[n1][m][g1] != -1 || smallest[m][n1][g1] != -1; g1++) for (int g2 = 1; smallest[n2][m][g2] != -1 || smallest[m][n2][g2] != -1; g2++) { int moves1; int reduction1 = 0; bool rotated1 = false; if ( smallest[n1][m][g1] == -1 || (smallest[m][n1][g1] != -1 && smallest[m][n1][g1] <= smallest[n1][m][g1])) { moves1 = smallest[m][n1][g1] - g1; reduction1 = n1 > 1 || g1 == 1; rotated1 = true; } else { moves1 = smallest[n1][m][g1]; if (n1 > 1 && moves1 == smallest[n1-1][m][g1] + m) reduction1 = 1; } int moves2; int reduction2 = 0; bool rotated2 = false; if ( smallest[n2][m][g2] == -1 || (smallest[m][n2][g2] != -1 && smallest[m][n2][g2] <= smallest[n2][m][g2])) { moves2 = smallest[m][n2][g2] - g2; reduction2 = n2 > 1 || g2 == 1; rotated2 = true; } else { moves2 = smallest[n2][m][g2]; if (n2 > 1 && moves2 == smallest[n2-1][m][g2] + m) reduction2 = 1; } if (moves1 > moves2 && reduction1) reduction2 = 0; else if (moves2 > moves1 && reduction2) reduction1 = 0; else reduction1 = reduction2 = 0; int moves = (moves1 - reduction1) > (moves2 - reduction2) ? (moves1 - reduction1) : (moves2 - reduction2); int val = g1 + g2 + moves + m; int g = g1 + g2; if (smallestPnm.assign_min(g, val)) { printf("S(%d,%d,%d) = %d = %d + %d + %d + %d from ", n, m, g, smallestPnm[g], g1, g2, moves, m); if (rotated1) printf("rotated S(%d,%d,%d) = %d", m, n1, g1, smallest[m][n1][g1]); else printf("S(%d,%d,%d) = %d", n1, m, g1, smallest[n1][m][g1]); printf(" = %d + %d %sand ", g1, moves1, reduction1 ? "(with one reduced) " : ""); if (rotated2) printf("rotated S(%d,%d,%d) = %d", m, n2, g2, smallest[m][n2][g2]); else printf("S(%d,%d,%d) = %d", n2, m, g2, smallest[n2][m][g2]); printf(" = %d + %d %sand column in the middle\n", g2, moves2, reduction2 ? "(with one reduced) " : ""); } } // Extra column at the side for (int g = 1; smallest[n-1][m][g] != -1; g++) if (smallestPnm.assign_min(g, smallest[n-1][m][g] + m)) printf("S(%d,%d,%d) = %d from S(%d,%d,%d) = %d and extra column at the side\n", n, m, g, smallestPnm[g], n-1, m, g, smallest[n-1][m][g]); // Extra column at the side (with rotated) for (int g = 1; smallest[m][n-1][g] != -1; g++) if (smallestPnm.assign_min(g, smallest[m][n-1][g] + m)) printf("S(%d,%d,%d) = %d from rotated S(%d,%d,%d) = %d and extra column at the side\n", n, m, g, smallestPnm[g], m, n-1, g, smallest[m][n-1][g]); } } printf("\n\nResults by number of groups, preceded by 2*sqrt(n) - 2 + 4log(n):\n\n"); for (int n = 1; n < max_n; n++) { for (int m = 1; m < max_n; m++) { printf("%2d,%2d: %10lf", n, m, 2*sqrt(n*m) - 2 + log(n*m)/log(4)); for (int g = 1; smallest[n][m][g] != -1; g++) printf("%5d", smallest[n][m][g]); printf("\n"); } } printf("\n\nTable with results of minimum of S(n,m,g) over g with minimum value of g\n\n |"); for (int n = 1; n < max_n; n++) printf("%7d", n); printf("\n--+"); for (int n = 1; n < max_n; n++) printf("-------"); printf("\n"); for (int m = 1; m < max_n; m++) { printf("%2d|", m); for (int n = 1; n < max_n; n++) { int max_g = max_groups(n, m); int min = -1; int min_g = 0; for (int g = 1; g <= max_g; g++) if (smallest[n][m][g] != -1) if (assign_min(min, smallest[n][m][g])) min_g = g; printf("%4d,%2d", min, min_g); } printf("\n"); } printf("\n\n |"); for (int n = 1; n < max_n; n++) printf("%3d", n); printf("\n--+"); for (int n = 1; n < max_n; n++) printf("---", n); printf("\n"); for (int m = 1; m < max_n; m++) { printf("%2d|", m); for (int n = 1; n < max_n; n++) { int max_g = max_groups(n, m); int min = -1; int min_g = 0; for (int g = 1; g <= max_g; g++) if (smallest[n][m][g] != -1) if (assign_min(min, smallest[n][m][g])) min_g = g; printf("%3d", min); } printf("\n"); } printf("\n\n |"); for (int n = 1; n < max_n; n++) printf("%3d", n); printf("\n--+"); for (int n = 1; n < max_n; n++) printf("---", n); printf("\n"); for (int m = 1; m < max_n; m++) { printf("%2d|", m); for (int n = 1; n < max_n; n++) { int max_g = max_groups(n, m); int min = -1; int min_g = 0; for (int g = 1; g <= max_g; g++) if (smallest[n][m][g] != -1) if (assign_min(min, smallest[n][m][g])) min_g = g; printf("%3d", min_g); } printf("\n"); } printf("\n\nTable with results of minimum of S(n,m,g) and S(m,n,g) over g with minimum and maximum value of g\n\n |"); for (int n = 1; n < max_n; n++) printf("%10d ", n); printf("\n--+"); for (int n = 1; n < max_n; n++) printf("-----------", n); printf("\n"); for (int m = 1; m < max_n; m++) { printf("%2d|", m); for (int n = 1; n < max_n; n++) { int max_g = max_groups(n, m); int min = -1; int min_g = 0; int min_gm = 0; char x = ' '; for (int g = 1; g <= max_g; g++) { if (smallest[m][n][g] != -1) { if (assign_min(min, smallest[m][n][g])) min_g = min_gm = g, x = '#'; else if (min == smallest[m][n][g] && x == '#') min_gm = g; } if (smallest[n][m][g] != -1) { if (assign_min(min, smallest[n][m][g])) min_g = min_gm = g, x = ' '; else if (min == smallest[n][m][g] && x == ' ') min_gm = g; } } printf("%4d,%2d-%2d%c", min, min_g, min_gm, x); } printf("\n"); } printf("\n"); return 0; }