首页 > 笔试面试题 > 微策略笔试题一道:数字序列和为0

微策略笔试题一道:数字序列和为0

2013年3月5日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

这道深搜的题目写的我心情好别扭,代码也感觉别扭。希望路过的爱动手的牛牛们指导,不管是代码还是思路方面的建议都行;/握手

题目:序列123...N,N介于3和9之间,在其中加入+、-或者空格,使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问,如何获得所有组合?

我代码的思路就是深搜,处理空格时复杂一些,具体参数见注释。

#include <iostream>
#include <string>
using namespace std;

/* parameter description
 *
 * N,1-N 的数字串
 * k,处理到第几个字符了,k范围[1-N]
 * val,当前表达式的值
 * result,结果字符串
 * pre,记录前一个操作符,用于遇到空格时考虑
 */
void dfs(int N, int k, int val, string& result, char pre)
{
	if(k > N)
	{
		if(val == 0)
		{
			printf("%s\n", result.c_str());
		}
		return;
	}
	/* deal space */
	int val_space = val;
	if(pre == '-')
	{
		val = val+(k-1)-((k-1)*10+k);
	}else if(pre == '+')
	{
		val = val-(k-1)+((k-1)*10+k);
	}else
	{
		val = val * 10 + k;
	}
	result.push_back(' ');
	result.push_back(k + '0');
	dfs(N, k+1, val, result, ' ');

	val = val_space;
	result.pop_back();
	result.pop_back();

	/* deal + */
	val += k;
	result.push_back('+');
	result.push_back('0' + k);
	dfs(N, k+1, val, result, '+');

	val -= k;
	result.pop_back();
	result.pop_back();

	/* deal - */
	val -= k;
	result.push_back('-');
	result.push_back('0' + k);
	dfs(N, k+1, val, result, '-');

	val += k;
	result.pop_back();
	result.pop_back();
}

void main()
{
	string res = "1";
	for(int i = 3; i <= 9; ++i)
	{
		dfs(i, 2, 1, res, ' ');
	}
}

【运行结果】

(全文完)

  • haithink

    感觉博主的代码对1-234的计算是错的啊
    1-234的时候
    val = val * 10 + k;
    val的值不对吧

    • Yx.Ac

      什么意思?这里是加入符号后值为0 ,推荐看这一篇http://www.ahathinking.com/archives/210.html

  • haithink

    @Tutu_Lux 这个代码怎么回事?很多字符缺少了?看不懂啊

  • http://mazheng.org 冰上游鱼

    学长好! 这个我去年也做了,答卷仓促。然后下来写了半天。

    • Yx.Ac

      哈,可以贴个代码交流下~ :-)

  • Tutu_Lux

    @Yx.Ac
    代码很简单啊,这不过这缩进……
    因为每个分隔符只有三种可能“ +-",转三进制,则不仅每一个数位可以表示一种可能,而且连续的整数会遍历所有可能情况~
    当元素有k种取值、总共n种情况时都可以用这一招哈

    • Yx.Ac

      @Tutu_Lux 奥,给力啊,厉害!代码好好写一下,你的变量名太随意了,缩进可以

      ...

      一下

  • Tutu_Lux

    //校园网IP不能评论?
    学长,我直接计算出所有可能的总数,然后转3进制就能输出所有分隔符的可能情况~
    看代码:
    #include

    /*
    * Initialize the string with 1 to 9 and seperated by whitespace
    * for len in range(3, 9+1):
    * for each possibility of seperators:
    * calculate the result, if it's zero, output
    */

    int calculate(char input[], int n){
    //Use a simple state machine to interpret the input as an expression
    int stack[3] = {0}, sp = 0, i = 0;

    while (i 0; sp -=2){
    str[sp] = choice[num%3];
    num /= 3;
    }
    }

    void result0(){
    char str[18] = "1 2 3 4 5 6 7 8 9";
    int n, sp, all;

    for (n = 3; n < 9; ++n){
    all = 1;
    for (sp = 1; sp < n; ++sp)
    all *= 3; //Count the number of possibilities
    while (all){
    set(str, n, --all);
    if (calculate(str, n) == 0){
    str[n*2-1] = '';
    printf("%s = 0\n", str);
    }
    }
    }
    }

    int main(int argc, char const *argv[]){
    result0();
    return 0;
    }

    • Yx.Ac

      @Tutu_Lux 哈,评论得我批准,有的是spam,插件不够智能
      你的代码我没看懂;为什么要转成3进制?