一道笔试题!

tyz

原帖由 benjiam 于 2008-8-2 11:13 发表
....  这道题是 这么算的
5*5*5 是6个面

125* 1*1*1 是 125*6 个面

需要增加多少个面?? 125*6-6 = 744 个面

因为1刀下去可以 double.

那么对多 2^x > 744
x =10
2^0 =1 是没有意义的。
所以从1 ...

这么想的话比较容易，解释起来也很合理
应该就是9
出题人本意应该是这样的

kaios

这是怎么个切法？

blizzard213

原帖由 lin_style 于 2008-8-3 03:08 发表
明明8刀就够了

从头上切4刀，拦腰切4刀不就行了。

你以为在切拉面啊？

heavenstar_x

7刀

blizzard213

原帖由 heavenstar_x 于 2008-8-4 02:10 发表
7刀

给出过程
回帖要有质量

rainballdh

6刀

blizzard213

原帖由 rainballdh 于 2008-8-4 10:08 发表
6刀

5刀

blackuhlan

A*B*C*D 分别代表长宽高和个数，以下为切的过程，如果能简化，欢迎指出
5*5*2*1+5*5*3*1
5*5*1*3+5*5*2*1
5*2*1*3+5*3*1*3+5*2*2*1+5*3*2*1
5*1*1*6+5*1*1*3+5*2*1*3+5*2*1*2+5*1*2*1+5*2*2*1=5*1*1*9+5*2*1*6+5*2*2*1
2*1*1*9+3*1*1*9+2*2*1*6+3*2*1*6+2*2*2*1+3*2*2*1
1*1*1*18+1*1*1*9+2*1*1*9+1*2*1*12+1*2*1*6+2*2*1*6+1*2*2*2+1*2*2*1+2*2*2*1=1*1*1*27+1*1*2*27+2*2*1*9+2*2*2*1
1*1*1*27+1*1*1*54+1*1*2*18+1*2*2*2
1*1*1*81+1*1*1*36+1*1*2*4
1*1*1*117+1*1*1*8=1*1*1*125

carleo21

至少9刀

将一个块按其三维的长度记作(x, y, z), 切一刀就是对某一维进行划分，变成(x1, y, z), (x2, y,z) (若x>1, x1+x2=x).

暴力搜索的一组最优结果：

[2 1 1] min cost: 1     [1 1 1] (0)    [1 1 1] (0) [2 2 1] min cost: 2     [2 1 1] (1)    [2 1 1] (1) [2 2 2] min cost: 3     [2 2 1] (2)    [2 2 1] (2) [3 1 1] min cost: 2     [1 1 1] (0)    [2 1 1] (1) [3 2 1] min cost: 3     [2 1 1] (1)    [2 2 1] (2) [3 2 2] min cost: 4     [2 2 1] (2)    [2 2 2] (3) [3 3 1] min cost: 4     [3 1 1] (2)    [3 2 1] (3) [3 3 2] min cost: 5     [3 2 1] (3)    [3 2 2] (4) [3 3 3] min cost: 6     [3 3 1] (4)    [3 3 2] (5) [4 1 1] min cost: 2     [2 1 1] (1)    [2 1 1] (1) [4 2 1] min cost: 3     [2 2 1] (2)    [2 2 1] (2) [4 2 2] min cost: 4     [2 2 2] (3)    [2 2 2] (3) [4 3 1] min cost: 4     [3 2 1] (3)    [3 2 1] (3) [4 3 2] min cost: 5     [3 2 2] (4)    [3 2 2] (4) [4 3 3] min cost: 6     [3 3 2] (5)    [3 3 2] (5) [4 4 1] min cost: 4     [4 2 1] (3)    [4 2 1] (3) [4 4 2] min cost: 5     [4 2 2] (4)    [4 2 2] (4) [4 4 3] min cost: 6     [4 3 2] (5)    [4 3 2] (5) [4 4 4] min cost: 6     [4 4 2] (5)    [4 4 2] (5) [5 1 1] min cost: 3     [1 1 1] (0)    [4 1 1] (2) [5 2 1] min cost: 4     [2 1 1] (1)    [4 2 1] (3) [5 2 2] min cost: 5     [2 2 1] (2)    [4 2 2] (4) [5 3 1] min cost: 5     [3 1 1] (2)    [4 3 1] (4) [5 3 2] min cost: 6     [3 2 1] (3)    [4 3 2] (5) [5 3 3] min cost: 7     [3 3 1] (4)    [4 3 3] (6) [5 4 1] min cost: 5     [4 1 1] (2)    [4 4 1] (4) [5 4 2] min cost: 6     [4 2 1] (3)    [4 4 2] (5) [5 4 3] min cost: 7     [4 3 1] (4)    [4 4 3] (6) [5 4 4] min cost: 7     [4 4 1] (4)    [4 4 4] (6) [5 5 1] min cost: 6     [5 1 1] (3)    [5 4 1] (5) [5 5 2] min cost: 7     [5 2 1] (4)    [5 4 2] (6) [5 5 3] min cost: 8     [5 3 1] (5)    [5 4 3] (7) [5 5 4] min cost: 8     [5 4 1] (5)    [5 4 4] (7) [5 5 5] min cost: 9     [5 5 1] (6)    [5 5 4] (8)

测试代码：

/*   file: block.c      divide a block (x y z) to blocks (1 1 1).   in fact, one division separates a block(x y z) to     (x1 y z) and (x2 y z). (x = x1 + x2, assume x > 1)   for a (n n n) block, possible sub blocks are    (1 1 1)    (2 1 1)    (2 2 1)    (2 2 2)    ...    (n 1 1)    (n 2 1)    ...    (n n n-1)    (n n n)   the total number is sigma(i(i+1)) (i=1,...,n) = n(n+1)(2n+1) / 6 */ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h> struct _Method; typedef struct _Block {   /* x, y, z: length of three dimensions */   int x;   int y;   int z;      /* min cost */   int n;      /* how we divide this block */   struct _Method *method; } Block; typedef struct _Method {   /* sub blocks, b1 '<=' b2 */   Block *b1;   Block *b2;   struct _Method *next; } Method; int max(int a, int b) {   return a >= b ? a : b; } /* let Block.x >= Block.y >= Block.z */ void legalize_Block(Block *p) {   int n;   if (p->y < p->z) {     n = p->z;     p->z = p->y;       p->y = n;   }   if (p->x < p->y) {     n = p->y;     p->y = p->x;     p->x = n;   }   if (p->y < p->z) {     n = p->z;     p->z = p->y;     p->y = n;   } } Block* new_Block(int x, int y, int z) {   Block *p = (Block *)malloc(sizeof(Block));   if (p) {     p->x = x;     p->y = y;     p->z = z;     legalize_Block(p);   }   return p; } /* let Method.b1 '<=' Method.b2 */ void legalize_Method(Method *m) {   Block *p;   if (m == NULL)     return;   if (m->b1 == NULL || m->b2 == NULL)     return;   if (cmp_block(m->b1, m->b2) > 0) {     p = m->b2;     m->b2 = m->b1;     m->b1 = p;   } } /* compare two blocks, each Block should be legalized    (so x >= y >= z) */ int cmp_block(Block *b1, Block *b2) {   if (b1 == NULL || b2 == NULL)     return 0;   if (b1->x != b2->x)     return b1->x - b2->x;   if (b1->y != b2->y)     return b1->y - b2->y;   return b1->z - b2->z; } /* try to insert a method to the list.    Block.x >= Block.y >= Block.z    method list was sorted ascendingly    return: 0 for success, non-zero for exists item */ int try_insert_method(Method **header, Method *m) {   Method *p;   int n;   if (m == NULL)     return -1;   p = *header;   if (*header == NULL) {     *header = m;     return 0;   }      n = cmp_block(p->b1, m->b1);   if (n == 0)     return 1;   else if (n > 0) {     m->next = p;     *header = m;     return 0;   }   while (p->next != NULL) {     n = cmp_block(p->next->b1, m->b1);     if (n == 0 ) {       return 1;     } else if (n > 0) {       m->next = p->next;       p->next = m;       return 0;     }     p = p->next;   }   m->next = p->next;   p->next = m;   return 0; } /* get all possible method to divide a block */ Method* getMethods(Block *b) {   Method *m;   Block *p;   int x1, x2;   int end;   int j;   if (b == NULL)     return;   if (b->x <= 1 && b->y <= 1 && b->z <= 1)     return NULL;      b->method = NULL;   for (j = 0; j < 3; j++) {     int d0, d1, d2;     switch (j) {     case 0:       if (b->x <= 1)         continue;       d0 = b->x;       d1 = b->y;       d2 = b->z;       break;     case 1:       if (b->y <= 1 || b->y == b->x)         continue;       d0 = b->y;       d1 = b->x;       d2 = b->z;       break;     case 2:       if (b->z <= 1 || b->z == b->y)         continue;       d0 = b->z;       d1 = b->x;       d2 = b->y;       break;     default:       continue;       break;     }     end = d0 / 2;     for (x1 = 1; x1 <= end; x1++) {       m = (Method *)malloc(sizeof(Method));       if (m == NULL) {         fprintf(stderr, "failed to allocate memory\n");         exit(1);       }       m->next = NULL;              p = new_Block(x1, d1, d2);       if (p == NULL) {         fprintf(stderr, "failed to allocate memory\n");         exit(1);       }       m->b1 = p;              p = new_Block(d0-x1, d1, d2);       if (p == NULL) {         fprintf(stderr, "failed to allocate memory\n");         exit(1);       }       m->b2 = p;       legalize_Method(m);       if (try_insert_method(&(b->method), m)) {         free(m->b1);         free(m->b2);         free(m);       }     }   } } /* get the index to access a Block in the global array */ int get_data_index(int x, int y, int z) {   int index;   if ((x < 1 || y < 1 || z < 1)) {     return -1;   }      if (x == 1)     return 0;   /* we need index, so decrease number */   index = (x-1)*x*(2*x-1)/6 + y*(y-1)/2 + z - 1;   return index; } /* find one of the best method to divide a Block */ void getBestMethod(Block *b, Block *block_data, int size) {   Method *m, *list;   Block *p;   Block *b1, *b2;   int n;   if (b == NULL) {     fprintf(stderr, "NULL block point, line %d in func %s\n",             __LINE__, __FUNCTION__);     exit(1);   }   if (block_data == NULL) {     fprintf(stderr, "NULL block data point, line %d in func %s\n",             __LINE__, __FUNCTION__);     exit(1);   }   if (b->x <= 1 && b->y <= 1 && b->z <= 1) {     b->n = 0;     b->method = NULL;     return;   }   getMethods(b);   list = b->method;   m = list;   b->method = (Method *)malloc(sizeof(Method));   if (b->method == NULL) {     fprintf(stderr, "failed to allocate memory!\n");     exit(1);   }   b->method->b1 = NULL;   b->method->b2 = NULL;   while (m != NULL) {     n = get_data_index(m->b1->x, m->b1->y, m->b1->z);     if (n < 0) {       fprintf(stderr, "Invalid block, can't get data index\n");       exit(1);     }     b1 = block_data + n;     if (b1->n == 0 && n > 0) {       fprintf(stderr, "Un-initialized Block data\n");       exit(1);     }     n = get_data_index(m->b2->x, m->b2->y, m->b2->z);     if (n < 0) {       fprintf(stderr, "Invalid block, can't get data index\n");       exit(1);     }     b2 = block_data + n;         if (b2->n == 0 && n > 0) {       fprintf(stderr, "Un-initialized Block data\n");       exit(1);     }     if (b->method->b1 == NULL ||         max(b->method->b1->n ,b->method->b2->n) > max(b1->n ,b2->n) ) {       b->method->b1 = b1;       b->method->b2 = b2;     }     m = m->next;   }   /* free method list */   while (list != NULL) {     m = list;     list = list->next;     free(m->b1);     free(m->b2);     free(m);   }   /* sanity check */   if (b->method->b1 == NULL || b->method->b2 == NULL) {     fprintf(stderr, "failed to get best method\n");     exit(1);   }   /* we need one division to separate block to b1 and b2 */   b->n = 1 + max(b->method->b1->n, b->method->b2->n); } int main(int argc, char **argv) {   int x, y, z;   int size;   Block *data, *b;   int i, j, k;   int index;   if (argc < 4) {     fprintf(stderr, "Usage: %s n1 n2 n3\n");     exit(1);   }   x = atoi(argv[1]);   y = atoi(argv[2]);   z = atoi(argv[3]);   if (x < 1 || y < 1 || z < 1) {     fprintf(stderr, "Usage: %s n1 n2 n3\n\n\t n1, n2 and n3 should be"             "positive integer\n");     exit(1);   }   if (x < 1 || y < 1 || z < 1) {     fprintf(stderr, "invalid dimension length\n");     exit(1);   }   /* sort x, y, z */   if (y < z) {     i = z;     z = y;     y = i;   }   if (x < y) {     i = y;     y = x;     x = i;   }   if (y < z) {     i = z;     z = y;     y = i;   }      size = get_data_index(x, y, z) + 1;   data = (Block *)malloc(size * sizeof(Block));   if (data == NULL) {     fprintf(stderr, "failed to allocate memory\n");     exit(1);   }      memset(data, 0, size * sizeof(Block));   for (i = 1; i <= x; i++) {     for (j = 1; j <= i; j++) {       for (k = 1; k <= j; k++) {         index = get_data_index(i, j, k);         b = data + index;         b->x = i;         b->y = j;         b->z = k;         legalize_Block(b);         if (b->n != 0) {           fprintf(stderr, "Index conflict: %d\n", index);           exit(1);         }         getBestMethod(b, data, size);         if (index > 0)         fprintf(stderr, "[%d %d %d] min cost: %d\t[%d %d %d] (%d)"                 "    [%d %d %d] (%d)\n",                 i, j, k, b->n,                 b->method->b1->x, b->method->b1->y,                 b->method->b1->z, b->method->b1->n,                 b->method->b2->x, b->method->b2->y,                 b->method->b2->z, b->method->b2->n                 );         if (i >= x && j >= y && k >= z) {           return 0;         }       }     }   }   return 0; }

lqseu

好强
下下来，学习下