组合数学

数字推理

3,8,24,63,143 ，（）

3=2*2-1

8=3*3-1

24=5*5-1

63=8*8-1

143=12*12-1

序列为2 3 5 8 12

相邻两数间隔1 2 3 4 5

因此下一个数17

17*17-1=288

组合数学

###How many rectangles you can find from 3*4 grid?

因为每两条横线与两条竖线可以组成一个矩形， 共有4条横线，5条竖线 ， 因此共有 C(4，2)C(5，2)=610=60 个矩形 。

##智力题

###小松鼠运坚果

小松鼠采到了100 颗坚果要运回家。家离放坚果的地方有100 米远。小松鼠每次最多运 50 颗。BUT！小松鼠很馋。。。每走2 米就要吃一颗坚果。。。返回时不会再吃坚果，问小松鼠最多能运回家多少颗坚果？

让松鼠走到离家50米的地方停止，把剩下的25个坚果放下，回去拿剩下的50个，然后到刚才放坚果的地方停下，这时候还有50个坚果，距离家的距离为50米，最后到家的时候吃25个，还剩下25个

设采坚果的地点为A，家为B，从A到B方向的运动需要消耗坚果。题目求最多运多少坚果回家，为使结果最大化，所以需要每次开始都运50颗，所以题目也就是求最少的坚果消耗量，由于A->B方向的运动一直要消耗坚果，所以也就是求此方向运动的最少距离。由于每次做多运50颗，所以有一段A->B方向必须走两次，设这段距离为x，剩下的距离为y，则有x+y=100。消耗的总坚果数为(2x+y)/2。并且为了使最后y段能够运走所有2x段剩下的坚果，需要满足2*(50-x/2)<=50，所以x>=50。由于要使(2x+y)/2=(x+100)/2最小，所以x应该去最小值50,所以消耗坚果数为（50+100）/2=75，所以剩下25个。

###在一个游戏的任务中,玩家需要进入1个山洞,取得宝石,之后回到入口.

山洞的地图如下:

​ S--------------------T

S是入口

T处有宝箱,打开宝箱之后可能得到的物品有:

1)宝石,出现概率为5%.

2)魔法券.出现概率为50%.玩家每消耗一个魔法券,可以直接传送到入口S.

3)什么也没有,概率为45%.

S到T的距离为1.

每次玩家回到S之后,宝箱T的状态会重置,再次进入山洞可以重新打开宝箱获得物品.

玩家的任务是到达T获取宝石之后回到入口S.如果到达T之后没有获得宝石,可以走出山洞之后

再进入反复刷.

问题:玩家完成任务所走路程的数学期望是()

因为宝石,出现概率为5%, 不管如何,出现要完成任务的期望次数是20次,大约10次不会有传送,那么就是20步

那么剩下10次会传送,那么是10步,总共30步

理论上，5% * 20=1，所以走了20次，开了20次宝箱，因为有往返过程，所以20*2=40，又因为在走40趟中，手里有了20 * 50%=10个魔法圈，可以不用用脚回到起点了，可以瞬间转移到起点 所以40-10=30次

可以设期望为x

拿到宝石：路程2

拿到魔法券：则走的路程为（1+x），可理解为先走1个单位的路程，然后直接传送到起点，之后需要行走的路程期望其实和初始时相同为x，故总的路程为（1+x），

什么也没有：走2个单位，回到起点，再开始走时和初始状态一样行走的路程期望也为x，故总的行走路程为（2+x）

综上所述，2*5% + （1+x）*50% + 45% * （2 + x）= x，解方程即可得答案

###选择工厂——最短距离问题

**12个工厂分布在一条东西向高速公路的两侧，工厂距离公路最西端的距离分别是0、4、5、10、12、18、27、30、31、38、39、47。在这12个工厂中选取3个原料供应厂，使得剩余工厂到最近的原料供应厂距离之和最短，问应该选哪三个厂 ？ **

5，4，10
27，4，10
0，4，10
5，27，39

img

思路：这道题在开始就诱导人们想两侧，其实不然，我们把工厂位置看成一条线，在里面找3个点， 剩余的工厂到最近的点的距离要尽量地小，那我们这3个点就要尽量分开，可以当成是上面一个，中间一个，下面一个，那这三个点之间必然要间隔这几个工厂，我们再看回选择部分，A选项4和5太近，是不可能的了，B选项的7有点莫名其妙，因为没有这个工厂。C选项的0和4也是相隔太近了。最后自然剩下D了

（1）工厂距离是从小到大排序的。

（2）从N个工厂中选择1个原料厂，选择位于中位数位置的工厂，距离之和最短。

（3）设A[i][j]表示从前i个工厂选择j个原料厂的最短距离 （1<=i<=j<=N）

B[i][j]表示从第i个工厂到第j个工厂选择1个原料厂的最短距离。（1<=j<=i<=N）

（4）从前i个工厂选择j个原料厂，可分为两部分：

从前k个工厂选择j-1个原料厂和从第k+1个工厂到第i个工厂选择1个原料厂（1<=j-1<=k<i, k+1<=i）

若j-1等于0, 则前k个工厂没有原料厂了。

（5）递归解为：

A[i][j] = B[1][i], 即j=1时

A[i][j] = min{ A[k][j-1] + B[k+1][i] }，其中1<=j-1<=k<i, k+1<=i

/*---------------------------------------------
*   日期：2015-03-02
*   作者：SJF0115
*   题目: 选择原料工厂(最短距离问题)
*   来源：经典面试题
*   博客：
-----------------------------------------------*/
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <math.h>
using namespace std;
 
int fac[100][100];
 
// n工厂个数 count原料厂个数 result原料厂下标集合
vector<int> BestFactoryPoint(int n,int count){
    vector<int> result;
    //[1,n]
    int k;
    for(int i = 1;i <= n;){
        //[1,n]分成两部分[1,k]有count-1个原料厂[k+1,n]有1个原料厂
        k = fac[n][count--];
        // [k+1,n]有一个原料厂,中位点就是原料厂点
        result.push_back(k+1 + (n-k-1)/2);
        // 所有原料厂寻找完毕
        if(count == 0){
            break;
        }//if
        // 如果工厂个数小于原料厂个数
        // 所有工厂全是原料厂
        if(k <= count){
            for(int i = 1;i <= k;++i){
                result.push_back(i);
            }//for
            break;
        }//if
        // 求[1,k]部分
        n = k;
    }//for
    return result;
}
 
// 从[start,end]选择一点使其到其他点的距离最小
int MinDistanceOneFactory(int point[],int start,int end){
    if(start > end){
        return -1;
    }//if
    int mid = (start + end) / 2;
    // 计算距离
    int distance = 0;
    for(int i = start;i <= end;++i){
        distance += abs(point[i] - point[mid]);
    }//for
    return distance;
}
//
int MinDistance(int point[],int n,int count){
    if(n <= 0){
        return -1;
    }//if
    //
    // B[i][j]表示从第i个工厂到第j个工厂设1个原料厂的最短距离
    // i <= j B上三角有用
    int B[n+1][n+1];
    // 计算第i个工厂到第j个工厂设1个原料厂的最短距离
    for(int i = 1;i <= n;++i){
        for(int j = i;j <= n;++j){
            B[i][j] = MinDistanceOneFactory(point,i,j);
        }//for
    }//for
    // A[i][j]表示从前i个工厂中设j个原料厂的最短距离之和
    int A[n+1][n+1];
    // i前i个工厂
    for(int i = 1;i <= n;++i){
        // 设j个原料厂
        // j = 1时
        A[i][1] = B[1][i];
        for(int j = 2;j <= i;++j){
            A[i][j] = INT_MAX;
            for(int k = j-1;k < i;++k){
                int curMin = A[k][j-1] + B[k+1][i];
                if(curMin < A[i][j]){
                    A[i][j] = curMin;
                    fac[i][j] = k;
                }//if
            }//for
        }//for
    }//for
    return A[n][count];
}
 
int main() {
    int array[] = {0, 0, 4, 5, 10, 12, 18, 27, 30, 31, 38, 39, 47};
    int n = 12;
    int count = 3;
    cout<<"最小距离->"<<MinDistance(array,n,count)<<endl;
    vector<int> result = BestFactoryPoint(n,count);
    for(int i = result.size()-1;i >= 0;--i){
        cout<<array[result[i]]<<" ";
    }//for
    cout<<endl;
    return 0;
}