Методы программирования: Методическое пособие для выполнения лабораторных работ

Страницы работы

Содержание работы

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

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

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

(часть 1)

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

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

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

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

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

Определение

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

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

Задание

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

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

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

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

На экран выводятся n + 1 строк. Каждая i –ая строка (0 £ i £ n ) содержит целые числа, записанные через пробел, — посчитанные биномиальные коэффициенты Cik  (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)  удаляет ненужную информацию. *

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


Похожие материалы

Информация о работе

Тип:
Методические указания и пособия
Размер файла:
229 Kb
Скачали:
0