首页 > 笔试面试题, 算法 数据结构 > 再谈数字序列和为0

再谈数字序列和为0

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

---

之前研究过一道微策略的笔试题-数字序列和为零,当时采用DFS做的,深感别扭,后来在Tutu_Lux的帮助下,得到一个不错的方案,思路简单,说白了就是暴搜,但实现巧妙,代码灰常漂亮。感谢Tutu_Lux

先说一下大致思路,然后贴代码,之后分析代码中的各个函数,实现充分展现了Tutu_Lux扎实的基本功和灵动的脑瓜子,哈,:-) 。

思路:

  1. 由于N是从3至9的范围,解决方案就是针对每个N的取值,先计算三个分隔符“_ + -”填入序列1-N的所有可能组合的情况总数
  2. 设置所有情况的组合序列(采用3进制的思想,即set函数)
  3. 对每种组合计算表达式值,如果为0则输出(利用栈&状态机,calculate函数)

代码如下:

#include <stdio.h>

/*
 * 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;
	for(; i < n*2-1; ++i)
	{
		switch(input[i])
		{
		case ' ':
			stack[sp] = stack[sp]*10;
			break;
		case '+':
		case '-':
			if(sp == 0)
			{
				stack[1] = input[i];
				sp = 2;
			}else
			{
				stack[0] = stack[0]+(stack[1]=='-' ? -1 : 1)*stack[2];
				stack[1] = input[i];
				stack[2] = 0;
			}
			break;
		default: //digits
			stack[sp] += input[i]-'0';
			break;
		}
	}
	if (sp == 2)
	{
		stack[0] = stack[0]+(stack[1]=='-' ? -1 : 1)*stack[2];
	}
	return stack[0];
}

void set(char str[], int n, int num)
{
	//Transform num into base3 to generate the presentation of seperators
	int sp;
	char choice[] = " +-";
	for(sp = (n-1)*2-1; sp > 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)  // 3-9
	{
		all = 1;
		for (sp = 1; sp < n; ++sp) //Count the num of possibilities on 1-n
		{
			all *= 3;
		}
		while(all)
		{
			set(str, n, --all);
			if (calculate(str, n) == 0)
			{
				str[n*2-1] = '\0';
				printf("%s = 0\n", str);
			}
		}
	}
}

int main()
{
	result0();
	return 0;
}

代码说明:

对于每个N,先计算出所有可能组合情况的数目,然后根据所有的情况数目all,将[1,all]的值传给函数set,并根据每个数值的三进制(分隔符只有三种情况,如果是四种分隔符,那就是四进制了)表示为str赋值。

for (sp = 1; sp < n; ++sp)
{
	all *= 3;
}
while(all)
{
	set(str, n, --all);
......

Set函数的本质是将每一种分隔符的排列情况映射为一个整数(即1-all之间的数字),由于这些数字是连续的,而连续的整数转换为某个进制上的表示是不会有重复的,故遍历这个区间,就可以通过进制转换表示出所有的可能,有多少个数被转换,就能输出多少种可能。正如Tutu_Lux所说:当元素有k种取值、总共n种情况时都可以用这一招!!

Calculate函数就是计算每一种set后的表达式值,采用了简单的自动机思想和简单的栈(数组)。值得说明的是,calculate程序程序的功能是计算中缀表达式的值,因此需要使用栈来保存操作数的值。由于题目中操作符只有加和减,两者是同一优先级的,因此可以直接简化为一个从左向右的扫描过程,同时栈只需要保存两个操作数的值即可(所以stack数组的长度才是3,其中一个用于保存操作符)。如果运算符不止一个优先级,那么栈就必须是变长了,而且需要一个独立的操作符栈,同时执行过程就会是中缀转后缀的算法了。因此这个函数是针对题目的特定优化和简化。

最后不得不感叹,一个小题目就能反映很多东西,自己的基础还需要进一步夯实,再次感谢Tutu_Lux。

(全文完)

  • zxw

    #include
    #include
    using namespace std;
    int N;

    //(2,2)返回数23,(4,3)返回数456,...
    int getsum(int st,int len){
    int res=st;
    while (len>1)
    {
    st++;
    res=res*10+st;
    len--;
    }
    return res;
    }

    //(2,2)返回串23,(4,3)返回串456,...
    string getstr(int st,int len){
    char sumstr[2];
    string res="";
    itoa(st, sumstr, 10);
    res=sumstr;
    while (len>1)
    {
    st++;
    itoa(st, sumstr, 10);
    res+=((string)" "+sumstr);
    len--;
    }
    return res;
    }

    void solve(int sum,int end,string str){
    if(end>=N&&sum==0){
    cout<<str<<endl;
    return;
    }
    //可根据sum做剪枝
    for (int nextend=end+1;nextend<=N;nextend++)
    {
    int nextn=getsum(end+1,nextend-end);//可根据nextn或nextend做剪枝
    string str1 = getstr(end+1,nextend-end);
    if(end==0){
    solve(sum+nextn,nextend,str1);
    }
    else{
    solve(sum+nextn,nextend,str+"+"+str1);
    solve(sum-nextn,nextend,str+"-"+str1);
    }
    }
    }
    int main()
    {
    for (N=3;N<10;N++)
    solve(0,0,(string)"");
    return 0;
    }

    • Yx.Ac

      亲,你是要表示另一种思路吗?可以给点文字说明么~~囧~~

  • zxw

    #include
    #include
    using namespace std;
    int N;
    //(2,2)返回数23,(4,3)返回数456,...
    int getsum(int st,int len){
    int res=st;
    while (len>1)
    {
    st++;
    res=res*10+st;
    len--;
    }
    return res;
    }
    //(2,2)返回串23,(4,3)返回串456,...
    string getstr(int st,int len){
    char sumstr[2];
    string res="";
    itoa(st, sumstr, 10);
    res=sumstr;
    while (len>1)
    {
    st++;
    itoa(st, sumstr, 10);
    res+=((string)" "+sumstr);
    len--;
    }
    return res;
    }

    void solve(int sum,int end,string str){
    if(end>=N&&sum==0){
    cout<<str<<endl;
    return;
    }

    //可根据sum做剪枝

    for (int nextend=end+1;nextend<=N;nextend++)
    {
    int nextn=getsum(end+1,nextend-end);//可根据nextn或nextend做剪枝
    string str1 = getstr(end+1,nextend-end);
    if(end==0){
    solve(sum+nextn,nextend,str1);
    }
    else{
    solve(sum+nextn,nextend,str+"+"+str1);
    solve(sum-nextn,nextend,str+"-"+str1);
    }
    }
    }
    int main()
    {
    for (N=3;N<10;N++)
    solve(0,0,(string)"");
    return 0;
    }

  • 风之谷

    我只能说:太精妙了!