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

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

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

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

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

Доброго времени суток!.Помогите пожалуйста с этим разобраться ,я понимаю что это надо делать через тип данных bool возвращающий 0-ложь и 1-истина.Нужно чтобы как в судоку от 1-9 и в столбце и в строке...,и как подключить эту функцию к выдаваемой матрице..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.05.2013, 21:44     Двумерный массив с уникальными элементами
Посмотрите здесь:
Двумерный массив с уникальными элементами в столбце C++
Создать матрицу NxN с уникальными элементами C++
C++ Двумерный массив с неповторяющимися элементами
C++ Двумерный массив. Удалить строки с нулевыми элементами
заполнить двумерный массив элементами в соответствии с рисунком C++
Двумерный массив. Найти номера столбцов с отрицательными элементами и отобразить их на экране C++
Двумерный массив. Сумму элементов массива, расположенных между первым и последним отрицательными элементами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.05.2013, 21:52     Двумерный массив с уникальными элементами #2
Сгенерировать все возможные варианты массивов или что?
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
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.05.2013, 22:17     Двумерный массив с уникальными элементами #4
Ну так вот у тебя уже есть. Что на входе программы должно быть и что на выходе?
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
только не в такой простой последовательности..
ну и естественно каждый раз разное..
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.05.2013, 23:00     Двумерный массив с уникальными элементами #6
Ну раз входящих условий никаких... Брутфорсом можно находить все подходящие варианты, проходя построчно и отбрасывая заведомо неподходящие. Но чтоб каждый раз разное... Можно в принципе рендомно генерировать одну строку, а потом из неё уже подбирать остальные. Но это будет не полный рандом, ибо все равно перебор по возрастающей будет до первого подходящего варианта, к примеру.
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
08.05.2013, 00:06  [ТС]     Двумерный массив с уникальными элементами #7
вот там по идее должно быть то что мне нужно но ... я С чет не очень понимаю...
Генерация массива целых случайных чисел, которые не повторяются
Генерация массива целых случайных чисел, которые не повторяются.
Генерация массива целых случайных чисел, которые не повторяются (быстрый алгоритм).
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
Tulosba
:)
Эксперт С++
4393 / 3236 / 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;
}
Просто вывод на экран. Но в массив запихнуть не сложно.
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
09.05.2013, 13:12  [ТС]     Двумерный массив с уникальными элементами #10
так у вас же уникальность сохраняется только в строках...а мне нужно чтобы и в строке и столбце ..
daslex
1271 / 516 / 106
Регистрация: 02.08.2011
Сообщений: 2,665
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();
 
}
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;
}
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;
}
ShikiofDevil
11 / 11 / 1
Регистрация: 18.12.2011
Сообщений: 112
09.05.2013, 17:34  [ТС]     Двумерный массив с уникальными элементами #14
а матрицей никак?,без использования вектора.И как я понял в судоку чтобы получить желаемого идет обычный сдвиг?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2013, 18:19     Двумерный массив с уникальными элементами
Еще ссылки по теме:
C++ Заполнить одномерный массив уникальными числами
C++ Двумерный вектор. Взаимодействие с элементами вложенного уровня
Дан массив A[N]. заполнить массив В[N] элементами массива A[N], которые удовлетворяют двойному неравенству C++
C++ Дан массив А(n). Создать новый массив, элементами которого являются произведение A(i) на максимальный элемент массива A.
Дан массив A(N). Сформулировать массив B(M), элементами которого являются большие из двух рядом стоящих в массиве A чисел C++

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

Или воспользуйтесь поиском по форуму:
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.05.2013, 18:19     Двумерный массив с уникальными элементами #15
ShikiofDevil, а зачем использовать двумерный массив, когда достаточно одномерного ? он вообще то память жрёт. Вектор это массив. Это не судоку, у вас не судоку. Нет в судоку, чтобы получить желаемого надо больше, а у вас всего лишь уникальность по столбцам и строкам....
Yandex
Объявления
09.05.2013, 18:19     Двумерный массив с уникальными элементами
Ответ Создать тему
Опции темы

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