- •Оценка эффективности алгоритмов
- •Целочисленная арифметика
- •Дано натуральное число. Выяснить является ли оно палиндромом, то есть читается справа налево и слева направо одинаково
- •Дано натуральное число. Выяснить соотношение между количествами двоек и пятерок в этом числе
- •Найти самую большую и самую маленькую цифры данного натурального числа
- •Выяснить образуют ли цифры натурального числа возрастающую последовательность
- •Формат выходного файла
- •Формат входного файла
- •Формат выходного файла
- •Формат входного файла
- •Формат входного файла
- •Формат выходного файла
- •Длинная арифметика
- •Выходные данные
- •Задачи Задача 52 Иностранные земли
- •Входные данные.
- •Выходные данные.
- •Формат входного файла
- •Формат выходного файла
- •Задачи Задача 56 Уравнение
- •Решение
- •Одномерные массивы
- •Базовые задачи на массивы
- •Задача 15 Сокращение одночленов
- •Входные данные:
- •Задача 16 Школьный субботник
- •Входные данные:
- •Входные данные:
- •Выходные данные:
- •Примеры
- •Задача 27 Решение систем линейных уравнений на Pascal
- •Двумерные массивы
- •Описание массива
- •Способы создания массива
- •Задачи:
- •Задача 5 Малыш играет в "Морской бой 2" Малыш играет в "Морской бой". Поле для игры представляет собой квадрат
- •Входные данные
- •Выходные данные
- •Задача 26 Шарик в лабиринте
- •Примечание
- •Задача 27 Блохи
- •В первой строке входного файла Input.Txt находится 5 чисел, разделенных пробелом: n, m, s, t, q.
- •Входные данные
- •Выходные данные
- •Примеры
- •Задача 34 Магический квадрат
- •Формат входного файла
- •Формат выходного файла
- •Входные данные
- •Выходные данные
- •Входные данные
- •Выходные данные
- •Рекурсия
- •Комбинаторика
- •2.5. Генерация комбинаторных объектов
- •Множество всех подмножеств
- •Перестановки
- •Размещения
- •Перестановки с повторениями
- •Сочетания с повторениями
- •Перебор
- •Символ o()
- •Отсечение по времени
- •Рассмотрим несколько олимпиадных задач.
- •Шарик в лабиринте
- •Задача 1. Шарик в лабиринте
- •Задача 3 Цепочка слов
- •Входные данные
- •Выходные данные
- •Примеры
- •Формат входного файла
- •Формат выходного файла
- •Примеры
- •Динамическое программирование
- •Задача 8 Гвоздики
- •Задача 13 Лесенки
- •Задача 18 Свинья-копилка
- •Входные данные
- •Выходные данные
- •Задача 13 Лесенки Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий.
- •Задача 18 Свинья-копилка
- •Формат входного файла:
- •Формат выходного файла:
- •Примеры
- •Решение
- •Входные данные:
- •Выходные данные:
- •Формат входа
- •Формат выхода
- •Задача 39 Лесенка-2
- •Входные данные
- •Выходные данные
- •Примеры
- •Системы счисления
- •Задача 11 Троичная сбалансированная система счисления
- •Алгоритм перевода
- •Процедуры и функции для работы с символами и строками
- •Определить количество слов в строке
- •Получите строковой массив из всех слов данной строки
- •Получите строковой массив из всех слов данной строки и
- •Получите строковой массив из всех слов данной строки и
- •Составьте программу, определяющую, является ли введенное слово изображением числа
- •Введите 2 целых числа. Преобразуйте числа в две строки, объедините их в одну строку и выведите результат на экран.
- •Вычислите длину самого короткого и самого длинного слов в строке
- •Подсчитайте количество букв в каждом слове данной строки
- •Дана строка. Определить количество слов этой строки, в которых есть ровно две буквы «е»
- •Составьте программу, удаляющую все лишние пробелы из введенной строки
- •Напишите программу, сортирующую символы введенной с клавиатуры строки в порядке возрастания их номеров в ascii-таблице. Например, если введено: 'cba', в результате надо получить ‘abc’.
- •В тексте, состоящем из маленьких латинских букв , подсчитайте количество гласных букв
- •Заданы фамилия, имя и отчество учащегося, разделенные пробелом. Напечатайте его фамилию и инициалы.
- •Сложное слово состоит из двух частей одинаковой длины и соединительной гласной. Найдите обе части этого слова.
- •Вычеркните из слова х те буквы, которые встречаются в слове z
- •Подсчитайте число различных букв в слове
- •Даны два слова. Составьте программу, определяющую можно или нет из букв слова а составить слово в.
- •Даны два слова. Являются ли они анаграммами
- •Является ли данная строка палиндромом?
- •Задача 4. Сокращение одночленов
- •Входные и выходные данные
- •Это чисто техническая задача на аккуратное программирование.
- •Задача 6 Текст
- •Входной файл Input.Txt в первой строке входного файла находится 5 чисел,разделенных пробелом: n, m, s, t, q.
- •Бинарные деревья. Алгоритм HeapSort
- •Поиск в глубину в графе
- •Алгоритм Флойда поиска кратчайших расстояний и кратчайших путей
- •Бинарные деревья. Алгоритм HeapSort
- •Графызадачи Двоичная куча
- •Примеры задач, которые решаются с помощью двоичной кучи
- •Поиск максимального потока методом Форда-Фалкерсона на Pascal
- •Графызадачи Поиск сильно связанных компонент на Pascal
- •Поиск точек раздела, мостов и двусвязных компонент
- •Идеи алгоритмов
- •Точки раздела
- •Двусвязные компоненты
- •Задача 21 Моя Столица
- •Вычислительная геометрия
- •3. Уравнение прямой 2
- •4. Уравнение прямой проходящей через точку м(х0у0)
- •Формат входного файла
Задача 27 Решение систем линейных уравнений на Pascal
const maxn = 1000;
var i,j,k,n,buf1,kmax:longint;
uf2,max:extended;
a:array[1..maxn,1..maxn]of extended;
x,y,b:array[1..maxn]of extended;
p:array[1..maxn]of longint;
begin
read(n);
for i:=1 to n do begin
for j:=1 to n do read(a[i,j]);
read(b[i]);
end;
for i:=1 to n do p[i]:=i;
for k:=1 to n do begin
max:=0;
for i:=k to n do if abs(a[i,k])>max then begin
max:=abs(a[i,k]);
kmax:=i;
end;
if max=0 then halt;
buf1:=p[k]; p[k]:=p[kmax]; p[kmax]:=buf1;
for i:=1 to n do begin
buf2:=a[k,i]; a[k,i]:=a[kmax,i]; a[kmax,i]:=buf2;
end;
for i:=k+1 to n do begin
a[i,k]:=a[i,k]/a[k,k];
for j:=k+1 to n do a[i,j]:=a[i,j]-a[i,k]*a[k,j];
end;
end;
for i:=1 to n do begin
y[i]:=b[p[i]];
for j:=1 to i-1 do y[i]:=y[i]-a[i,j]*y[j];
end;
for i:=n downto 1 do begin
x[i]:=y[i];
for j:=i+1 to n do x[i]:=x[i]-a[i,j]*x[j];
x[i]:=x[i]/a[i,i];
end;
for i:=1 to n do writeln(x[i]:0:5);
end.
задачинамассивы
Задача 28 Олимпиада
Напишите программу, генерирующую по результатам отдельных соревнований итоговый рейтинг всех стран. В первой строке входного файла содержатся целое число – количество соревнований N (0<N<=50). Далее следует N строк, каждая строка имеет вид:
GGG SSS BBB
где GGG, SSS, BBB – это трехбуквенные коды стран (3 прописных латинских буквы), получивших соответственно золотую, серебряную и бронзовую медали. Коды стран разделены одним пробелом. Например, строка ”RUS KOR USA” означает, что в данном виде спорта страна с кодом RUS – получила золотую медаль, KOR – серебряную и USA – бронзовую. В результатах соревнований появляется не более 50 различных кодов стран.
В выходной файл вывести итоговый рейтинг всех стран в формате:
CCC G S B
где CCC – это трехбуквенный код страны, G – число золотых медалей, завоеванных этой страной, S – число серебряных, B – число бронзовых. Страны нужно выводить в порядке убывания числа золотых медалей, при равенстве числа золотых – в порядке убывания числа серебряных медалей, при равенстве числа золотых и серебряных – в порядке убывания числа бронзовых медалей, а если и их количество одинаково, то страны должны быть выведены в алфавитном порядке по их трехбуквенному коду. Все данные разделены одним пробелом.
Пример:
Input.txt |
Output.txt |
4 ITA JPN AUS KOR TPE UKR KOR KOR GBR KOR CHN TPE |
KOR 3 1 0 ITA 1 0 0 TPE 0 1 1 CHN 0 1 0 JPN 0 1 0 AUS 0 0 1 GBR 0 0 1 UKR 0 0 1 |
Эта задача на технику программирования.
program Project2;
var res:array[1..3,1..100]of integer;
ctr:array[1..100]of string;
s,cur:string;
i,j,n,ind,kol:integer;
procedure swap(var a,b:integer); обмен содержимым двух переменных
var p:integer;
begin
p:=a; a:=b; b:=p;
end;
function find(s0:string):integer; поиск страны в массиве
var i0:integer;
begin
for i0:=1 to kol do
if s0=ctr[i0] then begin
result:=i0;
exit;
end;
result:=-1;
end;
begin
assign(input,'input.txt'); reset(input);
assign (output,'output.txt'); rewrite(output);
readln(n); считываем количество строк
kol:=0;
for i:=1 to n do перебираем строки
begin
readln(s); считываем очередную строку
cur:=copy(s,1,3); получаем название страны
ind:=find(cur); находим ее индекс в массиве
if ind=-1 then если такой страны нет
begin inc(kol); ind:=kol; ctr[ind]:=cur; end; считаем ее и добавляем в массив
delete(s,1,4); стираем 4 символа из строки s
inc(res[1,ind]); прибавляем одну золотую медаль
cur:=copy(s,1,3); получаем название следующей страны
ind:=find(cur);
if ind=-1 then
begin inc(kol); ind:=kol; ctr[ind]:=cur; end;
delete(s,1,4);
inc(res[2,ind]); прибавляем одну серебряную медаль
cur:=copy(s,1,3); получаем название следующей страны
ind:=find(cur);
if ind=-1 then
begin inc(kol); ind:=kol; ctr[ind]:=cur; end;
inc(res[3,ind]); прибавляем одну бронзовую медаль
end;
for i:=1 to kol-1 do сортируем
for j:=i+1 to kol do
if (res[1,i]<res[1,j])or
((res[1,i]=res[1,j])and(res[2,i]<res[2,j]))or
((res[1,i]=res[1,j])and(res[2,i]=res[2,j])and(res[3,i]<res[3,j]))or
((res[1,i]=res[1,j])and(res[2,i]=res[2,j])and(res[3,i]=res[3,j])and(ctr[i]>ctr[j]))then
begin
swap(res[1,i],res[1,j]);
swap(res[2,i],res[2,j]);
swap(res[3,i],res[3,j]);
s:=ctr[i];
ctr[i]:=ctr[j];
ctr[j]:=s;
end;
for i:=1 to kol do выводим результат
begin
write(ctr[i],' ',res[1,i],' ',res[2,i],' ',res[3,i]);
writeln;
end;
close(input); close(output);
end.
задачинамассивы
К оглавлению
