注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

数字序列和为0详解代码

机器学习 水墨上仙 3065次浏览 已收录 手机上查看

先说一下大致思路,然后贴代码,之后分析代码中的各个函数,实现充分展现了Tutu_Lux扎实的基本功和灵动的脑瓜子,哈,:-) 。思路:由于N是从3至9的范围,解决方案就是针对每个N的取值,先计算三个分隔符“_ + -”填入序列1-N的所有可能组合的情况总数设置所有情况的组合序列(采用3进制的思想,即set函数)对每种组合计算表达式值,如果为0则输出(利用栈&状态机,calculate函数)文章作者:Yx.Ac 文章来源:勇幸|Thinking (http://www.ahathinking.com)

#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;
    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,其中一个用于保存操作符)。如果运算符不止一个优先级,那么栈就必须是变长了,而且需要一个独立的操作符栈,同时执行过程就会是中缀转后缀的算法了。因此这个函数是针对题目的特定优化和简化。


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明数字序列和为0详解代码
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……