برای کار با ارقام یک عدد صحیح، دو عملگر کلاسیک داریم که با هم همه کار‌ها را انجام می‌دهند:
n % 10 — باقیمانده تقسیم بر ۱۰، یعنی رقم آخر (یکان) را برمی‌گرداند. مثلاً 457 % 10 = 7.
n / 10 — تقسیم صحیح بر ۱۰، یعنی رقم آخر را حذف می‌کند. مثلاً 457 / 10 = 45.
با ترکیب این دو در یک حلقه while (n > 0)، می‌توانیم هر عملیاتی روی ارقام انجام دهیم:
مجموع ارقام
چاپ معکوس
ساخت عدد معکوس
تشخیص پالیندروم
شمارش تکرار یک رقم
شمارش ارقام زوج/فرد
این درس شامل پنج الگوریتم کامل است که هر کدام یک تکنیک پایه را آموزش می‌دهد.
مثال ۱: محاسبه مجموع ارقام
الگوریتم: در هر تکرار، رقم آخر را با n % 10 می‌گیریم، به sum اضافه می‌کنیم و سپس n را با n / 10 یک رقم کوتاه می‌کنیم. این کار را تا رسیدن n به ۰ ادامه می‌دهیم.
مثال: n = 457 → جمع ۴ + ۵ + ۷ = ۱۶.
مجموع تک‌تک ارقام عدد n را محاسبه و چاپ می‌کندcpp
$خروجی برنامه
ورودی: 457
خروجی: 7 5 4
sum of digits = 16
در حال باز کردن ویرایشگر…
فلوچارت: مجموع ارقام
flow.svg
مثال ۲: چاپ ارقام به‌صورت معکوس
این الگوریتم بسیار شبیه مجموع ارقام است، اما به جای جمع کردن، فقط هر رقم را با cout چاپ می‌کنیم. به این ترتیب ارقام از انتها به ابتدا نمایش داده می‌شوند.
مثال: n = 12345 → خروجی 5 4 3 2 1.
این فقط چاپ معکوس است، نه ساخت عدد معکوس. برای ساخت عدد معکوس باید فرمول متفاوتی بکار ببریم که در مثال بعد می‌آید.
ارقام عدد را از آخر به اول چاپ می‌کندcpp
$خروجی برنامه
ورودی: 12345
خروجی: 54321
در حال باز کردن ویرایشگر…
تفاوت چاپ معکوس و ساخت عدد معکوس
دو الگوریتم متفاوت داریم:
چاپ معکوس: ارقام را یکی یکی از انتها چاپ می‌کنیم.
main.cppcpp
ورودی 457 → خروجی روی صفحه: 754.
ساخت عدد معکوس: یک عدد جدید می‌سازیم که مقدار آن معکوس عدد اصلی است.
main.cppcpp
ورودی 457 → مقدار rev: 754 (یک عدد واقعی).
تفاوت در فرمول rev * 10 + digit است که رقم جدید را به انتهای عدد می‌چسباند. این الگوریتم برای تشخیص پالیندروم لازم است.
مثال ۳: تشخیص عدد پالیندروم (متقارن)
عدد پالیندروم (Palindrome) یا متقارن، عددی است که از چپ به راست و از راست به چپ یکی خوانده شود؛ مثل ۱۲۱، ۱۲۳۲۱، ۴۵۵۴.
الگوریتم: یک کپی از عدد اصلی به نام n2 نگه می‌داریم. سپس با حلقه while، معکوس عدد را در rev می‌سازیم. در پایان اگر rev == n2 بود، عدد پالیندروم است.
نکته مهم: متغیر rev باید قبل از حلقه با ۰ مقداردهی شود، وگرنه مقدار زباله (Garbage Value) خواهد داشت.
بررسی می‌کند آیا عدد با معکوس خود برابر استcpp
$خروجی برنامه
ورودی: 12321
خروجی: Yes (palindrome)
در حال باز کردن ویرایشگر…
اصلاح: مقداردهی اولیه rev و n2
در نسخه اصلی جزوه، متغیر‌های Sum (یا rev) و n2 قبل از حلقه while مقداردهی اولیه نشده بودند. این باعث می‌شد Sum مقدار زباله (Garbage Value) داشته باشد و نتیجه کاملاً اشتباه از آب دربیاید. همچنین متغیر n در حلقه تخریب می‌شد و نیاز به کپی n2 = n قبل از حلقه بود.
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
فلوچارت: تشخیص پالیندروم
flow.svg
مثال ۴: شمارش تکرار یک رقم خاص
الگوریتم: ارقام n را یکی یکی استخراج می‌کنیم و با b مقایسه می‌کنیم. هر بار که برابر بودند، شمارنده k را یک واحد افزایش می‌دهیم.
مثال: n = 122333, b = 3 → خروجی 3 چون رقم ۳ سه بار آمده.
تعداد دفعاتی که رقم b در عدد n آمده را می‌شماردcpp
$خروجی برنامه
ورودی: 122333 3
خروجی: 3
در حال باز کردن ویرایشگر…
تله خطرناک: فراموش کردن n /= 10
اگر در حلقه‌های پردازش ارقام، خط n /= 10 را فراموش کنید، حلقه بی‌نهایت می‌شود. چون n هرگز تغییر نمی‌کند، شرط n > 0 همیشه برقرار می‌ماند و حلقه تا ابد (یا تا زمانی که حافظه پر شود) اجرا می‌شود.
این باگ در نسخه اصلی جزوه هم وجود داشت. همیشه قبل از اجرا بررسی کنید:
آیا در بدنه while چیزی هست که شرط را تغییر دهد؟
آیا این تغییر به سمت false بودن شرط می‌رود؟
اگر هر دو پاسخ «بله» نبود، حتماً باگی وجود دارد.
فلوچارت: شمارش تکرار رقم
flow.svg
مثال ۵: شمارش توان ۲ در تجزیه عدد
هر عدد صحیح را می‌توان به‌صورت ضربی از اعداد اول نوشت. مثلاً 24 = 2³ × 3¹. توان ۲ در تجزیهٔ ۲۴ برابر ۳ است.
الگوریتم: تا وقتی n زوج است (n % 2 == 0)، آن را بر ۲ تقسیم می‌کنیم و شمارنده را یکی افزایش می‌دهیم. تعداد تقسیم‌ها برابر توان ۲ در تجزیه است.
مثال: 24 → 12 → 6 → 3 (سه بار تقسیم بر ۲ شد، تا رسیدن به عدد فرد ۳). پس توان ۲ در تجزیه ۲۴ برابر ۳.
تعداد دفعاتی که عدد بر ۲ بخش‌پذیر است را می‌شماردcpp
$خروجی برنامه
ورودی: 24
خروجی: power of 2 = 3
در حال باز کردن ویرایشگر…
چرا توان ۲ مهم است؟
شمارش توان ۲ در تجزیهٔ عدد در چند زمینه مهم است:
رمزنگاری: در الگوریتم‌هایی مثل Miller-Rabin برای تشخیص عدد اول.
نظریه اعداد: توابع موبیوس و توابع ضربی.
پردازش بیتی: تشخیص اینکه آیا عدد دقیقاً توان ۲ است (یعنی در تجزیه‌اش فقط عامل ۲ با توان k ≥ 1 حضور دارد و هیچ عامل اول دیگری ندارد).
ترفند معروف تشخیص توان ۲: عدد n توان ۲ است اگر و فقط اگر n > 0 و (n & (n - 1)) == 0 باشد — مثلاً 8 & 7 برابر 0 می‌شود. دقت کنید پرانتز دور n & (n-1)اجباری است: تقدم == از & بالاتر است و بدون پرانتز، عبارت n & (n-1) == 0 به‌صورت n & ((n-1) == 0) ارزیابی می‌شود — همان تله‌ای که در درس عملگر‌ها دیدیم.
می‌توانید با تعمیم این الگوریتم، توان هر عدد اول دیگر (۳، ۵، ۷، …) را هم بشمارید، کافی است % 2 و /= 2 را تغییر دهید.
نام درس، موضوع یا کلمه کلیدی را بنویسید و با Enter به آن بروید
1#include<iostream>2usingnamespace std;34intmain(){5int n, sum =0;6 cin >> n;7while(n >0){8 sum += n %10;// افزودن رقم آخر به مجموع9 cout << n %10<<" ";// اختیاری: چاپ تک‌تک ارقام10 n /=10;// حذف رقم آخر11}12 cout << endl <<"sum of digits = "<< 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>2usingnamespace std;34intmain(){5int n;6 cin >> n;7while(n >0){8 cout << n %10;9 n /=10;10}11 cout << endl;12return0;13}
while(n >0){ cout << n %10; n /=10;}
int rev =0;while(n >0){ rev = rev *10+ n %10; n /=10;}
1#include<iostream>2usingnamespace std;34intmain(){5int n;6 cin >> n;7int n2 = n;// کپی از عدد اصلی8int rev =0;// مقداردهی اولیه الزامی9while(n >0){10int r = n %10;11 rev = rev *10+ r;12 n /=10;13}14if(rev == n2){15 cout <<"Yes (palindrome)"<< endl;16}else{17 cout <<"No"<< endl;18}19return0;20}
1main()2{3int n, Sum, n2;// خطا: Sum و n2 مقداردهی نشده‌اند4 cin >> n;5while(n >0){6 r = n %10;// خطا: r تعریف نشده7 Sum = Sum *10+ r;8 n /=10;9}10if(Sum == n2)// نادرست: n2 همیشه 0 است11 cout <<"Yes";12else13 cout <<"No";14}
1#include<iostream>2usingnamespace std;34intmain(){5int n, r, rev =0;6 cin >> n;7int n2 = n;// کپی قبل از تخریب n8while(n >0){9 r = n %10;10 rev = rev *10+ r;11 n /=10;12}13if(rev == n2) cout <<"Yes";14else cout <<"No";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.
شروع/پایانپردازشتصمیمورودی/خروجی
1#include<iostream>2usingnamespace std;34intmain(){5int n, b, k =0;6 cin >> n >> b;7while(n >0){8int r = n %10;9if(r == b){10 k++;11}12 n /=10;13}14 cout << k << endl;15return0;16}
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;7while(n %2==0){8 k++;9 n /=2;10}11 cout <<"power of 2 = "<< k << endl;12return0;13}