我意识到这个标题在 SO 上有很多问题,但我发现的所有问题都像 i =++i
或 f(f(f( x)))
,这两个都不在这段代码中。这是对 this 的回溯解决方案的尝试.我有一些使用 C 的经验,但我刚刚开始尝试学习 C++,并且我一直在做 Codeforces 问题来练习。下面的代码片段是程序的主体。 main
,我没有展示,处理输入和输出。为了保持 solve
的每个堆栈帧,我在这里为 weights
、answer
和 max_depth
使用了全局变量尽可能小。
导致问题的输入是 weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
和 max_depth = 1000
.当我用 g++ std=C++11 file.cpp
编译它时,它给出了“4 3 2 3 4 3 2 3 4 ... 3 2 1”,这是正确的答案。当 Codeforces 编译它时,它给出“9 10 9 10 9 10 9 10...”,这是不正确的。我的猜测是 for(int i : weights)
遍历 vector 的顺序不是由标准定义的,但即便如此,我也不明白为什么它会有任何不同。我错过了什么?
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
string answer = "";
vector<int> weights;
int max_depth;
bool solve(int left_scale, int right_scale, int last_added, int depth){
bool is_left = (depth % 2) == 0;
int new_weight;
int weight_to_inc = is_left ? left_scale : right_scale;
int weight_to_exceed = is_left ? right_scale : left_scale;
if (depth == max_depth){
return true;
}
for(int i : weights){
if (i != last_added){
new_weight = weight_to_inc + i;
if (new_weight > weight_to_exceed){
bool ans = solve(is_left ? new_weight : left_scale,
is_left ? right_scale : new_weight,
i, depth + 1);
if (ans){
stringstream ss;
ss << i;
answer.append(ss.str() + " ");
return true;
}
}
}
}
return false;
}
void start_solve(void){
if (solve(0, 0, 0, 0)){
return;
}
answer = "";
}
(我提交的完整代码,如果有任何区别的话,是 here。)
编辑:
万一有人在寻找 Codeforces 问题的答案时偶然发现:此代码的问题是“答案”被颠倒了。将 answer.append(ss.str() + "")
更改为 answer = ss.str() + answer
是使其正常工作的最短修复方法。
最佳答案
Why does this C++ code give different output on different compilers?
它不会给出不同的输出。
When I compile this with g++ std=C++11 file.cpp, it gives "4 3 2 3 4 3 2 3 4 ... 3 2 1," which is the correct answer. When Codeforces compiles it, it gives "9 10 9 10 9 10 9 10...", which is incorrect.
我相信你误解了 your test results on the codeforces server .
正确答案是“9 10 9 10...”。
您的程序在 codeforces 服务器和您的本地工作站上的输出都是“4 3 2 3 4 3 ...”。
所以你的算法是错误的,程序的输出是一致的。
您混淆了测试结果“输出”和“答案”的两个字段。
再次检查您的测试结果。
关于c++ - 为什么这个 C++ 代码在不同的编译器上给出不同的输出?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18525502/