任意N阶幻方算法实现

算法原理请参考：https://www.zhihu.com/question/23531676

先定义一些通用的函数，比如创建空幻方，删除幻方，打印幻方。

创建幻方

int **NewMagicS(int n) {

    int **magic = new int*[n];

    for (int k = 0; k < n; k++)

        magic[k] = new int[n];

    return magic;

}

删除幻方

void DeleteMagicS(int **magic, int n) {

    for (int k = 0; k < n; k++)

        delete[] magic[k];

    delete[] magic;

}

打印幻方

void ShowMagicS(int **magic, int n) {

    int i, j;

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++)

            printf("%-6d", magic[i][j]);

        printf("\n");

    }

}

一、奇数幻方算法实现：

辅助函数（实现算法）

void OddMagicSA(int **magic, int n, int value) {

    int i, j, total;

    //初始化二维数组

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++)

            magic[i][j] = 0;

    i = 0;

    j = n / 2;

    magic[i][j] = value++;

    for (total = 1; total < n*n; total++, value++) {//向右上角移动

        //调整位置

        if (!magic[(i - 1) == -1 ? n - 1 - i : i - 1][(j + 1) % n]) { //空闲

            i = (i - 1) == -1 ? n - 1 - i : i - 1;

            j = (j + 1) % n;

        }

        else //原位置下移一格(行变)

            i = (i + 1) % n;

        magic[i][j] = value;

    }

}

主函数（负责打印）

void OddMagicS(int n) {

    int **magic;

    if (n <= 0 || n == 1 || n == 2 || (n % 2 == 0)) return;

    magic = NewMagicS(n);

    OddMagicSA(magic, n, 1);

    //显示奇数幻方

    ShowMagicS(magic, n);

    DeleteMagicS(magic, n);

}

二、偶数幻方算法实现：

辅助函数（算法实现）

void EvenMagicSA(int **magic, int n, int value) {

    int i, j;

    //初始化二维数组

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++)

            magic[i][j] = 0;

    //分割为4x4格子，然后填充对角线位置为-1

    for (i = 0; i < n; i += 4)//i, j 表示4x4起点

        for (j = 0; j < n; j += 4) {

            //对角线填充

            for (int k = 0; k < 4; k++) {

                magic[i + k][j + k] = -1;

                magic[i + 3 - k][j + k] = -1;

            }

        }

    i = 0;

    for (; i < n; i++)

        for (j = 0; j < n; j++, value++) {

            //先填充4x4非对角线，从左向右，从上向下

            if (magic[i][j] != -1 && magic[i][j] == 0) magic[i][j] = value;

            //填充4x4对角线,左右向左，从下向上

            if (magic[n - 1 - i][n - 1 - j] == -1) magic[n - 1 - i][n - 1 - j] = value;

        }

}

主要函数（打印幻方）

void EvenMagicS(int n) {

    int **magic;

    if (n <= 0 || n == 1 || n == 2 || n % 4 != 0) return;

    magic = NewMagicS(n);

    EvenMagicSA(magic, n, 1);

    //显示偶数幻方

    ShowMagicS(magic, n);

    DeleteMagicS(magic, n);

}

三、最后一个幻方类型叫做奇偶幻方，算法实现：

增加一个幻方复制

void CopyMagicS(int **dstMagic, int sLine, int sColumn, int **srcMagic, int n) {

    for (int i = sLine, p = 0; p < n; i++, p++)

        for (int j = sColumn, q = 0; q < n; j++, q++)

            dstMagic[i][j] = srcMagic[p][q];

}

主要函数（算法实现）

void OddEvenMagicS(int n) {

    int **magic, **magicTemp, i, j, k, mid;

    if (!(n >= 0 && n != 1 && n != 2 && (n % 2 == 0 && n % 4 != 0))) return;

    magic = NewMagicS(n);

    magicTemp = NewMagicS(n / 2);

    //顺时针分成A,B,C,D四个象限，并且按照A, D, B, C的顺序以奇幻方方法填充

    i = j = 0;//A象限

    OddMagicSA(magicTemp, n / 2, 1);

    CopyMagicS(magic, i, j, magicTemp, n / 2);

    i = j = n / 2;//D象限

    OddMagicSA(magicTemp, n / 2, n / 2 * n / 2 + 1);

    CopyMagicS(magic, i, j, magicTemp, n / 2);

    i = 0;

    j = n / 2;//B象限

    OddMagicSA(magicTemp, n / 2, n / 2 * n / 2 * 2 + 1);

    CopyMagicS(magic, i, j, magicTemp, n / 2);

    i = n / 2;

    j = 0;//C象限

    OddMagicSA(magicTemp, n / 2, n / 2 * n / 2 * 3 + 1);

    CopyMagicS(magic, i, j, magicTemp, n / 2);

    k = (n - 2) / 4;

    //A, C象限交换

    for (int l = 0; l < n / 2; l++)

        for (int m = 0; m < k; m++)

            if (l == n / 4) {//中间行

                mid = magic[l][k + m];

                magic[l][k + m] = magic[n / 2 + l][k + m];

                magic[n / 2 + l][k + m] = mid;

            }

            else {

                mid = magic[l][m];

                magic[l][m] = magic[n / 2 + l][m];

                magic[n / 2 + l][m] = mid;

            }

    //B, D象限交换

    for (int l = 0; l < k - 1; l++) {//列

        for (int m = 0; m < n / 2; m++) {//行

            mid = magic[m][3 * n / 4 - l];

            magic[m][3 * n / 4 - l] = magic[n / 2 + m][3 * n / 4 - l];

            magic[n / 2 + m][3 * n / 4 - l] = mid;

        }

    }

    //显示奇偶数幻方

    ShowMagicS(magic, n);

    DeleteMagicS(magic, n);

    DeleteMagicS(magicTemp, n / 2);

}

所有代码均经过测试，结果正确。

巴特西

任意N阶幻方算法实现

最新文章

热门文章