62
Искусство программирования
Стадартные приемы программирования
Урок 2. Линейный поиск
Задачи поиска является одним из наиболее распространенных: они возникют при построении трансляторов и во многих программах, больших и малых, с которых вам придается встречность. Если поиск ведется в файле, или если массив, в котором ищут, неупорядочен (то есть по значению элемента нельзя узнать, где он расположен), то единственный возможный вид поиск — это линейный поиск, при котором информация программирования от начала к конца, элемент за элементом. Далее массив упорядочен, но имеет малую длину, нет смысла применять что-либо сложнее, чем линейный поиск. Таким образом, все три подготовительные задачи*)
*) См. Урок 1, «Квант» № 10.
Решения
Во всех решениях: x — заданное значение, k — искомый индекс
a)
Задача 1 (первый подходящий)
i:=1; k:=0;
while (i<=n) AND (k=0) do
begin
if a[i]=x then k:=i;
i:=i+1
end;
б)
for k:=1 to n do
if a[k]=x then goto 7;
k:=0;
7:…
Задача 2 (последний подходящий)
k:=0;
for i:=1 to n do
if a[i]=x then k:=i;
задача 3 (m-й подходящий)
k:=0; i:=1; j:=0;
while (i<=n) AND (k=0) do
begin j:=j+1;
if j=m then k:=i
end;
i:=i+1
end;
j:=0;
for k:=1 to n do
if a[k]=x then
begin j:=j+1;
if j=m then goto 7;
end;
k:=0;
7:…
62
64
Рис. 1.
Рис. 2.
Рис. 3.
сначала разрезали по тем взамимо-перпенди-кулярным плоскостям, проходящим через его центр — получилось 8 кусков; затем сделали четвертый, косой разрез, который все эти куски, кроме «заднего», разделил на два — получилось 15 кусков, однако один из них (а именно центральный — самая складная часть мякоти передней «восьмушки») не имеет корки. От этого arbуза осталось 14 корок. Возможны и другие варианты разрезания.
Главный редактор — академик И. К. Кикоин
Первый заместитель главного редактора — академик А. Н. Колмогоров
Заместители главного редактора: М. Н. Данильчева, В. А. Лешковцев, Ю. П. Соловьев
Редакционная коллекция: Л. Г. Асламазов, М. И. Башмаков, В. Е. Белонучкин, В. Г. Болтянский, А. А. Боровой, Ю. М. Брук, В. В. Вавилов, Н. Б. Васильев, С. М. Воронин, В. В. Гнеденко, В. Л. Гутенхмер, Н. П. Долбилин, В. Н. Дубровский, А. Н. Земляков, А. Р. Зильберман, С. М. Козел, С. С. Кротов, Л. Д. Кудрявцев, А. А. Минайлов, Е. М. Никишин, С. П. Новиков, М. К. Потапов, В. Г. Разумовский, Н. А. Родина, Н. Х. Розов, А. П. Савин, Я. А. Смородинский, А. Б. Сосинский, В. М. Уроев, В. А. Фабрикант
Редакционный совет: А. М. Балдин, С. Т. Беляев, Б. Б. Буховцев, Е. П. Великихов, И. Я. Верченko, Б. В. Возdvijженский, Г. В. Дорофеев, Н. А. Erмолаева, А. П. Erшов, Ю. Б. Иванов, Л. В. Канторович, П. Л. Капица, В. А. Кириллин, Г. Л. Коткин, Р. Н. Кузьмин, А. А. Логунов, В. В. Можаев, В. А. Орлов, Н. А. Патрикеева, А. В. Перышкин, Р. З. Сагдеев, С. Л. Соболев, А. Л. Стасенко, И. К. Сурин, Е. Л. Сурков, Л. Д. Фаддеев, В. В. Фирсов, Г. Н. Яковлев.
Номер оформили:
Б. Галкин, Л. Денисенко, М. Дубах,
Н. Кузьмин, Э. Назаров, А. Пермин, Е. Тенчурина
Заведующая редакцией Л. Чернова
Художественный редактор Т. Макарова
Корректор М. Медведская
103006, Москва, К-6, ул. Горького, 32/1,
«Квант», тел. 251-82-42
Сдано в набор 17.9.82. Подписано в печать 3.11.82.
Печать офсетная
Бумага 70×108 1/16. Физ. печ. 4
Усл. печ. л. 5,60 Уч.-изд. л. 7,15 Т-20908
Цена 40 коп. Заказ 2378 Тираж 175 067 экз.
Орделена Трудового Красного Заменина
Чеховский полигraphический комбинат
ВО «Соизполгrafпром»
Государственное комитета СССР
по делам издательств, полигraphии
и книжной торговли
г. Чехов Московской области