Данному образовательному сайту пришлось несколько раз менять свое имя. С 2011 года доступ к нему обеспечивается по URL
http://educomp.runnet.ru

emc.km.ru (2001-2007) ==> educomp.org.ru (2007-2011) ==> educomp.runnet.ru (2011-...)
Более подробно об истории сайта можно прочитать здесь.


Учебные модели компьютера



Модели (software):

"Е14" (parallel !!!)
"S9PU" (parallel)

Модели (hardware):






Награды сайта
Награды сайта

В предыдущем разделе приведен пример линейной программы на языке машинных команд УК "Нейман". Теперь рассмотрим задачу, решение которой требует составления циклической программы.

Задача. Сколько различных N-буквенных слов можно составить путем перестановок данных N букв ?

Из комбинаторики известно, что количество различных комбинаций из N предметов, получаемых изменением их порядка, называется числом перестановок. Это число выражается функцией от N, которая называется факториалом и записывается так: N! Читается : "N факториал". Для любого натурального N значение N! вычисляется как произведение последовательности натуральных чисел от 1 до N. Например:

                 1! = 1
                 2! = 1*2 = 2
                 3! = 1*2*3 = 6
                 4! = 1*2*3*4 = 24
                 5! = 1*2*3*4*5 = 120
и т.д.

Теперь вернемся к формулировке задачи. Если N обозначает количество букв, а F - количество слов из этих букв, то постановка задачи выглядит так:

                Дано:  N           Расчетная формула:
                Найти: F                 F = N!
Рассмотрим два варианта алгоритма решения этой задачи: первый вариант с циклом-пока, второй вариант с циклом-до. Запрограммируем оба алгоритма. Опишем на алгоритмическом языке первый вариант алгоритма:
     алг  ЗАДАЧА
     цел  F,N,R
     нач  ввод N
        F:=1
        R:=1    
        пока R<=N
        нц
           F:=F*R 
           R:=R+1
        кц 
        вывод F
     кон

Распределение памяти. Составление программы начинается с распределения памяти под данные. Поскольку команды программы всегда располагаются, начиная с 0-й ячейки, то данные можно располагать только после окончания программы. Обычно вначале помещаются константы, затем – переменные.

В программе будут использованы одна константа (1), три переменные (N,F,R) и еще одна дополнительная переменная (Q), которая в алгоритме не отражена.

                 Величина   1   N   F   R   Q
                 Ячейка     28  2C  30  34  38
Составление программы.

Таблица 3

Адрес КОП А1 А2 А3 Пояснения
00 00FC 002C ввод N
04 0028 0030 F:=1
08 0028 0034 R:=1
0C 0234 2C38 Q:=R-N
10 0A00 0020 при Q>0 идти к 20
14 0330 3430 F:=F*R
18 0134 2834 R:=R+1
1C 0B00 000C идти к 0С
2000 3000 FC вывод F
24 7700 0000 останов
28 0000 0001 константа 1

В этой программе кроме уже знакомых команд используются две команды управления. Команда безусловного перехода имеет вид:

0B -- -- A3

Эта команда производит передачу управления к команде программы по адресу А3. Содержимое A1 и А2 значения не имеют.

В нашей программе команда безусловного перехода стоит в ячейке 1C. Ее выполнение приводит к тому, что следующей будет выполняться команда в ячейке 0C. Таким образом происходит возврат управления к началу цикла.

Команда условного перехода:

0A -- -- А3

Эта команда передает управление к ячейке программы А3, если значение регистра-признака W равно 1. Если W=0, то управление перейдет к следующей команде.

Второй вариант алгоритма с циклом с постусловием:

     алг  ЗАДАЧА 3
     цел  F,N
     нач  ввод N
        F:=1
        повторять
           F:=F*N
           N:=N-1
        до  N=0
        вывод F
     кон

В программе будут использоваться всего две переменные и константа 1. Выделим под них память:

                 Величина   1   F   N
                 Ячейка     1С  20  24

Запишем программу на ЯМК.

Таблица 4

Адрес КОП А1 А2 А3 Пояснения
00 00FC 0024 ввод N
04 00 0020 F:=1
08 03 20 24 20 F:=F*N
0C 0224 1C24 N:=N-1
10 0A00 0008 при N>0 идти к 08
14 0020 00FC вывод F
18 7700 0000 стоп
1C 0000 0001 константа 1

Обратите внимание на то, что в этой программе не понадобилась команда безусловного перехода. Не понадобилось также дополнительной переменной Q. Управлением цикла занимается команда условного перехода в 10-й ячейке. Пока значение N>0 эта команда передает управление на ячейку 08. Когда в результате выполнения команды в ячейке 0С получится нуль, признак W станет равным нулю и цикл закончит работу. Управление передастся в ячейку 14.

Второй вариант программы вместе с данными занимает 10 ячеек, тогда как первый вариант - 15 ячеек.


© И.Г.Семакин, 2001
Полный текст статьи в виде документа MS Word можно загрузить здесь.
© Оформление Web-страницы Е.А.Еремин, 2001


Автор сайта - Евгений Александрович Еремин (Пермский государственный педагогический университет). e_eremin@yahoo.com