Нисходящее проектирование

Основной алгоритм

АЛГОРИТМ   Курсовой_проект

<Описание переменных> (см. спецификацию)

НАЧАЛО

       ЕСЛИ  (ввод с файла) ТО

                   Выбор файла и создание потока (1.1)

перепись 1-го графа с частичным контролем из файла на экран; (1.2)

ЕСЛИ (ошибка) ТО  

вывод («В данных на файле ошибка!»);

Выход;

                   КЕСЛИ

                   перепись 2-го графа с частичным контролем из файла на экран;

ЕСЛИ (ошибка) ТО

вывод («В данных на файле ошибка!»);

Выход;

                   КЕСЛИ

                   Закрыть поток.

       КЕСЛИ

Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности MS1 (1.3)

ЕСЛИ (ошибка) ТО

       вывод («В данных на форме ошибка»)

       Выход;

КЕСЛИ

Ввод с экрана 2-го графа с полным контролем и построением матрицы смежности

 MS2

 ЕСЛИ (ошибка) ТО  

       вывод («В данных на форме ошибка»)

       Выход;

КЕСЛИ

       Расчет диаметра 1-го графа d1 (1.4)

            Расчет диаметра 2-го графа d2;

       ЕСЛИ (d1=dr2) ТО

вывод («Графы эквивалентны»);

       ИНАЧЕ

вывод («Графы не эквивалентны»);

КЕСЛИ

КОНЕЦ

Из текста алгоритма видно, что в нем имеется 4 подзадачи (рис.21).

Рис. 21

    Дальнейшее проектирование можно выполнять двумя способами.

    1-й способ

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

    2-й способ

    Подзадачи (1.1) – (1.4) реализуются «заглушками». Заглушка – это алгоритм (метод), написанный на языке программирования  с правильным заголовком и с упрощенным либо пустым блоком. Указанные заглушки подставляем в основной алгоритм, а  затем записываем на языке программирования и вместе с «заглушками» отлаживаем программу. После отладки детализируем отдельные подзадачи таким же способом.

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

    Реализация подзадачи (1.1). Выбор файла и создание потока (подзадачу реализуем в виде блока)

Программирование будем выполнять на языке C#.

Переменные

string filename;

{

       if (openFileDialog1.ShowDialog == DialogResult.OK)

 {

filename = openFileDialog1.FileName;

           //создание потока и подсоединение к файлу

          Potok = new StreamReader(filename); 

}              

else

{

                   MessageBox.Show(“Файл не выбран!”);

                   return;

}

    Реализация подзадачи (1.2). Ввод графа с файла на экран с частичным контролем. Подзадачу реализуем в виде метода без типа.

Для размещения параметров графа n и m используем компоненты NumericUpDown, что позволяет уменьшить количество проверок, а для размещения FO – представления, компоненту  TextBox. Для имитации ошибок данных, при переносе с файла, на форме временно разместим компоненты типа CheckBox (CB1, CB2).

 

public void Move_Gr_fileToEcran (StreamReader Potok, NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBFО, ref bool error)

{

     MessageBox.Show(“Выполняется перенос графа с файла на экран”);

  error=CB1.Checked;

}

    Реализация подзадачи (1.3). Ввод данных с экрана с контролем и построением матрицы смежности. Подзадачу реализуем в виде метода без типа.

public  void Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm,     TextBox tBFO, ref int n, ref int m, ref int [,] MS, ref bool error)

{

       MessageBox.Show (“Выполняется ввод графа с экрана и построение матрицы”);

       error=CB2.Checked;

}

    Реализация заглушки (1.4). Расчет диаметра графа. Подзадачу реализуем в виде метода с типом результата (целое число)

public int Diametr(int[,]MS)

{

   MessageBox.Show(“Находим диаметр графа”);

   return 2;

}

    Подставляем «заглушки» в основной алгоритм

АЛГОРИТМ   Курсовой_проект

<Описание переменных> (см. спецификацию)

string filename;

bool error;

НАЧАЛО

       ЕСЛИ  (ввод с файла) ТО

                   //Выбор файла и создание потока (1.1)

if (openFileDialog1.Show == DialogResult.OK)

         {

    filename = openFileDialog1.Filename;

                   //создание потока и подсоединение к файлу

                   StreamReader Potok = new StreamReader(filename); 

        }              

       else

       {

               MessageBox.Show(“Файл не выбран!”);

               Return;

       }

   //перепись 1-го графа с частичным контролем из файла на экран; (1.2)

   Move_Gr_fileToEcran (Potok, nUDn1,  nUDm1, tBFО1, ref error);

              ЕСЛИ (error) ТО  

                          вывод («В данных на файле ошибка!»);

                          Выход;

         КЕСЛИ

              //перепись 2-го графа с частичным контролем из файла на экран;

   Move_Gr_fileToEcran (Potok, nUDn1,  nUDm1, tBFО1, ref error);

              ЕСЛИ (error) ТО

                            вывод («В данных на файле ошибка!»);

                           Выход;

          КЕСЛИ

  Potok.Close();

       КЕСЛИ

//Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности //MS1 (1.3)

Input_GrInEkran (nUDn1,  nUDm1,  tBFO1, ref n1, ref m1, ref MS1, ref error);

ЕСЛИ (error) ТО

       вывод («В данных на форме ошибка»)

       Выход;

КЕСЛИ

//Ввод с экрана 2-го графа с полным контролем и построением матрицы смежности

// MS2

Input_GrInEkran (nUDn2,  nUDm2,  tBFO2, ref n2, ref m2, ref MS2, ref error);

 ЕСЛИ (error)) ТО  

       вывод («В данных на форме ошибка»)

       Выход;

КЕСЛИ

       //Расчет диаметра 1-го графа r1 (1.4)

       // Расчет диаметра 2-го графа r2;

       ЕСЛИ (/*d1= d2*/ Diametr(MS1)== Radius(MS2)) ТО

вывод («Графы эквивалентны»);

       ИНАЧЕ

вывод («Графы не эквивалентны»);

КЕСЛИ

КОНЕЦ

 

    Записываем основной алгоритм на С# и вместе с заглушками отлаживаем его.

public void Kyrs_proekt()

{

     <Описание переменных> (см. спецификацию)

   string filename;

    bool error;

       if (/*ввод с файла*/radioGroup1.Checked)

      {

                   //Выбор файла и создание потока (1.1)

if (openFileDialog1.Show == DialogResult.OK)

         {

    filename = openFileDialog1.Filename;

                   //создание потока и подсоединение к файлу

                   StreamReader Potok = new StreamReader(filename); 

        }              

       else

       {

               MessageBox.Show(“Файл не выбран!”);

               Return;

       }

   //перепись 1-го графа с частичным контролем из файла на экран; (1.2)

   Move_Gr_fileToEcran (Potok, nUDn1,  nUDm1, tBFО1, ref error);

              if (error)

                {

                          MessageBox.Show (“В данных на файле ошибка!”);

                          return;

         }

              //перепись 2-го графа с частичным контролем из файла на экран;

   Move_Gr_fileToEcran (Potok, nUDn1,  nUDm1, tBFО1, ref error);

              if (error)

              {

                           MessageBox.Show (“В данных на файле ошибка!”);

                           return;

          }

   Potok.Close();

       }

//Ввод с экрана 1-го графа с полным контролем и построением матрицы смежности //MS1 (1.3)

Input_GrInEkran (nUDn1,  nUDm1,  tBFO1, ref n1, ref m1, ref MS1, ref error);

if (error) 

{

       MessageBox.Show (“В данных на форме ошибка”);

       return;

}

//Ввод с экрана 2-го графа с полным контролем и построением матрицы смежности

// MS2

Input_GrInEkran (nUDn2,  nUDm2,  tBFO2, ref n2, ref m2, ref MS2, ref error);

if (error)) 

{ 

       MessageBox.Show (“В данных на форме ошибка”);

       return;

}

       //Расчет диаметра 1-го графа r1 (1.4)

       // Расчет диаметра 2-го графа r2;

       if (/*d1= d2*/ Diametr(MS1)== Radius(MS2)) 

MessageBox.Show (“Графы эквивалентны”);

       else

MessageBox.Show (“Графы не эквивалентны”);

}

 

    Приступаем к проектированию подзадачи (1.2). Перепись графа с файла на экран с частичным контролем.  

Move_Gr_fileToEcran (StreamReader Potok. NumericUpDown nUDn, NumericUpDown nUDm,   TextBox tbFO, ref bool error)

НАЧАЛО

Перенос чисел n и m на форму в компоненты nUDn, nUDm.

 Считываем строку с файла и преобразуем ее в вектор строк (vect).

В vect[0] будет n, а в  vect[1] будет m (см. в спецификации размещение данных).

Выполняем контроль n и m и заносим их в компоненты nUDn и nUDm.

Перенос FO на форму в компоненту tbFO.

Считываем FO (может занимать несколько строк) с файла в строку S и преобразуем ее в вектор строк (vect), который переписываем в tbFO без контроля.

  КОНЕЦ

    В этой подзадаче есть подзадачи, но они реализуются простыми средствами языка C#, без  оформления их отдельными методами.

 

    Реализуем данную подзадачу на C#.

 

public void Move_Gr_fileToEcran (StreamReader Potok. NumericUpDown nUDn, NumericUpDown nUDm,  TextBox tBFO, ref bool error)

{

//Перенос чисел n и m на форму в компоненты numericUpDown.

//Считываем строку с файла и преобразуем ее в вектор строк (vekt).

//В vect[0] будет n, а в  vect[1] будет m (см. в спецификации размещение данных)

har ch= ‘ ‘;

string str =Potok.ReadLine();

string [] vect=str.split();

n = int.Parse(vect[0]);        

m = int.Parse(vect[1]);

//Выполняем контроль n и m и заносим их в компоненты nUDn и nUDm

       if((n < 1) || (n > 20))

{         

      MessageBox.Show ("Ошибка ввода количества вершин графа");

error = true;

       return;

}

nUDn.Value = n;

if ((m < 1) || (m > 50))

{

       MessageBox.Show ("Ошибка ввода количества ребер графа");

error = true;

       return;            

}

nUDm.Value = m;

//Перенос FO на форму в компоненту tbFO.

//Считываем FO (может занимать несколько строк) с файла в строку S и преобразуем //ее в вектор строк (vect), который переписываем в tbFO без контроля.

string strp =””;

while ((str = Potok.ReadLine())!= “”)

      strp += str;

vect = strp.Split(ch);

int k = vect.Length;

tBFO.Clear();

for(int i=0; i<k;i++)

tBFO.Lines[i]=vect[i];

}

Этот метод записываем вместо заглушки (1.2).

    Приступаем к проектированию подзадачи (1.3). Ввод данных с экрана с контролем и построением матрицы смежности

Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBFO, ref int n, ref int m, ref [,] MS, ref bool error)

НАЧАЛО

       Считываем с экрана n, m;

       n =(int) nUDn.Value;//преобразуем в целое, так как Value типа decimal

       m = (int)nUDm.Value;

       Проверка количества элементов FO.

       int k=tBFO.Lines.Length;

       ЕСЛИ k<> n+2*m ТО

         Вывод (“Количество элементов FO неверно”);

         error=true;

         Выход;

       КЕСЛИ

//обнуляем матрицу смежности

       ДЛЯ i = 1 ДО n ЦИКЛ

ДЛЯ j = 1 ДО n ЦИКЛ

       MS [i,j]=0;

КЦИКЛ

КЦИКЛ

       Считываем FO и строим матрицу смежности (1.31 на рис. 22).

Контроль симметричности матрицы смежности (1.32 на рис. 22).

 

КОНЕЦ

Рис. 22

    В этом алгоритме есть две  подзадачи (1.31) и (1.32). Реализуем их в виде методов с типом.

    Реализация подзадачи (1.31) - считывание FO и построение матрицы смежности.

bool CreatMS(TextBox tBFO,ref int [,] MS)

НАЧАЛО

 L=0;//индекс строки в компоненте tBFO

int n =(int)Math.Sqrt(MS.Length);

       ДЛЯ i = 1 ДО n ЦИКЛ //по вершинам графа

                   // считываем первую вершину j, следующую за i

        j = int,Parse(tBFO.Lines [L]);

       //контроль j

ЕСЛИ (j<0) или (j>n) ТО

Вывод («Элемент FO - неверный»);

Выход true;

                   КЕСЛИ

                   //считывание остальных вершин j, следующих за i

    ПОКА (j <>0) ЦИКЛ

                      MS[i,j]:=1;

                     L=L+1;

        j = int.Parse(tBFO.Lines [L]);

         //контроль j

  ЕСЛИ (j<0) или (j>n) ТО

  Вывод («Элемент FO - неверный»);

  Выход true;

                      КЕСЛИ

 

     КЦИКЛ

                L=L+1;

        КЦИКЛ

         Выход false

КОНЕЦ

    Реализация подзадачи (1.32) – проверка симметричности матрицы смежности.

bool SimetrMS(int [,] MS,ref string msg)

НАЧАЛО

int n =(int)Math.Sqrt(MS.Length);

msg=””;

    ДЛЯ i = 1 ДО n ЦИКЛ

ДЛЯ j = i+1 ДО n ЦИКЛ

       ЕСЛИ MS [i,j]<> MS [j,i] ТО

                 msg =msg +”[“+значения(I,j и j,i)+”]”;

       КЕСЛИ

       ЕСЛИ msg<>”” ТО

                 msg =”Проверить ребра ”+msg

                  Выход true;

        ИНАЧЕ

                   Выход false;

         КЕСЛИ

КОНЕЦ

    В подзадачах (1.31) и (1.32) нет других подзадач. Запишем их на C# и подставим в подзадачу (1.3).

 

public bool CreatMS(TextBox tBFO,ref int [,] MS)

{

 int L=0;//индекс строки в компоненте tBFO

int n=(int)Math.Sqrt(MS.Length);

       for(int i = 0; i< n; i++) //по вершинам графа

       {

                   // считываем первую вершину j, следующую за i

        j = int,Parse(tBFO.Lines [L]);

       //контроль j

If((j<0) || (j>n))

{

MessageBox.Show («Элемент FO - неверный»);

return false;

                   }

                   //считывание остальных вершин j, следующих за i

    while(j <>0)

        {

                      MS[i,j-1]:=1;

                     L++;

        j = int.Parse(tBFO.Lines [L]);

         //контроль j

  If((j<0) || (j>n))ТО

  {

  MessageBox.Show («Элемент FO - неверный»);

  return false;

                      }

     }

                L=L+1;

        }

         return true;

}

 

public bool SimetrMS(int [,] MS,ref string msg)

{

int n=(int)Math.Sqrt(MS.Length);

for(int i = 0; i<n;i++)

              for(int j = i+1;j< n; j++)

if(MS [i,j]!= MS [j,i])

        msg =msg +”[(“+i.ToString()+”,” + j.ToString()+”)и(”+j.ToString()+”,” + i.ToString()+”)]”;

       if(msg!=””)

        {

                 msg =”Проверить ребра ”+msg;

                  return false;

        }

         else

               return true;

}

На рис. 23 отобразим записанные задачи на C#:

Рис. 23

 

    Подставляем эти задачи в подзадачу (1.3):

Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBFO, ref int n, ref int m, ref [,] MS, ref bool error)

НАЧАЛО

       Считываем с экрана n, m.

       n =(int) nUDn.Value;//преобразуем в целое, так как Value типа decimal

       m = (int)nUDm.Value;

       Проверка количества элементов FO.

       int k=tBFO.Lines.Length;

       ЕСЛИ k<> n+2*m ТО

         Вывод (“Количество элементов FO неверно”);

         error=true;

         Выход;

       КЕСЛИ

//обнуляем матрицу смежности

       ДЛЯ i = 1 ДО n ЦИКЛ

ДЛЯ j = 1 ДО n ЦИКЛ

       MS [i,j]=0;

КЦИКЛ

КЦИКЛ

       //Считываем FO и строим матрицу смежности (1.31)

ЕСЛИ не CreatMS(tBFO,ref MS) ТО

  error=true

               Выход

       КЕСЛИ 

//Контроль симметричности матрицы смежности (1.32)

string msg=””;

ЕСЛИ не SimetrMS(MS,ref msg)ТО

  Вывод (msg);

  error=true;

               Выход;

       КЕСЛИ 

КОНЕЦ

 

    Записываем подзадачу (1.3) на C#, подставляем ее вместо заглушки (1.3) и отлаживаем основной алгоритм.

public void Input_GrInEkran (NumericUpDown nUDn, NumericUpDown nUDm, TextBox tBFO, ref int n, ref int m, ref int [,] MS, ref bool error)

{

       //Считываем с экрана n, m.

       n =(int) nUDn.Value;//преобразуем в целое, так как Value типа decimal

       m = (int)nUDm.Value;

      // Проверка количества элементов FO.

       int k=tBFO.Lines.Length;

       if (k!= n+2*m)    

       {

         MessageBox.Show (“Количество элементов FO неверно”);

         error=true;

         return;

       }

//обнуляем матрицу смежности

       f or(int i = 0; i< n; i++)

               for(int j = 0; j< n; j++)

 MS [i,j]=0;

       //Считываем FO и строим матрицу смежности (1.31)

if(!CreatMS(tBFO,ref MS))

{

  error=true;

               return;

      } 

//Контроль симметричности матрицы смежности (1.32)

string msg=””;

if(!SimetrMS(MS,ref msg))

{

  MessageBox.Show (msg);

  error=true;

               return;

       } 

}

 

    Переходим к проектированию подзадачи (1.4). Расчёт диаметра графа.

int Radius(int[,]MS)

НАЧАЛО

      int n =(int)Math.Sqrt(MS.Length);

   int r=1;

   int[,] MR=new int[n,n];

   int[,] B1=new int[n,n];

   int[,] B2=new int[n,n];

   bool pr =true;

  копировать матрицу MS в MR=MS(1.41)

  копировать матрицу MS в В1=MS

   ПОКА pr ЦИКЛ

         Pr=false;

         r=r+1;

         Умножение матриц В2=В1*MS(1.42)

          ДЛЯ i=1 ДО n ЦИКЛ

                  ДЛЯ j=1 ДО n ЦИКЛ

                           ЕСЛИ (MR[I,j]=0) и (B2[I,j]<>0) ТО

                                    MR[I,j]=r;

                                    Pr=true;

                           КЕСЛИ

                  КЦИКЛ

          КЦИКЛ

          копировать матрицу B2 в В1=B2

   КЦИКЛ

   Возврат r-1

КОНЕЦ

Рис. 24

    В данном алгоритме есть две подзадачи (рис. 24). Реализуем их.

    Подзадача (1.4.1) -    копирование матрицы.

CopyMatr(int [,] A,ref int [,] B)

НАЧАЛО

  Int n =(int)Math.Sqrt(A.Length);

  ДЛЯ i=1 ДО n ЦИКЛ

            ДЛЯ j=1 ДО n ЦИКЛ

                   B[I,j]=A[I,j];

            КЦИКЛ

   КЦИКЛ

КОНЕЦ

    Подзадача (1.4.2) - умножение матриц С=А*В

  MulMatr(int [,] A, int [,] B,ref int[,]C)

НАЧАЛО

  int n =(int)Math.Sqrt(A.Length);

  int S;

  ДЛЯ i=1 ДО n ЦИКЛ

            ДЛЯ j=1 ДО n ЦИКЛ

                   S=0;

                  ДЛЯkj=1 ДО n ЦИКЛ

                         S=S+A[I,k]*B[k,j]

                  КЦИКЛ

                  C[I,j]=S;

            КЦИКЛ

   КЦИКЛ

КОНЕЦ

Обе подзадачи запишем на языке C# и подставим в алгоритм (1.4).

public void CopyMatr(int [,] A,ref int [,] B)

{

iInt n =(int)Math.Sqrt(A.Length);

   for(int i=0;i< n; i++)

        for(intji=0;j< n; j++)

               B[i,j]=A[i,j];

}

 

  public void MulMatr(int [,] A, int [,] B,ref int[,]C)

{

  int n =(int)Math.Sqrt(A.Length);

  int S;

   for(int i=0;i< n; i++)

        for(int j=0;j< n; j++)

       {

                   S=0;

                  for(int k=0;k< n; k++)

                         S=S+A[i,k]*B[k,j]

                  C[i,j]=S;

         }

}

На рис. 25 отобразим записанные задачи на C#:

Рис. 25

 

Подставляем задачи в алгоритм (1.4).

int Diametr(int[,]MS)

НАЧАЛО

      int n =(int)Math.Sqrt(MS.Length);

   int r=1;

   int[,] MR=new int[n,n];

   int[,] B1=new int[n,n];

   int[,] B2=new int[n,n];

   bool pr =true;

  //копировать матрицу MS в MR=MS(1.41)

CopyMatr(MS,ref MR)

// копировать матрицу MS в В1=MS

  CopyMatr(MS,ref B1)

   ПОКА pr ЦИКЛ

         pr=false;

         r=r+1;

        // Умножение матриц В2=В1*MS(1.42)

        MulMatr(B1, MS, ref B2)

        ДЛЯ i=1 ДО n ЦИКЛ

                  ДЛЯ j=1 ДО n ЦИКЛ

                           ЕСЛИ (MR[I,j]=0) и (B2[I,j]<>0) ТО

                                    MR[I,j]=r;

                                    Pr=true;

                           КЕСЛИ

                  КЦИКЛ

          КЦИКЛ

          //копировать матрицу B2 в В1=B2

          CopyMatr(B2,ref B1)

   КЦИКЛ

    Возврат r-1;

КОНЕЦ

 

Запишем алгоритм на C# и подставим его вместо заглушки (1.4).

public int Diametr(int[,]MS)

{

      int n =(int)Math.Sqrt(MS.Length);

   int r=1;

   int[,] MR=new int[n,n];

   int[,] B1=new int[n,n];

   int[,] B2=new int[n,n];

   bool pr =true;

  //копировать матрицу MS в MR=MS(1.41)

CopyMatr(MS,ref MR)

// копировать матрицу MS в В1=MS

  CopyMatr(MS,ref B1)

   while (pr)

   {

         pr=false;

         r=r+1;

        // Умножение матриц В2=В1*MS(1.42)

        MulMatr(B1, MS, ref B2)

        For(int i=0; i< n; i++)

                  For(int j=0; j< n; j++)

                           if((MR[i,j]=0) && (B2[i,j]<>0))

                           {

                                    MR[i,j]=r;

                                    pr=true;

                            }

          //копировать матрицу B2 в В1=B2

          CopyMatr(B2,ref B1)

   }

   return r-1

}

Окончательный проект (рис. 26):

Рис. 26