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

Скачати 435.43 Kb.

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

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

1 2 3 4 5 6 7 8 9 10

Прямокутники

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

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

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

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

Task2.in	Task2.out
5 10 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 0	5

Ідея розв’язання. Очевидно, що кількість прямокутників дорівнює кількості його, наприклад, верхніх лівих кутів - елементів, що самі дорівнюють 1 та сусідні клітинки зверху та зліва містять 0:

1 0 0 1 1 0 0 1 1 1

0 0 0 1 1 0 0 1 1 1

0 0 0 0 0 0 0 1 1 1

1 1 0 1 1 1 0 1 1 1

0 0 0 1 1 1 0 0 0 0
Тобто треба порахувати кількість таких елементів. Матрицю треба «огородити» зверху та зліва. Зауваження: можна рахувати другі кути, але тоді й огороджувати потрібно інакше (спробуйте самі).

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

Var f:text;

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

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

Begin

Assign (f,’task2.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 Ograda;

Begin

For i:=0 to n+1 do

Begin

A[I,0]:=0;

End;

For j:=0 to m+1 do

Begin

A[0,j]:=0;

End;

End;

Procedure Poisk;

Begin

K:=0;

For i:=1 to n do

For j:=1 to m do

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

then k:=k+1;

End;

Procedure Out;

Begin

Assign (f,’task2.out’);

Rewrite(f);

Writeln(f,k);

Close(f);

End;

Begin

Init;

Ograda;

Poisk;

Out;

End.

Ламана

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

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

Формат вихідних файлів: у вихідних файл task3.out вивести одне число – кількість ламаних.

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

Task3.in	Task3.out
6 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 0 0 0	4

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

1 0 0 0 0 1 1 0 0

1 0 0 1 1 1 0 0 0

0 0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 1 0

0 1 0 1 1 1 0 1 0

0 1 1 1 0 1 0 0 0
Матрицю треба «огородити» з усіх боків.
Розв’язання.
Procedure Poisk;

Begin

K:=0;

For i:=1 to n do

For j:=1 to m do

If (A[I,j]=1) and (A[i-1,j]+A[I+1,j]+A[I,j-1]+A[I,j+1]=1)

then k:=k+1;

k:=k div 2;

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, які...

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