Некоммерческая организация «Ассоциация московских вузов»

Государственное образовательное учреждение

высшего профессионального образования

Московский государственный индустриальный университет

ГОУ ВПО МГИУ

Научно-образовательный материал

«Задачи программирования на языке Java»

Состав научно-образовательного коллектива:

, ведущий инженер

Москва 2010 г.

Задачи программирования на языке Java

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

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

ЗАДАЧА.. Напишите рекурсивную программу, перемножающую два целых числа, одно из которых неотрицательно, без использования опе­рации умножения. Точные пред - и постусловия требуемой программы, временная сложность которой не должна превосходить в (log 6), таковы: Q = (а 6 2W Л Ъ 6 Ъм Л Ъ ^ 0), R = (z = а&). Числа а и 6 в программе изменять нельзя.

ЗАДАЧА.. Напишите программу, печатающую значение многочлена степени п^Ов заданной точке Xq. Коэффициенты многочлена хранятся в массиве а в порядке убывания степеней и являются целыми числами, также как и значение Xq. Величины п, Хо и элементы массива а изменять в программе нельзя.

НЕ нашли? Не то? Что вы ищете?

ЗАДАЧА. Напишите рекурсивную программу, печатающую значе­ние производной многочлена степени п ^ 0 в заданной точке Xq. Коэффи­циенты многочлена хранятся в массиве а в порядке убывания степеней и являются целыми числами, так же как и значение Xq. Величины п, Xq и элементы массива а изменять в программе нельзя.

УКАЗАНИЕ. Пусть Рп{х) = а^хп + а\Хп~1 + ... + ап-\Х + ап. Продиф­ференцируем по х равенство Рп(х) = х ■ Рп_\(х) + ап и подставим затем х = Xq. Мы получим следующие соотношения: РоЫ = о,

Р'п(х0) = х0 ■ Р^Ы + Рп-гЫ-Воспользовавшись ими и формулами

РоОо) = а<ь

Рп{Хо) — ж0 - Рп-1\%о) + ап>

легко определить рекурсивную функцию неотрицательного целого аргу­мента д: Ъм —> 2W х ^Mi #(^) = (Рп(хо), Рп(хо)) Для вычисления которой и пишется программа.

2. Проектирование цикла при помощи инварианта. При решении задач из этого раздела необходимо построить и доказать правильность построенной программы вида "SO;while(e)S;", а при отсутствии в усло­вии задачи явно заданных инварианта цикла и ограничивающей функции объяснить предварительно, каким образом они были получены.

ЗАДАЧА Напишите программу, перемножающую два целых числа, одно из которых неотрицательно, без использования операции умножения. Точные пред - и постусловия требуемой программы, временная сложность которой не должна превосходить в (log 6), таковы: Q = (а 6 Ъм 1\Ь 6 2W Л Ь ^ 0), R = (z = ab). При написании программы величины а и Ъ изменять не разрешается, следует использовать инвариант /= (у ^ 0 /\z + xy = ab) и ограничивающую функция h = у.

ЗАДАЧА Напишите программу, возводящую целое число в целую неотрицательную степень. Точные пред - и постусловия требуемой про­граммы таковы: Q = (а Е %м Л Ъ Е ^м Л а > О Л 6 ^ 0), Л = (z = ab). При написании программы величины а и 6 изменять не разрешается, сле­дует использовать инвариант /= (у ^ 0 Л z ■ ху = аь) и ограничивающую функцию h = у.

ЗАДАЧА. Напишите программу, находящую приближенное значе­ние квадратного корня а Е 2^ из заданного неотрицательного целого числа п. Вот более точная формулировка пред - и постусловия: Q = (n Е ZM Лп^О), Л= (аЕ ZM Л а ^ 0 Л а2 ^ п Л (а + I)2 > п). При написании программы величину п изменять нельзя.

ЗАДАЧА. Напишите программу (линейный поиск), определяющую первое вхождение заданного целого числа х в заданный массив Ь[0..т — 1] целых чисел (т > 0). Известно, что х находится в массиве Ъ. Значения элементов массива Ь и число х в программе изменять нельзя.

ЗАДАЧА. Напишите программу, находящую сумму s элементов заданного целочисленного массива Ь[0..п — 1], элементы которого и ве­личину п изменять нельзя. Точные пред - и постусловия: Q = (п > 0),

ЗАДАЧА. Напишите программу, находящую приближенное зна­чение квадратного корня а Е Ъ\^ из заданного неотрицательного це­лого числа п. Точные пред - и постусловия требуемой программы, вре­менная сложность которой не должна превосходить O(logn), таковы: Q = (п Е Ъм А п ^ 0), R = (а Е Ъм А а ^ 0 Л а2 < п А (а + I)2 > п). При написании программы величину п изменять нельзя.

ЗАДАЧА. Найдите минимальное число, содержащееся в каждом из трех упорядоченных по возрастанию массивов целых чисел, в предпо­ложении, что таковое существует.

ЗАДАЧА. Напишите программу, печатающую п-ое число Фибо­наччи (/о = 0, /i = 1, fk = /fc_i + /fc_2 для к > 1). При написании программы используйте Q = (п Е Ъм An > 0), R = (а = /п), I=(l^.i^.nAa = fiAb= fi-i), h = п — г. Число п в программе изменять нельзя.

ЗАДАЧА. Напишите программу, находящую частное q и остаток г от деления х на г/, не использующую операций умножения и деления. При написании программы положите Q = [х Е Ъм А у Е %м Ах*^0Ау>0),

R = (0 ^ г < у A qy + г = х), I = (0 ^ г АО < у A qy + г = х), h = г — у + 1. Величины х и у в программе изменять не разрешается.

ЗАДАЧА. Напишите программу, находящую наибольший общий делитель gcd(X, У) двух целых положительных чисел X и У, не использу­ющую операций умножения и деления и не изменяющую величин X и У. При написании программы положите Q = (X € ЪмАУ € ЪмАХ > 0AY > 0), Д = (ж = г/ = #cd(X, У)), I = (0 < ж Л 0 < г/ Л #сф, у) = gcd(X, У)), h = х + у — 2 ■ gcd(x, у).

УКАЗАНИЕ. Воспользуйтесь следующими свойствами наибольшего об­
щего делителя двух чисел не равных одновременно нулю (не забудьте на­
учиться доказывать все эти свойства):
gcd(x, у) = gcd(x, у - х) = gcd(x - у, у),
gcd(x, у) = gcd(x, у + х) = gcd(x + у, у),
gcd(x,x) = x, gcd(x,y) = gcd(y,x), gcd(x, 0) = gcd(0, x) = x.

ЗАДАЧА. Напишите программу, находящую приближенное зна­чение квадратного корня а 6 2^ из заданного неотрицательного це­лого числа п. Вот более точная формулировка пред - и постусловия: (Q = п е Ъм А п ^ 0), R = (а е Ъм А а ^ 0 Л а2 < п А (а + I)2 > п). При написании программы величину п изменять нельзя. Для построения инварианта удалите из постусловия конъюнктивный член а2 ^ п. Оце­ните временную сложность получившейся программы и сравните ее со сложностью программы, построенной в задаче 2.1.

ЗАДАЧА. Напишите программу, определяющую первое вхождение заданного целого числа х в заданный массив массивов Ь\0..т — 1][0..п — 1] целых чисел (га > 0,п > 0). Значения элементов массива Ь и числа ж, га и п в программе изменять нельзя. В момент завершения должно быть либо b[i][j] = ж, либо, если числа х в массиве нет, г = га. Точные пред-и постусловия требуемой программы таковы: Q = (га > 0 An > 0), R = ((0^г <mA0 ^j <пАх = b[i\[j}) V (г = га Л х <£ Ъ[0..т - 1][0..п - 1])).

УКАЗАНИЕ. Используйте инвариант, утверждающий, что х не нахо­дится в уже проверенных строках 6[0..г — 1] и среди уже проверенных элементов b[i][0..j — 1] текущей строки г. В качестве ограничивающей функции возьмите h = (га — г) • п — j + га — г.

ЗАДАЧА. Напишите программу (бинарный или двоичный поиск), определяющую для упорядоченного по неубыванию массива Ь[0..п — 1] целых чисел и заданного целого числа х позицию г, в которую может быть вставлено это число без нарушения упорядоченности массива. Точ­ные пред - и постусловия требуемой программы, временная сложность ко­торой не должна превосходить G(logn), таковы: Q = (х 6 1>м Л n Е

Ъм Л п > 0 Л (Vj 0 < j < п - 1: b[j] < b[j + 1])), R = ((г = -1 Л х < Ь[0]) V (0 ^ г < п - 1 Л Ь[г] < х < Ь[г + 1]) V (г = п Л Ь[п - 1] < х)). При написании программы величины х, п и элементы массива 6 изменять не разрешается, для построения инварианта используйте метод замены константы переменной.

ЗАДАЧА. Напишите программу, печатающую факториал введен­ного неотрицательного целого числа, изменять которое нельзя. Для по­строения инварианта используйте метод замены константы переменной.

ЗАДАЧА. Напишите программу, находящую наибольшее целое чи­сло, являющееся степенью двойки, не превосходящее заданного натураль­ного числа п 6 2W) изменять которое в программе нельзя.

УКАЗАНИЕ. Сначала выпишите формальную спецификацию програм­мы, а затем постройте инвариант с помощью метода устранения конъ­юнктивного члена.

ЗАДАЧА. Напишите программу, находящую сумму s элементов заданного целочисленного массива Ь[0..п — 1], элементы которого и ве­личину п изменять нельзя. Точные пред - и постусловия: Q = (п > 0),

( П~1 \ R = I s = 2_. Ъ[з\ ) • Инвариант постройте методом замены константы 0 в

V j=o / постусловии R новой переменной г.

ЗАДАЧА. Напишите программу, находящую приближенное зна­чение квадратного корня а Е Ъм из заданного неотрицательного це­лого числа п. Точные пред - и постусловия требуемой программы, вре­менная сложность которой не должна превосходить O(logn), таковы: Q = (п е Ъм Л п ^ 0), R = (а е Ъм Л а ^ 0 Л а2 < п Л (а + I)2 > п). При написании программы величину п изменять нельзя, а инвариант следует построить методом замены константы а на переменную Ъ в конъюнктив­ном члене а2 $С п постусловия R.

ЗАДАЧА. Напишите программу, находящую наименьшее значение х € Ъм в заданном массиве целых чисел Ь[0..п — 1], где п > 0. Значения элементов массива Ь и число п в программе изменять нельзя, Q = (n Е Ъм Л п > 0), R = ((Vj 0 < j < п х < b[j}) Л (ЗИ О < " = ВД)), инвариант постройте методом замены константы п на переменную г.

ЗАДАЧА. Напишите программу, находящую длину р ^ 1 самой длинной площадки в упорядоченном по неубыванию массиве Ь[0..п — 1] целых чисел. Площадкой мы называем последовательность нескольких равных значений. Значения элементов массива Ъ и число п > 0 в програм­ме изменять нельзя, Q = (п 6 2WЛп > 0A(Vj 0 ^ j < п — 1 b[j] ^ 6[j + l])),

R = (((ЗА; 0 < к < п - р Ъ[к] = Ъ[к + р - 1]) Л (Vj О < j < п - р + 1 b[j] ф b[j +р]))), инвариант постройте методом замены константы п на перемен­ную г.

ЗАДАЧА. Напишите программу, находящую число т ^ 1 пло­щадок в упорядоченном по неубыванию массиве Ь[0..п — 1] целых чисел. Площадкой мы называем последовательность нескольких равных значе­ний. Значения элементов массива Ь и число п > О в программе изменять нельзя.

УКАЗАНИЕ. Воспользуйтесь формулировкой предыдущей задачи.

ЗАДАЧА. Напишите программу, печатающую значение многочле­на степени п ^ 0 в заданной точке Xq. Коэффициенты многочлена хранят­ся в массиве а в порядке убывания степеней и являются целыми числами, так же как и значение Xq. Величины n, Xq и элементы массива а изме­нять в программе нельзя. Для построения инварианта используйте метод замены константы переменной.

3. Схема вычисления инвариантной функции. При решении задач из этого раздела необходимо указать множества X, Y и Хр, функцию F и преобразование Т (см. определение инвариантной функции). Должна быть объяснена программная реализация преобразования Т и доказана правильность построенной программы вида "SO;while(e)S;Sl;".

ЗАДАЧА. Напишите программу, находящую наибольший общий
делитель gcdix, у) двух целых неотрицательных чисел ж и «/, не равных
одновременно нулю. Воспользуйтесь следующими свойствами наибольше­
го общего делителя (не забудьте научиться доказывать все эти свойства):
gcd(x, у) = gcd(x, у - х) = gcd(x - у, у),
gcd(x, у) = gcd(x, у + х) = gcd(x + у, у),
gcd(x,x) = x, gcd(x,y) = gcd(y,x), gcd(x, 0) = gcd(0,x) = x.

ЗАДАЧА. Напишите программу, перемножающую два целых чи­сла, одно из которых неотрицательно, без использования операции умно­жения. Точные пред - и постусловия требуемой программы, временная сложность которой не должна превосходить в (log Ь), таковы: Q = (а 6 Ъм Л Ь € Ъм Л Ь ^ 0), Л1 = [z = ab). При написании программы вели­чины а и Ь изменять не разрешается. Воспользуйтесь тем, что функция F: Ъм х Ъм х ^м —^ ^м? F(x, y,z) = z + ху является инвариантной отно­сительно преобразования Т: Ъм х %м х Ъм -^ ^м х Ъм х Ъм-, задаваемого

J (2x,y/2,z), если у-четно,

формулой Г(ж, у, я) = <

I (ж, г/ — 1, £ + х), иначе.

ЗАДАЧА. Напишите программу, находящую наибольший общий делитель gcd(x, у) двух целых неотрицательных чисел ж и «/, не равных одновременно нулю. Воспользуйтесь следующим свойством наибольшего общего делителя (докажите его!):

jgcd(x%y,y), если х ^ у, gcd{x, у) = \

\дса{х, у/ох), иначе.

Здесь операция х%у позволяет найти остаток от деления х па, у.

ЗАДАЧА. Напишите программу, возводящую целое число в це­лую неотрицательную степень. Точные пред - и постусловия требуемой программы таковы: Q = (а 6 Ъм Л Ь 6 Ъм Л а > О Л 6 ^ 0), Rl = (z = ab). При написании программы величины а и Ь изменять не разрешается. Вос­пользуйтесь тем, что функция F: Ъм х ^м х ^м ~~^ ^м? ^(^, у, ^) = ££у является инвариантной относительно преобразования Т: Ъм х Ъм х ^м -> Ъм х ^м х ЪМ-, задаваемого формулой Т(х, y,z) = (х, у — 1, xz).

ЗАДАЧА. Напишите программу, находящую наибольший общий
делитель gcd(x, у) двух целых неотрицательных чисел х и г/, не равных
одновременно нулю. Программа должна иметь временную сложность по­
рядка 0(logmax(£, у)) и не использовать операций деления и нахождения
остатка от деления (допустимо деление пополам, реализуемое с помощью
операции сдвига). Воспользуйтесь следующими свойствами наибольшего
общего делителя (докажите их!):
gcd(2x, 2у) = 2gcd(x, у), gcd(2x, 2у + 1) = gcd(x, 2у + 1).

УКАЗАНИЕ. Воспользуйтесь инвариантностью функции F(x, г/, z) = z • gcd(x, у) относительно следующего преобразования Т:

' (х/2, у/2, 2z\ если оба числа х и у — четны,
(х/2, у, z), если х — четно, а у — нечетно,

T(x,y,z)= <

(х, у/2, z), если х — нечетно, а у — четно,

(х — г/, у, г), если х и у — нечетны и х ^ г/,

^(х, у — ж, z), если х и?/ — нечетны ж х < у. Не забудьте доказать Т-инвариантность функции F.

4. Задачи на индуктивные функции. При решении задач из этого раздела необходимо выяснить, является ли индуктивной заданная функ­ция /. В случае ее индуктивности следует предъявить отображение G, иначе нужно построить индуктивное расширение F исходной функции и предъявить G для него. В последнем случае нужно также указать отобра­жение 7Г и исследовать построенное расширение на минимальность (ми­нимальность не является обязательным условием). Завершить решение следует написанием программы, реализующей однопроходный алгоритм,

с указанием соответствия между программными переменными и обозна­чениями, использованными в теоретической части решения. Необходимо объяснить, как в программе реализуется вычисление / или F на пустой (или ее заменяющей) цепочке, как именно реализовано перевычисление функции при удлинении цепочки, и как находится ir(F(u)) в случае ис­пользования индуктивного расширения.

ЗАДАЧА. Напишите программу, определяющую значение в целой точке t многочлена, заданного последовательностью его целых коэффи­циентов (в порядке убывания степеней).

ЗАДАЧА. Напишите программу, вводящую последовательность целых чисел, и печатающую количество ее максимальных элементов.

ЗАДАЧА. Напишите программу, определяющую номер / первого элемента, равного Xq, в последовательности целых чисел. В том случае, если число Xq в последовательности не встречается, положите / равным нулю.

ЗАДАЧА. Напишите программу, вводящую последовательность вещественных чисел, и печатающую среднее арифметическое ее элемен­тов (для непустой последовательности).

ЗАДАЧА. Напишите программу, определяющую количество вхо­ждений образца abed в последовательность символов.

ЗАДАЧА. Напишите программу, определяющую количество мини­мальных элементов в последовательности неположительных целых чисел.

УКАЗАНИЕ. В данном случае для доопределения индуктивного рас­ширения на пустой цепочке нет необходимости использовать величины Integer. MIN. VALUE или Integer. МАХ_VALUE.

ЗАДАЧА. Напишите программу, определяющую дисперсию не пу­стой последовательности действительных чисел. Дисперсией d последо-

1 " вательности х\, Х2, ■ ■ •, хп называется величина — У (xi — га) , где га =

п *-^

i=i

[х\ +Х2 + • • . + хп)/п — среднее арифметическое элементов последователь­ности.

Указание. Так как d = - У^(ж* - га)2 = - У^(ж2 - 2тх{ +

1=1 i=i

1 / п п п \i/n п

,2

га ) = — I у xi — га у Xi — га У\хг ~ т) ) — — I 7 , х% ~ т / , хг

' ' i=l ) \г=1 i=l

Глава II. Построение программ


1 п 1 / п \ z п п

— У^ Xi------- ( 2_, Хг\ э ТО ВВОДЯ Обозначения Sq = У, 1 = п, Si = У.

2

II II

п '—' nz

г=1

п

S2 = У.%1-, получим d = s^/sq — (si/so)2. Легко проверить, что функция

г=1

F = (s2, 5i, So) является индуктивной.

ЗАДАЧА. Напишите программу, определяющую значение в целой точке t многочлена, заданного последовательностью его целых коэффи­циентов (в порядке возрастания степеней).

ЗАДАЧА 8. Напишите программу, определяющую значение в целой точке t производной многочлена, заданного последовательностью его це­лых коэффициентов (в порядке убывания степеней).

УКАЗАНИЕ. Продифференцировав по х равенство Рп(х) = x-Pn-i(x)-\-ап и подставив затем х = t, получите соотношения Pq(£) = 0 и P'n{t) = t • P'n-i(t) + Pn-i(t), которые помогут построить индуктивное расширение исходной функции.

ЗАДАЧА. Напишите программу, определяющую значение в целой точке t производной многочлена, заданного последовательностью его це­лых коэффициентов (в порядке возрастания степеней).

ЗАДАЧА. Напишите программу, определяющую значение в целой точке t второй производной многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).

ЗАДАЧА. Напишите программу, определяющую правильность формулы над алфавитом из четырех символов X = {(,),£,+}. Формула считается правильной, если она может быть получена с помощью следу­ющей НФБН: е ->• t | (е + е).

УКАЗАНИЕ. Рассмотрите следующее индуктивное расширение F = (/ь/2,/з) Функции /, где h: X* -► {T, F}, /2: X* -► ZM, /3: X* -+ X, определены следующим образом:

/i (^) — ^ может быть продолжена до правильной формулы, /г(^) — разность числа левых и правых скобок в со, /з(^) = последний элемент ал

ЗАДАЧА. Напишите программу, определяющую номер / послед­него элемента, равного Xq, в последовательности целых чисел. В том слу­чае, если число Xq в последовательности не встречается, положите / = 0.

ЗАДАЧА. Напишите программу, определяющую число локальных максимумов последовательности целых чисел. Элемент называется ло­кальным максимумом, если у него нет соседа большего, чем он сам. На­пример, в любой одноэлементной последовательности всегда ровно один локальный максимум.

ЗАДАЧА. Напишите программу, определяющую среднюю длину связной возрастающей подпоследовательности в последовательности це­лых чисел.

ЗАДАЧА. Напишите программу (быстрое возведение в степень), возводящую целое число а в целую неотрицательную степень 6, временная сложность которой не должна превосходить О (log 6).

УКАЗАНИЕ. Рассмотрите эту функцию /, как функцию на простран­стве последовательностей над алфавитом {0,1}. В качестве последова­тельности и нужно взять инвертированное представление числа Ь в дво­ичной системе счисления. Данная последовательность получается есте­ственным образом — последняя цифра числа Ъ есть "Ь&1", предпоследняя получается по той же формуле после сдвига вправо ("Ь>>>=1;") и так далее. Индуктивное расширение F исходной функции / легко находится, что и позволяет написать требуемую программу.

ЗАДАЧА. Напишите программу, определяющую количество вхо­ждений образца аЪаЬ в последовательность символов.

ЗАДАЧА. Напишите программу, определяющую значение в целой точке t fc-ой производной многочлена, заданного последовательностью его целых коэффициентов (в порядке убывания степеней).