Методы решения олимпиадных задач по программированию
Исследование основных методов написания простых программ. Изучение основных подходов к решению и анализу алгоритмов, выбору оптимальных методов решения олимпиадных задач по программированию. Составление программ обработки данных общего предназначения.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | учебное пособие |
| Язык | русский |
| Дата добавления | 11.09.2014 |
| Размер файла | 176,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Решение
{$APPTYPE CONSOLE}
uses
SysUtils;
Function Min(a,b,c:word):word;
var
temp:word;
begin
if a<b then temp:=a
else temp:=b;
if temp<c then min:=temp
else min:=c;
end;
var
f:text;
n,m,i,j:byte;
a:array[0..21,0..21] of word;
res:word;
begin
assign(f,'Path.inp');
reset(f);
readln(f,n,m);
for i:=1 to n do
for j:=1 to m do
read(f,a[i,j]);
close(f);
for i:=1 to n do
begin
a[i,0]:=65535;
a[i,m+1]:=65535;
end;
for j:=0 to m+1 do
a[0,j]:=0;
for i:=1 to n do
for j:=1 to m do
a[i,j]:=min(a[i-1,j-1],a[i-1,j],a[i-1,j+1])+a[i,j];
res:=65535;
for j:=1 to m do
if a[n,j]<res then res:=a[n,j];
assign(f,'Path.out');
rewrite(f);
writeln(f,res);
close(f);
end.
Билеты
Ограничение по времени: 1 сек.
Входной файл: Ticket.inp
Выходной файл: Ticket.out
За билетами на футбольный матч перед вами выстроилась очередь из N человек. На всю очередь работает только одна касса, поэтому продажа билетов шла очень медленно. Вы быстро заметили, что, как правило, продажа нескольких билетов в одни руки идет быстрее, чем когда эти билеты продаются по одному. Поэтому вы предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех. Однако для борьбы с перекупщиками кассир продавала не более 2 билетов в одни руки, поэтому договориться могли лишь 2 стоящих подряд человека.
Известно, что на продажу i-му человеку из очереди 1-го билета кассир тратит Ai секунд, а на продажу 2-х билетов - Bi секунд.
Билеты на группу всегда покупает 1й человек. Никто также не покупает лишних билетов.
Вам необходимо определить минимальное время, за которое могут быть обслужены N стоящих перед вами болельщиков.
Входные данные для программы (текстовый файл Ticket.inp)
Первая строка входного файла содержит N (N <= 1000) - число покупателей, затем идут N строк, содержащие 2 числа Ai и Bi (1 <= Ai, Bi <= 20 ) - время в минутах.
Результат работы программы (текстовый файл Ticket.out)
Выведите в выходной файл минимальное время в минутах, за которое могли бы быть обслужены N стоящих перед вами болельщиков.
Примеры входных данных и результатов
|
Файл Ticket.inp |
Файл Ticket.out |
|
|
5 1 2 2 1 2 6 5 2 3 3 |
4 |
|
|
1 5 3 |
5 |
Подсказка:
В первом случае минимальное время в минутах, за которое может быть обслужен 1-й болельщик, составляет 1 минуту.
2 болельщика - 2 минуты.
3 болельщика тоже 2 минуты.
4 болельщика - 7 минут.
И все 5 болельщиков - 4 минуты :).
Решение
{$APPTYPE CONSOLE}
uses
SysUtils;
Function Min(a,b:word):word;
begin
if a<b then min:=a
else min:=b;
end;
var
f:text;
i,n:word;
a,b:array[1..1000] of byte;
mas:array[0..1000] of word;
begin
assign(f,'Ticket.inp');
reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i],b[i]);
close(f);
mas[0]:=0;
mas[1]:=a[1];
for i:=2 to n do
mas[i]:=min(mas[i-1]+a[i],mas[i-2]+b[i-1]);
assign(f,'Ticket.out');
rewrite(f);
writeln(f,mas[n]);
close(f);
end.
Список рекомендованной литературы
1. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.: Пер. с англ.: Уч. пос. Ї М.: Издательский дом “Вильямс”, 2000. Ї 384 с., ил.
2. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. Харьков: Фолио; Ростов н/Д: Феникс, 1997. Ї 368 с.
3. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. Ї М.: Мир, 1989. Ї 360 с., ил.
4. Караванова Т.П. Інформатика: методи побудови алгоритмів та їх аналіз: необчислювальні алгоритми: .: Навч. посіб. для 9-10 кл. із поглибл. вивч. інф-ки - К.: Генеза. - 2006.- 216 с
5. Караванова Т.П. Інформатика: основи алгоритмізації та програмування: 777 задач з рекомендаціями та прикладами: Навч. посіб. для 8-9 кл. із поглибл. вивч. інф-ки - К.: Генеза. - 2006.- 286 с.
6. Керман, Митчел, К. Программирование и отладка в Delphi. Учебный курс. Пер. с англ.. Ї М.: Издательский дом “Вильямс”, 2002, 672 с.: ил. - Парал. тит.англ.
7. Кнут Д. Искусство программирования. Ї М.: Вильямс, 2000
8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001. Ї 960 с., 263 ил.
9. Культин Н.Б., Основы программирования в Delphi 2006 Microsoft .NET Framework-CПб. БХВ-Петербург, 2006 - 487с.:ил.
10. Лавренов С.М. Excel: Сборник примеров и задач. - М.: Финансы и статистика, 2001. - 336 с. : ил. - (Диалог с компьютером)
11. Липский В. Комбинаторика для программистов: Пер. с польск. Ї М.: Мир, 1988. Ї 213 с., ил.
12. Шупруга В.В., Delphi 2006 на примерах CПб. БХВ-Петербург, 2006 - 528с.:ил.
Размещено на Allbest.ru
...Подобные документы
Характеристика предприятия ТОО "Com Sales Group". Составление программ на языке программирования. Составление алгоритмов, разработка численных методов решения задач. Методы откладки программ. Анализ технологии машинной обработки экономической информации.
отчет по практике [1,3 M], добавлен 19.04.2016Разработка алгоритма как конструктивный компонент программирования, не зависящий от особенностей синтаксиса языков программирования и специфики функционирования конкретных ЭВМ. Алгоритм - операциональный подход к программированию. Экономичность алгоритма.
учебное пособие [346,8 K], добавлен 09.02.2009Изучение методов создания диалоговой оболочки отладчика MPI-программ, который войдет в состав системы автоматизации разработки параллельных программ (DVM-системы). Основные подходы к параллельному программированию и созданию пользовательского интерфейса.
курсовая работа [1,5 M], добавлен 14.10.2010Использование информационных технологий для решения транспортных задач. Составление программ и решение задачи средствами Pascal10; алгоритм решения. Работа со средствами пакета Microsoft Excel18 и MathCad. Таблица исходных данных, построение диаграммы.
курсовая работа [749,1 K], добавлен 13.08.2012"Moodle" - модульная объектно-ориентированная динамическая среда обучения, ее использование для разработки систем дистанционного обучения. Общее представление о дистанционном практикуме по программированию. Разработка структуры данных и алгоритмов.
дипломная работа [1,2 M], добавлен 09.11.2016Разработка программы на языке Си++ и осуществление постановки и выбора алгоритмов решения задач обработки экономической информации, создание и редактирование базы данных, сортировка записей по определенному запросу, анализ эффективности обработки данных.
контрольная работа [316,8 K], добавлен 28.08.2012Написание программы вычисления сопротивления электрической цепи, состоящей из двух параллельно и двух последовательно соединенных сопротивлений. Схема машинного алгоритма по условию задачи. Применение операций при написании программ на языке C/C++.
контрольная работа [17,3 K], добавлен 09.11.2010Понятие массива и правила описания массивов в программах на языке С. Рассмотрение основных алгоритмов обработки одномерных массивов. Примеры программ на языке С для всех рассмотренных алгоритмов. Примеры решения задач по обработке одномерных массивов.
учебное пособие [1,1 M], добавлен 22.02.2011Описание программного продукта, решающего задачу по автоматизации сбора данных, связанных с деятельностью кружка по программированию. Изучение и совершенствование навыков программирования на различных языках среди студентов и школьников старших классов.
дипломная работа [418,3 K], добавлен 10.07.2017Особенности решения задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях нелинейного программирования. Общая характеристика классических и числовых методов решения.
дипломная работа [2,4 M], добавлен 20.01.2013Составление блок-схемы и алгоритма программы для решения уравнения с приближенным значением корня по методу Ньютона, расчета приближенного значения интеграла по формуле трапеций, вычисления уравнения длины вектора. Типы формул общего члена суммы.
курсовая работа [41,3 K], добавлен 15.12.2012Исходные данные по предприятию ОАО "Красногорсклексредства". Разработка математических моделей задач по определению оптимальных планов производства продукции с использованием пакетов прикладных программ для решения задач линейного программирования.
курсовая работа [122,5 K], добавлен 16.10.2009Создание схем алгоритмов и составление программы на языке Pascal для вычисления значений заданных функций. Сущность и порядок нахождения значения определенного интеграла. Анализ работы подпрограмм. Разработка тестов для проверки правильности алгоритмов.
контрольная работа [831,0 K], добавлен 24.11.2013Изучение особенностей создания алгоритмов вычислительных задач. Визуальное программирование стандартных компонентов среды программирования Delphi. Технология создания компонента Delphi для решения производственной задачи. Выполнение блок-схемы алгоритма.
курсовая работа [638,0 K], добавлен 30.01.2015Осуществление постановки и выбор алгоритмов решения задач обработки экономической информации; разработка программы для работы с базой данных о маршруте: начало, конец, номер, суммарное количество мест. Поиск маршрутов по названиям конечного пункта.
курсовая работа [2,5 M], добавлен 17.01.2013Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Написание программ для решения различных выражений и задач. При решении каждой задачи предусмотрены: анализ введенных с клавиатуры исходных данных, выведение условия для выхода и вывод результатов. Проиллюстрированы результаты работы каждой программы.
контрольная работа [259,8 K], добавлен 22.05.2010Составление структурных программ для решения практических задач по теме "Целочисленная арифметика". Алгоритм нахождения делителей натурального числа, алгоритм проверки простое ли число, алгоритм Решета Эратосфена. Система программирования Free Pascal.
разработка урока [27,1 K], добавлен 03.09.2014Основные понятия математического линейного программирования. Постановка и методы решения заданий целочисленного и параметрического составления программ. Примеры вычисления задач с параметрами в целевой функции и в свободных членах системных ограничений.
дипломная работа [432,0 K], добавлен 25.10.2010Обзор моделей анализа и синтеза модульных систем обработки данных. Модели и методы решения задач дискретного программирования при проектировании. Декомпозиция прикладных задач и документов систем обработки данных на этапе технического проектирования.
диссертация [423,1 K], добавлен 07.12.2010
