Билет № 16

Билет № 16

Билет № 16

1. Алгоритмическая структура «цикл». Циклы со счетчиком и циклы по условию.

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

Предположим, нам необходимо письменно перевести ан­глийский текст на русский язык. Возможный алгоритм действий:

Прочесть предложение.

1.  Перевести это предложение на русский язык.

2.  Записать перевод в тетрадь.

3.  Если в тексте остались предложения, не переведенные на русский язык, то перейти к шагу 1, в противном случае завершить работу.

А вот пример из математики. Число, кратное только са­мому себе и 1, называется простым. 1, 2, 3, 5, 7 — простые числа; 4, 6, 8 — нет. В III веке до нашей эры греческий ма­тематик Эратосфен предложил алгоритм для нахождения всех простых чисел, меньших заданного п:

1.  Выписать все натуральные числа от 1 до п.

2.  Вычеркнуть 1.

3. Подчеркнуть наименьшее из неотмеченных чисел.

4. Вычеркнуть все числа, кратные подчеркнутому на предыдущем шаге.

5. Если в списке имеются неотмеченные числа, то перейти к шагу 3, в противном случае все подчеркнутые чис­ла — простые.

При выполнении этого алгоритма повторение шагов 3-5 происходит до тех пор, пока в исходном списке остаются не­отмеченные числа.

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

Циклический алгоритм — это алгоритм, содержащий циклы. Ситуация, при которой выполнение цикла никогда не за­канчивается, называется зацикливанием. Следует разраба­тывать алгоритмы, не допускающие таких ситуаций. Для правильной организации цикла необходимо выполнять сле­дующие требования:

1) перед началом цикла задавать начальные значения параметров — переменных, используемых в логическом выражении, отвечающем за продолжение или завершение цикла;

2) внутри цикла изменять переменные, влияющие на ну (на противоположное) значения логического выражения, за счет которого продолжается цикл, — Для того, чтобы цикл в некоторый момент завершился;

3)  проверять условие продолжения или окончания цикла (вычислять логическое выраж-е);

4)  выполнять операторы внутри цикла (тело цикла);

5)  управлять циклом — переходить к его началу, если он не закончен, или выходить из цикла в противном случае.

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

Различают циклы с известным числом повторений (цикл с параметром) и итерационные (с пред - и постусловием).

Рассмотрим, как выполняется каждый из этих циклов.

1.  Цикл с предусловием.

нет

1.1.  Проверяется условие (вычисляется значение логиче­ского выражения).

1.2.  Если значение логического выражения — «истина» (да), осуществляется переход к следующему пункту, иначе к п. 1.5.

1.3.  Выполняется тело цикла.

1.4.  Осуществляется переход к п. 1.1.

1.5.  Конец цикла.

2. Цикл с постусловием.

2.1.  Выполняется тело цикла.

2.2.  Проверяется условие (вычисляется значение логиче­ского выражения).

2.3.  Если значение логического выражения — «ложь» (нет), осуществляется переход к п. 2.1, иначе к сле­дующему пункту.

2.4.  Конец цикла.

2.  Цикл с параметром.

 

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

3.2.  Параметру цикла присваивается начальное значение.

3.3.  Параметр цикла сравнивается с конечным значени­ем.

3.4.  Если при положительном шаге параметр цикла пре­восходит конечное значение (при отрицательном шаге параметр цикла меньше конечного значения), то осуществляется переход к п. 3.8, иначе к следую­щему пункту.

3.5.  Выполняется тело цикла.

3.6.  Параметр цикла автоматически изменяется на вели­чину шага.

3.7.  Осуществляется переход к п.3.3.

3.8.  Конец цикла.

Если начальное и конечное значения параметра цикла яв­ляются целыми величинами, а шаг цикла равен 1, то цикл называется циклом со счетчиком.

2. Задача на определение количества информации и преобразование единиц измерения количества информации.

Задача 1.

Сколько битов информации несет сообщение о том, что из колоды в 32 карты достали даму пик?

решение.

При случайном вытаскивании карт из перемешанной ко­лоды ни одна из них не имеет преимущества быть выбран­ной по сравнению с другими. Следовательно, случайный выбор карт, в том числе и дамы пик, — события равноверо­ятные, и неопределенность знаний о результате вытаскива­ния карты равна 32 — числу карт в колоде. Получаем урав­нение: 2i = 32. Но 32 = 25. Следовательно, i = 5 битов.

Задача 2.

Два текста содержат одинаковое количество символов. Первый текст составлен из символов алфавита мощностью 32 символа, второй — мощностью 64 символа. Сравнить ко­личество информации в этих текстах.

Решение.

Информационный объем текста равен произведению чис­ла символов на информационный вес одного символа: I = i ·К. Поскольку оба текста имеют одинаковое число сим­волов (К), то различие информационных объемов определя­ется только разницей в информативности символов алфави­та (i). Найдем i для первого алфавита и 12 для второго алфавита:

2i1 =32, i1 = 5 битов; 2i2 =64, i2 = 6 битов.

Следовательно, информационные объемы первого и второ­го текстов будут равны соответственно:

I1= К ·5 битов I2 =К · 6 битов

Отсюда следует, что количество информации во втором тексте больше, чем в первом, в 1,2 раза.

Задача 3.

Определить, сколько времени потребуется для распечатки на лазерном принтере, печатающем со скоростью 512 симво­лов в секунду, текстового файла размером 256 Кб.

Решение.

256 Кб = 256 • 1024 байт;

256 • 1024 (байт)/ 512 (байт/с) = 512 (с) 9 (мин).

Билет № 17

1.  Технология решения задач с помощью компьютера (моделирование, формализация, алгоритмизация, программирование). Показать на примере задачи (математической, физической или другой).

Работа по решению задач с использованием компьютера делится на следующие этапы:

Этап	Результат	Уровень
Постановка задачи	Описательная информационная модель

 

Содержательный

Математическая модель

 

Математический

Алгоритмизация

Алгоритм

 

Алгоритмический

Программирование	Программа

 

Уточнение модели, решение

Компьютерный эксперимент (отладка и тестирование)

Компьютерный

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

На втором этапе описательная информационная модель формализуется, то есть записывается с помощью некоторого формального языка. Для этого требуется:

• понять, к какому классу принадлежит рассматривае­мая задача;

•  записать известные связи между исходными данными и результатами с помощью математических соотноше­ний;

•  выбрать наиболее подходящий способ для решения за­дачи.

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

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

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

Пример. Рассмотрим конкретный пример из области фи­зики. Водитель автомобиля, движущегося с некоторой по­стоянной скоростью, увидев красный свет светофора, нажал на тормоз. После этого скорость автомобиля стала умень­шаться каждую секунду на 5 метров. Требуется найти рас­стояние, которое автомобиль прошёл до полной его останов­ки.

Первый этап.

Дано: vоx — начальная скорость;

vХ — конечная скорость (равна нулю, так как ав­томобиль остановился);

ах — ускорение (равно -5 м/с).

Найти: sx — расстояние, которое автомобиль прошёл до

полной его остановки.

Второй этап.

В данной ситуации мы имеем дело с прямолинейным рав­ноускоренным движением тела. Формула для перемещения при этом имеет вид:

sx=

Перепишем эту формулу с учетом того, что конечная скорость равна нулю: sx = - . При ах = -5 м/с получим: К = v2ox/10.

Четвёртый этап. Запишем данный алгоритм на языке программирования Паскаль: Program pr1; Var v, s :real ; Begin

Третий этап.

Представим алгоритм решения задачи в виде блок-схемы:

Writeln(‘Введите начальную скорость’); Read(v); S:=v*v/10; Writeln; Writeln(‘Расстояние пройденное автомобилем’,s); End.

 

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

Пятый этап.

Программа выполняется несколько раз при различных исходных данных. Анализ результатов показывает, что чем больше начальная скорость автомобиля, тем большее рассто­яние он пройдет с начала торможения до полной остановки. Следовательно, переходить дорогу в неположенном месте опасно.

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

2. Задача на составление таблицы истинности для логической функции, содержащей операции отрицания, дизъюнкции и конъюнкции.

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

Алгоритм построения таблицы истинности:

1- Подсчитать количество переменных в формуле — п.

2.  Определить число строк в таблице — т = 2n.

3.  Подсчитать количество логических операций в форму­ле.

4.  Установить последовательность выполнения логиче­ских операций с учетом скобок и приоритетов.

5. Определить количество столбцов в таблице: число пере­менных + число операций.

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

n-разрядные двоичные числа от 0 до 2n - 1.

7. Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с уста­новленной в п. 4 последовательностью.