محاسبه عدد π با سری لایبنیتس (۱ - ۱/۳ + ۱/۵ - ...)
محاسبه sin(x) و cos(x) با سری تیلور
پیاده‌سازی الگوریتم اقلیدسی برای ب.م.م با while
تجزیه عدد به عوامل اول با حلقه for و while تودرتو
مدیریت دقت محاسبات اعشاری و سرریز فاکتوریل
مقدمه‌ای بر سری‌های نامتناهی
بسیاری از توابع ریاضی (sin، cos، exp، ln) و ثوابت معروف (π، e) را نمی‌توان با چند عملگر ساده محاسبه کرد. اما ریاضیدانان سری‌های نامتناهی پیدا کرده‌اند که با جمع کردن تعداد کافی جمله از آن‌ها، می‌توان به مقدار واقعی نزدیک شد.
سه سری معروف:
۱. سری لایبنیتس برای π: $\pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...$
۲. سری تیلور برای sin: $\sin x = x - x^3/3! + x^5/5! - x^7/7! + ...$
۳. سری تیلور برای cos: $\cos x = 1 - x^2/2! + x^4/4! - x^6/6! + ...$
هر چه جمله‌های بیشتری را جمع کنیم، نتیجه دقیق‌تر می‌شود. در کامپیوتر، تعداد جمله‌ها را به n محدود می‌کنیم (مثلاً n = 20).
در ادامه هر کدام را پیاده می‌کنیم و سپس به سراغ الگوریتم اقلیدسی و تجزیه اول می‌رویم.
هشدار دقت: این سری کند همگرا است؛ یعنی برای چند رقم اعشار دقیق، به هزاران جمله نیاز است. برای دقت بالا، سری‌های دیگری مثل سری ماچین بهتر هستند.
مثال ۱: محاسبه π با سری لایبنیتس
متغیر a نقش علامت را بازی می‌کند: در هر تکرار، آن را در -۱ ضرب می‌کنیم تا علامت جمله بعدی برعکس شود. مخرج جملهٔ iام برابر (2*i - 1) است.
برای دقت بهتر از double استفاده می‌کنیم، نه float.
با n جمله از سری، تقریبی از π را محاسبه می‌کندcpp
$خروجی برنامه
ورودی: 1000
خروجی: pi = 3.1405926538
(مقدار واقعی: 3.1415926535)
اصلاح: حساسیت به بزرگی حروف Sum
C++ به بزرگی و کوچکی حروف حساس است. در نسخه اصلی جزوه، متغیر Sum (با S بزرگ) تعریف می‌شد اما در داخل حلقه و در دستور cout با حروف کوچک sum نوشته می‌شد. این یک خطای نحوی (Syntax Error) است و کامپایلر از آن جلوگیری می‌کند. برای جلوگیری از این اشتباه، توصیه می‌شود همیشه از حروف کوچک برای نام متغیر‌ها استفاده کنید (مثلاً sum به جای Sum).
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
فلوچارت: محاسبه π با لایبنیتس
flow.svg
سری تیلور برای sin(x)
فرمول:
$$\sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + ...$$
الگوریتم با به‌روزرسانی پویای جمله‌ها:
جملهٔ اول: $a = x$، مخرج: $b = 1! = 1$
هر جمله: $a / b$ که به Sum اضافه می‌شود.
به‌روزرسانی برای جملهٔ بعدی:
صورت: $a_{new} = -a \cdot x^2$
مخرج: $b_{new} = b \cdot (2i) \cdot (2i+1)$ (چون از $(2i-1)!$ به $(2i+1)!$ می‌رسیم)
نکته مهم: زاویه $x$ باید بر حسب رادیان باشد، نه درجه. برای تبدیل درجه به رادیان: $\text{rad} = \text{deg} \cdot \pi / 180$.
مثال ۲: محاسبه sin(x) با سری تیلور
متغیر a نقش صورت و b نقش مخرج جمله را دارد. در هر تکرار، a / b به Sum اضافه می‌شود و سپس a و b برای جملهٔ بعدی به‌روز می‌شوند.
اگرچه می‌توانستیم در هر تکرار فاکتوریل را از صفر حساب کنیم، اما این روش پویا بسیار کارآمدتر است، هیچ محاسبهٔ تکراری انجام نمی‌شود.
با n جمله از سری تیلور، sin(x) را تقریب می‌زندcpp
$خروجی برنامه
ورودی: 10 1.5708
خروجی: my sin = 1.000000
cmath = 1.000000
رادیان یا درجه؟
توابع sin، cos، tan در کتابخانه <cmath> و در سری تیلور زاویه را بر حسب رادیان می‌گیرند، نه درجه.
رابطهٔ تبدیل:
۳۶۰ درجه = ۲π رادیان
۱ درجه = π / 180 رادیان
۱ رادیان ≈ ۵۷.۳ درجه
برای مثال، sin(90°) = 1، اما sin(90) در C++ مقدار ۰.۸۹ می‌دهد چون ۹۰ رادیان است!
برای کار با درجه، قبل از فراخوانی sin تبدیل کنید:
main.cppcpp
M_PI در <cmath> تعریف شده (البته در بعضی کامپایلر‌ها باید #define _USE_MATH_DEFINES قبل از include بیاید).
به‌روزرسانی مخرج: از $(2i-2)!$ به $(2i)!$ می‌رسیم، پس ضریب جدید $(2i)(2i-1)$ است. این تفاوت کوچک اما مهم است، در کد، آن را با (2*i)*(2*i-1) می‌نویسیم (در مقابل (2*i)*(2*i+1) در sin).
ورودی: 10 0
خروجی: my cos = 1.000000
cmath = 1.000000
اصلاح: case sensitivity در sin و cos
در نسخه اصلی جزوه، در تمام برنامه‌های sin و cos، متغیر Sum در ابتدا با S بزرگ تعریف می‌شد اما در داخل حلقه و در cout با s کوچک نوشته می‌شد (sum). این خطای نحوی باعث کامپایل نشدن کد می‌شود.
توصیه: همیشه از سبک snake_case با حروف کوچک برای نام‌گذاری متغیر‌ها استفاده کنید. این کار از خطاهای تایپی جلوگیری می‌کند و کد را خواناتر می‌کند.
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
الگوریتم اقلیدسی برای ب.م.م
بزرگترین مقسوم‌علیه مشترک (GCD) دو عدد a و b، بزرگترین عددی است که هر دو را بدون باقیمانده تقسیم می‌کند.
الگوریتم اقلیدسی یکی از قدیمی‌ترین الگوریتم‌های شناخته‌شده (توسط اقلیدس، ۳۰۰ سال قبل از میلاد) و بسیار کارآمد است:
main.cppcpp
مثال: GCD(48, 18)
48 mod 18 = 12 → a=18, b=12
18 mod 12 = 6 → a=12, b=6
12 mod 6 = 0 → a=6, b=0
پایان؛ GCD = 6.
این الگوریتم در رمزنگاری RSA و ساده‌سازی کسر‌ها کاربرد دارد.
مثال ۴: محاسبه ب.م.م با الگوریتم اقلیدسی
الگوریتم: تا وقتی a % b != 0، باقیمانده را محاسبه می‌کنیم، a را به b تبدیل می‌کنیم و b را به باقیمانده. وقتی b == 0 شد، a برابر GCD است.
نکته: این الگوریتم حتی اگر a < b باشد هم درست کار می‌کند؛ چون در تکرار اول، a و b جابجا می‌شوند (چون a % b = a وقتی a < b).
با while و جای‌جایی a, b, rcpp
$خروجی برنامه
ورودی: 48 18
خروجی: GCD = 6
در حال باز کردن ویرایشگر…
فلوچارت: الگوریتم اقلیدسی
flow.svg
نسخه بازگشتی الگوریتم اقلیدسی
الگوریتم اقلیدسی به‌صورت طبیعی بازگشتی است:
main.cppcpp
نسخهٔ بازگشتی کوتاه‌تر و خواناتر است، اما نسخهٔ تکراری (با while) کارآمدتر است چون سربار فراخوانی تابع را ندارد.
برای کسر‌های بزرگ در رمزنگاری، از نسخهٔ تکراری استفاده می‌شود. همچنین می‌توان از الگوریتم باینری GCD (با عملگر‌های بیتی) برای سرعت بیشتر استفاده کرد.
همچنین با داشتن GCD می‌توان ک.م.م (LCM) را حساب کرد:
main.cppcpp
(تقسیم را قبل از ضرب انجام می‌دهیم تا از سرریز جلوگیری شود.)
تجزیه عدد به عوامل اول
هر عدد صحیح بزرگ‌تر از ۱ را می‌توان به طور یکتا به‌صورت ضربی از اعداد اول نوشت. این قضیه اساسی حساب نام دارد.
مثال: 84 = 2² × 3¹ × 7¹
الگوریتم تجزیه:
از i = 2 شروع می‌کنیم.
تا وقتی n % i == 0 است، n را بر i تقسیم می‌کنیم و شمارنده را زیاد می‌کنیم.
اگر شمارنده > 0 بود، عامل i به همراه توانش را چاپ می‌کنیم.
به i بعدی می‌رویم.
توقف: وقتی n == 1 شد.
بهینه‌سازی مهم: کافی است i را فقط تا sqrt(n) امتحان کنیم. اگر بعد از این مرحله n > 1 بود، خود n یک عدد اول است.
این الگوریتم پایهٔ رمزنگاری RSA است (که در آن تجزیهٔ عدد بزرگ بسیار سخت است).
مثال ۵: تجزیه عدد به عوامل اول
این الگوریتم ترکیبی از for (برای امتحان هر عامل) و while (برای تقسیم مکرر) است. به ازای هر i که عامل است، تا وقتی n بر i بخش‌پذیر است، تقسیم می‌کنیم و شمارنده k را زیاد می‌کنیم.
اگر k > 0 بود، یعنی i واقعاً یک عامل اول بوده و آن را با توانش چاپ می‌کنیم.
عدد n را به‌صورت p1^k1 * p2^k2 * ... چاپ می‌کندcpp
$خروجی برنامه
ورودی: 84
خروجی: 84 = 2^2 * 3^1 * 7^1
در حال باز کردن ویرایشگر…
تجزیه اول یا شمارش مقسوم‌علیه‌ها؟
دو مسئلهٔ متفاوت داریم که گاهی اشتباه گرفته می‌شوند:
۱. تجزیه به عوامل اول: یافتن اعداد اولی که در تجزیهٔ عدد نقش دارند. مثلاً 60 = 2² × 3 × 5.
۲. شمارش تعداد مقسوم‌علیه‌ها: یافتن تعداد اعدادی که عدد را بدون باقیمانده تقسیم می‌کنند. مثلاً مقسوم‌علیه‌های 60 عبارت‌اند از ۱، ۲، ۳، ۴، ۵، ۶، ۱۰، ۱۲، ۱۵، ۲۰، ۳۰، ۶۰ → ۱۲ مقسوم‌علیه.
رابطهٔ جالب: اگر تجزیهٔ عدد برابر $p_1^{a_1} \cdot p_2^{a_2} \cdot ...$ باشد، تعداد مقسوم‌علیه‌ها برابر $(a_1+1)(a_2+1)...$ است.
برنامه‌ای بنویسید که تعداد n را بگیرد و با سری لایبنیتس، π را تقریب بزند. سپس اختلاف بین مقدار محاسبه‌شده و M_PI را چاپ کند.
نمایش راهنما
از #include <cmath> و M_PI استفاده کنید. اختلاف را با fabs(pi - M_PI) محاسبه کنید.
02
تمرین•حل کامل دارد
برنامه‌ای بنویسید که یک زاویه بر حسب درجه دریافت کند و sin و cos آن را با سری تیلور محاسبه و چاپ کند. زاویه را ابتدا به رادیان تبدیل کنید.
نمایش راهنما
deg * M_PI / 180 را به‌عنوان x به الگوریتم تیلور بدهید. از 10 جمله استفاده کنید.
03
تمرین•حل کامل دارد
برنامه‌ای بنویسید که دو عدد a و b را بگیرد و ک.م.م آن‌ها را با استفاده از GCD محاسبه کند. فرمول: lcm(a,b) = a / gcd(a,b) * b.
نمایش راهنما
ابتدا gcd را با الگوریتم اقلیدسی محاسبه کنید، سپس فرمول lcm را اعمال کنید. دقت کنید تقسیم را قبل از ضرب انجام دهید تا از سرریز جلوگیری شود.
04
تمرین•حل کامل دارد
برنامه‌ای بنویسید که عدد n را بگیرد و تعداد مقسوم‌علیه‌های آن را با استفاده از فرمول تجزیهٔ اول محاسبه کند. یعنی اگر n = p1^a1 * p2^a2 * ...، تعداد مقسوم‌علیه‌ها برابر (a1+1)(a2+1)... است.
نمایش راهنما
ابتدا عوامل اول و توان‌هایشان را پیدا کنید. برای هر توان k، (k+1) را در یک متغیر prod ضرب کنید. برای اعداد اول (که فقط یک عامل با توان 1 دارند) جواب 2 خواهد بود.
05
تمرین•حل کامل دارد
برنامه‌ای بنویسید که عدد n را بگیرد و مجموع تمام مقسوم‌علیه‌های آن (به جز خودش) را چاپ کند. اگر مجموع برابر خود عدد بود، پیام "Perfect Number" چاپ کند (مثل 6 = 1+2+3 یا 28 = 1+2+4+7+14).
نمایش راهنما
از 1 تا n/1 حلقه بزنید و اگر n%i==0 بود، i را به sum اضافه کنید. در پایان با n مقایسه کنید.
// نکات-کلیدی۵
01سری لایبنیتس π/4 = 1 - 1/3 + 1/5 - 1/7 + ... کند همگرا است اما ساده و آموزشی است.
02در سری تیلور برای sin و cos، به‌جای محاسبهٔ فاکتوریل و توان از صفر، از به‌روزرسانی پویای صورت و مخرج استفاده کنید.
03الگوریتم اقلیدسی برای GCD بسیار کارآمد است: در O(log(min(a,b))) اجرا می‌شود.
04با داشتن GCD می‌توان LCM را با فرمول a/gcd*b محاسبه کرد (تقسیم قبل از ضرب برای جلوگیری از سرریز).
05هر عدد صحیح بزرگ‌تر از ۱ را می‌توان به طور یکتا به‌صورت ضربی از اعداد اول تجزیه کرد؛ تعداد مقسوم‌علیه‌ها از رابطهٔ (a1+1)(a2+1)... به دست می‌آید.
گام بعدی پیشنهادی
حلقه‌های تودرتو و الگوهای نجومی
رسم مثلث، مربع، لوزی، ضربدری و صلیب با ستاره‌ها به کمک حلقه‌های تودرتو
نام درس، موضوع یا کلمه کلیدی را بنویسید و با Enter به آن بروید
1#include<iostream>2#include<iomanip>3usingnamespace std;45intmain(){6int n;7double sum =0, a =1;// a نقش علامت را دارد8 cin >> n;9for(int i =1; i <= n; i++){10 sum += a /(2* i -1);11 a *=-1;// برگرداندن علامت12}13double pi =4* sum;14 cout << fixed <<setprecision(10);15 cout <<"pi = "<< pi << endl;16return0;17}
1main()2{3float n, Sum =0, a =1;// Sum با S بزرگ4 cin >> n;5for(int i =1; i <= n; i++){6 sum += a /(2* i -1);// خطا: sum با s کوچک تعریف نشده7 a *=-1;8}9 cout << Sum;// این درست است10}
1#include<iostream>2usingnamespace std;34intmain(){5int n;6double sum =0, a =1;7 cin >> n;8for(int i =1; i <= n; i++){9 sum += a /(2* i -1);10 a *=-1;11}12 cout <<4* sum << endl;13return0;14}
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>2#include<cmath>3#include<iomanip>4usingnamespace std;56intmain(){7int n;8double x, sum =0, a, b;9 cin >> n >> x;10 a = x;11 b =1;12for(int i =1; i <= n; i++){13 sum += a / b;14 a =-a * x * x;15 b = b *(2* i)*(2* i +1);16}17 cout << fixed <<setprecision(6);18 cout <<"my sin = "<< sum << endl;19 cout <<"cmath = "<<sin(x)<< endl;20return0;21}
double rad = deg * M_PI /180.0;double result =sin(rad);
1#include<iostream>2#include<cmath>3#include<iomanip>4usingnamespace std;56intmain(){7int n;8double x, sum =0, a =1, b =1;9 cin >> n >> x;10for(int i =1; i <= n; i++){11 sum += a / b;12 a =-a * x * x;13 b = b *(2* i)*(2* i -1);14}15 cout << fixed <<setprecision(6);16 cout <<"my cos = "<< sum << endl;17 cout <<"cmath = "<<cos(x)<< endl;18return0;19}
1main()2{3int n;4double x, Sum =0, a, b;5 cin >> n >> x;6 a = x; b =1;7for(int i =1; i <= n; i++){8 sum += a / b;// خطا: sum به جای Sum9 a =-a * x * x;10 b = b *(2*i)*(2*i+1);11}12 cout << sum;// خطا13}
1#include<iostream>2#include<cmath>3usingnamespace std;45intmain(){6int n;7double x, sum =0, a, b;8 cin >> n >> x;9 a = x; b =1;10for(int i =1; i <= n; i++){11 sum += a / b;12 a =-a * x * x;13 b = b *(2* i)*(2* i +1);14}15 cout << sum << endl;16return0;17}
تا وقتی b ≠ 0: r = a mod b
a = b
b = r
پس از پایان، a برابر GCD است.
1#include<iostream>2usingnamespace std;34intmain(){5int a, b;6 cin >> a >> b;7while(b !=0){8int r = a % b;9 a = b;10 b = r;11}12 cout <<"GCD = "<< a << endl;13return0;14}
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.
شروع/پایانپردازشتصمیمورودی/خروجی
intgcd(int a,int b){if(b ==0)return a;returngcd(b, a % b);}
intlcm(int a,int b){return a /gcd(a, b)* b;}
1#include<iostream>2usingnamespace std;34intmain(){5int n;6 cin >> n;7 cout << n <<" = ";8bool first =true;9for(int i =2; i <= n; i++){10int k =0;11while(n % i ==0){12 k++;13 n /= i;14}15if(k >0){16if(!first) cout <<" * ";17 cout << i <<"^"<< k;18 first =false;19}20if(n ==1)break;21}22 cout << endl;23return0;24}