2

我一直在努力提高 C++ 水平，所以我一直在解决为编程竞赛设计的问题。我几天前就开始了这个问题，并且无法解决我的一生。我需要一些关于我的算法以及如何修复它的帮助。这是问题所在：ACM Image Compression problem

我的代码：我在下面解释。

#include "Compress.h"
using namespace std;

Compress::Compress(){
    size = 0, threshold = 0, nRows=0, nCols=0;
    // Enter in a file name
    cout << "Welcome. Please type in the name of the file to read the numbers.\n";
    cin >> readFileName;

    inFile.open(readFileName.c_str());
    if(!inFile.is_open()) {
        cout << "Failed to open the file! Press Enter to exit..." << endl;
        exit(1);
    }

    //Finding the array size and threshold
    inFile >> size >> threshold;

    nRows = size;
    nCols = size;
    topright = size;
    bottomleft = size;

    //Let's make the array
    // creating the columns
    compressArray = new int* [nCols];

    // creating the rows
    for (int r = 0; r < nRows; r++){
        compressArray[r] = new int[nRows];
    }

    // FIll the array
    for (int i = 0; i < nRows; i++){
        for (int j = 0; j < nCols; j++){
            inFile >> compressArray[i][j];
        }
    }

    inFile.close();

    // Show before editing.
    print();
    work(0, nRows, 0, nCols);

}
Compress::~Compress(){
    for (int i = 0; i < nRows; i ++){
        delete compressArray[i];
    }
    delete [] compressArray;
}


void Compress::work(int start_x, int end_x, int start_y, int end_y){
    int nb_blacks = 0;
    int nb_whites = 0;
    int total_blocks = 0;
    int majority = 0;
    int percent = 0;

     cout << start_x << end_x << start_y << end_y << "\n------\n";

    for(int i = start_x; i < end_x; i++){
        for(int j = start_y; j < end_y; j++){
            if(compressArray[i][j] == 1){
                nb_blacks++;
            }
        }
    }

    total_blocks = ((end_x - start_x) * (end_y - start_y));
    nb_whites = total_blocks - nb_blacks;

    // give the max back
    majority = max(nb_blacks, nb_whites);
    // find the percent of the highest amount of colored blocks.
    percent = ((majority*100)/total_blocks);

    cout << "\n----\nPercent: " << percent << " Threshold: " << threshold  << endl;



    // majority/total_blocks is determining the percent of the greater
    // color in the box. We are comparing it to the threshold percent.
    if (percent >= threshold){
        for(int i = start_x; i < end_x; i++){
            for(int j = start_y; j < end_y; j++){
                if(nb_blacks > nb_whites) compressArray[i][j] = 1;
                else compressArray[i][j] = 0;
            }
        }
    }
    else {
            topright = topright/2;
            bottomleft = bottomleft/2;

            work(start_x, (end_x/2), (topright), end_y);
            work(start_x, (end_x/2), start_y, (end_y/2));
            work((bottomleft), end_x, start_y, (end_y/2));
            work((bottomleft), end_x, (topright), end_y);

    }

}

void Compress::print(){
    for (int r = 0; r < nRows; r++){
        for (int c = 0; c < nCols; c++){
            cout << compressArray[r][c];
        }
        cout << endl;
    }
}

所以，我的程序所做的是计算图像中黑色方块的数量（1）。然后将其与白色方块（0）的数量进行比较。无论哪个更大，都会根据图像中的正方形数量转换为百分比。它将它与阈值进行比较。如果阈值小于百分比......整个图像变成了大多数颜色。

如果阈值更高......它会分成四个递归部分并放大。它将从右上角开始，然后是左上角，左下角和右下角。

我的程序适用于 4 x 4 的正方形，因为它正确地分成了四个部分。但是，对于 8 x 8 的正方形……如果需要将其分解为小于四个部分，那么一切都会一团糟。

我知道它为什么这样做。我放大递归函数的算法是错误的。如果正方形是 8 x 8 ... 参数将类似于

0, 8, 0, 8 = 看整个正方形

0、4、4、8 = 右上角

使用 4 x 4 0、2、6、8 的角 = 看着最小的右上角

2乘2的正方形。

我只是不知道可以得到我需要的数学函数。我不知道如何解决 8 x 8 方格的问题。我的代码甚至可以修复吗？还是我需要想出另一种解决方法？如果是这样，怎么做？

谢谢

4

2 回答 2

2

修复！数学函数只是一种痛苦。

头功能

#include<cstdlib>
#include<iostream>
#include<string>
#include<fstream>


using namespace std;

class Compress{
    public:
        Compress();
        ~Compress();
        void input();
        void work(int start_x, int end_x, int start_y, int end_y);
        void print();

    private:
        int size;
        int threshold;
        int** compressArray;
        int nRows, nCols;

        string readFileName;
        ifstream inFile;
};

文件

#include "Compress.h"
using namespace std;

Compress::Compress(){
    size = 0, threshold = 0, nRows=0, nCols=0;
    // Enter in a file name
    cout << "Welcome. Please type in the name of the file to read the numbers.\n";
    cin >> readFileName;

    // Open the file.
    inFile.open(readFileName.c_str());
    if(!inFile.is_open()) {
        cout << "Failed to open the file! Press Enter to exit..." << endl;
        exit(1);
    }

    //Finding the array size and threshold
    inFile >> size;

    nRows = size;
    nCols = size;

    // Enter a threshold.
    cout << "Enter the desired threshold between 50-100: ";
    cin >> threshold;

    // Keep asking for the desired threshold until it is given.
    while (threshold < 50 || threshold > 100){
        cout << "\nIncorrect Threshold.\n";
        cout << "Enter the desired threshold between 50-100: ";
        cin >> threshold;
    }


    //Let's make the array
    // creating the columns
    compressArray = new int* [nCols];

    // creating the rows
    for (int r = 0; r < nRows; r++){
        compressArray[r] = new int[nCols];
    }

    // FIll the array
    for (int i = 0; i < nRows; i++){
        for (int j = 0; j < nCols; j++){
            inFile >> compressArray[i][j];
        }
    }

    inFile.close();

    // Show before editing.
    print();
    work(0, nRows, 0, nCols);

}
Compress::~Compress(){
    for (int i = 0; i < nRows; i ++){
        delete compressArray[i];
    }
    delete [] compressArray;
}


void Compress::work(int start_x, int end_x, int start_y, int end_y){
    int Size = end_y - start_y; // Finding the midpoints.
    int nb_blacks = 0;
    int nb_whites = 0;
    int total_blocks = 0;
    int majority = 0;
    int percent = 0;

//    Testing everything.

//    cout << "\nx1, y1: " << start_x << "," << start_y << " x2,y2: " << end_x << "," << end_y << endl;
//    for (int r = start_x; r < end_x; r++){
//        for (int c = start_y; c < end_y; c++){
//            cout << compressArray[r][c];
//        }
//        cout << endl;
//    }

    // Initial case. If 1, break and start returning results
    if (end_x <= start_x || end_y <= start_y){
        return;
    }

   //  Keep breaking it down until it reaches 1.
    else {
        // Count the Number of Black pieces
        for(int i = start_x; i < end_x; i++){
            for(int j = start_y; j < end_y; j++){
                if(compressArray[i][j] == 1){
                    nb_blacks++;
                }
            }
        }

        // Find the total and number of white pieces.
        total_blocks = ((end_x - start_x) * (end_y - start_y));
        nb_whites = total_blocks - nb_blacks;

        // give the max back
        majority = max(nb_blacks, nb_whites);
        // find the percent of the highest amount of colored blocks.
        percent = ((majority*100)/total_blocks);

//        cout << "Percent: " << percent << " Threshold: " << threshold  << "\n-----\n";


        // majority/total_blocks is determining the percent of the greater
        // color in the box. We are comparing it to the threshold percent.
        if (percent >= threshold){
            for(int i = start_x; i < end_x; i++){
                for(int j = start_y; j < end_y; j++){
                    if(nb_blacks > nb_whites) compressArray[i][j] = 1;
                    else compressArray[i][j] = 0;
                }
            }
        }

        // Keep breaking down until we reach the initial case.
        else {
            work((end_x - (Size/2)), (end_x), (start_y), (start_y + (Size/2)));
            work(start_x, (start_x + (Size/2)), (start_y), (start_y + (Size/2)));
            work((start_x), (start_x + (Size/2)), (end_y - (Size/2)), end_y);
            work((end_x - (Size/2)), end_x, (end_y - (Size/2)), end_y);
//
//            work((start_x), (mid_x), (mid_y), end_y);
//            work(start_x, (mid_x ), (start_y), (mid_y));
//            work((mid_x), end_x, start_y, (mid_y));
//            work((mid_x), end_x, (mid_y), end_y);
        }
    }
}

void Compress::print(){

    // Print the function
    cout << "\nImage: " << threshold << "%\n";
    for (int r = 0; r < nRows; r++){
        for (int c = 0; c < nCols; c++){
            cout << compressArray[r][c];
        }
        cout << endl;
    }
}
于 2012-11-08T18:51:59.327 回答
0

首先，你的阅读习惯有一些问题：

第二个数组创建循环是错误的，应该nCols用作循环的限制而不是nRows：

// creating the rows
for (int r = 0; r < nCols; r++){
    // Remember you're creating the "row"s for every column
    compressArray[r] = new int[nRows];
}

根据问题阐述，输入格式在位图像素之间不包含空格，因此您必须读取一行数据，然后遍历该行以提取单个字符：

// FIll the array
for (int i = 0; i < nRows; i++){
    // You should #include <string> for this to work
    string line;
    inFile >> line;
    for (int j = 0; j < nCols; j++) 
        compressArray[i][j] = line[j] - '0';
}

阅读完成后，您可以对work例程进行一些改进：

您要查找的公式不是火箭科学，请看下图：

在此处输入图像描述

只需像这样对位图进行分区，并对每个扇区进行相应的调用work（这里没有看到top/bottom-right/left变量的用途）

您的算法是递归算法，但没有初始情况，因此您的算法无限期执行，您应该在任何递归调用之前检查start和之间的差异是否为 0。end

还有其他警告，但您应该先解决这些问题，然后再继续

IMO，你解决这个问题的想法很好，只是需要一点点打磨

希望这可以帮助！

PS： 将OOP基础知识（例如课程）应用于一般软件开发是一个非常好的（如果不是最好的）实践，但是对于编程竞赛考虑时间因素和开发解决方案的软件复杂性，还不错，但请考虑到，在许多情况下，它可能会导致您浪费时间并增加一些不必要的复杂性

于 2012-11-07T05:43:07.137 回答