Лекции по Turbo Pascal (стр. 23 )

day=1..31;

data = Record

y : year;

m : month;

d : day;

end;

Var dat, next : data;

Function leap(yy:year):boolean; {функция определяет

високосный ли год}

begin

leap:=(yy Mod 4=0) And (yy Mod 400 <>0);

end;

Function Dmonth(mm:month; yy : year) : day; {функция определения

количества дней данного месяца в данном году}

begin

case mm of

1,3,5,7,8,10,12: Dmonth:=31;

4,6,9,11 : Dmonth:=30;

2 : if leap(yy) then Dmonth:=29 else Dmonth:=28;

end;

end;

procedure Tomorrow(td : data; var nd : data); {опр-ние завтрашней даты}

begin {если это не последний день месяца}

if td. d<> Dmonth(td. m, td. y) then

with nd do

begin

d:=td. d+1;

m:=td. m;

y:=td. y;

end;

else {если это последний день месяца}

if td. m=12 then {если это декабрь}

with nd do

begin

d:=1;

m:=1;

y:=td. y+1;

end;

else { если это не декабрь}

with nd do

begin

d:=1;

m:=td. m+1;

y:=td. y;

end;

end;

BEGIN

writeln(‘Введите сегодняшнее число, месяц и год’);

readln(dat. d, dat. m, dat. y);

Tomorrow(dat, next);

writeln(‘завтра будет’);

writeln(next. d, ‘.’, next. m, ‘.’, next. y);

END.

Задачи:

13.1   Фамилии и имена 25 учеников класса записаны в двух различных таблицах. Напечатать фамилию и имя каждого ученика на отдельной строке.

13.2   Названия 20 футбольных клубов и городов, которые они представляют, записаны в двух различных таблицах. Напечатать название и город каждого клуба на отдельной строке.

13.3   Даны названия 26 городов и стран, в которых они находятся. Среди них есть города, находящиеся в Италии. Напечатать их названия.

13.4   Известны данные о 16 сотрудниках фирмы: фамилия и отношение к воинской службе (военнообязанный или нет). Напечатать фамилии всех военнообязанных сотрудников.

13.5   Известны данные о мощности двигателя (в л. с.) и стоимость 30 легковых автомобилей. Определить общую стоимость автомобилей, у которых мощность двигателя превышает 100 л. с.

13.6   Известны данные о цене и тираже каждого из 15 журналов. Найти среднюю стоимость журналов, тираж которых меньше 10000 экземпл.

13.7   Известны данные о массе и объеме 30 чел, изготовленных из различных материалов. Определить максимальную плотность материала тел.

13.8   Известны вес, пол, рост каждого из 22 человек. Найти общую массу и средний рост мужчин.

13.9   Известно количество очков, набранных каждой из 20 команд - участниц первенства по футболу. Ни одна пара команд не набрала одинакового количества очков.

а) Определить название команды, ставшей чемпионом.

б) Определить названия команд, занявших второе и третье места.

в) Определить названия команд, занявших первое и второе места, не используя при этом двух операторов цикла (два прохода по массиву).

г) Вывести названия команд в соответствии с занятыми ими местами в чемпионате.

13.10 Известны оценки каждого из 25 учеников класса по десяти предметам. Найти фамилию одного из учеников :

а) имеющих наибольшую сумму оценок;

б) имеющих наименьшую сумму оценок.

13.11 Известны баллы, набранные каждым из 20 спортсменов-пятиборцев в каждом из пяти видов спорта. Определить фамилию спортсмена - победителя соревнований.

13.12 Известны данные о 20 учениках класса: фамилии, имена, отчества, даты рождения (год, номер месяца и число). Определить, есть ли в классе ученики, у которых сегодня день рождения, и если да, то напечатать имя и фамилию каждого.

10 класс

Повторение: Решить следующую задачу: Существует фирма, которая организует работу на контрактной основе, то есть если для какого-либо специалиста есть работа он нанимается, по окончания работы он увольняется, причем буквально на следующий день его могут нанять снова. Дан файл в котором хранится вся информация по рабочим за год, причем общее количество рабочих неизвестно. Она выглядит следующим образом: в первой строке записана фамилия рабочего, на следующей строке день и месяц его найма, на третьей – день и месяц окончания работы. Необходимо:

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

б) вывести на экран список рабочих и у каждого указать общее количество рабочих дней за год.

в) сформированный в предыдущем пункте список отсортировать по убыванию количества рабочих дней.

Двоичный и к-ичный перебор.

Метод двоичного перебора применяется в тех случаях, когда требуется организовать перебор всевозможных подмножеств данного множества (множество в Паскале представляет собой набор различных элементов одного типа). То есть если есть набор каких-либо элементов, то из него мы можем выбирать элементы в любых сочетаниях, и в любых количествах (например, группа людей в количестве ну для определенности пяти человек, собирается на прогулку, при этом они в итоге могут пойти все, а если вдруг испортилась погода, то может не пойти вообще никто, а могут собраться двое, трое и т. д.).

Очевидно, что каждый элемент из рассматриваемого множества может иметь только два состояния (включен или не включен, активен или не активен, есть или нет). Получаем, что каждый элемент может иметь только два значения именно поэтому данный метод, и является двоичным.

В качестве модели рассмотрим массив из n элементов, каждый из которых может принимать только два значения (каждый элемент массива соответствует какому-то одному объекту множества), следовательно, получаем, что элемент массива может принимать только два значения: 0 – не выбран или 1 - выбран, то есть данный объект множества включен в подмножество.

Задача сводится к тому, чтобы перебрать все возможные комбинации 0 и 1, в результате чего учитываются все варианты, при этом они не должны повторяться. Для определенности рассмотрим множество, состоящее из пяти элементов. Вначале в массив запишем пять нулей: (0, 0, 0, 0, 0). Эти нули соответствуют начальному состоянию множества, заключающееся в том, что выбранных объектов нет (то есть пустое множество).

На первом шаге обработки массива, увеличим на единицу последний элемент массива, то есть, получаем следующее подмножество (0, 0, 0, 0, 1). Тем самым мы получили новый возможный вариант комплектации массива, в котором выбран последний пятый элемент.

На втором шаге снова увеличиваем последний элемент массива на единицу, при этом получаем что он равняется двойке, что невозможно по условию формирования массива, следовательно последний элемент необходимо занулить, а на единицу увеличиваем предыдущий элемент, то есть четвертый, получаем (0, 0, 0, 1, 0). Этот вариант соответствует тому, что выбран только четвертый объект множества.

На третьем шаге снова увеличиваем последний элемент массива на единицу, получаем (0, 0, 0, 1, 1). Что соответствует тому, что выбраны уже четвертый и пятый объект некоторого множества.

На четвертом шаге снова увеличиваем последний элемент массива на единицу, и он у нас в итоге равняется двойке, что невозможно, поэтому мы его зануляем, а на единицу увеличиваем предыдущий разряд, при этом он так же обращается в двойку, необходимо и его занулить, а на единицу увеличить третий элемент массива, в результате получаем такой вариант (0, 0, 1, 0, 0). Следовательно, во множестве выбран только третий объект.

И таким образом происходит перебор всех возможных вариантов формирования множества состоящего из нулей и единиц. Последний возможный вариант для нашего множества, это все единицы (1, 1, 1, 1, 1). Что соответствует выбору всех объектов рассматриваемого множества. Предположим, что мы не остановились на этом этапе и продолжили увеличивать наш массив, то есть на единицу увеличиваем последний элемент массива, при этом он обращается в двойку, мы его зануляем и переносим единицу в предыдущий разряд, и в нем получаем двойку, снова зануляем и переносим, и это продолжается до тех пор, пока мы не оказываемся в позиции первого элемента, который также обращается в двойку, которую необходимо занулить а единицу перенести в предыдущий разряд, то есть в нулевой, который в обычном используемом нами массиве не фигурирует. Следовательно, в данном случае нам необходимо определить позицию нулевого элемента массива для определения окончания перебора всех возможных вариантов формирования массива из нулей и единиц. То есть в начале мы формирует массив из всех нулей, в том числе ноль находится и в нулевом разряде, после того как нами перебраны все варианты, и единицы находятся во всех позициях кроме нулевой мы делаем следующий шаг и получаем нули во всех позициях кроме нулевой, там находится единица, вот именно эта единица и будет служить для нас окончанием перебора всевозможных вариантов. В результате перебора мы должны получить 2n вариантов, где n – количество элементов массива. Для успешной работы программы n не может быть бесконечно, при n>20 на обработку данных программе требуется уже очень много времени.

Алгоритм решения задачи с использованием двоичного перебора:

1.  Ввести исходные данные (если в этом есть необходимость).

2.  Сформировать нулевой вектор с номерами элементов от 0 до n.

3.  Обработать этот вектор.

4.  Сформировать новый вектор.

5.  Если нулевой разряд вектора равен 0, то повторить третий пункт, иначе закончить.

Задача 1: Вывести на экран всевозможные наборы 0 и 1 и их порядковые номера.

program primer;

uses crt;

var p: array [0..30] of byte;

n, i, k: integer;

procedure vector;

begin

i:=n;

while p[i]=1 do begin

p[i]:=0;

dec(i);

end;

p[i]:=1;

end;

procedure work;

begin

inc(k);

write (k:3,’: ‘);

for i:=1 to n do

write (p[i]);

writeln;

end;

begin

clrscr;

writeln (‘Введите n’);

readln (n);

k:=0;

for i:=0 to n do p[i]:=0;

repeat

work;

vector;

until p[0]=1;

readln;

end.

Задачи:

1.  Даны n различных цифр, получить из них всевозможные числа, при условии, что в числе цифры не повторяются.

2.  Даны n различных букв, получить все возможные слова из них при условии что буквы в словах не повторяются.

3.  Имеется n монет разного достоинства, определить, можно ли получить задуманную сумму денег, данными монетами. Если вариантов несколько, то вывести их все на экран, а если их нет, то сообщить об этом.