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

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

Пусть в рассматриваемой модели число горизонтальных «улиц» равно 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 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 Array { get; private set; }.

}.

enum Arrow.

{.

ArrowUp = 1 111 111,.

ArrowRight= 222 222,.

};

}.

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 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 Write, Action 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; }.

}.

}.