Задача на нахождение похожих строк массива
19.02.2019, 21:58. Показов 751. Ответов 0
Нужно написать программу обрабатывающую матрицу N*M и находящую кол-во похожих на 1 строк(строки похожи, если состоят из одних элементов).
Сама программа вроде легкая, но чтобы ее оптимизировать нужно сначала каждую строку матрицы превратить в множество а затем отсортировать , вроде бы простая задача, но уже много времени не могу найти ошибку в функции "превращения" в множество (set). Если не трудно, подскажите.
| 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
| #include <stdio.h>
#include <stdlib.h>
#include <time.h>
void inic(char *, int N, int M);
int set(char *, int M, int i);
void eazySort(char *, int M, int i);
void finish_string(char *, int M, int i);
main()
{
register int N,M,M1;
printf("N/M\n");
scanf("%d",&N);
scanf("%d",&M);
char Arr[N*M];
inic(Arr,N,M);
printf("\n");
for (int i = 0; i <= N-1; i++)
{
M1 = set(Arr,M,i);
eazySort(Arr,M1,i);
finish_string(Arr,M1,i);
printf("\n");
}
}
void inic(char *arr, int N,int M)
{
srand(time(NULL));
for (int i = 0; i <= N-1; i++)
{
for (int j = 0; j <= M-1; j++)
{
*(arr+(i*M)+j) = rand() % 10;
printf("%d\t",*(arr+(i*M)+j));
}
printf("\n");
}
}
int set(char *arr, int M, int i)
{
int elem;
int M1 = M;
for (int j = 0; j <= M-1; j++)
{
elem = *(arr+(i*M)+j);
for ( int l = 0; l <= M-1; l++)
{
if (elem == *(arr+(i*M)+l) && j != l)
{
for ( int k = l; k <= M-1; k++)
{
*(arr+(i*M)+k) = *(arr+(i*M)+k+1);
}
M1--;
}
}
}
return M1;
}
void eazySort(char *arr, int M, int i)
{
register char newElement,location;
for (int j = 1; j <= M-1; j++)
{
newElement = *(arr+(i*M)+j);
location = j-1;
while(location >= 0 && *(arr+(i*M)+location) > newElement)
{
*(arr+(i*M)+location+1) = *(arr+(i*M)+location);
location--;
}
*(arr+(i*M)+location+1) = newElement;
}
}
void finish_string(char *arr, int M, int i)
{
for (int k = 0; k <= M-1; k++)
{
printf("%d\t",*(arr+(i*M)+k));
}
} |
|
Сама программа вот, но все тот же set... так и не работает
| 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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
| #include <stdio.h>
#include <stdlib.h>
#include <time.h>
void inic(char *, int N, int M);
int set(char *, int M, int i);
void eazySort(char *, int M, int i);
int seach(char *, int M , int i);
void finish_string(char *, int M, int i);
main()
{
register int N,M,M1,count = 0;
char flag = 0;
printf("N/M\n");
scanf("%d",&N);
scanf("%d",&M);
char Arr[N*M];
inic(Arr,N,M);
printf("\n");
for (int i = 0; i <= N-1; i++)
{
if (flag == 0)
{
M1 = set(Arr,M,i);
eazySort(Arr,M1,i);
finish_string(Arr,M1,i);
printf("\n");
flag++;
}
else
{
M1 = set(Arr,M,i);
eazySort(Arr,M1,i);
finish_string(Arr,M1,i);
printf("\n");
count += seach(Arr, M, i);
}
}
printf("\nAnswer: %d", count);
}
void inic(char *arr, int N,int M)
{
srand(time(NULL));
for (int i = 0; i <= N-1; i++)
{
for (int j = 0; j <= M-1; j++)
{
*(arr+(i*M)+j) = rand() % 10;
printf("%d\t",*(arr+(i*M)+j));
}
printf("\n");
}
}
int set(char *arr, int M, int i)
{
int elem;
int M1 = M;
for (int j = 0; j <= M-1; j++)
{
elem = *(arr+(i*M)+j);
for ( int l = 0; l <= M-1; l++)
{
if (elem == *(arr+(i*M)+l) && j != l)
{
for ( int k = l; k <= M-1; k++)
{
*(arr+(i*M)+k) = *(arr+(i*M)+k+1);
}
M1--;
}
}
}
return M1;
}
void eazySort(char *arr, int M, int i)
{
register char newElement,location;
for (int j = 1; j <= M-1; j++)
{
newElement = *(arr+(i*M)+j);
location = j-1;
while(location >= 0 && *(arr+(i*M)+location) > newElement)
{
*(arr+(i*M)+location+1) = *(arr+(i*M)+location);
location--;
}
*(arr+(i*M)+location+1) = newElement;
}
}
void finish_string(char *arr, int M, int i)
{
for (int k = 0; k <= M-1; k++)
{
printf("%d\t",*(arr+(i*M)+k));
}
}
int seach(char *arr, int M, int i)
{
for (int j = 0; j <= M-1; j++)
{
if (*(arr+(i*M)+j) != *(arr+j))
{
return 0;
}
}
return 1;
} |
|
0
|
(
