1

SO に関するこのタイトルには多くの質問があることを認識していますが、私が見つけたものはすべて や のようなものi = ++iでf(f(f(x)))、どちらもこのコードには含まれていません。これは、これに対するバックトラッキング ソリューションの試みです。私は C の経験がある程度ありますが、C++ を習得しようと試み始めたばかりで、練習のために Codeforces の問題に取り組んでいます。以下のスニペットは、プログラムの本体です。mainは示していませんが、入力と出力を処理します。ここでは、各スタック フレームをできるだけ小さく保つために、 、 、および にweightsグローバルanswer変数を使用しました。max_depthsolve

問題の原因となっている入力は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)、ベクトルをトラバースする順序は標準では定義されていませんが、それでも違いが生じる理由はわかりません。私は何が欠けていますか？

#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 = "";
}

(私が提出した完全なコードは、違いがある場合は、ここにあります。)

編集：

Codeforces の問題に対する答えを探して、誰かがこれに出くわした場合: このコードの問題は、「答え」が逆になっていることです。に変更answer.append(ss.str() + " ")することanswer = ss.str() + answerは、それを機能させる最短の修正です。

4

1 に答える 1

7

この C++ コードが異なるコンパイラで異なる出力を与えるのはなぜですか?

それは異なる出力を与えません。

これを 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...」と表示されますが、これは正しくありません。

codeforces サーバーでのテスト結果を誤解していると思います。

正解は「9 10 9 10…」です。

プログラムの出力は、codeforces サーバーとローカル ワークステーションの両方で「4 3 2 3 4 3...」です。

したがって、アルゴリズムは間違っており、プログラムの出力は一貫しています。

テスト結果の「出力」と「回答」の 2 つのフィールドを混同しています。

もう一度テスト結果を確認してください。

于 2013-08-30T05:42:31.710 に答える