Нестеренко Т.В.
Методическое пособие
к курсу «Методы программирования»
(часть 1)
Лабораторные работы
Новосибирск 2008
Данное методическое пособие содержит описание лабораторных работ, которые предлагаются для выполнения студентам Высшего колледжа информатики НГУ в рамках учебного курса “Методы программирования”. Они предназначены для закрепления теоретического материала, излагаемого на лекционных занятиях, а также для приобретения профессиональных практических навыков программмирования на языках программирования высокого уровня. Набор этих заданий был предложен разработчиками данного учебного курса Т.Г. Чуриной и В.А. Цикозой.
Рецензент к.ф.-м.н. Чурина Т.Г.
Многочлен вида
называется биномом Ньютона, а
коэффициенты 
(0
£ m £ n) называются
биномиальными коэффициентами.
Используя два описанных ниже метода, найти значения коэффициентов разложения многочлена (a + b)n .
С клавиатуры вводится число n — значениемаксимальной степени, для которой нужно посчитать коэффициенты бинома Ньютона.
На экран выводятся n + 1 строк. Каждая i –ая строка (0 £ i £ n ) содержит целые числа, записанные через пробел, — посчитанные биномиальные коэффициенты Cik (0 £ k £ i).
Выпишем коэффициенты разложения в строчку, начиная с 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.
Биномиальные коэффициенты также можно вычислить по следующей формуле (число сочетаний из n по k):
,
где выражение n!(n-факториал)обозначает произведение всех натуральных чисел от 1 до n.
Исходя из соотношений:
n!= n*(n-1)!
0! = 1,
необходимо написать рекурсивную функцию вычисления факториала на языке реализации, а затем использовать ее для вычисления биномиальных коэффициентов по приведенной выше формуле.
При реализации первого метода рекомендуется использовать один или два одномерных массива.
Необходимо экспериментально установить максимальное n, для которого можно посчитать коэффициенты разложения многочлена, не получив при этом знакового переполнения. Такое переполнение можно обнаружить, когда вместо положительных чисел на экран выдаются отрицательные.
Определение: Простое число — это целое число p, большее 1 и обладающее тем свойством, что единственными делителями p являются 1 и само р.
Например, 2, 3, 5, 7 и 11 являются простыми, а 4, 6, 9 и 10 не являются таковыми.
Используя два описанных ниже метода, найти все простые числа, не превосходящие некоторого числа N.
С клавиатуры вводится целое число N.
На экран в возрастающем порядке через пробел вывести все простые числа, меньшие либо равные N.
Перебирая по порядку все числа от 2 до N,
проверять для каждого числа, имеет ли оно делители, большие 1 и меньшие самого
этого числа. Если делителей нет, то выдать число на экран. Следует отметить,
что для любого числа K достаточно проверить,
делится ли оно на числа из интервала от 2 до 
.
Шаг 0. Образоватьиз целых чисел от 2 до N множество М. Выбрать в нем минимальный по значению элемент K (это 2).
Шаг 1. Удалить из множества все числа, большие K, которые делятся на K без остатка. Это все числа, отстоящие друг от друга на K, начиная с числа 2*K.
Шаг 2. Переменной K присвоить значение следующего минимального элемента из
множества М (это будет следующее простое число). Если К £ 
то перейти на Шаг 1.
Шаг 3. Выдать на экран значения всех элементов множества M в возрастающем порядке.
Язык программирования – Паскаль или С.
При реализации на Паскале второго метода использовать тип данных множество.
Написать программу, которая поддерживает работу с каталогом библиотеки:
1) вводит информацию о новых печатных изданиях,
2) показывает содержимое каталога библиотеки,
3) по некоторым признакам ищет в нем и выводит на экран подходящую информацию,
4) редактирует имеющуюся информацию, *
5) удаляет ненужную информацию. *
Печатные издания разделяются на книги, газеты и журналы. В каталоге должна храниться, например, следующая информация:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
