Двумерные массивы. Генерация уникальных элементов для каждой строчки и столбца
Понравилась задача по генерации элементов в двумерный массив. Смысл задачи в том, что имеется массив, размерностью N*N клеток. Каждую строчку надо заполнить значениями от 1 до N и каждую колонку надо заполнить значениями от 1 до N, причем ни в одной из строчек и ни в одной из колонок не должны встретится дубликаты.
Алгоритм решения этой задачи весьма прост: начинать заполнение каждой новой строки (или колонки) двумерного массива со значения, на единицу большего элементу предыдущей строки (или колонки), а после заполнения двумерного массива значениями — просто перемешать колонки и перемешать строки. Заполнение построчно или поколоночно определяется большим числом (больше строк — построчно, больше колонок — поколоночно).
ПРАВИЛЬНО
НЕПРАВИЛЬНО
1 2 3
3 1 2
2 3 1
1 2 3
2 3 1
2 1 3
Для понимания примера необходимо знать:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
//Visual Studio, Генерация уникальных элементов для каждой строчки и столбца #include <iostream> #include <iomanip> //setw #include <cstdlib> //srand using namespace std; void init_array(int **&ptr, int ROW, int COL) { //Функция, занимающаяся выделением памяти ptr = new int*[ROW]; for (int i = 0; i<ROW; i++) ptr[i] = new int[COL]; } void delete_array(int **ptr, int ROW) { //Функция, занимающаяся очисткой памяти for (int i = 0; i<ROW; i++) delete[]ptr[i]; delete[]ptr; } void fill_array(int** &ptr, const int ROW, const int COL) { //Функция, занимающаяся заполнением массива int count = 0; //число для заполнения ячйки массива if (COL < ROW) { //Если строк больше колонок, обходи поколоночно for (int i = 0; i < COL; i++) { for (int j = 0; j < ROW; j++) { ptr[j][i] = (count++) % ROW; } count = i + 1; } } else { //иначе заполняем стандартным способом for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { ptr[i][j] = (count++) % COL; //Записываем значение в ячейку массива } count = i + 1; } } } void mixer_cols(int **Arr, const int ROW, const int COL) //Функция тасует колонки. { int number; //Число, обозначающее номер колонки, которую надо поменять местом с текущей колонкой в цикле for (int k = 0; k < ROW; k++) { number = rand() % COL; //Случайный выбор номера колонки for (int i = 0; i < ROW; i++) for (int j = COL - 1; j < COL; j++) { if (number == j) continue; swap(Arr[i][number], Arr[i][j]); //Меняю колонки местами. } } } void mixer_strings(int **arr, const int ROW, const int COL) { int index = 0; //значение для выбора строки int *buf = 0; //указатель для временного хранения for (int i = 0; i < ROW; i++) { index = rand() % ROW; //Выбираем случайную строку if (i == index) continue; buf = arr[i]; arr[i] = arr[index]; arr[index] = buf; } } void print_array(int** ptr, const int ROW, const int COL) { //Функция вывода значений массива на экран for (int i = 0; i<ROW; i++) { for (int j = 0; j<COL; j++) { cout << setw(5) << ptr[i][j]; } cout << '\n'; } } int main() { srand(unsigned(time(0))); int **arr = 0; //Указатель на указатель как двумерный массив int N, M; //значения можно будет вводить в ходе работы программы, //но ограничусь указанием значений в исходном коде /*===== КВАДРАТНЫЙ МАССИВ БУДЕТ КРАСИВО ВЫГЛЯДЕТЬ =====*/ cout << '\n'; N = 5; M = 5; init_array(arr, N, M); fill_array(arr, N, M); mixer_cols(arr, N, M); //Тасую колонки двумерного массива mixer_strings(arr, N, M); //Тасую строки двумерного массива print_array(arr, N, M); delete_array(arr, N); cout << '\n'; /*===== МАССИВ, ГДЕ СТРОК БОЛЬШЕ, БУДЕТ ВЫГЛЯДЕТЬ НЕ ОЧЕНЬ, НО ЗАДАЧА РЕШЕНА =====*/ N = 9; M = 5; init_array(arr, N, M); fill_array(arr, N, M); mixer_cols(arr, N, M); //Тасую колонки двумерного массива mixer_strings(arr, N, M); //Тасую строки двумерного массива print_array(arr, N, M); delete_array(arr, N); /*===== МАССИВ, ГДЕ КОЛОНОК БОЛЬШЕ, БУДЕТ ВЫГЛЯДЕТЬ НЕ ОЧЕНЬ, НО ЗАДАЧА РЕШЕНА =====*/ cout << '\n'; N = 5; M = 9; init_array(arr, N, M); fill_array(arr, N, M); mixer_cols(arr, N, M); //Тасую колонки двумерного массива mixer_strings(arr, N, M); //Тасую строки двумерного массива print_array(arr, N, M); delete_array(arr, N); cin.ignore().get(); //Если будете вводить размерности вручную, чтобы окно не закрылось } |
Поскольку создаются таблицы с разным числом строк и разным числом колонок, выделение памяти и зачистка происходит при каждой необходимости воссоздать подобие массива.
Мне очень хотелось решить эту задачу не на квадратном массиве, а на любом прямоугольном. Из-за возможного разнобоя в числе строк и числе колонок нужно использовать два варианта заполнения: или заполнять обычным способом (построчно), или заполнять массив не очень привычным многим способом (поколоночно). Если этого не сделать, то в определённых случаях начнут случаться повторения, которых, согласно задаче, быть не должно.
Чтобы сделать массивы более-менее симпатичными — я использовал и перемешивание строк, и перемешивание колонок.
На заметку: Здесь использован механизм перемены мест колонок. Простой пример смены 1-й и 2-й колонок местами
|
1 |
for (int i=0;i<N;i++) swap(Arr[i][0],Arr[i][1]); //N - число строк, не забываем индексация массивов начинается с нуля |
6 комментариев на «“Двумерные массивы. Генерация уникальных элементов для каждой строчки и столбца”»
Добавить комментарий
Случайная книга в электронном формате
На главной странице 2 ссылки подряд на эту страницу
хм.. решения данной матрицы любой размерности как сразу пришло в голову только посмотрел на 2 ваши матрицы, тут одно вроде несложное правило, каждую следующую строку нужно сдвигать на 1 и повторений ни в строке ни в столбцах не будет, например первая строка у нас 1234567890, вторую строку сдвигаем на 1 и получаем 0123456789, далее следующую строку сдвигаем еще на 1 и получаем 9012345678, тое сть при сдвиге последнее число переносим на место первого и получаем матрицу где не в строке не в столбце нет повторений
1 2 3 4 5 6 7 8 9 0
0 1 2 3 4 5 6 7 8 9
9 0 1 2 3 4 5 6 7 8
8 9 0 1 2 3 4 5 6 7
7 8 9 0 1 2 3 4 5 6
6 7 8 9 0 1 2 3 4 5
5 6 7 8 9 0 1 2 3 4
4 5 6 7 8 9 0 1 2 3
3 4 5 6 7 8 9 0 1 2
2 3 4 5 6 7 8 9 0 1
хм.. также можно сдвигать на любое кол-во шагов не равное или не превышающее размерность матрицы тогда все будет выглядеть хаотичнее но не будет повторений.
Конечно пойдут, у тебя размерность массива по строкам больше чем элементов массива (элементов 5 а строк 9), повторения неизбежны и ничего тут не поможет.
И еще, почему когда я нажимаю на «Ответить» под чьим то комментарием то ничего не происходит? Просто исчезает написанный текст.
Матрица любой размерности — это матрица любой размерности, а не квадратная. Наверное комментарием выше имелось в виду квадратная матрица с произвольным количеством элементов в своей стороне.
Если ответить под автором сайта, то это как нажать ответить самому себе. В остальных случаях не могу подсказать почему.
Чтобы повторений не было, ни одна из размерностей массива (будь то строки или столбцы) не должно превышать количество (уникальных) элементов
Если число элементов в строках больше, чем в колонках, то уникализировать массив совсем просто.
Если число элементов в колонках больше, чем в строках, то для уникализации можно заполнять массив по колонкам.
Единственное, прямоугольный массив не будеть столь же опрятным, как квадратный.