Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Стандартные циклические алгоритмы





Рассмотрим стандартные циклические алгоритмы, такие как вычисление суммы, произведения и подсчет количества элементов, удовлетворяющих некоторому условию.

Вычисление суммы.

Для заданного натурального числа N вычислить сумму

.

Подсчет суммы осуществляется следующим образом. Начальное значение суммы S =0. На первом шаге сумма S есть первое слагаемое (S =1). Далее к первому слагаемому прибавляем второе, получаем новую сумму . Так как на предыдущемшаге S =1, то можно записать . К сумме двух первых слагаемых прибавляем третье . Так как на предыдущем шаге , то можно записать и т.д.

Получили следующую последовательность шагов:

1) S =1.

2) .

3)

Запишем i -й шаг, опираясь на предыдущие шаги:

i)

Выясним правило изменения номера шага i. В описанной последовательности i = 1, 2, 3 и т.д. В сумме N слагаемых, поэтому последним значением i будет N. Отсюда нашли правило изменения i =1, N, 1.

Сверяя инструкции каждого шага, находим, что выражение на первом шаге отличается от других (однотипных). Чтобы оно стало таким как все надо записать: S = S +1 (учитываем, что ). Отсюда для S возникает необходимость задания начального значения, но такого, чтобы на первом шаге S + 1=1. Этим числом является нуль, при сложении с нулем сумма не меняется.

Так как известно число шагов цикла, то для построения алгоритма используем цикл с параметром i. Блок-схема алгоритма приведена на рис. 16.

Алгоритм на псевдокоде:

Начало

Ввод N

S =0

Для i от 1 до N шаг 1

Нц

Кц

Вывод S

Конец

 

S= 0
i= 1, N, 1
Ввод N
Начало
Конец
Вывод S

Рис. 16. Блок-схема алгоритма вычисления суммы

 

Сформулируем правило вычисления суммы:

• начальное значение суммы S =0;

• в теле цикла выполнить команду S = S +<слагаемое>.

Упражнения для самостоятельной работы.

1. Для заданного натурального числа N вычислить сумму N -слагаемых:

а)

б)

в)

2. Вычислить значение полинома

z = x 8 + 2 x 7 + 3 x 6 + 4 x 5 + 5 x 4 + 6 x 3 + 7 x 2 + 8 x + 9.

Вычисление суммы с заданной точностью.

Найти приближенное значение суммы ряда с заданной точностью


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

Вычисление суммы осуществляется на основе соотношения:

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

откуда

Блок-схема алгоритма приближенного вычисления суммы бесконечного ряда приведена на рис. 17.

Алгоритм на псевдокоде:

Начало

Ввод x, e

S =0

a =1

n= 0

Пока ½ a ½> e

Нц

S = S + a

n = n +1

a = a × x / n

Кц

Вывод S

Конец

При выполнении этого алгоритма переменная n последовательно принимает значения 0, 1, 2, …, переменная a принимает значения 1, , , …, переменная S в свою очередь принимает значения 0, 1, 1+ , 1+ + , …

 

 

S= 0, a =1, n =0
Ввод x, e
Начало
Конец
Вывод S
Да
Нет
½ a ½> e
S=S+a n=n+1

 


Рис. 17. Блок-схема алгоритма вычисления суммы c заданной точностью

Упражнения для самостоятельной работы.

Вычислить приближенное значение суммы ряда:

 

Вычисление произведения.

Дано натуральное число N. Вычислить произведение для N сомножителей:

Подсчет произведения осуществляется следующим образом. Начальное значение произведения Р =1. т.к. при первом подсчете должны получить значение Р, равное , а при умножении на единицу произведение не меняется.

1) ,

Далее выполняется следующая последовательность шагов:

2)

3)

Запишем i -й шаг, опираясь на предыдущие шаги

i)

Сформулируем правило вычисления произведения:

• начальное значение произведения Р =1;

• в теле цикла выполнить команду Р = Р *<сомножитель>.

Так как известно число шагов цикла, то для построения алгоритма используем цикл с параметром i. Блок схема алгоритма приведена на рис. 18.

Р= 1
i= 1, N, 1
Ввод N
Начало
Конец
Вывод Р
Алгоритм на псевдокоде:

Начало

Ввод N

Р =1

Для i от 1 до N шаг 1

Нц

Кц

Вывод Р

Конец

 

 


Рис. 18. Блок-схема алгоритма

вычисления произведения


Упражнения для самостоятельной работы.

1. Вычислить факториал натурального числа N по формуле

N!=1*2*3*4*5 … * N

2. Для заданного натурального числа N вычислить произведение N -сомножителей

3. Число а возвести в степень b, используя операцию умножения.

 

Подсчет количества элементов.

Нет
Да
K = K +1
x >10
К= 0
i= 1, 20, 1
Ввод x
Начало
Вывод К
Конец
Задано 20 чисел. Определить сколько среди них чисел больше 10? Подсчет количества чисел является циклическим процессом, так как каждый раз мысовершаем одно и то же действие: предыдущее натуральное число увеличиваем на единицу. Обозначив через К – счетчик искомых элементов, легко получить правило счетчика: К = К +1 (на очередном шаге цикла). При первом подсчете значение счетчика К должно быть равно единице, а до начала счета счетчик пуст, следовательно, начальное значение счетчика равно нулю.

Блок-схема алгоритма приведена на рис. 19.

Алгоритм на псевдокоде:

Начало

К =0

Для i от 1 до 20 шаг 1

Нц

Ввод х

Если x >10

то К = К +1

Кц

Вывод К

Конец

Рис. 19. Блок-схема алгоритма

подсчета количества элементов

 

Сформулируем правило счетчика:

• начальное значение счетчика К =0;

• в теле цикла выполнить команду К = К +1.

Упражнения для самостоятельной работы.

1. Задано 20 чисел. Определить:

а) сколько среди них отрицательных чисел;

б) сколько среди них располагаются в интервале [5, 10];

в) сколько среди них четных чисел;

2. В ЭВМ по очереди вводятся координаты N точек. Определить сколько из них попадет в кольцо радиуса R.

 

Вложенные циклы

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

Вычислить сумму S = 1! + 2! + 3! + … + 10!

Блок-схема алгоритма приведена на рис. 20.

S = S + P
S= 0
Начало
Вывод S
Конец
i= 1, 10, 1
P= 1
j= 1, i, 1
P = P*j
Алгоритм на псевдокоде:

Начало

S =0

Для i от 1 до 10 шаг 1

Нц

P =1

Для j от 1 до i шаг 1

Нц

P=P*j

Кц

S = S + P

Кц

Вывод S

Конец

 

Рис. 20. Блок-схема алгоритма

вычисления суммы факториалов

Простые типы данных

Реальные данные, которые обрабатывает программа, — это целыеи вещественные числа, символы и логические величины. Эти простые типы данных называют базовыми.

Все данные, обрабатываемые компьютером, хранятся в ячейках памяти компьютера, каждая из которых имеет свой адрес. Во время работы программы, заранее не известно в каких ячейках и по какому адресу будут записаны данные. Поэтому в языках программирования введено понятие переменной, позволяющее обращаться к содержимому памяти с помощью идентификатора или имени – последовательности, содержащей английские буквы, цифры, символы подчеркивания и начинающейся не с цифры. Например: Summa, H 8_ G 7, X 1, _ Rezult. Это имя будет указывать на значение.

В описанных выше алгоритмах все данные хранятся в виде переменных. Например, инструкция "Ввод а, b "означает введение пользователем значений двух переменных, а инструкция " К = К +1" означает увеличение значения переменной К на единицу.

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

Переменные могут существовать на всем протяжении работы программы - тогда они называются статическими, а могут создаваться и уничтожаться на разных этапах ее функционирования – такие переменные называются динамическими. Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции " К = К +1" 1 есть константа, или для удобства обозначать идентификаторами, например, рi = 3,1415926536.

Числовые данные

Числа бывают двух видов: целые и вещественные. Если число отрицательное, перед ним ставится знак "-"; если положительное, то знак "+" можно ставить, а можно и опускать. Вычисления над целыми числами выполняются точно, над вещественными – приближенно.

При записи вещественных чисел в качестве десятичного разделителя используется точка: 1.28, 3.3333. Очень большие или очень маленькие числа записываются в виде ± m E ± p, где mмантисса, целое или вещественное число с фиксированной точкой; Е(е) имеет смысл "умножить на 10 в степени"; p – порядок, целое число со знаком или без. Например: 1Е+4 (соответствует числу 10000), 3Е-3 (соответствует числу 0,003), 5.412Е-1 (соответствует числу 0,5412).

Над числами могут быть выполнены операции сложения, вычитания и умножения и деления. Каждая операция имеет свой приоритет. Операции с более высоким приоритетом (умножение и деление) будут выполняться раньше, чем операции с более низким приоритетом (сложение и вычитание). Изменить порядок вычисления можно с помощью круглых скобок.

С помощью арифметических операций формируются арифметические выражения, которые состоят из операций и операндов (переменных и констант). Например, выражение " а 1+2" состоит из одной операции "+" и двух операндов – переменной а 1 и числовой константы 2.

Упражнения для самостоятельной работы.

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

а) ; б)  

 

 


Символьные данные

Символьные данные заключаются в кавычки. Главным свойством символьных данных является их упорядоченность, т.е. свойство быть сравнимыми. Каждый символ имеет определенный числовой код (например, код символа латинской буквы ' А ' в большинстве кодировок 65), и упорядочение происходит в соответствии с этими числовыми кодами. Поэтому справедливо 'A' < 'B', ' B '<' C ', ' C '<' D ' и т.д.

Сравнение символьных переменных осуществляется посимвольно, начиная с первого символа. Если первые символы обеих переменных совпадают, то сравниваются вторые и т.д. Если длины (количество символов) сравниваемых переменных не совпадают, то меньшее дополняется пробелами (пробел является самым младшим символом).

Например,

'ABC' <' ABCD' 'торт' > 'тор' '123' < '13' '353' > '35'

Кроме того, допускается также операция сцепления строк, записываемая, с помощью символа "+". Например,

'123'+'4567' – получится '1234567'

'абв '+'abc '+' эюя' – получится 'абв abc эюя'

Упражнения для самостоятельной работы.

Задан массив символьных данных: '764', '475', '49', '3001', '75'. После сортировки по возрастанию элементы массива будут расположены в следующем порядке …

 

 

Логические данные

Логические данные могут принимать только два значения "истина" (" true ") или "ложь" (" false "). Они создаются двумя способами: при проверке условий и в виде значений переменных.

В качестве условий используются операции отношения. Операции отношения в общем случае – это два выражения, разделенные одним из знаков =, >, < или одной из комбинаций знаков <> (соответствует ¹), >= (соответствует ³), <= (соответствует £). Например:

a = b

x < a - b

Из простых условий можно строить более сложные. Для соединения простых условий используются логические операции И – " and ", ИЛИ – " or ", НЕ - " not ". Например,

(x + y <=1) or (x >=0)

(x >=5) and (x <=10)

not (x =7)

Эти логические операции определяются таблицей истинности (табл. 1).

Таблица 1

Таблица истинности для логических операций

А В И (A and B) ИЛИ (A orB) НЕ (not A)
и и и и л
и л л и л
л и л и и
л л л л и

Приоритеты всех логических операций ниже, чем операций отношения, поэтому операции отношения всегда выполняются первыми. А логические операции вычисляются в следующем порядке: НЕ (not), И(and), ИЛИ(or). Первой из двух одинаковых операций выполняется та, знак которой в условии встречается раньше. Скобки могут изменить это порядок.

Например, для условия

(y > z) and not ((x >0) or (z > x)) or (x > y)

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

3 2 1 4

(y > z) and not ((x >0) or (z > x)) or (x > y)

Логические величины также могут определяться явным присваиванием переменной истинного или ложного значения. Например: Flag = True.

Упражнения для самостоятельной работы.

1. Запишите приведенные ниже высказывания в виде условного выражения:

а) значение А принадлежит интервалу [-2; 0];

б) значение А не принадлежит интервалу [0; 3];

в) значение А принадлежит одному из интервалов [-5; -4], [0; 2].

2. В результате выполнения фрагмента алгоритма

A = 5

B = 3

M = A > B

N = A <> B

M = M or N

значения переменных M и N будут равны …

3. В результате выполнения фрагмента алгоритма

X = 4

Y = 10

Вывод (' X = ', X > Y, ' Y = ', X + Y, X = Y)

на печать будет выведено …

 







Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.