首页 > 代码库 > 金币阵列问题

金币阵列问题

题目不在描述,见计算机算法设计与分析习题解答(第二版)王晓东 第6页

/*
 * CoinSort.cpp
 *
 *  Created on: Dec 4, 2014
 *      Author: hujianjie
 */
#include<iostream>
using namespace std;
int Max = 10;
int n, m, count, best;
bool flag;
int arrOld[10][10];
int arrNew[10][10];
int arrMid[10][10];

void copy(int arr1[10][10], int arr2[10][10]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            arr1[i][j] = arr2[i][j];
        }
    }
}
void transRow(int row) {
    for (int i = 0; i < m; i++) {
        //    arrNew[row][i] = arrNew[row][i] ^ 1;
        arrOld[row][i] = arrOld[row][i] ^ 1;
    }
    cout << "transRow" << endl;
    count++;

}
void transColum(int mid, int tem) {
    int temp;
    for (int k = 0; k < n; k++) {
        //temp = arrNew[k][mid];
        //arrNew[k][mid] = arrNew[k][tem];
        //arrNew[k][tem] = temp;
        temp = arrOld[k][mid];
        arrOld[k][mid] = arrOld[k][tem];
        arrOld[k][tem] = temp;
    }
    cout << "transColum" << endl;
    count++;

}
bool isSame(int mid, int tem) {
    for (int k = 0; k < n; k++) {
        if (arrOld[k][tem] != arrNew[k][mid]) {
            return false;
        }
    }
    return true;
}

int main() {
    flag = false;
    count = 0;
    cout << "Please input row n and colum m !" << endl;
    cin >> n >> m;
    cout << "Please input old  !" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arrOld[i][j];
        }
    }
    cout << "Please input New  !" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arrNew[i][j];
        }
    }
    //copy(arrMid, arrNew);
    copy(arrMid, arrOld);
    best = n + m + 1;
    for (int colum = 0; colum < m; colum++) {
        cout << colum << endl;
        //copy(arrNew,arrMid);
        copy(arrOld, arrMid);
        count = 0;
        //将每一列转换成第一列
        if (colum != 0)
            transColum(0, colum);
        //比较第一列的每一行,不同的则将其取反
        for (int row = 0; row < n; row++) {
            if (arrNew[row][0] != arrOld[row][0]) {
                transRow(row);
            }
        }
        //在第一行确定并翻转之后,比较剩下的列
        for (int mid = 1; mid < m; mid++) {
            for (int tem = mid; tem < m; tem++) {
                if (isSame(mid, tem)) {
                    if (mid != tem)
                        transColum(mid, tem);
                    flag = true;

                } else {
                    flag = false;
                }
            }
        }
        if (flag == true && count < best)
            best = count;
    }
    if (best < (m + n + 1))
        cout << "The best steps are : " << best << endl;
    else
        cout << "Can‘t finished! " << endl;
    return 0;
}
/*
 1 0 1
 0 0 0
 1 1 0
 1 0 1
 *
 *
 1 0 1
 1 1 1
 0 1 1
 1 0 1
 *
 *
 *
 *
 */
C 语言写的不好,思路是:将初始矩阵的每一列尝试作为目标的第一列,按枚举的思路一列一列的比较

金币阵列问题