В первой строке входных данных задаётся количество чисел N (3 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 3, в которых произведение элементов кратно 13.
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
Пояснение. Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 26·5, 26·4, 26·13, 2·4, 2·13, 3·13. Из них на 13 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Выпуск 7. Закрепляем описание операций — входные и выходные данные.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени, –
3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
| Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла) |
| Произведение двух чисел делится на 13, если хотя бы один из сомножителей делится на 13. При вводе чисел можно подсчитывать количество чисел, кратных 13, не считая 3 последних. Обозначим их n 13. Примечание для проверяющего. Сами числа, кроме 3 последних, при этом можно не хранить. Очередное считанное число будем рассматривать как возможный правый элемент искомой пары. Если очередное считанное число делится на 13, то к ответу следует прибавить количество чисел до него, не считая 3 последних (включая считанное). Если очередное считанное число на 13 не делится, то к ответу следует прибавить n 13. Чтобы построить программу, эффективную по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используются значения, находящиеся на 3 элемента ранее, достаточно хранить только 3 последних элемента или информацию о них. Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC) |
Неделя 1: 2 Что из себя представляет любая программа; Алгоритм, входные и выходные данные
| Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти |
| const s = 3; var n: longint; a: array[1..s] of longint; a_: longint; n13: longint; cnt: longint; i, j: longint; begin readln(n); for i:=1 to s do readln(a[i]); cnt:= 0; n13:= 0; for i:= s + 1 to n do begin if a[1] mod 13 = 0 then n13:= n13 + 1; readln(a_); if a_ mod 13 = 0 then cnt:= cnt + i — s else cnt:= cnt + n13; for j:= 1 to s — 1 do a[j]:= a[j + 1]; a[s]:= a_ end; writeln(cnt) end. |
| Комментарии для проверяющего 1. При таком решении хранятся только последние 3 прочитанных элемента. Таким образом, используемая память не зависит от длины последовательности. Время обработки очередного числа фиксировано, т.е. не зависит от длины последовательности. Поэтому при увеличении длины последовательности в k раз время работы программы увеличивается не более чем в k раз. Таким образом, приведённая выше программа эффективна как по времени, так и по используемой памяти. Это решение оценивается в 4 балла. В таких версиях Паскаля, как PascalABC или Delphi, тип longint может быть заменён на тип integer. В большинстве версий языков CC++ также можно использовать тип int. Программа может быть и ещё более эффективной, если на каждом шаге не сдвигать элементы вспомогательного массива, а записывать i -й считанный элемент в элемент с индексом i mod 3 (Паскаль) или i % 3 (Python), ведя нумерацию обоих индексов с нуля. Учёту подлежит элемент с этим же индексом (именно он находится на расстоянии s от i -го и будет заменён на него). Кроме того, при нумерации индексов элементов с нуля меняется одна из формул для подсчёта. Такая программа на языке Python приведена ниже (пример 2). Все подобные программы оцениваются, исходя из максимального балла – 4 (см. критерии). Вместо последних 3 элементов можно хранить и 3 счётчика: количество делящихся на 13 среди всех считанных чисел, всех считанных чисел без последнего, всех считанных чисел без 2 последних – и также сдвигать их после очередного шага. Такая программа приведена на языке С++ (пример 3). В этом же примере вместо вспомогательного массива длиной 3 используются 3 переменные. 2. Возможно решение, основанное на описанных идеях, однако предварительно сохраняющее элементы последовательности в массив. Такое решение эффективно по времени, но неэффективно по памяти. Оно оценивается, исходя из максимального балла – 3 (см. критерии). 3. Решение, неэффективное ни по времени, ни по памяти, запоминает входную последовательность в массиве, после чего явно перебирает все возможные пары. Такое решение оценивается, исходя из максимального балла – 2 (см. критерии). |
| Пример 2. Программа на языке Python. Программа эффективна по времени и памяти |
| s = 3 a = [0]*s n = int(input()) for i in range(s): a[i] = int(input()) cnt = 0 n13 = 0 for i in range(s, n): k = i % s if a[k] % 13 == 0: n13 = n13 + 1 a_ = int(input()) if a_ % 13 == 0: cnt = cnt + i — s + 1 else: cnt = cnt + n13 a[i % s] = a_ print(cnt) |
| Пример 3. Программа на языке С++. Программа эффективна по времени и памяти |
| #include using namespace std; int main() < int s = 3; //требуемое расстояние между элементами int n; int n1 = 0, n2 = 0, n3 = 0; //хранение последних s счетчиков int a_; // очередное значение int cnt; // количество искомых пар cin >> n; cnt = 0; for (int i = 0; i < n; ++i) < cin >> a_; // считано очередное значение if (i >= s) < if (a_ % 13 == 0) cnt += i — s + 1; else cnt += n3; >//сдвигаем элементы счетчиков n3 = n2; n2 = n1; //обновляем счетчик кратных 13 if (a_ % 13 == 0) n1 += 1; > cout |
| Указания по оцениванию | Баллы |
| Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бо́льшая из двух оценок. Описание алгоритма решения без программы оценивается в 0 баллов. | |
| Программа правильно работает для любых входных данных произвольного размера при условии исправления в ней не более трёх синтаксических ошибок из приведённого ниже списка допустимых ошибок. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано, пропущено или написано лишнее зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, не допустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку | 4 |
| Не выполнены условия, позволяющие поставить 4 балла. Программа работает правильно для любых входных данных произвольного размера при условии исправления в ней не более пяти синтаксических ошибок из приведённого в критериях на 4 балла списка и не более одной ошибки из приведённого ниже списка содержательных ошибок. Время работы пропорционально количеству введённых чисел. Допускается наличие не более одной содержательной (не являющейся синтаксической) ошибки следующих видов: 1) допущена ошибка при вводе данных, например не считывается значение N,или числа могут быть считаны, только если будут записаны в одной строке через пробел; 2) неверная инициализация или её отсутствие там, где она необходима; 3) используется неверный тип данных; 4) использована одна переменная (или константа) вместо другой; 5) используется один знак операции вместо другого; 6) используется одно зарезервированное слово языка программирования вместо другого; 7) неверно используется условный оператор, например else относится не к тому условию; 8) отсутствует вывод ответа, или выводится значение не той переменной; 9) выход за границу массива; 10) неверно расставлены операторные скобки. 3 балла также ставится за программу, в которой нет содержательных ошибок, но используемая память зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных) | 3 |
| Пример 4. Программа на языке Паскаль. Программа эффективна по времени и неэффективна по памяти |
| const s = 3; var n: longint; a: array[1..1000] of longint; n13: longint; cnt: longint; i, j: longint; begin readln(n); for i:=1 to s do readln(a[i]); cnt:= 0; n13:= 0; for i:= s + 1 to n do begin readln(a[i]); if a[i — s] mod 13 = 0 then n13:= n13 + 1; if a[i] mod 13 = 0 then cnt:= cnt + i — s else cnt:= cnt + n13; end; writeln(cnt) end. |
| Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает верно, эффективно по времени при условии исправления не более трёх содержательных ошибок, описанных в критериях на 3 балла, и не более девяти синтаксических ошибок, указанных в критериях на 4 балла. 2 балла также ставится за корректное переборное решение, в котором все числа сохраняются в массиве (или другой аналогичной структуре), рассматриваются все возможные пары и подсчитывается количество подходящих произведений с учётом допустимого расстояния между ними. Пример фрагмента соответствующей программы на языке Паскаль: cnt:= 0; for i:= 1 to N — s do for j:= i + s to N do if a[i] * a[j] mod 13 = 0 then cnt:= cnt + 1; writeln(cnt) Не допускается выставление 2 баллов за реализацию переборного алгоритма, содержащего любую логическую ошибку, например ошибку, приводящую к выходу индексов за границы массива, или ошибку, когда учитываются произведения вида a[i]*a[i], или пары считаются дважды, или неверно учитывается расстояние между индексами элементов пары | 2 |
| Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. При этом в программе должны присутствовать два обязательных элемента, возможно, реализованных с ошибками: 1) проверка делимости (в явной или неявной форме) элементов входной последовательности на заданное число; 2) проверка или учёт того, что расстояние между элементами искомой пары должно быть не меньше заданного | 1 |
| Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | |
| Максимальный балл | 4 |
Задание 27. Вариант 2
На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности ai и aj, такие что i < j и ai > aj (первый элемент пары больше второго, i и j – порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник: studopedia.ru
Описание входных и выходных данных
Методические указания предназначены для студентов специальностей «Электрооборудование автомобилей и тракторов» и «Электрооборудование и электрохозяйство предприятий».
Методические указания содержат краткие теоретические сведения по языку программирования С/С++, рекомендации и примеры выполнения типовых лабораторных работ по дисциплине «Программирование».
Составитель Пивнев В.В., к.т.н., доцент
1.ОБЩИЕ ТРЕБОВАНИЯ К СОДЕРЖАНИЮ ОТЧЕТОВ
1. Постановка задачи.
2. Описание входных и выходных данных.
4. Описание алгоритма.
5. Блок-схема алгоритма.
6. Текст программы.
7. Анализ результатов и выводы.
Как минимум, первые три пункта отчета следует подготовить и обсудить с преподавателем до написания текста программы. При этом в постановку задачи, в дополнение к тексту из настоящих методических указаний, следует внести описание реакции будущей программы на некоторые неоговоренные в задании значения исходных данных, в том числе — на некорректные с точки зрения постановки задачи значения.
Во втором разделе для входных и выходных параметров необходимо ввести символические обозначения (имена) и привести описания типов этих имен в терминологии языка С/C++ (Pascal), а в третьем — перечислить несколько вариантов значений входных параметров с соответствующими им значениями выходных, вычисленными вручную.
Основное требование к описанию алгоритма заключается в том, чтобы оно было более подробным описанием процесса решения задачи, чем постановка задачи из п.1, но менее подробным, чем текст программы. В описании должна найти отражение основная идея решения поставленной задачи.
Запись блок-схемы должна соответствовать ГОСТ 19.002-80 «Схемы алгоритмов и программ. Правила выполнения» и ГОСТ 19.003-80 «Схемы алгоритмов и программ. Обозначения условные и графические».
Текст программы необходимо снабдить комментариями.
Собственно решение задачи оформить в виде процедур/функций, если это задано, параметрами которых сделать все, перечисленное в п. 2 отчета. Такая процедура/функция не должна содержать операций ввода-вывода, если это не требуется в постановке задачи. Ввод исходных данных и вывод результатов выполняется в (основной) головной программе, так называемом имитаторе внешней среды, в которой может эксплуатироваться процедура.
В заключительном разделе должен быть приведен критический анализ проделанной работы с указанием достоинств и недостатков разработанного алгоритма решения задачи и его программной реализации, а также — количественные характеристики программы: ее объем, объем дополнительной памяти, привлекаемой для реализации алгоритма, время работы программы, измеренное в количестве выполняемых типичных операций в зависимости от размеров исходных данных.
1. Пример отчета о выполнении лабораторной работы №1
ЛАБОРАТОРНАЯ РАБОТА № 1
На тему: «Вычисление смешанного выражения»
1. Постановка задачи. Вычислить заданное смешанное арифметическое выражение для данных в форматах float (переменные a,b) и int (остальные переменные: с, d).
2.Описание входных и выходных данных
Исходные данные: a, b, c, d.
Результат: у – значение арифметического выражения.
| Исходные данные: a= b= c= d= | |||||
| -2 | |||||
| -1 | |||||
| Выходные данные: у= | -0.4747 | Нет решений | Нет решений | Нет решений | 0.061795 |
4. Описание алгоритма.
Из условия задачи следует, что значение у зависит от значения переменных: a, b, c, d, которые могут принимать любые значения из интервала . Однако, не при всех значениях исходных данных смешанное выражении может быть вычислено, например, когда знаменатель b и равен нулю.
Решение задачи можно разбить на несколько этапов:
1. Вводим исходные данные a, b, c, d.
2. Определяем, область допустимых значений аргументов a, b, c, d.
3. Вычисляем заданное смешанное выражение
5. Блок-схема решения задачи.
Источник: megaobuchalka.ru
Описание входных и выходных данных
a – переменная для ввода исходных данных типа integer.
b – переменная для ввода исходных данных типа integer.
c – переменная для ввода исходных данных типа integer.
Листинг программы
procedure TForm1.Button1Click(Sender: TObject);
if (sqr(a)+sqr(b)=sqr(c)) or (sqr(b)+sqr(c)=sqr(a)) or (sqr(a)+sqr(c)=sqr(b)) then
ShowMessage(‘Треугольник является прямоугольным’);
ShowMessage(‘Треугольник не является прямоугольным’);
Постановка задачи
Цель работы: Дано целое число в диапазоне 1-7. Вывести строку – название дня недели, соответствующее данному числу (1 – «понедельник», 2 – «вторник» и т. д.).
Описание алгоритма решения задачи
Описание входных и выходных данных
a – переменная для ввода исходных данных типа integer.
Листинг программы
procedure TForm1.Label2Click(Sender: TObject);
Постановка задачи
Цель работы: Дан номер месяца – целое число в диапазоне 1-12 (1 – январь, 2 – февраль и т. д.). Определить количество дней в этом месяце для не високосного года.
Описание алгоритма решения задачи
Описание входных и выходных данных
x – переменная для ввода исходных данных типа integer.
y – переменная для вывода полученных данных типа string.
Листинг программы
procedure TForm1.btn1Click(Sender: TObject);
if (x=1) or (x=3) or (x=5) or (x=7) or (x=8) or (x=10) or (x=12) then
if (x=4) or (x=6) or (x=9) or (x=11) then
Задание №3. Циклические алгоритмы
Постановка задачи
Цель работы: Вычислить значение функции y = 4x^3– 2x^2+ 5 для значений х, изменяющихся от –3 до 1 с шагом 0,1.
Описание алгоритма решения задачи
| X=-3 |
| начало |
| Y:=4x^3– 2x^2+ 5; |
| X>1 |
| X+0.1X+0.1X+0.1 |
u oLPAI2QZCPlxjLT0OMtK6oJepmEN0xXEeGGqGOKZVMMZmSizVycIMkjj+7KP3RhPD6qXUN2jXhaG 2cW/hocG7GdKOpzbgrpPG2YFJeqVQc1n48kkDHo0JtOLDA176ilPPcxwhCqop2Q4Ln38HENl19ib WkbdQhMHJnvOOI9Rzv3fCQN/aseoPz988RsAAP//AwBQSwMEFAAGAAgAAAAhAFMHcGDeAAAACQEA AA8AAABkcnMvZG93bnJldi54bWxMj9FOg0AQRd9N/IfNmPhi7AK1VChLoyYaX1v7AQM7BVJ2l7Db Qv/e8ck+3szJnXOL7Wx6caHRd84qiBcRCLK1051tFBx+Pp9fQfiAVmPvLCm4kodteX9XYK7dZHd0 2YdGcIn1OSpoQxhyKX3dkkG/cANZvh3daDBwHBupR5y43PQyiaJUGuwsf2hxoI+W6tP+bBQcv6en VTZVX+Gw3r2k79itK3dV6vFhftuACDSHfxj+9FkdSnaq3NlqL3rOq2TJqIIkyUAwkMRL3lIpSOMM ZFnI2wXlLwAAAP//AwBQSwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAA AAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAA AAAAAAAAAC8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAAIQCYsZW6OgIAACkEAAAOAAAAAAAA AAAAAAAAAC4CAABkcnMvZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQBTB3Bg3gAAAAkBAAAPAAAA AAAAAAAAAAAAAJQEAABkcnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAnwUAAAAA » stroked=»f»>
| нет |
| да |
| Y |
| Конец |
Описание входных и выходных данных
x – переменная для ввода исходных данных типа real.
y – результат вычисления выражения типа real.
Листинг программы
procedure TForm1.Button1Click(Sender: TObject);
Источник: stydopedia.ru