Решаем задачи

Итак, сегодня мы будем решать задачи. При этом главное внимание будет уделяться не разбору исходных текстов, а реализации методов и решений, посредством которых вы сами сможете подойти к непосредственному написанию поставленной задачи.

Я имею в виду, что постараюсь показать вам на наглядных примерах ход рассуждения, который в первую очередь необходим при выполнении программы. Что нужно сделать и понять, чтобы составить необходимый алгоритм, да и как составить сам алгоритм. Как вы сможете заметить по ходу выпуска, программы уже не столь элементарные, как были в предыдущих практических выпусках. Возможно, вам придется подумать - а может вы решите все очень просто.

Теперь про то, как надо решать задачи. Для начала нужно ознакомиться с условием, быть уверенным, что вы его поняли. После задуматься - а что нужно для реализации этой задачи? Какие для этого необходимы средства? Часто подходит использование массивов. Бывает - они и не нужны вовсе. Возможно - массивы предопределяются сразу в программе, делая ее максимально универсальной. Все это смотрите ниже.

Задачи подобраны так, чтобы охватить как можно больше информации.


Задача №1

Звездное небо

(аналог экранной заставки Norton Commander)

Задача: На экране в случайных точках появляются звезды, и в обратном порядке гаснут.

Итак, задание есть. Теперь давайте подумаем, каким образом будем выполнять нашу программу и что для этого понадобиться. В первую очередь обратим внимание на самые главные вещи. Что у нас главное? Точки. Ведь именно они и будут основным объектом работы программы, не так ли? Значит из этого и будем исходить: как нам реализовать появление точек на экране. Продолжаем.

Вы уже знаете, что экран в ДОС разбит на строки и столбцы, причем все они имеют номера. Переход к требуемым координатам экрана осуществляется процедурой GotoXY из модуля Crt. Отсюда ясно, что каждая точка будет иметь две координаты, которые будет получать случайным образом. Но точка у нас будет не одна, а скажем, 20. Вот и получается, что:

20 точек * 2 координаты = 40 переменных

40 переменных не так уж и мало для раздела var, верно? Кроме того, это очень неудобно. Допустим, вы захотели изменить количество точек с 20-ти на 15. Придется стирать лишние переменные. Захотели увеличить с 15-ти до 30-ти: дописывать недостающие.

Вот здесь мы и подходим к необходимости использования массивов. Подумайте, не легче ли будет завести массив, каждый элемент которого - это координата точки? Определенно легче и удобней. Теперь описание двадцати переменных сведется к следующему:

var

X: Array[1..20] of Byte;

Y: Array[1..20] of Byte;

Как вы видите, массивов два. Один - для хранения номера столбца (X), другой - строки (Y). В обоих массивах используется тип Byte, так как он самый подходящий для хранения координат экрана в текстовом режиме (80х25).

Но на этом подготовка к написанию программы не заканчивается и мы идем дальше. Давайте теперь задумаемся над тем, как же нам быстро изменять количество точек? Массивы заведены, как вы видите на 20 элементов. Кроме того, в самой программе придется обрабатывать эти массивы в цикле, который мы тоже будем делать до 20. Как же можно сделать так, чтобы и размер массивов и диапазон цикла изменялись всего лишь одним числом? Это вечная проблема оптимизации, у которой, к счастью, есть решение. Помните, я показывал предопределение переменных прямо в разделе const? Этим мы и воспользуемся. Модифицируем приведенный пример:

const

n = 20;

var

X: Array[1..n] of Byte;

Y: Array[1..n] of Byte;

Теперь изменение размера обоих массивов - это всего лишь редактирование значения единственной переменной. Но это не все достоинства данного метода. Вышеупомянутые циклы, которые будут проходить по массивам, тоже становяться максимально оптимизированными. Вот пример:

const

n = 20;

....

For I := 1 to n do

....

Посмотрите внимательно. Видите, при изменении значения одной переменной меняется обработка данных всей программы? Это важно. Я специально подробно останавился на этом, чтобы вы поняли до конца принцип оптимизации программы. Очень часто и очень многие недооценивают это. Не забывайте предопределять такие вещи :)

Двигаясь дальше замечаем, что все необходимое для управления точками на экране у нас есть. Теперь остаются такие незначительные данные как переменные для циклов и т.п., их все вы определяйте по ходу написания программы. Можно разбираться, как писать саму программу.

Начнем. Перечислю необходимые задачи для написания программы:

  • Решить, как будут изображатсья звезды;

  • Разобраться, каким образом будет производиться вывод их в соотв. координаты;

  • Составить основной цикл программы;

Здесь я немного собьюсь с плана и оговорюсь о последнем пункте. Основной цикл программы - это ее работа до возникновения определенных условий. Здесь подумайте и сделайте такой цикл, чтобы все действия заключались внутри него, а само условие цилка контролировало действия пользователя на выход (или что там еще придумаете). Решайте сами, какой цикл вам лучше взять.

Ну а теперь по порядку. В первую очередь будем разбираться с самим изображением звезд. Давайте опрелимся, какими символами они будут изображаться и как они будут исчезать. У нас зведочки будут максимально приближены к Norton'овским, т.е. будут расти из точки до звезды, после чего гаснуть. Будет происходить это так:

  • Сначала выводиться точка - '.'

  • После выводиться звездочка - '*'

  • И напоследок выводиться большая здезда - (к сожалению, в Windows (в частности, в HTML документе) нельзя отобразить таковую).

  • Теперь она будет исчезать - будет выводиться пробел, которым затреться изображение звезды.

"" таким образом у нас получиться анимация.

С первыми двумя, равно как и с исчезанием - все ясно. Выводим символы процедурой Write и все дела. Но как вывести большую звезду? Дело в том, что с этим символом вы, возможно, и не знакомы. Чтобы понять, про что я говорю, откройте документ в Turbo Pascal (под DOS) и напечатайте что-нибудь (просто внесите в него изменения). Теперь посмотрите в левый нижний угол экрана, где указана пара чисел СТРОКА:СИМВОЛ. Видите, перед ней стоит звездочка, которая означает, что файл был изменен? Она не является той, которая расположена на клавиатуре на цифре "8" и на доп. разделе под огоньками "NumLock" и т.п. Она несколько больше, причем отсутсвует на клавиатуре, но существует во внутреннем наборе символов операционной системы.

Я не хочу сейчас рассказывать про само понятие набора символов (и связанные с этим темы - кодировки ANSI, ASCII и т.п.) - это немного не к месту, лучше я посвящу им отдельную статью. Пока скажу только, что помимо символов клавиатуры есть еще и другие, которые нельзя набрать, но можно вывести на экран с помощью программы. Это, к примеру, символы рамки, из которой составлено тоже окно редактора TP, Norton Commander и т.д, наш с вами символ звезды и многие другие.

Все они имеют порядковый номер, по которому и осуществляется их вывод. К примеру, столь необходимый нам символ большой звезды имеет номер 15. Чтобы получить символ с требующимся номером, служит фукнция:

Chr(Num: Byte): Char;

В качестве ее параметра задается сам номер символа, а от своей работы она возвращает этот символ, причем типа Char, которого она и является. Вот пока и все, что вам нужно знать, чтобы суметь напечатать звезду:

Write(Chr(15));

Как видите, я использую Chr прямо в процедуре Write. Помните, это функция, которая возвращает от своей работы определенное значение. А мы можем его использовать так, как нам захочеться, в том числе и выводить на экран.

Итак, задача отображения звезд тоже решена. Теперь надо заняться вопросом вывода этих здезд в определенное место экрана, координаты которого задаются нашими массивами. Здесь много вариантов! Однако я останавливаюсь... Вот это и есть задача для вас! Я довольно много рассказал, провел через непонятные или неочевидные вещи, ну а решать саму задачу советую самостоятельно. Это совсем несложно.

Когда вы ее сделаете (или не сделаете :) - можете посмотреть готовый вариант на сайте рассылки (http://prog.agava.ru), как я уже говорил, в новом разделе Уроки для начинающих программистов >> Исходные тексты.

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


Задача №2

Сортировка массива

Задача:

Существует массив. Отсортировать его по возрастанию.

Эта, на первый взгляд простая задача под силу далеко не всем, даже не совсем новичкам. Дело в том, что если вы не знакомы с существующим алгоритмом для решения этой задачи, то определенно вам понадобиться значительно время, чтобы сообразить, как же ее решать. Алгоритм (надо отметить, что он не один) на самом деле очень простой и понятный, но, как я уже сказал, его нужно знать. И рассказать о нем в рассылке надо было в обязательном порядке, что я сегодня и делаю.

Итак, будем сортировать массив, то есть переставим в нем элементы так, чтобы они стояли по возрастанию. Используем известный (возможно, пока не вам) - алгоритм "Пузырька".

Определимся, что нам потребуется. Естественно, сам массив - один и только один, дополнительных массивов никаких не будет, только простые переменные. Заведем массив, скажем, на 30 элементов. Заполнять его будем, конечно, не с клавиатруры (вводить 30 элементов вручную довольно бесполезное занятие), а выполним это с помощью известной нам функции Random. Что дальше? А дальше и начнем нашу сортировку.

Для начала немного подготовим себя и попробуем реализовать операцию перестановки двух элементов массива местами. Это довольно просто и выполняется двумя способами:

  1. С помощью 3-ей переменной:

    var
    A: Array[1..10] of Byte;
    B: Byte;
    begin
    .....
    { Перестановка 1-го и 2-го элементов }
    B := A[1];
    A[1] := A[2];
    A[2] := B;
    { Вот и поменяли местами }
    .....
    end.

  2. С помощью арифметических действий:

    var
    A: Array[1..10] of Byte;
    begin
    .....
    { Перестановка 1-го и 2-го элементов }
    A[1] := A[1] + A[2];
    A[2] := A[1] - A[2];
    A[1] := A[1] - A[2];
    { Вот и поменяли местами }
    .....
    end.

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

Итак, разобрались на примерах, как переставить местами две переменные. Теперь двигаемся дальше и начнем реализовывать сам алгоритм. При этом я, безусловно, могу привести исходный текст в рассылке, но это будет, на мой взгляд, несколько преждевременно. Лучше я постараюсь подвести вас к самостоятельной реализации этого алгоритма - это позволит гораздо лучше понять его работу, да и позволит попрактиковаться. Конечный вариант вы, как всегда, можете посмотреть на сайте рассылки в разделе "Уроки для начинающих программистов >> Исходные тексты".

Итак, начнем.

Сортировка массива по возрастанию (или по убыванию - без разницы) методом пузырька осуществляется по следующему принципу, который разделим условно на два этапа (следите за ходом моих мыслей):

Первое:

  • Необходимо сделать цикл, на единицу меньше, чем размер массива.

  • В этом цикле организовать еще один, такой же.

Организовав такую структуру, вы получите два вложенных цикла, которые пробегут по массиву след. количество раз (n - размер массива):

(n-1) * (n-1)

Второе:

  • Во втором, внутреннем цикле необходимо выполнить проверку:

  1. Если текущий элемент больше, чем следующий, то переставить их местами.

Все :))

Теперь подробнее. Во-первых, если вы будете делать проверку на больше, то сортировка будет производиться по возрастанию. Если на меньше, то по убыванию. Во-вторых, в первом этапе мы создаем два вложенных цикла, диапазоном на единицу меньше, чем размер массива. Для чего? Это налицо во втором этапе нашего алгоритма. Внутри цикла мы сравниваем текущий элемент со следующим. Фактически, выходит такая проверка (j - индекс цикла): If A[j] > A[j+1] ... Как видите, если у нас массив до 10-ти, и J будет идти до 10-ти, то в последней итерации получится: If A[10] > A[11] ..., что будет ошибкой.

Да... Программа получается очень простой и маленькой, но говорить о ней можно много. Думаю, на этом хватит - вы без труда сами составите алгоритм "Пузырька". Конечный работоспособный вариант сморите на http://prog.agava.ru.


Задача №3

Обработка строк

Задача:

С клавиатуры вводится слово. Нужно на весь экран распространить это слово так, чтобы на 2-ой строке первая буква перескочила в конец. И т.д. Пример:

интернет

нтернети

тернетин

........ и т. д. .............

Итак, будем переставлять буквы. Сразу же определимся, где будет храниться введенная строка. Для этого нам подойдет тип String. План действий:

  • Введем переменную типа String с клавиатуры;

  • Будем переставлять буквы соответсвующим образом;

  • Сразу же будем выводить ее на экран;

Как видите, задач для написания этой программы не так уж и много. Но при их выполнении могут возникать еще и другие, не столь очевидные проблемы. Но все они, ествественно, решаемы - так что давайте двигаться дальше и разбираться, как будем осуществлять поставленные задачи.

1. Введите строку с клавиатуры. Ну, с этим, думаю, проблем не возникнет.

2. Будем переставлять буквы.

3. Выводить на экран.

Эти две задачи будут выполняться совместно, внутри цикла, который здесь просто необходим. Для начала давайте вспомним, что работать со строкой можно как и с массивом, то есть обращаться к каждому элементу в отдельности (см. пред. выпуски).

Теперь наглядно представим, как будет меняться наша строка по ходу перестановки элементов:

  1. Исходная строка:

    и н т е р н е т

  2. 2-й вариант:

    н т е р н е т и

  3. 3-й вариант:

    т е р н е т и н

  4. 4-й вариант:

    е р н е т и н т

  5. 5-й вариант:

    р н е т и н т е

  6. 6-й вариант:

    н е т и н т е р

  7. 7-й вариант:

    е т и н т е р н

  8. 8-й вариант:

    т и н т е р н е

  9. 9-й вариант:

    и н т е р н е т

Вот так и будет печататься и изменяться строка. Как вы видите, с каждым новым разом очередной символ переноситься в конец строки, после чего строка дополняется одним пробелом.

Собственно, это и все, в чем надо было разобраться для решения задачи. Осталось найти зависимость действий и составить алгоритм. Он будет следующего содержания:

1. Организуем цикл от 1-цы до Lenght(String); (см. пред. выпуски)

  • Добавлем к строке элемент, который соответсвует текущему элементу цикла: S := S + S[i];

  • Дополняем строку пробелами вначало: S := S + ' ';

  • Выводим строку на экран;

Это все. Теперь вам необходимо самостоятельно написать программу по приведенному алгоритму. Поверьте, вы сразу поймете, что все даже проще, чем кажется. Конечный вариант на сайте.


Задача №4

Титры фильма

Задача:

Написать программу "титры фильма". Нужно, чтобы строчка выезжала сбоку экрана до середины, затем уходила вниз. Затем следующая выезжала.... После вывода всех строк цикл повторяется после некоторой паузы.

Перед тем, как начать пистать программу, как всегда давайте определимся, что же нужно для ее реализации. Здесь очевидно, что будет использоваться несколько строк, которые поочередно будут обрабатываться. Содержать эти строки удобно будет в массиве, с элементами которого мы и будем работать. Реализовать такой массив совсем несложно. Можно так:

var
A: Array[1..10] of String;
begin
A[1] := 'Одна из строк массива';
A[2] := 'Очередная строка массива';
............
A[10] := 'Очередная строка массива';
end.

А можно и так:

Const
A: Array[1..10] of String =
('Одна из строк массива',
'Очередная строка массива',
............
'Очередная строка массива');
begin
.......
end.

Это знакомый нам вариант с предопределением переменных.

После того, как мы создали такой массив, весь рабочий материал для программы готов и можно думать о алгоритме. Начнем с того, что разберемся с самим движением строк.

Представьте себе строку, движущуюся по экрану - сначала горизонтально к центру, а потом падающую вниз. Что это? Это пример самой, что ни на есть анимации. Реализовываться она путем вывода строки с последующим ее затиранием. Похожий пример мы разбирали в задаче N1, где выводились здезды с последующим затиранием их пробелом.

Итак, мы нужно выводить строки и после их затирать. Это несложно, как мне кажестся. Дальше нужно разобраться с самим движением, а точнее со способом передвижения строки по экрану. Из предыдущих задач известно, что для отображения строки в определенном месте экрана надо перевести курсор в место с необходимыми координатами, после чего уже вывести строку. Координаты нужно изменять в двух циклах - сначала будем двигаться горизонтально от края к центру, после вниз до конца. И опять, по новой - но уже с другим элементом массива, то есть с другой строкой.

Циклы предстоит реализовать вам :) равно как и необходимые действия по анимации. Я же расскажу, как состаить общий план алгоритма работы, которого вам предстоит придерживаться.

Итак, программа будет работать следующим образом:

  • Пока пользователь не захочет выйти (не нажата клавиша Esc и т.п.) делаем:

    • Увеличиваем индекс строки (новая строка массива)

      1. Выводим текущую строку в ее координаты (горизонтально);

      2. Выполняем необходимые действия по анимации;

      3. Изменяем координаты;

      4. Выводим текущую строку в ее координаты (вертикально);

      5. Выполняем необходимые действия по анимации;

      6. Изменяем координаты;

Вот такие вот действия. Все достаточно просто, однако вам уже предстоит выполнить больше действий, чем в прошлых программах. Но они очень простые, так что думаю, что сложностей не возникнет. Посмотреть, как работает предложенный нами вариант программы можно как всегда на сайте http://prog.agava.ru.


Домашнее задание

Предлагаю вашему вниманию несколько задач для самостоятельного рассмотрения. Очень рекомендую попробовать решить их, используя приведенные мной примеры составления решений и алгоритмов. Поседите с бумагой и ручкой, возможно что-то и не будет получаться с первого раза - не беда, дальше обязательно выйдет. Главное - помните, при хорошем рассмотрении и разложении по полочкам любая из этих задач вам по силам.

Итак, задачи:

1 Написать программу, чтобы слово съезжалось с боков экрана по буквам
2 Написать программу, к-ая переворачивает вводимое слово задом наперед.
3 Написать программу-меню. Выбор какого-либо пункт осуществляется по вводу его номера с клавуатуры. При этом должны писаться разные сообщения.
4 Написать программу "строки состояния". Строка экрана постепенно заполняется минусами "-". Строка останавливается каждый раз в разном месте. В следующей строчке выводится процент заполнения. Вариант: строка до конца, процент заполнения выводится динамически.
5 Написать программу-калькулятор (Мы также вместе замемся этим в дальнешем, я предложу свой вариант калькулятора)
6 Написать программу "ввода пароля". Запрашивается пароль, очищается экран, затем дается три попытки его ввести.

Решения всех задач будут к следующему выпуску выложены на сайте рассылки. Кроме того, сегодня я уже поместил туда несколько дополнительных задач, которые, возможно, будут вам полезны при выполнении ДЗ. В любом случае, они содержат новые алгоритмы и приемы программирования, так что советую посмотреть и поразбираться самостоятельно.

Занимайтесь, ибо это и есть двигатель на пути к успеху!


Вопросы- ответы

Вопрос 1.

Программа подсчитывает дискриминант! В конце запрос: "Вы хотите еще найти дискриминант? y/n" Как сделать чтобы при нажатии на "y" программа начаналась сначала, а при нажатии на "n" выходила?

uses crt;{подключаем библиотеку}

var

c:char;

...................{другие переменные}

begin

repeat

................... {считаем то, что нужно}

writeln('Хотите еще y/n');

c:=readkey; {ожидаем нажатия клавиши}

until(c='n')or(c='N'); {если буква N - прекращаем работу}

end.

Вопрос 3. Что можно использовать вместо программы Turbo Pascal 7.0 для изучения программирования? Так как эта программа работает под DOS, то очень не удобно одновременно читать Ваши уроки в Windows и делать упражнения в DOS.

Первое, что приходит в голову, это Borland Pascal for Windows (BPW). Он входит в стандартную поставку BP 7.0 (напомню, что в эту же стандартную поставку еще входят TP 7.0. и BP 7.0). При помощи BPW вы можете делать тоже, что и в ДОСе, во время выполнения программы вместо окна ДОСа открывается обычное окно Виндовс, а все остальное то же самое. Это если вы хотите иметь в windows Паскале то же, что и в ДОСе.

Если же вы хотите создать для своей программы красивый и удобный Виндовс интерфейс, то добро пожаловать в Дельфи и объектно-ориентированное программирование, однако, это несколько другая и более сложная песня.

Существуют и другие Паскали, правда я никогда с ними не имел дела, но слышал и читал много хорошего. Virtual Pascal 2.0. знающие люди очень хвалят (работает по Виндовс), поищите в сети. Free Pascal (http://www.ru.freepascal.org) (говорят, не хуже).

Вопрос 4. У меня вот такой вопрос- как в программе описать массив X, если заранее неизвестна его размерность (т.е. кол- во элементов, как я понимаю) ?

Два варианта:

  • Объявить массив заведомо большего размера и работать только с нужными элементами. Кушает много памяти, да и вообще ее может нехватить (сегмент статич. данных в Пасе только 64К).

  • Поможет динамическая память:

=============Начало программы===========================
{$R-}
type
mass=array[1..1]of integer {массив нужного типа}
Parr=^mass;
var
D:Parr;
i,n:integer;
begin
randomize;
write('Введите размер массива ');
readln(n);
GetMem(D,n*sizeOf(integer)); {выделяем память под массив}
for i:=1 to n do {запоняем случайными числами и}
begin {печатаем}
D^[i]:=random(100);
write(D^[i],' ');
end;
FreeMem(D,n*sizeOf(integer)); {освобождаем память}
end.

Вопрос 5. Как можно запустить программу?

Если имеется в виду запустить внешнюю программу из своей, то с помощью процедуры Exec из модуля DOS:

{$M 4096,0,10000}
uses Dos;
.......
.......
begin
............
............
SwapVectors;
Exec(Путь&ИмяВашейПрограммы, Доп_Параметры);
SwapVectors;
.....................
.....................
end.

Вопрос 6. а). Я пользуюсь программой Borland Pascal 7.0. При подключении дополнительных модулей (crt, graph) после запуска программы Pascal выдает сообщение: "Error 200: Division by zero" - деление на ноль. После запуска утилиты CPU Grabber, замедляющей работу процессора примерно на 60 %, программа выполняется нормально. Как можно исправить положение? Заранее спасибо.

б). При попытке в паскале использовать функцию очистки экрана, возникает сообщение "Error 200:Division by zero", а в пользовательском окне (ALT-F5) сообщение runtime error 200 at 0014:0091, что такое?

Эти два вопроса - одно и тоже.

В связи с кривизной модуля CRT на быстрых машинах типа iPentium II/III, iCeleron программы откомпиленные на BP7/TP7 при запуске вылетают с run-time error 200 - деление на ноль. Причём ошибка эта появляется при подключение модуля даже если вы и не вызывали процедуру Delay, которая там криво написана.

Суть проблемы состоит в том, что в этом модуле время измерялась через производительность процессора - в то давнее древнее время, как сами понимаете, не было столь быстрых процессоров и не было этой ошибки. Для того, чтобы ваши программы не вылетали вам нужно установить пропатченный вариант CRT, который Вы сможете скачать с сайта Библиотека программиста - http://prog.agava.ru

Вопрос 7. При запуске Паскаля всё время появляется старая программа и приходится закрывать окно с этим текстом и открывать свежее. Как от этого избавится?

После того, как вы открыли "свежее", сделайти следующие действия: F10-Options-Save. Теперь каждый раз при запуске у вас бедет открываться новое окно.

Вопрос 8. В рассылке N11 Вы рассказывали про форматный вывод .Чтобы реализовать это, мы приписывали к переменной, стоящей в процедуре два числа, разделив их двоеточием: Write('Real: ', A:5:2);

После запятой цифры реагируют на команду, а вот до запятой совершенно не реагирует.

А теперь попробуйте:

var
a:array[1..10]of real;
................
begin
...............
for i:=1 to 10 do write(a[i]);
writeln;
for i:=1 to 10 do write(a[i]:10:4);
writeln;
for i:=1 to 10 do write(a[i]:5:4);
...............................
end.

И почувствуйте разницу.



Опубликовал admin
16 Ноя, Воскресенье 2003г.



Программирование для чайников.