Сложная задача по C++. Тема: сортировка матрицы (двумерного массива)

Question

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

Количество элементов в массиве предусматривает возможность создания квадратной матрицы. То есть если чисел 9 то матрица будет 3 на 3, если 25 то 5 на 5.

while(true)
    { // бесконечный цикл
 system("cls"); // очищаем экран
cout << "Введите количество элементов" << endl;
    cin >> m;
if (sqrt(m) == (long long)sqrt(m))break;  //Проверка что корень - целое число 
}

Количество повторяющихся элементов не может превышать корня всех элементов. То есть если чисел 9 то повторений может быть максимум 3 (как количество строк и столбцов).

while(true){
 cout << "Введите массив" << endl;
 for(int i=0; i<m; i++)
{
    while (!(cin>>(mas[i])) || (cin.peek() != '\n'))
{
    check ();
}
}
 int repeat=0;
  for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
             if(mas[i] == mas[j]) repeat++;
        }}
if (n >= repeat)break;
else{cout << "Из данных чисел невозможно построить матрицу удовлетворяющую условию задания" << endl;}
}

Мой код но без самой сортировки:

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <iomanip>

using namespace std;

void check ()
{
    cin.clear();
    while (cin.get() != '\n');
    cout << "Ошибка ввода!" << endl;
    cout << "Повторите ввод!" << endl;
}


int main()
{

 while(true){ // бесконечный цикл
 system("cls"); // очищаем экран

setlocale(LC_ALL, "");
int m;
//-------------------
while(true)
    { // бесконечный цикл
 system("cls"); // очищаем экран
cout << "Введите количество элементов" << endl;
    while (!(cin >> m) || (cin.peek() != '\n'))
{
    check ();
}
if (sqrt(m) == (long long)sqrt(m))break;
}
//-------------------
int n=sqrt(m);
int mas[m];
//-------------------
while(true){
 cout << "Введите массив" << endl;
 for(int i=0; i<m; i++)
{
    while (!(cin>>(mas[i])) || (cin.peek() != '\n'))
{
    check ();
}
}
 int repeat=0;
  for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
             if(mas[i] == mas[j]) repeat++;
        }}
if (n >= repeat)break;
else{cout << "Из данных чисел невозможно построить матрицу удавлеворяющую условию задания" << endl;}
}
//---------------------------------------Проверка массива
cout << "---------------" << endl;
for(int i=0; i<m; i++)
{
cout<<mas[i];
}
cout << "---------------" << endl;
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//------------------------------------ В данной части требуется помощь 
m=0;
int *mat[n][n];
for(int i=0; i<(n); i++)
 for(int j=0; j<(n); j++)
        {
        if (mat[i][j]){
        mat[i][j]=&mas[m];
        m++;}
        }
cout << "---------------" << endl;
for(int i=0; i<(n); i++)
    {
         for(int j=0; j<(n); j++)
    cout<<(*mat[i][j])<<"\t";
    cout<<"\n";
    }
cout << "---------------" << endl;
//------------------------------------
int menu;
cout<<""<<endl;
cout<<"Выполнить программу еще раз? (1-да, 2-нет)\n";
            cin>>menu;
            if(menu!=1)break;
        }
return 0;
}

Answer 1

А забавная задачка... Ну, вводить массу цифр - не мое, так что у меня эта матрица просто генерируется случайно, там уж сами меняйте.

#include <vector>
#include <iostream>
#include <iomanip>
#include <map>
#include <cmath>
#include <assert.h>

using namespace std;

vector<vector<int>> make(int m, map<int,int> els)
{
    vector<vector<int>> s(m,vector<int>(m,0));
    vector<vector<int>> f = s;
    // Расставляем дубли
    int col = 0;
    for(auto& x: els)
    {
        if (x.second > 1)
        {
            for(int j = 0; j < x.second; ++j)
            {
                s[(col+j)%m][j] = x.first;
                f[(col+j)%m][j] = 1;
            }
            col++;
            x.second = 0;
        }
    }
    // Расставляем остальные
    auto it = els.begin();
    if (it != els.end())
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < m; ++j)
                if (f[i][j] == 0)
                {
                    while (it->second == 0) it++;
                    s[i][j] = it->first;
                    it++;
                }
    return s;
}


int main(int argc, const char * argv[])
{
    srand(time(0));

    int n = 25;

    int m = sqrt(n)+0.5;
    if (m*m != n) { cout << n  << " - не квадрат!\n"; return 0; }

    map<int,int> els;
    for(int k, i = 0; i < n; ++i)
    {
        k = rand()%40;
        els[k]++;
        cout << k << " ";
    }
    cout << endl << endl;

    int dbls = 0, max_dbl = 0;
    for(auto x: els)
    {
        if (x.second > 1) dbls++;
        if (x.second > max_dbl) max_dbl = x.second;
    }
    if (dbls > m || max_dbl > m) { cout << "Решения нет!\n"; return 0; }

    auto v = make(m,els);

    for(auto r: v)
    {
        for(auto c: r) cout << setw(2) << c << " ";
        cout << endl;
    }

}

БЛОГ НА HUSL

Сложная задача по C++. Тема: сортировка матрицы (двумерного массива)

Ответы (1 шт):