19-Amaliy mashg`ulot (2-soat) Mavzu: Dinamik programmalash Maqsad

19-Amaliy mashg`ulot (2-soat)

Mavzu: Dinamik programmalash..

Maqsad: Algoritmlardan to`g`ri foydalanishni o`rgatish.

Texnik jihozlar va dasturiy vositalar: Pentium IV kompyuterlari, tarqatma materiallar.

Amaliy mashg`ulot bayoni.

Binomial koeffitsientlarni C (C ++)da hisoblash.

Kombinatorika muammolarini hal qilishda ko'pincha binom koeffitsientlarini hisoblash kerak. Nyuton binomiy i.e. kengayishida binom koeffitsientlari ham qo'llaniladi. Ularni hisoblash uchun siz binomial koeffitsientni ifodalovchi formuladan foydalanishingiz mumkin: yoki takrorlanish formulasidan foydalanish: Nyutonning binomiy va takroriy formulasidan binom koeffitsientlari butun sonlar ekanligi ayon bo'ladi.

Hisob-kitoblar sonini sezilarli darajada qisqartirish usullaridan biri bu Furye va diskret Furier transformatsiyalaridan foydalanishdir.

Furie o'zgartirilishini amalga oshiradigan ko'p sonli kutubxonalarning mavjudligi (tezkor versiyalarning barcha mumkin bo'lgan versiyalarida) dasturlash uchun algoritmlarni amalga oshirish juda qiyin vazifa emas. Amalga oshirilgan algoritmlar FFTTools ochiq manbali kutubxonasining bir qismidir.

Real o'zgaruvchining f funktsiyasining Fyuri o'zgarishi yaxlit va quyidagi formula bilan berilgan:

Turli manbalar yuqorida aytib o'tilganlardan farqli bo'lgan ta'riflarni, integral oldida koeffitsientni va eksponent oldidagi “-” belgisini tanlashi mumkin. Ammo barcha xususiyatlar bir xil bo'ladi, garchi ba'zi formulalarning ko'rinishi o'zgarishi mumkin. Bundan tashqari, ushbu kontseptsiyaning turli xil umumlashmalari mavjud.

Diskret Furye konvertatsiyasi.

Diskret Furie transformatsiyasi raqamli signallarni qayta ishlash algoritmlarida, shuningdek diskret signal chastotalarini tahlil qilish bilan bog'liq boshqa sohalarda keng qo'llaniladigan Furye transformatsiyalaridan biridir. Diskret Furye konvertatsiyasi kirish sifatida diskret funktsiyani talab qiladi. Bunday funktsiyalar ko'pincha diskretizatsiya orqali yaratiladi. Diskret Furye konversiyalari qisman differentsial tenglamalarni yechishga va konvulsiyalar kabi operatsiyalarni bajarishga yordam beradi. Diskret Furye transformatsiyalari statistikada, vaqt ketma-ketligini tahlil qilishda ham faol qo'llaniladi. Ko'p o'lchovli diskret Furier konversiyalari mavjud.

Formula diskret akslantirishlar.

To'g'ridan-to'g'ri akslantirish:

Teskari akslantirish:

Diskret Furye transformatsiyasi vaqt namunalarining vektorini bir xil uzunlikdagi spektral namunalar vektoriga aylantiradigan chiziqli o'zgarishdir. Shunday qilib, transformatsiyani simmetrik kvadrat matritsani vektorga ko'paytirish kabi amalga oshirish mumkin:

Ikkala funktsiyani birlashtirish. F va G ikkita funktsiyalarning birikishi FxG funktsiyasi:

FхG(t) = SUM F(i)*G(j)|i+j=t

Konvolyutsiyani hisoblash uchun fyurierlar.

Furye transformatsiyasining ajoyib xususiyatlaridan biri bu aniq dalil asosida (klassik formuladan foydalangan holda) yoki cheklangan halqada (diskret transformatsiyalardan foydalanganda) aniqlangan ikkita funktsiyaning o'zaro bog'liqligini tezda hisoblash qobiliyatidir.

Shunga o'xshash xususiyatlar ko'plab chiziqli o'zgarishlarga xos bo'lsa-da, amaliy foydalanish uchun, konvulsion operatsiyani hisoblash uchun, bizning ta'rifimizga ko'ra, formuladan foydalaniladi

FxG = BFT (FFT (F) * FFT (G))

Bu yerda

FFT to'g'ridan-to'g'ri Furye transformatsiyasi operatsiyasi.

BFT teskari Furye transformatsiyasi operatsiyasi.

Tenglikning to'g'riligini tekshirish juda oson - Fureni o'zgartirish formulalarini aniq ravishda almashtirish va natijada olingan formulalarni kamaytirish.

Binomial koeffitsientlar.

F(x)=1+x ko'paytmasini va uning nol marta yig'ilishini hisobga oling.

Fx..xF=SUM S(i,n-1)*x^i=BFT(FFT(F)*...*FFT(F))=BFT(FFT(F)^(n-1)).

Ya'ni C(i, n-1) binomiy koeffitsientlarini ko'p (1 + x) ^ (n-1) koeffitsientlarining qiymatlaridan olish mumkin.

Dasturi quyidagicha:

using System;

using System.Drawing;

using System.Linq;

using System.Numerics;

namespace FFTTools {

public class BinomialBuilder : BuilderBase, IBuilder {

///

/// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.

///

public void Dispose()

{

}

public static void GetLongs(long[] array, long x = 1) {

var n = array.Length - 1;

if (array.Length > 0) array[0] = 1;

for (var i = 0; i < n; i++)

array[i + 1] = x*array[i]*(n - i)/(i + 1);

}

public static void GetDoubles(double[] array, double x = 1.0) {

var complex = new Complex[array.Length];

if (array.Length > 0) complex[0] = Complex.One;

if (array.Length > 1) complex[1] = x;

if (array.Length > 0) {

Fourier(complex, FourierDirection.Forward);

complex = complex.Select(

value => Complex.Pow(value, array.Length - 1)/array.Length).ToArray();

Fourier(complex, FourierDirection.Backward);

}

var index = 0;

foreach (var value in complex) array[index++] = value.Real;

}

public Bitmap ToBitmap(Bitmap source){

throw new NotImplementedException();

}

}

}
Topshiriq.

2. Birinchi masalada keltirilgan formula yordamida rekursiv fact(N) funktsiyasini ishlab chiqing. Uning yordamida hisoblang:



7. Berilgan N ta elementdan K tasining kombinatsiyalari C(N, K) ni hisoblash uchun combin(N, K) funktsiyasini quring. Bunda quyidagi rekkurent munosabatlardan foydalanish mumkin:



Funksiyaning barcha parametrlari butun sonlar. N natural soni K ning 5 ta qiymatlari uchun C(N, K) larni hamda har bir son uchun rekursiv murojaatlar sonini aniqlang.

8. Berilgan N ta elementdan K tasining kombinatsiyalari C(N, K) ni hisoblash uchun combin2(N, K) funktsiyasini quring. Bunda quyidagi rekkurent munosabatlardan foydalanish mumkin:



Funktsiyaning barcha parametrlari butun sonlar. N ning qiymati 20 dan katta bo`lmasin. Rekursiv murojaatlar sonini kamaytirish uchun C(N, K) ning hisoblangan qiymatlarini saqlash uchun ikki o`lchovli yordamchi massiv kiriting. Combin2 funksiyasini hisoblashda zarur bo`lganda bu massiv elementlaridan foydalash mumkin. N natural soni K ning 5 ta qiymatlari uchun C(N, K) larni hamda har bir son uchun rekursiv murojaatlar sonini aniqlang.
Adabiyotlar

1. 
   Кнут Д. Исскуство программирование. В 4 томах. –М:Вильямс, 2013. -963 .
   
2. 
   Левитин А. И., Ананий В. Алгоритмы: введение в разработку и анализ.–М.:Вильямс, 2006 г. -576 с.
   
3. 
   Макконел Дж. Основы совремнных алгоритмов. –М:Техносфера, 2004. -368 с
   
4. 
   Окулов А. программирование в алгоритмах. М.: Бином, лаборатория знаний, 2002 г. -341 с.
   
5. 
   Уоррен Г. Алгоритмические трюки для программистов. –М:Вильямс, 2004. -282 с.