Тема 5: Строки. Элементы лексического и синтаксического разобра
«Печать строк»
Сергей очень любит играть в такую игру: произвольным способом выбирает два натуральных числа
N(1≤N≤100) и M (1≤M≤100).
Создается строка символов, в которых подряд выписываются числа: сначала одна 1, потом две 2, потом три 3 и так далее до N. Например, для N=5 полученная строка такая: 122333444455555. Потом полученная строка записывается в несколько строк по M символов в строке. Последняя строка может быть неполной длинны. Например, предыдущая строка для М=3 будет иметь вид:
Нужно написать программу, которая освободит Сергея от подобного времяпрепровождения.
Входные данные: LINE.DAT в одной строке входного файла заданы два числа N и М, которые не превышают 100 и разделены пробелом.
Выходные данные: LINE.SOLв каждой строке выходного файла должно содержаться по М символов из полученной N строки. Последняя строка может быть неполной.
| LINE.DAT | LINE.SOL |
| 5 3 |
Var
n, m, i, j: byte;{n - количество символов, используемых в строке, m-количество символов в одной строке вывода, i,j - переменные для счетчика цикла}
s, x: string;{s - строка символов, x - очередной символ строки}
Begin
assign(input, 'LINE.dat');{связываем входной файл и файловую переменную}
reset(input);{открываем файл для чтения}
readln(n, m);{считываем входные данные}
close(Input);{закрываем входной файл}
assign(Output,'LINE.sol');{связываем выходной файл и файловую переменную}
rewrite(Output);{открываем файл для записи}
s:='';{обнуляем строку}
fori:=1 ton do{перечисляем цифры для формирования строки}
forj:=1 toi do{перечисляем количество каждой отдельной цифры}
Begin
str(i,x); {переводим цифру в строку}
s:=s+x;{записываем символы в строку}
whileLength(s)>=m do{выводим до тех пор пока длина строки не станет меньшей M}
Begin
writeln(Copy(s,1,m));{копируем и выводим m-символов}
delete(s,1,m);{удаляем в исходной строке m символов}
end;
end;
iflength(s)>0 thenwriteln(s);{выводим последние символы в файл}
close(Output);{закрываем файл}
end.
Тема: Метод перебора вариантов, отсечение перебора
Задача«Вырубка деревьев»
Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет N деревьев, расстояния между соседними деревьями одинаковы.
После вырубки перед дворцом должно остаться M деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.
Входные данные
Входной файл INPUT.TXT содержит два целых числа M и N (0 <= M <= N <= 1000).
Выходные данные
В выходном файле OUTPUT.TXT должно содержаться одно число - искомое количество способов.
Комментарии
Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов вырубки некоторых из N деревьев так, чтобы после вырубки осталось M деревьев и соседние деревья находились на равном расстоянии друг от друга.
Примечания
Зафиксируем расстояние между деревьями после вырубки. Если оно равно d, то возможно n – d(m – 1) – m + 1 способов вырубить деревья. Суммируя по всем d, получаем ответ.
Если у нас есть 0 деревьев и 0 деревьев должно остаться после вырубки, то существует один вариант вырубки - это надо учитывать при решении задачи.
| INPUT.TXT | OUTPUT.TXT |
| 5 3 |
Progpam 111;
Var
n, m: longint;
i, d, s: longint;
input, output: text;
Begin
Assign(input,'input.txt');
Reset(input);
Read (input, n, m);
Close(input);
s:=0;
if m = 0 then
s:=1
Else
if m = 1 then
s:= n
Else
for d:= 1 to (n-1) div (m-1) do
inc(s,n-(m-1)*d);
Assign(output,'output.txt');
Rewrite(output);
Write(output,s);
Close(output);
end.
Тема: Сортировка и выбор
Условие задачи: Для игры в квидич используются мячи - снитчи. Проблема заключается в том, что они разного размера. Для проведения матча требуется выбрать снитч нужного веса. Перед началом матча все снитчи выстраиваются в ряд в порядке неубывания весов и Гарри Поттер должен как можно быстрее найти снитч с весом ровно Х кг или сообщить судье об отсутствии нужного мяча.
Формат входных данных:
В первой строке входного файла записаны через пробел два целых числа N и X. В следующих N строках записаны веса мячей в порядке неубывания (по одному числу в строке). Веса – целые числа, не превосходящие 100, 0<N£50000.
Формат выходных данных:
В выходной файл вывести номер снитча, имеющего вес X или число 0, если такого снитча нет.
Лимит времени: 1 секунда на тест.
Пример:
| INPUT. TXT | OUTPUT.TXT |
| 5 3 |
Указания к решению. Очевидное решение состоит в просмотре всего ряда снитчей сначала до конца, что требует времени, пропорционального числу снитчей. Однако этот алгоритм не использует того факта, что веса снитчей уже отсортированы. Наилучший метод поиска состоит в том, чтобы проверить, стоит ли нужный мяч в середине ряда. Если да, то ответ получен. Если вес x меньше веса среднего снитча, то мы можем применить тот же метод поиска к отсортированному подряду слева от среднего элемента; аналогично, если x больше веса среднего мяча, то в дальнейшем мы будем рассматривать правую половину ряда.
Код возможного решения:
program tt;
const bl = 32;
type mass = array [1..bl] of integer;
var i, n, h, x : integer;
a : mass;
input, output : text;
function snwe (a : mass; st, n, x, h : integer) : integer;
var i, br : integer;
begin
br:=round ((n-st)/2);
h:=br+st;
if (br = 0) then
begin
snwe:=0;
exit;
end;
if (a[h] = x) then
begin
snwe:=h;
end
else
begin
if (a[h] > x) then
begin
n:=n-br;
end
else
begin
st:=st+br;
end;
snwe:=snwe (a, st, n, x, h);
end;
end;
begin
assign (input, 'c:\input.txt');
assign (output, 'c:\output.txt');
filemode:=2;
reset (input);
rewrite (output);
read (input, n, x);
for i:=1 to n do
begin
read (input, a[i]);
end;
close (input);
write (output, snwe (a, 1, n, x, h));
close (output);
end.