1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 4
Текст из файла (страница 4)
ь содкгз<атвльньш анализ злдачи В т о р о й в ы в о д. Программы могут отличаться друг от друга сильнее и слабее: первая и вторая программы больше похожи друг на друга, нежели каждая иэ них на третью. Т р е т и й в ы в о д. Первые две программы настолько похожи, что даже лучше говорить, что это одна и та же программа, только с разнымн обозначениями для промежуточных величин— в первой программе они все разные, а во второй одни и те же. Ч е т в е р т ы й в ы в о д. Имеет смысл такая проблема: составить программу, используя наименьшее количество обозначений для величин. Это приводит к зкономии памяти.
Следует заметить, однако, что все эти выводы носят чисто наблюдательный характер. Автору первой программы не мешало бы спросить у своего коллеги, составившего вторую программу: «А как ты додумался весь счет вести через у?» Если второй автор не глуп, он не выразит недоумения, а, подумав, ответит: «Как только у умно>кается на х, он мне уже не нужен, и поэтому я могу это произведение направить туда же». В свою очередь первый автор, чтобы оправдать свой подход, ска»кет: «Но ведь у меня программа логичнее: х в пятой степени, например, никогда не будет равен х в третьей, вот я их и обозначил по-разному».
Второй заметит: «Но зато я зациклил и тем самым сократил свою программу»,— н покажет первому третий пример. Если кому-либо такая подача материала пока»кется слицжом примитивной, то мы заметим, что дискуссия двух авторов списана с реальных занятий по программированию, а в каждом из трех высказываний содержатся зерна истины, развитие которых постепенно приведет нас к решению задачи. В частности, мы немедленно попробуем обобщить сделанные замечания авторов программ в виде 'некоторых отправных принципов.
А. Прн сочинении программы мы из соображений удобства и логичности вводим различные обоаначения для исходных и промел<уточных величин задачи и для ее результатов. Если после получения символической программы распределить память по принципу «каждой величине свою ячейку», то может оказаться, что памяти будет израсходовано больше, чем это «на самом деле» нужно. Этот факт мок«но выразить и по-другому: можно переписать программу так, что она будет решать ту же задачу, но содержать меньшее количество обозначений.
Б. Сокращать число величин программы можно следующим образом: имея в команде (или операторе) некоторый результат, не надо торопиться вводить для него новое обозначение, а посмотреть, нет ли в данный момент «свободной» величины, т. е. такой, текущее значение которой больше не потребуется. Если такая величина есть, то опа и берется в качестве обозначения результата. Новые примеры.
Рассмотрим еще некоторое количество примеров. Пусть надо вычислить у = з»», опять-таки, не используя В 1 Е НАКОПЛЕНИЕ ФАКТОВ. ЛИНЕИНЫЕ ПРОГРАЗГМЬГ 27 операцию возведения в степень. Конечно, имея перед глазами пример 3, уже никому не захочется писать подряд 58 команд умножения, так что первый подход даст нам П р и м е р 4. Вычнслнть х".
начало вещ х, у; цел П ввод (х); у:= хХх; для 1: =- 1 шаг 1 до 57 цикл у:= — уХх; . -д(у) конец Однако зта программа, будучи весьма короткой, тем не менее очень долго работает: на решение задачи расходуется по меньшей мере 3 Х 57 действий: умножение, изменение 1 и сравнение его с 57. В то же время, если бы надо было вычислить 2ы (64 = 2'), то на зто потребовалось бы всего 6 умножений: р:= хХх (х'), у:= уХу (х'), у:= у~~у (хв), у.— уХу (х ), у:=у~у (х32), у: = у Х у ' (х"). Однако зто нарастание степеней двойки в геометрической прогрессии поможет нам и в нашем случае.
(А заинтересованный читатель без труда теперь додумается до правила для любого целого показателя степени.) Представим 59 как сумму степеней двойки: 59 = 32 ф- 16 + 8+ 2+ 1 (Тогда программу организуем так: вычислим подряд и сохраним значения степеней х с показателямн, равными степеням двойки, так чтобы последняя степень двойки была бы еще меньше исходного показателя, а следующая — уже больше. А потом перемножим друг на друга те степени х, у которых значения показателей входят как слагаемые в представление исходного показателя: хзв = хззух" хх'ххзхх. В результате получаем П р и м е р 5.
Вычислить х'о. начало вещ х, у, х2, х4, х8, х16, х32; ввод (х); х2:= хАх; х4:= х2Хх2; х8:= х4хх4; х16:= х8хх8; х32:= х16хх16; ГЛ. Ь СОДЕРЖАТЕЛЬНЫЙ АНАЛИЗ ЗАДАЧИ у:= хХх2; у:= уХх8; у:= уХх16; у:= ухх32; вывод (у) конец В заключительной части программы мы, под влиянием опыта 1-го и 2-го примеров, уже «велн вычисление через у», экономя обозначения промежуточных величин. Однако принцип Б побу»кдает нас более внимательно проверить программу и спросить себя, везде лн мы вводили новые величины «по необходимости», а не по инерции начальной идеи вычисления х'»? Наше рассуждение звучит примерно следующим образом.
Заку»«еруем операторы программы: 1: х2:= ххх; 2: х4:= х2хх2; 3: х8:= х4хх4; 4: х16:= х8Хх8; 5: х32:= х16Хх16; 6: у:= хХх2; 7: у:=- ухх8; 8: у:= уХх16; 9: у:= уХ32. Результат оператора 1 мы не можем присвоить х, так как тогда новый х будет равен х», а нам нужен исходный х в операторе 6. Результат оператора 2 мы не можем присвоить ни х, ни х2 по той же причине.
Однако после выполнения команды 3 нам уже не нужна величина х4 и мы можем ее результат присвоить той же переменной, заменив, естественно, х8 в командах 4 и 7 на х4. Просмотрев программу до конца, мы видим, что это единственная экономия на величинах, которую мы можем здесь себе позволить. П р и м е р 6. Вычислить х'».
начало вещ х, у, х2, х4, х16, х32; ввод (х); х2:= хХх; х4:= х2Хх2; х4:= х4хх4; х16:= х4хх4; х32:= х16 Хх16; у:= хХх2; у:= ухх4; Е ЬЕ НАКОПЛЕНИЕ ФАКТОВ. ЛИНЕИНЫЕ ПРОГРАММЫ тн у:= уХх(6; у;= ухх32; вывод (у) конец Наши кропотливые рассуждения о невозможности сэкономить обозначение величины во всех пяти первых операторах, кроме З-го, позволяют нам, однако, догадаться о причине этой невозможяости: мы плохо организовали нашу программу Мы сначала посчитали все «степени двойки», а только после этого начинаем их использовать.
Поступим по-другому: получив очередную «степень двойки», мы ее тут же «вгоним» в у, если она является слагаемым нашего показателя. Если же нет, то мы только употребим ее на получение следующей «степени двойки». Одновременно стараемся соблюдать принцип Б. Получаем П р и м е р 7. Вычислить х". начало вещ х, у, х2; ввод (х); 'х2:= ххх; у:= ххх2; х:= х2Хх2; х:= хХх; у:= уХх; х:= хХх у:= уХх; х:= хХх; у:= уХх; вывод (у) конец Этот результат удовлетворит всякого, но вы, читатель, не будете настоящим исследователем, если не спросите себя, а нельзя ли обойтясь меньшим количеством величин7 Утвердительный ответ, по-видимому, будет небольшим открытием для большинства; П р и и е р 8. Вычислить х'».
начало вещ х, у; ввод (х); у:= хХх; х:= хХу; у:= уХу; у:= уХу; х:= хХу; у:= уХу; х:= хХу; 20 ГЛ. 1. СОДЕРЖАТЕЛЬНЫЙ АНАЛИЗ ЗАДАС1Н у:= уХу; у:= хху; вывод (у) конец Тем, кто не додумался до этого примера, автор рекомендует в' качестве «утешительного аабега» доказать, почему в этой лрограмме нельзя обойтись меньшим количеством величин, т, е.
одной. Пауза для размьппления. После этих восьми примеров мы накопили достаточно материала, чтобы в нем разобраться, прежде чем двинуться дальше. Во-первых, мы окончательно поняли, что число обозначений величин в программе и число ячеек памяти— это непосредственно связанные друг с другом характеристики программы. Нет никакой принципиальной разницы между переменной величиной программы в алгоритмическом языке и ячейкой памяти машинной программы. Пока мы заняты построением программы, мы можем эти понятия отождествлять, и это нам действительно удобнее для рассуждения. Величина в программе — это не столько какая-нибудь физическая или математическая переменная величина, проникшая в программу из исходной формулировки задачи, сколько в чистом виде элемент памяти, своеобразная камера хранения.
В такой камере хранения хранится некоторое значение. Поступить туда оно может только как результат некоторого оператора или команды. Старое значение переменной величины при этом перестает существовать. Каждое значение в разумно составленной программе вырабатывается для того, чтобы позднее быть использованным в качестве аргумента в каком-то месте программы. Пока оно еще не испольаовано, хранящая его переменная величина «неприкосновенна» и ей нельзя присваивать нового значения. Таким образом, сколько величин используются в разных вариантах программы и как они обозначаются — не столь существенно, как то, что они должны сохранять все информационные связи в программе, т. е. «передачи» значений от результатов одних операторов к аргументам других. Второй вывод состоит в том;что существуют различные способы построения вариантов программы, как-то влияющих на количество величин в программе и их обозначения.
Первый способ состоит в том, что мы и»1еем, по существу, одну и ту же программу с различными наборами величин. Программа одна и та же в том смысле, что она состоит из одних и тех же команд с одними н теми жь зависимостями аргументов одних операторов от результатов других (примеры 1 и 2, 5 и 6, 7 и 8). Выигрываем мы на том, что согласно принципу Б мы не заводим без нужды новые величины, а стараемся обходиться уже имеющимися. Второй способ сохраняет состав команд и зависимости между результатами и аргументами, но % 1 Х НАКОПЛЕНИЕ ФАКГОВ, ЛИНЕЙНЫЕ ПРОГРАММЫ 22 разрешает перестраивать команды в программе, если это помогает делу (примеры 6 и 7). В природе экономии памяти в этом способе мы, скорее всего, еще не разобрались, не считая несколько расплывчатого утверждения, что если организовывать вычисления так, чтобы использовать резульеат по возможности сразу после получения, то можно сократить потребность в памяти для хранения значений.
Наконец, третий способ дает аффект благодаря полной перестройке программы, при этом, в общем случае, экономится память не для величин (з примере 3 мы даже ввели еще одну величину 2), а для программы, которая благодаря циклу становится более короткой. Первый способ, однако, з каком-то смысле является самым основным: каким бы способом мы ни получили программу, если мы хотим получить максимальную экономию памяти, мы должны проверить, не содержит ли она лишних величин, и постараться найти наилучший вариант (как в случае примера 8).
Наконец, мы должны отдавать себе отчет, что мы еще очень далеки от решения общей задачи экономии памяти. У нас в запасе есть только один принцип Б в качестве рабочего правила, а все наши примеры исчерпываются простейшим видом программ, так называемыми линейными программами, т. е. программами, не содержащими ни условных операторов, ни циклов, ни ссылок на процедуры вычисления функций (примеры 3 и 4 не в счет, так как мы их не анализировали). При атом дан<е для линейных программ принцип Б еще не носит характера формального правила и требует дальнейшей проработки, чем мы и займемся. Информационные связи н сечения.
Поразмышляем еще раз над принципом Б в попытках превратить его в систематическую процедуру: «не надо торопиться вводить для результата новое обозначение, а посмотреть, нет ли в данный момент освобождающейся величины, т. е. такой, текущее значение которой больше не потребуетсяы Эти слова подсказывают нам, что мы, решая задачу экономии памяти, должны просмотреть операторы программы в порядке их выполнения. Тогда (в случае линейной программы, ааписанной в столбик) выше очередного просматриваемого нами оператора будут операторы уже выполнившиеся, для которых мы уже как-то распорядились выбором величин, и ниже будут команды, еще не выполнизшиеся.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
