Решение экзаменационных задач
Решение задач по информатике представляют интерес не только для всех студентов, но и для абитуриентов и учащихся средних школ, собирающихся поступать на профильные специальности и факультеты. Здесь рассматриваются задачи, предлагавшиеся на вузовских экзаменах по информатике, а также задачи выпускных и вступительных экзаменов в 1994-1997 годах.
На экзаменах по информатике, как правило, включаютсязадачи обработки данных - информационные, логические, экономические, расчетные, комбинаторные и простейшие геометрические задачи. Включение в экзаменационные билеты задач по математике, физике или экономике не рекомендуется, поскольку для их решения требуются соответствующие знания, выходящие за рамки курса информатики.
Основнойсложностью организации экзаменов по информатике является необходимость отладки программ и получения результатов на ЭВМ при разнообразии языков программирования -Бейсик,Паскаль, Си, Фортран, изучаемых в вузах и школах. В силу этих причин приводимые здесь формулировки задач носят содержательный характер, независимый от языков программирования и используемых ЭВМ.
Основной технической трудностью при решении экзаменационных задач на ЭВМ являются вопросы организацииввода исходных данных, имеющих существенные различия в используемых языках программирования, что также отражается на формулировках и условиях задач.
Существуюттри основных общих способа организации ввода исходных данных в персональных ЭВМ, имеющихся в таких языках программирования как Бейсик, Паскаль, Си и Фортран. Рассмотрим их особенности и недостатки.
П е р в ы й с п о с о б - ввод исходных данных с клавиатуры ЭВМ. Этот способ может быть реализован на любых персональных ЭВМ с помощью любого языка программирования. Однако здесь весьма существенен порядок ввода данных, который должен явно указываться в условиях задач.
В т о р о й с п о с о б - запись исходных данных в файлах на магнитных дисках. Это способ может быть реализован не на всех персональных ЭВМ и не во всех языках программирования. К тому же не во всех действующих учебниках по информатике имеются примеры решения задач с вводом исходных данных из файлов на магнитных дисках.
Дополнительнымнедостатком этого способа является необходимость описания в программах форматов вводимых данных, что полностью отсутствует в учебниках по информатике. Для разрешения этих проблем приходится программировать форматный ввод, что приводит к дополнительным ошибкам как в программах, так и в данных.
Т р е т и й с п о с о б - наиболее удобный для отладки программ на персональных ЭВМ - описание исходных данных внутри текста программ в виде присваивании или операторовdata на языке Бейсик. Этот способ описания данных приведен в настоящем учебном пособии, изложен во всех школьных учебниках по информатике и известен всем школьникам, изучавшим информатику в школах.
Однако этот способ, характерный и удобный для диалоговых программ, отсутствует в профессиональных языках программирования таких как Паскаль, Си, Фортран, изучение которых выходит за рамки школьных учебников. По этой причине в формулировках задач по программированию, ориентированных на учащихся с углубленным изучением информатики, используется форматный способ ввода, принятый для професссиональных языков программирования.
Здесь впримерах программ решения экзаменационных задач используется самый простой и наиболее удобный для отладки программ способ организации ввода тестовых данных в виде операторов data на языке Бейсик. Однако формулировки задач приводятся так, чтобы исходные данные могли вводиться всеми тремя указанными выше способами.
Рассмотримобразцы решения экзаменационных задач с примерами составления как алгоритмов, так и сценариев диалога. Использование сценариев диалога и является тем средством, которое уравнивает все используемые на персональных ЭВМ языки программирования и позволяет экзаменующимся избегать ошибок ввода-вывода данных, характерных для профессиональных языков программирования.
Составление сценариев диалога позволяет до составления алгоритмов предусмотреть порядок ввода исходных данных и реакции программ на самые различные входные ситуации, которые будут проверяться при тестировании на ЭВМ, и тем самым защитить программу и себя от ошибок в исходных данных.
В качествеосновного языка иллюстраций и примеров программ здесь и далее используется язык Basic для компьютеров IВМ PC как из-за удобств описания входных данных, так и из удобств отладки программ на Бейсике на персональных ЭВМ.
Многолетняяпрактика проведения экзаменов по информатике на ЭВМ показала, что отладка программ на Бейсике стабильно завершается на ЭВМ в два раза быстрее, чем на более «мощных» языках, таких как Паскаль, Си или Фортран, что весьма существенно при жестких ограничениях времени на экзаменах.
Задача 1. «Информационно-логическая».
Составить алгоритм и программу выбора самого легкого по весу ученика по данным из таблицы, содержащей сведения о фамилиях, именах, росте и весе учеников.
| фамилия | имя | рост | вес | пол |
| Иванов | Вова | муж | ||
| Петрова | Катя | жен | ||
| Сидоров | Миша | муж |
Разработку программы решения данной задачи проведем с составления сценария диалога с ЭВМ, что существенно упрощает отладку и работу с программой при решении тестовых задач.
Сценарий
ученики:
 | | |
<фам> <имя> <вес> <рост> <пол> *
… … …
самый легкий ученик:
<фам> <имя> <вес>
отсутствует
ПрограммаАлгоритм
' выбор самого легкого ученика алг «выбор самого легкого ученика»
сls ' нач
? «ученики:» ' вывод («ученики:»)
vs = 0 ' vs = 0
do ' цикл
read fm$, nm$, r, v, pl$ ' ввод fmS, nm$, r, v, pl$
if fm$ = «» then exit do ' если fm$ = «» то выход
fm$, nm$, r, v, pl$ ' вывод fm$, nm$, r, v, pl$
if р1$=»муж» then ' если pl$ = «мyж» то
if vs = 0 then ' если vs = 0 то
vs = v ' vs = v
fs$ = finS: ns$ = nm$ ' fs$ = fin$: ns$ = nm$
elseif v < vs then ' инес v < vs то
vs = v ' vs = v
fs$ = fm$: ns$ = nm$ ' fs$ =fm$: ns$ = nm$
end if ' кесли
end if ' кесли
loop ' кцикл
? «самый легкий ученик:» ' вывод («самый легкий ученик:»)
if vs = 0 then ' если vs = 0 то
? «отсутствует» ' вывод («отсутствует»)
elseif vs > 0 then ' инес vs > 0 то
? fs$, ns, vs ' вывод (fs$, ns, vs)
end if ' кесли
end ' кон
data «Иванов», «Вова», 160, 85, «муж»
data «Петрова», «Катя», 167, 67, «жен»
data «Сидоров», «Миша», 180, 80, «муж»
data «», «», 0, 0, «»
Отметим, что при использовании языка Basic тексты программ и описания алгоритмов полностью идентичны друг другу и по форме и по содержанию. Можно сказать, что текст программы на Бейсике получается переводом русских слов и словосочетаний на язык Бейсик и наоборот.
Задача 2. «Экономическая».
Составить алгоритм и программу определения общей стоимости промышленных товаров по данным из таблицы:
| товар | тип | цена | кол-во |
| ананасы | прод | ||
| утюги | пром | ||
| сахар | прод |
Разработку алгоритма и программы начнем с составления сценария диалога, учитывая возможность отсутствия в таблице требуемых исходных данных.
Сценарий
промышленные товары
| |  |
отсутствуют
 | | |
<товар> <цена> <кол> <стоим> *
… … …
общая стоимость = <sum>
Программа Алгоритм
' стоимость промтоваров ' алг «стоимость промтоваров»
сls ' нач
? «промтовары:» ' вывод («промтовары:»)
n = 0: sum = 0 ' п = 0: sum = 0
do ' цикл
read tv$, tp$, сn, kl ' ввод tv$, tp$, сn, kl
if tv$ = «» then exit do ' если tv$ = «» то выход
if tp$ = «пром» then ' если tp$ = «пром» то
n = n + 1 ' n =n + 1
st = cn*kl ' st = cn *kl
? tv$, en; kl; st ' вывод (tv$, en, kl, st)
sum = sum + st ' sum = sum + st
end if ' кесли
loop ' кцикл
if n = 0 then ' если n = 0 то
? «отсутствуют» ' вывод («отсутствуют»)
else ' иначе
? «общая cтoимocть=»,sum ' вывод(«общая стоимость=», sum)
end if ' кесли
end ' кон
data «сахар», «прод», 6000, 20
data «утюги», «пром», 60000, 3
data «книги», «пром», 4000, 30
data «», «», 0, 0
Рассмотрим в качестве иллюстрациипримеры решения экзаменационных задач в МЭСИ - Московском государственном университете экономики, статистики и информатики. Этот университет одним из первых в 1991 году ввел вступительные экзамены по информатике и стал лидером в дистанционном образовании среди государственных вузов Российской Федерации.
Заданиена экзаменах в МЭСИ состоит из пяти задач. Первая задача по системам счисления. Вторая задача - на алгебру логики. Третья задача - тест или анализ блок-схемы. Четвертая и пятая задача - задача на составление алгоритмов и программ.
Первые три задачи в экзаменационных билетах МЭСИ по сложности оцениваются на два балла, а четвертая и пятая задача - на четыре и пять баллов. Положительную оценку на экзамене получает та работа, в которой набрано не менее 8 баллов.
Таким образомподсчет баллов показывает, что в МЭСИ для получения положительной оценки на экзаменах по информатике необходимо решить хотя бы одну задачу на составление программ, а решение задач на составление двух программ - гарантирует на экзамене положительную оценку.
В виду указанной особенности вступительных экзаменов по информатике в МЭСИ разберем примеры решения задач на составление программ, используя для описания алгоритмов псевдокод, а не блок-схемы, как это делается в учебниках МЭСИ.
Задача 1. Написать программу на любом языке программирования согласно следующему условию.
Дана целочисленная матрица А размера M´N, где M,N - заданные натуральные числа. Найти количество столбцов матрицы, содержащих одни нулевые элементы.
Пример матрицы:
Для представления матрицы в программе на языке Бейсик можно использовать операторы data, в первой строке которых указывается размерность матрицы:
Data 5
Data 1, 0, 1, 0, 0
Data 0, 1, 0, 0, 0
Data 0, 0, 1, 0, 0
Data 0, 1, 0, 0, 0
Data 0, 0, 0, 0, 0
Для вывода исходных данных и результатов их обработки можно воспользоваться следующим сценарием:
Матрица А<n><n>:
<а11> ... <a1n>
… … …
<anl> … <ann>
Число нулей в столбцах:
<d1> ... <dn>
Решением поставленной задачи на ЭВМ можно получить с помощью следующего алгоритма и программа на языке Бейсик. Обратите внимание в программе используются массивы переменной длины, которая определяется при вводе размеров матрицы А:
' подсчет нулевых столбцов ' алг «подсчет нулевых столбцов»
' в квадратной матрице Ann ' нач
read n ' чтение(п)
dim A(n,n), D(n) ' массивы А(1:п,1:п), D(1:n)
print «Матрица A»;n;n;«:» ' вывод («Матрица А»;п;п; «:»)
for k = 1 to n ' от k = 1 до п цикл
for 1 =1 to n ' от l =1 до п цикл
read A(k,l) ' чтение A(k,l)
print A(k,l) ' вывод A(k,l)
next 1 ' кцикл
next k ' кцикл
for k = 1 to n ' om k= 1 до п цикл
D(k) = 0 ' D(k) = 0
for 1 = 1 to n ' от l=1 до п цикл
if A(k, l) = 0 then ' если A(k, l) = 0 то
D(k) = D(k) + 1 ' D(k) = D(k) + 1
end if ' кесли
next 1 ' кцикл
print D(k); ' вывод D(k);
next k ' кцикл
end ' кон
Задача 2. Дана строка символов. Распечатать все слова нечетной длины, отличные от второго слова.
(В этой задаче«словом» называется группа символов, разделенная с одной или обеих сторон одним или несколькими пробелами и не содержащую внутри себя пробелов.)
Пример строки
Дата добавления: 2016-04-06; просмотров: 643;