محاسبه فاکتوریل n! با حلقه for و انتخاب نوع داده مناسب
تشخیص عدد اول با روش شمارش مقسوم‌علیه‌ها (k == 2 یعنی اول)
تولید سری فیبوناچی با الگوی جابجایی (Shift) متغیر‌ها
شناسایی و اصلاح اشتباهات تایپی رایج جزوه (b=l، n%i==o، *k=0)
درک بهینه‌سازی الگوریتم‌ها (بررسی تا sqrt(n) برای اول بودن)
سه الگوریتم کلاسیک
این درس به سه الگوریتم معروف می‌پردازد که در تقریباً هر دوره برنامه‌نویسی آمده‌اند:
۱. فاکتوریل (n!): حاصل‌ضرب اعداد ۱ تا n. پایه‌ای برای ترکیب، جای‌گشت و احتمالات.
۲. عدد اول (Prime): عددی که فقط بر ۱ و خودش بخش‌پذیر است. پایه‌ی رمزنگاری مدرن.
۳. فیبوناچی: دنباله‌ای که هر جمله‌اش جمع دو جملهٔ قبلی است. در طبیعت، هنر و تحلیل الگوریتم‌ها ظاهر می‌شود.
نسخه اصلی جزوه برای هر کدام چند اشتباه تایپی داشت که در این درس همه را اصلاح می‌کنیم. هدف این است که هم الگوریتم را درست یاد بگیرید و هم مهارت اشکال‌زدایی از کدهای ناقص را پیدا کنید.
فاکتوریل چیست؟
فاکتوریل عدد n (با نماد n!) برابر است با:
$$n! = 1 \times 2 \times 3 \times ... \times n$$
به‌طور قراردادی، 0! = 1 تعریف می‌شود.
فاکتوریل در ریاضیات ترکیبیات، جای‌گشت و احتمالات به کار می‌رود. به‌عنوان مثال، تعداد جای‌گشت‌های n شیء متمایز برابر n! است.
نکته عملی: فاکتوریل خیلی سریع بزرگ می‌شود. 13! = 6,227,020,800 از محدوده int (۲ میلیارد) عبور می‌کند، پس برای n ≥ 13 باید از long long یا unsigned long long استفاده کنیم.
مثال ۱: محاسبه فاکتوریل n!
الگوریتم: یک متغیر p با مقدار اولیه ۱ (نه ۰، چون ۱ عنصر خنثی ضرب است) تعریف می‌کنیم و در هر گام آن را در i ضرب می‌کنیم. در پایان p برابر فاکتوریل خواهد بود.
به جای int از long long استفاده می‌کنیم تا برای n تا ۲۰ هم جواب درست بدهد.
با متغیر p به‌عنوان انباشتگر ضربی (با مقدار اولیه ۱)cpp
$خروجی برنامه
ورودی: 10
خروجی: 10! = 3628800
در حال باز کردن ویرایشگر…
فلوچارت: الگوریتم فاکتوریل
flow.svg
چرا p = 1 و نه p = 0؟
برای جمع، عنصر خنثی ۰ است (x + 0 = x). برای ضرب، عنصر خنثی ۱ است (x * 1 = x).
اگر فاکتوریل را با p = 0 شروع کنید، نتیجه همیشه ۰ می‌شود چون 0 * 1 * 2 * ... = 0. این یکی از رایج‌ترین اشتباهات مبتدی‌هاست.
قاعده کلی:
انباشتگر جمع: شروع با ۰
انباشتگر ضرب: شروع با ۱
سرریز (Overflow) در فاکتوریل
فاکتوریل به سرعت بزرگ می‌شود:
n
n!
10
3,628,800
12
479,001,600
13
6,227,020,800 (سرریز int)
20
2,432,902,008,176,640,000
21
سرریز long long
اگر در int ذخیره کنید و n = 21 وارد کنید، خروجی یک عدد منفی یا اشتباه می‌بینید چون بیت علامت تغییر می‌کند. این سرریز (Overflow) نام دارد و C++ هیچ هشداری نمی‌دهد.
راه‌حل‌ها:
از unsigned long long برای تا n = 20 استفاده کنید.
برای n بزرگتر، از کتابخانه‌های اعداد بزرگ (BigInt) استفاده کنید.
حتماً n را بررسی کنید که در محدوده باشد.
عدد اول چیست؟
یک عدد طبیعی اول (Prime) است اگر:
بزرگتر از ۱ باشد.
دقیقاً دو مقسوم‌علیه داشته باشد: ۱ و خودش.
پس اعداد ۰ و ۱ اول نیستند. کوچکترین عدد اول ۲ است و تنها عدد اول زوج است.
اعداد اول پایه‌ی رمزنگاری کلید عمومی (RSA) هستند و در امنیت اینترنت نقش حیاتی دارند.
روش تشخیص اول بودن در این درس: شمارش مقسوم‌علیه‌ها. اگر تعداد مقسوم‌علیه‌ها دقیقاً ۲ بود، عدد اول است.
مثال ۲: تشخیص عدد اول با شمارش مقسوم‌علیه‌ها
الگوریتم: برای عدد n، یک حلقه از ۱ تا n می‌چرخانیم و هر بار که n بر i بخش‌پذیر بود (یعنی n % i == 0)، یک واحد به شمارنده k اضافه می‌کنیم. اگر در پایان k == 2 بود، عدد اول است.
اگرچه این روش ساده است، اما برای اعداد بزرگ کند است؛ در ادامه با بهینه‌سازی آشنا می‌شویم.
اگر k == 2 یعنی اول، در غیر این صورت Not Primecpp
$خروجی برنامه
ورودی: 13
خروجی: Prime
در حال باز کردن ویرایشگر…
اشکال‌زدایی: اصلاح چند خطای تایپی
نسخه اصلی جزوه چند اشتباه تایپی داشت که در تصویر به سختی خوانده می‌شد:
n%i==o به جای n%i==0 — حرف o (انگلیسی) به جای عدد 0.
*k=0 به جای k=0 — ستارهٔ اضافی که اشاره‌گر می‌سازد.
if(k==2)* — ستارهٔ اضافی در انتهای شرط.
k++i به جای k++ — حرف i اضافی.
این نوع اشتباهات تایپی در دست‌نویس‌ها رایج است. همیشه کد را با کامپایلر چک کنید.
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
فلوچارت: تشخیص عدد اول
flow.svg
بهینه‌سازی: بررسی تا √n
بررسی تمام اعداد از ۱ تا n برای عدد اول بودن، برای n بزرگ کند است. اما یک حقیقت ریاضی مهم داریم:
اگر n عدد اولی نباشد، حداقل یک مقسوم‌علیه غیر از ۱ و خودش دارد که کوچکتر یا مساوی √n است.
پس کافی است فقط تا sqrt(n) بررسی کنیم. همچنین چون ۲ تنها عدد اول زوج است، می‌توانیم زوج‌ها را کنار بگذاریم. این الگوریتم از O(n) به O(√n) می‌رسد که برای n = 1000000 یعنی ۱۰۰۰ برابر سریع‌تر!
نمونه کد بهینه:
main.cppcpp
سری فیبوناچی
سری فیبوناچی دنباله‌ای است که در آن هر جمله برابر جمع دو جملهٔ قبلی است:
این دنباله در طبیعت (تعداد گلبرگ گل‌ها، مارپیچ صدفیش، تقسیم سلولی) ظاهر می‌شود و نسبت دو جملهٔ متوالی آن به عدد طلایی (φ ≈ 1.618) میل می‌کند.
الگوریتم تولید nامین جمله: دو متغیر a و b برای دو جملهٔ قبلی نگه می‌داریم و در هر گام، جملهٔ جدید c = a + b را محاسبه کرده و متغیر‌ها را جابجا (Shift) می‌کنیم.
مثال ۳: تولید سری فیبوناچی
ایده: با a = 1, b = 1 شروع می‌کنیم (دو جمله اول). در هر تکرار، جملهٔ جدید c = a + b را چاپ می‌کنیم و سپس جابجایی (Shift) انجام می‌دهیم: a = b و b = c تا برای تکرار بعدی آماده شوند.
این الگوی Shift یکی از مهم‌ترین تکنیک‌های برنامه‌نویسی است که در بسیاری از الگوریتم‌ها (مثل پیمایش لیست پیوندی، الگوریتم پنجره لغزان) ظاهر می‌شود.
چاپ n جمله اول سری فیبوناچیcpp
$خروجی برنامه
ورودی: 10
خروجی: 1 1 2 3 5 8 13 21 34 55
در حال باز کردن ویرایشگر…
فلوچارت: سری فیبوناچی
flow.svg
اشکال‌زدایی: اصلاح b=l به b=1
در نسخه دست‌نویس جزوه، حرف l کوچک انگلیسی (L) با عدد ۱ اشتباه گرفته شده بود. این یک خطای تایپی بسیار رایج در فونت‌های Monospace است. خوشبختانه کامپایلر این اشتباه را به‌عنوان خطای «متغیر تعریف‌نشده» گزارش می‌دهد.
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
جابجایی متغیر‌ها بدون متغیر کمکی
گاهی می‌خواهیم مقدار دو متغیر را بدون استفاده از متغیر سوم عوض کنیم. چند روش خلاقانه وجود دارد:
main.cppcpp
روش ۱ هم خواناتر و هم امن‌ترین است. در C++ می‌توانید از تابع آماده swap(a, b) در <utility> هم استفاده کنید.
در فیبوناچی نیازی به swap دو متغیر نداریم؛ فقط یک انتقال (Shift) به جلو انجام می‌دهیم.
برنامه‌ای بنویسید که عدد n را بگیرد و تعداد اعداد اول بین ۱ تا n را چاپ کند (با استفاده از تابع کمکی isPrime).
نمایش راهنما
یک تابع bool isPrime(int x) بنویسید و در main آن را برای هر عدد ۲ تا n صدا بزنید و شمارش کنید.
02
تمرین•حل کامل دارد
برنامه‌ای بنویسید که عدد n را بگیرد و n جمله اول سری فیبوناچی را چاپ کند، اما فقط جملاتی که اول هستند را با علامت * نشانه‌گذاری کند.
نمایش راهنما
در حلقه، بعد از محاسبه c، آن را به isPrime بدهید. اگر true بود، کنارش * چاپ کنید.
03
تمرین•حل کامل دارد
برنامه‌ای بنویسید که دو عدد m و n را بگیرد و مقدار ترکیب C(m, n) = m! / (n! * (m-n)!) را محاسبه کند (با فرض m >= n).
نمایش راهنما
یک تابع long long fact(int x) بنویسید که فاکتوریل را برگرداند و در main فرمول را اعمال کنید.
04
تمرین•حل کامل دارد
برنامه‌ای بنویسید که عدد n را بگیرد و بزرگترین عدد اول کوچکتر یا مساوی n را چاپ کند (به عبارت دیگر، n امین عدد اول نباید؛ بلکه اولین عدد اول از سمت n به پایین).
نمایش راهنما
از n شروع کنید و یکی یکی کم کنید تا به یک عدد اول برسید. از تابع isPrime استفاده کنید.
// نکات-کلیدی۵
01برای محاسبه فاکتوریل، از عنصر خنثی ضرب یعنی 1 شروع کنید و از long long برای n تا 20 استفاده کنید.
02فاکتوریل خیلی سریع بزرگ می‌شود؛ برای n >= 13 با int سرریز رخ می‌دهد و C++ هیچ هشداری نمی‌دهد.
03عدد اول برابر است با عددی که دقیقاً دو مقسوم‌علیه دارد (1 و خودش)؛ می‌توان با شمارش k به آن رسید.
04بهینه‌سازی تشخیص اول بودن: کافی است تا sqrt(n) بررسی کنیم، که از O(n) به O(sqrt(n)) می‌رسد.
05الگوی Shift در فیبوناچی (a = b; b = c;) یکی از پرکاربردترین تکنیک‌های برنامه‌نویسی برای پیمایش دنباله‌هاست.
نام درس، موضوع یا کلمه کلیدی را بنویسید و با Enter به آن بروید
1#include<iostream>2usingnamespace std;34intmain(){5int n;6longlong p =1;7 cin >> n;8for(int i =1; i <= n; i++){9 p *= i;// یا p = p * i;10}11 cout << n <<"! = "<< p << endl;12return0;13}
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, k =0;6 cin >> n;7for(int i =1; i <= n; i++){8if(n % i ==0){9 k++;10}11}12if(k ==2){13 cout <<"Prime"<< endl;14}else{15 cout <<"Not Prime"<< endl;16}17return0;18}
1main()2{3int n,*k =0;// خطا: *k یک اشاره‌گر است4 cin >> n;5for(int i =1; i <= n; i++){6if(n % i == o)// خطا: o حرف است نه 07 k++i;// خطا: ++i به جای ++8}9if(k ==2)*// خطا: * اضافی10 cout <<"Prime";11else12 cout <<"Not Prime";13}
1#include<iostream>2usingnamespace std;34intmain(){5int n, k =0;// k یک int معمولی است، نه اشاره‌گر6 cin >> n;7for(int i =1; i <= n; i++){8if(n % i ==0){// 0 عدد است9 k++;// ++ ساده10}11}12if(k ==2) cout <<"Prime"<< endl;13else cout <<"Not Prime"<< endl;14return0;15}
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.
شروع/پایانپردازشتصمیمورودی/خروجی
boolisPrime(int n){if(n <2)returnfalse;if(n ==2)returntrue;if(n %2==0)returnfalse;for(int i =3; i * i <= n; i +=2){if(n % i ==0)returnfalse;}returntrue;}
1#include<iostream>2usingnamespace std;34intmain(){5int n;6 cin >> n;7longlong a =1, b =1, c;8 cout << a <<" "<< b <<" ";9for(int i =3; i <= n; i++){10 c = a + b;11 cout << c <<" ";12 a = b;// جابجایی: a می‌شود b قبلی13 b = c;// b می‌شود c جدید14}15 cout << endl;16return0;17}
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.
شروع/پایانپردازشتصمیمورودی/خروجی
1main()2{3int a =1, b = l, c, n;// خطا: l تعریف نشده (باید 1 باشد)4 cin >> n;5 cout <<"1 l ";// چاپ "1 l" به جای "1 1"6for(i =3; i <= n; i++){// خطا: i تعریف نشده7 c = a + b;8 cout << c <<" ";9 a = b;10 b = c;11}12 cout << c;13}
1#include<iostream>2usingnamespace std;34intmain(){5int a =1, b =1, c =0, n;// 1 عدد است، نه l6 cin >> n;7 cout <<"1 1 ";8for(int i =3; i <= n; i++){// تعریف int i9 c = a + b;10 cout << c <<" ";11 a = b;12 b = c;13}14 cout << endl;15return0;16}
// روش 1: با متغیر کمکی (پیشنهاد شده)int temp = a; a = b; b = temp;// روش 2: XOR (سریع اما نامفهوم)a ^= b; b ^= a; a ^= b;// روش 3: جمع و تفریقa = a + b; b = a - b; a = a - b;