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

daybreakcx

suoyi  1-12
he 1-23
benjiam 发表于 2010-08-18 14:35

    1-23都不行了还指望1-12，很简单地拿那个50改改就是1-12了
比如14
1-12的话是12+7-5
而实际上7+7=14

snriyt

想了想，还是不会

jeasun

假设12a+7b+5c = w使|a|+|b|+|c|最小：

如果b，c都为正，则有12A+7B+5C = w，A = a + 1，B=b-1，C=c-1，则显然|a|+b+c>|A|+B+C=|A|+b+c-2。a|+|b|+|c|最小不成立。

如果b，c都为负数，效果也是一样的。a|+|b|+|c|最小不成立。

因此b，c只能为异号，或者一个为0或全0。

下来只有下面这三种情况：

（1）12a+7b = w；如果a，b异号，则会出现12-5=7或者5-12= -7的情况，|a|+|b|+|c|最小不成立。因此a，b同号且为正。

（2）12a+5c = w；同（1）理，|a|+|b|+|c|最小不成立。因此a，c同号且为正。

（3）12a+7b+5c = w；因为 b，c为异号。如果a！=0也会出现12-5=7或者5-12= -7或者12-7=5或者7-12= -5的情况，|a|+|b|+|c|最小不成立。因此，当b，c为异号时，a=0。



综上，要是12a+7b+5c = w满足|a|+|b|+|c|最小。只有这三种情况：

（1）c=0, a,b>0,  12a+7b = w；

（2）b=0, a,c>0,  12a+5c = w；

（3）a=0, b*c<0,  7b+5c = w；

jeasun

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. 
   
5. {
   
6. 
   
7.     int i = 0;
   
8. 
   
9.     int j = 0;
   
10. 
    
11.     int w = 116;
    
12. 
    
13. 
    
14. 
    
15.     /* (1) c=0, a,b>0,  12a+7b = w */
    
16. 
    
17.     for (i = 0; i <= w/7+1; i++) {
    
18. 
    
19.        for (j = 0; j <= w/12+1;  j++) {
    
20. 
    
21.            if ((7*i + 12*j) == w) {
    
22. 
    
23.               printf("7*%d+12*%d=%d", i, j, w);
    
24. 
    
25.               return 0;
    
26. 
    
27.            }
    
28. 
    
29.        }
    
30. 
    
31.     }
    
32. 
    
33. 
    
34. 
    
35.     /* (2) b=0, a,c>0,  12a+5c = w */
    
36. 
    
37.     for (i = 0; i <= w/5+1; i++) {
    
38. 
    
39.        for (j = 0; j <= w/12+1;  j++) {
    
40. 
    
41.            if ((5*i + 12*j) == w) {
    
42. 
    
43.               printf("5*%d+12*%d=%d", i, j, w);
    
44. 
    
45.               return 0;
    
46. 
    
47.            }
    
48. 
    
49.        }
    
50. 
    
51.     }
    
52. 
    
53. 
    
54. 
    
55.     /* (3) a=0, b*c<0,  7b+5c = w ; 2 = 7-5 */
    
56. 
    
57.            for (i = 1; ; i++) {
    
58. 
    
59.                 for (j = -1; ; j--) {
    
60.                        
    
61.                         if ((7*i + 5*j) < 0)
    
62. 
    
63.                         {
    
64. 
    
65.                                 break;
    
66. 
    
67.                         }
    
68. 
    
69.                         if (((7*i + 5*j) == w) && i*j < 0) {
    
70. 
    
71.                                 printf("7*(%d)+5*(%d)=%d", i, j, w);
    
72. 
    
73.                                 return 0;
    
74. 
    
75.                         }
    
76. 
    
77.                         else if (((5*i + 7*j) == w)&& i*j < 0)
    
78. 
    
79.                         {
    
80.                                 printf("5*(%d)+7*(%d)=%d", i, j, w);
    
81. 
    
82.                                 return 0;
    
83.                         }
    
84.                 }
    
85. 
    
86.         }
    
87. 
    
88.     puts("can't find suit a,b,c"); /* can’t reach here.*/
    
89. 
    
90.     return 1;
    
91. 
    
92. }
    

复制代码

jeasun

上面的分析是同事做的，这个问题还是考观察能力和分析能力。
程序不是重点。

chong232

回复 23# jeasun


    我很景仰你同事啊, 呵呵,学数学出身的?不错,我数学太差了,根本就想不起来转化成方程来考虑,强啊

davelv

假设12a+7b+5c = w使|a|+|b|+|c|最小：

如果b，c都为正，则有12A+7B+5C = w，A = a + 1，B=b-1，C=c-1， ...
jeasun 发表于 2010-08-18 16:54

这个不是可以顶，这个是一定要顶。

litdong

假设12a+7b+5c = w使|a|+|b|+|c|最小：

如果b，c都为正，则有12A+7B+5C = w，A = a + 1，B=b-1，C=c-1， ...
jeasun 发表于 2010-08-18 16:54

呵呵,感觉回到学生解方程时代了.还是有点难度的附加题.
还真没想到如此分析.
顶

towardWang

我觉得12，7，5这几个数字有点特殊12=7+5，估计想考的不是这个特殊的例子。就是三常整数a1,a2,a3已知。然后满足a1x+a2y+a3z=w(x,y,z为整数)，求最小|x|+|y|+|z|.

daybreakcx

回复 24# jeasun


    顶分析
    分析的结果正确但是程序的第三部分不对，因为对于b和c的范围估计错误，比如我用w=1给你算算看，结果应该是b=-2，c=3，而你的没答案，不信你试试看
    个人小建议：因为a=0化为7b+5c=w，这里可以用拓展欧几里得来算