Данному образовательному сайту пришлось несколько раз менять свое имя. С 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):






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

"Кроха": примеры решения задач для ЭВМ "Кроха"

1. Составить программу вычисления периметра прямоугольника по длинам сторон. (Задача N 3а из учебника)

Р Е Ш Е Н И Е

Обозначим стороны прямоугольника a и b, а результат - P.

Вычисления будем вести по формулам: P = a + b; P = P + P. Такая последовательность вычислений обеспечивает наиболее экономичную (с точки зрения использования числа ячеек памяти) программу, т.к. не требуется отводить специальную ячейку под число 2.
АдресКомандаРасшифровкаКомментарий
000001 110 111 101 (6) + (7) ==> (5)a + b ==> P
001001 101 101 101 (5) + (5) ==> (5)P + P ==> P
010111 110 111 101 стоп; вывод (6), (7), (5)вывод a, b, P
011не используется
100не используется
101P  результат
110b  исходные
111a      данные



2. Составить программу вычисления половины полной поверхности параллелипипеда по длинам ребер. (Задача N 3в из учебника)

Р Е Ш Е Н И Е

Обозначим ребра параллеллипипеда a, b и c, а результат - s.

Вычисления будем вести по формуле: s = ab + bc + ac = b(a + c) + ac, что уменьшит количество арифметических действий, а значит и команд. Полученную формулу удобно разбить на две: r = b(a + c); s = ac + r
АдресКомандаРасшифровкаКомментарий
000001 101 111 000 (5) + (7) ==> (0)a + c ==> r [ r ]
001101 110 000 000 (6) * (0) ==> (0)b * r ==> r [ s ]
010101 101 111 001 (5) * (7) ==> (1)a * c ==> s
011001 000 001 001 (0) + (1) ==> (1)s + r ==> s
100111 001 001 001 стоп; вывод (1), (1), (1)вывод s
101a  исход-
110b      ные
111c      данные

Особенностью данной задачи является нехватка ячеек памяти для проведения вычислений. Поэтому приходится помещать рабочую переменную r и результат s на место уже отработавших команд программы. Нельзя сказать, что это удобно (перед каждым запуском первые команды приходится восстанавливать!), но другого способа решения для памяти из 8 ячеек нет.



3. Написать программу нахождения наибольшего из двух хранящихся в ячейках памяти чисел. (Задача N 4 из учебника)

Р Е Ш Е Н И Е

Обозначим исходные числа a и b, а результат max.
АдресКомандаРасшифровкаКомментарий
000110 110 111 011 если (6)>(7), перейти к 3сравнить a и b
001000 111 000 101 (7) ==> (5)a ==> max
010111 111 110 101 стоп; вывод (7), (6), (5)вывод a, b, max
011000 110 000 101 (6) ==> (5)b ==> max
100111 111 110 101 стоп; вывод (7), (6), (5)вывод a, b, max
101max  результат
110b  исходные
111a      данные

Примечание. Вместо команды "стоп" по адресу 010 можно выполнить безусловный переход на команду 100. Казалось бы, команды безусловного перхода у "Крохи" нет. Но проанализируем команду

100 000 000 100 - если (0) = (0), переход на (100).
Т.к. (0) = (0) всегда, то этот переход тоже будет происходить всегда. Чем не безусловный переход?



4. Написать программу деления двух чисел с учетом возможности деления на ноль (в последнем случае отобразить на экране все нули).

Р Е Ш Е Н И Е

Обозначим исходные числа a и b, а результат d.
АдресКомандаРасшифровкаКомментарий
000100 101 111 011 если (5)=(7), перейти к 3сравнить b с 0
001010 110 101 100 (6) / (5) ==> (4)a / b ==> d
010111 110 101 100 стоп; вывод (6), (5), (4)вывод a, b, d
011111 111 111 111 стоп; вывод (7), (7), (7)вывод 0, 0, 0
100d  результат
101b  исходные
110a      данные
111000 000 000 0000константа 0



5. Заданы два числа a и b. Написать программу, которая большее из них делит на меньшее.

Р Е Ш Е Н И Е

Обозначим результат d.
АдресКомандаРасшифровкаКомментарий
000110 110 111 011 если (6)>(7), перейти к 3сравнить a и b
001010 111 110 101 (7) / (6) ==> (5)a / b ==> d
010111 111 110 101 стоп; вывод (7), (6), (5)вывод a, b, d
011010 110 111 101 (6) / (7) ==> (5)b / a ==> d
100111 111 110 101 стоп; вывод (7), (6), (5)вывод a, b, d
101d  результат
110b  исходные
111a      данные



6. Написать программу вычисления n!

Р Е Ш Е Н И Е

Обозначим k рабочую переменную, которая является текущим множителем для факториала и меняется от 1 до n. Начальное значение k придется задавать перед каждым запуском "вручную", т.к. для команды пересылки константы 1 из ячейки 7 в ячейку 4 уже не хватает памяти. То же самое можно сказать и про начальное значение n!, которое перед запуском естественно установить равным 1.

Не забудьте также в ячейку 6 занести значение n + 1, которое является верхней границей цикла (цикл будет выполняться, пока k < n+1 и, следовательно, завершится после умножения на n).
АдресКомандаРасшифровкаКомментарий
000101 101 100 101(5) * (4) ==> (5)n! * k ==> n!
001001 100 111 100(4) + (7) ==> (4)k + 1 ==> k
010110 110 100 000если (6)>(4), перейти к 0k < n + 1 ?
011111 101 101 101стоп; вывод (5),(5),(5)вывод n!
100k [задать 1] рабочая ячейка
101n! [задать 1] результат
110n + 1 [задать] константа
111000 000 000 0011константа 1

При работе с программой полезно обратить внимание на эффект переполнения, который для быстрорастущего выражения типа факториал достигается довольно быстро. В самом деле, как подробно обсуждается в учебнике, максимально допустимое число для 12-разрядной "Крохи" равняется 4095. Таким образом, уже попытка вычислить 7! = 1*2*3*4*5*6*7 = 5040 приводит "Кроху" к непреодолимым вычислительным трудностям. Проверьте, как "Кроха" реагирует на переполнение.



7. Написать программу для вычисления выражения 1+2+3+4+...+n

Эта задача настолько похожа на предыдущую, что тратить силы на набор решения просто не поднимается рука. Отметим только, что начальное значение суммы (в отличие от факториала) надо задавать равным 0.



8. Написать программу вычисления выражения X*2n

Р Е Ш Е Н И Е

Для того, чтобы программа поместилась в память "Крохи", придется исходное выражение преобразовать к виду

X*2*2*...*2
Таким образом, решение задачи теперь свелось к удвоению значения X n раз, что удобно делать путем циклического сложения ячейки "самой с собой".
АдресКомандаРасшифровкаКомментарий
000001 101 101 101(5) + (5) ==> (5)X + X ==> X
001011 100 110 100(4) - (6) ==> (4)n - 1 ==> n
010110 100 111 000если (4)>(7), перейти к 0n > 0 ?
011111 101 101 101стоп; вывод (5),(5),(5)вывод X
100n исходные дан-
101X ные; результат
110000 000 000 0011константа 1
111000 000 000 0000константа 0



9. Вычислить выражение y=1*2*4*8*...*n

Р Е Ш Е Н И Е

Как нетрудно видеть из формулы для y, программа должна суммировать последовательные степени числа 2. Обозначим очередную степень s.

Особо отметим, что верхняя граница цикла в ячейке 7 переустанавливается программой. Вы перед пуском вводите в эту ячейку удобное для Вас значение n. Но машину это значение "не устраивает": ей требуется, чтобы верхняя граница равнялась 2 * n, только тогда последний учтенный сомножитель в цикле умножения будет равен n. Поэтому первой же командой ЭВМ удваивает 7-ю ячейку.
АдресКомандаРасшифровкаКомментарий
000001 111 111 111(7) + (7) ==> (7)n + n ==> n
001101 101 110 110(5) * (6) ==> (6)s * y ==> y
010001 101 101 101(5) + (5) ==> (5)s + s ==> s
011110 111 101 001если (7)>(5), перейти к 1s < 2 * n ?
100111 110 110 110стоп; вывод (6),(6),(6)вывод y
101s [задать 1] рабочая ячейка
110y [задать 1] результат
111n [задать], 2 * n граница цикла



10. Вычислить выражение y=1+2+4+8+...+n

Задача решается аналогично. Отметим только, что верхняя граница цикла в ячейке 7 устанавливается равной n+1.

Для проверки правильности результата полезно помнить, что для m слагаемых ответ может быть вычислен по формуле

y = 2m - 1



11. Задача о самомодифицирующейся программе.

Задано состояние памяти ЭВМ "Кроха" перед пуском (см. ниже). Определить, каков будет результат выполнения программы.

КОММЕНТАРИЙ к условию. Данная задача представляет не столько практический, сколько теоретический интерес. Тем не менее, автор ее очень любит и считает важной. Дело в том, что в этой задаче отчетливо видно, что ЭВМ может сама формировать себе программу и что содержимое одной и той же ячейки памяти "Крохи" в разные моменты времени может быть и данными (числом), и командой. Не пожалейте времени на разбор этой задачи, если Вы действительно хотите глубоко понять принципы работы ЭВМ и передать свои знания ученикам !!!

Начальное состояние памяти ЭВМ "Кроха" для задачи 11
АдресКомандаРасшифровкаКомментарий
000001 111 110 001(7) + (6) ==> (1)формируем (1)
001не имеет значения
010не имеет значения
011001 001 010 011сумма ячеек (3) и (4) дает
100110 000 000 000команду стоп для (3)
101001 011 100 011(3) + (4) ==> (3) для (2)
110000 101 000 000сумма ячеек (6) и (7) дает
111000 000 000 010команду (5) ==> (2) для (1)

Р Е Ш Е Н И Е

Конечное состояние памяти ЭВМ "Кроха" для задачи 11
АдресКомандаРасшифровкаКомментарий
000001 111 110 001(7) + (6) ==> (1)формируем (1)
001000 101 000 010(5) ==> (2)формируем (2)
010001 011 100 011(3) + (4) ==> (3)формируем (3)
011111 001 010 011стоп; вывод (1), (2), (3)стоп
100110 000 000 000 константы со-
101001 011 100 011 храняются без
110000 101 000 000 изменения кро-
111000 000 000 010 ме ячейки (3)

В результате выполнения программы на экран ЭВМ будет выведено содержимое ячеек (1), (2) и (3), сформированное в ходе выполнения программы.



12*. Написать циклическую программу, заносящую 1 в ячейки (4)-(6).

Р Е Ш Е Н И Е

АдресКомандаРасшифровкаКомментарий
000000 111 000 100(7) ==> (4)1 ==> ячейку
001001 111 000 000(7) + (0) ==> (0)модиф. адрес
010110 111 110 000если (7)>(6), перейти к 0(6) < 1 ?
011111 100 101 110стоп; вывод (4),(5),(6)вывод ячеек
100не имеет значения [сюда
101не имеет значения   запишутся
110[задать 0]   единицы]
111000 000 000 0011константа 1

Эта задача не зря помечена звездочкой. Она, по-видимому, самая трудная для понимания. В значительной мере это объясняется ее некоторой искусственностью в рамках учебной ЭВМ "Кроха". Тем не менее идея модификации адресов команд на "настоящих" ЭВМ при работе с массивами реализуется аналогично.

Впрочем, если задача Вам не понравилась, можете смело ее пропустить. Для тех же, кто "вошел во вкус" или кому в наше нелегкое время посчастливилось иметь дело со способными учениками (для таких она и предназначается !), небольшой комментарий.

Для проверки окончания цикла используется следующий прием. Перед запуском в ячейку (6) заносится 0, поэтому при проверке условия в команде (2) переход срабатывает: 1>0. Так продолжается до записи в ячейку (6) единицы. После этого условие перестает выполняться и цикл прекращается.


©
Е.А.Еремин, 1995


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