درس ۲۰متوسط

آرایه‌های دو‌بعدی

ماتریس، قطر اصلی و فرعی، پیمایش و الگوهای مثلثی

معمولی

آرایه‌ها و رشته‌ها•صفحه ۳۲•۴۰ دقیقه•۱٬۵۱۴ کلمه•۸ دقیقه مطالعهزمان مطالعه: ۰ دقیقه

فهرست این درس

آرایه دو‌بعدی چیست؟
تعریف و مقداردهی اولیه ماتریس
خواندن و چاپ ماتریس
قطر اصلی ماتریس (i == j)
قطر فرعی ماتریس (i + j == n - 1)
جمع عناصر قطر اصلی
جمع عناصر قطر فرعی
چاپ ماتریس با قطر اصلی برجسته
ماتریس مثلثی بالایی
مثلث خیام–پاسکال
فلوچارت پیمایش ماتریس
یافتن ماکزیمم هر سطر
اشتباه جزوه: VLA دو‌بعدی
ترتیب ذخیره‌سازی سطری (Row-Major)
هنگام ارسال آرایه دو‌بعدی به تابع
خلاصه و کاربرد‌ها

// اهداف۴

آشنایی با مفهوم آرایه دو‌بعدی (ماتریس) و نحوه تعریف و مقداردهی آن
درک شرط‌های قطر اصلی (i==j) و قطر فرعی (i+j==n-1) برای ماتریس
پیمایش ماتریس با حلقه تودرتو و چاپ الگوهای مثلثی
پیاده‌سازی الگوریتم‌های جمع قطر، یافتن ماکزیمم هر سطر و ماتریس مثلثی

آرایه دو‌بعدی چیست؟

آرایه دو‌بعدی یا ماتریس، آرایه‌ای از آرایه‌ها است که برای نمایش داده‌های جدولی استفاده می‌شود. هر عنصر با دو اندیس مشخص می‌شود: اندیس سطر (row) و اندیس ستون (column).

مثلاً int a[3][4] یک ماتریس با ۳ سطر و ۴ ستون است که در مجموع ۱۲ خانه دارد. در حافظه، این خانه‌ها به‌صورت سطری پشت‌سرهم ذخیره می‌شوند.

main.cppcpp
     col0  col1  col2  col3
row0  a00   a01   a02   a03
row1  a10   a11   a12   a13
row2  a20   a21   a22   a23

کاربرد‌ها: ماتریس‌های ریاضی، تصاویر (پیکسل‌ها)، صفحه‌نمایش، نقشه‌ها، جدول ضرب و ...

تعریف و مقداردهی اولیه ماتریس

برای مقداردهی اولیه، مقادیر هر سطر را داخل یک جفت آکولاد جداگانه قرار می‌دهیم. اگر مقادیر کافی نباشد، بقیه خودکار صفر می‌شوند.

روش‌های مختلف تعریفcpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    // روش ۱: مقداردهی کامل
6    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
7
8    // روش ۲: مقداردهی جزئی (بقیه صفر)
9    int b[3][3] = {{1, 2}, {3}};     // چند خانه صفر می‌شود
10
11    // روش ۳: همه‌ی خانه‌ها صفر
12    int c[3][3] = {0};
13
14    // چاپ ماتریس a
15    for (int i = 0; i < 2; i++) {
16        for (int j = 0; j < 3; j++)
17            cout << a[i][j] << ' ';
18        cout << endl;
19    }
20    return 0;
21}

خروجی برنامه

1 2 3 
4 5 6

در حال باز کردن ویرایشگر…

خواندن و چاپ ماتریس

پیمایش ماتریس با دو حلقه انجام می‌شود: حلقه بیرونی روی سطرها، حلقه داخلی روی ستون‌ها. برای چاپ، در پایان هر سطر یک endl می‌زنیم.

پیمایش با حلقه تودرتوcpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    const int ROW = 3, COL = 3;
6    int a[ROW][COL];
7
8    cout << "Enter 9 numbers: " << endl;
9    for (int i = 0; i < ROW; i++)
10        for (int j = 0; j < COL; j++)
11            cin >> a[i][j];
12
13    cout << "Matrix:" << endl;
14    for (int i = 0; i < ROW; i++) {
15        for (int j = 0; j < COL; j++)
16            cout << a[i][j] << '\t';
17        cout << endl;
18    }
19    return 0;
20}

خروجی برنامه

Enter 9 numbers:
1 2 3 4 5 6 7 8 9
Matrix:
1	2	3	
4	5	6	
7	8	9

در حال باز کردن ویرایشگر…

قطر اصلی ماتریس (i == j)

در یک ماتریس مربعی n × n، قطر اصلی (Main Diagonal) از گوشه‌ی بالا-چپ به پایین-راست می‌رود. در این خانه‌ها، اندیس سطر و ستون برابر است: i == j.

main.cppcpp
در ماتریس 5x5 (اندیس از 0):
X . . . .
. X . . .
. . X . .
. . . X .
. . . . X

کاربرد‌ها: ماتریس مثلثی بالا/پایین، ماتریس همانی (Identity)، یافتن Sparsity (خلوت بودن ماتریس).

قطر فرعی ماتریس (i + j == n - 1)

قطر فرعی یا ضد قطر (Anti/Secondary Diagonal) از گوشه‌ی بالا-راست به پایین-چپ می‌رود. شرط آن: i + j == n - 1 (وقتی اندیس از ۰ شروع می‌شود).

main.cppcpp
در ماتریس 5x5 (اندیس از 0):
. . . . X
. . . X .
. . X . .
. X . . .
X . . . .

نکته: اگر اندیس‌ها از ۱ شروع شوند، شرط قطر فرعی i + j == n + 1 می‌شود. (این همان فرمولی است که در درس حلقه‌های تودرتو هم دیدیم.)

جمع عناصر قطر اصلی

برای جمع عناصر قطر اصلی، یک حلقه تکی کافی است: خانه‌های a[0][0], a[1][1], ..., a[n-1][n-1] را پیمایش می‌کنیم.

مجموع خانه‌هایی که i == jcpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    const int N = 3;
6    int a[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
7
8    int sum = 0;
9    for (int i = 0; i < N; i++)
10        sum += a[i][i];      // قطر اصلی
11
12    cout << "Trace (sum of main diagonal) = " << sum << endl;
13    // 1 + 5 + 9 = 15
14    return 0;
15}

خروجی برنامه

Trace (sum of main diagonal) = 15

در حال باز کردن ویرایشگر…

جمع عناصر قطر فرعی

برای قطر فرعی، خانه‌های a[0][n-1], a[1][n-2], ..., a[n-1][0] را پیمایش می‌کنیم. شرط کلی: i + j == n - 1.

مجموع خانه‌هایی که i + j == n - 1cpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    const int N = 3;
6    int a[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
7
8    int sum = 0;
9    for (int i = 0; i < N; i++)
10        sum += a[i][N - 1 - i];    // قطر فرعی
11
12    cout << "Secondary diagonal sum = " << sum << endl;
13    // 3 + 5 + 7 = 15
14    return 0;
15}

خروجی برنامه

Secondary diagonal sum = 15

در حال باز کردن ویرایشگر…

چاپ ماتریس با قطر اصلی برجسته

این الگو دید بصری از قطر اصلی ماتریس می‌دهد.

روی قطر اصلی * و بقیه . چاپ می‌کنیمcpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    const int N = 5;
6    for (int i = 0; i < N; i++) {
7        for (int j = 0; j < N; j++) {
8            if (i == j)
9                cout << '*';
10            else
11                cout << '.';
12        }
13        cout << endl;
14    }
15    return 0;
16}

خروجی برنامه

*....
.*...
..*..
...*.
....*

در حال باز کردن ویرایشگر…

ماتریس مثلثی بالایی

یک ماتریس مثلثی بالایی (Upper Triangular) فقط خانه‌هایی را پر می‌کند که i <= j (یعنی روی قطر اصلی یا بالاتر از آن).

فقط خانه‌های بالا-قطر اصلی پر می‌شوندcpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    const int N = 4;
6    for (int i = 0; i < N; i++) {
7        for (int j = 0; j < N; j++) {
8            if (i <= j)
9                cout << "*";
10            else
11                cout << " ";
12        }
13        cout << endl;
14    }
15    return 0;
16}

خروجی برنامه

****
 ***
  **
   *

در حال باز کردن ویرایشگر…

مثلث خیام–پاسکال

کلاسیک‌ترین مثال «پر کردن ماتریس با یک قاعده» مثلث خیام–پاسکال است (صفحه ۴۱ جزوه): اولین خانه‌ی هر سطر ۱ است و هر خانه‌ی داخلی برابر مجموع دو خانه‌ی بالایی خودش است — a[i][j] = a[i-1][j-1] + a[i-1][j]. چون بقیه‌ی خانه‌ها صفر می‌مانند، این جمع هیچ‌وقت از محدوده خارج نمی‌شود.

نکته‌ی ریاضی: سطر n-ام ضرایب دوجمله‌ای (a+b)^n را می‌دهد؛ مثلاً سطر چهارم یعنی 1 4 6 4 1: (a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4.

هر خانه = مجموع دو خانه‌ی بالایی آن (صفحه ۴۱ جزوه)cpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    const int N = 5;
6    int a[N][N] = {0};                       // همه‌ی خانه‌ها صفر
7    for (int i = 0; i < N; i++) {
8        a[i][0] = 1;                          // شروع هر سطر
9        for (int j = 1; j <= i; j++)
10            a[i][j] = a[i-1][j-1] + a[i-1][j]; // قاعده‌ی خیام
11    }
12    for (int i = 0; i < N; i++) {
13        for (int j = 0; j <= i; j++)
14            cout << a[i][j] << ' ';
15        cout << endl;
16    }
17    return 0;
18}

خروجی برنامه

در حال باز کردن ویرایشگر…

فلوچارت پیمایش ماتریس

گام‌های پیمایش و چاپ یک ماتریس n×m:

flow.svg100%

.flow-nojs{height:auto!important;max-height:none!important;aspect-ratio:auto!important}.flow-nojs .react-flow{height:var(--flow-nojs-h,600px)!important;overflow:auto!important}.flow-nojs .react-flow__viewport{transform:none!important}

شروع/پایانپردازشتصمیمورودی/خروجی

flow.svg

یافتن ماکزیمم هر سطر

برای یافتن ماکزیمم هر سطر، در هر تکرار حلقه بیرونی، یک متغیر maxInRow را با a[i][0] مقداردهی می‌کنیم و در حلقه داخلی به‌روزرسانی می‌کنیم.

ماکزیمم محلی در هر سطرcpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    const int N = 3, M = 4;
6    int a[N][M] = {
7        {3, 7, 1, 4},
8        {9, 2, 5, 8},
9        {6, 0, 11, 7}
10    };
11
12    for (int i = 0; i < N; i++) {
13        int maxInRow = a[i][0];
14        for (int j = 1; j < M; j++)
15            if (a[i][j] > maxInRow) maxInRow = a[i][j];
16        cout << "Max of row " << i << " = " << maxInRow << endl;
17    }
18    return 0;
19}

خروجی برنامه

Max of row 0 = 7
Max of row 1 = 9
Max of row 2 = 11

در حال باز کردن ویرایشگر…

اشتباه جزوه: VLA دو‌بعدی

مانند آرایه یک‌بعدی، در ⁦C++⁩ استاندارد تعریف ماتریس با اندازه‌ی متغیر (int a[n][m] پس از cin >> n >> m) مجاز نیست. اگر اندازه‌ی حداکثر از قبل معلوم است از const int استفاده کنید؛ در غیر این صورت از vector<vector<int>>.

نسخه اشتباه جزوه

کد دارای باگcpp

1#include <iostream>
2using namespace std;
3int main() {
4    int n, m;
5    cin >> n >> m;
6    int a[n][m];   // ✗ VLA دو‌بعدی غیراستاندارد
7    for (int i = 0; i < n; i++)
8        for (int j = 0; j < m; j++)
9            cin >> a[i][j];
10    return 0;
11}

نسخه اصلاح‌شده و استاندارد

کد صحیحcpp

1#include <iostream>
2#include <vector>
3using namespace std;
4int main() {
5    int n, m;
6    cin >> n >> m;
7    vector<vector<int>> a(n, vector<int>(m));   // ✓ استاندارد
8    for (int i = 0; i < n; i++)
9        for (int j = 0; j < m; j++)
10            cin >> a[i][j];
11    return 0;
12}

ترتیب ذخیره‌سازی سطری (Row-Major)

در ⁦C++⁩ آرایه‌های دو‌بعدی به‌صورت Row-Major Order در حافظه ذخیره می‌شوند، یعنی ابتدا تمام عناصر سطر اول، سپس سطر دوم، و به همین ترتیب. به همین دلیل، برای پیمایش کارآمد حافظه (کش شدن بهتر CPU)، حلقه بیرونی باید روی سطر و حلقه داخلی روی ستون باشد: for i ... for j .... اگر برعکس بنویسید (for j ... for i ...)، به ازای هر دسترسی، کش misses اتفاق می‌افتد و برنامه کندتر می‌شود.

هنگام ارسال آرایه دو‌بعدی به تابع

در ⁦C++⁩، وقتی آرایه دو‌بعدی را به تابع می‌فرستید، بعد دوم باید ثابت و مشخص باشد. مثلاً تابعی که int a[3][4] می‌گیرد باید امضایش void f(int a[][4], int rows) باشد. دلیل: کامپایلر برای محاسبه‌ی a[i][j] باید اندازه‌ی ستون را بداند. اگر ابعاد متغیر هستند، از vector<vector<int>> استفاده کنید که این محدودیت را ندارد.

خلاصه و کاربرد‌ها

آرایه‌های دو‌بعدی پایه‌ی بسیاری از الگوریتم‌ها هستند: ماتریس همانی، ماتریس مثلثی، ضرب ماتریس، مسیریابی در نقشه، شبیه‌سازی‌های فیزیکی، بازی‌های جدولی (شطرنج، مین‌روب، تیک‌تک‌تو) و پردازش تصویر. در درس‌های بعد با مرتب‌سازی‌ها و ماتریس‌های پیشرفته‌تر آشنا می‌شویم.

اهداف:

آشنایی با مفهوم آرایه دو‌بعدی (ماتریس) و نحوه تعریف و مقداردهی آن
درک شرط‌های قطر اصلی (i==j) و قطر فرعی (i+j==n-1) برای ماتریس
پیمایش ماتریس با حلقه تودرتو و چاپ الگوهای مثلثی

نکات کلیدی:

آرایه دو‌بعدی (ماتریس) با دو اندیس سطر و ستون کار می‌کند و در حافظه به‌صورت سطری (Row-Major) ذخیره می‌شود.
قطر اصلی ماتریس مربعی n×n با شرط `i == j` مشخص می‌شود.
قطر فرعی با شرط `i + j == n - 1` (وقتی اندیس از ۰ شروع شود) یا `i + j == n + 1` (وقتی از ۱ شروع شود).
برای پیمایش کارآمد ماتریس، حلقه بیرونی روی سطر و حلقه داخلی روی ستون باشد.

مرور سریع مطالب

۱۶ بخش در این درس

آرایه دو‌بعدی چیست؟
تعریف و مقداردهی اولیه ماتریس
خواندن و چاپ ماتریس
قطر اصلی ماتریس (i == j)
قطر فرعی ماتریس (i + j == n - 1)
جمع عناصر قطر اصلی
جمع عناصر قطر فرعی
چاپ ماتریس با قطر اصلی برجسته
ماتریس مثلثی بالایی
مثلث خیام–پاسکال
فلوچارت پیمایش ماتریس
یافتن ماکزیمم هر سطر
اشتباه جزوه: VLA دو‌بعدی
ترتیب ذخیره‌سازی سطری (Row-Major)
هنگام ارسال آرایه دو‌بعدی به تابع
خلاصه و کاربرد‌ها

تمرین‌ها

تمرین•حل کامل دارد

برنامه‌ای بنویسید که یک ماتریس n×n را بخواند و حاصل‌جمع هر دو قطر اصلی و فرعی را در صورت فرد بودن n چاپ کند (اگر n فرد باشد، خانه‌ی وسط در هر دو قطر مشترک است و نباید دو بار شمرده شود).

نمایش راهنما

ابتدا قطر اصلی را جمع کنید، سپس قطر فرعی را به آن اضافه کنید ولی اگر `i == n-1-i` است، آن خانه را دو بار نفرمایید.

تمرین•حل کامل دارد

برنامه‌ای بنویسید که یک ماتریس ۳×۳ را بخواند و تعیین کند آیا ماتریس **همانی** است یا خیر (همانی: قطر اصلی همه ۱ و بقیه ۰).

نمایش راهنما

بررسی کنید `a[i][j]` در صورت `i==j` باید ۱ و در غیر این صورت ۰ باشد.

تمرین•حل کامل دارد

برنامه‌ای بنویسید که یک ماتریس n×n را بخواند و **ترانهاده** (Transpose) آن را چاپ کند (یعنی سطر‌ها و ستون‌ها را جابجا کند).

نمایش راهنما

در ترانهاده، عنصر `(i,j)` ماتریس اصلی برابر `(j,i)` ترانهاده است. یعنی در چاپ، حلقه داخلی روی i و بیرونی روی j را عوض کنید.

تمرین•حل کامل دارد

برنامه‌ای بنویسید که یک ماتریس n×n را بخواند و یک **ماتریس مثلثی پایینی** بسازد: فقط خانه‌های `i >= j` را نگه دارد و بقیه را صفر کند. سپس ماتریس را چاپ کند.

نمایش راهنما

در حلقه، اگر `i < j` بود `a[i][j] = 0` کنید.

// نکات-کلیدی۶

01آرایه دو‌بعدی (ماتریس) با دو اندیس سطر و ستون کار می‌کند و در حافظه به‌صورت سطری (Row-Major) ذخیره می‌شود.
02قطر اصلی ماتریس مربعی n×n با شرط `i == j` مشخص می‌شود.
03قطر فرعی با شرط `i + j == n - 1` (وقتی اندیس از ۰ شروع شود) یا `i + j == n + 1` (وقتی از ۱ شروع شود).
04برای پیمایش کارآمد ماتریس، حلقه بیرونی روی سطر و حلقه داخلی روی ستون باشد.
05تعریف ماتریس با اندازه‌ی متغیر (VLA) غیراستاندارد است؛ از `const int` یا `vector<vector<int>>` استفاده کنید.
06هنگام ارسال ماتریس به تابع، بعد دوم باید ثابت و مشخص باشد.

گام بعدی پیشنهادی

مرتب‌سازی: Bubble Sort و Selection Sort

دو الگوریتم کلاسیک مرتب‌سازی آرایه‌ها به همراه پیاده‌سازی صحیح و تحلیل پیچیدگی

۳۵ دقیقهمتوسط۱۴ بخش

شروع درس

آرایه دو‌بعدی چیست؟ اشتراک

تعریف و مقداردهی اولیه ماتریس اشتراک

خواندن و چاپ ماتریس اشتراک

قطر اصلی ماتریس (i == j) اشتراک

قطر فرعی ماتریس (i + j == n - 1) اشتراک

جمع عناصر قطر اصلی اشتراک

جمع عناصر قطر فرعی اشتراک

چاپ ماتریس با قطر اصلی برجسته اشتراک

ماتریس مثلثی بالایی اشتراک

مثلث خیام–پاسکال اشتراک

فلوچارت پیمایش ماتریس

یافتن ماکزیمم هر سطر اشتراک

اشتباه جزوه: VLA دو‌بعدی

ترتیب ذخیره‌سازی سطری (Row-Major)

هنگام ارسال آرایه دو‌بعدی به تابع

خلاصه و کاربرد‌ها

مرور سریع مطالب

تمرین‌ها

مرتب‌سازی: Bubble Sort و Selection Sort

جستجوی سریع در درس‌ها

آرایه دو‌بعدی چیست؟

تعریف و مقداردهی اولیه ماتریس

خواندن و چاپ ماتریس

قطر اصلی ماتریس (i == j)

قطر فرعی ماتریس (i + j == n - 1)

جمع عناصر قطر اصلی

جمع عناصر قطر فرعی

چاپ ماتریس با قطر اصلی برجسته

ماتریس مثلثی بالایی

مثلث خیام–پاسکال

یافتن ماکزیمم هر سطر