首页 > 搜索 > DFS搜索 > 微策略2013年校园招聘笔试题-寻找表达式
2014
01-11

微策略2013年校园招聘笔试题-寻找表达式

题目描述:
现在有一个序列123……N,其中N介于3和15之间,要求在序列之间加入+、-或者空格,使得该序列组成的数学表达式的运算结果为0。
输入:
输入可能包含多个测试样例。
对于每个测试案例,输入整数N(3<=N<=15),代表这个序列的长度。
输出:
对应每个测试案例,输出所有使得表达式结果为0的组合,当有多个组合时,按字典序进行排序输出。
样例输入:
3
6
样例输出:
1+2-3
1 2+3-4-5-6
提示:
 1_2+3-4-5-6相当于12+3-4-5-6(‘_’代表空格)

题目来自九度 1498 http://ac.jobdu.com/problem.php?pid=1498

分析:由于只有 加减两种操作,因此要比普通的 表达式求值简单很多。此题应该算是一个搜索的题目,这里是用的递归(dfs),穷举所有的情况,符合情况就输出。

是一个练习深搜的不错题目!

在递归的时候分布遍历这3中情况:合并上一个,加,减。

传入参数last,代表上一个数,因为当前数 可以选择和上一个数合并。

比如1_2+3-4-5-6

1就是上一个数,2就是当前数,形成12。

//copyright: www.acmerblog.com
#include <stdio.h>
char str[100];
int n,j;
//搜索到第i个数;总和为sum;last表示上一个数的值
void f(int i,int sum,int last){
    if(i == n+1){
        if(sum == 0){ //遍历结束的时候判断是否符合情况
            printf("1");
            for(j=0; j<n-1; j++){
                printf("%c%d",str[j],j+2);
            }
            puts("");
        }
        return;
    }
    //合并时需要考虑上一个数的正负号
    int tmp = last > 0 ? i : -i;
    str[i-2] = ' ';//str记录所有的操作
    if(i < 10)
        f(i+1,sum+last*10+tmp-last, last*10+tmp);//合并上一个数
    else
        f(i+1,sum+last*100+tmp-last, last*100+tmp);//合并上一个数
    str[i-2] = '+';
    f(i+1,sum+i, i);//加当前数
    str[i-2] = '-';
    f(i+1,sum - i, -i);//减当前数
}

int main() {
    while(scanf("%d",&n) != EOF)
    {
        str[0] = '1';//第一个为1已经确定
        f(2,1,1);//从第2个数开始,当前和为1,上一个数也为1
    }
    return 0;
}
/**************************************************************
    Problem: 1498
    User: 从此醉
    Language: C
    Result: Accepted
    Time:90 ms
    Memory:912 kb
****************************************************************/

 


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 不考虑最后将结果排序的话,快排的时间复杂度是O(N) ,而堆排的是O(N*logK),这样比较看,快排快