c语言,计算等式

Apria 发布于 2017/02/19 18:02
阅读 1K+
收藏 0

编程在算式123 45 67 8 9=N的下划线部分填上加号(+)或减号(-),使该等式成立。要求程序运行时输出该等式。(保证数据存在满足的等式)

输入一个整数N。

输出满足条件的等式。若不存在满足的等式,则输出"impossible"(输出不包括引号)

100

123+45-67+8-9=100
加载中
1
MikeManilone
MikeManilone
#include <stdio.h>

char ans[4];
int num[] = {123,45,67,8,9};
int n;

int calc() {
    int res = num[0];
    for(int i = 0; i < 4; ++i) {
	if(ans[i] == '+') res += num[1+i];
	else res -= num[1+i];
    }
    return res;
}

void print_ans() {
    printf("123%c45%c67%c8%c9=%d\n", ans[0], ans[1], ans[2], ans[3], n);
}

int solve(int depth) {
    if(depth == 4) {
	if(calc() == n) return 1;
	else return 0;
    }

    ans[depth] = '+';
    if(solve(depth+1)) return 1;
    ans[depth] = '-';
    if(solve(depth+1)) return 1;
    return 0;
}

int main() {
    while(scanf("%d", &n) == 1) {
	if(solve(0)) print_ans();
	else printf("impossible\n");
    }
    return 0;
}

这个题很简单啊,就是上面有人提到的 DFS,不花 10 分钟就能写出来。题主要多多练习啊,思路很简单,就看怎么尽快地把思路变成能运行的代码。

另外还可以想到,这个题目解空间是有限的,而且很小,只有 2^4 = 16 个解,那么完全可以提前把这些解全部算出来,输入的时候直接查表。

这个题简单在没有括号和乘除,题主可以用这个思路分析一下二十四点游戏怎么解决。提示:用逆波兰表示法。

Apria
Apria
函数看不懂,什么意思呀
Apria
Apria
大神啊,我的天,谢谢
0
中山野鬼
中山野鬼

最简单的方式就是深度遍历,每个节点有两个子结点,"+","-",没啥好分析的,到底计算一下结果,不行就回退。哈。

Apria
Apria
就是不会编啊,说得简单。
返回顶部
顶部