Нестеренко Т.В.

Методическое пособие

к курсу «Методы программирования»

(часть 1)

Лабораторные работы

Новосибирск 2008

Данное методическое пособие содержит описание лабораторных работ, которые предлагаются для выполнения студентам Высшего колледжа информатики НГУ в рамках учебного курса “Методы програм­мирования”. Они предназначены для закрепления теоретического материала, излагаемого на лекционных занятиях, а также для приобретения профессиональных практических навыков программ­ми­ро­вания на языках программирования высокого уровня. Набор этих заданий был предложен разработчиками данного учебного курса Т.Г. Чуриной и В.А. Цикозой.

Рецензент к.ф.-м.н. Чурина Т.Г.

Лабораторная работа № 1. Треугольник Паскаля

Определение

Многочлен вида

называется биномом Ньютона, а коэффициенты (0  m  n) называются биномиальными коэффициентами.

Задание

Используя два описанных ниже метода, найти значения коэффициентов разложения многочлена (a + b)ⁿ .

Входные данные

С клавиатуры вводится число n — значение максимальной степени, для которой нужно посчитать коэффициенты бинома Ньютона.

Выходные данные

На экран выводятся n + 1 строк. Каждая i –ая строка (0  i  n ) содержит целые числа, записанные через пробел, — посчитанные биномиальные коэффициенты C_i^k (0  k  i).

Метод 1. Треугольник Паскаля

Выпишем коэффициенты разложения в строчку, начиная с n = 0, 1 и так далее следующим образом:

n | Коэффициенты

0 | 1

1 | 1 1

2 | 1 2 1

3 | 1 3 3 1

4 | 1 4 6 4 1

5 | 1 5 10 10 5 1

6 | 1 6 15 20 15 6 1

7 |1 7 21 35 35 21 7 1

... |...........................................

Можно заметить, что первые и последние значения в каждой строке равны 1, а каждое из остальных значений в строчках, соответствующих n  2, равно сумме двух значений, расположенных над ним.

Таким образом, для каждого коэффициента можно записать следующие рекуррентные соотношения:

Используя полученные формулы, можно посчитать все коэффициенты по строкам, начиная с n = 0.

Метод 2. С использованием рекурсивной функции вычисления факториала

Биномиальные коэффициенты также можно вычислить по следующей формуле (число сочетаний из n по k):

,

где выражение n!(n-факториал)обозначает произведение всех нату­раль­ных чисел от 1 до n.

Исходя из соотношений:

n!= n*(n-1)!

0! = 1,

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

Требования к реализации

Язык программирования – Паскаль или С.

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

Необходимо экспериментально установить максимальное n, для которого можно посчитать коэффициенты разложения многочлена, не получив при этом знакового переполнения. Такое переполнение можно обнаружить, когда вместо положительных чисел на экран выдаются отрицательные.

Лабораторная работа № 2. Простые числа

Определение: Простое число — это целое число p, большее 1 и обла­да­ю­щее тем свой­ством, что единственными делителями p являются 1 и само р.

Например, 2, 3, 5, 7 и 11 являются простыми, а 4, 6, 9 и 10 не являются таковыми.

Задание

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

Входные данные

С клавиатуры вводится целое число N.

Выходные данные

На экран в возрастающем порядке через пробел вывести все простые числа, меньшие либо равные N.

Метод 1. По определению

Перебирая по порядку все числа от 2 до N, проверять для каждого числа, имеет ли оно делители, большие 1 и меньшие самого этого числа. Если делителей нет, то выдать число на экран. Следует отметить, что для любого числа K достаточно проверить, делится ли оно на числа из интервала от 2 до .

Метод 2. Решето Эратосфена

Шаг 0. Образовать из целых чисел от 2 до N множество М. Вы­брать в нем минимальный по значению элемент K (это 2).

Шаг 1. Удалить из множества все числа, большие K, которые делятся на K без остатка. Это все числа, отстоящие друг от друга на K, начиная с числа 2*K.

Шаг 2. Переменной K присвоить значение следующего минимального элемента из множества М (это будет следующее простое число). Если К  то перейти на Шаг 1.

Шаг 3. Выдать на экран значения всех элементов множества M в возрастающем порядке.

Требования к реализации

Язык программирования – Паскаль или С.

При реализации на Паскале второго метода использовать тип данных множество.

Лабораторная работа № 3. Библиотека Задание

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

1. вводит информацию о новых печатных изданиях,

2. показывает содержимое каталога библиотеки,

3. по некоторым признакам ищет в нем и выводит на экран подходящую информацию,

4. редактирует имеющуюся информацию, *

5. удаляет ненужную информацию. *

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

• книги

  • название

  • автор

  • год издания

  • издательство

  • номер полки

• газеты

  • название

  • год издания

  • месяц

  • день

  • номер полки

• журналы

  • название

  • год издания

  • номер выпуска

  • номер полки

Метод

Хранение информации должно осуществляться в одном типизи­ро­ван­ном файле. При этом для описания и хранения сведений о конкретных из­да­ниях нужно использовать такие типы данных, как записи с вариантными полями.

Интерфейс программы должен содержать меню, предо­ставляющее поль­зователю доступные действия, такие как ввод, редактирование, про­смотр, удаление данных, а также выход из программы.

Можно написать две программы: одна осуществляет ввод информации в файл, а другая — поиск и редактирование в уже созданном и запол­нен­ном файле.

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