VPF::Избавьте от зацикливания! - Форум программистов

Garcian

Дата 21.5.2011, 20:02 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Здравствуйте, Уважаемые программисты!
Совсем недавно я вступил в ООП. И пока не понимаю его преимущества. Но об этом потом.
В общем, пишу программу на основе нахождения кратчайшей сети Крускала (вкратце - суть в том, чтобы найти минимальные паросочетания взвешанного двудольного графа). Для примера здесь используется матрица весов C.
Моя проблема состоит в следующем: я, как мне кажется, с программировал этот алгоритм правильно, но я совсем застрял на том моменте, где я рекурсивно вызываю функцию Krasckal! Признаюсь, опыта в программировании у меня немного, и может я не знаю каких-либо элементарных вещей. Подскажите, пожалуйста, как избавится от зацикливания! Собственно, здесь у меня происходит проверка (строка 47):

Код


if (check[k1] == check[k2])

которая проверяет, принадлежат ли минимальные элементы в разных строках одному столбцу. И, если таковых нет, метод Krasckal должен прекращать свою работу. С этим у меня и возникла проблема.
Теперь, что касается ООП. Я знаю, что три основных принципа, это инкапсуляция, полиморфизм и наследование. Но я не представляю как можно улучшить работу программы используя этот подход. Если у Вас есть идеи и Вас не затруднит, объясните, пожалуйста.
И, наконец, сроки сдачи работы у меня поджимают. А программу требуется выполнить в Windows Forms. Реально ли разобраться в этом за пару суток, или мне стоит искать помощь в реализации этого на стороне?

Код


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsolePurpose1
{
    class Purpose // класс, реализующий задачу о назначениях
    {
        public int[,] C = {
                           {5, 6, 7, 8},
                           {4, 7, 6 , 10},
                           {4, 9, 8, 2}
                       }; // Матрица весов C двудольного графа
        public int[] Cmin1 = new int[3]; // минимальный элемент в строке
        public int[] check = new int[3]; // матрица, хранящая номера столбцов мин элементов в строке
        public int[] Cmin2 = new int[3]; // второй элемент по минимальности
        public int[] dCmin = new int[2]; // разность первого и второго минимальных элементов
        int l = 0;
        int k;
        int x, y; // номера строк, у которых 2 мин эл-та в столбце


        public void Krasckal(int[,] Cex)
        {
            int i, j;
            for (i = 0; i < 3; i++)
            {
                Cmin1[i] = Cex[i, 0]; // минимальным является первый эл-т в строке
                for (j = 0; j < 4; j++)
                {
                    if (C[i, j] < Cmin1[i]) // если нашелся элемент меньше
                    {
                        Cmin1[i] = Cex[i, j]; // он становится минимальным
                        check[i] = j; // запоминаем номер столбца минимального элемента
                    }
                }
            }

            for (int k1 = 0; k1 < 3; k1++)     // проверяем
            {                                  // находятся ли минимальные элементы
                for (int k2 = 0; k2 < 3; k2++) // в одном столбце
                {
                    while (k1 != k2)
                    {
                        if (check[k1] == check[k2]) // если да, то
                        {
                            k = check[k1];
                            y = k1; // запоминаем строки
                            x = k2; // с минимальными элементами
                            if (l == check[k1]) l++; // если минимумы были в первом столбце, переходим во второй
                            for (i = 0; i < 3; i++) // опять ищем мин элемент Cmin2
                            {
                                Cmin2[i] = Cex[i, l]; // за минимальный принимаем элемент либо нулевой,
                                for (j = 0; j < 4; j++) // либо тот, что идет за ним
                                {
                                    while (check[k1] != j) // исключаем столбец с Cmin1
                                    {
                                        if (C[i, j] < Cmin2[i]) // если нашелся элемент меньше
                                        {
                                            Cmin2[i] = Cex[i, j]; // он становится минимальным
                                        }
                                        break;
                                    }
                                }
                            }
                        }
                        break;
                    }
                }
            }
            dCmin[0] = Cmin2[x] - Cmin1[x];
            dCmin[1] = Cmin2[y] - Cmin1[y];
            if ((dCmin[1] - dCmin[0]) >= 0)
            {
                Cex[x, k] = 100;

            }
            else
            {
                Cex[y, k] = 100;
            }
            Krasckal(C);
        }
     
        public void Write(int[,] C) // вывод таблицы
        {
            StreamWriter swFile = File.CreateText("Purpose.txt");
            swFile.WriteLine(" Курсовая работа Часть 2.");
            swFile.WriteLine("Матрица весов С: ");
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    swFile.Write("{0}\t", C[i, j]);
                }
                swFile.WriteLine();
            }
            swFile.Close();
        }
    }

    class Test
    {
        public static void Main()
        {
            Purpose pur = new Purpose();
            //pur.Inic();
            //pur.Read(pur.C);
            pur.Write(pur.C);
            pur.Krasckal(pur.C);
            //pur.Min(pur.C, pur.Cmin1);
            Console.WriteLine("Сmin1: ");
            for (int i = 0; i < 3; i++)
            {
                    Console.WriteLine("{0}\t", pur.Cmin1[i]);
            }
            Console.WriteLine("Сmin2: ");
            for (int i = 0; i < 3; i++)
            {
                Console.WriteLine("{0}\t", pur.Cmin2[i]);
            }
            Console.WriteLine("dСmin: ");
            for (int i = 0; i < 2; i++)
            {
                Console.WriteLine("{0}\t", pur.dCmin[i]);
            }
            Console.ReadKey();
        }
    }
}

--------------------

Неродивый студент

Garcian

Дата 22.5.2011, 08:11 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Все окончательно исправил

Код


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsolePurpose1
{
    class Purpose // класс, реализующий задачу о назначениях
    {
        public int[,] C = {
                           {5, 6, 7, 8, 1, 6, 7},
                           {4, 7, 6, 9, 3, 7, 2},
                           {4, 9, 8, 2, 5, 9, 7},
                           {4, 7, 4, 8, 5, 4, 3},
                           {5, 6, 4, 8, 6, 7, 8},
                           {8, 9, 7, 3, 6, 5, 1}
                       }; // Матрица весов C двудольного графа
        public int[] Cmin1 = new int[6]; // минимальный элемент в строке
        public int[] check = new int[6]; // матрица, хранящая номера столбцов мин элементов в строке
        public int[] Cmin2 = new int[6]; // второй элемент по минимальности
        public int[] dCmin = new int[2]; // разность первого и второго минимальных элементов
        int l = 0;
        int k;
        int x, y; // номера строк, у которых 2 мин эл-та в столбце
        bool flag; // метка
        public int min = 0;

        public void Krasckal(int[,] Cex)
        {
            flag = false; // метка = ложь
            int i, j;
            for (i = 0; i < 6; i++)
            {
                check[i] = 0;
            }
            for (i = 0; i < 6; i++)
            {
                Cmin1[i] = Cex[i, 0]; // минимальным является первый эл-т в строке
                for (j = 0; j < 7; j++)
                {
                    if (C[i, j] < Cmin1[i]) // если нашелся элемент меньше
                    {
                        Cmin1[i] = Cex[i, j]; // он становится минимальным
                        check[i] = j; // запоминаем номер столбца минимального элемента
                    }
                }
            }

            for (int k1 = 0; k1 < 6; k1++)     // проверяем
            {                                  // находятся ли минимальные элементы
                for (int k2 = 0; k2 < 6; k2++) // в одном столбце
                {
                    while (k1 != k2)
                    {
                        if (check[k1] == check[k2]) // если да, то
                        {
                            flag = true; // метка = истина
                            k = check[k1];
                            y = k1; // запоминаем строки
                            x = k2; // с минимальными элементами
                            if (l == check[k1]) l++; // если минимумы были в первом столбце, переходим во второй
                            for (i = 0; i < 6; i++) // опять ищем мин элемент Cmin2
                            {
                                Cmin2[i] = Cex[i, l]; // за минимальный принимаем элемент либо нулевой,
                                for (j = 0; j < 7; j++) // либо тот, что идет за ним
                                {
                                    while (check[k1] != j) // исключаем столбец с Cmin1
                                    {
                                        if (C[i, j] < Cmin2[i]) // если нашелся элемент меньше
                                        {
                                            Cmin2[i] = Cex[i, j]; // он становится минимальным
                                        }
                                        break;
                                    }
                                }
                            }
                        }
                        break;
                    }
                }
            }
            dCmin[0] = Cmin2[x] - Cmin1[x]; // вычисляем разность второго и первого минимальных элементов строки
            dCmin[1] = Cmin2[y] - Cmin1[y]; // тоже самое
            if ((dCmin[1] - dCmin[0]) >= 0) // проверяем
            {
                Cex[x, k] = 100; // Сmin1 = Cmin2 для первой строки

            }
            else
            {
                Cex[y, k] = 100; // Сmin1 = Cmin2 для второй строки
            }
            if (flag)
            {
                Krasckal(C);
            }
        }

        public void Check(int[] ch) // метод отслеживает невостребованные объекты
        {
            int p = 0;
            int[] Cch = new int[7]; // массив единиц и нулей
            for (int i = 0; i < 6; i++)
            {
                p = ch[i]; 
                for (int j = 0; j < 7; j++)
                {
                    if (j == p) // если столбец j был задействован
                    {
                        Cch[p] = 1; // no в p-й элемент мы ставим 1
                        break;
                    }
                }
            }
            for (int j = 0; j < 7; j++) // проверяем массив Cch
            {
                if (Cch[j] == 0) // если в нем имеется нулейвой эл-т - то это номер 
                {                // невостребованного объекта 
                    Console.WriteLine("Объект y{0} остался невостребованным!", j + 1);
                }
            }
        }

        public void Write(int[,] C) // вывод таблицы
        {
            StreamWriter swFile = File.CreateText("Purpose.txt");
            swFile.WriteLine("Хижин Денис гр. 8301. Курсовая работа Часть 2.");
            swFile.WriteLine("Матрица весов С: ");
            for (int i = 0; i < 6; i++)
            {
                for (int j = 0; j < 7; j++)
                {
                    swFile.Write("{0}\t", C[i, j]);
                }
                swFile.WriteLine();
            }
            swFile.Close();
        }
    }

    class Test
    {
        public static void Main()
        {
            Purpose pur = new Purpose();
            //pur.Read(pur.C);
            pur.Write(pur.C);
            pur.Krasckal(pur.C);
            Console.WriteLine("Минимальная сумма затрат: ");
            for (int i = 0; i < 6; i++)
            {
                pur.min = pur.min + pur.Cmin1[i];
            }
            Console.WriteLine("{0}", pur.min);
            pur.Check(pur.check);
            Console.ReadKey();
            pur.Write(pur.C);
        }
    }
}

Если не сложно, ответьте на два последующих вопроса smile

Тяжело сделать форму для этого?)

Это сообщение отредактировал(а) Garcian - 22.5.2011, 22:23

--------------------

Неродивый студент

-Mikle-

Дата 22.5.2011, 23:12 (ссылка)

(нет голосов)

Загрузка ...

Невидимка Vingrad'а

Профиль
Группа: Экс. модератор
Сообщений: 1672
Регистрация: 22.6.2003
Где: Казахстан, Астана

Репутация: 4
Всего: 59

Как минимум, можно выделить сходу уже два небольших класса. По большому счету обертки над массивом, но с дополнительной небольшой функциональностью. Твой алгоритм мне абсолютно не знаком, поэтому переделывал "наугад" и тебе стоит проверить правильность (может быть что-то еще нужно переделать или подправить), но идея в любом случае отражена:

Код


    public class KrusckalMatrix
    {
        List<KrusckalMatrixRow> _rows;

        public KrusckalMatrix()
        {
            _rows = new List<KrusckalMatrixRow>();
        }
        public KrusckalMatrix(params KrusckalMatrixRow[] rows)
        {
            _rows = new List<KrusckalMatrixRow>();
            foreach (var row in rows) AddRow(row);
        }

        public void AddRow(KrusckalMatrixRow row)
        {
            if (row == null)
                throw new ArgumentNullException("row");
            if (_rows.Count > 0 && _rows[0].Length != row.Length)
                throw new ArgumentOutOfRangeException("row", "Размерность добавляемой строки должна быть одинаковой");
            _rows.Add(row);
        }

        public KrusckalMatrixRow this[int row] { get { return _rows[row]; } }
        public int Length { get { return _rows.Count; } }

        public void Calculate()
        {
            l = k = x = y = 0;
            CalcCore();
        }

        int l = 0, k = 0;
        int x = 0, y = 0; // номера строк, у которых 2 мин эл-та в столбце
        void CalcCore()
        {
            for (int k1 = 0; k1 < this.Length; k1++)     // проверяем находятся ли минимальные элементы в одном столбце
            {
                for (int k2 = 0; k2 < this.Length; k2++)
                {
                    if (k1 == k2) continue;

                    if (this[k1].MinValueIndex == this[k2].MinValueIndex) // если да, то
                    {
                        y = k1; // запоминаем строки
                        x = k2; // с минимальными элементами
                        k = this[k1].MinValueIndex;

                        if (l == this[k1].MinValueIndex) l++; // если минимумы были в первом столбце, переходим во второй

                        for (int i = 0; i < this.Length; i++) // опять ищем мин элемент Cmin2
                        {
                            this[i].MinValue2 = this[i][l]; // за минимальный принимаем элемент либо нулевой,
                            for (int j = 0; j < this[i].Length; j++)    // либо тот, что идет за ним
                            {
                                if (this[k1].MinValueIndex == j) continue; // исключаем столбец с Cmin1

                                if (this[i][j] < this[i].MinValue2) // если нашелся элемент меньше
                                    this[i].MinValue2 = this[i][j]; // он становится минимальным
                                break;
                            }
                        }
                    }
                    break;
                }
            }

            if (this[y].MinValueSubtract >= this[x].MinValueSubtract)
                this[x][k] = 100;
            else
                this[y][k] = 100;

            CalcCore();
        }
    }

    public class KrusckalMatrixRow
    {
        int[] _values;
        public KrusckalMatrixRow(params int[] values)
        {
            _values = values;
            CalcMinValueIndex();
        }

        public int this[int column]
        {
            get { return _values[column]; }
            set
            {
                _values[column] = value;
                CalcMinValueIndex();
            }
        }

        public int Length { get { return _values.Length; } }

        public int MinValue { get { return _values[MinValueIndex]; } }
        public int MinValueIndex { get; private set; }

        public int MinValue2 { get; set; }

        public int MinValueSubtract { get { return MinValue2 - MinValue; } }


        private void CalcMinValueIndex()
        {
            int min = _values[0];        // минимальным считаем первый эл-т в строке
            for (int i = 1; i < this.Length; i++)
            {
                if (_values[i] >= min) continue;

                // если нашелся элемент меньше
                min = _values[i];        // он становится минимальным
                MinValueIndex = i;            // запоминаем номер столбца минимального элемента
            }
        }
    }

Код


        public static void Main()
        {
            KrusckalMatrix matrix = new KrusckalMatrix
            (
                new KrusckalMatrixRow(5, 6, 7, 8),
                new KrusckalMatrixRow(4, 7, 6, 10),
                new KrusckalMatrixRow(4, 9, 8, 2)
            );

            Print(matrix);
            matrix.Calculate();
            // .............
        }

        private static void Print(KrusckalMatrix matrix)
        {
            // выводишь матрицу
        }

Выводд матрицы лучше не засовывать в класс матрицы, так как сам вывод зависит от приложения. Другими словами, каждый класс отвечает только за свою логику и за свою задачу, которая касается только его.

--------------------

Если тебе плюют в спину, значит ты впереди...

Garcian

Дата 23.5.2011, 16:48 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Разбирал как китайскую грамоту, через дебагер smile

Все таки много непривычных конструкций таких как get, set (в которых я еще не успел разобраться); ключевых слов типа this и пр.
Да уж, совсем другое представление) Как я понял List<KrusckalMatrixRow> _rows - список, в который мы добавляем строки. Для каждой строки у нас есть ее длина, 2 минимальных эл-та, их разность и индекс минимального элемента.
Рассматривая матрицу приведенную ниже выявил кое-какие ошибки.

Код


KrusckalMatrix matrix = new KrusckalMatrix
            (
                new KrusckalMatrixRow(5, 6, 7, 8, 1, 6, 7),
                new KrusckalMatrixRow(4, 7, 6, 9, 3, 7, 2),
                new KrusckalMatrixRow(4, 9, 8, 2, 5, 9, 7),
                new KrusckalMatrixRow(4, 7, 4, 8, 5, 4, 3),
                new KrusckalMatrixRow(5, 6, 4, 8, 6, 7, 8),
                new KrusckalMatrixRow(8, 9, 7, 3, 6, 5, 1)
            );

Исправил метод CalcCore (убрал лишние break и добавил flag). Программа все равно зациклится, нужно каждый раз при запуске CalcCore обнулять MinValueIndex. Осуществить я это не сумел.
Все таки для меня этот код тяжел для понимания, т.к. я не то что не могу добавить метод Check (мой второй пост), но и даже саму матрицу вывести не в состоянии.

Код


        void CalcCore()
        {
            bool flag = false; // условие для запуска метода
            for (int k1 = 0; k1 < this.Length; k1++)     // проверяем находятся ли минимальные элементы в одном столбце
            {
                for (int k2 = 0; k2 < this.Length; k2++)
                {
                    if (k1 == k2) continue;
                    if (this[k1].MinValueIndex == this[k2].MinValueIndex) // если да, то
                    {
                        flag = true; // запустим метод еще раз
                        y = k1; // запоминаем строки
                        x = k2; // с минимальными элементами
                        k = this[k1].MinValueIndex;
                        if (l == this[k1].MinValueIndex) l++; // если минимумы были в первом столбце, переходим во второй
                        for (int i = 0; i < this.Length; i++) // опять ищем мин элемент Cmin2
                        {
                            this[i].MinValue2 = this[i][l]; // за минимальный принимаем элемент либо нулевой,
                            for (int j = 0; j < this[i].Length; j++)    // либо тот, что идет за ним
                            {
                                if (this[k1].MinValueIndex == j) continue; // исключаем столбец с Cmin1
                                if (this[i][j] < this[i].MinValue2) // если нашелся элемент меньше
                                    this[i].MinValue2 = this[i][j]; // он становится минимальным
                                //break; // - лишний break, не давал заносить в MinValue2 действительно минимальный элемент
                            }
                        }
                    }
                    // break; тоже лишний
                }
            }
            if (this[y].MinValueSubtract >= this[x].MinValueSubtract)
                this[x][k] = 100;
            else
                this[y][k] = 100;
            if (flag) // проверка
            CalcCore();
        }

Это сообщение отредактировал(а) Garcian - 23.5.2011, 16:50

--------------------

Неродивый студент

-Mikle-

Дата 23.5.2011, 17:57 (ссылка)

(нет голосов)

Загрузка ...

Невидимка Vingrad'а

Профиль
Группа: Экс. модератор
Сообщений: 1672
Регистрация: 22.6.2003
Где: Казахстан, Астана

Репутация: 4
Всего: 59

Я сделал так, что MinValueIndex пересчитывается автоматически, каждый раз как только меняется любое значение в строке. Происхожит это здесь:

Код


public class KrusckalMatrixRow
{
......................
.........................
        public int this[int column]
        {
            get { return _values[column]; }
            set
            {
                _values[column] = value;
                CalcMinValueIndex();
            }
        }
............
.................
        private void CalcMinValueIndex()
        {
........................
        }

((Кстати в методе ошибка есть, надо в самое самое начало метода CalcMinValueIndex добавить строку MinValueIndex = 0, возможно из-за этого ошибка. Попробуй сначала исправить и проверить, если все равно не будет работать как надо, то тогда пробуй дальше.))

То есть каждый раз когда задается значение любой колонке вызывается метод пересчета свойства MinValueIndex. Если тебе не требуется автоматика, то убери вызов из сетера и измени модификатор метода CalcMinValueIndex с private на public (это позволит тебе вызывать этот метод снаружи, там где основной алгоритм). Если тебе потребуется вдруг снаружи класса устанавливать значение свойства MinValueIndex, то надо в классе KrusckalMatrixRow изменить строку public int MinValueIndex { get; private set; } на public int MinValueIndex { get; set; } (убрать модификатор private с сетера свойства). Ну и если что пиши, раз я уже взялся, то доведем как-нить твой алгоритм (если не до ума, то хотя бы до рабочего состояния smile

).

PS: а вот вывод матрицы по тому же принципу как у тебя в первом посте (намеренно ничего не менял, чтоб все похоже было):

Код


        private static void Print(KrusckalMatrix matrix)
        {
            // выводишь матрицу

            StreamWriter swFile = File.CreateText("Purpose.txt");
            swFile.WriteLine("Курсовая работа Часть 2.");
            swFile.WriteLine("Матрица весов:");
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0; j < matrix[i].Length; j++)
                {
                    swFile.Write("{0}\t", matrix[i][j]);
                }
                swFile.WriteLine();
            }
            swFile.Close();
        }

--------------------

Если тебе плюют в спину, значит ты впереди...

Garcian

Дата 23.5.2011, 23:04 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Цитата

Кстати в методе ошибка есть, надо в самое самое начало метода CalcMinValueIndex добавить строку MinValueIndex = 0, возможно из-за этого ошибка.

угу) она и есть) все работает) все правильно) Добавил метод Check:

Код


 private static void Check(KrusckalMatrix matrix)
        {
            int p = 0;
            int min = 0;
            StreamWriter swFile = File.AppendText("Purpose.txt");
         
            int[] Cch = new int[7]; // массив единиц и нулей

            for (int i = 0; i < matrix.Length; i++)
            {    
                p = matrix[i].MinValueIndex;
                for (int j = 0; j < matrix[i].Length; j++)
                {
                    if (j == p) // если столбец j был задействован
                    {
                        Cch[p] = 1; // no в p-й элемент мы ставим 1
                        break;
                    }
                }
            }
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0; j < matrix[i].Length; j++) // проверяем массив Cch
                {
                    if (Cch[j] == 0) // если в нем имеется нулейвой эл-т - то это номер 
                    {                // невостребованного объекта 
                        swFile.WriteLine("Объект y{0} остался невостребованным!", j + 1);
                        //break;
                    }
                } break;
            }
            for (int i = 0; i < matrix.Length; i++)
            {
                min = min + matrix[i].MinValue;
            }
            swFile.WriteLine("\nМинимальная сумма затрат: {0}", min);
            swFile.Close();
        }

Результат работы такой же как и во втором моем посте)

Код


Курсовая работа Часть 2.
Матрица весов:
5    6    7    8    1    6    7    
4    7    6    9    3    7    2    
4    9    8    2    5    9    7    
4    7    4    8    5    4    3    
5    6    4    8    6    7    8    
8    9    7    3    6    5    1    
Объект y2 остался невостребованным!

Минимальная сумма затрат: 16

Правда меня тут не совсем устраивает инициализация массива Cch, но я по другому просто не умею)

Код


int[] Cch = new int[7];

Уф, а теперь самое сложное, сделать ко всему этому форму... Смотрю видео лекции на английском и понимаю, что все очень печально smile

Это сообщение отредактировал(а) Garcian - 23.5.2011, 23:09

--------------------

Неродивый студент

-Mikle-

Дата 24.5.2011, 17:14 (ссылка)

(нет голосов)

Загрузка ...

Невидимка Vingrad'а

Профиль
Группа: Экс. модератор
Сообщений: 1672
Регистрация: 22.6.2003
Где: Казахстан, Астана

Репутация: 4
Всего: 59

Цитата(Garcian @ 24.5.2011, 02:04

)

Правда меня тут не совсем устраивает инициализация массива Cch, но я по другому просто не умею)

С этим разберешься потом сам, как домашнее задание тебе. Пока курсовую не сдал не трогай это, пусть останется так как есть (если работает).

По поводу форм, как только появятся наработки и проблемы, пиши. Как минимум, тебе сначала надо хорошо представить, как будет выглядеть форма.

--------------------

Если тебе плюют в спину, значит ты впереди...

Garcian

Дата 24.5.2011, 22:28 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Да, тут спорный момент. Все таки задание звучало "по содержимому таблицы найдите..." + контрольный пример. Т. е. и матрица весов вроде как задана, и ее размер тоже... и тогда программа носит чисто демонстративный характер, но смысла в ней тогда мало. Поэтому я решил оставить размер матрицы 7x6. А вот значения в ней могут варьироваться (пользователем).
Форма будет включать в себя таблицу, которая и будет представлять матрицу весов. Значения по умолчанию в таблице будут стоять, допустим, единички. Эти значения можно менять от 1 до 99. Соответственно, можно добавить кнопку запуска обработки таблицы методом Крускала. Для большей наглядности после обработки таблицы, можно залить ее ячейки с минимальными элементами (которые получились в конце), каким-либо цветом. Также дополнительно куда-нибудь вывести сообщение о невостребованном объекте (номер столбца Y) и минимальную сумму затрат (сумма минимальных элементов). Ну и напоследок сделать кнопочку "сброса" всех значений таблички обратно в состояние "по умолчанию".

Преподаватель требует выполнения работы в 2010 студии) Ничего против не имею, но большую часть учебных курсов, которые я искал, для 2008 студии, а там все таки есть различия (смотрел курс видео лекций Total Training - MS Visual Studio 2008 Essentials Featuring Windows Forms). Чет я не догадался на MSDN сразу зайти...

В общем, постараюсь разобраться.

Цитата

Как минимум, тебе сначала надо хорошо представить, как будет выглядеть форма.

Представил)

Цитата

как только появятся наработки и проблемы, пиши

обязательно smile

Это сообщение отредактировал(а) Garcian - 24.5.2011, 22:48

--------------------

Неродивый студент

Garcian

Дата 27.5.2011, 16:03 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Много всего просмотрел, в том числе на MSDNе. К сожалению нигде не нашел нормального практического руководства. Конечно, я оттуда кое что вынес, но этого явно недостаточно.
Тем не менее я создал, как мне кажется, вразумительную форму (файл я вложил в сообщение) на основе того, что я узнал. Но я не представляю, как связать мой консольный вариант с этой формой. Времени разобраться уже совсем не осталось, а получать удовл за работающую программу совсем не хочется.
Где должен располагаться основной текст программы? Как его вызвать на выполнение? В общем, у меня в голове белый лист.

Это сообщение отредактировал(а) Garcian - 27.5.2011, 16:04

Присоединённый файл ( Кол-во скачиваний: 10 )

Krusckal.rar 132,96 Kb

--------------------

Неродивый студент

Garcian

Дата 1.6.2011, 12:38 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Подскажите, пожалуйста, какой командой можно вывести информацию в ListView! Надеюсь на скорейший ответ, очень надо!

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

RichTextBox для этого оказался удобнее) Но можно ли в него передать 2 параметра каким-либо образом. Например, есть строчка:

Код


swFile.WriteLine("Объект y{0} остался невостребованным!", j + 1);

И как это можно реализовать в боксе? AppendText больше 1 параметра не поддерживает(

Это сообщение отредактировал(а) Garcian - 1.6.2011, 13:28

--------------------

Неродивый студент

wester

Дата 1.6.2011, 13:55 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 675
Регистрация: 27.2.2009

Репутация: 3
Всего: 13

Garcian,
использовать String.Format() ?

Garcian

Дата 1.6.2011, 14:11 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Можно пример?

--------------------

Неродивый студент

wester

Дата 1.6.2011, 14:18 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 675
Регистрация: 27.2.2009

Репутация: 3
Всего: 13

string example = string.Format("Просканировано файлов {0}, Подходящих {1}", 190, 2);
здесь тоже есть пример

Garcian

Дата 1.6.2011, 14:33 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

wester, спасибо большое!

--------------------

Неродивый студент

Garcian

Дата 1.6.2011, 15:34 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 5.11.2008

Репутация: нет
Всего: нет

Всем спасибо) Сделал форму, вроде даже как рабочую) Единственное, что не смог осуществить - перекрашивание ячеек TextBox, в которых содержаться минимальные элементы (не смог связать ядро программы с графической интерпретацией), а так все что намеревался сделать - сделал.

Реализовал может не совсем рационально, но главное работает smile

Код


using System;
using System.IO;
using System.Collections.Generic;
using System.ComponentModel;
using System.Drawing;
using System.Data;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Krusckal
{
    public partial class KrTable : UserControl
    {
        public KrTable()
        {
            InitializeComponent();
            textBox0_0.Text = "5";
            textBox0_1.Text = "6";
            textBox0_2.Text = "7";
            textBox0_3.Text = "8";
            textBox0_4.Text = "1";
            textBox0_5.Text = "6";
            textBox0_6.Text = "7";
            //////////////////////
            textBox1_0.Text = "4";
            textBox1_1.Text = "7";
            textBox1_2.Text = "6";
            textBox1_3.Text = "9";
            textBox1_4.Text = "3";
            textBox1_5.Text = "7";
            textBox1_6.Text = "2";
            //////////////////////
            textBox2_0.Text = "4";
            textBox2_1.Text = "9";
            textBox2_2.Text = "8";
            textBox2_3.Text = "2";
            textBox2_4.Text = "5";
            textBox2_5.Text = "9";
            textBox2_6.Text = "7";
            //////////////////////
            textBox3_0.Text = "4";
            textBox3_1.Text = "7";
            textBox3_2.Text = "4";
            textBox3_3.Text = "8";
            textBox3_4.Text = "5";
            textBox3_5.Text = "4";
            textBox3_6.Text = "3";
            //////////////////////
            textBox4_0.Text = "5";
            textBox4_1.Text = "6";
            textBox4_2.Text = "4";
            textBox4_3.Text = "8";
            textBox4_4.Text = "6";
            textBox4_5.Text = "7";
            textBox4_6.Text = "8";
            //////////////////////
            textBox5_0.Text = "8";
            textBox5_1.Text = "9";
            textBox5_2.Text = "7";
            textBox5_3.Text = "3";
            textBox5_4.Text = "6";
            textBox5_5.Text = "5";
            textBox5_6.Text = "1";
        }

        private void textBox0_0_TextChanged(object sender, EventArgs e)
        {

        }

        private void BC(TextBox t)
        {
            t.BackColor = Color.White;
        }

        private void buttonClear_Click(object sender, EventArgs e)
        {
            textBox0_0.Text = "5";
            textBox0_1.Text = "6";
            textBox0_2.Text = "7";
            textBox0_3.Text = "8";
            textBox0_4.Text = "1";
            textBox0_5.Text = "6";
            textBox0_6.Text = "7";
            //////////////////////
            textBox1_0.Text = "4";
            textBox1_1.Text = "7";
            textBox1_2.Text = "6";
            textBox1_3.Text = "9";
            textBox1_4.Text = "3";
            textBox1_5.Text = "7";
            textBox1_6.Text = "2";
            //////////////////////
            textBox2_0.Text = "4";
            textBox2_1.Text = "9";
            textBox2_2.Text = "8";
            textBox2_3.Text = "2";
            textBox2_4.Text = "5";
            textBox2_5.Text = "9";
            textBox2_6.Text = "7";
            //////////////////////
            textBox3_0.Text = "4";
            textBox3_1.Text = "7";
            textBox3_2.Text = "4";
            textBox3_3.Text = "8";
            textBox3_4.Text = "5";
            textBox3_5.Text = "4";
            textBox3_6.Text = "3";
            //////////////////////
            textBox4_0.Text = "5";
            textBox4_1.Text = "6";
            textBox4_2.Text = "4";
            textBox4_3.Text = "8";
            textBox4_4.Text = "6";
            textBox4_5.Text = "7";
            textBox4_6.Text = "8";
            //////////////////////
            textBox5_0.Text = "8";
            textBox5_1.Text = "9";
            textBox5_2.Text = "7";
            textBox5_3.Text = "3";
            textBox5_4.Text = "6";
            textBox5_5.Text = "5";
            textBox5_6.Text = "1";


            BC(textBox0_0);
            BC(textBox0_1);
            BC(textBox0_2);
            BC(textBox0_3);
            BC(textBox0_4);
            BC(textBox0_5);
            BC(textBox0_6);
            //////////////////////
            BC(textBox1_0);
            BC(textBox1_1);
            BC(textBox1_2);
            BC(textBox1_3);
            BC(textBox1_4);
            BC(textBox1_5);
            BC(textBox1_6);
            //////////////////////
            BC(textBox2_0);
            BC(textBox2_1);
            BC(textBox2_2);
            BC(textBox2_3);
            BC(textBox2_4);
            BC(textBox2_5);
            BC(textBox2_6);
            //////////////////////
            BC(textBox3_0);
            BC(textBox3_1);
            BC(textBox3_2);
            BC(textBox3_3);
            BC(textBox3_4);
            BC(textBox3_5);
            BC(textBox3_6);
            //////////////////////
            BC(textBox4_0);
            BC(textBox4_1);
            BC(textBox4_2);
            BC(textBox4_3);
            BC(textBox4_4);
            BC(textBox4_5);
            BC(textBox4_6);
            //////////////////////
            BC(textBox5_0);
            BC(textBox5_1);
            BC(textBox5_2);
            BC(textBox5_3);
            BC(textBox5_4);
            BC(textBox5_5);
            BC(textBox5_6);

            richTextBox1.Clear();
        }

        public int N;
        private int ReadText(TextBox t)
        {
            try
            {
                 N = Convert.ToInt32(t.Text);
            }
            catch (Exception e)
            {
                MessageBox.Show("Вы ввели некорректное значение");
            }
            return N;
        }

        private void buttonStart_Click(object sender, EventArgs e)
        {
            int s0_0 = 0;
            int s0_1 = 0;
            int s0_2 = 0;
            int s0_3 = 0;
            int s0_4 = 0;
            int s0_5 = 0;
            int s0_6 = 0;
            /////////////
            int s1_0 = 0;
            int s1_1 = 0;
            int s1_2 = 0;
            int s1_3 = 0;
            int s1_4 = 0;
            int s1_5 = 0;
            int s1_6 = 0;
            /////////////
            int s2_0 = 0;
            int s2_1 = 0;
            int s2_2 = 0;
            int s2_3 = 0;
            int s2_4 = 0;
            int s2_5 = 0;
            int s2_6 = 0;
            /////////////
            int s3_0 = 0;
            int s3_1 = 0;
            int s3_2 = 0;
            int s3_3 = 0;
            int s3_4 = 0;
            int s3_5 = 0;
            int s3_6 = 0;
            /////////////
            int s4_0 = 0;
            int s4_1 = 0;
            int s4_2 = 0;
            int s4_3 = 0;
            int s4_4 = 0;
            int s4_5 = 0;
            int s4_6 = 0;
            /////////////
            int s5_0 = 0;
            int s5_1 = 0;
            int s5_2 = 0;
            int s5_3 = 0;
            int s5_4 = 0;
            int s5_5 = 0;
            int s5_6 = 0;

            s0_0 = ReadText(textBox0_0);
            s0_1 = ReadText(textBox0_1);
            s0_2 = ReadText(textBox0_2);
            s0_3 = ReadText(textBox0_3);
            s0_4 = ReadText(textBox0_4);
            s0_5 = ReadText(textBox0_5);
            s0_6 = ReadText(textBox0_6);
            ///////////////////////////
            s1_0 = ReadText(textBox1_0);
            s1_1 = ReadText(textBox1_1);
            s1_2 = ReadText(textBox1_2);
            s1_3 = ReadText(textBox1_3);
            s1_4 = ReadText(textBox1_4);
            s1_5 = ReadText(textBox1_5);
            s1_6 = ReadText(textBox1_6);
            ///////////////////////////
            s2_0 = ReadText(textBox2_0);
            s2_1 = ReadText(textBox2_1);
            s2_2 = ReadText(textBox2_2);
            s2_3 = ReadText(textBox2_3);
            s2_4 = ReadText(textBox2_4);
            s2_5 = ReadText(textBox2_5);
            s2_6 = ReadText(textBox2_6);
            ///////////////////////////
            s3_0 = ReadText(textBox3_0);
            s3_1 = ReadText(textBox3_1);
            s3_2 = ReadText(textBox3_2);
            s3_3 = ReadText(textBox3_3);
            s3_4 = ReadText(textBox3_4);
            s3_5 = ReadText(textBox3_5);
            s3_6 = ReadText(textBox3_6);
            ///////////////////////////
            s4_0 = ReadText(textBox4_0);
            s4_1 = ReadText(textBox4_1);
            s4_2 = ReadText(textBox4_2);
            s4_3 = ReadText(textBox4_3);
            s4_4 = ReadText(textBox4_4);
            s4_5 = ReadText(textBox4_5);
            s4_6 = ReadText(textBox4_6);
            ///////////////////////////
            s5_0 = ReadText(textBox5_0);
            s5_1 = ReadText(textBox5_1);
            s5_2 = ReadText(textBox5_2);
            s5_3 = ReadText(textBox5_3);
            s5_4 = ReadText(textBox5_4);
            s5_5 = ReadText(textBox5_5);
            s5_6 = ReadText(textBox5_6);
            ///////////////////////////

            KrusckalMatrix matrix = new KrusckalMatrix
            (
                new KrusckalMatrixRow(s0_0, s0_1, s0_2, s0_3, s0_4, s0_5, s0_6),
                new KrusckalMatrixRow(s1_0, s1_1, s1_2, s1_3, s1_4, s1_5, s1_6),
                new KrusckalMatrixRow(s2_0, s2_1, s2_2, s2_3, s2_4, s2_5, s2_6),
                new KrusckalMatrixRow(s3_0, s3_1, s3_2, s3_3, s3_4, s3_5, s3_6),
                new KrusckalMatrixRow(s4_0, s4_1, s4_2, s4_3, s4_4, s4_5, s4_6),
                new KrusckalMatrixRow(s5_0, s5_1, s5_2, s5_3, s5_4, s5_5, s5_6)
            );
            Show show = new Show();
            show.Print(matrix, richTextBox1);
            matrix.Calculate();
            show.Check(matrix, richTextBox1);
            
        }

        private void listViewHistory_SelectedIndexChanged(object sender, EventArgs e)
        {

        }

        private void History_Click(object sender, EventArgs e)
        {

        }
    }
    public class Show
    {
        public void Check(KrusckalMatrix matrix, RichTextBox T)
        {
            int p = 0;
            int min = 0;
            StreamWriter swFile = File.AppendText("Purpose.txt");
            
            int[] Cch = new int[7]; // массив единиц и нулей

            for (int i = 0; i < matrix.Length; i++)
            {
                p = matrix[i].MinValueIndex;
                for (int j = 0; j < matrix[i].Length; j++)
                {
                    if (j == p) // если столбец j был задействован
                    {
                        Cch[p] = 1; // no в p-й элемент мы ставим 1
                        break;
                    }
                }
            }
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0; j < matrix[i].Length; j++) // проверяем массив Cch
                {
                    if (Cch[j] == 0) // если в нем имеется нулейвой эл-т - то это номер 
                    {                // невостребованного объекта 
                        swFile.WriteLine("Объект y{0} остался невостребованным!", j + 1);
                        string t;
                        t = string.Format("Объект y{0} остался невостребованным!", j + 1);
                        T.AppendText(t);
                        //break;
                    }
                } break;
            }
            for (int i = 0; i < matrix.Length; i++)
            {
                min = min + matrix[i].MinValue;
            }
            swFile.WriteLine("\nМинимальная сумма затрат: {0}", min);
            string tt;
            tt = string.Format("\nМинимальная сумма затрат: {0}\n", min);
            T.AppendText(tt);
            swFile.Close();
        }

        public void Print(KrusckalMatrix matrix, RichTextBox T)
        {
            StreamWriter swFile = File.CreateText("Purpose.txt");
            swFile.WriteLine("Курсовая работа Часть 2.");
            string t;
            t = string.Format("\nМатрица весов:\n");
            swFile.WriteLine("Матрица весов:");
            T.AppendText(t);
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0; j < matrix[i].Length; j++)
                {
                    swFile.Write("{0}\t", matrix[i][j]);
                    t = string.Format("{0}\t", matrix[i][j]);
                    T.AppendText(t);
                }
                T.AppendText("\n");
                swFile.WriteLine();
            }
            swFile.Close();
            // выводишь матрицу
        }
    }
    public class KrusckalMatrix
    {
        List<KrusckalMatrixRow> _rows;
        public KrusckalMatrix()
        {
            _rows = new List<KrusckalMatrixRow>();
        }
        public KrusckalMatrix(params KrusckalMatrixRow[] rows)
        {
            _rows = new List<KrusckalMatrixRow>();
            foreach (var row in rows) AddRow(row);
        }
        public void AddRow(KrusckalMatrixRow row)
        {
            if (row == null)
                throw new ArgumentNullException("row");
            if (_rows.Count > 0 && _rows[0].Length != row.Length)
                throw new ArgumentOutOfRangeException("row", "Размерность добавляемой строки должна быть одинаковой");
            _rows.Add(row);
        }
        public KrusckalMatrixRow this[int row] { get { return _rows[row]; } }
        public int Length { get { return _rows.Count; } }
        public void Calculate()
        {
            l = k = x = y = 0;
            CalcCore();
        }

        int l = 0, k = 0;
        int x = 0, y = 0; // номера строк, у которых 2 мин эл-та в столбце
        void CalcCore()
        {
            bool flag = false;
            for (int k1 = 0; k1 < this.Length; k1++)     // проверяем находятся ли минимальные элементы в одном столбце
            {
                for (int k2 = 0; k2 < this.Length; k2++)
                {
                    if (k1 == k2) continue;
                    if (this[k1].MinValueIndex == this[k2].MinValueIndex) // если да, то
                    {
                        flag = true;
                        y = k1; // запоминаем строки
                        x = k2; // с минимальными элементами
                        k = this[k1].MinValueIndex;
                        if (l == this[k1].MinValueIndex) l++; // если минимумы были в первом столбце, переходим во второй
                        for (int i = 0; i < this.Length; i++) // опять ищем мин элемент Cmin2
                        {
                            this[i].MinValue2 = this[i][l]; // за минимальный принимаем элемент либо нулевой,
                            for (int j = 0; j < this[i].Length; j++)    // либо тот, что идет за ним
                            {
                                if (this[k1].MinValueIndex == j) continue; // исключаем столбец с Cmin1
                                if (this[i][j] < this[i].MinValue2) // если нашелся элемент меньше
                                    this[i].MinValue2 = this[i][j]; // он становится минимальным
                                //break;
                            }
                        }
                    }
                    //break;
                }
            }
            if (flag)
            {
                if (this[y].MinValueSubtract >= this[x].MinValueSubtract)
                    this[x][k] = 100;
                else
                    this[y][k] = 100;
                CalcCore();
            }
        }
    }
    public class KrusckalMatrixRow
    {
        int[] _values;
        public KrusckalMatrixRow(params int[] values)
        {
            _values = values;
            CalcMinValueIndex();
        }
        public int this[int column]
        {
            get { return _values[column]; }
            set
            {
                _values[column] = value;
                CalcMinValueIndex();
            }
        }
        public int Length { get { return _values.Length; } }
        public int MinValue { get { return _values[MinValueIndex]; } }
        public int MinValueIndex { get; private set; }
        public int MinValue2 { get; set; }
        public int MinValueSubtract { get { return MinValue2 - MinValue; } }
        private void CalcMinValueIndex()
        {
            MinValueIndex = 0;
            int min = _values[0];        // минимальным считаем первый эл-т в строке
            for (int i = 1; i < this.Length; i++)
            {
                if (_values[i] >= min) continue;
                // если нашелся элемент меньше
                min = _values[i];        // он становится минимальным
                MinValueIndex = i;            // запоминаем номер столбца минимального элемента
            }
        }
    }
}

--------------------

Неродивый студент

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| .NET для новичков \| Следующая тема »