Теорія чисел в програмуванні

Скачати 435.43 Kb.

Назва	Теорія чисел в програмуванні
Сторінка	9/10
Дата	24.10.2013
Розмір	435.43 Kb.
Тип	Документи

bibl.com.ua > Інформатика > Документи

1 2 3 4 5 6 7 8 9 10

Різнобарвні прямокутники

Дана прямокутна матриця з N рядків та M стовпчиків, кожен елемент якої дорівнює 0 або 1-7. Матриця містить декілька прямокутників (колір заданий числом від1 до 7). Якщо дві сусідні клітинки «зафарбовані» однім числом, то вони належать до одного зафарбованого фрагмента. Сусідніми клітинками будемо вважати 4 клітинки, що мають спільну бокову, верхню або нижню сторони. Прямокутники не доторкаються один до одного. Треба порахувати кількість прямокутників кожного кольору.

Формат вхідних даних: у першому рядку вхідного файлу task4.in містяться два цілих числа N (1≤N≤100) та M (1≤ M ≤100) через один пробіл – кількість рядків та стовпчиків. У наступних N рядках містяться M чисел через пробіл – елементи матриці.

Формат вихідних файлів: у вихідних файл task4.out вивести кількість прямокутників кожного кольору.

Приклад введення і виведення даних:

Task4.in	Task4.out
5 6 0 1 0 0 3 3 0 0 0 0 3 3 1 1 0 0 0 0 0 0 0 5 5 5 3 0 0 5 5 5	1->2 3->2 5->1

Ідея розв’язання. Дивиться розв’язання задачі «Прямокутники». Треба додати тільки кольори. Додаємо в розділ опису змінних масив кількості прямокутників (k:array [1..7] of integer;) та внесемо зміни в процедуру Poisk:
Procedure Poisk;

Begin

For i:= 1 to 7 do K[i]:=0;

For i:=1 to n do

For j:=1 to m do

If (A[I,j]<>0) and (A[i-1,j]=0) and (A[I,j-1]=0)

then k[a[I,j]]:=k[a[I,j]]+1;

End;

Залишається тільки оформити виведення результатів (зробить це самі).

Метод «зафарбовування». Розглянемо прийоми розв’язування задач, до яких не можна застосувати метод «ключових»елементів.

Зафарбування

Чорно-біла картинка задається у вигляді матриці, розміром N на N (1≤N≤100); елемент масиву показує чорну точку, якщо він дорівнює 1, й білу, якщо він дорівнює 0. Скласти програму перефарбування в чорний колір білої області, що обмежена чорної межею та/або межами масиву. Задано – масив, що зберігає картинку, та координати X и Y точки, від якої треба почати зафарбування.

Розв’язання.

program karta;

const N=100;

type Ar100B=array[1..n,1..n] of byte;

var a:ar100b;

i,j,m,x,y:byte;
procedure Z(m:byte; var a:ar100b;x,y:byte);

begin

if(x>1)and(x<=m)and(y>=1)and(y<=m)and(a[x,y]=0)

then

begin

a[x,y]:=1;

z(m,a,x+1,y);

z(m,a,x-1,y);

z(m,a,x,y+1);

z(m,a,x,y-1);

end;

end;

begin

readln(m);

for i:=1 to m do

for j:=1 to m do

read(a[i,j]);

write(‘координати х та у :’);readln(x,y);

z(m,a,x,y);

end.

Мікроорганізми

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

Формат вхідних даних: у першому рядку вхідного файлу task5.in містяться два цілих числа N (1≤N≤100) та M (1≤ M ≤100) через один пробіл – кількість рядків та стовпчиків. У наступних N рядках містяться M чисел через пробіл – елементи матриці (0 або 1).

Формат вихідних файлів: у вихідних файл task5.out вивести кількість мікроорганізмів

Приклад введення і виведення даних:

Task5.in	Task5.out
6 10 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0	4

Ідея розв’язання. Будемо використовувати «зафарбування» мікроорганізмів нулями.

Розв’язання.
Program task5;

Var f:text;

A:array [0..100, 0..100] of byte;

M,n,I,j,k:byte;
Procedure Init;

Begin

Assign (f,’task5.in’);

Reset(f);

Readln(f, n, m);

For i:=1 to n do

For j;=1 to m do

Read(f,a[I,j]);

Close(f);

End;
procedure Z(x,y:byte);

begin

if(x>1)and(x<=n)and(y>=1)and(y<=m)and(a[x,y]=1)

then

begin

a[x,y]:=0;

z(x+1,y);

z(x-1,y);

z(x,y+1);

z(x,y-1);

end;

end;

Procedure Out;

Begin

Assign (f,’task5.out’);

Rewrite(f);

Writeln(f,k);

Close(f);

End;

Begin

Init;

K:=0;

For i:=1 to n do

For j:=1 to m do

If a[I,j]=1 then

Begin

K:=k+1;

Z(I,j);

End;

Out;

End.

1 2 3 4 5 6 7 8 9 10

Схожі:

Відомі українські математики Діапазон наукової творчості Остроградського надзвичайно широкий: диференціальне та інтегральне числення, алгебра, теорія чисел, диференціальна...	Сума та перетин пiдпросторiв, розклад в пряму суму, фактор-простори” Алгебра і теорія чисел” I курсу, проведене 03. 03. 2008 студентом-практикантом VI курсу
Урок в 6 класі Тема. Найбільший спільний дільник кількох чисел ( НСД) Мета: сформулювати поняття спільного дільника кількох чисел, найбільшого спільного дільника, взаємно простих чисел; домогтися засвоєння...	МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ МІЖНАРОДНИЙГУМАНІТАРНИЙУНІВЕРСИТЕТ... Україні, а також виходячи з необхідності закріплення ідеї пріоритету права в юридичній діяльності вивчення навчальної дисципліни...
Порівняння чисел у межах Порівняння чисел у межах Послідовність чисел у межах Складання і розв'язування прикладів	Відгук на дипломну роботу студента ОКР «бакалавр» Солодюка Олега... Солодюк О. В. виконав досить великий обсяг роботи, опрацював серйозну монографічну і журнальну літературу, що стосувалось досліджень...
Урок №6 Тема. Найменше спільне кратне кількох натуральних чисел Мета: на основі знань про кратне число сформувати уявлення учнів про поняття спільного кратного кількох натуральних чисел, НСК, а...	ПРОГРАМА ДИСЦИПЛІНИ “Математика ” Натуральні числа і нуль. Читання та запис натуральних чисел. Порівняння натуральних чисел. Дії над натуральними числами
Міністерство освіти і науки, молоді та спорту України Державний вищий навчальний заклад Натуральні числа і нуль. Читання і запис натуральних чисел. Порівняння натуральних чисел. Дії над натуральними числами	Задача № 1 групи «А» Назвімо число m особливим, якщо можна дібрати такі цілі a та b, що. Скільки існує натуральних чисел, менших від 123 456 789, які...

Додайте кнопку на своєму сайті:
Портал навчання