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

Скачати 435.43 Kb.

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

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

1 2 3 4 5 6 7 8 9 10

Точки перетину

Є дві паралельні лінії. На першій з них вибрано А точок, а на другій В точок. Будь-які дві точки з різних прямих з’єднані відрізком. Точки на прямих вибрані так, що кількість точок перетину утворених відрізків щонайбільша. Обчислити цю кількість. На вході задається два числа А та В (

.

Ідея розв’язання. Якщо провести дослідження, то можна вивести необхідну формулу

Ланцюговий дріб

Задано натуральні числа А і В – знаменник та чисельник звичайного дробу. Скласти програму знаходження ланцюгового дробу

., де q_i - прості числа. Відповідь отримати у вигляді:

.

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

Var m, n, a, b, c, I, j, j1:integer;

Otv: array [1..200] of integer;

Begin

Readln(a,b);

For j:=1 to 200 do otv[j]:=0;

M:=a; n;=b; i:=1;

Repeat

Otv[i]:= m div n; {пошук наступного q}

If otv[i]>1 then {пошук найближчого простого числа}

Begin

J:=otv[i]+1;

Repeat

J:=j-1;

J1:=j;

Repeat

J1:=j1-1

Until (j mod j1=0) or (j1=1)

Until j1=1;

Otv[i]:=j; {збереження відповіді}

End;

C:=m; {“перевертання” дробу}

M:=n;

N:=c-otv[i]*n;

I:=i+1

Until n=0;

Write(a, ‘/’, b, ‘=[‘);

For j:=1 to i-2 do write(otv[j],’, ‘);

Writeln(otv[i-1],’]’);

End.

Ознаки подільності

Ознаки подільності стануть вам в нагоді, якщо вам знадобиться обробляти багатоцифрові числа.

Комбінаторні сполучення

Розв’язання деяких олімпіадних задач передбачає вміння підраховувати кількість та генерувати комбінаторні сполучення. Розглянемо спочатку підрахунок кількості комбінаторних сполучень. Нагадаємо відомі формули:

Кількість переставлень

Кількість розміщень

Кількість сполучень

Підрахунок кількості комбінаторних сполучень

Зробіть самі програми підрахунку кількості переставлень, розміщень та сполучень за наведеними формулами. Оцініть за швидкістю роботи.

Генерація всіх можливих переставлень. Задача1.

Отримати всі можливі переставлення з N перших натуральних чисел.

Ідея розв’язання. Рекурсивна функція Chang усіма можливими способами намагається ставити число у позицію з номером ind масиву перестановок таким чином, щоб числа у перестановці не повторювалися (за цим “слідкує” множина w) Якщо множина використаних у перестановці чисел містить усі можливі числа, виконується виведення отриманої пеерстановки. У протилежному випадку організується поступове додавання чергового елементу до масиву перестановоу у тілі циклу від 1 до N з перевіркою множини w та викликом рекурсивної функції Chang.

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

Варіант 1:

Program perest;

Type ij=set of byte;

Const n=4;

Var f,k:integer;

M:array [1..n] of byte;

Procedure Chang(w:ij; ind:integer);

Var i,j:byte;

Begin

If w=[1..n] then {якщо переставлення сгенеровано }

Begin

Inc(f);

For k:=1 to n do write(m[k]); {друк відповіді}

Writeln;

End

Else

For j:=1 to n do {генеруємо переставлення}

If not(j in w) then

Begin

M[ind]:=j; {додаємо наступне число}

Chang(w+[j],ind+1);

End;

End;

Begin

F:=0; {кількість переставлень}

Chang([],1); {М- масив переставлень}

End.
Варіант 2:

Ідея розв’язання. Цей варіант відрізняється від попереднього тим, що множина s позначає невикористані у перестановці числа. Коли перестановку буде згенеровано, множина стане порожньою, перестановку буде надруковано.

Program perest2;

Const n=4;

Type intSet=set of 1..n;

Var M:array [1..n] of byte;

Procedure Chang2(s:intSet; k:integer);

Var i:byte;

Begin

For i:=1 to n do

If i in s then

Begin

M[k]:=i;

Chang2(s-[i],k+1);

End;

If s=[] then For i:=1 to n do write(m[i]);

Writeln;

End

Begin

Chang2([1..n],1); {М- масив переставлень }

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

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