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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
#1

Двумерный массив с уникальными элементами - C++

07.05.2013, 21:44. Просмотров 625. Ответов 19
Метки нет (Все метки)

Доброго времени суток!.Помогите пожалуйста с этим разобраться ,я понимаю что это надо делать через тип данных bool возвращающий 0-ложь и 1-истина.Нужно чтобы как в судоку от 1-9 и в столбце и в строке...,и как подключить эту функцию к выдаваемой матрице..
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.05.2013, 21:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Двумерный массив с уникальными элементами (C++):

Двумерный массив с уникальными элементами в столбце - C++
Добрый день. Помогите пожалуйста решить задачу. Есть двумерный массив 3*5, который генерируется случайным образом. Необходимо сделать,...

Создать матрицу NxN с уникальными элементами - C++
Как создать неповторимый элементы матрицы NxN ???

Двумерный массив с неповторяющимися элементами - C++
Добрый вечер! Столкнулся с проблемкой, нужна помощь. Цель задачи: составить программу, которая найдет в двумерном массиве минимальный...

заполнить двумерный массив элементами в соответствии с рисунком - C++
массив 6x6 от 1 до 36 1 3 6 10 15 21 2 5 9 14 20 26 4 8 13 19 25 30 7 12 18 24 29 33 11 17 23 28 32 35 16 22 27 31 34 36 ...

Двумерный массив. Удалить строки с нулевыми элементами - C++
Здравствуйте! Нужна функция, которая удаляет строки двумерного массива, в которых содержится хотя бы один нулевой элемент. (Знаю, что...

Двумерный массив. Найти номера столбцов с отрицательными элементами и отобразить их на экране - C++
Само задание: Ввести двумерный массив E. Найти номера столбцов с отрицательными элементами и отобразить их на экране. Сделать блок-схему...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.05.2013, 21:52 #2
Сгенерировать все возможные варианты массивов или что?
0
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
07.05.2013, 22:06  [ТС] #3
ну вот допустим есть сгенерированый массив 9х9 в нем в строках и столбцах есть повторяющиеся элементы...
1 2 6 8 9 4 6 8 9
3 1 4 6 5 9 3 2 7
4 9 5 7 8 2 5 1 3
9 8 7 4 6 5 2 9 8
6 7 4 8 9 9 3 1 7
1 3 6 2 1 4 7 9 5
7 3 5 9 1 8 6 2 4
4 2 9 7 6 3 1 7 6
2 9 3 7 4 1 6 5 9
а нужно чтобы было так
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.05.2013, 22:17 #4
Ну так вот у тебя уже есть. Что на входе программы должно быть и что на выходе?
0
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
07.05.2013, 22:24  [ТС] #5
Массив генерируется случайным образом
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <time.h>
#include <conio.h>
void main()
{srand(time (NULL));
    for(int i=0;i<n;i++)
{   for(int j=0;j<n;j++)
 
{int a[n][n]=rand()%9+1;
    cout<<a[n][n];
    cout<<" ";
    }
    cout<<"\n";}
    _getch();
    }
а на выходе должно получится что-то вроде этого
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8
только не в такой простой последовательности..
ну и естественно каждый раз разное..
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.05.2013, 23:00 #6
Ну раз входящих условий никаких... Брутфорсом можно находить все подходящие варианты, проходя построчно и отбрасывая заведомо неподходящие. Но чтоб каждый раз разное... Можно в принципе рендомно генерировать одну строку, а потом из неё уже подбирать остальные. Но это будет не полный рандом, ибо все равно перебор по возрастающей будет до первого подходящего варианта, к примеру.
0
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
08.05.2013, 00:06  [ТС] #7
вот там по идее должно быть то что мне нужно но ... я С чет не очень понимаю...
Генерация массива целых случайных чисел, которые не повторяются
Генерация массива целых случайных чисел, которые не повторяются.
Генерация массива целых случайных чисел, которые не повторяются (быстрый алгоритм).
0
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
09.05.2013, 12:00  [ТС] #8
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
int checki(int a,int b)
{srand(time (NULL));
    int test[]={1,2,3,4,5,6,7,8,9};
    for (int i = 0; i < n; i++)
            {for (int j = 0; j < n; j++)
{do
                {  
                    a= test[rand()%9];
        for(b=0;b<j && a!=arr[i][b];b++);
                    } 
                while( b!=j );
                arr [i][j] = a ;
    }}
return arr[i][j];
}
int checkj(int a,int b)
{srand(time (NULL));
    int test[]={1,2,3,4,5,6,7,8,9};
    for (int i = 0; i < n; i++)
            {for (int j = 0; j < n; j++)
{do
                {  
                    a= test[rand()%9];
        for(b=0;b<i && a!=arr[b][j];b++);
                    } 
                while( b!=i );
                arr [i][j] = a ;
    }}
return arr[i][j];
}
Помогите! может кто знает как эти 2 функции объединить чтобы было вроде того как я писал выше...
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8
0
Tulosba
:)
Эксперт С++
4396 / 3239 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
09.05.2013, 12:44 #9
А если так:
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
 
int main()
{
    std::vector<int> v;
 
    for( int i=1; i<10; ++i )
        v.push_back(i);
 
    std::ostream_iterator<int> oit( std::cout, " " );
 
    for( int i=0; i<9; ++i )
    {
        std::random_shuffle( v.begin(), v.end() );
        std::copy( v.begin(), v.end(), oit );
        std::cout << std::endl;
    }
 
    std::system( "pause" );
    return 0;
}
Просто вывод на экран. Но в массив запихнуть не сложно.
0
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
09.05.2013, 13:12  [ТС] #10
так у вас же уникальность сохраняется только в строках...а мне нужно чтобы и в строке и столбце ..
0
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,678
09.05.2013, 15:11 #11
Вот пример на относительно простом алгоритме.

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

Чем больше массив, тем чаще он будет собираться, поэтому при размерности 9 на 9 и количестве в нем чисел от 1 до 9 массив будет генерироваться очень долго, из-за максимальной вероятности того, что в какой-то колонке встретится дубликат. Чтобы сократить время генерации для больших массивов, можно увеличить разброс генерируемых чисел.

Так как алгоритм достаточно прост, то сам по себе вообще не эффективен.
Если подходит и нужны комментарии, то опишу.

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
#include <iostream>
#include <ctime>
 
const int N=9,M=9; //Число колонок и строк
 
bool check_arrstroki(int Arr[])
{
    for (int i=0;i<N-1;i++)
    {
        for (int j=i+1;j<N;j++)
        {
            if (Arr[i]==Arr[j]) return 0;
        }
    }
    return true;
}
 
bool check_arrkolonki(int Arr[])
{
    for (int i=0;i<M-1;i++)
    {
        for (int j=i+1;j<M;j++)
        {
            if (Arr[i]==Arr[j]) return 0;
        }
    }
    return true;
}
 
void generator(int Arr[])
{
    while (!check_arrstroki(Arr))
    {
    for (int i=0;i<N;i++)
    {
        Arr[i]=rand()%100+1; //Разброс генерируемых чисел
    }
    }
}
 
void show_arrstroki(int Arr[])
{
    for (int i=0;i<N;i++)
    {
        std::cout<<Arr[i]<<"  ";
    }
    std::cout<<"\n";
}
 
void show_arr(int Arr[][M])
{
    for (int i=0;i<N;i++)
    {
        for (int j=0;j<M;j++)
        {
            std::cout<<Arr[i][j]<<"\t";
        }
        std::cout<<"\n";
    }
}
 
bool check_Arr(int Arr[][M])
{
    int ArrKolonki[M];
    //std::cout<<"\n";
 
     for (int i=0;i<M;i++)
     {
         for (int j=0;j<M;j++)
         {
            ArrKolonki[j]=Arr[j][i];            
         }  
        //std::cout<<"\n";
 
        for (int i=0;i<M;i++)
        {
        //  std::cout<<ArrKolonki[i]<<"  ";
        }
        if (!check_arrkolonki(ArrKolonki)) return false;
     }
 
 
    
    return true;
}
 
int main()
{
    int ArrStroki[N];
    int Arr[N][M];
    srand(time(NULL));
 
    
    while (!check_Arr(Arr))
    {
    for (int i=0;i<M;i++)
    {
    generator(ArrStroki);
    //show_arrstroki(ArrStroki);
 
       for (int k=0;k<N;k++)
       {
           Arr[i][k]=ArrStroki[k];
       }
 
    ArrStroki[0]=ArrStroki[1];
    }
    
    }
    
    show_arr(Arr);
    
 
    std::cin.get();
 
}
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
09.05.2013, 15:17 #12
Вот решение более сложной задачи - вторая встречная.
Дано поле 7*7. Необходимо заполнить все пустые клетки цифрами от 1 до 6 таким образом, чтобы в каждом столбце и в каждой строке каждая цифра встречалась ровно один раз. Одна клетка в каждом столбце и в каждой строке при этом останутся пустыми. Цифры слева, справа, снизу и сверху поля указывают, что именно эта цифра будет второй цифрой в данном направлении.
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#pragma hdrstop
#pragma argsused
 
#include <tchar.h>
#include <stdio.h>
#include <iostream>
#include <conio.h>
const int rowcols=7;
bool check(int row,int**table,int**condition) {
    int i,j,k;
    if (condition[0][row]!=0) {
        if (table[row][1]!=condition[0][row]) {
            if (table[row][2]!=condition[0][row]) return false;
                else
                    if((table[row][1]!=0)&&(table[row][0]!=0)) return false;
        }
        else
            if(table[row][0]==0) return false;
    }
    if (condition[1][row]!=0) {
        if (table[row][rowcols-2]!=condition[1][row]) {
            if (table[row][rowcols-3]!=condition[1][row]) return false;
                else
                    if(table[row][rowcols-2]!=0&&table[row][rowcols-1]!=0) return false;
        }
        else
            if (table[row][rowcols-1]==0) return false;
    }
    //check cols
    for (i = 0; i < rowcols; i++) {     //столбцы
        for (j = 0; j < rowcols; j++) {   //цифры
            int count=0;
            for (k=0; k<row+1; k++)    //строчки
                if (table[k][i]==j) count++;
            if (count>1) return false;
        }
    }
    if (row<rowcols-3)
        for (i = 0; i < rowcols; i++)
            if (table[row][i]==condition[3][i])
                return false;
    if (row==1) {
        for (i = 0; i < rowcols; i++) {
            if (condition[2][i]!=0) {
             if (table[1][i]!=condition[2][i]) {
                if ((table[0][i]!=0)&&(table[1][i]!=0)) return false;
             }
             else
             if (table[0][i]==0) return false;
            }
        }
    }
    if (row==2) {
       for (i = 0; i < rowcols; i++) {
           if (condition[2][i]!=0) {
            if (table[1][i]!=condition[2][i]&&table[2][i]!=condition[2][i]) return false;
            }
           }
    }
    if (row==rowcols-1) {
       for (i = 0; i < rowcols; i++) {
        if (condition[3][i]!=0)
            if (table[row-1][i]!=condition[3][i]) {
                if (table[row-2][i]!=condition[3][i]) return false;
                    else
                    if (table[row-1][i]!=0&&table[row][i]!=0) return false;
            }
            else
            if (table[row][i]==0) return false;
       }
    }
    return true;
}
void swap(int**table,int i, int j, int k) {
    int temp=table[i][j];
    table[i][j]=table[i][k];
    table[i][k]=temp;
}
bool generate(int i, int**current_table) {
    int j,k;
    if (current_table[i][0]==-1) {
        for (j=0; j<rowcols; j++) {
            current_table[i][j]=j;
        }
        return true;
    }
    else {
        // находим элемент меньше или равного последующему
        int pos = -1;
        for (j=rowcols-2;j>=0;j--)
            if (current_table[i][j] < current_table[i][j+1]) {
                pos=j;
                break;
            }
        if (pos == -1)
            return false; // текущая перестановка последняя в лексикографическом порядке
        // находим минимальный элемент превышающий найденый
        int value = current_table[i][pos];
        int swapIndex = -1;
        for (j=rowcols-1;j>=pos;j--)
        if (current_table[i][j]>value) {
            swapIndex = j;
            break;
        }
        swap(current_table,i,pos,swapIndex);
        //реверс подстроки правее индекса pos
        int f = pos+1, s = rowcols-1;
        while (f<s) {
            swap(current_table,i,f,s);
            f++;
            s--;
        }
        return true;
    }
}
bool rekurs(int i, int** current_table, int**condition_table) { //i- nomer tekushey stroki, cur - tekushaya tablica
 while (true) {
  if (generate(i,current_table)==false) { //generaciya stroki i po vozrastaniyu, vozvrashaet false pri nevozmojnosti
    current_table[i][0]=-1;
    return false;
   }
  if (check(i,current_table,condition_table)==true) {
    if (i<rowcols-1) {
        if (rekurs(i+1,current_table,condition_table)) {
            return true;
        }
    }
    else return true;
  }
  }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int i,j,k;
    FILE *f=fopen("input.txt","r");
    if (f==NULL) {
        std::cout<<"File input.txt not found"<<std::endl;
        getch();
        return 0;
    }
    int **condition=new int*[4];
    int **result=new int*[rowcols];
    for (i = 0; i < rowcols; i++) {
        result[i]=new int[rowcols];
        for (j = 0; j < rowcols; j++) {
            result[i][j]=-1;
        }
    }
    for (i = 0; i < 4; i++) {
        condition[i]=new int[rowcols];
        for (j = 0; j < rowcols; j++) {
            fscanf(f,"%d",&condition[i][j]);
            std::cout<<condition[i][j]<<" ";
        }
        std::cout<<std::endl;
    }
    std::cout<<std::endl;
    fclose(f);
    f=fopen("output.txt","w");
    if (f==NULL) {
        std::cout<<"Can't create file output.txt"<<std::endl;
        getch();
    }
    if (rekurs(0,result,condition)==false) {
        std::cout<<"There is no solution"<<std::endl;
        if (f!=NULL) fprintf(f,"There is no solution");
        }
    else
        for (i = 0; i < rowcols; i++) {
            for (j = 0; j < rowcols; j++) {
                if (result[i][j]==0) {
                    std::cout<<"  ";
                    if (f!=NULL) fprintf(f,"  ");
                }
                else {
                    std::cout<<result[i][j]<<" ";
                    if (f!=NULL) fprintf(f,"%d ",result[i][j]);
                }
            }
            std::cout<<std::endl;
            if (f!=NULL) fprintf(f,"\n");
        }
    fclose(f);
    for (i = 0; i < rowcols; i++) {
        delete [] result[i];
    }
    delete [] result;
    for (i = 0; i < 4; i++) {
        delete [] condition[i];
    }
    delete [] condition;
    std::cout<<std::endl<<"Press any key to exit...";
    getch();
    return 0;
}
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 15:43 #13
ShikiofDevil, Уже решал связанные с судоку задачи : Судоку. Задача довольно-таки интересная
тут такая фича, просто вводишь массив из нулей или вообще, просто, изначально обнуляешь и не вводишь ничего.
Но есть прикол 1, в той задаче я ещё учитывал блоки 3x3, в них тоже должно было быть всё уникальным

Добавлено через 52 секунды
ShikiofDevil, а у вас вообще очень простая задача, вам нужно просто 9 перестановок, которые отличаются циклическим сдвигом

Добавлено через 5 минут
ShikiofDevil,
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
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include "windows.h"
 
using namespace std; 
 
int main(){
    int n = 9;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    srand(GetTickCount());
    random_shuffle(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", a[(i + j)%n]);
        }
        puts("");
    }
    return 0;
}
1
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
09.05.2013, 17:34  [ТС] #14
а матрицей никак?,без использования вектора.И как я понял в судоку чтобы получить желаемого идет обычный сдвиг?
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 18:19 #15
ShikiofDevil, а зачем использовать двумерный массив, когда достаточно одномерного ? он вообще то память жрёт. Вектор это массив. Это не судоку, у вас не судоку. Нет в судоку, чтобы получить желаемого надо больше, а у вас всего лишь уникальность по столбцам и строкам....
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2013, 18:19
Привет! Вот еще темы с ответами:

Двумерный массив. Сумму элементов массива, расположенных между первым и последним отрицательными элементами - C++
приветствую всех. нужна ваша помощь с написанием программы на с++. помогите, пожалуйста, если кому не сложно. Определить массив A (m и...

Заполнить одномерный массив уникальными числами - C++
Помогите. Надо ввести количество элементов М, нижнюю границу g1, верхнюю границу g2, заполнить этот массив случайными натуральными числами...

Двумерный вектор. Взаимодействие с элементами вложенного уровня - C++
Добрый день. Ещё на НГ хотел игру сделать простенькую аркадную. Там экран делится на 41 столбец и ровно в рамках данных столбцов падают...

Как можно вложить двумерный массив в двумерный? - C++
Нужно написать программу перемножения двух матриц размерностью МxМ, элементы которых, матрицы размерностью КxК... Подскажите (желательно с...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
09.05.2013, 18:19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru