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

Алгоритм нахождения покрытия, близкого к кратчайшему - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Вопрос про наследование. http://www.cyberforum.ru/cpp-beginners/thread208784.html
Добрый день всем! Возможно ли создать производный класс в который будут помещены 2 объекта базового класса с возможностью переопределения методов последнего? напрмер class a { int x; public a(int y) {x=y;} virtual int GetX() const {return x;} }
C++ линейные списки, удаление последнего эллемента списка нужно написать функцию удаления последнего эллемента списка, помогите пожалуйста #include <iostream.h> #include <stdlib.h> #include <stdio.h> #include <conio.h> struct Elem {int data; Elem*next;}; Elem*create (int n) {Elem*pb = new Elem; pb -> data = n; pb -> next = 0; return pb;} void showlist ( Elem*pb) http://www.cyberforum.ru/cpp-beginners/thread208780.html
C++ Из последовательности чисел выбрать элементы, делящиеся на 3
Из последовательности чисел y1, y2, ,…,yn выбрать элементы, делящиеся на 3. Подсчитать их число и вывести их порядковые номера в массиве. Подскажите примерно, как выбрать эти элементы?
интеграл C++
Всем доброго времени суток, нужно решить интеграл
C++ Оператор цикла с предусловием http://www.cyberforum.ru/cpp-beginners/thread208752.html
Используя оператор цикла с предварительным условием, вычислить сумму конечного числа слагаемых. При вычислении члена ряда использовать рекурентное соотношение. Значение x ввести с клавиатуры.http://www.cyberforum.ru/attachment.php?attachmentid=53608&d=1292095002
C++ DLL на C++ Доброго времени суток, уважаемые форумчани! У меня собственно такой вопрос: Не могли бы Вы написать код для DLL на C++ который нужен для выполнения такого задания - перемножить два беззнаковых числа длиной 64 бита каждое. Заранее спасибо. подробнее

Показать сообщение отдельно
Cheshire Cat
1 / 1 / 1
Регистрация: 11.12.2010
Сообщений: 14
11.12.2010, 23:23     Алгоритм нахождения покрытия, близкого к кратчайшему
Необходимо найти покрытие, близкое к кратчайшему, по методу "минимальный столбец - максимальная строка".
Описание алгоритма:
1. Исходная таблица считается текущей преобразуемой таблицей покрытий, множество строк покрытий - пусто.
2. В текущей таблице выделяется столбец с наименьшим числом единиц. Среди строк, содержащих единицы в этом столбце, выделяется одна с наибольшим числом единиц. Эта строка включается в покрытие, текущая таблица сокращается вычеркиванием всех столбцов, в которых выбранная строка имеет единицу, если в таблице есть не вычеркнутые столбцы, то выполняется п.2, иначе - покрытие построено.

Вопрос не по алгоритму, но по возникновению исключительной ситуации.
0xC0000005: Access violation writing location 0xcdcdcdcd. Выполнение останавливается на строке 107:
C++
1
for (int i=0; i<M; i++){ for (int j=0; j<N; j++) A[i][j]=Temp[i][j];}
B чём может быть причина? почитал немного об этом в интернете, реестр почистил Reg Organizer`ом, стоит антивирус Касперского. Если проблема в том, что где-то не освобождаю память, укажите, пожалуйста, где (проверял, но мог и не заметить).
Просьба не ругаться по поводу некоторой "сложности" алгоритма, а ответить на вопрос по существу. Если есть предложения, как улучшить алгоритм - буду очень благодарен за решения.
Моя реализация:
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
#include "stdafx.h"
#include <iostream>
using namespace std;
void Perebor(int**A,int M, int N, int**B, int c);
void Min_column(int**A, int N, int M, int* Sum, int**B,int c);
void Max_row(int**A, int MCN, int M, int N, int**B, int c);
void Build_cover(int**A,int**B,int c, int MRN, int N,int M);
void Erase_columns(int**A,int**B,int MRN, int M, int N, int c);
int _tmain(int argc, _TCHAR* argv[])
{
    int M,N,c=0; //М - для хранения кол-ва строк, N- для хранения кол-ва столбцов
    cout<<"Enter number of rows: ";cin>>M;
    cout<<"Enter number of columns: ";cin>>N;
    int **B= new int*[M-1]; // массив В организован для хранения покрытия
    int **A= new int*[M];                       
    for (int i=0; i<M; i++) {A[i]= new int[N];}            
    cout<<"Fill the matrix\n";
    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){scanf("%u", &A[i][j]);}
    }
    Perebor(A,M,N,B,c);
return 0;
};
void Perebor(int**A,int M, int N, int**B, int c){
    int *Sum= new int[N]; //в массиве Sum будем хранить кол-во единиц в каждом столбце матрицы
    for (int j=0; j<N; j++){
        Sum[j]=0;
        for (int i=0; i<M; i++){
            Sum[j]=Sum[j]+A[i][j];
        }
        if (Sum[j]==0) {
            cout<<"There is no cover in this matrix\n"; delete[]Sum;
            for(int i=0; i<M; i++) delete[]A[i]; delete[]A; delete[]B; exit(1);}
    };
    Min_column(A,N,M,Sum,B,c);
}
void Min_column(int**A, int N, int M, int* Sum, int**B,int c){
    int MCS=0; //Переменная для хранения кол-ва единиц в минимальном столбце
    int MCN=0; // Переменная для хранения номера минимального столбца
    for (int j=0; j<N-1; j++){
        if (Sum[j]<=Sum[j+1]){
            if (MCS==0){MCS=Sum[j];MCN=j;}             //организовано для того, чтобы мин. столбцом
            else{ if(MCS>Sum[j]){MCS=Sum[j];MCN=j;}} //стал первый обнаруженный мин. столбец
        }
        else {if (MCS==0){MCS=Sum[j+1];MCN=j+1;}}
    }
    delete[] Sum;
    Max_row(A,MCN,M,N,B,c);
}
void Max_row(int**A, int MCN, int M, int N, int**B, int c){
    int *Sum= new int[M];
    int MRS=0,MRN=0;
    for (int i=0; i<M; i++){
        Sum[i]=0;
        if (A[i][MCN]==1){
            for(int j=0; j<N; j++) Sum[i]=Sum[i]+A[i][j];
        }
    }
    for (int i=0; i<M-1; i++){
        if (Sum[i]-Sum[i+1]!=0){
            if(Sum[i]>Sum[i+1]){
                if (MRS==0) {MRS=Sum[i]; MRN=i;}
                else{
                    if(MRS<Sum[i]) {MRS=Sum[i]; MRN=i;}
                }
            }
            else{ 
                if (MRS==0) {MRS=Sum[i+1]; MRN=i+1;}
                else{
                    if(MRS<Sum[i+1]) {MRS=Sum[i+1]; MRN=i+1;}
                }
            }
        }
        if (Sum[i]!=0 && Sum[i+1]!=0 && Sum[i]==Sum[i+1]){
            if (MRS==0) {MRS=Sum[i+1]; MRN=i+1;}
            else{
                if(MRS<=Sum[i+1]) {MRS=Sum[i+1]; MRN=i+1;}
                }
        }
    }
    delete[] Sum;
    Build_cover(A,B,c,MRN,N,M);
}
void Build_cover(int**A,int**B,int c, int MRN, int N,int M){
    B[c]=new int[N];
    for(int j=0; j<N; j++) B[c][j]=A[MRN][j];
    c++;
    Erase_columns(A,B,MRN,M,N,c);
}
void Erase_columns(int**A,int**B,int MRN, int M, int N, int c){
    int d=0,e=0; // Счётчики для массива Temp (d-строки, е-столбцы)
    int ed=0; //Счётчик количества единиц в максимальной строке
    for (int j=0; j<N; j++) if (A[MRN][j]==1) ed++;
    if (ed==N){cout<<"Cover is built\n"; for(int i=0; i<M; i++) delete[]A[i]; delete[]A; delete[]B; system("Pause"); exit(1);}
    int**Temp=new int*[M];
        for (int i=0; i<M; i++) Temp[i]=new int[N-ed];
        for (int j=0; j<N; j++){
            if (A[MRN][j]!=1){
                for (int i=0; i<M; i++){Temp[d][e]=A[i][j]; d++;}
                e++;d=0;}
        }
        for (int i=0; i<M; i++){delete[]A[i];}
        delete[]A;
        N=N-ed;
        int**A=new int*[M];
        for(int i=0; i<N; i++) A[i]=new int[N];
        for (int i=0; i<M; i++){ for (int j=0; j<N; j++) A[i][j]=Temp[i][j];}
        for (int i=0; i<M; i++) delete[]Temp[i];
        delete[]Temp;
        Perebor(A,M,N,B,c);
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 00:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru