123456789=100 - 编程论坛

#2

flylee2010-01-05 20:42

若干年前做过此题，让我想想

#3

沙漠狼2010-01-05 21:05

回复 2楼 flylee

好的。谢谢你，一定要帮帮我，这是我课程设计的题目。

#4

flylee2010-01-05 21:06

程序代码：

#include <stdio.h>

char sign[9];
int res;

void search(int pos)
{
    int val, i;
    if(pos == 10) {
        if(res == 100) {
            for(i=0; i<9; ++i) {
                if(sign[i]) printf("%c", sign[i]);
                printf("%d", i+1);
            }
            printf("=100\n");
        }
    }
    else {
        val = 0;
        for(i=pos; i<10; ++i) {
            val += i;

            res += val;
            sign[pos-1] = '+';
            search(i + 1);
            res -= val;

            res -= val;
            sign[pos-1] = '-';
            search(i + 1);
            res += val;

            val *= 10;
            sign[i] = 0;
        }
    }
}

int main()
{
    res = 0;
    search(1);
    return 0;
}

#5

沙漠狼2010-01-05 21:28

可以跟我说一下算法思想吗？我运行的时候有错误，能帮我改一下吗？

#6

flylee2010-01-05 21:31

回复 5楼沙漠狼

哪里错误？我在我的机器上运行没有问题

只有本站会员才能查看附件，请登录

#7

flylee2010-01-05 21:32

回复 5楼沙漠狼

思路，其实就是一个不加优化的深度优先搜索

#8

沙漠狼2010-01-05 21:47

哦，知道了，谢谢，的却没错，在我的机子运行不行再我同学的上面可以，谢谢！太感激了！

#9

沙漠狼2010-01-05 21:51

你这是用C语言写的吧？有些地方我不太明白，因为我学的是C++的，你可以再跟我说一下你是具体用什么数据结构的吗？最好详细一点，谢谢！

#10

flylee2010-01-05 22:03

回复 9楼沙漠狼

C和C++在基础语法上没多大区别，我觉得应该能看懂这个程序
至于数据结构，这个题还用不到什么复杂的数据结构，我只用了全局的res和sign[]来分别保存当前计算得到的值以及符号
如果有不明白的地方，我想更多是算法上的原因，推荐你看一些DFS和BFS方面的东西，google一下就能得到很多

#11

沙漠狼2010-01-05 22:09

哦，那我知道了，其实就是深度遍历和广度遍历，这个我知道一点，谢谢了，太感激了

#12

烈烈水云天2010-01-06 10:43

好强啊，我才看到。其实这个题我会。只是晚了一步