前几天在一家公司面试，有几道算法题，请大家解答：

Question

前几天在一家公司面试，有几道算法题，请大家解答：
1，用箱子装盘子，若用户想要1~1000之内的任意盘子数，都不用打开箱子，直接用几个装好盘子的箱子组合给用户就行了，问最少需要几个箱子？2，怎样把4枚棋子放在4*4的棋盘上，能使任一横线，竖线和斜线上都没有1枚以上的棋子，共有几种放法？3，有5封信，放到5个信封里，如果全部放错共有几种放法？（一个信封里只能放一封信，且必须有信）

Answer 1

第一个，就合人民币一样，1，2，2，5，10，20，20，50，100，200，200，500
第二个也是排列组合题。4x3x2-2。
第三个好象还是，4x3x2

Answer 2

2题，对称的也算有2种。
3题，96种. S1 = 0; S2 = 1; S3 = 4; S4 = 18; S5 = 96;

Answer 3

第二题:
第一个棋子放下去有四种可能，第二个有三种可能，第三个有两种可能，
最后一个没得选了。扣除两种对角线情况：4*3*2-2
第三题：（设5个信封为ABCDE）
第一个信封（设A）放错有四种可能，设其放入B，
第二个信封（非B，设为C）放错有三种可能，设其放入D,
第三个信封（非B，非D，只能E）放错有二可能，
最后剩BD没得选了，所以为4*3*2
还有一种方法（递归）:
1。如果只有2个信封，放错法有1种。
2。设i个信封有N种放错法，则i+1个信封会有i*N种放错法。

Answer 4

楼上,你第三题的逻辑是错误的,
"第二个信封（非B，设为C）放错有三种可能，设其放入D,"
不能假设"非B，设为C",应该把信封固定住

Answer 5

第三题详细算法如下:
令f(n)表示"有n封信，放到n个信封里，全部放错"的放法总数.
令c(x,y)表示排列组合,即c(5,2) = 5*4/2*1,c(4,2) = 4*2/2*1;
则
  f(1) = 0;
  f(2) = 2! - 1 - c(2,1)*f(1)  = 1;
  f(3) = 3! - 1 - c(3,2)*f(1) - c(3,1)*f(2)   = 2;
  f(4) = 4! - 1 - c(4,3)*f(1) - c(4,2)*f(2) - c(4,1)*f(3)  = 9;
  f(5) = 5! - 1 - c(5,4)*f(1) - c(5,3)*f(2) - c(5,2)*f(3) - c(5,1)*f(4)  = 44;注解:
  "-1"表示全部放对;
  c(m,n)表示m个中有n个放对;

Answer 6

总结如下:
  f(n) = n! - 1 - c(n,n-1)*(f1) - c(n,n-2)*f(2) - c(n,n-3)*f(3).....-c(n,1)*f(n-1)可见大体上是个递归算法

Answer 7

1. 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32, 2^6 = 64, 2^7 = 128, 2^8 = 256, 2^9 = 512,共有10个箱子2. 两种，我画了一下
0 X 0 0 0 0 X 0
0 0 0 X X 0 0 0
X 0 0 0 0 0 0 X
0 0 X 0 0 X 0 03.大致上，P(5 5)-C(1 5)*P(4 4)+C(2 5)*P(3 3)-C(3 5)*P(2 2)+C(4 5)*P(1 1) = 45(可能不正确，不知道楼上为什么-1)

Answer 8

to ypyao85(云) :
   你的识子最后是否该添上 "-C(5 5)*p(0 0)

Answer 9

1:不明白这个最小的含义，假设只一种箱子，里面全部装的是一个的呢，能表示所有的吗？
2：八皇后问题，2种情况
3：假设ABCDE四个信封，A信封最后放，有4*3*2*1种情况；

Answer 10

dozoo(飞来峰上有晴天):
我觉得咱们的思路差不多，无非就是所有的排列，减去只要有一封信正确的排列，我确实少减了1。正确结果是44吧

Answer 11

3：假设ABCDE四个信封，A信封最后放，有4*3*2*1种情况；
我觉得这种算法有问题,假定ABCDE五封信，放到12345这五个信封中去，正确顺序是ABCDE->12345.
现在如果A先放，那它必须在BCDE，如果A在2，好办，B有4种可能了，如果A不在2，这样B只有3种可能，所以那个4*3*2*1不正确，我觉得。

Answer 12

第一题是我搞错了，钻到钱眼里去了，什么都不学资本家，偏偏学这个，哈哈，liushmh(c++)  是对的

Answer 13

ypyao85(云):
    照你的意思,应该连着减才是, 你怎么有加有减, 加表示什么?

Answer 14

有重复计数，比如只要有一个对的排列中，如果A和B正确，那么在计算A的时候已经把B计算在内了，当然在计算B的时候就需要把A减掉

Answer 15

我算出来也是44种，但用的方法不太一样：
现在将问题这样看，a不能放到A里，b不能放到B里............e不能放到E里
（小写的代表信，大写的代表信封）
则第一个放a，有四种放法；设放到B里，则b就有四种放法
若放到A里，则剩下的三封信要全放错就只有两种放法，
若放到A以外的信封里(C,D,E)，设放到C里，则c就有三种放法(A,D,E)
  若C放到A里，则d,e要全放错就只有一种可能，
  若不放到A里，则可以放到D，E里面的一个，
  如放到D里，则d必须放到E里；如放到E里，则e必须放到D里。所以共有4*(1*2+3*(1+1+1)))=44种 ypyao85(云)：
    你对于第二题的解法我觉得有点问题，你这样放的话那两条对角线上就一颗子也没有了，不知道你有什么看法？

Answer 16

lyymax() :
 如果有更多封信的话,你这样想下去恐怕要头疼死了^_^
 还是ypyao85(云)的方法简单实用.不过我还是没弄明白.

Answer 17

dozoo(飞来峰上有晴天) 
这是高中的排列组合题，大学里概率课也讲了，数学逻辑上我也讲不太清楚，毕竟毕业好几年了。就是类推吧，所有的排列－至少有1封装对的排列＋至少有2封装对的排列……lyymax() 
第二道，题上只说最多不多过2枚棋子，并没有说不允许一条线上没有棋子呀

Answer 18

to jasn(春江雨): 
  强!把算法都实现了!