Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики




НазваниеМетодические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики
страница1/8
Дата16.02.2013
Размер0.7 Mb.
ТипМетодические указания
  1   2   3   4   5   6   7   8





Томский государственный университет

Факультет информатики


Ю. Л. Костюк, А. Л. Фукс, И. Л. Фукс


Основы разработки алгоритмов


Издание 2-е, дополненное


Методические указания


Томск – 2004


Методические указания рассмотрены и одобрены методической комиссией факультета информатики.


Декан факультета информатики С.П. Сущенко


Председатель методической комиссии В.В. Поддубный


Методические указания предназначены для подготовки к сдаче ЕГЭ, а также для подготовки к вступительному экзамену по информатике. Для решения предлагаемых задач достаточно знаний в объеме школьной программы по информатике и владения начальными навыками алгоритмизации.

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


Издание посвящается 400-летию г. Томска


Почтовый адрес: 634050, г. Томск, пр. Ленина, 36, ТГУ,

приемная комиссия

Телефон: (382-2) 52-96-72

Информационный интернет-сервер:

http://www.inf.tsu.ru

Электронная почта:

kostuk@inf.tsu.ru

fooks@inf.tsu.ru

foox@inf.tsu.ru



© Костюк Ю. Л., Фукс А. Л., Фукс И. Л., 2004

1.РЕКУРРЕНТНЫЕ АЛГОРИТМЫ


Основой рекуррентных алгоритмов являются рекуррентные соотношения. Это соотношения вида:

где – константы,



В практических задачах чаще всего .


Вычисление суммы элементов массива. Дан вещественный массив a длины n. Найти сумму элементов массива.

Введем обозначение для суммы первых i элементов массива. Тогда можно записать следующее рекуррентное соотношение:

, , при .

В программе будем последовательно вычислять , используя для этих сумм одну переменную S.

S:=0;

for i:=1 to n do S:=S+a[i];


Нахождение минимума в массиве. Дан целочисленный массив длины n. Найти минимальный элемент в массиве.

Пусть – минимальный среди первых i элементов массива. Очевидно, что , а при выполняется:

.

В программе будем последовательно вычислять , используя для хранения этих значений одну переменную m.

m:=a[1];

for i:=2 to n do

if a[i]
then m:=a[i];


Поиск второго максимума. Дан целочисленный массив длины n. Найти второй максимальный элемент (т.е. элемент, который будет иметь номер n-1, если массив упорядочить по возрастанию).

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

, , если ,

, , если ,

, , если .

В программе будем последовательно вычислять и , используя для этого переменные s и f.

if a[1]>=a[2]

then begin f:=a[1]; s:=a[2]; end

else begin f:=a[2]; s:=a[1]; end;

for i:=3 to n do

if a[i]>f then begin s:=f; f:=a[i]; end

else if a[i]>s then s:=a[i];


Вычисление числа по цифрам. Дан целочисленный массив, содержащий k десятичных цифр некоторого целого положительного числа N. Вычислить значение N.

Пусть цифры числа заносились в массив последовательно слева направо, т.е. содержит цифру самого старшего ()-го разряда, а – самого младшего (нулевого). Очевидно, что при правильном задании массива десятичных цифр , а искомое значение

.

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

.

Будем последовательно вычислять выражения внутри скобок, начиная с самых внутренних, а результат сохранять в переменной N:

N:=a[1];

for i:=2 to k do N:=N*10+a[i];


Вычисление приближенного значения функции. Для заданного вещественного x и целого n вычислить приближенное значение

.

При вычислении подобных сумм удобно определять сразу два рекуррентных соотношения: одно – для вычисления следующего слагаемого на основе предыдущего, а другое – для вычисления частичных сумм. Введем обозначения: i-е слагаемое, – сумма первых i слагаемых (). Тогда , а при . Выразим через : . Для сумм выполняется: и . В программе для хранения слагаемых и сумм используем вещественные переменные a и S.

a:=1; S:=1;

for i:=1 to n do

begin a:=a*x/i; S:=S+a; end;


Трудоемкость алгоритмов. Каждый из рассмотренных алгоритмов содержит цикл for, выполняющийся n ( или n – 1) раз. Так как перед циклом и внутри цикла количество выполняемых действий – константа, то общее число действий можно представить в виде C1 + C2 * n, где C1 и C2 – константы. Таким образом, трудоемкость этих алгоритмов – линейная.


Задачи для самостоятельного решения 1


1.1.Дан вещественный массив длины n. Найти сумму квадратов элементов массива.

1.2.Дан вещественный массив длины n. Найти суммы положительных и отрицательных элементов массива.

1.3.Для заданного целого неотрицательного n вычислить значение факториала . ().

1.4.Для заданного целого неотрицательного n вычислить значения двойных факториалов и .

1.5.Вычислить n-е число Фибоначчи , используя рекуррентное соотношение: , , при .

1.6.Вычислить n-е число Фибоначчи ранга 3, используя рекуррентное соотношение:

, , при .

1.7.По заданному вещественному значению x и массиву вещественных коэффициентов вычислить значение полинома .

1.8.Для заданного вещественного x и целого n вычислить приближенное значение

.


1.9.Для заданного вещественного x и целого n вычислить приближенное значение



1.10.Для заданного вещественного x и целого n вычислить приближенное значение

.

1.11.Для заданного вещественного x и целого n вычислить приближенное значение

.

1.12.Для заданного вещественного x и целого n вычислить приближенное значение

.


1.13.Для заданного вещественного значения и числа итераций n вычислить приближенное значение , используя рекуррентное соотношение: , , при .

1.14.Вычислить наибольший общий делитель (НОД) целых положительных чисел a и b, используя следующие соотношения:

НОД(a, b) = НОД(b, a),

НОД(a, 0) = a,

НОД(a, b) = НОД(b, a mod b), если .

1.15.** По заданному целому положительному значению N вычислить и сохранить в массиве набор десятичных цифр N.


  1   2   3   4   5   6   7   8

Похожие:

Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconМетодические указания к дипломному проектированию по специальности 351400 «Прикладная информатика в экономике»
Методические указания рассмотрены и одобрены кафедрой “Экономических информационных систем и информационных технологий” (Протокол...
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconУо «гродненский государственный аграрный университет» Кафедра растениеводства
Методические указания рассмотрены и одобрены на заседании методической комиссии агрономического факультета заочного отделения (протокол...
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconМетодические указания к выполнению контрольной работы по физике для студентов инженерных специальностей заочного отделения
...
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconМетодические указания к выполнению лабораторных работ по материаловедению
Рассмотрены и рекомендованы к изданию методической комиссией механического факультета Архангельского государственного технического...
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconМетодические указания (рекомендации) студентам
Методические указания рассмотрены и одобрены кафедрой ихтиопатологии и гидробиологии фгоу впо «Калининградский государственный технический...
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconРабочая программа и методические указания для студентов направления 080100 «Экономика»
Рассмотрены и рекомендованы к изданию учебно-методической комиссией факультета экономики и управления Санкт-Петербургского
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconМетодические указания по выполнению курсовой работы для студентов очного и заочного отделения по специальностям i-25 01 04 «Финансы и кредит»
Методические указания рассмотрены и одобрены на засе­дании кафедры учета и анализа в апк уо «ггау»
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconМетодические указания составлены в соответствии с Государственным образовательным стандартом высшего профессионального образования по дисциплине «Русский язык и культура речи»
Методические указания и контрольные задания рассмотрены и одобрены кафедрой 22 апреля 2005 г., протокол №8
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconМетодические указания по выполнению контрольных работ для студентов направления 080200 «Менеджмент» Санкт-Петербург
Рассмотрены и рекомендованы к изданию учебно-методической комиссией факультета экономики и управления Санкт-Петербургского
Методические указания Томск 2004 Методические указания рассмотрены и одобрены методической комиссией факультета информатики iconМетодические указания к лабораторно практическим занятиям по дисциплине: «строительное материаловедение»
Природные каменные материалы: Методические указания к лабораторной работе по дисциплине «Архитектурное материаловедение» / Сост....
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница