Guruh talabasi Abdullayev Jamshidbekning Algoritmlarni loyihalash fanidan laboratoriya ishi

911-20 guruh talabasi Abdullayev Jamshidbekning
Algoritmlarni loyihalash fanidan laboratoriya ishi

Tajriba ishi 10

Furye kengaytirish algoritmlari

Furye seriyasi frantsuzlar sharafiga nomlangan

matematik Jan-Batist Jozef Furye (1768-1830),
o‘rganishga muhim hissa qo‘shgan
dastlabkidan keyin trigonometrik qator
Leonhard Euler, Jan Leron tadqiqotlari
d'Alembert va Daniel Bernoulli. Furye seriyani taqdim etdi
issiqlik tenglamasini yechish uchun
boshingizni yozish orqali metall plastinka
uning “Taqsimotni eslash” asari bilan yakunlanadi
qattiq moddalardagi issiqlik" ("Taqsimotga oid risola
qattiq moddalarda isitiladi") va nashr
Issiqlikning analitik nazariyasi (Théorie analytique de la
chaleur) 1822 yilda. Xotira tahlilni taqdim etadi

Birinchidan

bu buyuk kashfiyot haqida e'lon qilindi
Furye 1807 yilda frantsuz akademiyasi oldida[4]
.
Davriy funktsiyani kengaytirish uchun dastlabki g'oyalar
Oddiy tebranish funktsiyalari yig'indisi 3 ga qarang
miloddan avvalgi asr, qadimgi astronomlar qachon
sayyoralar harakatining empirik modelini taklif qildi,
oilalar va epitsikllarga asoslangan.

Analog signallarni tahlil qilishda bo'lgani kabi, diskret signallar ham vaqt va chastota sohalarida ifodalanishi mumkin. Hozirgi vaqtda diskret signalni qayta ishlash ko'pincha chastotalar domenida amalga oshiriladi, bu raqamli uskunalar hajmi va ishlov berish vaqtining sezilarli darajada qisqarishi bilan bog'liq.

Spektral zichlikka ega bo'lgan davomiylikka ega bo'lgan analog impuls signali diskret ishlovga duchor bo'lsin (9.16-rasm, a, b). Nazariy jihatdan, signal delta funktsiyalarining davriy ketma-ketligi bilan tanlanadi deb taxmin qilish mumkin.

,

(9,35)

bu erda Kotelnikov teoremasiga mos keladigan kerakli namunalar soni .

(9.32) dagi yig'indi chegaralarini 0 dan ga o'rniga qo'yib, formulalar hajmini soddalashtirish va kamaytirish uchun bu erda va pastda almashtiring , biz diskret signalning ifodasini yozamiz (9.16-rasm, f).

...

(9,36)

(9.36) formulaga asoslanib, ushbu diskret signalning spektri chastota o'qi bo'ylab davriy tuzilishga ega degan xulosaga kelishimiz mumkin (9.16-rasm, d). Diskret signalni davriy ravishda interval bilan aqliy ravishda davom ettiramiz (9.16-rasm, e).

Rasm.9.16. DFT chiqishi uchun grafiklar:
a, b - analog signal va uning spektri; c, d - diskret signal va uning spektri; d - diskret signalning davriy ketma-ketligi; e - signalning DFT 
, . 
Davriy uzluksiz signallarni ko'rsatishga o'xshash
, bu yerda th garmonikaning kompleks amplitudasi . Diskret funktsiyani kompleks Furye qatorida kengaytirish mumkin.

Misol
Bir o’lchamli sonli massiv berilgan. Massiv elementlari o’sish tartibida berilgan. 

Keyin m ta son beriladi. Bu sonlardan nechtasi berilgan massivda uchrashini topuvchi dastur tuzing.
Kiruvchi ma’lumotlar
Birinchi qatorda bitta butun n soni−massiv elementlari soni berilgan(1≤n≤10⁵).
Ikkinchi qatorda n ta son−massiv elementlari o’sish tartibda bitta probel bilan ajratib berilgan. Uchinchi qatorda butun m−so’rovlar soni berilgan(1≤m≤10⁵). Keyingi m ta qatorda har birida bittadan son izlanayotgan son berilgan. Massiv elementlari va izlanayotgan sonlar butun va modul jihatdan 10⁹ dan oshmaydi.
Chiquvchi ma’lumotlar
Birinchi satrda bitta sonni so’ralgan sonlardan nechtasi berilgan massivdauchrashini chiqaring. Agar 
hech biri uchramasa 0 chiqaring.
Misollar

№	Kiruvchi ma’lumotlar	Chiquvchi ma’lumotlar
1	5 1 4 6 10 20 4 1 25 10 10	3

#include

using namespace std;
int main() {
int n,m,L,R,k=0;
cout<<"n="; cin>>n;
int a[n+1];
for(int i=1; i<=n; i++) {
cin>>a[i];
}
cout<<"m="; cin>>m;
int b[m+1];
for(int i=1; i<=m; i++) {
cin>>b[i];
}
for(int i=1; i<=m; i++) {
L=1; R=n+1;
while(R-L>1) {
int m=(R+L)/2;
if(a[m]<=b[i])
L=m;
else {
R=m;
} }
if(a[L]==b[i])
k++;
}
cout<}