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

Скачати 435.43 Kb.

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

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

1 2 3 4 5 6 7 8 9 10

Ділення поліному на поліном

У файлі task3.in у першому рядку записано числа N та M – степені поліномів А та В. В другому рядку через пробіл записано N+1 коефіцієнтів поліному А, заданому у вигляді:

. У третьому рядку записано M+1 коефіцієнтів поліному В. скласти програму обчислення частки і остачі від ділення поліному а на поліном В. Результат записати у файл task3.out: у першому рядку коефіцієнти поліному-частки, у другому рядку коефіцієнти поліному-остачі.

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

const n1=100;

var a,b,c:array[0..n1] of real;

i,j,n,m,k:integer;

f:text;

procedure input;

begin

assign(f,’task3.in’);

reset(f);

readln(f,n,m);

for i:=0 to n-1 do read(f,a[i]);

readln(f,a[n]);

for i:=0 to m do read(f,b[i]);

close(f);

k:=n-m;

end;

procedure output;

begin

assign(f,’task3.out’);

rewrite(f);

writeln(f, k);

for i:=0 to k do write(f, c[i]:8:4,' '); writeln(f);

for i:=k+1 to n do write(f, a[i]:8:4,' ');writeln(f);

close(f);

end;

begin

input;

i:=0;

repeat

c[i]:=a[i]/b[0];

for j:=1 to m do a[i+j]:=a[i+j]-b[j]*c[i];

i:=i+1

until i>k;

output;

end.

«Закодовані» малюнки

Опрацювання матриць, що складаються з 0 та 1.

Метод пошуку «ключових» елементів. Серед олімпіадних завдань доволі часто зустрічаються задачі опрацювання малюнків, що зберігаються в нульовий матриці у вигляді поряд розташованих одиниць. Існує декілька прийомів, які дають можливість зменшити час розв’язання таких задач. Один з цих прийомів дозволяє не відволікатися на перевірку «граничних» елементів. Це досягається за допомогою «огороджування» матриці рядками та стовпчиками, що складаються з нулів. Другій прийом – пошук так званих «ключових» елементів. Розглянемо, як використовувати ці прийоми на практиці.

Кути

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

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

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

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

Task1.in	Task1.out
8 10 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0	6

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

1 0 0 1 1 1 1 0 0 0

1 1 0 0 0 0 1 0 0 0

0 0 0 0 1 0 0 0 0 0

0 1 0 0 1 0 0 0 0 0

1 1 0 0 1 1 1 1 0 0

0 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 0 1 1 1 0

1 1 1 1 1 0 0 0 0 0

1 0 0 0 0 0 0
Тобто треба порахувати кількість таких елементів. Матрицю треба «огородити» з усіх боків.
Розв’язання.
Program task1;

Var f:text;

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

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

Begin

Assign (f,’task1.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; A[I,m+1]:=0;

End;

For j:=0 to m+1 do

Begin

A[0,j]:=0; A[n+1,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,j+1]=1) and ((A[i-1,j]=1) or (A[i+1,j]=1)))

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

then k:=k+1;

End;

Procedure Out;

Begin

Assign (f,’task1.out’);

Rewrite(f);

Writeln(f,k);

Close(f);

End;

Begin

Init;

Ograda;

Poisk;

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

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