رسم نمودار ستونی (هیستوگرام) برای مقادیر آرایه با ستاره
درک منطق «max کاهشی» برای رسم هیستوگرام از بالا به پایین
شمارش اعدادی که از عنصر قبلی خود بزرگ‌ترند
شمارش تعداد تکرار عنصر ماکزیمم با الگوریتم صحیح دو مرحله‌ای
آشنایی با آرایه کاراکتری و تفاوت آن با رشته‌ی C++
هیستوگرام (نمودار ستونی) چیست؟
هیستوگرام نوعی نمودار ستونی است که در آن، ارتفاع هر ستون نشان‌دهنده‌ی فراوانی یا مقدار یک داده است. در برنامه‌نویسی، می‌توانیم با چاپ ستاره در هر سطر، یک نمودار ستونی متنی بسازیم.
مثلاً اگر آرایه {3, 5, 2, 4} داشته باشیم، می‌خواهیم ۴ ستون ستاره‌ای بکشیم که ارتفاع اولی ۳، دومی ۵، سومی ۲ و چهارمی ۴ باشد. ماکزیمم مقدار ۵ است، پس نمودار ۵ سطر خواهد داشت:
main.cpptext
به این شکل دقت کنید: ستون دوم (با ارتفاع ۵) در همه سطر‌ها ستاره دارد، ستون چهارم (با ارتفاع ۴) از سطر چهارم به بعد ستاره دارد، و الی آخر. برای رسم این نمودار از حلقه تودرتو استفاده می‌کنیم: حلقه بیرونی روی ارتفاع (از ماکزیمم تا ۱ به‌صورت کاهشی) و حلقه داخلی روی ستون‌ها.
مثال ۱: رسم نمودار ستونی با ستاره
ترفند: متغیر max را در هر سطر یک واحد کاهش می‌دهیم. هر خانه که مقدارش بزرگ‌تر یا مساویmax فعلی باشد، ستاره می‌گیرد. وقتی max از آن مقدار کمتر شد، دیگر ستاره چاپ نمی‌شود. این روش نمودار را از بالا به پایین می‌سازد.
هیستوگرام عمودی برای آرایه با ۴ مقدارcpp
$خروجی برنامه
*
* *
** *
****
****
در حال باز کردن ویرایشگر…
فلوچارت رسم هیستوگرام
گام‌های رسم نمودار ستونی عمودی با ستاره:
flow.svg
منطق «max کاهشی» چطور کار می‌کند؟
تصور کنید هر ستون یک برج از ستاره‌ها است که ارتفاعش برابر a[j] است. در سطر اول (از بالا)، فقط ستون‌هایی ستاره دارند که ارتفاعشان به سقف maxVal رسیده باشد. در سطر دوم، ستون‌هایی که ارتفاعشان >= maxVal - 1 است. و به همین ترتیب تا سطر آخر که همه ستون‌ها با ارتفاع >= 1 ستاره می‌گیرند.
بنابراین متغیر row به‌جای متغیر ثابت max، از maxVal شروع و تا ۱ کاهش می‌یابد و در هر سطر شرط a[j] >= row را بررسی می‌کنیم. این روش تمیزتر و خواناتر از کاهش دستی max است.
مثال ۲: شمارش اعداد بزرگ‌تر از عنصر قبلی
می‌خواهیم تعداد عناصری را که از عنصر قبلی خود بزرگ‌ترند بشماریم. کافی است از i = 1 شروع کنیم و در هر مرحله a[i] را با a[i-1] مقایسه کنیم. نکته: حلقه داخلی لازم نیست، فقط یک حلقه تک‌سطحی کافی است.
بررسی a[i] > a[i-1]cpp
$خروجی برنامه
Enter n: 5
1 20 3 4 5
3
در حال باز کردن ویرایشگر…
اشتباه جزوه: حلقه تودرتو به‌جای مقایسه با عنصر قبلی
در جزوه، عنوان مسئله «اعداد بزرگ‌تر از عدد قبلی» است اما کد با دو حلقه تودرتو نوشته شده که همه جفت‌های (i, j) را مقایسه می‌کند و منطق متفاوتی دارد (شمارش معکوس‌ها). نسخه‌ی صحیح تنها به یک حلقه نیاز دارد و فقط با a[i-1] مقایسه می‌کند.
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
مثال ۳: شمارش تعداد تکرار ماکزیمم
اشتباه رایج این است که در همان حلقه‌ی یافتن max، هر بار که max به‌روز شد، شمارنده را یکی اضافه کنیم. این کار تعداد تغییرات max را می‌شمارد، نه تکرار آن را! روش صحیح: ابتدا در یک حلقه max را پیدا کنید، سپس در حلقه دوم تعداد برابری‌ها با max را بشمارید.
الگوریتم دو مرحله‌ای: ابتدا یافتن max، سپس شمارشcpp
$خروجی برنامه
Enter n: 8
3 7 2 7 1 7 4 5
Max = 7 appears 3 time(s)
در حال باز کردن ویرایشگر…
فلوچارت شمارش تکرار ماکزیمم
گام‌های الگوریتم دو مرحله‌ای شمارش تکرار ماکزیمم:
flow.svg
اشتباه رایج: شمارش «تغییرات» به‌جای «تکرار»
این کد ظاهراً درست به‌نظر می‌رسد ولی اشتباه است:
main.cppcpp
مثلاً برای آرایه‌ی {5, 7, 7, 7} این کد مقدار k = 2 می‌دهد (چون max از ۵ به ۷ تغییر کرده) در حالی که پاسخ صحیح ۳ است (۷ سه بار تکرار شده). راه‌حل: مرحله‌ی شمارش را جدا انجام دهید.
آرایه‌ی کاراکتری: اولین قدم به سوی رشته‌ها
آرایه‌ی کاراکتری آرایه‌ای از نوع char است که برای ذخیره‌ی متن (رشته) استفاده می‌شود. در زبان C کلاسیک، رشته به‌صورت آرایه‌ای از کاراکتر‌ها که با کاراکتر پوچ \0 (Null Terminator) تمام می‌شد، پیاده‌سازی می‌شد.
main.cppcpp
در C++ مدرن، کلاس std::string جایگزین بسیار بهتر و امن‌تری برای آرایه‌ی کاراکتری است که در درس بعد به‌طور کامل آن را بررسی می‌کنیم. با این حال، آشنایی با آرایه کاراکتری برای فهم کارکرد تابع cin.getline ضروری است.
تعریف و استفاده از آرایه‌ی کاراکتری
دستور cin >> ch یک کلمه (تا رسیدن به اولین فاصله) را می‌خواند. به‌محض رسیدن به space، خواندن متوقف می‌شود و بقیه‌ی متن در بافر می‌ماند.
خواندن یک کلمه با cin و چاپ آنcpp
$خروجی برنامه
Enter a word: Hello
You typed: Hello
Length = 5
خطر Buffer Overflow در `cin >> ch`
اگر کاربر کلمه‌ای طولانی‌تر از ظرفیت آرایه وارد کند، cin >> ch بدون چک کردن طول، در حافظه می‌نویسد و باعث Buffer Overflow می‌شود! دو راه‌حل امن:
۱. استفاده از cin.getline(ch, 100); که حداکثر ۹۹ کاراکتر می‌خواند.
۲. استفاده از کلاس std::string که خودش حافظه را مدیریت می‌کند.
برای همین در C++ مدرن، توصیه می‌شود از std::string استفاده کنید مگر اینکه دلیل خاصی برای آرایه‌ی کاراکتری داشته باشید.
کاراکتر Null (پایان رشته)
در آرایه‌ی کاراکتری C-style، رشته با کاراکتر \0 (کد اسکی ۰) تمام می‌شود. این کاراکتر به توابع کتابخانه‌ای مانند strlen یا cout می‌گوید کجای رشته تمام شده. به همین دلیل، اگر آرایه‌ی char ch[5] تعریف کنید، در واقع فقط ۴ کاراکتر قابل ذخیره است چون خانه‌ی پنجم برای \0 لازم است.
برنامه‌ای بنویسید که ۵ عدد صحیح از ورودی بگیرد و نمودار ستونی افقی برای آن‌ها رسم کند. یعنی برای هر عدد، به تعداد آن عدد ستاره چاپ شود. مثلاً برای ۳: `***`.
نمایش راهنما
برای هر عنصر آرایه، یک حلقه داخلی به تعداد مقدار آن چاپ ستاره کنید.
02
تمرین•حل کامل دارد
برنامه‌ای بنویسید که n عدد بگیرد و تعداد عناصری را که از میانگین خود + عنصر قبلی بزرگ‌ترند، بشمارد (یعنی `a[i] > (a[i-1] + a[i+1]) / 2`).
نمایش راهنما
مراقب باشید برای i=0 یا i=n-1، به اندیس خارج از محدوده دسترسی پیدا نکنید.
03
تمرین•حل کامل دارد
برنامه‌ای بنویسید که n عدد بگیرد و کوچک‌ترین مقدار و تعداد تکرار آن را چاپ کند.
نمایش راهنما
ابتدا min را پیدا کنید، سپس تعداد برابری با min را بشمارید.
04
تمرین•حل کامل دارد
برنامه‌ای بنویسید که یک کلمه (بدون فاصله) را با `cin >> ch` بخواند و تعداد حروف بزرگ انگلیسی (A-Z) آن را بشمارد.
نمایش راهنما
از آرایه `char` و شرط `ch[i] >= 'A' && ch[i] <= 'Z'` استفاده کنید.
// نکات-کلیدی۶
01هیستوگرام ستاره‌ای با حلقه تودرتو رسم می‌شود: حلقه بیرونی روی ارتفاع (از maxVal تا ۱) و حلقه داخلی روی ستون‌ها.
02در شرط هیستوگرام، `a[j] >= row` اگر برقرار باشد ستاره چاپ می‌شود، در غیر این صورت فاصله.
03برای «بزرگ‌تر از عنصر قبلی» فقط یک حلقه کافی است و نیازی به حلقه تودرتو نیست (`a[i] > a[i-1]`).
04برای شمارش تکرار ماکزیمم، دو مرحله‌ی جداگانه لازم است: ابتدا یافتن max، سپس شمارش برابری‌ها.
05آرایه‌ی کاراکتری C-style با کاراکتر `\0` تمام می‌شود و در `cin >> ch` خطر Buffer Overflow دارد.
06در C++ مدرن، کلاس `std::string` جایگزین امن‌تر آرایه‌ی کاراکتری است.
گام بعدی پیشنهادی
رشته‌ها (string) در C++
std::string، cin در برابر getline، شمارش کلمات، تبدیل حروف، یافتن زیررشته و استخراج اعداد
نام درس، موضوع یا کلمه کلیدی را بنویسید و با Enter به آن بروید
*
* *
** *
****
****
1#include<iostream>2usingnamespace std;34intmain(){5constint N =4;6int a[N]={3,5,2,4};78// یافتن بیشترین مقدار (ارتفاع هیستوگرام)9int maxVal = a[0];10for(int i =1; i < N; i++)11if(a[i]> maxVal) maxVal = a[i];1213// رسم از بالا به پایین14for(int row = maxVal; row >=1; row--){15for(int j =0; j < N; j++){16if(a[j]>= row)17 cout <<'*';18else19 cout <<' ';20}21 cout << endl;22}23return0;24}
flow.svg100%
Press enter or space to select a node. You can then use the arrow keys to move the node around. Press delete to remove it and escape to cancel.
Press enter or space to select an edge. You can then press delete to remove it or escape to cancel.
شروع/پایانپردازشتصمیمورودی/خروجی
1#include<iostream>2usingnamespace std;34intmain(){5int n;6 cout <<"Enter n: ";7 cin >> n;89int a[100];10for(int i =0; i < n; i++) cin >> a[i];1112int count =0;13for(int i =1; i < n; i++){14if(a[i]> a[i -1]) count++;15}16 cout << count << endl;17return0;18}
1#include<iostream>2usingnamespace std;3intmain(){4int a[100], k =0;5for(int i =0; i <100; i++) cin >> a[i];6for(int i =0; i <100; i++){7for(int j = i; j <100; j++){// ✗ حلقه تودرتو غیرلازم8if(a[i]> a[j]) k++;// ✗ مقایسه با همه، نه فقط قبلی9}10}11 cout << k;12return0;13}
1#include<iostream>2usingnamespace std;3intmain(){4int n, k =0;5 cin >> n;6int a[100];7for(int i =0; i < n; i++) cin >> a[i];8for(int i =1; i < n; i++){// ✓ فقط یک حلقه از i=19if(a[i]> a[i -1]) k++;// ✓ مقایسه با عنصر قبلی10}11 cout << k;12return0;13}
1#include<iostream>2usingnamespace std;34intmain(){5int n;6 cout <<"Enter n: ";7 cin >> n;89int a[100];10for(int i =0; i < n; i++) cin >> a[i];1112// مرحله ۱: یافتن ماکزیمم13int maxVal = a[0];14for(int i =1; i < n; i++)15if(a[i]> maxVal) maxVal = a[i];1617// مرحله ۲: شمارش تعداد تکرار max18int count =0;19for(int i =0; i < n; i++)20if(a[i]== maxVal) count++;2122 cout <<"Max = "<< maxVal
23<<" appears "<< count <<" time(s)"<< endl;24return0;25}
flow.svg100%
Press enter or space to select a node. You can then use the arrow keys to move the node around. Press delete to remove it and escape to cancel.
Press enter or space to select an edge. You can then press delete to remove it or escape to cancel.
شروع/پایانپردازشتصمیمورودی/خروجی
int k =1, max = a[0];for(int i =1; i < n; i++){if(a[i]> max){ k++;// ✗ این تعداد تغییرات max را می‌شمارد! max = a[i];}}
char ch[100];cin >> ch;cout << ch;
1#include<iostream>2#include<cstring>3usingnamespace std;45intmain(){6char ch[100];7 cout <<"Enter a word: ";8 cin >> ch;// فقط تا اولین فاصله9 cout <<"You typed: "<< ch << endl;10 cout <<"Length = "<<strlen(ch)<< endl;11return0;12}