Язык C isMagicsquare: какая логическая ошибка в коде моей функции?

Question

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

Ранее я уже обращался к этой проблеме:

"Что произойдет в вашем коде, если нет повторяющихся чисел, используются все числа, сумма в вашем последнем столбце верна, но ваш второй за последнимневерная сумма в столбце? "

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

Мой текущий код:

/* Magic Square */
#include <stdio.h>

#define MAX_N 100
#define TRUE  1
#define FALSE 0

int isMagicSquare(int square[MAX_N][MAX_N], int n);

int main(void) {
    int square1[MAX_N][MAX_N] = {
            {4, 9, 2},
            {3, 5, 7},
            {8, 1, 6}};

    // should print TRUE
    int check1 = isMagicSquare(square1, 3);
    if (check1 == TRUE) {
        printf("TRUE\n");
    } else {
        printf("FALSE\n");
    }

    int square2[MAX_N][MAX_N] = {
            {20,  6,  7, 17},
            { 9, 15, 14, 12},
            {13, 11, 10, 16},
            { 8, 18, 19, 5} };

            /*{ 1 , 2 , 3 , 4 , },
            { 5 , 6 , 7 , 8 , },
            { 9 , 10, 11, 12, },
            { 13, 14, 15, 16,} };*/

            /*{16, 2, 3, 13,}, 
            {5, 11, 10, 8 ,},
            {9,  7, 6, 12 ,},
            {4, 14, 15, 1, } };*/ 

    // should print FALSE
    int check2 = isMagicSquare(square2, 4);
    if (check2 == TRUE) {
        printf("TRUE\n");
    } else {
        printf("FALSE\n");
    }

    int square3[MAX_N][MAX_N] = {
            {17, 24,  1, 15,  8},
            {23,  5,  7, 16, 14},
            { 4,  6, 13, 22, 20},
            {10, 12, 19,  3, 21}, 
            {11, 18, 25,  9,  2}};

    // should print FALSE
    int check3 = isMagicSquare(square3, 5);
    if (check3 == TRUE) {
        printf("TRUE\n");
    } else {
        printf("FALSE\n");
    }

    return 0;
}

int isMagicSquare(int square[MAX_N][MAX_N], int n) {
    int row, col;
    int drow, dcol;
    int sum, sum1, sum2, sum3;
    int boolean = 0;

    //For Diagonals
    sum = 0;
    for (row = 0; row < n; row++) {
        for (col = 0; col < n; col++) {
            if (row == col)
                sum += square[row][col];
        }
    }

    for (row = 0; row < n; row++) {
        sum3 = 0;
        for (col = 0; col < n; col++) {
            sum3 += square[n-row-1][col]; 
        }
        if (sum == sum3)
            boolean = 1;
        else {
            return FALSE;
        }
    }

    //For Rows
    for (row = 0; row < n; row++) {
        sum1 = 0;
        for (col = 0; col < n; col++) {
            sum1 = sum1 + square[row][col];
        }
        if (sum == sum1)
            boolean = 1;
        else {
            return FALSE;
        }
    }

    //For Columns
    for (row = 0; row < n; row++) {
        sum2 = 0;
        for (col = 0; col < n; col++) {
            sum2 = sum2 + square[col][row];
        }
        if (sum == sum2)
            boolean = 1;
        else {
            return FALSE;
        }
    }

    if (boolean == 1) {
        //Check if All Numbers is used

        for (row = 0; row < n; row++) {
            for (col = 0; col < n; col++) {
                if(square[row][col] > n*n || square[row][col] < 0) {
                    boolean = 0;
                    break;
                }
            }
        }

        //Check for Repeating Numbers
        for (row = 0; row < n; row++) {
            for(col = 0; col < n; col++) {

                for(drow = row + 1; drow < n; drow++){
                    for(dcol = col + 1; dcol < n; dcol++) {
                        if(square[row][col] == square[drow][dcol]) {
                            boolean = 0;
                            break;
                        }
                    }   
                }
            }
        }
        // if Statement End
    }
    else {
        boolean = 0;
    }

    if (boolean == 1)
        return TRUE;
    else
        return FALSE;
}

Answer 1

Вы можете использовать более компактную схему, чтобы проверить, что все числа 1 .. (n*n) используются без дубликатов с использованием кода, такого как:

int counts[n * n];  // Can't use an initializer with a VLA
memset(counts, '\0', sizeof(counts));

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (square[i][j] <= 0 || square[i][j] > n * n)
            return FALSE;
        counts[square[i][j] - 1]++;  // Map 1..n*n to 0..n*n-1
        // if (++counts[square[i][j] - 1] > 1)
        //     return FALSE;
    }
}

for (int i = 0; i < n * n; i++)
{
    if (counts[i] != 1)
        return FALSE;
}

Поскольку есть элементы n*n для проверки, этот код используетпространство и время, которые являются линейными по отношению к количеству элементов в магическом квадрате, который находится в пределах постоянного фактора оптимального.

Answer 2

кажется, что переменная sum3 повторно инициализируется в 0 внутри цикла вычислений, плюс проверка равенства диагональной суммы должна быть вне цикла.

Я бы переработал ее следующим образом:

//For Diagonals
sum = 0;
sum3 = 0;
for (row = 0; row < n; row++) {
    sum  += square[row][row];
    sum3 += square[row][n - 1 - row];
}
if (sum == sum3)
    boolean = 1;
else {
    return FALSE;
}

Кстати, я немного упростил вычисление диагонали, поскольку оно является линейным, нет необходимости в 2 вложенных циклах.

Я обнаружил некоторые другие ошибки в окончательных проверках:

-0 не должнобыть действительным значением

- возврат вместо простого прерывания (разрыв существует только во внутреннем цикле, внешний цикл продолжается)

for (row = 0; row < n; row++) {
    for (col = 0; col < n; col++) {
        if(square[row][col] > n*n || square[row][col] <= 0) {
            return FALSE;
        }
    }
}

//Check for Repeating Numbers
int storedNumbers[n * n];
for (row = 0; row < n; row++) {
    for(col = 0; col < n; col++) {
        storedNumbers[row + n * col] = square[row][col];
    }
}

Затем сканируйте сохраненные числа на наличие дубликатов. Поиск дублирующихся значений в массиве

cheers