Часть III. Программирование на VB – второй уровень

Если вам кажется, что вы уже все можете, то вы правы и неправы. Правы потому, что вы можете написать сколь угодно большую и сложную программу, разбив ее на разумное число процедур. Неправы потому, что ваша способность манипулировать данными разных типов еще очень ограничена. А без нее вам не поддадутся многие «умные» задачи. Например, не познакомившись с так называемыми массивами, вы не сможете запрограммировать игру в крестики-нолики или морской бой. Не освоив работу со строками, вы не сможете решить задачу о мало-мальски серьезной шифровке и дешифровке секретных сообщений. Не умея работать с файлами, вы не сможете сохраняться в созданных вами играх. Вам нужно освоить объектное программирование, познакомиться с базами данных, с работой в Интернете и с другими вещами.

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

Глава 15. Массивы, рекурсия, сортировка

Массивы– одно из главных средств хранения в памяти компьютера больших объемов информации.

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

Рекурсия – это вызов процедуры из тела самой процедуры. Она лежит в основе рекурсивного стиля программирования, очень интересного и плодотворного стиля для определенного круга задач.

Сортировка – это процесс упорядочивания элементов массива. Очень популярная и распространенная задача программирования.

Начнем с массивов.

Переменные с индексами

В основе массивов лежит понятие индекса. В математике широко применяются так называемые индексированные переменные. На бумаге они записываются так:

x₁ x₂ b₈ y_i y_i-6 z _{i j} z _{i+1 j}

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

X(1) X(2) B(8) Y(i) Y(i-6) Z(i,j) Z(i+1, j)

Числа Фибоначчи. Зачем математикам нужны индексированные переменные? Ну, их удобно применять хотя бы при операциях над числовыми рядами. Числовой ряд – это просто несколько чисел, выстроенных по порядку одно за другим. Чисел в ряду может быть много и даже бесконечно много.

Возьмем, например, бесконечный ряд чисел Фибоначчи:

1 1 2 3 5 8 13 21 34 .....

Попробуйте догадаться, по какому закону образуются эти числа. Если вы сами не догадались, то я подскажу: каждое из чисел, начиная с третьего, является суммой двух предыдущих. А теперь попробуем записать это утверждение с помощью языка математики. Для этого обозначим каждое из чисел Фибоначчи индексированной переменной таким образом:

Первое число Фибоначчи обозначим так: f(1),

Второе число Фибоначчи обозначим так: f(2)

и т.д.

Тогда можно записать, что

f(1)=1 f(2)=1 f(3)=2 f(4)=3 f(5)=5 f(6)=8 ......

Очевидно, что

f(3)=f(1)+f(2),

f(4)=f(2)+f(3),

f(5)=f(3)+f(4)

и т.д.

Как математически одной формулой записать тот факт, что каждое из чисел является суммой двух предыдущих? Математики в индексном виде записывают это так:

f(i)=f(i-2)+f(i-1).

Для пояснения этой формулы подставим вместо i любое число, например, 6. Тогда получится:

f(6)=f(6-2)+f(6-1)

или упрощая:

f(6)=f(4)+f(5),

что соответствует определению чисел Фибоначчи.

Какое бы i, большее 2, мы не подставляли, получается правильное равенство. Значит, формула верна сама по себе.

Задание 101.

Запишите на бумаге в индексном виде, как получается из предыдущего числа ряда последующее:

1) 14 18 22 26 .....

2) 6 12 24 48 ....

3) 3 5 9 17 33 65 ....

Еще примеры. Вот еще примеры, когда математики предпочитают использовать индексы. Пусть мы на протяжении года каждый день раз в сутки измеряли температуру за окном. Тогда вполне естественно обозначить через t(1) температуру первого дня года, t(2) – второго, ..... , t(365) – последнего. Пусть 35 спортсменов прыгали в высоту. Тогда через h(1) можно обозначить высоту, взятую первым прыгуном, h(2) – вторым и т.д.

Пока мы только немного привыкли к индексам, но никакой выгоды от них не получили. Выгода – в следующем разделе.

Одномерные массивы

Одна из типичных задач программирования формулируется примерно так. Имеется большое количество данных, например, тех же температур или высот. С этими данными компьютер должен что-нибудь сделать, например, вычислить среднегодовую температуру, количество морозных дней, максимальную взятую высоту и т.п. Раньше мы уже вычисляли подобные вещи, и при этом данные вводили в компьютер с клавиатуры одно за другим. При этом всегда получалось, что они вводятся в одну и ту же ячейку памяти (см. Глава 10. ). Однако, программистская практика показывает, что удобно, а часто и необходимо иметь данные в оперативной памяти сразу все, а не по очереди. Тогда для задачи, скажем, про температуру нам понадобится 365 ячеек. Эти 365 ячеек мы и назовем массивом. Итак, массивомможно назвать ряд ячеек памяти, отведенных для хранения значений индексированной переменной. На вопрос о том, как большое количество значений оказывается в памяти, отвечу, что обычно они вводятся из файла (19.2).