7.Советы по решению задач

1.1. Рекуррентное соотношение и алгоритм записываются так же, как в задаче «Вычисление суммы элементов массива».

1.2. Рекуррентное соотношение для суммы положительных элементов:

пусть – сумма первых i элементов массива. Тогда можно записать следующее рекуррентное соотношение:

, при .

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

1.3. Рекуррентное соотношение:

; при .

1.4. Рекуррентное соотношение аналогично задаче 1.3.

1.5. Очередное значение рекуррентной последовательности определяется по двум предыдущим. Поэтому необходимо использовать три переменные для хранения трех последовательных значений.

1.6. Очередное значение рекуррентной последовательности определяется по трем предыдущим. Поэтому необходимо использовать четыре переменные для хранения четырех последовательных значений.

1.7. Использовать схему Горнера, как в задаче «Вычисление числа по цифрам».

1.8. Использовать схему Горнера, как в задаче «Вычисление числа по цифрам».

1.9. Идея решения такая же, как в задаче «Вычисление приближенного значения функции».

, , поэтому .

1.9. Идея решения такая же, как в задаче «Вычисление приближенного значения функции».

, ,

поэтому .

1.11. Идея решения такая же, как в задаче «Вычисление приближенного значения функции».

, ,

поэтому .

1.12. Идея решения такая же, как в задаче «Вычисление приближенного значения функции».

, ,

поэтому .

1.12. Идея решения такая же, как в задаче «Вычисление приближенного значения функции».

, ,

поэтому .

1.13. Необходимо просто использовать приведенное рекуррентное соотношение.

1.14. Для записи алгоритма нужно использовать цикл while, поскольку заранее нельзя вычислить необходимое число итераций. Цикл должен выполняться, пока .

1.15. Цифры будут последовательно выделяться из исходного числа, начиная с самой младшей. Поэтому значение N будет меняться, и для него необходимо построить рекуррентное соотношение. (исходное значение), . i-я цифра, начиная с самой младшей, вычисляется по формуле для всех i, начиная от 0, пока значение .

1.16. Особое свойство элементов подпоследовательности – сохранение знака или чередование знаков. Поскольку нулевых значений нет, проверку можно провести по произведению соседних элементов: если A[i]*A[i+1]>0, то знаки одинаковые, в противном случае – разные.

1.17. Проверка числа на четность может быть выполнена с помощью операции mod – вычисление остатка от деления двух целых чисел. Если (A[i] mod 2)=0, то A[i] – четное, в противном случае – нечетное.

Для просмотра элементов, стоящих на четных (нечетных) местах, нужно организовать цикл с шагом 2. Цикл for этого не позволяет, следовательно, используется while.

1.18. Внутри подпоследовательности является истинным условие совпадения разностей между соседними парами элементов.

1.19. Ступенька – это подпоследовательность строго возрастающих значений (условие 1). Перед ступенькой находится значение, большее или равное A[i], или ступенька начинается с первого элемента (первая часть условия 2). После ступеньки находится значение, меньшее или равное A[j], или ступенька кончается в конце массива (вторая часть условия 2).

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

1.20. "Пилу" можно отыскать, продвигаясь по массиву с шагом 1 и проверяя выполнение условий 1 и 2 (условия связаны операцией OR) для каждой новой тройки элементов. Максимальный и минимальный элементы пилы – это больший из первых двух и, соответственно, меньший из двух последних элементов "пилы".

1.21. Решение такое же, как для 1.20.

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

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

Начальное значение для максимальной длины – 1, а для максимальной суммы – (минимальное значение в массиве – 1).

Структура алгоритма:

начальные значения;

for i:=1 to n-2 do begin {i – начало отыскиваемой подпоследовательности)

начальное значение очередной суммы;

for j:=i+1 to n-1 do begin {j – номер элемента, добавляемого к сумме}

добавить очередной элемент;

if получилась подпоследовательность

then записать в результаты;

end;

end;

1.23. Восходящая трасса – это то же, что ступенька в 1.19, но она формируется на основе одновременной проверки двух массивов с координатами точек. Информацию обо всех трассах (номер начального элемента и количество элементов или номер последнего элемента) нужно сохранять в массивах. Длина этих массивов (n div 2) – максимальное количество трасс получается, если каждая пара точек образует трассу. Если трассы не найдутся, то массивы могут остаться незаполненными.

1.24. Решение удобно разложить на 2 части: сначала поработать с нисходящими трассами, а потом – с восходящими. В остальном все делается так же, как в 1.23.

1.25. Каждый i-й элемент массива, кроме последнего, может быть первым в искомой группе. Перебирая значения k от 1 до n–1, нужно попытаться построить группу и затем сравнить ее длину с максимальной.

1.26. Любая прогрессия начинается с элемента A[1], а вторым в ней может быть любой элемент исходного массива. Разность этих значений – разность прогрессии.

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

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

1.27. Решение аналогично задаче 1.26.

1.28. Элементы исходного массива обладают особыми свойствами, которые нужно учесть при построении алгоритма. Следовательно, стандартный алгоритм упорядочивания не будет полностью правильным решением. Рекомендуется подсчитать по отдельности количество 0, 1 и 2, а затем заполнить массив полученным количеством разных значений.

1.29. Сначала решается задача поиска. Затем, если значение p найдено на месте i, то от i до конца массива организуется цикл, который работает, пока очередной элемент равен p. По разности между тем номером, где остановился цикл, и i вычисляется ответ.

1.30. Решается задача поиска значения, меньшего из пары (p, q). От того места в массиве, где нашлось это значение, снова производится поиск, но теперь уже большего значения из пары (p, q). Ответ – по разности мест, если нашлись оба значения.

1.31. Заметим, что заранее не известно, сколько элементов будет в результате. Их число лежит в интервале от 0 (все значения в исходном массиве разные) до половины длины исходного массива.

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

1.32. Строгая упорядоченность означает отсутствие совпадений между элементами.

Длина массива с результатом заранее не известна и, вообще говоря, может быть вычислена только после ввода исходного массива: (A[n]–A[1]+1)–n. Следовательно, описание массива с результатами не может быть сделано строго.

Решение основано на том, что в новый массив последовательно записываются числа из интервалов (A[1], A[2]), (A[2], A[3]) и т.д., для чего в программе организуются вложенные циклы. Заметим, что новый массив может остаться полностью незаполненным, если значения элементов A представляют собой арифметическую прогрессию с разностью 1.

1.33. Длина массива с результатом заранее не известна. Она находится в интервале от 1 (все элементы совпадают) до n1+n2 (все элементы разные).

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

1.34 Длина массива с результатом заранее не известна. Она находится в интервале от 0 (все значения совпадают) до n1 (ни один элемент из A не совпадает ни с одним из элементов B). Решение основано на задаче слияния.

1.35. Результат работы программы – массив из (m+1) счетчиков. Для каждого j-го элемента массива B путем последовательных сравнений отыскивается первый такой A[i], что B[j] < A[i]. Это означает, что B[j] попадает в интервал [A[i-1], A[i]). Следовательно, нужно добавить 1 в i-й счетчик. Такая нумерация счетчиков удобна, т.к., если B[j] < A[1], то считается, что этот элемент попал в 1-й интервал, а если B[j] >= A[m], то считается, что элемент попал в (m + 1)-й интервал.

1.36. Для того, чтобы освободить j-е место вставляемому (i+1)-му элементу, следует сдвинуть вправо на одну позицию элементы от j-го до i-го. Для этого удобно использовать цикл for с downto.

1.37. Подсчитать по отдельности количество 1, 2, 3 и т.д. в исходном массиве. В качестве счетчиков использовать элементы дополнительного массива длиной 100. Заполнить исходный массив полученным количеством разных значений.

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

1.39. Упорядочить массив и решать задачу о самой длинной подпоследовательности.

1.40. Косвенное упорядочение заключается в том, что после сравнения двух элементов массива меняются местами не они, а их номера, которые хранятся в дополнительном массиве. Перед упорядочением в дополнительный массив заносятся значения от 1 до n – исходные номера элементов по порядку. При обращении к элементам заданного массива в качестве индексов используются элементы дополнительного массива.

1.41. Задачу можно решить двумя способами:

1) в качестве повторяющегося фрагмента вывода выбираем уголок (1, 2, 3). Последний элемент выводится после общего цикла;

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

1.42. Решение удобно разбить на две части: сначала выводятся элементы верхнего треугольника, а затем в другом цикле – нижнего.

1.43. Массив нужно рассматривать как последовательность кругов, каждый из которых поворачивается на 90 градусов против часовой стрелки.

1.44. Удобно представить последовательность вывода как вывод "слоев" или "кругов" элементов. Например, внешний "слой" образуют элементы первого столбца (снизу вверх), первой строки (слева направо), последнего столбца (сверху вниз) и последней строки (справа налево). Всего в массиве – (n div 2)} "слоев".

1.45. Для представления результатов работы потребуется два линейных массива – для номеров строк и номеров столбцов. Максимальная длина этих массивов – n. Они могут остаться не заполненными, если в массиве, например, все элементы разные, или оказаться заполненными частично.

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

1.46. В двух дополнительных одномерных массивах отмечаются те строки и столбцы, в которых есть нулевые элементы. Затем производится обнуление.

1.47. Поскольку условие i – j = k связывает номер столбца с номером строки, то для каждой строки достаточно вычислить номер столбца и проверить, не выходит ли вычисленное значение за границы массива.

1.48. Заметим, что две пары строк (i, j)} и (j, i) дают один и тот же вариант решения. Это нужно учесть при организации циклов. При первом несовпадении внутри тройки строк следует закончить проверку и сменить номер одной из строк.

По условию задачи требуется найти какую-нибудь тройку строк. Условие можно усилить и найти все подходящие тройки строк.

1.49. Рекомендуется использовать дополнительный массив для хранения сумм элементов по строкам. Упорядочение проводится на основе этого массива. Можно применить косвенную сортировку, рассмотренную в задаче 1.40.

1.50. Результаты работы программы должны быть сохранены в двух массивах, максимальная длина которых – n (n – 1) / 2. С другой стороны, может оказаться, что не найдется ни одной подходящей пары.

Для решения задачи используется дополнительный массив– для максимальных или минимальных элементов строк. Условие i < j учитывается при организации циклов.

1.51. Решение аналогично задаче 1.50. Дополнительный массив используется для хранения сумм элементов строк или столбцов.

1.52. Упорядочить элементы массива по строкам. Попарное сравнение строк выполнять на основе алгоритма слияния.

1.53. Циклический сдвиг влево может быть заменен циклическим сдвигом вправо на вычисляемое число позиций. Если k >= n, то не нужно делать лишние сдвиги, при которых элементы возвращаются на те же места.

1.54. Упорядоченность исходного массива позволяет продвигаться в поисках разных значений одновременно по всем строкам, как бы широким фронтом. Для хранения координат этого фронта по каждой строке используется дополнительный целочисленный массив длиной n. Вначале все его элементы имеют значение 1. Значение m + 1 обозначает, что все элементы соответствующей строки просмотрены.

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

1.56. Решение основано на поиске заданных буквосочетаний и проверке, действительно ли они находятся в конце слов.

1.57. Задачу можно решить двумя способами.

1. Определять границы каждого слова в тексте и сравнивать слова с образцом.

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

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

1.59. Организовать цикл выделения слов из текста. Первые q символов каждого слова сравнить с образцом. В случае совпадения вывести все слово.

1.60. В символьной строке номер последней буквы вычисляется функцией length (строка). В последовательности вложенных циклов, каждый из которых указывает на номер одного из четырех слов, проверяются все возможные комбинации слов.

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

1.62. Сначала переписываются символы между строками, а затем строки из исходных S1, S2, S3 заносятся на новые места. В зависимости от соотношения длин строк символы между строками могут сдвигаться вправо (S2 > S1, S1 < S3) или влево. При сдвиге вправо переписывание производится от начала интервала, а при сдвиге влево – от конца.

1.63. Переписывание символов из T в Q продолжается до тех пор, пока не встретится корень S1. Поскольку приставки может и не быть, проверять начало слова не нужно. Удобно выделить конец слова (окончание) в отдельную строковую переменную и проверить, совпадает ли она с каким-нибудь элементом из массива окончаний. Если совпадение есть, то в Q записывается S2 и окончание, после чего просмотр массива T продолжается с первого разделителя за окончанием. Если совпадения окончаний нет, то переписывание продолжается со следующей буквы корня.

1.64. Текст удобно просматривать с конца. Если один из элементов массива E встретился в конце слова, то проверяется, не стоит ли один из корней перед этим окончанием. Если корень нашелся, то остаток слова от начала корня до первого разделителя слева можно перенести в дополнительную строковую переменную как искомую приставку. Если приставка есть (длина строки > 0), и она не совпадает с ранее найденными приставками, то ее нужно записать в массив P.

1.65. Упорядочить первую таблицу по фамилиям с помощью косвенной сортировки. Во второй таблице найти фамилию самого высокого ученика. Дихотомическим поиском найти эту фамилию в первой таблице и, таким образом, определить, в каком классе он учится.

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

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

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

1.69. Решение аналогично 1.68.

1.70. Задача решается на основе предварительного упорядочения: сначала по классам, затем внутри каждого класса – по фамилиям, а внутри каждой фамилии – по предметам. При использовании косвенной упорядоченности понадобится один дополнительный целочисленный массив.

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

1.72. В задаче идет речь об объединении информации из трех таблиц. Если исходные таблицы упорядочены по фамилиям, то можно применить алгоритм слияния.

1.73. Если исходные таблицы упорядочить:

информацию о жителях – по фамилиям,

о жителях-владельцах – по номерам автомобилей,

о нарушениях – по номерам автомобилей,

то результат можно сформировать на основе алгоритма слияния.

1.74. Упорядочение обеих исходных таблиц по фамилиям, а внутри одной фамилии – по категории, позволит применить алгоритм слияния.