Задача g6_1001: Проблема с A и B.Поменять значения переменных A и B между собой, не заводя дополнительных переменных. Входной файл input.txt содержит числа a и b (0 <= a, b <= 32767). В выходном файле output.txt должны содержаться значения этих переменных после обмена.Решение g6_1001: Первая мысль, приходящая в голову, это написать программу, похожую на эту:
A := B;
B := A;
Естественно, это программа работать не будет (в обеих переменных будет значение B).Теперь поищем правильное решение. Обозначим начальное значение A за A1, B за B1. Тогда необходимо, чтобы по окончании работы программы A равнялось B1, а B - A1.0) A = A1; B = B1;1) Занесем в переменную A результат суммирования A и B (A := A + B):A = A1 + B1; B = B1;2) Занесем в переменную B разность A и B (B := A - B):A = A1 + B1; B = A1;3) Занесем в переменную A разность A и B (A := A - B):A = B1; B = A1;Код программы:
A := A + B;
B := A - B;
A := A - B;
Ура!Этого решения хватило мне, чтобы сдать эту задачу в школе на уроке, однако дома я нашел в этом алгоритме несколько слабых моментов:1) Возможно переполнение переменных. Это зависит от настроек компилятора.2) А что, если переменные не числовые? Например char.Это привело меня ко второму решению: Для начала разберемся, что такое логическая операция xor. Вот несколько ее свойств:1) A xor A = 0;2) A xor B = B xor A;3) A xor (A xor B) = B;Их нам вполне достаточно, чтобы написать новую программу, которая меньше зависит от типа данных A и B:Код программы:
A := A xor B;
B := A xor B;
A := A xor B;
Разобраться в ней не так уж сложно.
Задача g6_1002: Трамвайные билеты.Написать программу определения количества шестизначных "счастливых" трамвайных билетов, у которых сумма первых трех цифр совпадает с суммой трех последних.Оптимизировать решение по времени выполнения. Количество билетов вывести в файл output.txtРешение g6_1002:Логично устроить цикл в цикле, затем считать сумму первых и последних трех цифр и сравнивать их между собой.Как считать сумму цифр?
For Spec := 1 to 3 do
Begin
K := K + Luck mod 10;
Luck := Luck div 10;
End;
где Luck - число, в котором надо посчитать сумму цифр, K - сумма цифр (более правильная реализация с циклом while, но это я предоставлю реализовать вам ;).Итак, у нас два цикла, в которых перебираются 1000 чисел, итого 1000000 итераций, т.е. мы перебираем все возможные билеты, но делаем это не очень явно.Попробуем разогнать программу в 1000 раз :). В этом нам поможет динамическое программирование, т.е. сохранение уже полученных однажды результатов.Рассмотрим трехзначное число. Сумма цифр этого числа может принимать значения от 0 до 27, т.е. мы можем просто посчитать сколько чисел от 0 до 999 с данной суммой цифр и записать это значение в массив от 0 до 27.Т.к. второе число также трехзначное, то мы можем пользоваться для него тем же массивом данных. Тогда, после подсчета кол-ва чисел с данной суммой цифр, мы можем достаточно просто подсчитать количество "счастливых билетов":
For I := 0 to 27 do
L := L + M[I] * M[I];
где I - счетчик, L - кол-во счастливых билетов, M - массив значений суммы цифр.Удачи вам в реализации!
Задача g6_1003: Шифр Цезаря.Написать программу, реализующую сдвиг по ключу(ключ задается) только для больших русских букв(буква Ё не используется).Пример:Входные данные:АБЯ - строка, 2 - ключ.Выходные данные:ВГБ Решение g6_1003:Здесь стоит создать строку длиной 32 символа и заполнить ее русским алфавитом (его можно извлечь из ASCI-таблицы). Допустим, мы считали одну букву. Осуществим поиск этой буквы в строке. Если буква не найдена (т.е. это не большая русская буква), то выводим ее. Если же буква найдена, то к ее позиции прибавляем значения ключа. От числа получаем остаток от деления на 32 (сдвиг циклический) и выводим букву, соответствующую новой позиции.
Задача g6_1004: Равновеликие прямоугольники.Прямоугольники, площади которых равны, называются равновеликими. Написать программу, находящую все возможные целочисленные стороны равновеликих прямоугольников заданной площади. Одинаковые прямоугольники, получающиеся заменой сторон, печатать не надо.Входные данные:Площадь четырехугольника (1<=n<=50000).Выходные данные:Стороны четырехугольника (A*B)Пример входных данных:12Пример выходных данных:1*122*63*4Решение g6_1004:Попробуем упростить задачу. Разберемся, что такое площадь прямоугольника. Площадь прямоугольника - произведение длин двух прилежащих сторон. Т.е. задачу можно представить как нахождение всех пар множителей, дающих заданный результат.Рассмотрим алгоритм эффективного поиска множителей данного числа. (Кстати, эта задача была на одной из олимпиад несколько лет назад)Мы будем искать одновременно два сопряженных множителя, т.е. множителя, которые при перемножении дают искомое число. Код программы:
MaxF := trunc(sqrt(N)); {Первый множитель данного числа не может
быть больше корня из этого числа, в то время как сопряженный с
ним множитель всегда не меньше этого корня}
For F := 1 to MaxF do
If N mod F = 0 then Writeln (F, N div F);
Вот и все! Для примера я приведу авторское решение:
{Равновеликие прямоугольники. Решение А.Никитина, Самара }
program equrectangle;
var p:word; {переменная для площади}
procedure find_and_print_side(a,b:word);
begin
if (a<=b) then begin
if (a*b=p) then writeln(a,'*',b);
inc(a); find_and_print_side(a,p div a);
end;
end;
begin { основная программа }
assign(input,'square.in'); reset(input); readln(p); close(input);
assign(output,'square.out'); rewrite(output);
find_and_print_side(1,p);
close(output);
end.
По моему мнению, оно неэффективное. Для этого я проделал небольшой эксперимент:1) Заменил ограничение на N<=1000000000.2) Исправил в авторском решении тип переменных с word на longint.На тесте 98765432 я не дождался, пока программа найдет ответ, а если ввести какое-нибудь большое простое число, то она будет проводить n итераций, в то время как моя программа независимо от числа производит sqrt(n) операций. Ура мне :)
Задача g6_1005 - MIME64.
Пpи пеpедаче файлов по телекоммуникационным каналам, помимо дpугих возможных ваpиантов, используется так называемый фоpмат MIME64 (Multitask Internet Mail Extensions; '64' означает использование 64-символьной стpоки-шаблона). Этот фоpмат позволяет пеpевести исходный ASCII-текст, включающий как символы "человеческого" алфавита, так и pяд специальных символов, в "видимый фоpмат".Механизм кодиpовки для этого фоpмата следующий:1) исходный текст pассматpивается как последовательность битов;она pазбивается, слева напpаво, на 6-битовые отpезки (если последний отpезок "неполный", то он дополняется битовыми нулями);2) каждая 6-битовая комбинация тpактуется как число (естественно, из диапазона 0..63);3) число заменяется символом с соответствующим поpядковым номеpом из стpоки-шаблона, состоящей из 26 заглавных букв латинского алфавита (A..Z), 26 стpочных букв того же алфавита (a..z), цифp (0..9) и еще двух символов ("+" и "/"), то есть из стpокиABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz 0123456789+/Задача: =================Написать программу декодирования сообщения в формате MIME.Hа вход пpогpаммы подается непустой текстовый MIME64-файл (MIME64.IN).Сфоpмиpовать соответствующий ASCII-текст (или еще что-то), поместив его в выходной файл (MIME64.OUT).Попытаться выяснить, что же было закодировано.Решение g6_1005:Задача была предложена на школьной OL11 в 2000 году. Тогда я не сумел ее решить (ламер), но сейчас я ее добил.Задача имеет практическое применение: сейчас такая программа встроена во все почтовые клиенты, а раньше людям приходилось самим писать программы-распаковщики.Итак, на вход поступает строка, с алфавитом в 64 символа(кодируется 6-ю битами), а на выход должно поступать строка с алфавитом 256 символов (кодируется 8-ю битами). Задача заключается в преобразовании потока 6-битных в поток 8-битных.Для решения этой задачи логично использовать буфер (в данном случае хватит буфера длиной 16, точнее 12 бит - переменной word).На первом этапе мы считываем одну букву и получаем ее номер в строке:
Repeat
Read(C);
If (C in ['0'..'9']) or (C in ['A'..'Z']) or (C in ['a'..'z'])
or (C = '+') or (C = '/') then begin
Spec := Pos(C, S) - 1;
PushBuff(Spec);
end;
Until EOF;
S - строка шаблон.Здесь присутствует процедура PushBuff. Приведем ее текст:
Procedure PushBuff (Inp : byte);
begin
Buffer := Buffer shl 6; {сдвинули содержимое на 6 бит влево}
Buffer := Buffer or Inp; {добавили новое 6-и битное число
(первые 2 бита - нули)}
BIB := BIB + 6; {буфер увеличился на 6 бит}
If BIB >= 8 then PopBuff; {выбрасываем содержимое}
end;
BIB - количество бит в буфере.Процедура PopBuff - выбрасывет содержимое буфера:
Procedure PopBuff;
var
Work : word;
Ans : byte;
begin
Work := Buffer;
Work := Work shr (BIB - 8); {Оставляем в переменной "самые
старые" 8 бит}
BIB := BIB - 8; {теперь бит меньше}
Buffer := Buffer shl (16 - BIB);
Buffer := Buffer shr (