Форум программистов, компьютерный форум CyberForum.ru

Латинский квадрат - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.65
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
27.11.2011, 15:13     Латинский квадрат #1
Латинский квадрат. Латинским квадратом пордка n называется квадратная таблица размером nxn каждая строка и каждый столбец которой содержит все числа от 1 до n. Проверить является ли заданная целочисленная матрица латинским квадратом. Я так понимаю в этой задаче три этапа: проверка введенных данных (действительно ли квадрат), действительно ли числа в матрице от 1 до n, сравнение элементов строк и столбцов чтобы они не были равны. Но как это реализовать, вообще массивы плохо понимаю, а задачу нужно сделать...
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.11.2011, 15:18     Латинский квадрат #2
Ничего трудного здесь нет. Достаточно, чтобы каждая строка и столбец были некоторыми перестановками элементов множества {1,2,...,n}. Строки и столбцы друг с другом не надо сравнивать.
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
27.11.2011, 15:26  [ТС]     Латинский квадрат #3
Ну как это сделать, помоги пожалуйста

Добавлено через 7 минут
Пользователь вводит сам матрицу, предварительно введя размерность N
alenka-46
16 / 16 / 2
Регистрация: 28.04.2011
Сообщений: 38
27.11.2011, 15:36     Латинский квадрат #4
Можно уточнить: как задана сама матрица как одномерный массив или как двумерный? И как нужно её задавать: пользователь сам должен ввести числа или они уже даны и написаны в самой программе?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.11.2011, 15:37     Латинский квадрат #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
C
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
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define N 3
 
int RowPerestanovka(int a[N][N], int k)
{
   int flag = 1, i, *count = (int *)calloc(N+1, sizeof(int));
   for (i = 0; i < N && flag; i++)
      if (a[k][i] >= 1 && a[k][i] <= N)
         count[a[k][i]]++;
      else flag = 0;
   for (i = 1; i <= N && flag; i++)
      if (count[i] != 1)
         flag = 0;
   free(count);
   return flag;
}
 
int StPerestanovka(int a[N][N], int k)
{
   int flag = 1, i, *count = (int *)calloc(N+1, sizeof(int));
   for (i = 0; i < N && flag; i++)
      if (a[i][k] >= 1 && a[i][k] <= N)
         count[a[i][k]]++;
      else flag = 0;
   for (i = 1; i <= N && flag; i++)
      if (count[i] != 1)
         flag = 0;
   free(count);
   return flag;
}
 
void Init(int a[N][N])
{
   int i, j;
   for(i = 0; i < N; i++)
      for(j = 0; j < N; j++)
         scanf("%d", &a[i][j]);
}
 
void Print(int a[N][N])
{
   int i, j;
   for(i = 0; i < N; i++)
   {
      for(j = 0; j < N; j++)
         printf("%d ", a[i][j]);
      putchar('\n');
   }
}
 
int Check(int a[N][N])
{
   int i, flag;
   for(i = 0, flag = 1; i < N && flag; i++)
      if (!RowPerestanovka(a, i) || !StPerestanovka(a, i))
         flag = 0;
   return flag;
}
 
int main()
{
   int a[N][N];
   Init(a);
   Print(a);
   printf("%s\n", Check(a) ? "yes" : "no");
   getch();
   return 0;
}
kompnet
41 / 1 / 0
Регистрация: 11.10.2011
Сообщений: 100
27.11.2011, 15:56  [ТС]     Латинский квадрат #6
Спасибо конечно. Но это слишком сложно для меня, мне нужно решение в лоб. Вот моё начало:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <conio.h>
void main()
{ int n,j,i;
  int A[100][100];
  printf("Vvedite razmer massiva n: ");
  scanf("%d",&n);
  printf("Vvedite elementy massiva\n");
  for (i=0; j<n; i++)
    for (j=0; j<n; j++)
  scanf("%d",A[i][j]);
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.11.2011, 16:03     Латинский квадрат #7
Цитата Сообщение от kompnet Посмотреть сообщение
Спасибо конечно. Но это слишком сложно для меня, мне нужно решение в лоб.

Не по теме:

Хорошо, прописывайте сами проверку на перестановку. Только 15 драгоценных минут зря на вас потратил.

alenka-46
16 / 16 / 2
Регистрация: 28.04.2011
Сообщений: 38
27.11.2011, 19:49     Латинский квадрат #8
Можно решить эту задачу с помощью одномерного динамического массива ( динамические массивы позволяют существенно экономить память, не нужно будет создавать массив 100 на 100, если не известен размер квадрата заранее) .

Добавлено через 53 минуты
C++
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
#include <iostream.h>
#include <conio.h>
 
void main()
{
int i, j,       // счётчики для циклов,
    n,         // количество элементов в строке 
    flag=0,  // переменная, определяющая действительно ли это латинский квадрат
    sum=0,   // фактическая сумма элементов в строке или столбце
    summa;  // сумма элементов в строке или столбце, которая должна быть
 
clrscr(); // очистка экрана
 
cout <<"\n Введите количество чисел в строке квадрата: ";
cin >> n; 
 
// рассчитаем сумму элементов в строке квадрата по след. формуле n*(n+1)/2
// (результат всегда будет целым числом)
 
summa=n*(n+1)/2;
 
// создадим одномерный динамический массив для элементов квадрата
 
int *mass = new int [n*n];
 
// попросим пользователя произвольно заполнить квадрат
 
for(i=0; i<n; i++)
   for(j=0; j<n; j++)
   {
      cout << "\n Введите элемент строки " <<i+1 <<" столбца " <<j+1 <<" : ";
      cin >> mass[i*n+j];
   }
 
// проверка элементов строк
 
for(i=0; i<n; i++)
{
   for(j=0; j<n; j++)
   {
      if(mass[i*n+j]<1 || mass[i*n+j]>n)   // если один из элементов строки меньше 1 или больше n ,
      {                                                 // то это не латинский квадрат,
          i=n;                                          // приравниваем счётчики i и j к n,
          j=n;                                          // что обеспечивает выход из циклов for
          flag=1;                                      // объединичиваем flag  для нелатинских квадратов
      }
      sum+=mass[i*n+j];                         // прибавляем к sum очередной элемент строки
   }
   if(sum!=summa)   // если сумма элементов в строке не равна нужной summa,
   {                      // то это не латинский квадрат (дальше делаем то же самое)
       i=n; 
       j=n; 
       flag=1;
   }
   sum=0;              // обнуляем переменную sum
}
 
// проверяем элементы столбцов (практически также)
if(flag==0)    // если в строках не обнаружено несоответствие, то проверяем столбцы
{
   for(i=0; i<n; i++)
   {
      for(j=0; j<n; j++)
      {
         if(mass[i+j*n]<1 || mass[i+j*n]>n)   // если один из элементов столбца меньше 1 или больше n ,
         {                                                 // то это не латинский квадрат,
            i=n;                                          // приравниваем счётчики i и j к n,
            j=n;                                          // что обеспечивает выход из циклов for
            flag=1;                                      // объединичиваем flag  для нелатинских квадратов
         }
         sum+=mass[i+j*n];                         // прибавляем к sum очередной элемент строки
      }
      if(sum!=summa)   // если сумма элементов в строке не равна нужной summa,
      {                      // то это не латинский квадрат (дальше делаем то же самое)
          i=n; 
          j=n; 
          flag=1;
      }
      sum=0;              // обнуляем переменную sum
   }
}
 
clrscr(); // очистка экрана
 
// печать массива в виде квадрата
 
cout <<"  Квадрат: ";
 
for(i=0; i<n; i++)
   {
   cout <<"\n ";
   for(j=0; j<n; j++)
      cout << mass[i*n+j] <<"\t";
   }
   
if(flag==0)
   cout << "\n Данный квадрат действительно латинский";
else
   cout << "\n Квадрат не является латинским";
 
}
Добавлено через 8 минут
ПРОВЕРЬТЕ эту программу на ошибки, они там могут быть (если что - пишите)
// В этой программе можно было использовать обычные массивы, а не динамические (смотря что требует задача). также можно было сделать двумерный массив-матрицу ( но с одномерным мне было удобнее)
//Вместо cout и cin можно использовать printf() и scanf(), тогда вместо <iostream.h> подключают <stdio.h>

В общем, главное разберитесь в алгоритме, надеюсь эта программа хоть чем-то поможет
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.11.2011, 20:37     Латинский квадрат #9
alenka-46, на всякий случай. Сложность алгоритма проверки массива на перестановку в вашем алгоритме O(n^2), в посте 5 - O(n). То есть можно значительно оптимизировать. Но это так, для заметки
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.06.2013, 12:14     Латинский квадрат
Еще ссылки по теме:

Судоку (латинский квадрат) C++
C++ Квадрат
Комментарии к программе латинский квадрат C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
tatarin4555
10 / 10 / 0
Регистрация: 20.11.2012
Сообщений: 156
Записей в блоге: 1
17.06.2013, 12:14     Латинский квадрат #10
Цитата Сообщение от alenka-46 Посмотреть сообщение
Можно уточнить: как задана сама матрица как одномерный массив или как двумерный? И как нужно её задавать: пользователь сам должен ввести числа или они уже даны и написаны в самой программе?
как я понял это двумерный массив, и пользователь сам должен задавать размер введя n
Yandex
Объявления
17.06.2013, 12:14     Латинский квадрат
Ответ Создать тему
Опции темы

Текущее время: 02:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru