Де і в якому столітті виготовлено монету

Розв’язання: Для розв’язку задачі згадаємо логічні операції, які ми розглядали раніше. З розглянутих операцій для розв’язку даної задані нам будуть потрібні операції not, and і or. Запишемо висловлення хлопчиків при допомозі цих операцій, ввівши попередньо наступні позначення:

А = {монета грецька},

B = {монета фінікійська},

C = {монету викарбувано в ІІІ столітті},

D = {монету викарбувано в ІV столітті },

E = {монету викарбувано в V столітті }.

Крім того використаємо для зменшення кількості записів такі позначення логічних операцій, які прийнято в алгебрі логіки, а саме:

n not (A) Ы

n A and B Ы A&B

n A or B Ы AЪ B

Використовуючи домовленості, запишемо висловлювання юних нумізматів на мові алгебри логіки:

A&E – слова Юрка,

В &С – слова Сашка,

Ъ D – слова Михайла.

Зі слів вчителя історії випливає, що кожне з цих висловлень хибне, так як кожен з хлопчиків вірно висловив лише половину свого висловлення. Що це значить? Припустимо, що Юрко вірно вказав, що монета грецька (А = 1), але помилився в часі її виготовлення (Е = 0). Якщо ж він не правий в тому, що монета грецька (А = 0), то вірно вказав час виготовлення (Е = 1). Звідси випливає, що

А & Ъ & Е = 1.

Проводячи аналогічні міркування для висловлень Сашка та Михайла, отримаємо ще два істинних складних висловлення:

В & Ъ & C = 1

& Ъ A & D = 1.

Якщо ж ці висловлювання логічно перемножити, то отримаємо істинне складне висловлення:

(А & Ъ & Е) & (В & Ъ & C) & ( & Ъ A & D) = 1

Розкриваємо дужки, тобто спрощуємо отриманий складний вираз:

А & & B & & & Ъ A & & B & & A & D Ъ

А & & & C & & Ъ A & & & C & A & D Ъ

& E & B & & & Ъ & E & B & & A & D Ъ

& E & &C & & Ъ & E & B & C & A & D = 1.

Так як А & = 0 (монета не може бути одночасно і грецькою і не грецькою), то будуть рівні нулю (будуть хибними) і вирази:

А & & B & & & = 0

А & & & C & & = 0

& E & B & & A & D = 0

& E & B & C & A & D = 0

Крім того, з умови випливає, що:

так як A & B = 0, то A & & B & & A & D = 0,

C & D = 0, то A & & & C & A & D = 0,

E & C = 0, то & E & &C & & = 0.

(З яких даних умови це випливає?)

Тому залишається єдина відповідь:

& E & B & & & = 1, тобто істинними є висловлення В і Е.

Програмна реалізація даного розв’язку з виведенням станів всіх логічних змінних і відповідних повідомлень приведена нижче. Крім того під час виконання дана програма будує в пам’яті таблицю істинності для отриманого висловлення. Рекомендуємо Вам модифікувати дану програму для отримання значень таблиці істинності при всіх значеннях змінних.

program logic1;

uses crt;

const a1 = ‘ Монета грецька. ’;

b1 = ‘ Монета фiнiкiйська. ’;

c1 = ‘ Монету викарбувано в III столiттi. ’;

d1 = ‘ Монету викарбувано в IV столiттi. ’;

e1 = ‘ Монету викарбувано в V столiттi. ’;

var

a,b,c,d,e: boolean;

function answer: boolean;

begin

answer:= (not (a)) and (e) and (b) and (not(c)) and (not a) and (not d);

end;

begin

clrscr;

for a:= false to true do

for b:= false to true do

for c:= false to true do

for d:= false to true do

for e:= false to true do

begin

if answer = true then

begin

writeln(a,‘ ’,b,‘ ’,c,‘ ’,d,‘ ’,e,‘ ’,answer);

if a = true then writeln(a1);

if b = true then writeln(b1);

if c = true then writeln(c1);

if d = true then writeln(d1);

if e = true then writeln(e1);

end;

end;

writeln;

readln;

end.

Перед тим, як перейти до наступної задачі, спробуйте задати функцію answer таким чином, щоб в ній не було готового результату, а були лише дані, що отримуються на підставі аналізу умови задачі.

Розглянемо ще одну задачу такого типу. Вона буде цікавою ще й тим, що ми введемо нову логічну операцію, яка в мові Паскаль не визначена.

Задача 150. 150. Повернувшись додому, комісар Мегре подзвонив на набережну Орфевр.

– Говорить Мегре. Є новини?

– Так, шеф. Надійшли повідомлення від інспекторів. Торранс встано-вив, що якщо Франсуа був напідпитку, то або Етьєн вбивця, або Франсуа каже неправду. Жусьє вважає, що або Етьєн вбивця, або Франсуа не був напідпитку і вбивство відбулось вночі. Інспектор Люка просив передати вам, що якщо вбивство відбулось вночі, то або Етьєн вбивця, або Франсуа каже неправду. Потім подзвонила...

– Гаразд. Дякую. Цього достатньо. – комісар поклав слухавку. Він знав, що тверезий Франсуа ніколи не каже неправду. Тепер він знав все.

Розв’язання: Задачі такого типу є досить цікавими, але рідко розглядаються в шкільному курсі інформатики. Для того, щоб постаратись зацікавити вас алгеброю логіки, при розв’язуванні даної задачі введемо ще одну логічну операцію, яку не реалізовано в мові Паскаль – imp (implementation).

Прості висловлення записані, як і в попередній задачі, у вигляді констант.

program logic2;

uses crt;

const a1 = ' Франсуа був не тверезим. ';

a2 = ' Етьен - вбивця. ';

a3 = ' Франсуа каже неправду. ';

a4 = ' Вбивство вiдбулось вночi. ';

var

a,b,c,d,m: boolean;

Операція imp призначена для реалізації наступної логічної операції над двома логічними змінними a,b: a imp b = falseтоді і тільки тоді, коли a=trueіb=false, у всіх інших випадках a imp b = true. В застосуванні до умови нашої задачі це звучить так: «якщо Франсуа був напідпитку, то або Етьєн вбивця, або Франсуа каже неправду» і записується на мові алгебри логіки так:

А Ю (В Ъ С) = 1

Зверніть увагу, що ми примінили дану операцію до трьох змінних, об’єднавши дві з них у складне висловлення ((В Ъ С) = 1).

Тепер спробуйте самостійно записати на мові алгебри логіки умову задачі, якщо у вас виникнуть труднощі, то розберіться з функцією answer, в якій і записано повністю умову задачі, без жодних спрощень складних логічних виразів. Зверніть при аналізі розв’язку увагу саме на той факт, що використавши нову логічну операцію ми позбавились від необхідності виконувати логічні дії самостійно.

function imp(a,b:boolean):boolean;

begin

if (a=true) and (b=false) then imp:=false

else imp:= true;

end;

function answer: boolean;

begin

m:= b or c;

answer:= ((imp(a,m)) and (b or (not(a) and d)) and (imp(d,m)))

and (not (a) and (not (c)));

end;

begin

clrscr;

for a:= false to true do

for b:= false to true do

for c:= false to true do

for d:= false to true do

if answer = true then

begin

writeln(a,' ',b,' ',c,' ',d,' ',f);

if a = true then writeln(a1);

if b = true then writeln(a2);

if c = true then writeln(a3);

if d = true then writeln(a4);

end;

writeln;

readln;

end.

Вправи та завдання

При написанні програм до приведених нижче завдань обов’язково використовуйте процедури та функції.

151. 151. Знаючи координати вершин чотирикутника знайти його периметр.

152. 152. Знайти найдовшу сторону чотирикутника. Координати вершин відомі.

153. 153. Знайти меншу з діагоналей паралелограма ABCD, якщо відомо координати його вершин. Виконати перевірку, чи є даний чотирикутник паралелограмом.

154. 154. Знайти найбільшу висоту трикутника, якщо відомо координати його вершин.

155. 155. Знайти найбільшу з висот N трикутників, якщо відомо координати їх вершин.

156. 156. Знайти суму бісектрис трикутника, знаючи координати його вершин.

157. 157. Який з трьох трикутників, заданих координатами своїх вершин, має більший периметр?

158. 158. Який з N трикутників, заданих координатами своїх вершин, має більший периметр?

159. 159. Знайти найбільший кут (в градусах) трикутника АВС, заданого координатами своїх вершин.

160. 160. Знайти найбільший кут (в градусах) N–кутника, заданого координатами своїх вершин.

161. 161. Знайти радіус більшого з кіл описаних навколо двох трикутників АВС та МРК, якщо відомі координати їх вершин.

162. 162. Піраміду SABC задано координатами своїх вершин. Знайти повну поверхню[7] піраміди.

163. 163. Яке з двох введених чисел А та В має меншу суму цифр?

164. 164. В якому з трьох чисел сума непарних цифр найменша?

165. 165. Задано два числа M i N. Яке з двох чисел буде більшим, якщо в обох числах переставити крайні цифри?

166. 166. Брауну, Джонсу і Сміту пред’явлено звинувачення в співучасті в пограбуванні банку. Відомо, що грабіжники зникли з місця злочину на автомобілі, що їх очікував. На слідстві Браун засвідчив, що злочинці зникли на синьому «Бьюїку», Джонс стверджував, що це був чорний «Крейслер», а Сміт запевняв, що це був «Форд Мустанг» і ні в якому випадку не синій. Стало відомо, що бажаючи заплутати слідство, кожен з них вказав вірно або лише марку автомобіля, або лише її колір. Якого кольору і якої марки був автомобіль?

167. 167. Марія Василівна повернулась до школи з міської олімпіади з математики і на питання учнів, хто з їх однокласників зайняв яке місце, відповіла:

– Я втомилась під час перевірки робіт, але знаю, що Наталка, Оля, Ірина і Тетяна зайняли перші чотири місця. Якщо ви бажаєте взнати, хто яке місце зайняв, я вам повідомлю три факти, з яких кожен є вірним лише наполовину:

­­– Тетяна – перша, Оля – друга;

– Тетяна – друга, Наталка – третя;

– Ірина – друга, Наталка – четверта.

А тепер ви мені повідомите, хто яке місце посів.

168. 168. По звинуваченню в крадіжці до суду було притягнуто Іванова, Петрова і Сидорова. Слідством встановлено, що:

1. Якщо Іванов не винний або Петров винний, то Сидоров винний.

2. Якщо Іванов не винний, то Сидоров не винний.

Чи приймав участь в крадіжці Іванов?

Масиви

Поняття масиву

Кожен з вас в початкових класах вів щоденник спостережень за природою (календар природи), куди, крім інформації про вітер, сонце, опади, заносили ще й значення температури кожного дня. Припустимо, що ми ведемо спостереження в лютому місяці 1999 року – останнього року ХХ століття. Оскільки ми не є науковими співробітниками, то і значення температури будемо вимірювати приблизно – з точністю до цілих.

Давайте складемо табличку, яка буде містити лише один рядок і в кожній клітинці якої буде знаходитись температура о 7-й годині ранку в лютому місяці. Наша табличка повинна містити 28 клітинок, крім того будемо вважати, що рік – не високосний.

-8	-7	-5	-4	-4	-5	-4	...	-9	-7	-4	-2			-1
							...

Рис. 1.

Ми спеціально пронумерували внизу номера клітинок таблиці і, крім того, зобразили лише початок і кінець нашої таблиці, що вмістити всю таблицю в один рядок.

Таку таблиця у програмуванні називають одномірним масивом. Одномірним тому, що в нашому розпорядженні є лише один рядок таблиці. Кожна клітинки таблиці називається коміркою масиву і має свій номер. Якщо значення комірки (в нашому випадку – температури) може змінюватись, то номер комірки є фіксованим і змінюватись для даної комірки не може. Номер комірки іноді ще називають індексом масиву.

На мові програмування в розділі опису змінних даний масив можна було б описати так:

var temp: array [1..28] of integer;

Опис даної групи змінних можна було б здійснити і не використовуючи масивів, але тоді б нам знадобилось 28 змінних типу integer: temp1, temp2,..., temp28. Звичайно, використати і описати одну змінну, а не 28 є значно зручнішим. Причому інформацію про номер дня ми не втрачаємо, так як звернення до елементів (комірок) масиву відбувається тільки через їх індекси (в нашому випадку – номери днів). Якщо масив уже заповнено, то ми без будь–яких зусиль можемо вивести на екран температуру у відповідний день місяця, наприклад:

write(temp[4]); – надрукуємо температуру 4–го лютого;

write(temp[25]); – надрукуємо температуру 25–го лютого.

Отже, для того щоб задати масив і програмі нам необхідно описати його в розділі змінних, обов’язково вказавши, якого типу змінні містяться у всіх комірках масиву. Звернення до кожної комірки масиву подібне до звернення до звичайної змінної аналогічного типу за тим винятком, що обов’язково вказується номер комірки (індекс) масиву.

Зробимо наш календар природи електронним. Програма для наших спостережень за лютий місяць матиме вигляд:

program kalendar_priroda;

uses dos, crt;

var i: integer;

temp: array[1..28] of integer;

begin

clrscr;

for i:= 1 to 28 do

begin

write(‘Введiть значення температури ’,i,‘-го лютого: ’);

readln(temp[i]);

end;

for i:= 1 to 28 do write(i:4);writeln;

for i:= 1 to 28 do write(temp[i]:4); writeln;

readln

end.

Отже, масив – це спосіб організації збереження великої кількості однотипних даних. Масиви досить широко використовуються при розв’язуванні конкретних задач різного типу: економічних, математичних, статистичних, і т.д., тому розберемо декілька найбільш частіше використовуваних типів задач, що виникають при роботі з масивами.