Решение задач с использованием структурных моделей

Размещено на http://www.allbest.ru/

Федеральное государственное автономное

образовательное учреждение

высшего образования

«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Институт космических и информационных технологий

Информационные системы

Лабораторная работа

Компьютерное математическое моделирование

Решение задач с использованием структурных моделей

Преподаватель Н.В. Молокова

Студент ВКИ 13-13Б 031009698 Г.С. Смоленков

Красноярск 2016

Задание

Построение алгоритма

Пусть в рассматриваемой модели число горизонтальных «улиц» равно n, а вертикальных -m. Все данные задачи, входные и выходные, можно свести в массив c размерностью 2n - 1 строк и 2m- 1 столбцов. Начальные (входные) данные - стоимости горизонтальных участков - занимают в этом массиве места с нечетными номерами строк и четными номерами столбцов; входные данные - стоимости вертикальных участков - занимают места с четными номерами строк и нечетными номерами столбцов. Остальные элементы определяются в ходе исполнения алгоритма.

Порядок, в котором формируется массив выходной информации таков. Вначале заполняются правый столбец и верхняя строка. Затем находится элемент d3,2m 3 и решается вопрос, где поставить стрелку- справа или сверху от него. Затем находятся элементы диагонали d3,2m-5, d5,2m-3 ? и определяется местоположение связанных с ними стрелок, затем элементы следующей диагонали d3,2m-7, d5,2m-5, d7,2m-3 и т. д., пока не дойдем до элемента d2n-1,1.

Алгоритм работает при произвольном размере массива



программирование компьютер массив

Реализация алгоритма

Согласно блок схеме составлена программа на языке программирования C#.

Код программы:

Matrix.cs

using System;

using System.Collections.Generic;

namespace MathLab5

{

public class Matrix

{

public Matrix(int column, int row, List<int> array)

{

if (column * row != array.Count)

{

throw new ArgumentException("Не верное соотношение колонок и столбцов");

}

Column = column;

Row = row;

Array = array;

}

public int Column { get; private set; }

public int Row { get; private set; }

public List<int> Array { get; private set; }

}

enum Arrow

{

ArrowUp = 1111111,

ArrowRight= 222222,

};

}

MatrixCalculator.cs

using System;

using System.Collections.Generic;

using System.Diagnostics.Eventing.Reader;

using System.Globalization;

using System.IO;

using System.Linq;

using System.Runtime.InteropServices.WindowsRuntime;

namespace MathLab5

{

public class MatrixCalculator

{

public static QuadroMatrix BuildMatrix(string path)

{

Matrix MatrixX;

Matrix MatrixY;

using (var reader = new StreamReader(path))

{

MatrixX = ReadArray("x", reader);

}

using (var reader = new StreamReader(path))

{

MatrixY = ReadArray("y", reader);

}

return BuildQuadroMatrix(MatrixX, MatrixY);

}

private static QuadroMatrix BuildQuadroMatrix(Matrix matrixX, Matrix matrixY)

{

var quadro = new int[matrixX.Row * 2 - 1, matrixY.Column * 2 - 1];

var indexX = 0;

var indexY = 0;

for (int x = 0; x < quadro.GetLength(0); x++)

{

for (int y = 0; y < quadro.GetLength(1); y++)

{

if ((x % 2 == 0) && (y % 2 != 0))

{

quadro[x, y] = matrixX.Array[indexX++];

}

if ((x % 2 != 0) && (y % 2 == 0))

{

quadro[x, y] = matrixY.Array[indexY++];

}

}

}

return new QuadroMatrix(matrixX.Row, matrixY.Column, quadro);

}

private static Matrix ReadArray(string typeArray, StreamReader reader)

{

var array = new List<int>();

int row = 0;

int column = 0;

while (!reader.EndOfStream)

{

var line = reader.ReadLine();

if (string.IsNullOrWhiteSpace(line))

{

continue;

}

if (line.Contains(typeArray))

{

row++;

var newline = line.Replace(typeArray, "");

var intList = newline.Trim()

.Split(' ')

.Select(r => int.Parse(r.Trim()))

.ToList();

if (column == 0)

{

column = intList.Count;

}

else if (intList.Count != column)

{

throw new Exception(string.Format("В строке {0} не верное число элементов. должно быть {1}", line, column));

}

array.AddRange(intList);

}

}

return new Matrix(column, row, array);

}

public static int[,] CalculateWays(QuadroMatrix quadro)

{

var inputMatrix = quadro.Matrix;

var waysArray = new int[inputMatrix.GetLength(0), inputMatrix.GetLength(1)];

waysArray[0, waysArray.GetLength(1) - 1] = 0; //Стоимость конечной точки равна нулю.

//Заполняем вернхнюю строку числами и стрелками.

for (int y = waysArray.GetLength(1) - 1; y > 1; y--, y--)

{

waysArray[0, y - 2] = waysArray[0, y] + inputMatrix[0, y - 1];

waysArray[0, y - 1] = (int)Arrow.ArrowUp;

}

//Заполняем правый столбец числами и стрелками.

var lastRowIndex = waysArray.GetLength(1) - 1;

for (int x = 2; x < waysArray.GetLength(0); x++, x++)

{

waysArray[x, lastRowIndex] = waysArray[x - 2, lastRowIndex] + inputMatrix[x - 1, lastRowIndex];

waysArray[x - 1, lastRowIndex] = (int)Arrow.ArrowRight;

}

//Проходим диагональ

for (int col = 1; col <= quadro.Column - 1; col++)

{

for (int i = 2, j = 2 * quadro.Column - 1 - (2 * col)-1; (i <= 2 * quadro.Row - 1) && (j <= 2 * quadro.Column - 3); i += 2, j += 2)

{

var tempA = inputMatrix[i, j+1] + waysArray[i, j+2];

var tempB = inputMatrix[i-1, j] + waysArray[i-2, j];

if (tempA < tempB)

{

waysArray[i, j] = tempA;

waysArray[i, j + 1] = (int)Arrow.ArrowUp;

}

else

{

waysArray[i, j] = tempB;

waysArray[i - 1, j] = (int)Arrow.ArrowRight;

}

}

}

for (int row = 1; row < quadro.Row -1; row++)

{

for (int i = 2*row+2,j=0; (i <= 2*quadro.Row-1)&&(j <= 2*quadro.Column-2); i+=2,j+=2)

{

var tempA = inputMatrix[i, j + 1] + waysArray[i, j + 2];

var tempB = inputMatrix[i - 1, j] + waysArray[i - 2, j];

if (tempA < tempB)

{

waysArray[i, j] = tempA;

waysArray[i, j + 1] = (int)Arrow.ArrowUp;

}

else

{

waysArray[i, j] = tempB;

waysArray[i - 1, j] = (int)Arrow.ArrowRight;

}

}

}

return waysArray;

}

}

}

Printer.cs

using System;

using System.Text;

namespace MathLab5

{

public class Printer

{

public static void Print(Action<string> Write, Action<string> WriteLine, int[,] matrix)

{

for (int i = 0; i < matrix.GetLength(0); i++)

{

for (int j = 0; j < matrix.GetLength(1); j++)

{

string writeResult = "";

if (i % 2 != 0 || j % 2 != 0)

{

if (matrix[i, j] == (int)Arrow.ArrowRight || matrix[i, j] == (int)Arrow.ArrowUp)

{

var arrow = (Arrow)matrix[i, j];

switch (arrow)

{

case Arrow.ArrowUp:

writeResult = '>'.ToString() + " ";

break;

case Arrow.ArrowRight:

writeResult = '^'.ToString() + " ";

break;

}

}

else

{

writeResult = " ";

}

}

else

{

writeResult = string.Format("{0}", matrix[i, j]);

}

Write(writeResult);

}

WriteLine("");

}

for (int i = 0; i < matrix.GetLength(0); i++)

{

for (int j = 0; j < matrix.GetLength(1); j++)

{

string writeResult = "";

if (i % 2 != 0 || j % 2 != 0)

{

if (matrix[i, j] == (int)Arrow.ArrowRight || matrix[i, j] == (int)Arrow.ArrowUp)

{

var arrow = (Arrow)matrix[i, j];

switch (arrow)

{

case Arrow.ArrowUp:

writeResult = '>' + " ";

break;

case Arrow.ArrowRight:

writeResult = "\u2192" +

"" + " ";

break;

}

}

else

{

writeResult = " ";

}

}

else

{

writeResult = string.Format("{0}", matrix[i, j]);

}

Console.Write(writeResult);

}

Console.WriteLine();

}

}

}

}

Program.cs

using System;

using System.Collections.Generic;

using System.IO;

using System.Linq;

using System.Runtime.InteropServices;

using System.Text;

using System.Threading.Tasks;

namespace MathLab5

{

class Program

{

private static string message = "";

static void Main(string[] args)

{

var isWork = true;

do

{

try

{

Console.WriteLine(

" Файл должен состоять из строк, при этом строки массива X должны начинаться с символа 'x'");

Console.WriteLine("строки массива Y с символа 'y'. Разделитель между числами - пробел.");

Console.WriteLine("Введите путь к файлу с исходными данными");

string path = Console.ReadLine();

//var inputMatrix = MatrixCalculator.BuildMatrix(@"D:\учеба\3 курс\Мат мод\input.txt");

var inputMatrix = MatrixCalculator.BuildMatrix(path);

Console.WriteLine("Введите путь к файлу с выходными данными:");

string pathOut = Console.ReadLine();

//pathOut = @"D:\учеба\3 курс\Мат мод\output.txt";

Console.WriteLine("Формируем исходные данные...");

Console.WriteLine();

PrintMatrix(inputMatrix.Matrix);

Console.WriteLine();

Console.WriteLine("Выводим результат...");

int[,] result = MatrixCalculator.CalculateWays(inputMatrix);

Printer.Print(Console.Write, Console.WriteLine, result);

using (var writter = new StreamWriter(pathOut, false, Encoding.GetEncoding(1251)))

{

Printer.Print(writter.Write, writter.WriteLine, result);

}

Console.WriteLine("Успешно!");

}

catch (Exception ex)

{

Console.WriteLine("Что-то пошло не так....");

Console.WriteLine(ex.Message);

}

finally

{

Console.WriteLine("Для выхода нажмиет Esc, для продолжения любую клавишу...");

var t = Console.ReadKey();

if (t.Key == ConsoleKey.Escape)

{

isWork = false;

}

}

} while (isWork);

}

private static void PrintMatrix(int[,] matrix)

{

for (int x = 0; x < matrix.GetLength(0); x++)

{

for (int y = 0; y < matrix.GetLength(1); y++)

{

var write = string.Format("{0} ", matrix[x, y] == 0 ? " " : matrix[x, y] < 10 ? ("0" + matrix[x, y].ToString()) : matrix[x, y].ToString());

Console.Write(write);

}

Console.WriteLine();

}

}

}

}

QuadroMatrix.cs

namespace MathLab5

{

public class QuadroMatrix

{

public QuadroMatrix(int row, int column, int[,] matrix)

{

Row = row;

Column = column;

Matrix = matrix;

}

public int Row { get; }

public int Column { get; }

public int[,] Matrix { get; }

}

}

Решение задачи

Ввод данных согласно варианту

x 35 30 33 14 30 40

x 28 19 22 23 19 24

x 44 17 16 28 14 31

x 27 39 19 21 23 18

x 16 41 26 11 41 19

y 26 30 16 14 22 31 21

y 28 29 19 28 17 29 12

y 31 22 33 24 29 17 26

y 19 25 22 30 19 25 28



Вывод данных

Оптимальный путь отображен на схеме

182> 147> 117> 84> 70> 40> 0

^

148> 120> 101> 79> 56> 37> 13

^

156 120> 103> 87> 59> 45 24

^

159> 132 108> 89> 68 54> 36

^

161> 145 117> 91> 80 65 51

Вывод

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

Размещено на Allbest.ru

...