Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
mybook11.05.12.doc
Скачиваний:
15
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

Формат входного файла

Первая строка содержит число N (1<=N<=24) – количество деталей в конструкторе. Следующие N строк содержат описания деталей: каждая строка содержит непустую последовательность различных заглавных латинских букв, обозначающих метки разъемов детали.

Формат выходного файла

Первая строка должна содержать число K. Вторая строка должна содержать K чисел, разделенных пробелами – номера деталей, которые Петя может использовать для сборки конструкции. Числа следует выводить в порядке возрастания.

Примеры

Input.txt

Output.txt

6

ABD

EG

GE

ABE

AC

BCD

5

1 2 3 5 6

1

ABC

0

4

AB

X

A

B

3

1 3 4

Сокращенное условие:

Из латинских букв некоторым (см.подробное условие) образом строится последовательность. Требуется написать программу, которая по заданному числу N находит символ, который стоит на N-ом месте в последовательности, получившейся после 26-го шага.

Формат входных данных:

Входной файл Input.txt содержит в первой строке число N (1<=N<226).

Формат выходных данных:

В выходном файла Ootput.txt записывается символ, стоящий в позиции N получившейся последовательности.

Пример

Input.txt

Output.txt

4

w

Задачу надо решать методом перебора с возвратом. Этот метод использовался в задаче "Последовательность". Надеюсь, что все будет понятно после прочтения программы.

var

k : integer;

n, p : longint;

inp, out : text;

begin

assign(inp,'input.txt'); reset(inp);

assign(out,'output.txt'); rewrite(out);

readln(inp,n);

p:=2; for k:=2 to 25 do p:=p*2;

k:=0;

while n>1 do

begin

k:=k+1;

if n>p then n:=n-p else n:=n-1;

p:=p div 2

end;

writeln(out,chr(ord('z')-k));

close(out)

end.

переборзадачи

Задача 10 Арифметическая прогрессия

В арифметической прогрессии было 10 вещественных чисел. Два из них были утеряны, остальные перепутаны. Найти всевозможные варианты восстановления утерянных чисел и вывести каждый вариант в новой строке.

program C4 ;

var a:array[1..8] of real;

i,j,k: integer;

d,p:real;

begin

assign(input,'in.txt') ;

reset (input);

assign(output,'out.txt');

rewrite(output);

k:=0;

for i:=1 to 8 do read(a[i]);

for i:=1 to 7 do сортировка

for j:=i+1 to 8 do

if a[i]>a[j]

then

begin

p:=a[i];

a[i]:=a[j];

a[j]:=p;

end;

d:=maxint;

for i:=1 to 7 do

if d>a[i+1]-a[i] then d:=a[i+1]-a[i]; находим разность прогрессии

for i:=1 to 7 do считаем сколько раз выполняется

if a[i+1]-a[i]=d then inc(k); равенство a[i+1]-a[i]=d

if k=7 если 7 раз, то

then утерянные числа могут стоять

begin

writeln(a[1]-2*d,' ',a[1]-d); два в начале

writeln(a[8]+d,' ',a[8]+2*d); два в конце

writeln(a[1]-d,' ',a[8]+d); одно в начале и одно в конце

end;

if k=6 если 6 раз, то

then

for j:=1 to 7 do ищем место пропущенного числа

begin

if a[j+1]-a[j]=2*d могут быть два случая

then

begin

writeln(a[1]-d,' ',a[j]+d); пропущенное число стоит перед первым и в

середине на j месте

writeln(a[j]+d,' ',a[8]+d); halt пропущенное число стоит в середине на j месте

и после последнего

end;

if a[j+1]-a[j]=3*d если пропущены два соседних внутри массива

then

begin writeln(a[j]+d,' ',a[j]+2*d);halt end; выводим их

end;

end.

переборзадачи

Задача 10 Вычеркивание чисел

а) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность.

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, одной пары соседних элементов ( одного "разрыва" возрастающей подпоследовательности).

Например: A=(1,2,3,2,4,3,4,6);

Искомая подпоследовательность (1,2,3,2,3,4,6)

Разрыв подчеркнут. ---

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, m пар соседних элементов ( возрастающая подпоследовательность с m "разрывами").

а). Пусть К(L,i) обозначает множество возрастающих подпоследовательностей длины L, которые составлены из элементов с номерами от 1 до i-1. Понятно, что их может быть очень много. Однако их число можно существенно сократить, воспользовавшись следующим фактом: из двух цепочек длины L более перспективной будет цепочка, у которой величина последнегоэлемента меньше, так как ее может продолжить большее числоэлементов. Пусть S(L,i) - это именно такая самая перспективная цепочка длины Lс минимальным по величине последним элементом, а S(i) – это множество всех цепочек S(L,i) со всевозможными L. Понятно, что в S(i) содержится не более i-1 цепочек (с длинами 1,...,i-1). Пусть мы знаем S(i). Для того, чтобы определить, какие цепочки может продолжать i-й элемент,достаточно знать последние элементы перспективных цепочек.

Для этого удобно завести массив адресов АДР последних элементов перспективных цепочек длины 1,2,...,n. При этом легко понять, что последний элемент перспективной цепочки длины s не превышает последнего элемента перспективной цепочки длины s+1. Следовательно, для очередного i-го элемента достаточно найти только максимальную длину перспективной цепочки, для которой он будет последним. Понятно, что это будет цепочка максимальной длины, последний элемент которой меньше текущего элемента. Учитывая упорядоченность последних элементов перспективных цепочек, поиск можно сделать дихотомией. При присоединении i-го элемента к какой-нибудь цепочке длины p ее длина увеличивается на 1, a ее последним элементом становится элемент i. При этом множество S(i+1) совпадает с S(i) за исключением одной цепочки

S(p+1,i+1) = S(p,i) сцепленная с i-ым элементом. Для хранения цепочек удобно хранить для каждого элемента номер элемента, который ему предшествует в цепочке.

Другое решение этой задачи:

Заведем 3 массива длины N: в массиве A[1..N] помещаются сами числа последовательности. Элемент B[i] имеет значение длины максимальной возрастающей подпоследовательности, завершающейся элементом A[i], а величина C[i] есть индекс предшествующего элементу A[i] элемента в этой максимальной последовательности (A[i]=0 есть такого элемента нет).

Если N=1, то A[1] и есть искомая подпоследовательность. При этом B[1]=1, C[1]=0. Предположим, что мы заполнили массивы A,B и C от начала до элемента M-1. Попытаемся обработать элемент A[M]. Просматривая массив A от 1 до M-1-го элемента мы ищем такое A[k], что одновременно

1) A[k]<A[M],

2) B[k] максимально.

Очевидно, что для того, чтобы получить максимальную по длине подпоследовательность, заканчивающуюся A[M], этот элемент надо приписать к подпоследовательности с последним элементом A[K]. Получаем, что B[M]=B[K]+1, C[M]=K.

Пусть мы обработали все N элементов массива A. Находим максимальный элемент массива B, пусть это будет B[K]. По построению это длина максимальной подпоследовательности.

Выписываем эту подпоследовательность: полагаем j:=k; печатаем элемент A[j]; так как предшествующий в последовательности элемент имеет индекс C[j], то делаем присваивание j:=C[j], распечатываем этот элемент и т.д., до тех пор, пока j не станет 0 (т.е. мы дошли до начала последовательности).

Запись алгоритма:

for i:=2 to N do B[i]:=0;

C[1]:=0; B[1]:=1; Max:=1; IndexMax:=1;

for i:=2 to N do

for j:=1 to i-1 do

if (A[j]<A[i]) AND (B[i]<B[j]+1)

then begin

C[i]:=j;

B[i]:=B[j]+1;

if B[i]>Max

then begin Max:=B[i]

IndexMax:=i

end;

while IndexMax<>0 do begin

writeln(A[Index-Max]);

IndexMax:=C[IndexMax]

end;

В программе в переменной Max хранится максимальная найденная до сих пор длина подпоследовательности, в IndexMax находится индекс последнего элемента этой подпоследовательности.

Структура данных, каждый элемент которой (в данном случае A[i]) содержит ссылку (в этой задаче C[i]) на предыдущий элемент (или, если требуется, на последующий элемент) называется однонаправленным списком. Если у элемента есть ссылка как на предыдущий, так и на последующий за ним элемент, то список двунаправленный (его можно реализовать, используя не один массив для индексов, а два).

б). Частный случай пункта в).

в). Заведем матрицу С[0..m+1,1..n]. В ней i-тая строка будет хранить информацию о последовательностях с i-1 разрывами; j-ый элемент в этой строке есть длина самой длинной подпоследовательности элементов "хвоста" массива А ( от j-го элемента до n-го), начинающейся в j-ой позиции и с не более чем i-1 разрывом.

Правило заполнения матрицы:

Заполним нулевую строку нулями (чтобы можно было заполнить первую строку по общему алгоритму). Для каждого номера строки i от 1 до m+1 выполнить следующие действия:

Для j-го элемента массива A (j изменяется от n до 1) находим максимальную по длине подпоследовательность, которую можно присоединить к этому элементу так, чтобы получить подпоследовательность максимальной длины с не более чем i-1 разрывом. Для этого мы:

1) ищем элемент A[k] последовательности A, больший A[j], стоящий в массиве A правее j-го элемента и с максимальным С[i,k];

2) затем просматриваем элементы i-1 -ой строки матрицы С, начиная с j+1 -го и до конца, и находим C[i-1,s] - максимальный из них;

3) сравниваем C[i-1,s] с С[i,k]. Больший из них (обозначим его C[row,col]), увеличенный на 1, запоминаем в C[i,j]. Это и будет длина максимальной подпоследовательности, начинающейся в позиции j, с не более чем i-1 разрывом.

4) Запоминаем индексы row и col элемента массива C, предшествующего C[i,j], в ячейках X[i,j] и Y[i,j] соответственно.

После окончания цикла максимальный элемент m+1 -ой строки матрицы C и есть максимальная длина возрастающей подпоследовательности с m разрывами. Выписать всю подпоследовательность можно следующим образом: для каждого элемента подпоследовательности в массивах X и Y хранится информация о предшественнике. Мы, начиная с максимального элемента m+1 -ой строки матрицы C, восстанавливаем всю подпоследовательность.

Обоснование алгоритма:

Пусть мы знаем C[i-1,j] для всех j от 1 до n и для некоторого i, а также C[i,k] для k от j+1 до n. Мы хотим вычислить C[i,j].

Для j-го элемента массива А существует максимальная по длине подпоследовательность с не более чем i-1 -им разрывом, начинающаяся с A[j]. Второй элемент (обозначим его A[k]) этой максимальной подпоследовательности (если он, конечно, есть) может быть

1) больше, чем A[j]. Тогда мы находим его среди элементов, обладающих следующими свойствами:

а) k>j,

б) C[i,k] максимальный (т.е. мы присоединяем к A[j] максимальную по длине подпоследовательность с не более чем i-1 разрывом, формируя подпоследовательность опять не более чем с i-1 разрывом);

2) меньше или равный, чем A[j]. Тогда мы ищем его среди элементов, обладающих следующими свойствами:

а) k>j;

б) C[i-1,k] максимальный (т.е. мы присоединяем максимальную подпоследовательность с не более чем i-2 -мя разрывами, формируя подпоследовательность с не более чем i-1 разрывом).

Полученная подпоследовательность получается максимальной длины, так как длина подпоследовательности, начиная с A[k], максимальная.

Упоминавшиеся выше индексы row и col, которые запоминаются в X[i,j] и Y[i,j] соответственно, обозначают

col - индекс следующего за A[j] элемента в максимальной по длине подпоследовательности, начинающейся в позиции j и имеющей не более i-1 разрыва;

row-1 - максимальное количество разрывов в подпоследовательности, начинающейся в A[col].

const max=100; {максимальная длина массива A}

var

sw,l,i,j,k,n,m,maxind,swind:integer;

c:array [0..max,1..max] of integer;

x,y:array [1..max,1..max] of integer;

a,b:array [1..max] of integer;

begin

readln(n);

for i:=1 to n do

read(a[i]);

readln(m);

fillchar(c,sizeof(c),0); fillchar(x,sizeof(x),0);

fillchar(y,sizeof(y),0);

for i:=1 to m+1 do

for j:=n downto 1 do

begin

c[i,j]:=1;

for k:=j+1 to n do

if (a[k]>a[j]) and (c[i,k]>=c[i,j]) then

begin

c[i,j]:=c[i,k]+1;

x[i,j]:=k;

y[i,j]:=i;

end;

for k:=j+1 to n do

if c[i-1,k]>=c[i,j] then

begin

c[i,j]:=c[i-1,k]+1;

x[i,j]:=k;

y[i,j]:=i-1;

end;

end;

maxind:=1;

for i:=1 to n do

if c[m+1,i]>c[m+1,maxind] then

maxind:=i;

l:=c[m+1,maxind];

j:=maxind;i:=m+1;k:=1;

while (c[i,j]<>1) do

begin

b[k]:=j; inc(k); в массив b выписываем индексы элементов

максимальной по длине подпоследовательности

sw:=x[i,j]; в прямом порядке

i:=y[i,j];

j:=sw;

end;

b[k]:=j;

for i:=1 to k do write(a[b[i]],' ');

writeln;

writeln(1);

end.

переборзадачи

Задача 13 Замечательные числа

Назовем целое число N замечательным, если для него справедливо равенство (*)

N2=(N – 1)2 + M2, где М – целое число. Даны два целых числа А и В. Найти количество замечательных чисел из диапазона [A,B] включительно. Например, в диапазоне [1,10] таких чисел два, а именно числа 1 и 5.

Входные данные: во входном файле содержатся два целых числа А и В (1<=A<=B<=109), разделенных пробелом.

Выходные данные: в выходной файл записать количество замечательных чисел из заданного диапазона.

Пример:

Input.txt

Output.txt

1 10

2

Эта задача на сокращение перебора.

Упрощаем равенство (*), получим 2*N-1= M2 . В левой части этого равенства находится нечетное число, следовательно, М тоже нечетное и принадлежит отрезку от 1 до квадратного корня из числа 2*N-1. Так как максимальное значение N равно В, то правая граница отрезка, содержащего М равна квадратному корню из числа 2*1000000000-1. Увеличим ее и возьмем равную квадратному корню из числа 2*1000000000.

program zad1;

{$APPTYPE CONSOLE}

uses

SysUtils;

const eps = 1e-10;

var m,a,b,sq,n,a1,b1:integer;

kol:integer;

begin

reset(input,'input.txt'); rewrite(output,'output.txt');

read(a,b);

kol:=0;

for m:=1 to trunc(sqrt(2000000000)) do перебираем М

if m mod 2 = 1 then если М нечетное

begin

n:=(m*m+1) div 2; вычисляем N

if (n>=a)and(n<=b) then inc(kol); и проверяем принадлежность N отрезку

end;

writeln(kol);

close(input); close(output);

end.

переборзадачи

Задача 14 Симметричные последовательности

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:

1 2 3 4 5 4 3 2 1

1 2 1 2 2 1 2 1

Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

Входные данные: в первой строке содержится число N - количество элементов исходной последовательности. Во второй строке записано N чисел, разделенных пробелом - элементы этой последовательности. 1 ≤ N ≤ 100, элементы последовательности - натуральные числа от 1 до 9.

Выходные данные: в первой строке число M - минимальное количество элементов, которое надо дописать к последовательности, во второй строке M чисел, которые надо дописать к последовательности.

Пример :

Input.txt

Output.txt

9

1 2 3 4 5 4 3 2 1

0

5

1 2 1 2 2

3

1 2 1

5

1 2 3 4 5

4

4 3 2 1

Алгоритм понятен из пояснений к программе.

program zad2;

var a,b:array[1..300]of integer;

i,j,n,k:integer;

function check:boolean; проверяет последовательность на симметричность

var i:integer;

begin

result:=false;

for i:=1 to n+k do

if b[i]<>b[n+k-i+1] then exit;

result:=true;

end;

begin

assign(input,'input.txt'); reset(input);

assign (output,'output.txt'); rewrite(output);

read(n); считываем массив

for i:=1 to n do read(a[i]);

for k:=0 to n do перебираем все возможные добавления

begin

fillchar(b,sizeof(b),0); очищаем массив b

b:=a; копируем массив а в массив b

for i:=n+1 to n+k do добавляем в массив b К чисел

b[i]:=a[n+k-i+1];

if check then проверяем массив на симметричность

begin

writeln(k); если получили симметричную последовательность, то

for i:=n+1 to n+k do выводим количество добавленных чисел и сами числа

write(b[i],' ');

close(input); close(output);

halt(0); прерываем работу программы

end;

end;

close(input); close(output);

end.

переборзадачи

К оглавлению

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]