Семакин И.Г., Шестаков А.П. Основы программирования

Подождите немного. Документ загружается.

24.

Текстовый файл содержит запись многочлена некоторой сте-

пени с одной переменной

х,

коэффициенты многочлена

—

целые.

Например, 5х

4-Зх

3 +

15х

2-4. Указать степень многочлена,

его коэффициенты. Дописать в указанный файл таблицу значений

этого многочлена на данном отрезке [а, Ь].

25.

Дан файл, содержащий текст на русском языке. Подсчи-

тать количество слов, начинающихся и заканчивающихся на одну

и ту же букву.

6.14. Задачи по теме «Модули»

I. Реализовать в виде модуля набор подпрограмм для выполне-

ния следующих операций над комплексными числами:

1) сложения;

2) вычитания;

3) умножения;

4) деления;

5) модуля комплексного числа;

6) возведения комплексного числа в степень п (п

—

натураль-

ное).

Комплексное число представить следующим типом:

Type Complex=Record

Real;

М: Real

End;

Используя этот модуль, решить следующие задачи.

Дан массив А

—

массив комплексных чисел. Получить мас-

сив С, элементами которого будут модули сумм рядом стоящих

комплексных чисел.

Дан

массив А[М] —

массив комплексных

чисел.

Получить мат-

рицу B[N, M], каждая строка которой получается возведением в

степень, равную номеру этой строки, данного массива А.

II.

Реализовать

в виде

модуля набор подпрограмм

для

выполнения

следующих операций над обыкновенными дробями вида ^ (Р

—

целое, Q — натуральное):

1) сложения;

2) вычитания;

3) умножения;

4) деления;

5) сокращения дроби;

6) возведения дроби в степень п (п — натуральное);

7) функций, реализующих операции отношения (равно, не

равно, больше или равно, меньше или равно, больше, меньше).

Дробь представить следующим типом:

370

Type Frac=Record

P: Integer;

1..32767

End;

Используя этот модуль, решить задачи 1, 2.

Дан массив А — массив обыкновенных дробей. Найти сумму

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

Вычислить среднее арифметическое всех дробей, результат пред-

ставить в виде несократимой дроби.

Дан массив А

—

массив обыкновенных

дробей.

Отсортировать

его в порядке возрастания.

III.

Реализовать в виде модуля набор подпрограмм для выпол-

нения следующих операций с квадратными матрицами:

1) сложения двух матриц;

2) умножения одной матрицы на другую;

3) нахождения транспонированной матрицы;

4) вычисления определителя матрицы.

Матрицу описать следующим образом:

Const NMax=10;

Type Matrica=Array[1..NMax,1..Nmax] Of

Real;

Используя этот модуль, решить следующие задачи.

Решить систему линейных уравнений TV-го порядка

(2 < N< 10) методом Крамера.

Задан массив величин типа Matrica. Отсортировать этот мас-

сив в порядке возрастания значений определителей матриц.

IV. Реализовать в виде модуля набор подпрограмм для выпол-

нения следующих операций над векторами:

1) сложения;

2) вычитания;

3) скалярнго умножения векторов;

4) умножения вектора на число;

5) нахождения длины вектора.

Вектор представить следующим типом:

Type Vector=Record

X,Y: Real

End;

Используя этот модуль, решить задачи 1, 2.

Дан массив А

—

массив векторов. Отсортировать его в поряд-

ке убывания длин векторов.

С помощью датчика случайных чисел сгенерировать 2N целых

чисел. Nnap этих чисел задают N точек координатной плоскости.

Вывести номера тройки точек, которые являются координатами

вершин треугольника с наибольшим углом.

371

V. Реализовать в виде модуля набор подпрограмм для выполне-

ния следующих операций над натуральными числами в Р-ичной

системе счисления (2 < Р< 9):

1) сложения;

2) вычитания;

3) умножения;

4) деления;

5) перевода из десятичной системы счисления в Р-ичную;

6) перевода из Р-ичной системы счисления в десятичную;

7) функции проверки правильности записи числа в Р-ичной

системе счисления;

8) функций, реализующих операции отношения (равно, не

равно, больше или равно, меньше или равно, больше, меньше).

Р-ичное число представить следующим типом:

Type Chislo=Array[l..16] Of 0..9;

Используя этот модуль, решить задачи 1, 2.

Возвести число в степень (основание и показатель степени

записаны в Р-ичной системе счисления). Результат выдать в Р-

ичной и десятичной системах счисления.

Дан массив А

—

массив чисел, записанных в Р-ичной систе-

ме счисления. Отсортировать его в порядке убывания. Результат

выдать в Р-ичной и десятичной системах счисления.

VI.

Реализовать в виде модуля набор подпрограмм для выпол-

нения следующих операций над натуральными числами в шест-

надцатеричной системе счисления:

1) сложения;

2) вычитания;

3) умножения;

4) деления;

5) перевода из двоичной системы счисления в шестнадцате-

ричную;

6) перевода из шестнадцатеричной системы счисления в деся-

тичную;

7) функции проверки правильности записи числа в шестнад-

цатеричной системе счисления;

8) функций, реализующих операции отношения (равно, не

равно, больше или равно, меньше или равно, больше, меньше).

Используя этот модуль, решить следующие задачи.

Возвести число в степень (основание и показатель степени

записаны в шестнадцатеричной системе счисления). Результат

выдать в шестнадцатеричной и десятичной системах счисления.

Дан массив А — массив чисел, записанных в шестнадцате-

ричной системе счисления. Отсортировать его

порядке убывания.

Результат выдать

шестнадцатеричной

десятичной системах счис-

ления.

372

VII.

Определим граф как набор точек, некоторые из которых

соединены отрезками, подграф — как граф, являющийся под-

множеством данного графа.

Реализовать в виде модуля набор подпрограмм, определяющих:

1) число точек в графе;

2) число отрезков в графе;

3) число изолированных подграфов в графе (подграфов, не

соединенных отрезками);

4) диаметр графа — длину максимальной незамкнутой линии

в графе (длина каждого звена — 1);

5) граф — объединение двух графов;

6) подграф — пересечение двух графов;

7) подграф — дополнение данного графа до полного (графа с

тем же количеством вершин, что и в данном, и с линиями между

любыми двумя вершинами);

8) число отрезков, выходящих из каждой вершины графа.

При запуске должны инициализироваться переменные:

Full_Graph — полный граф с числом вершин NumberOfVertix,

Null_Graph — граф без отрезков с числом вершин

NumberOfVertix.

Граф представить как объект

Const NumberOfVertix=50;

Type Graph=Array[1..NumberOfVertix,

1..NumberOfVertix]

Of Boolean;

Используя модуль, решить следующую задачу.

Найти все правильные графы из N вершин (граф правилен,

если из всех вершин выходит равное количество отрезков).

VIII. Реализовать в виде модуля набор подпрограмм для выпол-

нения следующих операций над длинными числами:

1) сложения;

2) вычитания;

3) умножения;

4) нахождения частного и остатка от деления одного числа на

Другое;

5) функций, реализующих операции отношения (равно, не

равно, больше или равно, меньше или равно, больше, меньше).

Длинное число представить следующим типом:

Type Tsifra=0..9;

Chislo=Array[l..1000] Of Tsifra;

Используя этот модуль, решить задачи 1, 2.

Возвести число в степень (основание и показатель степени

—

длинные числа).

Дан массив длинных чисел. Упорядочить этот массив в поряд-

ке убывания.

373

IX. Реализовать в виде модуля набор подпрограмм для выпол-

нения операций с многочленами от одной переменной (первый

многочлен степени т, второй

—

степени п):

1) сложения;

2) вычитания;

3) умножения;

4) деления с остатком;

5) операций отношения (равно, не равно);

6) возведения в натуральную степень к;

7) вычисления производной от многочлена;

8) вычисления значения в точке х

Многочлен представить следующим типом:

Type Mnogochlen

Array[1..500] Of Integer;

Используя этот модуль, решить задачи 1, 2.

Найти наибольший общий делитель многочленов

Р(х)

и Q(x).

Вычислить P

(x)

—

(x).

X. Разработать способ представления множеств, содержащих

более 255 элементов (до 2000). Создать модуль, позволяющий вы-

полнять следующие операции над элементами таких множеств:

а) объединение;

б) пересечение;

в) разность;

г) функция проверки принадлежности элемента множеству;

д) функция проверки, является ли данное множество подмно-

жеством (надмножеством) другого.

Используя созданный модуль, решить следующие задачи.

Дан массив

множеств.

Упорядочить элементы массива

поряд-

ке возрастания количества компонент соответствующих множеств.

Разработать программу, которая вводит несколько множеств,

выражение, операндами которого являются эти множества, с опе-

рациями объединения, пересечения и вычитания, вычисляет зна-

чение этого выражения и выводит результат.

6.15. Задачи по теме «Динамические структуры данных»

Составить программу, которая вставляет в список L новый

элемент F

за

каждым вхождением элемента Е.

Составить программу, которая вставляет в список L но-

вый элемент /"перед первым вхождением элемента Е, если Е

входит в L.

Составить программу, которая вставляет в непустой список

L, элементы которого упорядочены по неубыванию, новый эле-

мент Е так, чтобы сохранилась упорядоченность.

Составить программу, которая удаляет из списка L все эле-

менты Е, если таковые имеются.

374

Составить программу, которая удаляет из списка L за каж-

дым вхождением элемента Е один элемент, если таковой имеется

и он отличен от Е.

6. Составить программу, которая удаляет из списка L все отри-

цательные элементы.

Составить программу, которая проверяет, есть ли в списке L

хотя бы два одинаковых элемента.

8. Составить программу, которая переносит в конец непустого

списка L его первый элемент.

9. Составить программу, которая вставляет в список L за пер-

вым вхождением элемента Е все элементы списка L, если Е вхо-

дит в L.

10.

Составить программу, которая переворачивает список L,

т.е.

изменяет ссылки в этом списке так, чтобы его элементы ока-

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

11.

Составить программу, которая в списке L из каждой группы

подряд идущих одинаковых элементов оставляет только один.

12.

Составить программу, которая формирует список L, вклю-

чив в него по одному разу элементы, которые входят одновре-

менно в оба списка Ц и L

13.

Составить программу, которая формирует список L, вклю-

чив в него по одному разу элементы, которые входят в список L

но не входят в список L

14.

Составить программу, которая формирует список L, вклю-

чив в него по одному разу элементы, которые входят в один из

списков Ц и Ь

, но в то же время не входят в другой.

15.

Многочлен

Р(х) =

а„х"

а„_\Х

+ ••• +

а,х + а

с целыми коэффициентами можно представить в виде списка, при-

чем если а

(

= 0, то соответствующее звено не включается в список.

—>

Л-1

O/2-l

—»

—>

1 а

яо

Nil

Ниже показано представление многочлена S(x)

—

52х

—

Зх

+ х.

—>

8 -3

1 1 Nil

Описать на языке Паскаль тип данных, соответствующий

такому представлению многочленов, и определить следующие

процедуры и функции для работы с этими списками-много-

членами:

15.1.

Логическую функцию Ravno (P,

Q),

проверяющую на ра-

венство многочлены Р и Q.

375

15.2.

Функцию Znach(P,x), вычисляющую значение много-

члена Р в целочисленной точке х.

15.3.

Процедуру Diff (P,Q), которая строит многочлен Q

—

производную многочлена Р.

15.4.

Процедуру Slozh

(P,

R),

которая строит многочлен R

—

сумму многочленов

и Р.

15.5.

Процедуру Print (P,v), которая печатает многочлен Р

как многочлен от переменной, однобуквенное имя которой явля-

ется значением литерного параметра v; например, для указанного

выше многочлена £ процедура Print (S, 'у') должна напечатать

52уТ40-ЗуТ8

у.

15.6.

Процедуру Vvod (P), которая считывает из входного фай-

ла безошибочную запись многочлена (за ней

—

пробел) и форми-

рует соответствующий список-многочлен Р.

15.7.

Дан многочлен

Р(х)

степени

п.

Получить многочлен

(х).

15.8.

Дан многочлен Р{х) степени п. Получить многочлен

Р(х +

1) —

Р(х).

Какова степень этого многочлена?

16.

Составить программу для упорядочения в порядке возраста-

ния элементов однонаправленного списка.

17.

Составить программу, заполняющую список последователь-

ностью случайных различных целых чисел и суммирующую те

его элементы, которые расположены между минимальным и мак-

симальным элементом (если минимальный элемент предшеству-

ет максимальному).

18.

Дан список, содержащий целые числа. Сформировать дру-

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

являются простыми числами.

19.

Дан список, содержащий натуральные числа. Удалить те его

элементы, которые кратны заданному числу к.

20.

Дан список, элементами которого являются векторы

(Const NMax=200;

Type Vector=Array[1..NMax] Of

Real;).

Сформировать список из длин этих векторов.

21.

Элементами списка являются слова

—

имена существитель-

ные,

записанные в именительном падеже (строки длиной не бо-

лее

символов). Составить программу, которая добавляет за каж-

дым словом все его падежные формы.

22.

Дан список, содержащий целые числа. Определить количе-

ство различных элементов этого списка.

23.

Даны упорядоченные списки Ц и

1^.

Вставить элементы спис-

ка L

в список L

{

, не нарушая его упорядоченности.

24.

Дан список, содержащий запись неотрицательных целых

чисел в двоичной системе счисления. Заменить каждый эле-

мент списка на его запись в шестнадцатеричной системе счис-

ления.

376

25.

Дан список, содержащий обыкновенные дроби вида ^,

(Р — целое, Q

—

натуральное). Составить программу для сумми-

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

венной несократимой дроби.

26.

Программа должна находить среднее арифметическое эле-

ментов непустого однонаправленного списка вещественных чи-

сел,

заменять все вхождения числа х на число у, менять местами

первый и последний элементы, проверять, упорядочены ли чис-

ла в списке по возрастанию.

27.

Дан список вещественных

чисел.

Написать следующие функции:

а) проверки наличия в нем двух одинаковых элементов;

б) переноса в начало его последнего элемента;

в) переноса в конец его первого элемента;

г) вставки списка самого в себя вслед за первым вхождением

числа х.

28.

Дан список строк. Написать следующие подпрограммы:

а) обращение списка (изменить ссылки в списке так, чтобы

элементы оказались расположены в противоположном порядке);

б) из каждой группы подряд идущих элементов оставить толь-

ко один;

в) оставить в списке только первые вхождения одинаковых

элементов.

29.

Даны два списка L\ и L

пар вещественных чисел. Написать

подпрограммы, возвращающие новый список L, включающий в себя:

а) пары списка Ь

первая координата которых встречается как

вторая координата у пар списка L

;

б) пары

(х,

у) списка L

встречающиеся в виде

(у,

х) в списке Li,

в) пары

(х,у),

где х<у списка L

30.

Даны два списка L

и L

вещественных чисел. Написать под-

программы, возвращающие новый список L, включающий по

одному разу числа, которые:

а) входят одновременно в оба списка;

б) входят хотя бы в один из списков;

в) входят в один из списков L

и L

, но в то же время не входят

в другой из них;

г) входят в список L

но не входят в список L

31.

Целое длинное число представляется строкой цифр. Напи-

сать программу, упорядочивающую числа по неубыванию.

32.

Дан список слов, среди которых есть пустые. Написать под-

программу, выполняющую следующее действие:

а) перестановку первого и последнего непустых слов;

б) печать текста из первых букв непустых слов;

в) удаление из непустых слов первых букв;

г) определение количества слов в непустом списке, отличных

от последнего.

377

6.16. Задачи по теме «Графика»

Построить чертежи к следующим задачам.

В треугольной пирамиде построить сечение, параллельное

основанию.

треугольной пирамиде построить сечение, проходящее че-

рез боковое ребро и медиану основания.

треугольной пирамиде построить сечение, проходящее через

одну из сторон основания и середину противоположного ребра.

треугольной пирамиде построить сечение, проходящее че-

рез среднюю линию боковой грани и противоположную вершину

основания.

В треугольной пирамиде провести сечение, проходящее

через сторону основания и наклоненное к основанию под уг-

лом 30°.

6. В правильной четырехугольной пирамиде провести сече-

ние,

проходящее через диагональ основания и вершину

пирамиды.

В правильной четырехугольной пирамиде провести сече-

ние,

проходящее через диагональ основания и середину боко-

вого ребра.

8. В правильной четырехугольной пирамиде провести сечение,

проходящее через диагональ основания и наклоненное к плоско-

сти основания под углом 30°.

9. В правильной четырехугольной пирамиде провести сечение,

параллельное основанию и проходящее через середину бокового

ребра.

10.

правильной четырехугольной пирамиде провести сечение,

проходящее через вершину пирамиды и перпендикулярное плос-

кости основания.

11.

правильной четырехугольной пирамиде провести сечение,

проходящее через одну из сторон основания и середину высоты.

12.

Основание четырехугольной пирамиды

—

ромб. Вершина

пирамиды проектируется в центр симметрии ромба. Провести се-

чение, проходящее через высоту основания, опущенную из тупо-

го угла ромба, и боковое ребро, которое проходит через эту же

вершину.

13.

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

—

ромб. Вершина пирамиды проекти-

руется в вершину острого угла ромба. Провести сечение, проходя-

щее через вершину пирамиды и высоту ромба, опущенную из ту-

пого угла.

14.

В прямоугольном параллелепипеде провести диагональное

сечение.

15.

В прямоугольном параллелепипеде провести сечение, про-

ходящее через сторону нижнего основания и противоположную

сторону верхнего основания.

378

16.

В прямой четырехугольной призме провести сечение, про-

ходящее через диагональ нижнего основания и одну из вершин

верхнего основания.

17.

прямой четырехугольной призме провести сечение, про-

ходящее через сторону нижнего основания под углом

30 °

к ос-

нованию.

18.

правильной шестиугольной призме провести сечение, про-

ходящее через одну из сторон нижнего основания и противопо-

ложную ей сторону верхнего основания.

19.

прямоугольном параллелепипеде построить сечение, про-

ходящее через одну из сторон нижнего основания и одну из вер-

шин верхнего.

20.

прямоугольном параллелепипеде построить сечение, про-

ходящее через одно из его ребер и точку пересечения диагоналей

противолежащей этому ребру грани.

21.

правильной шестиугольной пирамиде построить сечение,

проходящее через вершину и большую диагональ основания.

22.

прямом цилиндре построить осевое сечение.

23.

В правильной шестиугольной призме построить сечение,

проходящее через большую диагональ нижнего основания и одну

из сторон верхнего.

24.

Изобразить на экране ЭВМ следующий рисунок:

3) 4)

379