組み合わせ論と動的プログラミングを含むプログラミングの課題を解決しようとしています。
良いニュースは、私はすでにそれを解決したということですが、特定の入力に対して、プログラムは間違った答えをスローします。
このプログラムは、入力として 2 つの数値を受け取ります。しましょうw = argv[1]、h = argv[2]
簡単に表現できるように、疑似数学的な方法で記述します
たとえば、次の「式」は、私のプログラムが w と h の 2 つのパラメーターを受け入れ、出力がx
T(w,h) = x
理論上の結果を で表しT(w,h)、プログラムの結果を で表しR(w, h)ます。T(w, h)それが常に正しい答えであると100％確信しています。
さあ行こう：
T(10, 10) = 2 R(10, 10) = 2
T(11, 10) = 2 R(11, 10) = 288**結果は異なります**
T(12, 10) = 4 R(12, 10) = 4
T(13, 10) = 4 R(13, 10) = 4
T(14, 10) = 66 R(14, 10) = 66
T(15, 10) = 290 R(15, 10) = 290
T(20, 10) = 9594 R(20, 10) = 98826 結果が異なる
T(25, 10) = 419854 R(25, 10) = 419854
T(30, 10) = 94082988 R(30, 10) = 94082988
T(35, 10) = 5578404294 R(35, 10) = 1283436998 この時点から、結果は常に異なります
T(36, 10) = 19730715436 R(36, 10) = 18446744071965430572 データ型オーバーフロー?
T(37, 10) = 19730715436 R(37, 10) = 18446744071965430572
T(38, 10) = 73368404198 R(38, 10) = 393345822 この結果は前回よりも小さく、前回よりも大きくなるはずです。
T(39, 10) = 287780277370 R(39, 10) = 17468538
T(40, 10) = 287780277370 R(40, 10) = 17468538
T(41, 10) = 1095232487336 R(41, 10) = 15826856
T(42, 10) = 4013757692218 R(42, 10) = 18446744071672822074 再び上がります。計算に膨大な時間がかかる
ブラック ボックス テストにはこれで十分だと思います。では、アルゴリズムと実際のコードを見てみましょう。
最初のパラメーターは 2 で乗算され、3 で除算され、整数にキャストされます。
例えば
引数1 = 20
20*2 = 40
40/3 = 13整数除算
その値は、問題を引き起こしている関数に渡されます。
iNormalizedWidthその値にしましょう。
iNormalizedWidthが奇数の場合、プログラムは常に間違った答えを返します。次の数字でのみ間違った答えが返ってきます:
11, 20, 25, 29, 35 - 48.
(48 は私のプログラムが処理する最大値です)。
これは私が書いた関数です:
typedef long long int int64;
#define BLOCK_A = 2;
#define BLOCK_B = 3;
/* main function, more macros, prototypes of other functions and
irrelevant information for the scope of my question */
vector< vector<int64> > iTileBricks(int iWidth) {
int iK, i, j, iMaxIterations, iEvenWidth, iOffset;
vector<int64> viBrickRange;
vector< vector<int64> > viBrickWall;
vector< vector<int64> > viResult;
iEvenWidth = iWidth % 2;
iK = (int)(iWidth/2); // The amount of all possible combinations that follow the pattern nCr(iN-i,2i)
iMaxIterations = iK/3 + 1; // By dividing all the possible combinations by 3, I am finding out how the maximum amount of iterations
for(i = 0; i < iMaxIterations; i++) {
iOffset = 2*i + iEvenWidth;
vector<bool> vAux(iK-i); // Creating a iK - i long vector. Test Case:
// Let dOriginalPanelWidth = 48
// iPanelWidth = 32
// iK = iPanelWidth/2 = 16
// iMaxIterations = iK/3 ~= 5
// iK - i = 16 - i Where 1 <= i <= 5
// For the first iteration of i the value of vAux will be:
if(iOffset <= iK-i) {
fill(vAux.begin() + iOffset, vAux.end(), true); // For the first iteration of i the value of vAux will be:
}
// vAux = [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
do { // In this block of code I'm generating all the possible layouts of bricks that can build
for(j = 0; j < iK-i; j++) { // a wall of 48" (or any value of width where 3 <= width <= 48 and (width % 1/2) == 0).
if(vAux[j] == false) {
viBrickRange.push_back(j); // Generating n-tuples with all possible combinations
}
}
viBrickWall.push_back(viBrickRange);
viBrickRange.clear();
} while(next_permutation(vAux.begin(), vAux.end()));
for(unsigned int a=0; a < viBrickWall.size(); a++) {
vector<int64> viTmp(iK-i);
fill(viTmp.begin(), viTmp.end(), BLOCK_A);
for(unsigned int b = 0; b < viBrickWall[a].size(); b++) {
viTmp[viBrickWall[a][b]] = BLOCK_B;
}
viResult.push_back(viTmp);
viTmp.clear();
}
viBrickWall.clear();
vAux.clear();
}
return viResult;
}
Python で書かれた動作するプログラムを見つけました。後者の関数は、Python 関数から C++ への移植にすぎません。それが役立つ場合は、参考までに次のとおりです。
def all_single_rows(width):
result = []
n = width / 2
width_parity = width % 2
for i in range(n/3 + 1):
for bits in combinations(range(n-i), 2*i + width_parity):
s = [2] * (n-i)
for bit in bits:
s[bit] = 3
result.append(s)
return result
これはかなり大きな関数 (および質問) ですが、これを一日中デバッグしようとしてきましたが、解決策を見つけることができませんでした。
最終値を生成する計算は他にもありますが、これは他の関数が失敗する原因となっている関数です。
特定の入力に対して答えが急上昇し、その後再び戻る理由についての理論を知りたいです。
私の関数と python で記述された関数を並べて比較すると、出力は同じですが、他の入力 (上記) では出力が異なります。
どんな助けでも大歓迎です。
どうもありがとう！