[已解决]程序制作时的一个问题，请大佬求助

zhangjinxuan

人造人 发表于 2022-10-15 09:11
void dfs(int i, int s) { //深搜找答案
你这dfs和枚举有何区别？

dfs函数里面有递归啊，dfs函数里有回溯啊，怎么能说是枚举算法啊

tommyyu

zhangjinxuan 发表于 2022-10-15 09:28
请举例说明，我认为你说的那种必须是不按照顺序的算式调换一下数字位置就可以了

11 * 4 - 4 * 5
3 * 12 - 1 * 12
8 * 10 - 8 * 7

zhangjinxuan

tommyyu 发表于 2022-10-15 09:47
11 * 4 - 4 * 5
3 * 12 - 1 * 12

不是你想的那样，我的程序计算出来的算式只有在忽略优先级，从左往右算的时候才可得到24

比如：
5+4*3-4
这个算式从左向右算是等于24，对吧，我的意思是在这个算式中添加一些括号，使它不用忽略优先级，不用从左往右算就可以得到24，就拿5+4*3-4举例，他加上括号：(5+4)*3-4

你的两个反例从左向右算得不到24，还有，看代码，看代码，看看就明白我的意思了

tommyyu

zhangjinxuan 发表于 2022-10-15 09:19
哎，都没有理解题面，语文表达才重要啊

比如5*8-6*7
5和8是二级算式，相乘也是二级算式，不需要加括号
5*8-6 是两个二级算式相减，变成一级算式，但是还不需要加括号
5*8-6*7是一级算式乘二级算式，所以一级算式需要加上括号，就是(5*8-6)*7

zhangjinxuan

tommyyu 发表于 2022-10-15 09:47
11 * 4 - 4 * 5
3 * 12 - 1 * 12
8 * 10 - 8 * 7

我的程序算出来的算式只有从左向右算才等于24，看代码吧，看就能明白了

zhangjinxuan

tommyyu 发表于 2022-10-15 09:58
比如5*8-6*7
5和8是二级算式，相乘也是二级算式，不需要加括号
5*8-6 是两个二级算式相减，变成一级算 ...

我再思考一会儿...让我想想...

jackz007

        走弯路了不是？
       1 × 2 × 3 × 4 = 24

dolly_yos2

可以测试一下看看是不是这个意思（总觉得写复杂了）（假设操作数总在 int 范围内、输入总是以操作数开始、除最后一个操作数外每个操作数后总是紧接着一个四则运算符、每个四则运算符后总是紧接着一个操作数、输入中没有任何其他符号）

#include <iostream>
#include <vector>
void parse_helper(
        const std::vector<int>& operands,
        const std::vector<char>& operators,
        const size_t level,
        std::ostream& output
){
        bool issue_parentheses = false;
        if(level > 0){
                if(!(operators.at(level) & 4u) && (operators.at(level - 1) & 4u)){
                        issue_parentheses = true;
                        output.put('(');
                }
                parse_helper(operands, operators, level - 1, output);
        }else{
                output << operands.at(0);
        }
        if(issue_parentheses) output.put(')');
        output.put(operators.at(level) - 1);
        output << operands.at(level + 1);
}
void parse(std::istream& input, std::ostream& output){
        std::vector<int> operands;
        std::vector<char> operators;
        int value;
        char op;
        input >> value;
        operands.emplace_back(value);
        while(true){
                input >> op >> value;
                if(input.eof()) break;
                operands.emplace_back(value);
                operators.emplace_back(op + 1);        // 一个小小的 trick 来简化算符优先级判断
                                                // 考虑到 ASCII 下四则运算符的码值分别为
                                                //  * -- 0x2A (00101010)
                                                //  + -- 0x2B (00101011)
                                                //  - -- 0x2D (00101101)
                                                //  / -- 0x2F (00101111)
                                                // 给码值加一后可见高优先级运算符的第三低有效位（从一开始）
                                                //  均为 0 而低优先级的均为 1
        }
        parse_helper(operands, operators, operators.size() - 1, output);
}
int main(){
        parse(std::cin, std::cout);
        return 0;
}

zhangjinxuan

dolly_yos2 发表于 2022-10-15 16:06
可以测试一下看看是不是这个意思（总觉得写复杂了）

稍等，现在听课，待会看

人造人

zhangjinxuan 发表于 2022-10-15 09:32
dfs函数里面有递归啊，dfs函数里有回溯啊，怎么能说是枚举算法啊

枚举不就是一个一个的试么？

zhangjinxuan

dolly_yos2 发表于 2022-10-15 16:06
可以测试一下看看是不是这个意思（总觉得写复杂了）（假设操作数总在 int 范围内、输入总是以操作数开始、 ...

所以代码精简后就是这样，对吗：

#include <bits/stdc++.h>
using namespace std;

char opts[11];
int nums[11], n;
void parse_helper(int l) {
    bool flag = false;
    if(l > 1) {
        if((opts[l] == '*' || opts[l] == '/') && (opts[l - 1] == '+' || opts[l - 1] == '-')){
                flag = true;
            printf("(");
        }
        parse_helper(l - 1); 
    } else printf("%d", nums[1]);
    if (flag) printf(")");
    printf("%c", opts[l]);
    if (l != n) printf("%d", nums[l + 1]);
}
int main() {
        scanf("%d%d", &n, &nums[1]);
        getchar();
        for (int i = 2; i <= n; ++i) {
                scanf("%c%d", &opts[i - 1], &nums[i]);
                getchar();
        }
        parse_helper(n);
    return 0;
}

如果是，那么我就测试一下，测试成功就设置你为最佳答案

高山

哪里有tommyyu的题解？

zhangjinxuan

高山 发表于 2022-11-27 11:57
哪里有tommyyu的题解？

题解是dolly_yos2提供的

zhangjinxuan

dolly_yos2 发表于 2022-10-15 16:06
可以测试一下看看是不是这个意思（总觉得写复杂了）（假设操作数总在 int 范围内、输入总是以操作数开始、 ...

对了，我看大佬已经中级鱼油了，现在可以批准加好友了吗

zhangjinxuan

人造人 发表于 2022-10-15 16:56
枚举不就是一个一个的试么？

我蒙了，我算法都白学了吗

zhangjinxuan

tommyyu 发表于 2022-10-15 08:59
我的意思是这种方法可能不一定能够求出答案，因为会有那种必须是不按照顺序的算式

https://fishc.com.cn/thread-221351-1-1.html 第二弹

zhangjinxuan

dolly_yos2 发表于 2022-10-15 16:06
可以测试一下看看是不是这个意思（总觉得写复杂了）（假设操作数总在 int 范围内、输入总是以操作数开始、 ...

https://fishc.com.cn/thread-221351-1-1.html 第二弹

tommyyu

zhangjinxuan 发表于 2022-11-28 10:56
https://fishc.com.cn/thread-221351-1-1.html 第二弹

可不可以打表

tommyyu

zhangjinxuan 发表于 2022-11-28 10:55
我蒙了，我算法都白学了吗

我感觉dfs、bfs、dp都是高级枚举

zhangjinxuan

tommyyu 发表于 2022-11-28 10:58
可不可以打表

你说呢