Toshkent axborot texnologiyalari universiteti samarqand filiali

TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI

"Algoritmlarni loyihalash" fanidan

LABARATORIYA ISHI

Bajardi: Keldibekov. I. N
Qabul qildi: Bobonazarov. A. A


SAMARQAND – 2022
3-Mustaqil ish topshiriqlari
Mavzu. Raqamli algoritmlarni tahlil qilishda Furye algoritmi. Spektral tahlil. Dinamik dasturlash.

1	Raqamli axborotlarni qayta ishlashda Furye usuli. Spektral tahlil.
2	Jadval funksiyalarini Furye qatoriga yoyish
3	Statistik axborotlarni qayta ishlashda va prognoz masalalarida dinamik dasturlash usullari

1. 
   Nazariy topshiriqlar: Quyidagi nazariy savollarga javob bering:
   

Topshiriq 1. N - raqamli omadli chiptalar sonini hisoblash talab qilinadi. Eslatib o'tamiz, agar chipta raqamlarining birinchi yarmining yig'indisi ikkinchi yarmining yig'indisiga teng bo'lsa, chipta omadli deb ataladi. Misol uchun, 064109 chiptasi omadli, chunki 0+6+4=1+0+9.
Ma'lumotlarni kiritish. INPUT.TXT kirish faylining bitta satrida N (N ≤ 100) juft natural son - chiptadagi raqamlar soni mavjud.
Chiqish. OUTPUT.TXT chiqish faylining yagona qatorida bitta butun sonni - N-raqamli omadli chiptalar sonini chiqarish kerak.
Misol

№	INPUT.TXT	OUTPUT.TXT
1	4	670
2	6	55252
3	12	39581170420

#include
using namespace std;


const long long osn = 100000000;
const int cif = 15;


vector sum(vector *a, vector *b) {
vector s(cif, 0);
int x = cif - 1;
while ((*a)[x] == 0 && (*b)[x] == 0) x--;
for (int z = 0; z <= x ; z++) s[z] = (*a)[z] + (*b)[z];
for (int z = 0; z <= x ; z++) if (s[z] >= osn) {
s[z + 1] += s[z] / osn;
s[z] %= osn;
}
return s;
}


vector diff(vector *a, vector *b) {
vector s(cif, 0);
int x = cif - 1;
while ((*a)[x] == 0 && (*b)[x] == 0) x--;
for (int z = 0; z <= x; z++) s[z] = (*a)[z] - (*b)[z];
for (int z = 0; z <= x; z++) if (s[z] < 0) {
s[z] += osn;
s[z + 1]--;
}
return s;
}
vector sq(vector *a) {
vector s(cif, 0);
int x = cif - 1;
while ((*a)[x] == 0) x--;
for (int z = 0; z <= x; z++) {
vector p(cif, 0);
for (int c = 0; c <= x; c++) p[c] = (*a)[z] * (*a)[c];
for (int c = 0; c <= x; c++) if (p[c] >= osn) {
p[c + 1] = p[c + 1] + p[c] / osn;
p[c] = p[c] % osn;
}


for (int c = 0; c <= x+1; c++) s[c+z] += p[c];
}
x = cif - 1;
while ((*a)[x] == 0) x--;
for (int c = 0; c <= x; c++) if (s[c] >= osn) {
s[c + 1] = s[c + 1] + s[c] / osn;
s[c] = s[c] % osn;
}
return s;
}


int main() {
ifstream in("input.txt");
ofstream out("output.txt"); out.clear();
long long n;
in >> n;
if (n == 2) {
out << 10; return 0;
}
else n = n / 2;
vector > f(10 * n, vector(cif, 0));
vector > v(10 * n, vector(cif, 0));
v[0][0] = 1;
for (int z = 0; z < 10; z++) f[z][0] = 1;


for (int z = 1; z < n; z++) {
vector s(cif, 0); s[0] = 1;
for (int x = 1, y = (8 + 9 * z); y >= x; x++, y--) {
s = sum(&f[x], &s);
if (x > 9) s = diff(&s, &f[x - 10]);
v[y] = s;
v[x] = s;
}
v[9 + 9 * z][0] = 1;
for (int b = 0; b <= 9 + 9 * z; b++) f[b] = v[b];
}

vector sss(cif, 0);
for (int z = 0; z <= 9 * n; z++) {
vector kv(cif, 0);
kv = sq(&f[z]);
sss = sum(&kv, &sss);
}

int z = cif - 1;
while (sss[z] == 0) z--;
out << sss[z];
while (z > 0) {
z--;
out << setfill('0') << setw(8) << sss[z];
}
return 0;
}
Topshiriq: Nta sondan iborat sonlar ketma-ketligi berilgan. Undan elementlarning minimal sonini olib tashlash kerak, shunda qolganlari qat'iy ortib boruvchi ketma-ketlikni hosil qiladi.

№	INPUT.TXT	OUTPUT.TXT
1	N=6 5 3 6 8 4 9	6 8 9

#include
using namespace std;
int main(){
int n, INF=1e9, ans=0;
cin >> n;
vector v(n);
int d[n+1];
d[0]=-INF;
for ( int i=1; i<=n; i++ ){
d[i]=INF;
}
for ( int &e:v )
cin >> e;
for ( int i=0; ifor ( int j=1; j<=n; j++ ){
if ( d[j-1]d[j]=v[i];
}
}
}
for ( int i=0; i<=n; i++ ){
if ( d[i]!=-INF && d[i]!=INF ){
cout << d[i] << " ";
}
}
}

25

Jadvalda qaysidir mamlakatning so’nggi 10 yildagi (x - yil) yalpi mahsulot (y, mln so’m) dinamikasi ko'rsatilgan. xi 1 2 3 4 5 6 7 8 9 10 yi 178 182 190 199 200 213 220 231 235 242 Bu yerda x va y o’rtasida chiziqli bog’liqlik bor deb faraz qilinadi. y=kx+b chiziqli regressiya parametrlarini eng kichik kvadratlar usuli bilan toping. Keyingi yildagi mumkin bo’lgan yalpi mahsulot hajmini toping.

#include
using namespace std;
int main(){
double s=0, n=10, x0, ans;
cin >> x0;
ans=x0;
for ( int i=1; idouble a;
cin >> a;
s+=fabs(x0-a);
x0=a;
}
s/=n;
cout << ans-s;
}