Программа на Python — C ++ выдает правильные ответы для определенных входных данных и неправильные для других. Я подозреваю переполнение типа данных

Я пытался решить проблему программирования, которая включает комбинаторику и динамическое программирование.

нажмите здесь, чтобы прочитать проблему

Хорошей новостью является то, что я уже решил это, но для определенных входных данных программа выдает неправильные ответы.

Программа принимает два числа в качестве входных данных.
Позволять w = argv[1], h = argv[2]

Я напишу это псевдоматематическим способом для более легкого представления

Например. Следующая «формула» означает, что моя программа принимает два параметра: w и h, и вывод x

T(w,h) = x

Я собираюсь представить теоретические результаты T(w,h) и результаты моей программы по R(w, h), Я на 100% уверен, что T(w, h) всегда будет правильный ответ.

Поехали:

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. ARGV1 = 20

2. 20 * 2 = 40

3. 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 бок о бок
для некоторых входов выход идентичен, а для некоторых других (показанных выше) выход отличается.

Любая помощь будет принята с благодарностью.

Большое спасибо!