考考大家一道某著名IT的面试题

叼着馒头看电视

有没有做出来，把代码贴出来浏览一下。。。我是新手

卐伪装卐

看不懂，不知何意呀

shymn

回复 61# 叼着馒头看电视


失望了，
这是我在47楼发的，希望你可以帮我检查一下，告诉我对不对

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main(int argc, char **argv)
   
5. {
   
6.         int        w, q, i, k;
   
7. 
   
8.         if (argc < 2) {
   
9.                 fprintf(stderr, "Usage: %s w ...", argv[0]);
   
10.                 exit(0);
    
11.         }
    
12. 
    
13.         for (i = 1; i < argc; i++) {
    
14.                 printf("%s: ", argv[i]);
    
15.                 w = atoi(argv[i]);
    
16. 
    
17.                 for (k = 0; w > 0 || (w%7 && w%5); k++)
    
18.                         w -= 12;
    
19. 
    
20.                 if (w == 0)
    
21.                         printf("(12)*%d\n", k);
    
22.                 else if (w%7 == 0) {
    
23.                         q = w/7 >= 0 ? w/7 : -w/7;
    
24.                         if (q > k)
    
25.                                 printf("(-7)*%d + (5)*%d\n", q-k, k);
    
26.                         else if (q == k)
    
27.                                 printf("(5)*%d\n", q);
    
28.                         else
    
29.                                 printf("(5)*%d + (12)*%d\n", q, k-q);
    
30.                 }
    
31.                 else if (w%5 == 0) {
    
32.                         q = w/5 >= 0 ? w/5 : -w/5;
    
33.                         if (q > k)
    
34.                                 printf("(-5)*%d + (7)*%d\n", q-k, k);
    
35.                         else if (q == k)
    
36.                                 printf("(7)*%d\n", q);
    
37.                         else
    
38.                                 printf("(7)*%d + (12)*%d\n", q, k-q);
    
39.                 }
    
40.         }
    
41. }

复制代码

chong232

回复 63# shymn


    在W＞0的情况下, 算法没问题,所以应该对负数判断一下,结果全部取反

chong232

回复 63# shymn


    就算法来说,已经很不错了

shymn

回复 65# chong232


    谢谢，总算有人回我了，那个问题里面w是正数，所以我就没考虑w为负数的情况了

chong232

回复 66# shymn


    呵呵,我是针对你的公式说的

shymn

回复 67# chong232


    那样的话，如果w一开始就是负数，应该是要迭代地加上12，再把后面的负号变正号，正变负对吗？

yj_yulin

一个整数规划问题,很直观啊.用lindo解决.

scorer1120

我给个解法：
6种木块（12,-12,+7,-7,+5,-5），数量任意，假设背包大小W＝N
为了用最小的块数填充，于是从 ...
feuerchop 发表于 2010-08-18 20:09

    我也是用这种取余数的方法，我是用PYTHON写的，没用循环，速度很快。   
思路是：
            12a+7b+5c=w
             先取12的余数，或者先取7的余数，或者先取5的余数，这样有6种[a,b,c]的list
             然后从list中取出其中|a|+|b|+|c|最小的那个list就是所要求的。