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

4tar

修改了一下陈述使其更严密些，同时添加了两个原始搜索中漏掉的组合（shy，原本的穷举算法漏掉了一些边际条件）。当然，不影响思路本身。

容易证明：如果W的一个满足条件的解中含有12，则向该解中添加一个12可以构成W+12的一个满足条件的解。
所以只需要找到一个连续的区间[n,n+11]，使得落在其中的每一个W都有一个含12的解，则之后所有的正值均可通过向该区间内某个正值的解中添加若干个12来获得。
同样也容易证明：当W足够大，12在其解中必然出现。（此证明对解决问题不是必要的，只不过稍微增添一点搜索的信心罢了。直觉可以知道这个12-区间将很早出现）。
简单的穷举搜索即可知[43,54]是我们需要的最早出现的12-区间，当然你也可以使用一些技巧来加快搜索（可参见之前帖子里已有的一些分析），但对于此问题来说，由于仅存在少量的数字（12/7/5），且该少量数字存在一定的特殊性（12=7+5），使得这些技巧显得有些无谓。
这个思路对于一般的数字组合也是适用的，无非是搜寻的区间长度和添加的数字组合需要根据可选的数字组合而变化。具体如何确定长度及相关的添加集合实际上是一个丢番都方程问题，可以查看相关资料，不赘述。

以下是lz问题的搜索结果：
W=1, 5, ( -7 -7 5 5 5 )
W=2, 2, ( 7 -5 )
W=3, 3, ( -7 5 5 )
W=4, 4, ( 7 7 -5 -5 )
W=5, 1, ( 5 )
W=6, 6, ( -7 -7 5 5 5 5 ) or ( 7 7 7 -5 -5 -5 )
W=7, 1, ( 7 )
W=8, 4, ( -7 5 5 5 )
W=9, 3, ( 7 7 -5 )
W=10, 2, ( 5 5 )
W=11, 5, ( 7 7 7 -5 -5 )
W=12, 1, ( 12 )
W=13, 5, ( -7 5 5 5 5 )
W=14, 2, ( 7 7 )
W=15, 3, ( 5 5 5 )
W=16, 4, ( 7 7 7 -5 )
W=17, 2, ( 12 5 )
W=18, 6, ( -7 5 5 5 5 5 ) or ( 7 7 7 7 -5 -5 )
W=19, 2, ( 12 7 )
W=20, 4, ( 5 5 5 5 )
W=21, 3, ( 7 7 7 )
W=22, 3, ( 12 5 5 )
W=23, 5, ( 7 7 7 7 -5 )
W=24, 2, ( 12 12 )
W=25, 5, ( 5 5 5 5 5 )
W=26, 3, ( 12 7 7 )
W=27, 4, ( 12 5 5 5 )
W=28, 4, ( 7 7 7 7 )
W=29, 3, ( 12 12 5 )
W=30, 6, ( 7 7 7 7 7 -5 ) or ( 5 5 5 5 5 5 )
W=31, 3, ( 12 12 7 )
W=32, 5, ( 12 5 5 5 5 )
W=33, 4, ( 12 7 7 7 )
W=34, 4, ( 12 12 5 5 )
W=35, 5, ( 7 7 7 7 7 )
W=36, 3, ( 12 12 12 )
W=37, 6, ( 12 5 5 5 5 5 )
W=38, 4, ( 12 12 7 7 )
W=39, 5, ( 12 12 5 5 5 )
W=40, 5, ( 12 7 7 7 7 )
W=41, 4, ( 12 12 12 5 )
W=42, 6, ( 7 7 7 7 7 7 )
W=43, 4, ( 12 12 12 7 )
W=44, 6, ( 12 12 5 5 5 5 )
W=45, 5, ( 12 12 7 7 7 )
W=46, 5, ( 12 12 12 5 5 )
W=47, 6, ( 12 7 7 7 7 7 )
W=48, 4, ( 12 12 12 12 )
W=49, 7, ( 7 7 7 7 7 7 7 ) or ( 12 12 5 5 5 5 5 )
W=50, 5, ( 12 12 12 7 7 )
W=51, 6, ( 12 12 12 5 5 5 )
W=52, 6, ( 12 12 7 7 7 7 )
W=53, 5, ( 12 12 12 12 5 )
W=54, 7, ( 12 7 7 7 7 7 7 )

4tar

回复 50# kamingli


题意没理解正确。

sleepcats

回复 13# chong232


    这个也不行，50=5*10,得用10个；50=12*4+7-5，只用6个。

sleepcats

这句看不懂，只明白了|a|+b+c>|A|+b+c-2，但为什么可以导出  |a|+|b|+|c|最小不成立？？
ssa852741 发表于 2010-08-18 22:03

    因为|A|+|B|+|C|比他小。

sealdad

现算 +5,-5,+2,-2的情况，把这个算清楚了再算＋12，－12，＋7，－7，＋5，－5。

davidbeckham921

太狠了！学习！~~

daybreakcx

囧，这个帖子都拉到这种程度了……{:3_190:}

jeasun

1. #include <stdlib.h>
   
2. #include <stdio.h>
   
3. int main(int argc, char *agrv[]){
   
4. 
   
5.     int x, y, w;
   
6.     int x1,x2;
   
7.     int y1, y2;
   
8. 
   
9.     if (2 == argc){
   
10.         w = atoi(agrv[1]);
    
11.     }
    
12. 
    
13.     if (w <= 0){
    
14.         w = 7*7001 - 5*2;
    
15.     }
    
16.     //12a+7b=w & 12a+5c=w => y=a+b, x=a, 5x+7y=w & 7x+5y=w
    
17.     //y >= x
    
18.     for (y = 1, y2 = y1 = w/5 + 1; y < y1 && y < y2; y++){
    
19.         x = (w - 7*y)/5;
    
20.         if (0 <= x && x <= y && w == 5*x + 7*y){
    
21.             x1 = x;
    
22.             y1 = y;
    
23.         }
    
24.         x = (w - 5*y)/7;
    
25.         if (0 <= x && x <= y && w == 7*x + 5*y){
    
26.             x2 = x;
    
27.             y2 = y;
    
28.         }
    
29.     }
    
30.    
    
31.     y = w/5 + 1;
    
32.     if (y1 < y && y1 <= y2){        
    
33.         printf("12 * (%d) + 7 * (%d) + 5 * (%d) = %d\n", x1, y1-x1, 0, w);
    
34.         printf("Sum = %d", y1);
    
35.         return 0;
    
36.     }
    
37.     else if (y2 < y && y2 < y1){
    
38.         printf("12 * (%d) + 7 * (%d) + 5 * (%d) = %d\n", x2, 0, y2-x2, w);
    
39.         printf("Sum = %d", y2);
    
40.         return 0;
    
41.     }
    
42.   
    
43. 
    
44.     //5a-7b=w & 7a-5b=w => y=a+b, b=x, 5y-12x=w & 7y-12x=w
    
45.     for (y = w/7, y1 = y2 = 0; 0 == y1 && 0 == y2; y++){
    
46.         x = (7*y - w) / 12;
    
47.         if (w == 7*y - 12*x){
    
48.             x1 = x;
    
49.             y1 = y;
    
50.         }
    
51. 
    
52.         x = (5*y - w) / 12;
    
53.         if (w == 5*y - 12*x){
    
54.             x2 = x;
    
55.             y2 = y;
    
56.         }
    
57.     }
    
58. 
    
59.     if (0 != y1){
    
60.         printf("12 * (%d) + 7 * (%d) - 5 * (%d) = %d\n", 0, y1-x1, x1, w);
    
61.         printf("Sum = %d", y1);
    
62.     }
    
63. 
    
64.     if (0 != y2){
    
65.         printf("12 * (%d) - 7 * (%d) + 5 * (%d) = %d\n", 0, x2, y2-x2, w);
    
66.         printf("Sum = %d", y2);
    
67.     }
    
68. 
    
69.     return 0;
    
70. }

复制代码

shymn

不是吧，难道我第一次发的贴就这样给忽视了吗，都没人给我一个肯定或者否定的答案，看来我只有一直潜水的命了

chong232

回复 51# 4tar


    这个思路不错啊,,有一定通用性!

   给定空间W, 木块±a， ±b， ±c

   则找出连续空间: （N， N＋LCM（a，b，c） － 1）；

   则对于任意空间X，W都可以通过扩张n＊man（a，b，c）到X