Бактерії
Додамо до задачі «мікроорганізми» додаткові умови. Нехай вважається, що дві клітинки з позначками належать одному й тому ж мікроорганізму, якщо з однієї з них можна потрапити в іншу рухаючись по клітинкам з позначками ліворуч, праворуч, вгору або вниз. Якщо мікроорганізм утворює замкнуту область, то все що попадає усередину вважається частиною цього мікроорганізму.
Формат вхідних даних: у першому рядку вхідного файлу task6.in містяться два цілих числа N (1≤N≤100) та M (1≤ M ≤100) через один пробіл – кількість рядків та стовпчиків. У наступних N рядках містяться M чисел через пробіл – елементи матриці (0 або 1).
Формат вихідних файлів: у вихідних файл task6.out вивести кількість мікроорганізмів
Приклад введення і виведення даних:
Task6.in
|
Task6.out
|
10 17
0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0
0 1 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1
1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1
1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1
1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1
1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1
1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0
|
7
|
Ідея розв’язання. Спочатку «зафарбуємо» всі клітинки навколо бактерій, наприклад, 2. Будемо використовувати «огороджування» матриці нулями, щоб не шукати першу нульову клітинку. Потім будемо «зафарбовувати» все, що не дорівнює 2 та паралельно підраховувати кількість бактерій.
Розв’язання.
Program task6;
var k,i,j,m,n,t1,t2:integer;a:array[0..11,0..11] of 0..2; f:text;
procedure kr(x,y,tcvet1,tcvet2:integer);{tcvet1=0, tcvet2=2}
begin
if (a[x,y]=tcvet1)and(x>=0)and(x<=n)and(y>=0)and(y<=m) then
begin
a[x,y]:=tcvet2;
kr(x-1,y,tcvet1,tcvet2);
kr(x+1,y,tcvet1,tcvet2);
kr(x,y-1,tcvet1,tcvet2);
kr(x,y+1,tcvet1,tcvet2);
end;
end;
Procedure Out;
Begin
Assign (f,’task6.out’);
Rewrite(f);
Writeln(f,k);
Close(f);
End;
begin
assign(f,'task6.in');
reset(f);
readln(f,n,m);
for i:=1 to n do
begin
for j:=1 to m-1 do
read(f,a[i,j]);
readln(f,a[i,m]);
end;
for i:=0 to n+1 do
begin a[i,0]:=0; a[i,m+1]:=0;
end;
for j:=0 to m+1 do
begin a[0,j]:=0; a[n+1,j]:=0;
end;
close(f);
t1:=0;
t2:=2;
kr(0,0,t1,t2);
for i:=1 to n do
for j:=1 to m do
if a[i,j]=0 then a[i,j]:=1;
t1:=1;
t2:=0;
k:=0;
for i:=1 to n do
for j:=1 to m do
if a[i,j]=t1 then
begin
inc(k);
kr(i,j,t1,t2);
end;
out;
end.
Трафарет
Для багаторазового нанесення зображення на поверхню попередньо виготовляється трафарет з цим зображенням. Головною умовою виготовлення трафаретів є така: після вирізання нанесеного зображення його елементи не повинні випадати. Скласти програму, яка за заданою таблицею розміру NxM визначить, чиє на даному трафареті «випадаючи» частини зображення та їх кількість. У таблиці, що містить лише значення 0 та 1, зображення закодовано цифрами 1. Вважається, що сусідні елементи таблиці «зливаються» в єдине ціле, якщо вони містяться на однієї горизонталі чи вертикалі. Елементами зовнішнього контуру є значення 0.
Ідея розв’язання. Спочатку «зафарбуємо» всі клітинки навколо зображень, наприклад, 2. Потім будемо «зафарбовувати» все, що дорівнює 0 та паралельно підраховувати кількість частин зображення, що «випадають» (тобто – «Бактерії»). Зробіть це самі.
Обчислення периметру та площі. Розглянемо задачі, в яких потрібно обчислити площу або периметр фігури, що складається з 1.
Плакати
На стіні розташовано деяка кількість плакатів прямокутної форми. Всі їх сторони або вертикальні, або горизонтальні. Кожен плакат може бути частково або повністю перекритий другими прямокутниками. Периметром називається загальна довжина внутрішніх та зовнішніх меж отриманих фігур. Скласти програму, яка обчислює значення отриманого периметра. Координати вершини всіх прямокутників - цілі числа.
Формат вхідних даних: у першому рядку вхідного файлу task8.in знаходиться ціле число N (1≤N≤100)– кількість плакатів. У наступних N рядках містяться 4 числа через пробіл – координати верхнього лівого та нижнього правого кутів (<=100) кожного плакату
Формат вихідних файлів: у вихідних файл task8.out вивести загальний периметр отриманих фігур
Приклад введення і виведення даних:
Task8.in
|
Task8.out
|
7
1 2 3 7
2 3 4 5
2 10 3 12
3 11 5 13
3 7 6 8
4 1 5 5
5 3 7 7
|
52
|
Ідея розв’язання. Спочатку створимо матрицю із 0 та 1. Потім будемо рахувати кількість 0 навколо елементів, що дорівнюють 1. Матрицю треба «огородити» з усіх боків.
Ця матриця відповідає розташуванню плакатів, що задано у вхідному файлі.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0 1 1 1 0 0
0 0 1 1 1 1 1 1 1 0 1 1 1 1 0
0 1 1 1 1 1 0 1 1 0 0 1 1 1 0
0 1 1 1 1 1 0 1 1 0 0 1 1 1 0
0 0 0 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Розв’язання.
Program task8;
Var n,I,j,p,maxx,maxY, ij:integer;
A:array[0..100,0..100] of byte;
F:text;
X1,y1,x2,y2:array [1..100] of byte;
Procedure Init;
Begin
Assign (f,’task8.in’);
Reset(f);
Readln(f, n);
For i:=1 to n do
ReadLn(f,x1[i], y1[i],x2[i],y2[i]);
Close(f);
End;
Procedure maxkoord;
Begin
Maxx:=0; maxY:=0;
For i:=1 to n do
Begin
If x2[i]>maxX then maxX:=x2[i];
If y2[i]>maxY then maxY:=y2[i];
End;
End;
Procedure matrix;
Begin
For I:=0 to max Y+1 do
For j:= 0 to maxX+1 do
A[I,j]:=0;
For ij:=1 to n do
Begin
For j:=x1[ij] to x2[ij] do
For i:= y1[ij] to y2[ij] do
A[I,j]:=1;
End;
End;
Procedure perimeter;
Begin
P:=0;
For i:=1 to maxY do
For j:=1 to maxX do
If a[I,j]=1 then
P:=p+4-(a[i-1,j]+a[I,j-1]+a[i+1,j]+a[I,j+1]);
End;
Procedure Out;
Begin
Assign (f,’task8.out’);
Rewrite(f);
Writeln(f,p);
Close(f);
End;
Begin
Init;
Maxkoord;
Matrix;
Perimeter;
Out;
End.
Плакати2
Візьмемо попередню задачу. Але нехай підрахувати буде потрібно не периметр отриманої фігури, а її площу.
Ідея розв’язання. Спочатку створимо матрицю із 0 та 1. Потім знайдемо мінімальні й максимальні значення координат по Х та по У. Знайдемо площу отриманого таким чином прямокутника. А потім віднімемо із результату кількість нулів, що попадають в цій прямокутник.
0 1 1 1 1 1 1 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 1 1 1 0
0 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 0 0 1 1 1
1 1 1 1 1 0 1 1 0 0 1 1 1
0 0 1 1 1 1 1 1 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0 0 0 0
Зробіть це самі.
Калькулятори
Розглянемо декілька задач, розв’язання яких потребує здійснення підрахунків.
Калькулятор
Прочитати з клавіатури арифметичний вираз, що містить числа, знаки арифметичних дій та скобки. Скласти програму обчислення значення виразу.
Розв’язання
program calcul;
type shortstring=string[5];
var a,b:string;
code,c:integer;
function schang(k:shortstring):real;
var d:real;
begin
d:=0;
b:='';
while pos(a[c+1],k+')')=0 do
begin
c:=c+1;
case a[c] of
'0'..'9','.':begin b:=b+a[c]; val(b,d,code); end;
'E':begin c:=c+1; b:=b+'E'+a[c]; val(b,d,code); end;
'+':d:=d+schang('+-');
'-':d:=d-schang('+-');
'*':d:=d*schang('+-*/');
'/':d:=d/schang('+-*/');
'(':begin d:=schang(''); c:=c+1; end;
end;
end;
schang:=d;
end;
begin
writeln('enter expression:');
readln(a);
a:=a+')';
c:=0;
writeln('result:', schang(''));
readln;
end.
Пропонуємо самостійно розібратися з роботою рекурсивного калькулятора.
Калькулятор. Задача 2
У файлі в N рядках записано арифметичні вирази, що містять числа, знаки арифметичних дій та скобки. Скласти програму обчислення значення виразів.
Ідея розв’язання
Вам потрібно буде додати читання в циклі виразів з файлу, здійснити обчислення їхніх значень та вивести ці значення у файл. Зробіть це самі.
Знаки арифметичних дій
Задано вираз ((((1?2)?3)?4)?5)?6=35. Підставити на місця знаків «?» знаки арифметичних дій.
Ідея розв’язання
Будемо на місця знаків “?” почерзі вставляти знаки арифметичних дій, що зберігаються у константі с з перевіркою результата обчислення. Додавання знаків арифметичних дії організуємо рекурсивно.
Розв’язання
Const c:array [1..4] of Char=(‘+’, ‘-‘, ‘*’, ‘/’);
Var rez:real;
I, a:byte;
Str1,s:string;
Procedure chet(a:byte; s:string);
Var str2:string;
Begin
For i:=1 to 4 do
Begin
Case c[i] of
‘+’: rez:=rez+a;
‘-’: rez:=rez-a;
‘*’: rez:=rez*a;
‘/’: rez:=rez/a;
End;
Str(rez:8:4,st1); str(a,str2);
If (a<=6) and (rez<=35) then chet(a+1,s+c[i]+str2)
Else
If rez=35 then writeln(s,’=35’);
Case c[i] of
‘+’: rez:=rez-a;
‘-’: rez:=rez+a;
‘*’: rez:=rez/a;
‘/’: rez:=rez*a;
End;
End;
End;
Begin
Rez:=1; a:=2; str(rez,str1); s:=str1;
Chet(a,s);
End.
Знаки арифметичних дій. Задача 2
Задано вираз 123456789=100. Розташувати між цифрами знаки арифметичних дій ‘+’, ‘-‘ так, щоб отримати вірну рівність
Ідея розв’язання Спочатку розташуємо між цифрами знаки пробілів. Потім спробуємо всіма можливими способами (рекурсивнр) розташувати на місях пробілів знаки арифметичних дій та порахуємо результат. Потім будемо всіма можливими способами прибирати знаки пробілів, що дозволить отримувати многозначні числа. На місця пробілів будемо знову розташовувати знаки арифметичних дій.
Розв’язання
Var I,n,k:integer;
A,s:string[8];
Procedure init(k,n:word);
Var I,j,n1,er:integer;
St,st1,st11:string[17];
Ch:char;
Rez,r:longint;
Begin
St:=’123456789’;
For j:=1 to 8 do
Insert(a[j],st,2*j); n1:=17;
J:=1;
While j<=n1 do
Begin
If st[j]=’ ‘ then
Begin
Delete(st,j,1); n1:=n1-1;
End;
End;
St11:=st;
J:=1;
While (j<=n1) and (st[j] in [‘1’..’9’] do J:=j+1;
If j<=n1 then
Begin
St1:=copy(st,1,j-1);
Ch:=st[j];
Delete(st,1,j);
N1:=n1-j;
Val(st1,rez,er);
Repeat
J:=1;
While (j<=n1) and (st[j] in [‘1’..’9’] do J:=j+1;
St1:= copy(st,1,j-1);
Val(st1,r,er);
If ch=’+’ then rez:=rez+r else rez:=rez-r;
Ch:=st[j];
Delete(st,1,j);
N1:=n1-j
Until n1<=0;
If rez=100 then writeln(st11,’=100’);
End;
End
Else
For i:=1 to 3 do
Begin
A[k]:=s[i];
Init(k-1,n);
End;
End;
Begin
S:=’ +-‘; k:=8; n:=3; init(k,n);
End.
Література
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М., МЦНМО, 2001.
Бондарев В. М., Рублинецкий В. И., Качко Е. Г. Основы программирования. Харьков «Фоли», Ростов-на-Дону «Феникс», 1998.
Караванова Т.П. Основи алгоритмізації та програмування. 750 задач з рекомендаціями та прикладами. К., Форум, 2002.
Раков С.А., Логвинова Г.В. Комбинаторные алгоритмы. Харьков, 1992.
Пильщиков В.Н. Сборник упражнений по программированию по языку Паскаль. М., Наука, 1989.
Брудно А. Л., Каплан Л. И. Олимпиады по программированию для школьников. М., Наука, 1985.
Черняхівський В.В. Інформатика. Збірник задач з основ алгоритмізації. Львів, ВНТЛ, 1997.
Халамайзер А.Я. Комбинаторика и бином Ньютона. М., Просвещение, 1980.
Зубов В.С. Программирование на языке Turbo Pascal. М., Филинъ, 1997.
Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль (версия 5.5). М., Росвузнаука, 1992.
Матеріали ІІІ туру Всеукраїнської олімпіади з інформатики. Суми, 1992-2006.
Новиков Ф.А. Дискретная математика для программистов. Санкт-Петербург, Питер, 2002.
Скляр І. Обробка багатоцифрових чисел засобами мови програмування. – Інформатика, № 47(191).
Савченко В. Ефективність алгоритмів. – Інформатика, № 36-38.
Максименко М., Скляр І. Рекурсія в задачах. – Інформатика №3 (387), січень 2007.
|