Matritsada qidiruv algoritmlari
![nashrda tasvirlanadi. Shaklda ko'rsatilgan nurga nisbatan. ichki kuchlarning
diagrammalarini qurishda matritsani hisoblash algoritmi quyidagicha yoziladi.
Tarmoqli quvur liniyasidagi kuchlarni haroratni isitishdan (og'irlik yukining
ta'siri hisobga olinmagan) aniqlash uchun muallif aralash usulning matritsali
algoritmini taklif qildi : tizimning alohida tarmoqlari kuch usuli yordamida
hisoblab chiqilgan, keyin esa deformatsiya usulining tenglamalari tuzildi va
yechildi, buning natijasida tarmoq tugunlarida noma'lum deformatsiyalar
aniqlandi. Bunday tizimlarda ko'paytiriladigan matritsaning elementlari har
bir tsiklda almashtirilishi va chiziqli tenglamalar tizimini echish uchun
to'g'ridan-to'g'ri matritsali algoritmlarni amalga oshirish mumkinligi tufayli
yuqori ishlov berish tezligi ta'minlanadi . Bu usullarning iterativ usullardan
afzalligi shundaki, ular ma'lum miqdordagi tsikllar doirasida amalga
oshiriladi, shu bilan birga kerakli takrorlashlar soni odatda oldindan ma'lum
emas. A [/, / r] ning ixtiyoriy elementiga kirish uchun sarflangan vaqt, agar
har bir satr yoki ustunda elementlar juda kam bo'lsa, oqilona chegaralar ichida
qoladi; bundan tashqari, ko'pchilik matritsa algoritmlari o'zboshimchalik bilan
elementlarga kirishdan foydalanmaganligi sababli, matritsaning ketma-ket
o'tishi bilan bog'liq vakillik tezlikni biroz yo'qotishiga olib keladi. Konturlarni
o'z ichiga olgan yo'llarni yo'q qilishning aniq matritsa usullari
tasvirlangan; ammo bu usullar, masalan, tasvirlangan ketma-ket tarmoqdan
o'tish algoritmi juda katta hajmdagi hisob-kitoblarni talab qiladi. Shuning
uchun, quyida tavsiflangan
taxminiy matritsa algoritmi mos bo'lishi
mumkin. Ilgari aytilganlarga asoslanib, eksperimental tarzda tasdiqlangan
ketma-ketlik tarmog'ida har bir makroskopik bosqich tanlangan atomlar
guruhining oddiy o'tish jarayoni sifatida namoyon bo'lishi aniq.Ko'rsatilgan
kompyuter dasturi - oddiy matritsali algoritm - teskari masalani osonlikcha
hal qiladi: berilgan makroskopik bosqich uchun u mumkin bo'lgan
reaktsiyalarni aniqlaydi, tanlaydi. Ushbu makroskopik bosqichni amalga
oshiradigan barcha elementar reaktsiyalar mexanizmi.
2.1.Matritsada muntazam qidiruv
Algoritmni ishlab chiqishni davom ettirishdan oldin, oddiy misolni ko'rib
chiqaylik:
15 20 40 85
20 35 80 95
30 55 95 105
40 80 100 120
1-jadval
Aytaylik, biz 55-elementni qidiryapmiz. Uni qanday topish mumkin?
Agar satr va ustunning birinchi elementlarini ko'rib chiqsak, biz izlayotgan
elementning joylashuvini qidirishni boshlashimiz mumkin. Shubhasiz, 55 dan
8](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_8.png)
![katta qiymat bilan boshlanadigan ustunda 55 bo'lishi mumkin emas, chunki
minimal element har doim ustunning boshida bo'ladi. Bundan tashqari, biz 55
ning o'ng tomonda bo'lishi mumkin emasligini bilamiz, chunki har bir
ustunning birinchi elementining qiymati chapdan o'ngga ortadi. Shuning
uchun, agar ustunning birinchi elementi x dan katta ekanligini topsak , chapga
o'tishimiz kerak.
Xuddi shunday tekshiruv satrlar uchun ham ishlatilishi mumkin. Agar biz
birinchi element qiymati x dan katta bo'lgan satr bilan boshlagan bo'lsak,
yuqoriga ko'tarilishimiz kerak.
Xuddi shunday mulohazalardan ustunlar yoki satrlarning oxirgi
elementlarini tahlil qilishda foydalanish mumkin. Agar ustun yoki satrning
oxirgi elementi x dan kichik bo'lsa, x ni topish uchun pastga (satrlar uchun)
yoki o'ngga (ustunlar uchun) harakat qilish kerak. Bu shunday, chunki oxirgi
element har doim maksimal bo'ladi.
Keling, ushbu barcha kuzatuvlardan yechim yaratish uchun foydalanamiz:
Agar ustunning birinchi elementi x dan katta bo'lsa , u holda x chap
ustunda joylashgan.
Agar ustunning oxirgi elementi x dan kichik bo'lsa , u holda x o'ng
ustunda joylashgan.
Agar satrning birinchi elementi x dan katta bo'lsa , x uning ustidagi
satrda bo'ladi.
Agar satrning oxirgi elementi x dan kichik bo'lsa , x uning ostidagi
satrda bo'ladi.
Keling, ustunlar bilan boshlaylik.Biz o'ng ustundan boshlashimiz va chapga
o'tishimiz kerak. Bu shuni anglatadiki, taqqoslash uchun birinchi element [0]
[c-1] bo'ladi , bu erda c - ustunlar soni. Ustunning birinchi elementini x
(bizning holatimizda 55) bilan taqqoslab, x 0,1 yoki 2 ustunlarda bo'lishi
mumkinligini tushunish oson. Keling , [0][2] dan boshlaylik .
Bu element to liq matritsadagi qatorning oxirgi elementi bo lmasligi mumkin,ʻ ʻ
lekin u submatritsadagi qatorning oxiri hisoblanadi. Va submatritsa bir xil
shartlarga bo'ysunadi. [0][2] elementining qiymati 40 ga teng, ya'ni u bizning
elementimizdan kamroq, ya'ni biz pastga siljishimiz kerakligini bilamiz.
Endi submatritsa quyidagi shaklni oladi (kulrang hujayralar tashlanadi):
15 20 40 85
20 35 80 95
30 55 95 105
9](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_9.png)
![Quyidagi kod ushbu algoritmni amalga oshiradi:
public static boolean findElement( int [][] matrix , int elem ) {
int row = 0;
int col = matrix [0]. length - 1;
while ( row < matrix . length && col >= 0) {
if ( matrix [ row ][ col ] == elem ) {
return true;
} else if ( matrix [ row ][ col ] > elem ) {
col --;
} else {
row ++;
}
}
return false;
}
Muammoni hal qilishning yana bir yondashuvi ikkilik qidiruvdir. Biz
murakkabroq kodni olamiz, lekin u xuddi shu qoidalarga asoslanadi.
2.2.Matritsada ikkilik qidiruv
Keling, misolimizga yana qaraylik:
15 20 70 85
20 35 80 95
30 55 95 105
40 80 100 120
3-jadval
Biz algoritm samaradorligini oshirishni xohlaymiz. Keling, o'zimizga savol
beraylik: element qayerda bo'lishi mumkin?
Bizga barcha satrlar va ustunlar tartiblanganligi aytiladi. Bu [i][j] elementi
0 va j ustunlar orasidagi i qatordagi elementlardan va 0 va i-1 qatorlar
orasidagi j qatordagi elementlardan kattaroq ekanligini bildiradi . Boshqa so'z
bilan:
a[i][0] <= a[i][1] <= ... <= a[i][ji] <= a[i][j] a[0][j] <= a
[ 1][j] <= ... <= a[i-1][j] <= a[i][j]
Matritsaga qarang: quyuq kulrang hujayradagi element boshqa tanlangan
elementlardan kattaroqdir.
15 20 70 85
20 35 80 95
30 55 95 105
40 80 100 120
4-jadval
11](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_11.png)
![Oq hujayralardagi elementlar tartiblangan. Ularning har biri chap elementdan
ham, yuqoridagi elementdan ham kattaroqdir. Shunday qilib, tanlangan
element kvadratdagi barcha elementlardan kattaroqdir.
15 20 70 85
20 35 80 95
30 55 95 105
40 80 100 120
5-jadval
Biz qoidani shakllantirishimiz mumkin: matritsada tanlangan har qanday
to'rtburchakning pastki o'ng burchagida eng katta element bo'ladi.
Xuddi shunday, yuqori chap burchak har doim eng kichik bo'ladi. Quyidagi
diagrammadagi ranglar elementlarning tartiblanishi haqidagi ma'lumotlarni
aks ettiradi (och kulrang < oq < to'q kulrang):
15 20 70 85
20 35 80 95
30 55 95 105
40 80 100 120
6-jadval
Keling, asl muammoga qaytaylik. Aytaylik, 85-elementni topishimiz
kerak.Diagonalga qarasak, 35 va 95- elementlarni ko‘ramiz.Bundan 85-
elementning joylashuvi haqida qanday ma’lumotlarni olishimiz mumkin?
15 20 70 85
20 35 80 95
30 55 95 105
40 80 100 120
7-jadval
85 quyuq kulrang maydonda bo'lishi mumkin emas, chunki 95 element yuqori
chap burchakda joylashgan va bu kvadratdagi eng kichik elementdir.
85 ochiq kulrang maydonga tegishli emas, chunki 35 element pastki o'ng
burchakda joylashgan.
85 ikkita oq maydondan birida bo'lishi kerak.Shunday qilib, biz to'rimizni
to'rtta kvadrantga ajratamiz va pastki chap va yuqori o'ng kvadrantlarda
qidiramiz. Ularni kvadrantlarga bo'lish va keyinroq qidirish mumkin.
E'tibor bering, diagonal tartiblangan, ya'ni biz ikkilik qidiruvdan samarali
foydalanishimiz mumkin.
Quyidagi kod ushbu algoritmni amalga oshiradi:
public Coordinate findElement ( int [][] matrix , Coordinate origin , Coordinate
dest , int x ) {
if ( ! origin . inbounds ( matrix ) || ! dest . inbounds ( matrix )) {
return null ;
12](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_12.png)
![}
if ( matrix [ origin . row ][ origin . column ] == x ) {
return origin ;
} else if ( ! origin . isBefore ( dest )) {
return null ;
}
Coordinate start = ( Coordinate ) origin . clone ();
int diagDist = Math . min ( dest . row - origin . row , dest . column - origin . column );
Coordinate end = new Coordinate ( start . row + diagDist , start . column +
diagDist );
Coordinate p = new Coordinated ( 0 , 0 );
while ( start . isBefore ( end )) {
р . setToAverage ( start , end );
if ( x > matrix [ p . row ][ p . column ]) {
start . row = p . row + 1 ;
start . column = p . column + 1 ;
} else {
end . row = p . row - 1 ;
end . column = p . column - 1 ;
}
}
return partitionAndSearch ( matrix , origin , dest , start , x );
}
public Coordinate partitionAndSearch ( int [][] matrix ,
Coordinate origin . Coordinate dest , Coordinate pivot , int elem ) {
Coordinate lowerLeftOrigin = new Coordinate ( pivot . row , origin . column );
Coordinate lowerLeftDest = new Coordinate ( dest . row , pivot . column - 1 );
Coordinate upperRightOrigin = new Coordinate ( origin . row , pivot . column );
Coordinate upperRightDest = new Coordinate ( pivot . row - 1 , dest . column );
Coordinate lowerLeft = findElement ( matrix , lowerLeftOrigin ,
lowerLeftDest , elem );
if ( lowerLeft == null ) {
return findElement ( matrix , upperRightOrigin , upperRightDest , elem );
}
return lowerLeft ;
}
public static Coordinate findElement ( int [][] matrix , int x ) {
Coordinate origin = new Coordinate ( 0 , 0 );
Coordinate dest = new Coordinate ( matrix . length - 1 , matrix [ 0 ]. length - 1 );
13](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_13.png)
![return findElement ( matrix , origin , dest , x );
}
public class Coordinate implements Cloneable {
public int row ;
public int column ;
public Coordinate ( int r , int c ) {
row = r ;
column = c ;
}
public boolean inbounds ( int [][] matrix ) {
return row >= 0 && column >= 0 &&
row < matrix . length && column < matrix [ 0 ]. length ;
}
public boolean isBefore ( Coordinate p ) {
return row <= p . row && column <= p . column ;
}
public Object clone () {
return new Coordinate ( row , column );
}
public void setToAverage ( Coordinate min , Coordinate max ) {
row = ( min . row + max . row ) / 2 ;
column = ( min . column + max . column ) / 2 ;
}
}
Ushbu kodni birinchi marta to'g'ri yozish juda qiyin.Esda tutingki, siz kodni
usullarga ajratish orqali hayotingizni osonlashtirasiz. Dasturlarni yozishda
asosiy sohalarga e'tibor bering. Va siz har doim hamma narsani birlashtira
olasiz.
2.3.Matritsada qidirsh algoritm dastulari c++ va phytonda kodlari tahlili
Saralangan matritsali mat[n][m] va "x" elementi berilgan. Agar mavjud
bo'lsa, x ning matritsadagi o'rnini toping, aks holda -1 ni chop eting. Matritsa
shunday tartiblanganki, qatordagi barcha elementlar ortib borish tartibida va
“i” qatori uchun, bu yerda 1 <= i <= n-1, “i” qatorining birinchi elementi dan
katta yoki teng. "i-1" qatorining oxirgi elementi. Yondashuv O (log n + log m)
vaqt murakkabligiga ega bo'lishi kerak.
Misollar:
Kirish : mat[][] = { {1, 5, 9},
{14, 20, 21},
14](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_14.png)
![{30, 34, 43} }
x = 14
Chiqish: topilgan (1, 0)
Kirish : mat[][] = { {1, 5, 9, 11},
{14, 20, 21, 26},
{30, 34, 43, 50} }
x = 42
Chiqish: -1
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 4; // no. of rows
int m = 5; // no. of columns
int a[n][m] = {{0, 6, 8, 9, 11},
{20, 22, 28, 29, 31},
{36, 38, 50, 61, 63},
{64, 66, 100, 122, 128}};
int k = 31; // element to search
map<int,pair<int,int>>mp;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(k==a[i][j]){
cout<<"Found at ("<<i<<","<<j<<")"<<endl;
}
mp[a[i][j]]={i,j};
}
}
if(mp.find(k)!=mp.end()){
//cout<<"("<<mp[k]<<",)"<<endl;
cout<<"This is how we can found using mapping: "<<endl;
cout<<"("<<mp[k].first<<","<<mp[k].second<<")"<<endl;
}else{
cout<<"Not Found"<<endl;
}
return 0;
}
Vaqt murakkabligi : O(n+m), O'tish uchun.
15](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_15.png)
![Phytonda kodi:
n = 4
m = 5
a = [[0, 6, 8, 9, 11],
[20, 22, 28, 29, 31],
[36, 38, 50, 61, 63],
[64, 66, 100, 122, 128]]
k = 31
mp = {}
for i in range(n):
for j in range(m):
if(k==a[i][j]):
print("Found at (", i, ",", j, ")")
mp[a[i][j]] = [i, j]
if k in mp:
cout<<"("<<mp[k]<<",)"<<endl;
print("This is how we can found using mapping: ")
print("(", mp[k][0], ",", mp[k][1], ")")
else:
print("Not Found")
2.4.Matritsalarni tartiblash algoritm
nxn matritsasi berilgan. Muammo berilgan matritsani qat'iy tartibda
tartiblashdir. Bu erda qat'iy tartib matritsaning shunday tartiblanganligini
anglatadiki, qatordagi barcha elementlar o'sish tartibida va "i" qatori uchun,
bu erda 1 <= i <= n-1, "i" qatorining birinchi elementi. "i-1" qatorining oxirgi
elementidan katta yoki unga teng.
Kirish : mat[][] = { {5, 4, 7},
{1, 3, 8},
{2, 9, 6} }
Chiqish: 1 2 3
4 5 6
7 8 9
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<vector<int>>v{{5, 4, 7},{1, 3, 8},{2, 9, 6}};
int n=v.size();
16](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_16.png)
![vector<int>x;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
x.push_back(v[i][j]);
}
}
sort(x.begin(),x.end());
int k=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
v[i][j]=x[k++];
}
}
cout<<"Sorted Matrix Will be:"<<endl;
for(auto it:v){
for(auto vt:it){
cout<<vt<<" ";
}cout<<endl;
}
return 0;
}
Phytondagi kodi:
v = [[5,4,7], [1,3,8], [2,9,6]]
n = len(v)
x = []
for i in range(n):
for j in range(n):
x.append(v[i][j])
x.sort()
k = 0
for i in range(n):
for j in range(n):
v[i][j] = x[k]
k += 1
print("Sorted Matrix will be: ")
for i in range(n):
for j in range(n):
print(v[i][j], end=" ")
print("")
17](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_17.png)
![III BOB.Matritsalarni qo’shish,ayirishva ko’paytirish
3.1.Matirtsalarni qo’shish
# include <iostream>
using namespace std ;
int main ()
{
int r, c, a[ 100 ][ 100 ], b[ 100 ][ 100 ], sum[ 100 ][ 100 ], i, j;
cout << " Qatorlar sonini kiriting (1 dan 100 gacha): " ;
cin >> r;
cout << " Ustunlar sonini kiriting (1 dan 100 gacha): " ;
cin >> c;
cout << endl << " 1-matritsaning elementlarini kiriting: " << endl ;
for (i = 0 ; i < r; ++i)
for (j = 0 ; j < c; ++j)
{
cout << "a elementni kiriting" << i + 1 << j + 1 << " : " ;
cin >> a[i][j];
}
cout << endl << "2-matritsaning elementlarini kiriting: " << endl ;
for (i = 0 ; i < r; ++i)
for (j = 0 ; j < c; ++j)
{
cout << "b elementni kiriting:" << i + 1 << j + 1 << " : " ;
cin >> b[i][j];
}
for (i = 0 ; i < r; ++i)
for (j = 0 ; j < c; ++j)
sum[i][j] = a[i][j] + b[i][j];
cout << endl << "2 ta matritsani yigindisi: " << endl ;
for (i = 0 ; i < r; ++i)
for (j = 0 ; j < c; ++j)
{
cout << sum[i][j] << " " ;
if (j == c - 1 )
cout << endl ;
}
return 0 ;
}
18](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_18.png)
![3.2. Matirtsalarni ayirish
#include <bits/stdc++.h>
using namespace std;
#define N 4
void subtract(int A[][N], int B[][N], int C[][N])
{
int i, j;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
C[i][j] = A[i][j] - B[i][j];
}
// Driver code
int main()
{
int A[N][N] = { {1, 1, 1, 1},
{2, 2, 2, 2},
{3, 3, 3, 3},
{4, 4, 4, 4}};
int B[N][N] = { {1, 1, 1, 1},
{2, 2, 2, 2},
{3, 3, 3, 3},
{4, 4, 4, 4}};
int C[N][N];
int i, j;
subtract(A, B, C);
cout << "Result matrix is " << endl;
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
cout << C[i][j] << " ";
cout << endl;
}
return 0;
}
19](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_19.png)
![3.3.Matritsalarni ko’paytirish
# include <iostream>
using namespace std ;
int main () {
int a[ 10 ][ 10 ], b[ 10 ][ 10 ], mult[ 10 ][ 10 ], r1, c1, r2, c2, i, j, k;
cout << "Birinchi matritsa uchun satr ustunlarini kiriting: " ;
cin >> r1 >> c1
cout << " Ikkinchi matritsa uchun satr ustunlarini kiriting: " ;
cin >> r2 >> c2;
while (c1!=r2){
cout << " Xato! birinchi matritsa ustuni ikkinchi qatorga teng emas." ;
cout << " Birinchi matritsa uchun satr va ustunlarni kiriting: " ;
cin >> r1 >> c1;
cout << " Ikkinchi matritsa uchun satr va ustunlarni kiriting: " ;
cin >> r2 >> c2; }
cout << endl << " 1-matritsaning elementlarini kiriting:" << endl ;
for (i = 0 ; i < r1; ++i)
for (j = 0 ; j < c1; ++j){
cout << "a elementni kiriting" << i + 1 << j + 1 << " : " ;
cin >> a[i][j]; }
cout << endl << "2 matritsani elementni kiriting:" << endl ;
for (i = 0 ; i < r2; ++i)
for (j = 0 ; j < c2; ++j){
cout << "b elementni kiriting" << i + 1 << j + 1 << " : " ;
cin >> b[i][j]; }
for (i = 0 ; i < r1; ++i)
for (j = 0 ; j < c2; ++j) {
mult[i][j]= 0 ; }
for (i = 0 ; i < r1; ++i)
for (j = 0 ; j < c2; ++j)
for (k = 0 ; k < c1; ++k) {
mult[i][j] += a[i][k] * b[k][j]; }
cout << endl << "Matritsani chop etish" << endl ;
for (i = 0 ; i < r1; ++i)
for (j = 0 ; j < c2; ++j){
cout << " " << mult[i][j];
if (j == c2 -1 )
cout << endl ;
}
return 0 ; }
20](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_20.png)
![Ilovalar
# include <iostream>
using namespace std ;
int main () {
int a[ 10 ][ 10 ], b[ 10 ][ 10 ], mult[ 10 ][ 10 ], r1, c1, r2, c2, i, j, k;
cout << "Birinchi matritsa uchun satr ustunlarini kiriting: " ;
cin >> r1 >> c1
cout << " Ikkinchi matritsa uchun satr ustunlarini kiriting: " ;
cin >> r2 >> c2;
while (c1!=r2){
cout << " Xato! birinchi matritsa ustuni ikkinchi qatorga teng emas." ;
cout << " Birinchi matritsa uchun satr va ustunlarni kiriting: " ;
cin >> r1 >> c1;
cout << " Ikkinchi matritsa uchun satr va ustunlarni kiriting: " ;
cin >> r2 >> c2; }
cout << endl << " 1-matritsaning elementlarini kiriting:" << endl ;
for (i = 0 ; i < r1; ++i)
for (j = 0 ; j < c1; ++j){
cout << "a elementni kiriting" << i + 1 << j + 1 << " : " ;
cin >> a[i][j]; }
cout << endl << "2 matritsani elementni kiriting:" << endl ;
for (i = 0 ; i < r2; ++i)
for (j = 0 ; j < c2; ++j){
cout << "b elementni kiriting" << i + 1 << j + 1 << " : " ;
cin >> b[i][j]; }
for (i = 0 ; i < r1; ++i)
for (j = 0 ; j < c2; ++j) {
mult[i][j]= 0 ; }
for (i = 0 ; i < r1; ++i)
for (j = 0 ; j < c2; ++j)
for (k = 0 ; k < c1; ++k) {
mult[i][j] += a[i][k] * b[k][j]; }
cout << endl << "Matritsani chop etish" << endl ;
for (i = 0 ; i < r1; ++i)
for (j = 0 ; j < c2; ++j){
cout << " " << mult[i][j];
if (j == c2 -1 )
cout << endl ;
}
return 0 ; }
23](/data/documents/3f3d1797-9be6-4519-8b75-36a26ee5d19c/page_23.png)
Mavzu: “Matritsada qidiruv algoritmlari” Mundarija Mavzu: Matritsada qidiruv algoritmlari ......................................................................................................... 2 Kirish ............................................................................................................................................................. 2 I BOB.Matritsa haqida tushuncha .................................................................................................................. 4 1.1.Matritsalarni qayta ishlash .................................................................................................................. 5 1.2. Matritsani kiritish-chiqarish algoritmi ................................................................................................ 5 1.3. Matritsalarni qayta ishlash algoritmlariga misollar ............................................................................. 6 II BOB.Matritsalarni qidirish algoritmi tarixi va uning dasturi ........................................................................ 7 2.1.Matritsada muntazam qidiruv ............................................................................................................. 8 2.2.Matritsada ikkilik qidiruv ................................................................................................................... 11 2.3.Matritsada qidirsh algoritm dastulari c++ va phytonda kodlari tahlili ............................................... 14 2.4.Matritsalarni tartiblash algoritm ....................................................................................................... 16 III BOB.Matritsalarni qo’shish,ayirishva ko’paytirish ................................................................................... 18 3.1.Matirtsalarni qo’shish ........................................................................................................................ 18 3.2. Matirtsalarni ayirish .......................................................................................................................... 19 3.3.Matritsalarni ko’paytirish .................................................................................................................. 20 Foydalanilgan adabiyotlar ........................................................................................................................... 22 Ilovalar ........................................................................................................................................................ 23
Mavzu: Matritsada qidiruv algoritmlari Kirish Universitetga matematika bilan bog'liq mutaxassislik bo'yicha kirgan har qanday odam matritsalarni o'rganishga duch keladi. Matritsa operatsiyalari algebraning eng muhim bo'limidir. C + da dasturlash kursini o'rganar ekanmiz, biz faqat eng oddiy vazifalardan foydalandik, masalan, yig'indi va farqni topish, shuningdek, qatorlar / ustunlar bo'yicha saralashning har xil turlari va boshqalar. Bugungi kunda matematik dasturlash barcha dasturlashning muhim tarkibiy qismi hisoblanadi. Oddiy dasturlar tufayli katta va murakkab hisob-kitoblar oddiy holga keladi. Mikroelektronika fan va texnikaning eng tez va samarali rivojlanayotgan sohalaridan biridir. Biroq, sxemalarning rivojlanishi bilan birga, ishlab chiqilgan sxemalarning murakkabligi ham ortadi. Mantiqiy modeli matritsa, xususan, mantiqiy modeli bo'lgan sxema elementlari mavjud. Mikrosxemaning maydoni va uning ishlashi ko'p jihatdan matritsaning parametrlariga bog'liq. Shuning uchun, ustuvor vazifa, masalan, Mantiqiy matritsalarning eng qisqa qopqog'ini topish orqali elementning hajmini kamaytirishdir. Eng qisqa qamrovlarni izlashning maqsadga muvofiqligi mantiqiy funktsiyalarning DNF ni minimallashtirishda, mantiqiy sxemalarning ayrim turlarini sintez qilishda, mantiqiy tenglamalar tizimini echishda, eng oddiy diagnostika testlarini qidirishda, shuningdek, boshqa ko'plab muammolarni hal qilishda yuzaga keladi. bo'lib chiqadigan hal qilish usullarining samaradorligi Eng qisqa qoplamalarni topish algoritmlari, ayniqsa, nisbatan katta matritsa o'lchamiga ega bo'lgan odam uchun mashaqqatli ishdir, shuning uchun men ishlab chiqqan dastur bu ishni juda osonlashtiradi. Ushbu ishning dolzarbligi shundaki, bugungi kunda Yer sayyorasi aholisining yarmidan ko'pi kompyuterdan foydalanadi. Ularning ko'pchiligi o'z ishini turli manbalardan kerakli ma'lumotlarni, xoh u Internet, ma'lumotlar bazalari yoki mahalliy diskdagi fayllarni qidirishdan boshlaydi va agar qidiruv vaqti hatto bir soniyaga ko'paytirilsa, unda umumiy vaqt sarflangan kerakli ma'lumotlarni qidirayotgan barcha foydalanuvchilar 200 yildan oshadi. Shuning uchun qidiruv vaqtini minimal darajaga qisqartiradigan qidiruv algoritmlarini ishlab chiqish, saqlash va amalga oshirish juda muhimdir. Google infratuzilma bo‘yicha vitse-prezidenti Urs Xölzlening so‘zlariga ko‘ra, “Tezlikni saqlab qolish uchun bizda bitta oddiy qoida bor: qidiruv jarayonini sekinlashtiradigan funksiyalarni ishlatmang. Siz ajoyib yangi algoritm ixtiro qilishingiz mumkin, lekin agar u qidiruvni sekinlashtirsa, siz bu haqda unutishingiz, tuzatishingiz yoki sekinlashuvning o'rnini bosadigan boshqa o'zgarishlarni o'ylab topishingiz kerak bo'ladi. Bizda oilaviy byudjetga o'xshash "qat'iy kechikish byudjeti" mavjud. Agar siz 2
chiroyliroq ta'tilga chiqmoqchi bo'lsangiz-u, lekin byudjetingiz kengaymasa, boshqa joyni qisqartirishingiz kerak." Aynan shuning uchun ko'plab o'zini o'zi hurmat qiladigan dasturiy ta'minot ishlab chiqaruvchi kompaniyalarda umuman dasturiy ta'minot tezligiga va ayniqsa samarali qidiruv algoritmlarini ishlab chiqishga alohida e'tibor beriladi, ishlab chiqish guruhi darajalarni ko'rishi uchun ishlash doimiy ravishda nazorat qilinadi. xizmatlarning kechikishi. Shuning uchun ham bir necha yil oldin ishlar sekinlasha boshlaganida, asosiy e’tibor mahsulotlarni tezroq ishlab chiqarishga qaratildi. Tezlik muhandislik madaniyatining muhim qismidir. Tez qidiruvning asosi nafaqat ma'lumotni tezda topish, balki ushbu ma'lumotlarning so'rovga mos kelishiga ishonch hosil qilish imkonini beruvchi samarali qidiruv algoritmlarini ishlab chiqishdir, shuning uchun ushbu kurs ishining maqsadi qidiruv algoritmlarini o'rganish va tahlil qilishdir. 3
I BOB.Matritsa haqida tushuncha Matritsa - bu halqa yoki maydon elementlarining to'rtburchaklar jadvali (masalan, butun, haqiqiy yoki murakkab sonlar) shaklida yozilgan matematik ob'ekt bo'lib, uning elementlari kesishgan joyda joylashgan qatorlar va ustunlar to'plamidir. Matritsaning satrlari va ustunlari soni matritsaning hajmini aniqlaydi. Masalan, uchburchak matritsalar tarixan ko'rib chiqilgan bo'lsa-da, bugungi kunda faqat to'rtburchaklar matritsalar haqida gapiriladi, chunki ular eng qulay va umumiydir. Matritsalar matematikada chiziqli algebraik yoki differentsial tenglamalar tizimini ixcham tasvirlash uchun keng qo'llaniladi. Bunda matritsa qatorlari soni tenglamalar soniga, ustunlar soni esa noma’lumlar soniga mos keladi. Natijada chiziqli tenglamalar sistemalarining yechimi matritsalar ustidagi amallarga qisqaradi. Matritsa uchun quyidagi algebraik amallar aniqlanadi: 1. bir xil o'lchamdagi matritsalarni qo'shish; 2. mos o'lchamdagi matritsalarni ko'paytirish (ustunlari bo'lgan matritsa o'ng tomonda satrli matritsaga ko'paytirilishi mumkin ); 3. shu jumladan vektor matritsa bilan ko'paytirish (matritsani ko'paytirishning odatiy qoidasiga ko'ra; vektor bu ma'noda matritsaning maxsus holatidir); 4. matritsani asosiy halqa yoki maydonning elementi (ya'ni skaler) bilan ko'paytirish. Qo'shishga nisbatan matritsalar abel guruhini tashkil qiladi; agar biz skaler bilan ko'paytirishni ham ko'rib chiqsak, u holda matritsalar mos keladigan halqa (maydon ustidagi vektor fazosi) ustida modul hosil qiladi. Kvadrat matritsalar to'plami matritsani ko'paytirishda yopiladi, shuning uchun bir xil o'lchamdagi kvadrat matritsalar matritsani qo'shish va matritsani ko'paytirishda birlik bilan assotsiativ halqa hosil qiladi. 4
n o'lchovli chiziqli fazoda harakat qiluvchi har bir chiziqli operator n tartibli yagona kvadrat matritsa bilan bog'lanishi mumkinligi isbotlangan; va aksincha - n-tartibli har bir kvadrat matritsasi bu fazoda harakat qiluvchi yagona chiziqli operator bilan bog'lanishi mumkin. Matritsaning xossalari chiziqli operatorning xossalariga mos keladi. Xususan, matritsaning xos qiymatlari operatorning tegishli xos vektorlarga mos keladigan xos qiymatlari hisoblanadi. 1.1.Matritsalarni qayta ishlash Matritsa ikki o'lchovli massiv bo'lib, uning har bir elementi ikkita indeksga ega: qator raqami - i ; ustun raqami - j . Shuning uchun matritsa elementlari bilan ishlash uchun ikkita halqadan foydalanish kerak. Agar birinchi tsikl parametrining qiymatlari matritsa satrlari raqamlari bo'lsa, ikkinchisi parametrining qiymatlari ustunlar bo'ladi (yoki aksincha). Matritsani qayta ishlash shundan iboratki, dastlab birinchi qator (ustun) elementlari navbatma- navbat, keyin ikkinchisi va boshqalar ko'rib chiqiladi. oxirigacha. Masalalarni yechishda matritsalar ustida bajariladigan asosiy amallarni ko'rib chiqing. 1.2. Matritsani kiritish-chiqarish algoritmi Matritsalar, massivlar kabi, element bo'yicha kiritilishi (chiqish) kerak. Matritsa elementlarini kiritish blok diagrammasi rasmda ko'rsatilgan. 1-rasm. Matritsaning chiqishi kirishga o'xshash tarzda tashkil etilgan. 1-rasm 2-rasm Matritsalarni qayta ishlashning bir qancha masalalarini ko'rib chiqamiz. Ularni yechish uchun matritsalarning ayrim xossalarini o‘quvchiga eslatib o‘tamiz (2-rasm): agar elementning satr raqami ustun raqamiga to'g'ri kelsa (i = j) , bu element matritsaning asosiy diagonalida joylashganligini anglatadi; 5