Главная  Полное построение алгоритма 

[0] [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] [112] [113] [114] [115] [116] [117]

создать возможный тур коня (рис. 2.1ЛЗ, а). Это должно включать построение пути и затем распечатку результата (рис. 2.1.13, б). Построение пути сводится к выбору начальной позиции (рис. 2.1.13, е) и затем построению маршрута из этой позиции.

Здесь у нас есть достаточно хороший способ выбора начальной позиции, например считывая два целых числа (/, J), принимающих значения от 1 до 8. Мы также видим, что распечатка результатов предполагает распечатку целых значений, которые хранятся в соответствующем шахматной доске массиве (BOARD (/, J)). Поэтому теперь нам нужно сосредоточиться на том, как построить путь, начинающийся в поле (/, /).

Из того факта, что целые числа хранятся в массиве BOARD (/, J), следует необходимость присвоить всем элементам массива начальные значения, равные О (р.чс. 2.1.13, г). Таким образом, ход на поле {J, J) возможен при BOARD (/, 7)=0. Далее, выход за пределы доски можно обнаружить, проверив принадлежность значений / и J отрезку значений целых чисел [I, 8].

Выход за пределы доски можно обнаружить также и по другой схеме (рис. 2.1.14). Добавим по два дополнительных ряда полей к каждому краю массива BOARD и занесем в каждое новое поле некоторое начальное значение, например 99. Тогда попытка выйти за пределы доски обнаруживается по ненулевому значению рассматриваемого поля.

Закончив с присваиванием начальных значений массиву BOARD, вернемся опять к задаче построения тура из произвольного поля (/, J). Мы должны попытаться разбить этот этап на последовательность меньших этапов, сводящихся к операторам if-then-e!se, do-vhi!e или while-do.

Здесь мы начинаем ощущать, что нам не обойтись без основного цикла, в котором некоторый индекс, скажем К, пробегает множество всех возможных полей, на которые можно пойти с поля (/, J). Движение коня приостанавливается, когда /(>8. Из этого следует разбиение обсуждаемого этапа, представленное на рис. 2.1.15, а.

При попытке пойти на новое поле из поля (/, J) может произойти одно из двух: либо ход возможен, и тогда мы заменяем значение (/, J) на новое, присваивая К значение 1, либо ход невозможен, и тогда значение К увеличивается на 1 (рис. 2.1.15, б).

Остается еще определить значение К для поля (/, J). Для этой цели создается специальная таблица (рис. 2.1.16), в которой указываются модификации значений / и / для определения поля К- Теперь мы можем завершить построение нашей окончательной структурированной блок-схемы, которая приведена на рис. 2.1.17.

Реализация этого алгоритма на Фортране приведена на следующем рисунке (рис. 2.1.18). В качестве упражнения напишите и пропустите на машине программу для этого алгоритма и проверьте, можею ли



СозЗоть Возможный турконя

Выфать нача/гьте

Расгсчтать peay-ibmamb/

Построить путь из nom{l,J)

Построить пс/Шь

Распечатать результаты

Вбфать начальное noeiJ.J)

Игщиализо

ровать 1

Построить путь из no/iniJJ)

Распечатать результаты

Рис. 2.1.113. Разработка алгоритма возможного тура копя методом сверху-вниз.

Рис. 2.1.14. ПервоначЕльная конфигурация на доске.




Попытаться пойти m/<-oem/reu3{r,J); получить ноВое значение К


Рис. 2.1.15. Продолжение разработки алгоритма «тур коня» методом сверху-вниз.

К Х-перемещате J-nepeHemeime-

1 2 3 4 5 6 7 8

-2 -1 +1 +2 +2 +1 -1 -2

+1 +2 +2 .+1 -1 -2 -2 -1

Рис. 2.1.16. Таблица модификации значений / и / для хода на новое поле /С.



[0] [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] [112] [113] [114] [115] [116] [117] обсада

0.0011