نقطه زین اسبی در آرایه های دو بعدی پویا با سی پلاس پلاس
به احتمال زیاد با مفهوم و تعریف نقطه زین اسبی در ریاضیات و در درس ریاضی عمومی ۲ آشنا هستید.
نقطه ی زین اسبی در برنامه نویسی (saddle point): به زبان ساده اگر در یک آرایه ی دو بعدی (ماتریس) نقطه ای داشته باشیم که در سطر خودش کمترین مقدار و در ستون خودش بیشترین مقدار را داشته باشد آن را نقطه ی زین اسبی میگویند.
برای مثال عدد ۳ در ماتریس زیر که با * مشخص شده، همان نقطه ای است که ما باید به دنبال آن باشیم.
۱ ۲ ۳ ۲
۵ ۵ ۴ *۳
۲ ۰ ۱ ۲
نکته: یک ماتریس ممکن است نقطه مذکور را نداشته باشد یا بیش از یکی داشته باشد؛ پس در تشخیص آن باید تمام نقاط بررسی شوند.
هدف از ارائه ی این سوال آشنایی با آرایه ی دوبعدی پویا و تابع است.
ورودی های تابع به ترتیب اشاره گر به ابتدای آرایه ی دو بعدی، اندازه ابعاد آرایه و طول و عرض نقطه ای که زین اسبی بودن آن را بررسی می کنیم.
یعنی روش حل به این شکل است که به ازای هر i و j که به عنوان دو ورودی در آرگومان تابع قرار میگ یرند مینیمم بودن مقدار در سطر i ام و ماکزیمم بودنش در ستون j ام بررسی میشود.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include <iostream> using namespace std; int issaddle(int **table, int x, int y, int i, int j) { bool is_max=true, is_min=true; for (int k = 0; k < y; k++) { if (table[i][k] < table[i][j]) { is_min = false; return 0; } } for (int k = 0; k < x; k++){ if (table[k][j] > table[i][j]) { is_max = false; return 0; } } return 1; } int main(void){ int **table; bool none = true; int x, y; cout<<"Enter dimensions:"<<endl<<"x= "; cin>>x; cout<<"y= "; cin>>y; table = new int * [x]; for (int i = 0; i < x; i++) { table[i] = new int [y]; } cout<<"enter the values in turn using space between them."<<endl; for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { cin>>table[i][j]; } } cout<<endl<<"----------"<<endl; for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { if (issaddle(table, x, y, i, j)==1) { cout<<"table["<<i<<"]["<<j<<"]="<<table[i][j]<<endl; none = false; } } } if (none) { cout<<"there is no saddle point in the table."<<endl; } cin.get(); } |