2013年07月23日

构造和最接近m的序列


微软笔试题一道

给定数字N和M,则从数字1到N得序列中添加+或-,使得序列的和最接近M,打印出所有满足此关系的序列,例如,给定N=4 M=6,则满足条件得序列是1-2+3+4=6

分析

看到这样得题目,第一反应是动态规划,对于每一个数,其有两种取法,+或-,则依次遍历所有得数,尝试这两种可能,最后得出结果。动态规划需要列出详细的递归表达式,定义出递归表达式得意义,给出边界条件,记录递归过程中得中间结果,知道在什么情况下,递归结束。

首先列出递归表达式,F(i,m)表示数组前i的元素通过添加加减号后与整数M之间最小得差距,例如对于上面给出得例子,F(3,6)=0 > F(i,m) = min{|F(i-1,m-a[i])|,|F(i-1,m+a[i])|} ( 0<= i < n)

除了上面得表达式之外,还需要一个二位数组记录中间结果。

代码

方法一

根据前面的动态规划分析,则可以按照递归表达式来写出方程。在记录中间结果的时候,target-array[i]可能小于0了,所以使用了一个offset偏移量,保证前面的能够大于0。因为是记录前i个数通过添加加减号之后与M的差距,故只记录绝对值。

int dfsV4(const int* array, int index, int target,int offset, int **state){
    if(index == 0){
        return abs(target-1,0) < abs(target+1,0) ? target - 1 : target + 1;
    }
    if(state[index][target+offset] > INT_MIN)
        return state[index][target+offset];

    int plus = dfsV4(array,index-1,target+array[index],offset,state);
    state[index-1][target + array[index] + offset] = plus;

    int minus = dfsV4(array,index-1,target-array[index],offset,state);
    state[index-1][target - array[index] + offset] = minus;

    state[index][target+offset] = abs(plus,0) < abs(minus,0) ? abs(plus) : abs(minus); 
    return state[index][target+offset];
}

此题的动态规划过程很简单,按照表达式来实现就行了,然后是进行回溯,打印出所有存在的可能组合,

void backtracing(const int *array, int index, int **state, int offset, int target,stack<bool> symbol){
    if(index == 0){
        if(abs(target + 1,0) < abs(target - 1,0))
            symbol.push(true);
        else
            symbol.push(false);
        int i = 0;
        while(!symbol.empty()){
            if(!symbol.top()){
                if(i == 0){
                    cout << array[i++];
                }else{
                    cout <<"+"<< array[i++];
                } 
            }else{
                cout << "-" << array[i++];
            }
            symbol.pop();
        }
        cout << endl;
        return;
    }
    int left = state[index-1][target-array[index] + offset];
    int middle = state[index][target+offset];
    if(middle == left){
        symbol.push(false);
        backtracing(array,index-1,state,offset,target-array[index],symbol);
    }else{
        symbol.push(true);
        backtracing(array,index-1,state,offset,target+array[index],symbol);
    }

    int right = state[index-1][target+array[index] + offset];
    if(middle == left && middle == right){
        symbol.pop();
        symbol.push(true);
        backtracing(array,index-1,state,offset,target+array[index],symbol);
    }
}

测试此代码,给定N = 4,M = 6,则是在1,2,3,4中查找与6最接近得组合。运行结果如下:

1-2-3+4+5

1+2+3-4+5

1+2+3+4-5

虽说有了正确得结果,但是总感觉,还可以定义其他得递归表达式,使思路看上去更加明了和清晰!欢迎大家指导!

总结

关于这个题目得变形有很多,大概都是在数组构造出和为某个值的子序列。例如

前一篇: Openstack Keystone介绍 后一篇: Hello Github