بخش سوم : کنترل جریان برنامه¶
مقدمه¶
تا اینجای درس، همهی برنامههای ما یک ویژگی مشترک داشتند: دستورها از اولین خط تا آخرین خط، دقیقاً یکبار و به همان ترتیبی که نوشته شدهاند اجرا میشدند. به این الگو اجرای ترتیبی (Sequence) میگوییم. اما مسئلههای واقعی اینطور نیستند. وقتی یک سیستم بانکی میخواهد برداشت از حساب را انجام دهد، باید ابتدا تصمیم بگیرد: «اگر موجودی کافی است، برداشت را ثبت کن؛ وگرنه پیام خطا بده». وقتی میخواهیم میانگین نمرات یک کلاس را حساب کنیم، باید یک کار مشخص را برای هر دانشجو تکرار کنیم، بدون اینکه تعداد دانشجویان در زمان نوشتن برنامه معلوم باشد. یعنی دو نیاز تازه پیدا کردهایم: تصمیمگیری و تکرار.
این بخش دقیقاً به همین دو نیاز پاسخ میدهد. در فصل ۸ با ساختارهای شرطی (if، else if، else، عملگر ?: و switch) یاد میگیریم برنامه چگونه بین چند مسیر یکی را انتخاب کند. در فصل ۹ با حلقهها (while، do-while، for) و ابزارهای کنترل آنها (break، continue) یاد میگیریم برنامه چگونه یک کار را تکرار کند، و در پایان، دلیل اینکه چرا دستور goto را عملاً کنار میگذاریم بررسی میشود.
در طول این بخش از یک سناریوی واحد استفاده میکنیم تا مفاهیم پراکنده نمانند: برنامهی ارزیابی نمرات کلاس. نمرهها را اعتبارسنجی میکنیم، درجهبندی میکنیم، از ورودی میخوانیم، میانگین و بیشترین و کمترین را حساب میکنیم و در نهایت یک منوی تعاملی میسازیم. در کنار آن، چند الگوریتم کلاسیک کوچک (سال کبیسه، شمارش ارقام، عدد اول، بزرگترین مقسومعلیه مشترک) هم میبینیم، چون بهترین محل برای تمرین «فکر کردن با شرط و حلقه» هستند.
نقشه کلی بخش:¶
اجرای ترتیبی (Sequence)
│
├── نیاز به «تصمیمگیری» ──► Selection (فصل ۷)
│ if / if-else / else-if / ?: / switch
│
└── نیاز به «تکرار» ──────► Iteration (فصل ۸)
while / do-while / for
│
├── حلقههای تودرتو
├── break / continue
└── goto (و دلیل پرهیز از آن)
الگوهای مهم حلقه:
Counter / Accumulator / Min-Max / Search / Sentinel / Convergenceفصل ۷ : ساختارهای شرطی (Conditional Structures)¶
7.1 چرا به شرط نیاز داریم؟¶
فرض کنید در برنامهی ارزیابی نمرات، میخواهیم برای یک دانشجو وضعیت «قبول» یا «مردود» را چاپ کنیم. نمرهی قبولی در این درس ۱۰ از ۲۰ است. با دانش فعلیمان چنین مینویسیم:
%%writefile src/p04_c08_01_sequential_naive.c
#include <stdio.h>
int main(void)
{
int score = 8;
printf("Score: %d\n", score);
printf("Status: Pass\n");
printf("Status: Fail\n");
return 0;
}
!gcc -Wall -o bin/p04_c08_01_sequential_naive src/p04_c08_01_sequential_naive.c && ./bin/p04_c08_01_sequential_naiveScore: 8
Status: Pass
Status: Fail
خروجی بالا بیمعنی است: برای نمرهی ۸ هر دو پیام «قبول» و «مردود» چاپ شده است. اگر مقدار score را عوض کنیم، باز هم همین دو خط چاپ میشود. دلیلش ساده است: در اجرای ترتیبی، برنامه هیچ راهی برای «نگاه کردن به داده و تصمیم گرفتن» ندارد؛ هر دستور فقط به این دلیل اجرا میشود که در فهرست قرار دارد. چند سؤال از خودتان بپرسید:
اگر بخواهیم فقط برای نمرههای کمتر از ۱۰ پیام «مردود» چاپ شود، این تصمیم را در کدام خط بگیریم؟
اگر بخواهیم برای نمرههای ۱۷ به بالا پیام «عالی»، برای ۱۴ تا ۱۶ پیام «خوب» و برای بقیهی قبولیها پیام «قبول» چاپ شود، فقط با
printfچه کار میتوانیم بکنیم؟اگر نمره از کاربر گرفته شود (و در زمان نوشتن برنامه معلوم نباشد)، چطور برنامه باید رفتارش را با آن تطبیق دهد؟
مشکل اصلی این است: ما به سازهای نیاز داریم که:
یک شرط را بسنجد (نتیجهی آن فقط «درست» یا «نادرست» باشد).
بر اساس نتیجهی شرط، فقط یکی از چند مسیر را اجرا کند.
مسیرهای انتخابنشده را کاملاً نادیده بگیرد.
این دقیقاً همان چیزی است که ساختار انتخاب (Selection) فراهم میکند. شکل کلی آن را بهصورت Flowchart ببینید:
تمرین درون فصل ۸.۱¶
نوع تمرین: Quick Reasoning
برنامهی sequential_naive را در نظر بگیرید. فرض کنید مقدار score را به 19 تغییر دهیم. آیا خروجی برنامه تغییر میکند؟ بدون اجرای کد توضیح دهید چرا نمیتوان فقط با تغییر ورودی، این برنامه را «درست» کرد و چه چیزی در ساختار برنامه کم است.
8.2 شرط در زبان C: درست، نادرست و عملگرهای منطقی¶
پیش از دیدن if، باید دقیقاً بدانیم «شرط» چیست. شرط در برنامهنویسی هر عبارتی است که نتیجهاش به یکی از دو حالت «درست» یا «نادرست» تعبیر میشود. زبان C برخلاف زبانهایی مثل Python یا Java، در استاندارد کلاسیکش نوع دادهی مستقل bool ندارد و از اعداد صحیح برای این کار استفاده میکند. قرارداد C این است:
مقدار صفر یعنی نادرست (False).
هر مقدار غیرصفر (۱، ۵، -۳ و ...) یعنی درست (True).
عبارتهای مقایسهای و منطقی همیشه یکی از دو مقدار
1(درست) یا0(نادرست) را تولید میکنند.
عملگرهای مقایسهای (Relational)¶
| عملگر | معنی | مثال | نتیجه |
|---|---|---|---|
== | برابر است با | 5 == 5 | 1 |
!= | برابر نیست با | 5 != 5 | 0 |
< , <= | کوچکتر، کوچکتر یا مساوی | 3 < 5 | 1 |
> , >= | بزرگتر، بزرگتر یا مساوی | 3 >= 5 | 0 |
عملگرهای منطقی (Logical)¶
| عملگر | نام | معنی |
|---|---|---|
&& | AND | وقتی درست است که هر دو طرف درست باشند |
|| | OR | وقتی درست است که حداقل یکی از دو طرف درست باشد |
! | NOT | نتیجه را برعکس میکند |
جدول درستی (Truth Table) دو عملگر && و || را ببینید (A و B دو شرط دلخواهاند):
| A | B | A && B | A || B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
%%writefile src/p04_c08_02_boolean_expr.c
#include <stdio.h>
int main(void)
{
int a = 7, b = 3;
printf("a > b -> %d\n", a > b);
printf("a == b -> %d\n", a == b);
printf("a != b -> %d\n", a != b);
printf("a > 5 && b > 5 -> %d\n", a > 5 && b > 5);
printf("a > 5 || b > 5 -> %d\n", a > 5 || b > 5);
printf("!(a > b) -> %d\n", !(a > b));
printf("!!a (a is 7) -> %d\n", !!a);
return 0;
}
Writing src/p04_c08_02_boolean_expr.c
!gcc -Wall -o bin/p04_c08_02_boolean_expr src/p04_c08_02_boolean_expr.c && ./bin/p04_c08_02_boolean_expra > b -> 1
a == b -> 0
a != b -> 1
a > 5 && b > 5 -> 0
a > 5 || b > 5 -> 1
!(a > b) -> 0
!!a (a is 7) -> 1
خط آخر نکتهی مهمی را نشان میدهد: a برابر ۷ است (نه ۱)، اما در یک شرط «درست» محسوب میشود، چون غیرصفر است؛ و عملگر ! دوبار روی آن اثر کرده و آن را به مقدار استاندارد 1 تبدیل کرده است.
ارزیابی کوتاهمدار (Short-Circuit Evaluation)¶
یک ویژگی بسیار مهم && و || این است که طرف راست فقط در صورت لزوم ارزیابی میشود:
در
A && B، اگرAنادرست باشد، نتیجه قطعاً نادرست است وBاصلاً ارزیابی نمیشود.در
A || B، اگرAدرست باشد، نتیجه قطعاً درست است وBاصلاً ارزیابی نمیشود.
این فقط یک بهینهسازی نیست؛ یک ابزار الگوریتمی است. با ترتیب دادن درست شرطها میتوانیم یک محاسبهی خطرناک را «نگهبانی» کنیم (Guard):
%%writefile src/p04_c08_03_short_circuit.c
#include <stdio.h>
int main(void)
{
int x = 0;
int calls = 0;
/* Guard: the division is evaluated only when x != 0 */
if (x != 0 && 10 / x > 1) {
printf("10 / x is greater than 1\n");
} else {
printf("Skipped: x is zero, the division never ran\n");
}
/* Side effect on the right side of || */
if (x == 0 || ++calls > 0) {
printf("calls = %d (the right side did not run)\n", calls);
}
return 0;
}
Writing src/p04_c08_03_short_circuit.c
!gcc -Wall -o bin/p04_c08_03_short_circuit src/p04_c08_03_short_circuit.c && ./bin/p04_c08_03_short_circuitSkipped: x is zero, the division never ran
calls = 0 (the right side did not run)
چرا ترتیب شرطها در x != 0 && 10 / x > 1 مهم است؟
اگر ترتیب را برعکس کنیم (10 / x > 1 && x != 0)، ابتدا تقسیم بر صفر ارزیابی میشود و برنامه دچار خطای زمان اجرا میشود. با قرار دادن «شرطِ نگهبان» در سمت چپ، تضمین میکنیم طرف راست فقط وقتی اجرا شود که امن است.
چرا در خط دوم برنامه مقدار calls هنوز صفر است؟
چون x == 0 درست است و در || وقتی طرف چپ درست باشد، طرف راست (++calls > 0) هرگز اجرا نمیشود؛ پس اثر جانبی آن (افزایش calls) هم رخ نمیدهد. به همین دلیل نوشتن عبارتهایی با اثر جانبی داخل شرطها عادت خوبی نیست.
اولویت عملگرها¶
وقتی چند عملگر در یک عبارت هستند، ترتیب ارزیابی از بالا به پایین جدول زیر است:
| اولویت | عملگر |
|---|---|
| ۱ (بالاترین) | ! |
| ۲ | < , <= , > , >= |
| ۳ | == , != |
| ۴ | && |
| ۵ (پایینترین) | || |
یعنی && قویتر از || است. این دقیقاً جایی است که خوانندهی کد را (و گاهی نویسندهی آن را) به اشتباه میاندازد:
%%writefile src/p04_c08_04_precedence.c
#include <stdio.h>
int main(void)
{
printf("1 || 0 && 0 -> %d\n", 1 || 0 && 0);
printf("(1 || 0) && 0 -> %d\n", (1 || 0) && 0);
return 0;
}
Writing src/p04_c08_04_precedence.c
!gcc -Wall -o bin/p04_c08_04_precedence src/p04_c08_04_precedence.c && ./bin/p04_c08_04_precedencesrc/p04_c08_04_precedence.c: In function ‘main’:
src/p04_c08_04_precedence.c:5:41: warning: suggest parentheses around ‘&&’ within ‘||’ []8;;https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wparentheses-Wparentheses]8;;]
5 | printf("1 || 0 && 0 -> %d\n", 1 || 0 && 0);
| ^~
1 || 0 && 0 -> 1
(1 || 0) && 0 -> 0
عبارت اول بهصورت 1 || (0 && 0) ارزیابی میشود (چون && اول انجام میشود) و نتیجهاش 1 است؛ در حالی که با پرانتز، نتیجه 0 میشود. توجه کنید کامپایلر با -Wall هم دقیقاً همین ابهام را هشدار داده است. قاعدهی عملی: هر جا ترکیب && و || را کنار هم مینویسید، پرانتز بگذارید؛ حتی اگر لازم نباشد.
قوانین دمورگان (De Morgan's Laws)¶
برای ساختن «نقیض» یک شرط (مثلاً وقتی میخواهیم حالتهای نامعتبر را از روی حالتهای معتبر بسازیم) از دو قانون زیر استفاده میکنیم:
| عبارت اصلی | عبارت معادل |
|---|---|
!(A && B) | !A || !B |
!(A || B) | !A && !B |
مثال: نمرهی معتبر یعنی score >= 0 && score <= 20. پس نمرهی نامعتبر یعنی !(score >= 0 && score <= 20) که طبق دمورگان برابر است با score < 0 || score > 20. به عملگر دقت کنید: && تبدیل به || شد و هر مقایسه برعکس شد.
تمرین درون فصل ۸.۲¶
نوع تمرین: Predict the Output
int x = 5;
printf("%d %d\n", x > 3 && x < 10, x < 3 || x > 10);بدون اجرای کد، خروجی را پیشبینی کنید. سپس با استفاده از قوانین دمورگان، عبارت !(x > 3 && x < 10) را بدون استفاده از ! بازنویسی کنید.
8.3 دستور if¶
ایده الگوریتم¶
سادهترین شکل تصمیمگیری: «اگر شرط برقرار بود، یک کار اضافه انجام بده؛ در غیر این صورت، همین مرحله را رد کن و ادامه بده.» در این حالت دو مسیر داریم، اما یکی از آنها «هیچ کاری نکردن» است.
Pseudocode¶
if condition:
statements // only when the condition is true
next statement // always runsFlowchart¶
Example A - Simple: پاداش برای نمرهی بالا¶
%%writefile src/p04_c08_05_if_simple.c
#include <stdio.h>
int main(void)
{
int score;
if (scanf("%d", &score) != 1) {
return 1;
}
printf("Score: %d\n", score);
if (score >= 18) {
printf("Excellent! Bonus point awarded.\n");
}
printf("Report finished.\n");
return 0;
}
Writing src/p04_c08_05_if_simple.c
%%bash
gcc -Wall -o bin/p04_c08_05_if_simple src/p04_c08_05_if_simple.c || exit 1
echo "19" | ./bin/p04_c08_05_if_simple
echo "12" | ./bin/p04_c08_05_if_simpleScore: 19
Excellent! Bonus point awarded.
Report finished.
Score: 12
Report finished.
برنامه دو بار با ورودیهای 19 و 12 اجرا شده است. در اجرای دوم، پیام پاداش چاپ نشده، اما خط آخر (Report finished.) در هر دو اجرا چاپ شده. چرا؟
کدام خطها «زیر کنترل» if هستند؟
فقط دستورهای داخل آکولاد ({ ... }) بعد از شرط. خط printf("Report finished.\n") بیرون از آکولاد است و به شرط وابسته نیست؛ یعنی بعد از پایان if ــ چه بدنه اجرا شده باشد، چه نه ــ برنامه از همین خط ادامه مییابد. این همان گرهی «دو مسیر که دوباره به هم میرسند» در Flowchart است.
چرا برای بدنهی if همیشه آکولاد مینویسیم، حتی برای یک دستور؟
چون اگر آکولاد نباشد، فقط اولین دستور بعد از شرط به آن وابسته است و هر خط بعدی (حتی اگر با تورفتگی نوشته شده باشد) مستقل میشود. این یکی از رایجترین منابع باگ است (در «خطاهای رایج» همین فصل میبینیم).
Example B - Real: اعتبارسنجی بازهی نمره¶
در برنامهی واقعی، اولین کاری که با ورودی کاربر باید کرد این است که مطمئن شویم معتبر است. نمره باید بین ۰ تا ۲۰ باشد:
%%writefile src/p04_c08_06_if_validate.c
#include <stdio.h>
int main(void)
{
int score;
if (scanf("%d", &score) != 1) {
return 1;
}
if (score < 0 || score > 20) {
printf("%d: invalid score (must be between 0 and 20)\n", score);
return 1;
}
printf("%d: valid score\n", score);
return 0;
}
Writing src/p04_c08_06_if_validate.c
%%bash
gcc -Wall -o bin/p04_c08_06_if_validate src/p04_c08_06_if_validate.c || exit 1
echo "15" | ./bin/p04_c08_06_if_validate
echo "20" | ./bin/p04_c08_06_if_validate
echo "0" | ./bin/p04_c08_06_if_validate
echo "21" | ./bin/p04_c08_06_if_validate
echo "-1" | ./bin/p04_c08_06_if_validate || true15: valid score
20: valid score
0: valid score
21: invalid score (must be between 0 and 20)
-1: invalid score (must be between 0 and 20)
چرا شرط نامعتبر را با || نوشتهایم، نه با &&؟
نمره وقتی نامعتبر است که از یک طرف بازه بیرون باشد: یا خیلی کوچک (< 0) یا خیلی بزرگ (> 20). عبارت score < 0 && score > 20 هیچوقت درست نمیشود، چون هیچ عددی همزمان هم از ۰ کوچکتر است و هم از ۲۰ بزرگتر. این همان قانون دمورگان است که در ۸.۲ دیدیم.
چرا بعد از چاپ پیام خطا return 1 نوشتهایم؟
return در main برنامه را فوراً تمام میکند. مقدار غیرصفر طبق قرارداد یعنی «برنامه با خطا تمام شد». این الگو (Guard Clause: «اگر ورودی بد است، همینجا کار را تمام کن») باعث میشود بقیهی برنامه فقط با دادهی معتبر سروکار داشته باشد؛ در ۸.۶ بیشتر از آن استفاده میکنیم.
Example C - Tricky: دستور بعد از شرط، بدون آکولاد¶
if (score < 10)
printf("Fail\n");
printf("Please retake the course\n");برای score = 15، آیا پیام «Please retake the course» چاپ میشود؟ بله. تورفتگی فقط برای انسان است و کامپایلر آن را نمیبیند. کامپایلر کد بالا را اینطور میخواند:
if (score < 10) {
printf("Fail\n");
}
printf("Please retake the course\n"); // همیشه اجرا میشودبرای همین است که هیچوقت نباید به تورفتگی برای تشخیص حدود if اعتماد کرد؛ آکولاد تنها منبع حقیقت است.
تمرین درون فصل ۸.۳¶
نوع تمرین: Predict the Output
int x = 4;
if (x > 5)
printf("A\n");
printf("B\n");خروجی چیست؟ دلیل خود را با استناد به قاعدهی «یک دستور بدون آکولاد» توضیح دهید.
تمرینهای پایانی زیربخش: if¶
★ سطح پایه
Small Implementation:
برنامهای بنویسید که یک عدد صحیح بخواند و فقط اگر عدد منفی بود، پیامNegative numberرا چاپ کند. در هر حالت، در انتهاDoneچاپ شود.Predict the Output:
int a = 10, b = 20;
if (a > b) {
printf("X\n");
}
printf("Y\n");خروجی را پیشبینی کنید و بگویید کدام خطها به شرط وابستهاند.
★★ سطح متوسط
Small Implementation:
برنامهای بنویسید که سه عدد صحیح بگیرد و فقط اگر هر سه عدد مثبت بودند، مجموع آنها را چاپ کند.Find the Bug:
if (score >= 0 && score <= 20);
{
printf("Valid\n");
}این کد برای هر ورودی «Valid» چاپ میکند. علت را پیدا کنید و اصلاح کنید.
★★★ سطح چالشی
Design:
شرط «عددxدر بازهی [۱۰, ۲۰] نیست» را یکبار با!و یکبار بدون!(با دمورگان) بنویسید و ثابت کنید (با جدول مقادیر آزمایشی) که معادلاند.Explain Why:
توضیح دهید چرا نوشتنif (x = 0)در C خطای کامپایل نمیدهد، اما تقریباً همیشه اشتباه است. این شرط برای چه مقادیری ازxبدنه را اجرا میکند؟
8.4 دستور if-else¶
ایده الگوریتم¶
در بسیاری از مسئلهها، هر دو حالت «شرط درست» و «شرط نادرست» کاری برای انجام دارند. if-else یک تقسیم دوشاخه است: دقیقاً یکی از دو مسیر اجرا میشود، نه هر دو و نه هیچکدام. به همین دلیل مشکل برنامهی sequential_naive (چاپ همزمان «قبول» و «مردود») با آن حل میشود.
Pseudocode¶
if condition:
statements A // condition is true
else:
statements B // condition is false
next statementFlowchart¶
Example A - Simple: زوج یا فرد¶
%%writefile src/p04_c08_07_even_odd.c
#include <stdio.h>
int main(void)
{
int n;
if (scanf("%d", &n) != 1) {
return 1;
}
if (n % 2 == 0) {
printf("%d is even\n", n);
} else {
printf("%d is odd\n", n);
}
return 0;
}
Writing src/p04_c08_07_even_odd.c
%%bash
gcc -Wall -o bin/p04_c08_07_even_odd src/p04_c08_07_even_odd.c || exit 1
echo "10" | ./bin/p04_c08_07_even_odd
echo "7" | ./bin/p04_c08_07_even_odd
echo "0" | ./bin/p04_c08_07_even_odd10 is even
7 is odd
0 is even
ایدهی الگوریتم: باقیماندهی تقسیم بر ۲ فقط دو مقدار ممکن دارد؛ پس مسئلهی «زوج یا فرد» دقیقاً با یک تصمیم دوشاخه حل میشود. به اینکه عدد 0 زوج حساب شده است دقت کنید: 0 % 2 برابر 0 است، پس الگوریتم بدون هیچ استثنای جداگانه درست کار میکند.
Example B - Real: سال کبیسه (Leap Year)¶
این مسئله یک نمونهی کلاسیک از قاعدهی چندلایه است. قاعدهی تقویم میلادی این است: سالی کبیسه است که بر ۴ بخشپذیر باشد، مگر اینکه بر ۱۰۰ بخشپذیر باشد، مگر اینکه بر ۴۰۰ هم بخشپذیر باشد. دو راه برای تبدیل این قاعده به شرط وجود دارد: یک عبارت منطقی واحد، یا یک زنجیرهی تصمیم از خاصترین استثنا به عمومیترین قاعده (۴۰۰ ← ۱۰۰ ← ۴).
Pseudocode¶
function IS_LEAP(year):
if year divisible by 400: return TRUE
else if year divisible by 100: return FALSE
else if year divisible by 4: return TRUE
else: return FALSE%%writefile src/p04_c08_08_leap_year.c
#include <stdio.h>
int main(void)
{
int year;
if (scanf("%d", &year) != 1) {
return 1;
}
/* Formulation 1: one logical expression */
int leap_expr = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
/* Formulation 2: from the most specific exception to the general rule */
int leap_chain;
if (year % 400 == 0) {
leap_chain = 1;
} else if (year % 100 == 0) {
leap_chain = 0;
} else {
leap_chain = (year % 4 == 0);
}
if (leap_expr) {
printf("%d: leap year\n", year);
} else {
printf("%d: common year\n", year);
}
if (leap_expr != leap_chain) {
printf("MISMATCH between the two formulations!\n");
}
return 0;
}
Writing src/p04_c08_08_leap_year.c
%%bash
gcc -Wall -o bin/p04_c08_08_leap_year src/p04_c08_08_leap_year.c || exit 1
echo "1900" | ./bin/p04_c08_08_leap_year
echo "2000" | ./bin/p04_c08_08_leap_year
echo "2024" | ./bin/p04_c08_08_leap_year
echo "2023" | ./bin/p04_c08_08_leap_year
echo "2100" | ./bin/p04_c08_08_leap_year
echo "1600" | ./bin/p04_c08_08_leap_year1900: common year
2000: leap year
2024: leap year
2023: common year
2100: common year
1600: leap year
چرا این شش سال برای تست انتخاب شدهاند؟
هر سال یک مسیر متفاوت از الگوریتم را آزمایش میکند: سالهای 2000 و 1600 مسیر «بخشپذیر بر ۴۰۰» را؛ 1900 و 2100 مسیر «بخشپذیر بر ۱۰۰ ولی نه ۴۰۰» را؛ 2024 مسیر «بخشپذیر بر ۴ ولی نه ۱۰۰» را؛ و 2023 مسیر «هیچکدام» را. این ایده را پوشش مسیرها (Path Coverage) مینامند: برای هر مسیر ممکن، حداقل یک ورودی آزمایشی. اگر فقط سالهای «عادی» مثل ۲۰۲۴ و ۲۰۲۳ را تست میکردیم، یک پیادهسازی سادهی year % 4 == 0 هم قبول میشد، در حالی که برای ۱۹۰۰ غلط است.
چرا در فرمول دوم ترتیب ۴۰۰ ← ۱۰۰ ← ۴ مهم است؟
چون اگر ابتدا بپرسیم «آیا بر ۴ بخشپذیر است؟»، سال ۱۹۰۰ همانجا کبیسه تلقی میشود و استثنای ۱۰۰ هرگز فرصت اصلاح این تصمیم را پیدا نمیکند. در یک زنجیرهی تصمیم، هر شرط فقط وقتی بررسی میشود که همهی شرطهای قبلی نادرست بودهاند؛ پس شرطها باید از خاص به عام مرتب شوند (در ۸.۵ این اصل را کامل بررسی میکنیم).
چرا برنامه دو فرمول را با هم مقایسه میکند؟
وقتی برای یک مسئله دو راه حل مستقل داریم، مقایسهی نتیجهی آنها یک تکنیک ارزان برای کشف باگ است. اگر هیچوقت MISMATCH چاپ نشود، احتمال اشتباه هر دو همزمان کم میشود.
Trace: دنبال کردن مسیر تصمیم برای سال ۱۹۰۰ و ۲۰۲۴¶
code_leap = ["if (year % 400 == 0)",
" leap = 1;",
"else if (year % 100 == 0)",
" leap = 0;",
"else",
" leap = (year % 4 == 0);"]
LG_PATH = [["cmp", "شرط در حال بررسی"], ["dim", "نادرست بود؛ رد شد"], ["ok", "شرطِ برنده"], ["i", "هنوز بررسی نشده"]]
def leap_scene(year):
r = Rec(f"Leap year: decision path for year = {year}", code_leap,
["year % 400", "year % 100", "else"], LG_PATH, labels=["شرط ۱", "شرط ۲", "شرط ۳"])
r.var(year=year, leap="—")
r.at(1, f"شروع: {_c('year')} برابر {_c(year)} است و {_c('leap')} هنوز مقدار ندارد. شرطها از بالا به پایین و به ترتیب بررسی میشوند.")
conds = [(400, "leap = 1"), (100, "leap = 0")]
for k, (d, act) in enumerate(conds):
if k: r.mark(k - 1, "dim")
r.mark(k, "cmp")
rem = year % d
r.at(1 if k == 0 else 3, f"باقیماندهی {_c(f'{year} % {d}')} برابر {_c(rem)} است ← شرط " + ("<b>درست</b> است." if rem == 0 else "نادرست است؛ سراغ شرط بعدی میرویم."))
if rem == 0:
r.mark(k, "ok")
val = 1 if d == 400 else 0
r.var(leap=val)
r.at(2 if k == 0 else 4, f"این شاخه برنده شد: {_c(act)}. همهی شاخههای بعدی بدون بررسی رد میشوند.")
r.mark({j: "dim" for j in range(k + 1, 3)})
r.at([1, 6], f"پایان تصمیم: {_c('leap')} = {_c(val)}.")
return r
r.mark(1, "dim")
r.mark(2, "ok")
r.at(5, "هیچکدام از دو شرط بالا برقرار نبود، پس شاخهی else اجرا میشود.")
val = int(year % 4 == 0)
r.var(leap=val)
r.at(6, f"{_c('leap = (year % 4 == 0)')} ← باقیماندهی {_c(f'{year} % 4')} برابر {_c(year % 4)} است، پس {_c('leap')} = {_c(val)}.")
return r
display(leap_scene(1900).show())
display(leap_scene(2024).show())
Example C - Tricky: باقیماندهی اعداد منفی¶
%%writefile src/p04_c08_09_even_odd_negative.c
#include <stdio.h>
int main(void)
{
int n = -7;
printf("n %% 2 = %d\n", n % 2);
if (n % 2 == 1) {
printf("version 1 (n %% 2 == 1): odd\n");
} else {
printf("version 1 (n %% 2 == 1): even <-- wrong!\n");
}
if (n % 2 != 0) {
printf("version 2 (n %% 2 != 0): odd\n");
} else {
printf("version 2 (n %% 2 != 0): even\n");
}
return 0;
}
Writing src/p04_c08_09_even_odd_negative.c
!gcc -Wall -o bin/p04_c08_09_even_odd_negative src/p04_c08_09_even_odd_negative.c && ./bin/p04_c08_09_even_odd_negativen % 2 = -1
version 1 (n % 2 == 1): even <-- wrong!
version 2 (n % 2 != 0): odd
در C (از استاندارد C99 به بعد) تقسیم صحیح به سمت صفر گرد میشود و علامت باقیمانده با علامت مقسوم یکی است؛ پس -7 % 2 برابر -1 است، نه 1. نسخهی اول فقط برای عددهای نامنفی درست بود. نسخهی دوم بهجای «آیا باقیمانده دقیقاً ۱ است؟» میپرسد «آیا باقیمانده صفر نیست؟» که برای همهی اعداد درست است. درس الگوریتمی: شرط را طوری بنویس که روی کل دامنهی ورودی درست باشد، نه فقط روی مثالهایی که امتحان کردهای.
تمرین درون فصل ۸.۴¶
نوع تمرین: Trace
الگوریتم سال کبیسه را برای year = 2100 و سپس year = 2000 روی کاغذ دنبال کنید. برای هرکدام بنویسید کدام شرطها به ترتیب بررسی میشوند و نتیجهی هرکدام (درست/نادرست) چیست و در نهایت کدام مسیر انتخاب میشود.
تمرینهای پایانی زیربخش: if-else¶
★ سطح پایه
Small Implementation:
برنامهای بنویسید که یک عدد بخواند و بگوید مثبت است یا «غیر مثبت» (صفر یا منفی).Predict the Output:
int n = 15;
if (n % 5 == 0) {
printf("A\n");
} else {
printf("B\n");
}
printf("C\n");★★ سطح متوسط
Small Implementation:
برنامهای بنویسید که سه عدد بخواند و با فقطif-elseو عملگرهای منطقی بگوید آیا هر سه برابرند یا نه.Find the Bug:
if (year % 4 == 0)
printf("Leap\n");
else
printf("Common\n");این کد برای کدام سالها (حداقل دو مثال بزنید) جواب غلط میدهد؟ چه شرطهایی باید اضافه شود؟
Trace:
برایyear = 1600وyear = 1700الگوریتم دو فرمول (عبارت واحد و زنجیره) را دنبال کنید و نشان دهید هر دو به یک نتیجه میرسند.
★★★ سطح چالشی
Edge Case Reasoning:
اگر در برنامهی زوج/فرد بهجایn % 2 != 0ازn % 2 == 1استفاده شود، برای کدام ورودیها پاسخ غلط میدهد؟ یک ورودی آزمایشی بنویسید که این باگ را فاش کند.Design:
مسئلهی «بخشپذیری بر ۳ و ۵» (همهی اعدادی که هم بر ۳ و هم بر ۵ بخشپذیرند) را با یک شرط واحد و سپس با دوifتو در تو بنویسید. کدام خواناتر است؟ چرا؟
8.5 زنجیرهی else if (انتخاب چندمسیره)¶
ایده الگوریتم¶
گاهی بیش از دو مسیر داریم. مثلاً در برنامهی ارزیابی نمرات، نمره باید به یکی از چند دسته تبدیل شود: «عالی» (۱۷ تا ۲۰)، «خوب» (۱۴ تا ۱۶)، «قبول» (۱۰ تا ۱۳) و «مردود» (زیر ۱۰). راهحل، یک زنجیرهی شرطها است که از بالا به پایین یکییکی بررسی میشوند و اولین شرطی که درست باشد برنده است؛ بقیهی زنجیره اصلاً بررسی نمیشود.
این جملهی کوتاه («اولین شرط درست برنده است») مهمترین نکتهی این بخش است و تمام قاعدههای بعدی از آن نتیجه میشوند.
Pseudocode¶
if condition 1: statements 1
else if condition 2: statements 2
else if condition 3: statements 3
...
else: statements N // optional: if nothing above matchedFlowchart¶
Example A - Simple: درجهبندی نمره¶
%%writefile src/p04_c08_10_grade_ladder.c
#include <stdio.h>
int main(void)
{
int score;
if (scanf("%d", &score) != 1) {
return 1;
}
if (score < 0 || score > 20) {
printf("%d: invalid score\n", score);
} else if (score >= 17) {
printf("%d: Excellent\n", score);
} else if (score >= 14) {
printf("%d: Good\n", score);
} else if (score >= 10) {
printf("%d: Pass\n", score);
} else {
printf("%d: Fail\n", score);
}
return 0;
}
Writing src/p04_c08_10_grade_ladder.c
%%bash
gcc -Wall -o bin/p04_c08_10_grade_ladder src/p04_c08_10_grade_ladder.c || exit 1
echo "20" | ./bin/p04_c08_10_grade_ladder
echo "17" | ./bin/p04_c08_10_grade_ladder
echo "16" | ./bin/p04_c08_10_grade_ladder
echo "14" | ./bin/p04_c08_10_grade_ladder
echo "13" | ./bin/p04_c08_10_grade_ladder
echo "10" | ./bin/p04_c08_10_grade_ladder
echo "9" | ./bin/p04_c08_10_grade_ladder
echo "0" | ./bin/p04_c08_10_grade_ladder
echo "21" | ./bin/p04_c08_10_grade_ladder
echo "-5" | ./bin/p04_c08_10_grade_ladder20: Excellent
17: Excellent
16: Good
14: Good
13: Pass
10: Pass
9: Fail
0: Fail
21: invalid score
-5: invalid score
چرا در شرط سوم فقط score >= 14 نوشتهایم و score < 17 را ننوشتهایم؟
چون برای رسیدن به این شرط، شرط قبلی (score >= 17) باید نادرست شده باشد؛ یعنی در این نقطه از برنامه، ما از قبل «میدانیم» که score < 17 است. هر شرط در زنجیره بهطور ضمنی نقیضِ همهی شرطهای بالایی را هم در خود دارد. این ویژگی شرطها را کوتاه و خوانا میکند، اما همزمان یعنی ترتیب شرطها بخشی از منطق برنامه است.
چرا شرط اعتبارسنجی در ابتدای زنجیره آمده است؟
چون اگر نمرهی 25 را بدون بررسی اعتبار وارد زنجیره میکردیم، به شرط score >= 17 میرسید و «Excellent» چاپ میشد. حالتهای خاص و استثنایی (ورودی نامعتبر) باید پیش از حالتهای عمومی بررسی شوند.
چرا شاخهی نهایی else شرط ندارد؟
else یعنی «هر حالتی که هیچکدام از شرطهای بالا پوشش ندادهاند». چون در اینجا آخرین دسته (مردود) دقیقاً «بقیهی حالتها» است، نیازی به نوشتن score >= 0 && score < 10 نیست.
Trace: مسیر تصمیم برای نمرهی ۱۵¶
code_ladder = ["if (score < 0 || score > 20)",
" printf(\"invalid\");",
"else if (score >= 17)",
" printf(\"Excellent\");",
"else if (score >= 14)",
" printf(\"Good\");",
"else if (score >= 10)",
" printf(\"Pass\");",
"else",
" printf(\"Fail\");"]
LG_LAD = [["cmp", "شرط در حال بررسی"], ["dim", "نادرست بود؛ رد شد"], ["ok", "شرطِ برنده"], ["i", "هنوز بررسی نشده"]]
def ladder_scene(score):
r = Rec(f"else-if ladder: score = {score}", code_ladder,
["invalid", "≥ 17", "≥ 14", "≥ 10", "else"], LG_LAD,
labels=["شاخه ۱", "شاخه ۲", "شاخه ۳", "شاخه ۴", "شاخه ۵"], interval=1300)
r.var(score=score)
r.at(1, f"نمرهی {_c(score)} وارد زنجیره میشود. «اولین شرطِ درست برنده است» و بقیهی زنجیره اصلاً بررسی نمیشود.")
tests = [(0, 1, f"score < 0 || score > 20", score < 0 or score > 20, "invalid"),
(1, 3, "score >= 17", score >= 17, "Excellent"),
(2, 5, "score >= 14", score >= 14, "Good"),
(3, 7, "score >= 10", score >= 10, "Pass")]
for k, ln, expr, res, word in tests:
if k: r.mark(k - 1, "dim")
r.mark(k, "cmp")
r.at(ln, f"{_c(expr)} با {_c(f'score = {score}')} ← " + ("<b>درست</b>؛ این شاخه برنده است." if res else "نادرست؛ به شرط بعدی میرویم."))
if res:
r.mark(k, "ok"); r.mark({j: "dim" for j in range(k + 1, 5)})
r.echo(word)
r.at(ln + 1, f"{_c(f'printf(\"{word}\")')} اجرا شد. باقی شاخهها (حتی اگر درست بودند) دیگر بررسی نمیشوند.")
return r
r.mark(3, "dim"); r.mark(4, "ok")
r.echo("Fail")
r.at(10, "هیچ شرطی برقرار نبود؛ شاخهی else (یعنی «بقیهی حالتها») اجرا میشود.")
return r
display(ladder_scene(15).show())
تست مرزی (Boundary Value Testing)¶
«چه ورودیهایی را تست کنیم؟» سؤالی است که یک برنامهنویس حرفهای هر بار از خودش میپرسد. برای زنجیرههای شرطی، پاسخ استاندارد این است: روی مرز هر شرط، یک مقدار درست قبل از مرز، خود مرز، و یک مقدار درست بعد از آن را امتحان کنید؛ چون اکثر باگهای شرطی دقیقاً همانجا (اشتباه > بهجای >=) پنهان میشوند.
| مرز | مقادیر آزمایشی | خروجی مورد انتظار |
|---|---|---|
| مرز اعتبار پایین | -1 , 0 | invalid , Fail |
| مرز Fail/Pass | 9 , 10 | Fail , Pass |
| مرز Pass/Good | 13 , 14 | Pass , Good |
| مرز Good/Excellent | 16 , 17 | Good , Excellent |
| مرز اعتبار بالا | 20 , 21 | Excellent , invalid |
اگر دوباره به خروجی برنامهی grade_ladder نگاه کنید، دقیقاً همین مقادیر آزمایش شدهاند و همه با جدول بالا میخوانند. فرض کنید بهجای score >= 14 اشتباهاً score > 14 نوشته بودیم؛ فقط ورودی 14 (که روی مرز است) این باگ را نشان میداد، در حالی که تست با 16 یا 12 هرگز آن را نمیدید.
Example B - Real: دستهبندی مثلث¶
مسئله: سه عدد صحیح بهعنوان طول ضلعها داده شده است. برنامه باید بگوید این سه عدد (۱) اصلاً ضلع معتبر هستند؟ (۲) تشکیل مثلث میدهند؟ (۳) مثلث متساویالاضلاع، متساویالساقین یا مختلفالاضلاع است؟ (۴) قائمالزاویه هست یا نه؟
ایدهی الگوریتم: سؤالها را به ترتیب وابستگی مرتب میکنیم. تا وقتی ضلعها مثبت نباشند، بحث نامساوی مثلث بیمعناست؛ تا وقتی نامساوی مثلث برقرار نباشد، بحث نوع مثلث بیمعناست. پس: اعتبار ← نامساوی مثلث ← نوع.
Pseudocode¶
read a, b, c
if a <= 0 or b <= 0 or c <= 0: print "invalid"
else if a + b <= c or a + c <= b or b + c <= a:
print "not a triangle"
else:
if a = b = c: type ← "equilateral"
else if two sides are equal: type ← "isosceles"
else: type ← "scalene"
right ← (a² + b² = c²) or (a² + c² = b²) or (b² + c² = a²)
print type, and "right-angled" if right%%writefile src/p04_c08_11_triangle.c
#include <stdio.h>
int main(void)
{
int a, b, c;
if (scanf("%d %d %d", &a, &b, &c) != 3) {
return 1;
}
if (a <= 0 || b <= 0 || c <= 0) {
printf("%d %d %d: invalid (sides must be positive)\n", a, b, c);
} else if (a + b <= c || a + c <= b || b + c <= a) {
printf("%d %d %d: not a triangle\n", a, b, c);
} else {
int right = (a * a + b * b == c * c) ||
(a * a + c * c == b * b) ||
(b * b + c * c == a * a);
printf("%d %d %d: ", a, b, c);
if (a == b && b == c) {
printf("equilateral");
} else if (a == b || b == c || a == c) {
printf("isosceles");
} else {
printf("scalene");
}
if (right) {
printf(", right-angled");
}
printf("\n");
}
return 0;
}
Writing src/p04_c08_11_triangle.c
%%bash
gcc -Wall -o bin/p04_c08_11_triangle src/p04_c08_11_triangle.c || exit 1
echo "3 4 5" | ./bin/p04_c08_11_triangle
echo "5 5 5" | ./bin/p04_c08_11_triangle
echo "5 5 8" | ./bin/p04_c08_11_triangle
echo "6 7 9" | ./bin/p04_c08_11_triangle
echo "1 2 3" | ./bin/p04_c08_11_triangle
echo "0 4 4" | ./bin/p04_c08_11_triangle
echo "5 12 13" | ./bin/p04_c08_11_triangle3 4 5: scalene, right-angled
5 5 5: equilateral
5 5 8: isosceles
6 7 9: scalene
1 2 3: not a triangle
0 4 4: invalid (sides must be positive)
5 12 13: scalene, right-angled
چرا شرط نامساوی مثلث با <= نوشته شده، نه <؟
در یک مثلث واقعی مجموع هر دو ضلع اکیداً از ضلع سوم بزرگتر است. حالت 1 2 3 (که 1 + 2 == 3) یک «مثلث تباهیده» است: سه نقطه روی یک خط. اگر < مینوشتیم، این ورودی بهاشتباه مثلث معتبر شمرده میشد. همین ورودی یک تست مرزی عالی است.
چرا ساختار این برنامه ترکیبی از زنجیرهی else if و یک if تو در تو است؟
بخش اول (اعتبار ← مثلث بودن) یک انتخاب چندمسیرهی کلاسیک است. اما وقتی مطمئن شدیم مثلث معتبر است، دو سؤال مستقل از هم داریم: «نوع از نظر ضلعها» و «قائمالزاویه بودن». این دو را نمیتوان در یک زنجیرهی واحد گنجاند، چون در یک زنجیره فقط یک مسیر اجرا میشود، در حالی که ما باید هر دو پاسخ را بدهیم. ترکیب right (یک متغیر 0/1) با چاپ شرطی انتهای خط، راه سادهی ما برای ترکیب پاسخ هر دو سؤال است.
Example C - Tricky: ترتیب اشتباه شرطها¶
فرض کنید یک برنامهنویس همان زنجیرهی درجهبندی را از پایین به بالا نوشته باشد:
%%writefile src/p04_c08_12_ladder_wrong_order.c
#include <stdio.h>
int main(void)
{
int score;
if (scanf("%d", &score) != 1) {
return 1;
}
/* BUG: conditions are in the wrong order */
if (score >= 10) {
printf("%d: Pass\n", score);
} else if (score >= 14) {
printf("%d: Good\n", score);
} else if (score >= 17) {
printf("%d: Excellent\n", score);
} else {
printf("%d: Fail\n", score);
}
return 0;
}
Writing src/p04_c08_12_ladder_wrong_order.c
%%bash
gcc -Wall -o bin/p04_c08_12_ladder_wrong_order src/p04_c08_12_ladder_wrong_order.c || exit 1
echo "18" | ./bin/p04_c08_12_ladder_wrong_order
echo "15" | ./bin/p04_c08_12_ladder_wrong_order
echo "12" | ./bin/p04_c08_12_ladder_wrong_order
echo "5" | ./bin/p04_c08_12_ladder_wrong_order18: Pass
15: Pass
12: Pass
5: Fail
کد بدون هیچ خطا یا هشداری کامپایل میشود و حتی برای نمرههای پایین درست کار میکند؛ اما برای 18 و 15 جواب غلط میدهد. چرا؟ چون شرط score >= 10 برای هر نمرهی قبولی درست است و طبق قانون «اولین شرط درست برنده است»، دو شاخهی بعدی هرگز اجرا نمیشوند (به آنها کد غیرقابلدسترس یا Unreachable Code میگوییم).
قاعدهی طراحی: در یک زنجیرهی else if که روی بازهها کار میکند، شرطها را از محدودترین (سختگیرانهترین) به عمومیترین بنویسید؛ یا برعکس، از عمومیترین به محدودترین ولی با مقایسهی < (مثلاً score < 10، سپس score < 14، ...). هر دو درستاند؛ مهم این است که مرتب باشند.
هزینهی یک زنجیرهی else if¶
در بدترین حالت (مقداری که با هیچ شرطی تطابق ندارد یا فقط با آخرین شرط تطابق دارد)، یک زنجیرهی k شرطی باید همهی k شرط را ارزیابی کند؛ یعنی هزینهی آن متناسب با k است. این عدد معمولاً کوچک است و تأثیری ندارد؛ اما همین نکته توجیه میکند چرا برای زنجیرههای بزرگ و پرتکرار، شرطهایی را که محتملتر هستند بالاتر میگذارند (به شرطی که منطق برنامه را به هم نریزد).
تمرین درون فصل ۸.۵¶
نوع تمرین: Trace
برای score = 14 و سپس score = 13 زنجیرهی درجهبندی را دنبال کنید. در هر مورد بنویسید کدام شرطها به ترتیب بررسی میشوند و چرا نتیجهی این دو ورودی که فقط یک واحد اختلاف دارند متفاوت است.
تمرین درون فصل ۸.۶ : چرا ترتیب مهم است؟¶
نوع تمرین: Explain Why
در برنامهی ladder_wrong_order (ترتیب اشتباه)، برای چه نمرههایی خروجی درست است و برای چه نمرههایی غلط؟ آیا میتوانید بدون تغییر ترتیب شرطها، فقط با تغییر خود شرطها (بدون جابهجایی) آن را درست کنید؟ یک راه پیشنهاد دهید و مقایسهاش با راهحل «اصلاح ترتیب» را بنویسید.
تمرینهای پایانی زیربخش: else if¶
★ سطح پایه
Trace:
برای ورودی3 4 5در برنامهی دستهبندی مثلث، شرطهایی که به ترتیب بررسی میشوند و مقدارrightرا بنویسید.Predict the Output:
int x = 7;
if (x > 10) {
printf("A\n");
} else if (x > 5) {
printf("B\n");
} else if (x > 0) {
printf("C\n");
}★★ سطح متوسط
Small Implementation:
برنامهای بنویسید که دمای هوا (عدد صحیح) را بگیرد و آن را به یکی از دستههای «یخبندان» (زیر ۰)، «سرد» (۰ تا ۱۴)، «معتدل» (۱۵ تا ۲۵) و «گرم» (بالای ۲۵) تبدیل کند.Find the Bug:
if (age >= 18) {
printf("Adult\n");
} else if (age >= 13) {
printf("Teen\n");
} else if (age >= 0 && age < 13) {
printf("Child\n");
}اگر age = -4 باشد چه اتفاقی میافتد؟ چه چیزی در طراحی این زنجیره از نظر مدیریت ورودی نامعتبر کم است؟
Edge Case Implementation:
برای برنامهی دستهبندی مثلث، یک جدول از حداقل هشت ورودی آزمایشی بنویسید که همهی مسیرهای برنامه (invalid، not a triangle، سه نوع ضلعی، قائمالزاویه و غیرقائم) را پوشش دهد.
★★★ سطح چالشی
Design:
مالیاتها معمولاً پلهای محاسبه میشوند: تا ۱۰۰۰ واحد، معاف؛ از ۱۰۰۰ تا ۵۰۰۰ واحد، ۱۰٪ مقدار اضافهبر ۱۰۰۰؛ بالای ۵۰۰۰ واحد، ۴۰۰ واحد (مالیات کامل پلهی دوم) بهاضافهی ۲۰٪ مقدار اضافهبر ۵۰۰۰. با یک زنجیرهیelse ifمالیات را حساب کنید و مرزهای ۱۰۰۰ و ۵۰۰۰ را تست کنید.Modify the Algorithm:
برنامهی دستهبندی مثلث را طوری تغییر دهید که علاوه بر نوع ضلعها، نوع زاویهها را هم (حاده، قائمه، منفرجه) تشخیص دهد. (راهنمایی: فقط بزرگترین ضلع مهم است؛ چگونه آن را بدون آرایه پیدا میکنید؟)
8.6 شرطهای تو در تو (Nested Conditions)¶
ایده الگوریتم¶
یک if میتواند داخل بدنهی if یا else دیگری قرار بگیرد. این کار زمانی طبیعی است که یک تصمیم فقط وقتی معنا دارد که تصمیم قبلی به نتیجهی مشخصی رسیده باشد. مثال: برداشت از خودپرداز. پرسیدن «آیا مبلغ از موجودی کمتر است؟» وقتی مبلغ منفی باشد بیمعنی است؛ پس باید ابتدا اعتبار مبلغ بررسی شود.
قواعد برداشت: مبلغ مثبت باشد؛ مضرب ۱۰ باشد؛ از موجودی (اینجا ۱۰۰۰) بیشتر نباشد؛ از سقف برداشت روزانه (اینجا ۵۰۰) بیشتر نباشد.
Example A - Simple: نسخهی تو در تو (Nested)¶
%%writefile src/p04_c08_13_atm_nested.c
#include <stdio.h>
int main(void)
{
int balance = 1000, limit = 500, amount;
if (scanf("%d", &amount) == 1) {
if (amount > 0) {
if (amount % 10 == 0) {
if (amount <= balance) {
if (amount <= limit) {
balance -= amount;
printf("OK: withdrew %d, balance = %d\n", amount, balance);
} else {
printf("Denied: above the daily limit\n");
}
} else {
printf("Denied: insufficient balance\n");
}
} else {
printf("Denied: amount must be a multiple of 10\n");
}
} else {
printf("Denied: amount must be positive\n");
}
}
return 0;
}
Writing src/p04_c08_13_atm_nested.c
%%bash
gcc -Wall -o bin/p04_c08_13_atm_nested src/p04_c08_13_atm_nested.c || exit 1
echo "200" | ./bin/p04_c08_13_atm_nested
echo "0" | ./bin/p04_c08_13_atm_nested
echo "25" | ./bin/p04_c08_13_atm_nested
echo "700" | ./bin/p04_c08_13_atm_nested
echo "1500" | ./bin/p04_c08_13_atm_nestedOK: withdrew 200, balance = 800
Denied: amount must be positive
Denied: amount must be a multiple of 10
Denied: above the daily limit
Denied: insufficient balance
برنامه درست کار میکند، اما دو مشکل دارد. اول: پیام خطای هر شرط از خود شرط دور افتاده است (پیام positive در انتهای برنامه است و شرطش در ابتدا). دوم: کد بهشکل هرم (Pyramid) به سمت راست رشد میکند و هرچه شرطها بیشتر شوند، خواندن آن سختتر میشود. با هر سطح تو در تو، ذهن خواننده باید یک شرط دیگر را بهخاطر بسپارد.
Example B - Real: نسخهی تخت (Flat) با Guard Clause¶
%%writefile src/p04_c08_14_atm_flat.c
#include <stdio.h>
int main(void)
{
int balance = 1000, limit = 500, amount;
if (scanf("%d", &amount) != 1) {
return 1;
}
if (amount <= 0) {
printf("Denied: amount must be positive\n");
} else if (amount % 10 != 0) {
printf("Denied: amount must be a multiple of 10\n");
} else if (amount > balance) {
printf("Denied: insufficient balance\n");
} else if (amount > limit) {
printf("Denied: above the daily limit\n");
} else {
balance -= amount;
printf("OK: withdrew %d, balance = %d\n", amount, balance);
}
return 0;
}
Writing src/p04_c08_14_atm_flat.c
%%bash
gcc -Wall -o bin/p04_c08_14_atm_flat src/p04_c08_14_atm_flat.c || exit 1
echo "200" | ./bin/p04_c08_14_atm_flat
echo "0" | ./bin/p04_c08_14_atm_flat
echo "25" | ./bin/p04_c08_14_atm_flat
echo "700" | ./bin/p04_c08_14_atm_flat
echo "1500" | ./bin/p04_c08_14_atm_flatOK: withdrew 200, balance = 800
Denied: amount must be positive
Denied: amount must be a multiple of 10
Denied: above the daily limit
Denied: insufficient balance
خروجی هر دو نسخه برای ورودیهای یکسان دقیقاً یکی است، اما ساختار دوم تخت و خواناتر است. ایدهی اصلی: بهجای «اگر مبلغ معتبر بود، ادامه بده»، مینویسیم «اگر مبلغ نامعتبر است، همینجا رد کن». هر شرط، یک حالت خطا را فوراً کنار پیام خودش مدیریت میکند و حالت موفق در انتها (در else) میماند. به این الگو Guard Clause یا «بررسی نگهبان» میگویند.
قاعدهی سرانگشتی: اگر عمق تو در تویی از سه سطح گذشت، احتمالاً زنجیرهی تخت یا ترکیب شرطها با && سادهتر است.
Example C - Tricky: Dangling Else¶
وقتی در یک if تو در تو آکولاد نمیگذاریم، پرسش «این else متعلق به کدام if است؟» پیش میآید. قاعدهی C: **هر else به نزدیکترین if بدون else متصل میشود**، صرفنظر از تورفتگی.
%%writefile src/p04_c08_15_dangling_else.c
#include <stdio.h>
int main(void)
{
int a = 1, b = 0;
/* looks like "else belongs to the outer if", but it does not */
if (a == 1)
if (b == 1)
printf("both are 1\n");
else
printf("else: runs when a == 1 and b != 1\n");
/* braces make the intention explicit */
if (a == 1) {
if (b == 1) {
printf("both are 1\n");
}
} else {
printf("a is not 1\n");
}
printf("done\n");
return 0;
}
Writing src/p04_c08_15_dangling_else.c
!gcc -Wall -o bin/p04_c08_15_dangling_else src/p04_c08_15_dangling_else.c && ./bin/p04_c08_15_dangling_elsesrc/p04_c08_15_dangling_else.c: In function ‘main’:
src/p04_c08_15_dangling_else.c:8:8: warning: suggest explicit braces to avoid ambiguous ‘else’ []8;;https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wdangling-else-Wdangling-else]8;;]
8 | if (a == 1)
| ^
else: runs when a == 1 and b != 1
done
خط اول خروجی نشان میدهد else به if (b == 1) چسبیده است، نه به if (a == 1)؛ در حالی که ظاهر کد (و نیت نویسنده) چیز دیگری بود. کامپایلر هم با یک هشدار دقیقاً همین ابهام را گزارش کرده است. با آکولاد، نیت برنامهنویس بدون ابهام بیان میشود و بلوک دوم هیچ چیزی چاپ نمیکند (چون a == 1 و b != 1 است و else بیرونی هم اجرا نمیشود).
تمرین درون فصل ۸.۷¶
نوع تمرین: Predict the Output
int a = 0, b = 5;
if (a == 0)
if (b > 10)
printf("X\n");
else
printf("Y\n");
printf("Z\n");خروجی را پیشبینی کنید و بگویید else به کدام if تعلق دارد.
تمرینهای پایانی زیربخش: شرطهای تو در تو¶
★ سطح پایه
Trace:
در برنامهی خودپرداز (نسخهی تخت)، برایamount = 700شرطهای بررسیشده و پیام نهایی را بنویسید.Predict the Output:
در همان برنامه، برایamount = 1000خروجی چیست؟ (توجه:limitبرابر ۵۰۰ است.)
★★ سطح متوسط
Refactoring:
کد زیر را بدون هیچifتو در تو و فقط با&&بازنویسی کنید:
if (age >= 18) {
if (has_id) {
printf("Entry allowed\n");
}
}Find the Bug:
نسخهی تخت خودپرداز را طوری تغییر دهید که ترتیب دو شرطamount > balanceوamount > limitعوض شود. آیا خروجی برای همهی ورودیها یکسان میماند؟ برای کدام ورودی تفاوت پیدا میشود؟
★★★ سطح چالشی
Design:
یک برنامهی ورود (Login) ساده طراحی کنید که نامکاربریها و رمز را بهصورت عددی (مثلاًuser_idوpin) بگیرد، ابتدا اعتبارuser_idرا بسنجد (فقط ۱۰۰۱ و ۱۰۰۲ معتبرند)، سپس درستیpinرا بررسی کند و در هر مرحله پیام مخصوص خود را بدهد. هم نسخهی تو در تو و هم نسخهی تخت را بنویسید.Compare Approaches:
دو نسخهی «تو در تو» و «تخت» از یک مسئله را از نظر تعداد خطوط، خوانایی، و سهولت اضافهکردن یک قانون جدید (مثلاً «حداقل برداشت ۵۰») مقایسه کنید.
8.7 عملگر شرطی سهتایی ?:¶
ایده الگوریتم¶
گاهی تصمیم ما فقط برای انتخاب یک مقدار است، نه اجرای چند دستور. مثلاً «بزرگترین دو عدد» یا «قدر مطلق». در این حالت نوشتن یک if-else کامل فقط برای یک انتساب پرحرف است. C عملگر ?: را برای همین منظور دارد:
شرط ? مقدار_اگر_درست : مقدار_اگر_نادرستتفاوت بنیادین این عملگر با if: **if یک دستور (Statement) است و مقدار تولید نمیکند؛ اما ?: یک عبارت (Expression) است و خودش یک مقدار دارد.** به همین دلیل میتوان آن را در سمت راست یک انتساب، داخل printf و یا هر جای دیگری که مقدار لازم است قرار داد.
Pseudocode¶
result ← (condition) ? value_if_true : value_if_false
// equivalent
if condition:
result ← value_if_true
else:
result ← value_if_falseExample A - Simple: بیشینه، قدر مطلق و علامت¶
%%writefile src/p04_c08_16_ternary_basic.c
#include <stdio.h>
int main(void)
{
int a = 12, b = 20;
int max = (a > b) ? a : b;
int diff = (a > b) ? (a - b) : (b - a); /* |a - b| */
int sign = (a - b > 0) ? 1 : ((a - b < 0) ? -1 : 0); /* sign of a - b */
printf("max = %d\n", max);
printf("|a - b| = %d\n", diff);
printf("sign(a - b) = %d\n", sign);
printf("a is %s\n", (a % 2 == 0) ? "even" : "odd");
return 0;
}
Writing src/p04_c08_16_ternary_basic.c
!gcc -Wall -o bin/p04_c08_16_ternary_basic src/p04_c08_16_ternary_basic.c && ./bin/p04_c08_16_ternary_basicmax = 20
|a - b| = 8
sign(a - b) = -1
a is even
چرا خط آخر ?: را داخل printf گذاشتهایم؟
چون ?: مقدار تولید میکند (اینجا یک رشتهی متنی، "even" یا "odd") و printf به همان مقدار نیاز دارد. با if باید دو printf جداگانه مینوشتیم یا یک متغیر کمکی میساختیم.
چرا برای محاسبهی sign از ?: تو در تو استفاده شد و آیا کار درستی است؟
از نظر عملکرد درست است، اما خواندنش سختتر از معادل if-else if-else است. این نمونه نشان میدهد وقتی عملگر ?: را تو در تو میکنیم، به مرز کاهش خوانایی رسیدهایم.
Example B - Real: جمع بستن درست کلمهها (Plural)¶
%%writefile src/p04_c08_17_ternary_plural.c
#include <stdio.h>
int main(void)
{
int n;
for (n = 0; n <= 2; n++) {
printf("%d file%s selected\n", n, (n == 1) ? "" : "s");
}
return 0;
}
Writing src/p04_c08_17_ternary_plural.c
!gcc -Wall -o bin/p04_c08_17_ternary_plural src/p04_c08_17_ternary_plural.c && ./bin/p04_c08_17_ternary_plural0 files selected
1 file selected
2 files selected
(این برنامه یک حلقهی for دارد که در فصل بعد کامل میبینیم؛ فعلاً فقط بدانید n را یکییکی از ۰ تا ۲ میشمارد.) پیام «1 file» در مقابل «0 files» و «2 files»، یک نمونهی ایدهآل برای ?: است: فقط یک بخش کوچک از متن بر اساس یک شرط عوض میشود.
Example C - Tricky: اولویت پایین ?:¶
عملگر ?: از تقریباً همهی عملگرهای دیگر اولویت پایینتر دارد (فقط از انتساب بالاتر است). برای همین عبارتهای بدون پرانتز میتوانند نتیجهی غیرمنتظره بدهند:
int a = 5, b = 3;
int r = a > b ? 100 : 200 + 1; // r = 100 (چون شرط درست است)
a = 1;
r = a > b ? 100 : 200 + 1; // r = 201 (200 + 1 کامل در شاخهی نادرست است)در مثال دوم، + 1 جزو شاخهی نادرست است، نه یک جمع بعد از کل ?:. قاعدهی عملی: **هر عبارت ?: را کامل داخل پرانتز بنویسید**، مخصوصاً وقتی با عملگرهای دیگر ترکیب میشود.
همچنین اگر دو شاخه از نوعهای مختلف باشند (مثلاً int و double)، نتیجه به نوع «بزرگتر» (اینجا double) تبدیل میشود؛ پس باید printf را با مشخصکنندهی مناسب (%f) به کار برد.
کدام یک: if-else یا ?:؟¶
| معیار | if-else | ?: |
|---|---|---|
| نوع | دستور (مقدار ندارد) | عبارت (مقدار دارد) |
| اجرای چند دستور | بله | خیر (فقط یک عبارت در هر شاخه) |
| مناسب برای | تصمیمگیری دربارهی «چه کاری انجام شود» | تصمیمگیری دربارهی «چه مقداری استفاده شود» |
| تو در تو کردن | خوانا (با تورفتگی) | بهسرعت ناخوانا |
تمرین درون فصل ۸.۸¶
نوع تمرین: Complete the Code
عبارت زیر را با ?: کامل کنید تا abs_val قدر مطلق x شود:
int x = -9;
int abs_val = /* ??? */;سپس همین کار را با if-else بنویسید و بگویید در این مسئله کدام نسخه را ترجیح میدهید و چرا.
تمرینهای پایانی زیربخش: عملگر ?:¶
★ سطح پایه
Predict the Output:
int n = 3;
printf("%s\n", (n > 2) ? "big" : "small");Small Implementation:
با?:کوچکترین دو عددaوbرا به متغیرminبدهید.
★★ سطح متوسط
Find the Bug:
int a = 2, b = 7;
int r = a > b ? a : b + 10;مقدار r چیست؟ آیا نویسنده احتمالاً همین را میخواسته؟ با پرانتز، نیت «ده تا بیشتر از بزرگترین» را بنویسید.
Refactoring:
عبارت زیر را به یکif-else if-elseخوانا تبدیل کنید و بگویید کدام را ترجیح میدهید:
char c = (x > 0) ? '+' : (x < 0) ? '-' : '0';★★★ سطح چالشی
Design:
بزرگترین سه عدد را (الف) با?:تو در تو، (ب) با دوif، و (ج) با ترکیب&&پیدا کنید. کدام خواناتر است؟ هر سه را روی ورودیهایی که دو عدد برابرند (مثلاً5 5 3) تست کنید.Explain Why:
چرا نمیتوان از?:بهجایifبرای اجرای دو دستور مثلprintfو انتساب همزمان استفاده کرد؟ تفاوت «دستور» و «عبارت» را در یک مثال توضیح دهید.
8.8 switch-case¶
ایده الگوریتم¶
بعضی تصمیمها یک الگوی خاص دارند: یک مقدار را با چند مقدار ثابت و مشخص مقایسه میکنیم. مثلاً شمارهی روز هفته، نوع عملگر ماشینحساب، یا انتخاب کاربر در یک منو. اگر این کار را با else if بنویسیم، مجبوریم عبارت day == ... را بارها تکرار کنیم:
if (day == 1) { ... } else if (day == 2) { ... } else if (day == 3) { ... }دستور switch برای همین الگو ساخته شده است: مقدار عبارت را یکبار حساب میکند، سپس مستقیماً به برچسب case مطابق «میپرد» و از آنجا شروع به اجرا میکند. اگر هیچ caseی تطابق نداشت، به default میرود (اگر وجود داشته باشد).
Pseudocode¶
evaluate expression once
jump to the case whose constant equals the value
execute from there downwards, until "break" or the end of the switch
if no case matches: jump to default (if any)Flowchart¶
Example A - Simple: نام روز هفته¶
%%writefile src/p04_c08_18_switch_day.c
#include <stdio.h>
int main(void)
{
int day;
if (scanf("%d", &day) != 1) {
return 1;
}
switch (day) {
case 1:
printf("Saturday\n");
break;
case 2:
printf("Sunday\n");
break;
case 3:
printf("Monday\n");
break;
case 4:
printf("Tuesday\n");
break;
case 5:
printf("Wednesday\n");
break;
case 6:
printf("Thursday\n");
break;
case 7:
printf("Friday\n");
break;
default:
printf("Invalid day number\n");
}
return 0;
}
Writing src/p04_c08_18_switch_day.c
%%bash
gcc -Wall -o bin/p04_c08_18_switch_day src/p04_c08_18_switch_day.c || exit 1
echo "1" | ./bin/p04_c08_18_switch_day
echo "5" | ./bin/p04_c08_18_switch_day
echo "7" | ./bin/p04_c08_18_switch_day
echo "9" | ./bin/p04_c08_18_switch_daySaturday
Wednesday
Friday
Invalid day number
قوانین مهم switch¶
عبارت داخل
switch (...)باید از نوع صحیح باشد (int،char،enum). مقدار اعشاری (double) یا رشتهی متنی مجاز نیست.هر
caseباید یک مقدار ثابت صحیح باشد (عدد، کاراکتر مثل'a'، یا ثابت#define)؛ متغیر و بازه (مثلcase 1..5) مجاز نیست.مقدار هر
caseباید منحصربهفرد باشد.switchفقط تساوی را میسنجد؛ برای شرطهای «بزرگتر از» یا «بین دو مقدار» ساختار مناسب نیست.defaultاختیاری است ولی برای دریافت ورودیهای پیشبینینشده بسیار مفید است.
نقش break و پدیدهی Fall-Through¶
مهمترین نکتهی switch این است: **پرش به case مناسب فقط نقطهی شروع اجراست، نه نقطهی پایان.** پس از رسیدن به case، برنامه به اجرای دستورها ادامه میدهد و از case بعدی هم رد میشود، مگر اینکه به دستور break برسد. این رفتار را Fall-Through (سقوط به بلوک بعدی) مینامند. دستور break کنترل را از switch خارج میکند.
%%writefile src/p04_c08_19_switch_fallthrough.c
#include <stdio.h>
int main(void)
{
int level = 2;
printf("--- without break ---\n");
switch (level) {
case 3:
printf("A ");
case 2:
printf("B ");
case 1:
printf("C ");
default:
printf("D ");
}
printf("\n");
printf("--- with break ---\n");
switch (level) {
case 3:
printf("A ");
break;
case 2:
printf("B ");
break;
case 1:
printf("C ");
break;
default:
printf("D ");
}
printf("\n");
return 0;
}
Writing src/p04_c08_19_switch_fallthrough.c
!gcc -Wall -o bin/p04_c08_19_switch_fallthrough src/p04_c08_19_switch_fallthrough.c && ./bin/p04_c08_19_switch_fallthrough--- without break ---
B C D
--- with break ---
B
مقدار level برابر ۲ است. در نسخهی اول، پرش به case 2 انجام میشود، اما چون break نداریم، B و بعد از آن C و حتی D (بلوک default) هم چاپ میشوند. در نسخهی دوم، break بعد از B برنامه را از switch بیرون میبرد. تفاوت را در انیمیشنهای زیر خطبهخط دنبال کنید:
code_sw1 = ["switch (level) {",
" case 3: printf(\"A \");",
" case 2: printf(\"B \");",
" case 1: printf(\"C \");",
" default: printf(\"D \");",
"}"]
LG_SW = [["cur", "در حال اجرا"], ["ok", "اجرا شد"], ["dim", "از روی آن پریده شد"], ["i", "هنوز اجرا نشده"]]
r = Rec("switch WITHOUT break (level = 2)", code_sw1, ["case 3", "case 2", "case 1", "default"], LG_SW,
labels=["مقدار ۳", "مقدار ۲", "مقدار ۱", "هر مقدار دیگر"])
r.var(level=2)
r.at(1, f"{_c('switch')} مقدار {_c('level')} را فقط یکبار حساب میکند: {_c(2)}.")
r.mark(0, "dim"); r.mark(1, "cur")
r.at(3, f"پرش مستقیم به {_c('case 2')} (برچسب {_c('case 3')} نادیده گرفته میشود). «پرش» فقط نقطهی <b>شروع</b> اجراست.")
r.echo("B "); r.mark(1, "ok")
r.at(3, f"{_c('B')} چاپ شد. در این خط {_c('break')} نداریم، پس برنامه متوقف نمیشود.")
r.mark(2, "cur"); r.echo("C ")
r.at(4, f"سقوط (Fall-Through) به {_c('case 1')}: بدون بررسی شرط، {_c('C')} هم چاپ میشود.")
r.mark(2, "ok"); r.mark(3, "cur"); r.echo("D ")
r.at(5, f"سقوط به {_c('default')}: {_c('D')} هم چاپ میشود.")
r.mark(3, "ok")
r.at(6, "پایان switch. خروجی: «B C D» — یعنی فراموش کردن break سه بلوک را اجرا کرد، نه یکی.")
display(r.show())
code_sw2 = ["switch (level) {",
" case 3: printf(\"A \"); break;",
" case 2: printf(\"B \"); break;",
" case 1: printf(\"C \"); break;",
" default: printf(\"D \");",
"}"]
r = Rec("switch WITH break (level = 2)", code_sw2, ["case 3", "case 2", "case 1", "default"], LG_SW,
labels=["مقدار ۳", "مقدار ۲", "مقدار ۱", "هر مقدار دیگر"])
r.var(level=2)
r.at(1, f"{_c('switch')} مقدار {_c('level')} را فقط یکبار حساب میکند: {_c(2)}.")
r.mark(0, "dim"); r.mark(1, "cur")
r.at(3, f"پرش مستقیم به {_c('case 2')}.")
r.echo("B "); r.mark(1, "ok")
r.at(3, f"{_c('B')} چاپ شد.")
r.mark({2: "dim", 3: "dim"})
r.at(3, f"{_c('break')}: کنترل فوراً از کل {_c('switch')} خارج میشود؛ {_c('case 1')} و {_c('default')} اجرا نمیشوند.")
r.at(6, "پایان switch. خروجی فقط «B» است.")
display(r.show())
Fall-Through همیشه باگ نیست؛ گاهی عمداً از آن استفاده میکنیم (مثلاً وقتی چند case باید یک کار مشترک کنند، در مثال C پایین). به همین دلیل زبان C آن را ممنوع نکرده است. اما چون فراموش کردن break یکی از رایجترین خطاهاست، قرارداد خوبی است که اگر عمداً break نمیگذارید، با یک توضیح (/* fall through */) آن را مشخص کنید.
Example B - Real: ماشینحساب¶
%%writefile src/p04_c08_20_calculator.c
#include <stdio.h>
int main(void)
{
int a, b;
char op;
if (scanf("%d %c %d", &a, &op, &b) != 3) {
printf("Bad input\n");
return 1;
}
switch (op) {
case '+':
printf("%d + %d = %d\n", a, b, a + b);
break;
case '-':
printf("%d - %d = %d\n", a, b, a - b);
break;
case '*':
printf("%d * %d = %d\n", a, b, a * b);
break;
case '/':
if (b == 0) {
printf("Error: division by zero\n");
} else {
printf("%d / %d = %d (remainder %d)\n", a, b, a / b, a % b);
}
break;
default:
printf("Error: unknown operator '%c'\n", op);
}
return 0;
}
Writing src/p04_c08_20_calculator.c
%%bash
gcc -Wall -o bin/p04_c08_20_calculator src/p04_c08_20_calculator.c || exit 1
echo "8 + 2" | ./bin/p04_c08_20_calculator
echo "8 - 12" | ./bin/p04_c08_20_calculator
echo "6 * 7" | ./bin/p04_c08_20_calculator
echo "17 / 5" | ./bin/p04_c08_20_calculator
echo "8 / 0" | ./bin/p04_c08_20_calculator
echo "8 ^ 2" | ./bin/p04_c08_20_calculator8 + 2 = 10
8 - 12 = -4
6 * 7 = 42
17 / 5 = 3 (remainder 2)
Error: division by zero
Error: unknown operator '^'
چرا شاخهی / یک if داخلی دارد؟
switch فقط «کدام عملگر» را مشخص میکند؛ اما «آیا تقسیم امن است؟» یک تصمیم دیگر است و باید با ساختار شرطی دیگری گرفته شود. ساختارهای شرطی را میتوان آزادانه داخل هم گذاشت.
چرا ورودی 8 ^ 2 به default میرود؟
چون '^' با هیچیک از caseها برابر نیست. default همان جایی است که ورودیهای پیشبینینشده را با یک پیام روشن مدیریت میکنیم؛ بدون آن، برنامه در این حالت بیصدا هیچ کاری نمیکرد.
Example C - Tricky: ترکیب چند case (و محدودیت بازه)¶
فرض کنید میخواهیم بگوییم یک کاراکتر «حرف صدادار» است یا «بیصدا». پنج حرف صدادار داریم (در دو حالت کوچک و بزرگ) که همگی یک پاسخ مشترک دارند. با Fall-Through عمدی، چند case پشتسرهم را به یک بلوک وصل میکنیم. اما switch نمیتواند بپرسد «آیا اصلاً حرف الفبا است؟» (چون این یک بازه است)؛ آن را با if قبل از switch بررسی میکنیم:
%%writefile src/p04_c08_21_switch_vowel.c
#include <stdio.h>
int main(void)
{
char ch;
if (scanf(" %c", &ch) != 1) {
return 1;
}
if (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))) {
printf("'%c': not a letter\n", ch);
} else {
switch (ch) {
case 'a': case 'A':
case 'e': case 'E':
case 'i': case 'I':
case 'o': case 'O':
case 'u': case 'U':
printf("'%c': vowel\n", ch);
break;
default:
printf("'%c': consonant\n", ch);
}
}
return 0;
}
Writing src/p04_c08_21_switch_vowel.c
%%bash
gcc -Wall -o bin/p04_c08_21_switch_vowel src/p04_c08_21_switch_vowel.c || exit 1
echo "e" | ./bin/p04_c08_21_switch_vowel
echo "K" | ./bin/p04_c08_21_switch_vowel
echo "U" | ./bin/p04_c08_21_switch_vowel
echo "7" | ./bin/p04_c08_21_switch_vowel'e': vowel
'K': consonant
'U': vowel
'7': not a letter
این مثال یک تقسیم کار روشن را نشان میدهد: **بازهها را if مدیریت میکند، مقادیر گسسته را switch.** اگر همین مسئله را با else if مینوشتیم، شرطی با ده مقایسهی || پشتسرهم لازم بود.
Example D - Real: تعداد روزهای ماه (ترکیب با الگوریتم کبیسه)¶
این مسئله ترکیب طبیعی دو الگوریتم قبلی است: ماهها در سه گروه قرار میگیرند (۳۰ روزه، ۳۱ روزه، و فوریه). فوریه خودش یک تصمیم است (کبیسه بودن سال) که همان الگوریتم ۸.۴ را اجرا میکند.
%%writefile src/p04_c08_22_days_in_month.c
#include <stdio.h>
int main(void)
{
int month, year, days = 0;
if (scanf("%d %d", &month, &year) != 2) {
return 1;
}
switch (month) {
case 4: case 6: case 9: case 11:
days = 30;
break;
case 2:
if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
days = 29;
} else {
days = 28;
}
break;
case 1: case 3: case 5: case 7: case 8: case 10: case 12:
days = 31;
break;
default:
printf("Invalid month: %d\n", month);
return 1;
}
printf("Month %d of year %d has %d days\n", month, year, days);
return 0;
}
Writing src/p04_c08_22_days_in_month.c
%%bash
gcc -Wall -o bin/p04_c08_22_days_in_month src/p04_c08_22_days_in_month.c || exit 1
echo "2 2024" | ./bin/p04_c08_22_days_in_month
echo "2 1900" | ./bin/p04_c08_22_days_in_month
echo "4 2023" | ./bin/p04_c08_22_days_in_month
echo "12 2023" | ./bin/p04_c08_22_days_in_month
echo "13 2023" | ./bin/p04_c08_22_days_in_month || trueMonth 2 of year 2024 has 29 days
Month 2 of year 1900 has 28 days
Month 4 of year 2023 has 30 days
Month 12 of year 2023 has 31 days
Invalid month: 13
به ترکیب سه ایده دقت کنید: (۱) گروهبندی caseها برای مقادیر با پاسخ مشترک، (۲) تصمیم تو در تو در داخل یک case، (۳) default برای ورودی نامعتبر که با return برنامه را فوراً تمام میکند. همچنین مقدار اولیهی days = 0 تضمین میکند که متغیر در هیچ مسیری ناخواسته مقداردهینشده باقی نماند.
Example E - Trick: تبدیل بازه به مقدار گسسته¶
گفتیم switch بازه را نمیفهمد. اما یک ترفند الگوریتمی وجود دارد: بازه را با یک محاسبهی ساده به یک مقدار گسسته تبدیل کنیم. در سیستم نمرهدهی ۱۰۰تایی، نمرهها را بر ۱۰ تقسیم صحیح میکنیم؛ همهی نمرههای ۹۰ تا ۹۹ میشوند ۹، همهی ۸۰ تا ۸۹ میشوند ۸ و ...
%%writefile src/p04_c08_23_switch_score_div10.c
#include <stdio.h>
int main(void)
{
int score;
char grade = '?';
if (scanf("%d", &score) != 1) {
return 1;
}
if (score < 0 || score > 100) {
printf("%d: invalid score\n", score);
return 1;
}
switch (score / 10) {
case 10: /* only 100 */
case 9:
grade = 'A';
break;
case 8:
grade = 'B';
break;
case 7:
grade = 'C';
break;
case 6:
grade = 'D';
break;
default:
grade = 'F';
}
printf("%d -> %c\n", score, grade);
return 0;
}
Writing src/p04_c08_23_switch_score_div10.c
%%bash
gcc -Wall -o bin/p04_c08_23_switch_score_div10 src/p04_c08_23_switch_score_div10.c || exit 1
echo "100" | ./bin/p04_c08_23_switch_score_div10
echo "95" | ./bin/p04_c08_23_switch_score_div10
echo "90" | ./bin/p04_c08_23_switch_score_div10
echo "89" | ./bin/p04_c08_23_switch_score_div10
echo "70" | ./bin/p04_c08_23_switch_score_div10
echo "60" | ./bin/p04_c08_23_switch_score_div10
echo "59" | ./bin/p04_c08_23_switch_score_div10
echo "0" | ./bin/p04_c08_23_switch_score_div10
echo "105" | ./bin/p04_c08_23_switch_score_div10
echo "-5" | ./bin/p04_c08_23_switch_score_div10 || true100 -> A
95 -> A
90 -> A
89 -> B
70 -> C
60 -> D
59 -> F
0 -> F
105: invalid score
-5: invalid score
چرا case 10 هم لازم است؟
چون 100 / 10 برابر 10 است و جزو بازهی A محسوب میشود. این یک مورد مرزی است که فقط با تست 100 پیدا میشود.
چرا اعتبارسنجی بازه پیش از switch ضروری است؟
چون 105 / 10 برابر 10 است و بدون اعتبارسنجی «A» میگرفت؛ و -5 / 10 در C برابر 0 است (گردکردن به سمت صفر) که به شاخهی default میرفت و «F» میداد. ترفند «تقسیم بر ۱۰» فقط وقتی امن است که ورودی از قبل در بازهی مورد انتظار باشد.
switch یا else if؟¶
| معیار | switch | زنجیرهی else if |
|---|---|---|
| نوع شرط | فقط تساوی با ثابتهای صحیح | هر شرط دلخواه (بازه، ترکیب منطقی، اعشاری و ...) |
| تکرار عبارت مورد مقایسه | یکبار نوشته میشود | در هر شرط تکرار میشود |
ترتیب caseها | معمولاً بیاثر (چون ثابتها منحصربهفردند) | حیاتی (اولین شرط درست برنده است) |
| Fall-Through | وجود دارد (خطر و ابزار) | وجود ندارد |
| مناسب برای | منو، دستور، کد وضعیت، روز و ماه | بازهها، شرطهای مرکب، دادهی اعشاری |
نکتهی مهم: انتخاب بین این دو، اول از همه یک تصمیم دربارهی خوانایی است. ممکن است کامپایلر switch را بهینهتر ترجمه کند، اما روی برنامههای درسی تفاوت سرعت قابلتوجهی ایجاد نمیشود.
تمرین درون فصل ۸.۹¶
نوع تمرین: Predict the Output
int x = 3;
switch (x) {
case 1: printf("one ");
case 3: printf("three ");
case 4: printf("four "); break;
case 5: printf("five ");
}
printf("end\n");خروجی را پیشبینی کنید. سپس بگویید اگر x = 5 باشد خروجی چه میشود.
تمرین درون فصل ۸.۱۰ : switch روی مقدار اعشاری¶
نوع تمرین: Explain Why
چرا کد زیر در C خطای کامپایل میدهد؟ چه ساختار جایگزینی را پیشنهاد میکنید؟
double price = 9.5;
switch (price) {
case 9.5:
printf("Cheap\n");
break;
}تمرینهای پایانی زیربخش: switch¶
★ سطح پایه
Small Implementation:
برنامهای بنویسید که شمارهی ماه (۱ تا ۱۲) را بگیرد و نام فصل (بهار، تابستان، پاییز، زمستان) را با Fall-Through عمدی چاپ کند.Predict the Output:
int n = 2;
switch (n) {
case 1: printf("A"); break;
case 2: printf("B");
case 3: printf("C"); break;
default: printf("D");
}★★ سطح متوسط
Find the Bug:
char op = '+';
switch (op) {
case '+':
printf("add\n");
case '-':
printf("subtract\n");
break;
}خروجی چیست و چرا اینطور است؟ اصلاح کنید.
Modify the Algorithm:
برنامهی ماشینحساب را طوری تغییر دهید که علاوه بر چهار عمل اصلی، عملگر%(باقیمانده) را هم پشتیبانی کند و برای%هم از تقسیم بر صفر محافظت کند.
★★★ سطح چالشی
Design:
برنامهای بنویسید که نمرهی ۰ تا ۲۰ را بگیرد و با ترفند «تقسیم صحیح»، درجهبندی ۴تایی (۰ تا ۹ مردود، ۱۰ تا ۱۳ قبول، ۱۴ تا ۱۶ خوب، ۱۷ تا ۲۰ عالی) را فقط باswitchانجام دهد. چه محاسبهای مرزهای نامنظم این بازهها را به مقدارهای گسسته تبدیل میکند؟ (راهنمایی: ممکن است ترکیب Fall-Through با تعداد زیادیcaseسادهتر از یک فرمول باشد.)Compare Approaches:
دو نسخهیswitchوelse ifاز «نمایش نام روز هفته» را مقایسه کنید. در چه موقعیتی نسخهیelse ifکاملاً غیرقابل جایگزینی باswitchاست؟
8.9 انتخاب ساختار مناسب¶
حالا که پنج ابزار شرطی در اختیار داریم، سؤال طبیعی این است: برای هر مسئله کدام را انتخاب کنیم؟ جدول زیر یک راهنمای تصمیمگیری است:
| نوع مسئله | ساختار پیشنهادی |
|---|---|
| یک کار اضافه که فقط در صورت برقراری شرط انجام میشود | if |
| دو مسیر متقابل (دقیقاً یکی اجرا شود) | if-else |
| چند بازه یا شرط مرکب که دستههای ناسازگار تولید میکنند | زنجیرهی else if |
| فقط انتخاب یک مقدار بر اساس شرط | ?: |
| مقایسهی یک عبارت صحیح با چند مقدار ثابت گسسته | switch |
| چند شرط مستقل که ممکن است همزمان درست باشند | چند if جداگانه (نه زنجیره!) |
سطر آخر جدول مهمترین و پنهانترین تفاوت است. فرض کنید در یک فروشگاه، مشتری «عضو باشگاه» ۵٪ تخفیف و سفارش «بالای ۱۰۰۰» ۱۰٪ تخفیف میگیرد؛ و هر دو تخفیف قابل جمع هستند. اگر این دو شرط را با else if به هم بچسبانیم، فقط یکی اعمال میشود:
%%writefile src/p04_c08_24_independent_vs_chain.c
#include <stdio.h>
int main(void)
{
int total, member;
if (scanf("%d %d", &total, &member) != 2) {
return 1;
}
/* Independent conditions: both discounts may apply */
int discount_a = 0;
if (member) {
discount_a += 5;
}
if (total >= 1000) {
discount_a += 10;
}
/* Chained conditions: only the first matching one applies */
int discount_b = 0;
if (member) {
discount_b = 5;
} else if (total >= 1000) {
discount_b = 10;
}
printf("total=%d member=%d | independent: %d%% | chained: %d%%\n",
total, member, discount_a, discount_b);
return 0;
}
Writing src/p04_c08_24_independent_vs_chain.c
%%bash
gcc -Wall -o bin/p04_c08_24_independent_vs_chain src/p04_c08_24_independent_vs_chain.c || exit 1
echo "1200 1" | ./bin/p04_c08_24_independent_vs_chain
echo "300 1" | ./bin/p04_c08_24_independent_vs_chain
echo "1200 0" | ./bin/p04_c08_24_independent_vs_chain
echo "300 0" | ./bin/p04_c08_24_independent_vs_chaintotal=1200 member=1 | independent: 15% | chained: 5%
total=300 member=1 | independent: 5% | chained: 5%
total=1200 member=0 | independent: 10% | chained: 10%
total=300 member=0 | independent: 0% | chained: 0%
فقط در حالت اول (1200 1، یعنی مشتری عضو و سفارش بزرگ) دو نسخه تفاوت دارند: نسخهی مستقل ۱۵٪ و نسخهی زنجیرهای فقط ۵٪. سؤالی که باید همیشه بپرسید: «آیا این شرطها متقابل (فقط یکی میتواند درست باشد) هستند، یا مستقل؟» پاسخ، انتخاب بین else if و چند if را تعیین میکند.
تمرین درون فصل ۸.۱۱¶
نوع تمرین: Choose the Structure
برای هر سناریوی زیر مشخص کنید کدام ساختار مناسبتر است (if ، if-else ، else if ، ?: ، switch ، یا چند if مستقل) و دلیل بیاورید:
تبدیل شمارهی ماه (۱ تا ۱۲) به نام فصل.
محاسبهی هزینهی ارسال: ۲۰ هزار تومان برای وزن زیر ۱ کیلو، ۳۵ هزار برای ۱ تا ۵ کیلو، ۶۰ هزار برای بالاتر.
چاپ هشدار «باتری ضعیف» و هشدار «حافظهی پر» که ممکن است همزمان رخ دهند.
انتخاب کوچکتر از دو عدد برای نمایش.
اجرای دستور کاربر از منوی «۱ ثبتنام، ۲ ورود، ۳ خروج».
8.10 خطاهای رایج در ساختارهای شرطی¶
**❌ اشتباه ۱: استفاده از = بهجای ==**
if (x = 5) {
printf("x is five\n");
}چرا اشتباه است؟
x = 5 یک انتساب است: ابتدا مقدار ۵ را در x میریزد و بعد خود مقدار ۵ را بهعنوان نتیجهی شرط برمیگرداند؛ پس شرط همیشه درست است و x هم بیسروصدا خراب میشود. کامپایلر معمولاً هشدار میدهد، پس هشدارها را (با -Wall) جدی بگیرید.
✅ نسخه صحیح
if (x == 5) {
printf("x is five\n");
}❌ اشتباه ۲: نقطهویرگول بعد از شرط
if (score >= 18);
{
printf("Excellent\n");
}چرا اشتباه است؟
; یک «دستور خالی» است و بدنهی if همان میشود. بلوک بعدی یک بلوک معمولی و مستقل است که همیشه اجرا میشود.
✅ نسخه صحیح: ; را حذف کنید.
❌ اشتباه ۳: مقایسهی زنجیرهای
if (0 <= score <= 20) { ... } // درست به نظر میرسد، اما نیستچرا اشتباه است؟
0 <= score نتیجهاش 0 یا 1 است و بعد آن عدد با 20 مقایسه میشود؛ پس عبارت همیشه درست است.
✅ نسخه صحیح
if (score >= 0 && score <= 20) { ... }❌ اشتباه ۴: مقایسهی دقیق اعداد اعشاری
if (0.1 + 0.2 == 0.3) { ... } // نادرست است!چرا اشتباه است؟
اعداد اعشاری در حافظه بهصورت تقریبی ذخیره میشوند و 0.1 + 0.2 دقیقاً برابر 0.3 نیست.
✅ نسخه صحیح: فاصلهی دو عدد را با یک تلورانس (مثلاً 1e-9) مقایسه کنید: diff < 1e-9، که diff قدر مطلق تفاضل دو عدد است.
**❌ اشتباه ۵: x == 1 || 2**
if (x == 1 || 2) { ... } // همیشه درست استچرا اشتباه است؟
این عبارت (x == 1) || 2 خوانده میشود و 2 غیرصفر است و پس عبارت **برای هر x** درست است. مفهوم انسانی «x برابر ۱ یا ۲ باشد» باید کامل نوشته شود.
✅ نسخه صحیح
if (x == 1 || x == 2) { ... }**❌ اشتباه ۶: فراموش کردن break در switch (در ۸.۸ دیدیم)، و ❌ اشتباه ۷: ترتیب غلط در زنجیرهی else if** (در ۸.۵ دیدیم).
برای دیدن چهار مورد اول در عمل، برنامهی زیر را اجرا کنید و به هشدارهای کامپایلر (قبل از خروجی) هم دقت کنید:
%%writefile src/p04_c08_25_pitfalls.c
#include <stdio.h>
int main(void)
{
int x = 3;
/* 1. assignment instead of comparison */
if (x = 5) {
printf("1) entered the if, and x is now %d\n", x);
}
/* 2. chained comparison */
if (3 > 2 > 1) {
printf("2) 3 > 2 > 1 is true\n");
} else {
printf("2) 3 > 2 > 1 is FALSE (surprise!)\n");
}
/* 3. floating-point equality */
double sum = 0.1 + 0.2;
if (sum == 0.3) {
printf("3) 0.1 + 0.2 equals 0.3\n");
} else {
printf("3) 0.1 + 0.2 != 0.3 (sum = %.17f)\n", sum);
}
/* 4. x == 1 || 2 */
int y = 7;
if (y == 1 || 2) {
printf("4) y == 1 || 2 is true even for y = %d\n", y);
}
return 0;
}
Writing src/p04_c08_25_pitfalls.c
!gcc -Wall -o bin/p04_c08_25_pitfalls src/p04_c08_25_pitfalls.c && ./bin/p04_c08_25_pitfallssrc/p04_c08_25_pitfalls.c: In function ‘main’:
src/p04_c08_25_pitfalls.c:8:9: warning: suggest parentheses around assignment used as truth value []8;;https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wparentheses-Wparentheses]8;;]
8 | if (x = 5) {
| ^
src/p04_c08_25_pitfalls.c:13:15: warning: comparisons like ‘X<=Y<=Z’ do not have their mathematical meaning []8;;https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wparentheses-Wparentheses]8;;]
13 | if (3 > 2 > 1) {
| ^
1) entered the if, and x is now 5
2) 3 > 2 > 1 is FALSE (surprise!)
3) 0.1 + 0.2 != 0.3 (sum = 0.30000000000000004)
4) y == 1 || 2 is true even for y = 7
(اشتباه ۲، یعنی نقطهویرگول بعد از if، بهخاطر ایجاد بلوک خالی در برنامهی بالا لحاظ نشده است؛ آن را در تمرینها خودتان امتحان کنید.)
8.11 کاربردهای واقعی ساختارهای شرطی¶
اعتبارسنجی ورودی کاربر (فرمها، رمزها، سن، مبلغ) پیش از پردازش.
کنترل دسترسی و سطح مجوز در سیستمها (مدیر / کاربر عادی / مهمان).
منوها و دستورهای واسط کاربری (
switchروی کلید یا انتخاب).کدهای خطا و وضعیت در سیستمعامل و پروتکلها (تبدیل کد عددی به معنی).
محاسبهی مالیات، تخفیف، تعرفه و هزینهی پلهای.
بازیها: تصمیمگیری شخصیتها، تشخیص برخورد، قوانین امتیازدهی.
سیستمهای کنترلی و حسگرها: روشن/خاموش شدن بر اساس آستانهی دما یا فشار.
...
تمرینهای پایانی فصل ۸¶
توجه: این تمرینها با آنچه در تمرینهای زیربخش دیدید تفاوت دارند و ساختارهای شرطی، تست مرزی و طراحی را با هم ترکیب میکنند.
Predict the Output:
int a = 5, b = 10;
if (a > 3 && b < 5 || a == 5) {
printf("X\n");
} else {
printf("Y\n");
}خروجی را پیشبینی کنید و جای پرانتزهای «ضمنی» را با رعایت اولویت عملگرها نشان دهید.
Trace:
برای ورودی15در برنامهی درجهبندی ۲۰تایی، و سپس ورودی100در برنامهی درجهبندی ۱۰۰تایی (switch)، مسیر اجرا را دنبال کنید و نتیجه را بنویسید.Find the Bug:
if (n % 2 == 0)
printf("even\n");
printf("divisible by two\n");
else
printf("odd\n");این کد اصلاً کامپایل نمیشود. دلیل را توضیح دهید و راه اصلاح بدهید.
Edge Case Reasoning:
یک برنامهی تشخیص «سال کبیسه» را با ورودیهای0،-4،4و100در ذهن اجرا کنید. آیا الگوریتم برای سالهای ≤ ۰ معنای تقویمی دارد؟ این یک مسئلهی الگوریتمی است یا مسئلهی دادهی ورودی؟Design + Implementation:
برنامهای بنویسید که ساعت (۰ تا ۲۳) را بخواند و پیام مناسب را چاپ کند: «صبح بخیر» (۵ تا ۱۱)، «ظهر بخیر» (۱۲ تا ۱۳)، «عصر بخیر» (۱۴ تا ۱۸)، «شب بخیر» (بقیهی ساعتهای معتبر) و برای ورودی خارج از ۰ تا ۲۳ پیام خطا. مرزها را تست کنید.Refactoring:
برنامهی خودپرداز نسخهی تو در تو را با ایدهی Guard Clause وreturnزودهنگام (بدونelse if) بازنویسی کنید.Compare Approaches:
مسئلهی «تشخیص سال کبیسه» را (الف) با یک عبارت منطقی، (ب) با زنجیرهیelse if، (ج) باifتو در تو بنویسید و از نظر خوانایی و احتمال خطا مقایسه کنید.Algorithm Design:
سه عدد صحیحa, b, cرا به ترتیب صعودی مرتب چاپ کنید (بدون آرایه و فقط باif). حداقل چند مقایسه لازم است؟ آیا یک ساختار مرتبسازی هست که برای هر ورودی دقیقاً همین تعداد مقایسه را انجام دهد؟Refactoring:
عبارت زیر را با استفاده از قوانین دمورگان ساده کنید و ثابت کنید با عبارت اصلی معادل است:
if (!(a > 0 && b > 0) && !(c < 0 || d < 0)) { ... }Retrieval Practice فصل ۸¶
هنگام ارزیابی
A && B، چه وقتBاصلاً ارزیابی نمیشود؟قوانین دمورگان چه کاربردی در نوشتن شرط «نامعتبر» دارند؟
چرا در یک زنجیرهی
else if، ترتیب شرطها بخشی از منطق برنامه است؟تست مرزی (Boundary Test) یعنی چه و برای شرط
score >= 14چه ورودیهایی را شامل میشود؟Guard Clause چیست و چه مشکلی از کد تو در تو را حل میکند؟
تفاوت «دستور» و «عبارت» در
ifو?:چیست؟Fall-Through چیست؟ یک مورد که مفید و یک مورد که خطرناک است نام ببرید.
چرا
switchنمیتواند شرطscore >= 17را مستقیماً بسنجد؟
8.12 جمعبندی فصل ۸¶
در این فصل یاد گرفتیم چرا اجرای ترتیبی برای مسئلههای واقعی کافی نیست و شرط چگونه به برنامه امکان انتخاب بین چند مسیر را میدهد. دیدیم که در C مقدار صفر «نادرست» و هر مقدار غیرصفر «درست» است، که && و || بهصورت کوتاهمدار ارزیابی میشوند و قوانین دمورگان ابزار ساختن نقیض شرطها هستند. سپس if، if-else و زنجیرهی else if را بررسی کردیم و به این نتیجه رسیدیم که «اولین شرط درست برنده است» و ترتیب شرطها بخشی از الگوریتم است. با تست مرزی و پوشش مسیرها یاد گرفتیم درستی شرطها را بهصورت سیستماتیک بیازماییم. دیدیم که عملگر ?: برای انتخاب مقدار مناسب است و switch برای مقایسهی یک عبارت با ثابتهای گسسته، با نقش حیاتی break و پدیدهی Fall-Through. در نهایت یاد گرفتیم بین «شرطهای متقابل» (زنجیره) و «شرطهای مستقل» (چند if) تمایز بگذاریم.
حالا که میتوانیم تصمیم بگیریم، سؤال طبیعی بعدی این است: چطور یک تصمیم یا یک محاسبه را چندین بار تکرار کنیم؟ مثلاً چطور همین درجهبندی را برای نمرهی ۵۰۰ دانشجو انجام دهیم، بدون اینکه ۵۰۰ بار کد را کپی کنیم؟ این موضوع فصل بعد است.
فصل ۹ : حلقهها (Loops)¶
9.1 چرا به حلقه نیاز داریم؟¶
فرض کنید میخواهیم اعداد ۱ تا ۵ را چاپ کنیم و مجموعشان را حساب کنیم. با دانش فعلیمان مینویسیم:
%%writefile src/p04_c09_01_loops_naive.c
#include <stdio.h>
int main(void)
{
int sum = 0;
printf("1\n");
sum += 1;
printf("2\n");
sum += 2;
printf("3\n");
sum += 3;
printf("4\n");
sum += 4;
printf("5\n");
sum += 5;
printf("Sum: %d\n", sum);
return 0;
}
Writing src/p04_c09_01_loops_naive.c
!gcc -Wall -o bin/p04_c09_01_loops_naive src/p04_c09_01_loops_naive.c && ./bin/p04_c09_01_loops_naive1
2
3
4
5
Sum: 15
برای ۵ عدد قابل تحمل است. اما چند سؤال از خودتان بپرسید:
اگر عدد ۱ تا ۱۰۰۰ بود، باید ۲۰۰۰ خط کد مینوشتیم؟
اگر تعداد اعداد را کاربر تعیین کند (یعنی در زمان نوشتن برنامه معلوم نباشد)، چند خط باید نوشت؟
کد بالا ده خط تقریباً یکسان دارد؛ اگر در یکی از آنها اشتباه کنیم، چطور آن را پیدا کنیم؟
مشکل اصلی: کدی که تعداد دفعات اجرایش در زمان نوشتن ثابت (و در عمل محدود به صبر ما) است، نمیتواند با اندازهی مسئله رشد کند. ما به سازهای نیاز داریم که:
یک دسته دستور را بارها اجرا کند، بدون اینکه آن را کپی کنیم.
تعداد تکرار را بر اساس دادهی زمان اجرا (یک شرط) تعیین کند، نه بر اساس تعداد خطوط برنامه.
در هر تکرار، وضعیت را کمی تغییر دهد تا بالاخره به پایان برسد.
این دقیقاً همان چیزی است که حلقه (Loop) فراهم میکند.
آناتومی یک حلقه¶
هر حلقهی درست از چهار بخش ساخته میشود. تشخیص این چهار بخش، مهمترین مهارت این فصل است:
| بخش | پرسش | مثال (چاپ ۱ تا ۵) |
|---|---|---|
| مقداردهی اولیه (Initialization) | حلقه از کجا شروع میشود؟ | i = 1 |
| شرط ادامه (Condition) | تا کی تکرار کنیم؟ | i <= 5 |
| بدنه (Body) | در هر تکرار چه کار کنیم؟ | printf, sum += i |
| بهروزرسانی (Update) | چطور به پایان نزدیک شویم؟ | i++ |
اگر یکی از این چهار بخش غلط یا فراموش شود، حلقه یا اصلاً اجرا نمیشود، یا کار اشتباه میکند، یا هرگز تمام نمیشود. همچنین به یک ایدهی ذهنی عمیق عادت کنید: نامتغیر حلقه (Loop Invariant)، یعنی چیزی که در ابتدای هر تکرار درست است. مثلاً در حلقهی جمع ۱ تا n، قبل از هر تکرار میدانیم «sum مجموع همهی اعداد کوچکتر از i است». درستی الگوریتم یعنی این جمله از اول تا آخر برقرار بماند.
تمرین درون فصل ۹.۱¶
نوع تمرین: Quick Reasoning
در برنامهی loops_naive تعیین کنید «مقداردهی اولیه»، «شرط ادامه» و «بهروزرسانی» چه نقشی دارند، اگر بخواهیم آن را به یک حلقه تبدیل کنیم. چه چیزی در هر تکرار ثابت میماند و چه چیزی تغییر میکند؟
9.2 حلقهی while¶
ایده الگوریتم¶
while سادهترین حلقه است: «تا وقتی شرط برقرار است، بدنه را تکرار کن». شرط قبل از هر تکرار بررسی میشود؛ پس اگر از همان ابتدا نادرست باشد، بدنه حتی یکبار هم اجرا نمیشود (Pre-test Loop).
Pseudocode¶
initialise state
while condition:
body
update state // must move the state toward making the condition falseFlowchart¶
Example A - Simple: شمارش معکوس و مجموع ۱ تا n¶
%%writefile src/p04_c09_02_while_countdown.c
#include <stdio.h>
int main(void)
{
int n = 5;
while (n > 0) {
printf("%d ", n);
n--;
}
printf("Liftoff!\n");
return 0;
}
Writing src/p04_c09_02_while_countdown.c
!gcc -Wall -o bin/p04_c09_02_while_countdown src/p04_c09_02_while_countdown.c && ./bin/p04_c09_02_while_countdown5 4 3 2 1 Liftoff!
%%writefile src/p04_c09_03_while_sum.c
#include <stdio.h>
int main(void)
{
int n;
if (scanf("%d", &n) != 1) {
return 1;
}
int i = 1;
long long sum = 0;
while (i <= n) {
sum += i;
i++;
}
printf("n = %d: loop sum = %lld, formula n(n+1)/2 = %lld\n",
n, sum, (long long)n * (n + 1) / 2);
return 0;
}
Writing src/p04_c09_03_while_sum.c
%%bash
gcc -Wall -o bin/p04_c09_03_while_sum src/p04_c09_03_while_sum.c || exit 1
echo "5" | ./bin/p04_c09_03_while_sum
echo "100" | ./bin/p04_c09_03_while_sum
echo "1" | ./bin/p04_c09_03_while_sum
echo "0" | ./bin/p04_c09_03_while_sumn = 5: loop sum = 15, formula n(n+1)/2 = 15
n = 100: loop sum = 5050, formula n(n+1)/2 = 5050
n = 1: loop sum = 1, formula n(n+1)/2 = 1
n = 0: loop sum = 0, formula n(n+1)/2 = 0
چرا ورودی 0 جواب 0 میدهد و برنامه خراب نمیشود؟
چون شرط i <= n از همان ابتدا نادرست است و بدنه اصلاً اجرا نمیشود (صفر تکرار). مجموع هیچ عددی، همان مقدار اولیهی sum یعنی 0 است. این رفتار بدون نیاز به if اضافه، حالتهای مرزی را درست پوشش میدهد.
چرا فرمول n(n+1)/2 هم کنار حلقه چاپ شده است؟
یک درس الگوریتمی مهم: گاهی یک فرمول بسته همان نتیجه را بدون حلقه میدهد. حلقهی بالا n جمع انجام میدهد (زمان متناسب با n)، اما فرمول فقط چند عمل (زمان ثابت). پیش از نوشتن حلقه بپرسید: «آیا راه ریاضی مستقیمی هست؟» با این حال حلقه عمومیتر است و هرجا فرمول نداریم کار میکند. نکتهی فنی: long long به کار رفته تا جمعهای بزرگ سرریز نکنند.
Trace: جدول مقادیر برای مجموع ۱ تا ۴¶
code_w = ["int i = 1, sum = 0;",
"while (i <= 4) {",
" sum += i;",
" i++;",
"}",
"printf(\"%d\", sum);"]
LG_LOOP = [["cur", "تکرار جاری (مقدار i)"], ["vis", "تکرار انجامشده"], ["min", "شرط نادرست شد"], ["i", "هنوز نرسیدهایم"]]
r = Rec("while loop: sum of 1..4", code_w, [1, 2, 3, 4, 5], LG_LOOP, labels=["i=1", "i=2", "i=3", "i=4", "i=5"])
r.var(i=1, sum=0)
r.ptr(i=0)
r.mark(0, "cur")
r.at(1, f"مقداردهی اولیه: {_c('i = 1')} و {_c('sum = 0')}. هنوز وارد حلقه نشدهایم.")
s = 0
for i in range(1, 5):
r.mark(i - 1, "cur"); r.ptr(i=i - 1)
r.at(2, f"شرط {_c(f'i <= 4')} با {_c(f'i = {i}')} ← {_c(f'{i} <= 4')} درست است؛ وارد بدنه میشویم.")
s += i; r.var(sum=s)
r.at(3, f"{_c(f'sum += {i}')} ← مقدار {_c('sum')} میشود {_c(s)}.")
r.var(i=i + 1); r.mark(i - 1, "vis"); r.mark(i, "cur"); r.ptr(i=i)
r.at(4, f"{_c('i++')} ← مقدار {_c('i')} میشود {_c(i + 1)}؛ برمیگردیم و دوباره شرط را بررسی میکنیم.")
r.mark(4, "min")
r.at(2, f"{_c('5 <= 4')} نادرست است؛ حلقه تمام میشود. بدنه دقیقاً ۴ بار اجرا شد.")
r.echo("10")
r.at(6, f"{_c('printf')} مقدار نهایی {_c('sum')} یعنی {_c(10)} را چاپ میکند.")
display(r.show())
Example B - Real: جمع ارقام یک عدد¶
مسئله: مجموع ارقام عدد n را حساب کنید (مثلاً 472 ← 4+7+2 = 13). ایدهی الگوریتم: رقم آخر هر عدد را میتوان با n % 10 جدا کرد و با n / 10 آن رقم را حذف کرد. پس تا وقتی عدد صفر نشده، رقم آخر را بردار، به مجموع اضافه کن و عدد را کوتاه کن. توجه: تعداد تکرارها از قبل معلوم نیست (به تعداد ارقام وابسته است)؛ این یک حلقهی کلاسیک while است.
%%writefile src/p04_c09_04_digit_sum.c
#include <stdio.h>
int main(void)
{
int n;
if (scanf("%d", &n) != 1 || n < 0) {
printf("Please enter a non-negative integer\n");
return 1;
}
int original = n;
int sum = 0, count = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
count++;
}
printf("%d: digit sum = %d, digit count = %d\n", original, sum, count);
return 0;
}
Writing src/p04_c09_04_digit_sum.c
%%bash
gcc -Wall -o bin/p04_c09_04_digit_sum src/p04_c09_04_digit_sum.c || exit 1
echo "472" | ./bin/p04_c09_04_digit_sum
echo "999" | ./bin/p04_c09_04_digit_sum
echo "7" | ./bin/p04_c09_04_digit_sum
echo "1000" | ./bin/p04_c09_04_digit_sum
echo "0" | ./bin/p04_c09_04_digit_sum472: digit sum = 13, digit count = 3
999: digit sum = 27, digit count = 3
7: digit sum = 7, digit count = 1
1000: digit sum = 1, digit count = 4
0: digit sum = 0, digit count = 0
code_d = ["int sum = 0;",
"while (n > 0) {",
" sum += n % 10;",
" n /= 10;",
"}"]
LG_DIG = [["cur", "رقمی که الان جدا میشود"], ["dim", "از عدد حذف شد"], ["i", "هنوز در عدد است"]]
r = Rec("while loop: digit sum of 472", code_d, [4, 7, 2], LG_DIG, labels=["صدگان", "دهگان", "یکان"])
n, s = 472, 0
r.var(n=n, sum=0)
r.at(1, f"{_c('sum')} را صفر میکنیم. عدد {_c(472)} را ارقام آن در نظر بگیرید؛ ارقام را از «یکان» به سمت چپ خواهیم برداشت.")
idx = 2
while n > 0:
r.at(2, f"شرط {_c('n > 0')} با {_c(f'n = {n}')} درست است.")
r.mark(idx, "cur"); r.ptr(**{"n%10": idx})
s += n % 10; r.var(sum=s)
r.at(3, f"{_c(f'n % 10')} برابر {_c(n % 10)} است (رقم آخر) و به {_c('sum')} اضافه میشود: {_c('sum')} = {_c(s)}.")
n //= 10; r.var(n=n); r.mark(idx, "dim"); idx -= 1
r.at(4, f"{_c('n /= 10')} ← رقم آخر حذف شد و {_c('n')} میشود {_c(n)}.")
r.ptr(**{"n%10": None})
r.at(2, f"{_c('0 > 0')} نادرست است؛ حلقه تمام شد. مجموع ارقام {_c(s)} است.")
display(r.show())
چرا ورودی 0 ارقام را صفر میشمارد؟
چون شرط n > 0 برای 0 از ابتدا نادرست است و بدنه اجرا نمیشود: sum = 0 درست است، اما count = 0 از نظر معنایی غلط است (عدد 0 یک رقم دارد). این یک باگ مرزی واقعی است. راهحل در بخش بعدی (do-while) میآید.
Example C - Tricky: الگوی Sentinel (حلقه با مقدار نگهبان)¶
گاهی تعداد داده از قبل معلوم نیست و کاربر «پایان دادهها» را با یک مقدار ویژه اعلام میکند؛ این مقدار را Sentinel مینامیم (اینجا -1 که نمرهی معتبر نیست). scanf عدد برگشتی دارد: تعداد مقادیر خواندهشدهی موفق؛ پس scanf(...) == 1 یعنی ورودی واقعاً خوانده شد (و در پایان ورودی، حلقه خودبهخود تمام میشود).
%%writefile src/p04_c09_05_while_sentinel_avg.c
#include <stdio.h>
int main(void)
{
int x, count = 0, sum = 0;
while (scanf("%d", &x) == 1 && x != -1) {
sum += x;
count++;
}
if (count == 0) {
printf("No scores entered\n");
} else {
printf("count = %d, sum = %d, average = %.2f\n",
count, sum, (double)sum / count);
}
return 0;
}
Writing src/p04_c09_05_while_sentinel_avg.c
%%bash
gcc -Wall -o bin/p04_c09_05_while_sentinel_avg src/p04_c09_05_while_sentinel_avg.c || exit 1
echo "18 15 20 12 17 -1" | ./bin/p04_c09_05_while_sentinel_avg
echo "-1" | ./bin/p04_c09_05_while_sentinel_avg
echo "14" | ./bin/p04_c09_05_while_sentinel_avgcount = 5, sum = 82, average = 16.40
No scores entered
count = 1, sum = 14, average = 14.00
چرا قبل از تقسیم، count == 0 را بررسی میکنیم؟
اگر کاربر بلافاصله -1 بزند، count صفر است و تقسیم sum / count یک تقسیم بر صفر میشد. هر الگوریتم «میانگینگیر» باید حالت «ورودی خالی» را پیشبینی کند؛ این یک Edge Case کلاسیک است.
ورودی سوم (14 بدون -1) چرا درست کار میکند؟
چون با تمام شدن ورودی، scanf مقدار 1 برنمیگرداند و شرط حلقه نادرست میشود. ترکیب scanf(...) == 1 && x != -1 هم پایان دادهها (EOF) و هم Sentinel را پوشش میدهد؛ و به لطف ارزیابی کوتاهمدار، x فقط وقتی با -1 مقایسه میشود که واقعاً مقدار گرفته باشد.
تمرین درون فصل ۹.۲¶
نوع تمرین: Trace
برای n = 305 الگوریتم جمع ارقام را دستی دنبال کنید و جدولی با ستونهای n ، n % 10 ، sum بعد از هر تکرار بسازید. توجه کنید چرا رقم صفر وسط عدد مشکلی ایجاد نمیکند.
تمرینهای پایانی زیربخش: while¶
★ سطح پایه
Predict the Output:
int i = 3;
while (i > 0) {
printf("%d ", i * i);
i--;
}Small Implementation:
برنامهای بنویسید که باwhileهمهی مضربهای ۳ از ۳ تا ۳۰ را چاپ کند.
★★ سطح متوسط
Find the Bug:
int i = 1;
while (i <= 5) {
printf("%d ", i);
}این حلقه چه رفتاری دارد و کدام بخش از چهار بخش آناتومی حلقه فراموش شده است؟
Small Implementation:
برنامهای بنویسید که عدد صحیح مثبتnرا بگیرد و معکوس آن را چاپ کند (مثلاً1234←4321). (راهنمایی:rev = rev * 10 + n % 10.)Trace:
برای ورودیهای5 -2 8 -1در الگوریتم میانگین با Sentinel، مقدارcountوsumرا بعد از هر تکرار بنویسید. آیا عدد منفی-2هم جزو دادهها حساب میشود؟ این رفتار مطلوب است؟
★★★ سطح چالشی
Design:
الگوریتمی بنویسید که تعداد دفعاتی که عددnرا میتوان بر ۲ تقسیم صحیح کرد تا به ۱ برسد (یعنی⌊log₂ n⌋) را بشمارد. برایn = 1000وn = 1تست کنید.Explain Why:
چرا در حلقهی جمع ارقام، متغیرnتغییر میکند و ما مقدار اصلی را درoriginalکپی کردهایم؟ اگر کپی نمیکردیم چه مشکلی پیش میآمد؟
9.3 حلقهی do-while¶
ایده الگوریتم¶
گاهی بدنه باید حداقل یکبار اجرا شود و فقط بعد از آن بپرسیم آیا ادامه بدهیم. مثال کلاسیک: گرفتن ورودی معتبر از کاربر. قبل از اینکه بتوانیم «معتبر بودن» را بسنجیم، باید یک مقدار گرفته باشیم. do-while شرط را بعد از هر تکرار بررسی میکند (Post-test Loop).
Flowchart¶
Example A - Simple: رفع باگ شمارش ارقام¶
%%writefile src/p04_c09_06_do_while_digits.c
#include <stdio.h>
int main(void)
{
int n;
if (scanf("%d", &n) != 1 || n < 0) {
return 1;
}
int original = n;
int count = 0;
do {
count++;
n /= 10;
} while (n > 0);
printf("%d has %d digit(s)\n", original, count);
return 0;
}
Writing src/p04_c09_06_do_while_digits.c
%%bash
gcc -Wall -o bin/p04_c09_06_do_while_digits src/p04_c09_06_do_while_digits.c || exit 1
echo "0" | ./bin/p04_c09_06_do_while_digits
echo "7" | ./bin/p04_c09_06_do_while_digits
echo "472" | ./bin/p04_c09_06_do_while_digits
echo "1000" | ./bin/p04_c09_06_do_while_digits0 has 1 digit(s)
7 has 1 digit(s)
472 has 3 digit(s)
1000 has 4 digit(s)
حالا 0 یک رقم دارد (درست). دلیل: بدنه حتماً یکبار اجرا میشود (count = 1)، و بعد n که صفر شده شرط را نادرست میکند. بقیهی ورودیها هم مثل قبل درستاند. این نمونه نشان میدهد انتخاب نوع حلقه فقط سلیقه نیست؛ گاهی درستی الگوریتم را تعیین میکند.
Example B - Real: اعتبارسنجی با تکرار تا ورودی معتبر¶
%%writefile src/p04_c09_07_do_while_validation.c
#include <stdio.h>
int main(void)
{
int s;
do {
printf("Enter score (0-20): ");
if (scanf("%d", &s) != 1) {
printf("\nNo more input\n");
return 1;
}
if (s < 0 || s > 20) {
printf("Invalid: %d\n", s);
}
} while (s < 0 || s > 20);
printf("Accepted: %d\n", s);
return 0;
}
Writing src/p04_c09_07_do_while_validation.c
%%bash
gcc -Wall -o bin/p04_c09_07_do_while_validation src/p04_c09_07_do_while_validation.c || exit 1
echo "25 -3 17" | ./bin/p04_c09_07_do_while_validation
echo "12" | ./bin/p04_c09_07_do_while_validation
echo "99" | ./bin/p04_c09_07_do_while_validation || trueEnter score (0-20): Invalid: 25
Enter score (0-20): Invalid: -3
Enter score (0-20): Accepted: 17
Enter score (0-20): Accepted: 12
Enter score (0-20): Invalid: 99
Enter score (0-20):
No more input
الگوی «بخوان ← بررسی کن ← اگر نامعتبر بود تکرار کن» دقیقاً شکل do-while است. با while باید قبل از حلقه یک بار ورودی را میخواندیم (و یک بار هم داخل آن)، یعنی کد خواندن دو جا تکرار میشد. نکتهی احتیاط: اگر ورودی به پایان برسد (scanf != 1)، حلقه بهدلیل نبود داده تا ابد تکرار میشد؛ پس این حالت جدا مدیریت شده است (ورودی سوم، 99 فقط یک مقدار نامعتبر دارد و بعد ورودی تمام میشود).
مقایسهی while و do-while¶
| معیار | while | do-while |
|---|---|---|
| زمان بررسی شرط | قبل از بدنه | بعد از بدنه |
| حداقل تعداد اجرای بدنه | صفر | یک |
| مناسب برای | دادهای که ممکن است خالی باشد | «یکبار انجام بده، بعد بسنج» (ورودی، منو) |
| نقطهویرگول | ندارد | بعد از while(...) الزامی است |
تمرین درون فصل ۹.۳¶
نوع تمرین: Predict the Output
int i = 10;
do {
printf("%d ", i);
i++;
} while (i < 5);خروجی چیست؟ اگر همین را با while بنویسیم خروجی چه میشود؟
تمرینهای پایانی زیربخش: do-while¶
★ سطح پایه
Predict the Output: برنامهی بالا (در تمرین درونفصل) را برای
i = 1دوباره پیشبینی کنید.Small Implementation:
برنامهای بنویسید که باdo-whileعددی را بخواند تا زمانی که مثبت باشد.
★★ سطح متوسط
Find the Bug:
do {
scanf("%d", &x);
} while (x < 0)
printf("ok\n");این کد چرا کامپایل نمیشود؟
Choose the Algorithm:
برای هر مورد مشخص کنیدwhileبهتر است یاdo-while: (الف) خواندن اعداد تا رسیدن به پایان فایل، (ب) نمایش منو و گرفتن انتخاب، (ج) شمارش ارقام یک عدد.
★★★ سطح چالشی
Design:
یک بازی «حدس عدد» طراحی کنید: عدد مخفی ثابت (مثلاً ۴۲) است و برنامه تا وقتی حدسها (از ورودی) غلطاند «Higher» یا «Lower» چاپ میکند و در پایان تعداد حدسها را نشان میدهد.
9.4 حلقهی for¶
ایده الگوریتم¶
در بسیاری از حلقهها، چهار بخش آناتومی (مقداردهی، شرط، بدنه، بهروزرسانی) به یک شمارنده مربوطاند. for این سه بخش (بهجز بدنه) را در یک خط کنار هم مینویسد تا نگاه یکجا به «محدودهی حلقه» ممکن شود:
for (مقداردهی ; شرط ; بهروزرسانی) {
بدنه
}Flowchart¶
ترتیب اجرا بسیار مهم است: مقداردهی (۱ بار) ← شرط ← بدنه ← بهروزرسانی ← شرط ← بدنه ← ... ← شرط (نادرست) ← خروج. بهروزرسانی بعد از بدنه اجرا میشود، با اینکه در خط اول نوشته شده است:
code_f = ["for (i = 0; i < 3; i++) {",
" printf(\"%d \", i);",
"}"]
LG_FOR = [["cur", "i فعلی"], ["vis", "تکرار انجامشده"], ["min", "شرط نادرست شد"], ["i", "هنوز نرسیدهایم"]]
r = Rec("for loop: the real order of execution", code_f, [0, 1, 2, 3], LG_FOR, labels=["i=0", "i=1", "i=2", "i=3"])
r.var(i="—"); r.echo("")
r.at(1, "سه بخش داخل پرانتز <code dir='ltr'>for</code> به ترتیب خاصی اجرا میشوند: مقداردهی، شرط، (بدنه)، بهروزرسانی.")
r.var(i=0); r.mark(0, "cur"); r.ptr(i=0)
r.at(1, f"① <b>مقداردهی</b>: {_c('i = 0')}. این بخش فقط یکبار و در ابتدای کار اجرا میشود.")
for i in range(3):
r.at(1, f"② <b>شرط</b>: {_c(f'{i} < 3')} درست است، پس بدنه اجرا میشود.")
r.echo(f"{i} ")
r.at(2, f"③ <b>بدنه</b>: مقدار {_c(i)} چاپ میشود.")
r.mark(i, "vis"); r.mark(i + 1, "cur"); r.ptr(i=i + 1); r.var(i=i + 1)
r.at(1, f"④ <b>بهروزرسانی</b>: {_c('i++')} ← {_c('i')} میشود {_c(i + 1)}. توجه کنید این بخش بعد از بدنه اجرا میشود، هرچند در خط اول نوشته شده است.")
r.mark(3, "min")
r.at(1, f"② <b>شرط</b>: {_c('3 < 3')} نادرست است؛ از حلقه خارج میشویم. بدنه ۳ بار اجرا شد، اما شرط ۴ بار بررسی شد.")
display(r.show())
Example A - Simple: سه الگوی رایج شمارش¶
%%writefile src/p04_c09_08_for_basic.c
#include <stdio.h>
int main(void)
{
printf("Up: ");
for (int i = 1; i <= 5; i++) {
printf("%d ", i);
}
printf("\nDown: ");
for (int i = 5; i >= 1; i--) {
printf("%d ", i);
}
printf("\nStep 2: ");
for (int i = 0; i <= 10; i += 2) {
printf("%d ", i);
}
printf("\nTwo variables: ");
for (int lo = 0, hi = 6; lo < hi; lo++, hi--) {
printf("(%d,%d) ", lo, hi);
}
printf("\n");
return 0;
}
Writing src/p04_c09_08_for_basic.c
!gcc -Wall -o bin/p04_c09_08_for_basic src/p04_c09_08_for_basic.c && ./bin/p04_c09_08_for_basicUp: 1 2 3 4 5
Down: 5 4 3 2 1
Step 2: 0 2 4 6 8 10
Two variables: (0,6) (1,5) (2,4)
چرا int i داخل پرانتز for تعریف شده است؟
از C99 به بعد میتوان متغیر شمارنده را داخل خود for تعریف کرد. دامنهی چنین متغیری فقط همان حلقه است؛ یعنی بیرون از حلقه وجود ندارد و نمیتوان از آن اشتباهاً استفاده کرد. همین کار باعث میشود در سه حلقهی پشتسرهم بتوانیم هر بار نام i را استفاده کنیم.
چه چیز در حلقهی دوم متفاوت است؟
هر سه بخش عوض شدهاند: شروع از ۵، شرط >= 1 و بهروزرسانی i--. جهت شرط باید با جهت بهروزرسانی هماهنگ باشد؛ اگر در حلقهی شمارش معکوس شرط i <= 5 را نگه دارید، همیشه درست میماند.
تعداد تکرارها: خطای یکیکمیکیزیاد (Off-by-One)¶
برای حلقهای که i را از a تا b با گام ۱ میشمارد:
اگر شرط
i <= bباشد (بازهی بسته): تعداد تکرارهاb - a + 1است.اگر شرط
i < bباشد (بازهی نیمهباز): تعداد تکرارهاb - aاست.
مثلاً for (i = 1; i <= 5; i++) پنج بار و for (i = 0; i < 5; i++) هم پنج بار اجرا میشود. بیشترین باگهای حلقه از اشتباه بین < و <= یا شروع از ۰ و ۱ میآید. عادت خوب: پیش از نوشتن حلقه، تعداد تکرار موردنیاز را بنویسید و با فرمول بالا چک کنید.
Example B - Real: فاکتوریل و محدودیت نوع داده¶
%%writefile src/p04_c09_09_for_factorial.c
#include <stdio.h>
int main(void)
{
unsigned int small = 1; /* 32-bit */
long long big = 1; /* 64-bit */
for (int n = 1; n <= 15; n++) {
small *= n;
big *= n;
if (n >= 11) {
printf("%2d! = %-12lld | 32-bit unsigned: %u\n", n, big, small);
}
}
return 0;
}
Writing src/p04_c09_09_for_factorial.c
!gcc -Wall -o bin/p04_c09_09_for_factorial src/p04_c09_09_for_factorial.c && ./bin/p04_c09_09_for_factorial11! = 39916800 | 32-bit unsigned: 39916800
12! = 479001600 | 32-bit unsigned: 479001600
13! = 6227020800 | 32-bit unsigned: 1932053504
14! = 87178291200 | 32-bit unsigned: 1278945280
15! = 1307674368000 | 32-bit unsigned: 2004310016
الگوریتم ضربهای متوالی از ابتدا تا انتها درست است، اما نوع داده ظرفیت محدودی دارد: از 13! به بعد مقدار ۳۲ بیتی با مقدار واقعی فاصله میگیرد (چون 13! = 6227020800 از ظرفیت ۳۲ بیت یعنی حدود ۴.۲۹ میلیارد بیشتر است و نتیجه «دور میزند»). نوع long long تا 20! درست کار میکند. درس مهم: درستی الگوریتم = درستی منطق + کافی بودن نوع داده. (برای ارقام علامتدار سرریز رفتار نامشخص دارد و از آن استفاده نکنید؛ در این مثال عمداً از unsigned استفاده شد که دور زدن آن تعریفشده است.)
Example C - Tricky: شمارندهی اعشاری¶
%%writefile src/p04_c09_10_float_loop.c
#include <stdio.h>
int main(void)
{
/* Danger: counting with a double and testing with != */
double x = 0.0;
int k = 0;
while (x != 1.0 && k < 12) { /* k < 12 is a safety cap for this demo */
x += 0.1;
k++;
}
printf("after %d additions: x = %.17f, x == 1.0 ? %d\n", k, x, x == 1.0);
/* Safer: count with an integer, derive the double from it */
int hits = 0;
for (int j = 0; j <= 10; j++) {
double y = j * 0.1;
if (y == 1.0) {
hits++;
}
}
printf("integer counter: reached 1.0 exactly %d time(s)\n", hits);
return 0;
}
Writing src/p04_c09_10_float_loop.c
!gcc -Wall -o bin/p04_c09_10_float_loop src/p04_c09_10_float_loop.c && ./bin/p04_c09_10_float_loopafter 12 additions: x = 1.19999999999999996, x == 1.0 ? 0
integer counter: reached 1.0 exactly 1 time(s)
با ده بار جمع 0.1 به مقداری میرسیم که کمی کمتر از 1.0 است؛ پس شرط x != 1.0 هرگز نادرست نمیشود و بدون سقف ایمنی، حلقه بینهایت میشد. قاعدهی عملی: شمارندهی حلقه را عدد صحیح بگیرید و مقدار اعشاری را از روی آن محاسبه کنید (y = j * 0.1)، یا برای حلقههای اعشاری از < و <= بهجای == و != استفاده کنید.
کدام حلقه؟ راهنمای انتخاب¶
| وضعیت | حلقهی مناسب |
|---|---|
| تعداد تکرار از قبل معلوم است (یا شمارنده داریم) | for |
| تعداد تکرار نامعلوم و بستگی به شرطی دارد؛ ممکن است صفر بار هم اجرا نشود | while |
| بدنه باید حداقل یکبار اجرا شود (ورودی، منو) | do-while |
هر سه حلقه از نظر قدرت محاسباتی همارزند؛ هر for را میتوان با while نوشت و بالعکس. تفاوتشان در صراحت نیت است: وقتی for میبینید، میدانید با یک شمارندهی مشخص سروکار دارید.
تمرین درون فصل ۹.۴¶
نوع تمرین: Complete the Code
حلقهی for زیر را با while بازنویسی کنید (چهار بخش آناتومی را مشخص کنید):
for (int i = 10; i > 0; i -= 3) {
printf("%d ", i);
}خروجی چیست و بدنه چند بار اجرا میشود؟ تعداد را با فرمول مناسب بنویسید.
تمرینهای پایانی زیربخش: for¶
★ سطح پایه
Small Implementation:
باforجدول مربعهای ۱ تا ۱۰ را چاپ کنید.Predict the Output:
for (int i = 0; i < 5; i += 2) {
printf("%d ", i);
}★★ سطح متوسط
Find the Bug:
int sum = 0;
for (int i = 1; i <= 10; i++);
{
sum += i;
}خطا (یا خطاها) را پیدا کنید. چرا این کد حتی ممکن است کامپایل نشود؟
Trace:
برایfor (int i = 1; i < 20; i *= 2)مقدارهایiو تعداد تکرارها را بنویسید. این حلقه از چه مرتبهای است (خطی یا لگاریتمی)؟Modify the Algorithm:
برنامهی فاکتوریل را طوری تغییر دهید که اگرnاز ۲۰ بیشتر بود، بهجای سرریز، پیام خطا چاپ کند.
★★★ سطح چالشی
Design:
مقدارe ≈ 1 + 1/1! + 1/2! + 1/3! + ...را تا ۱۰ جمله با یک حلقهیforحساب کنید، بدون اینکه هر بار فاکتوریل را از ابتدا بشمارید. (راهنمایی: از جملهی قبلی استفاده کنید.)Explain Why:
چرا درfor (unsigned i = 3; i >= 0; i--)حلقه بینهایت است؟ (راهنمایی: کوچکترین مقدارunsignedچیست؟)
9.5 الگوهای رایج حلقه (Loop Patterns)¶
اگر دهها برنامهی دارای حلقه را کنار هم بگذارید، متوجه میشوید اکثرشان از تعداد کمی الگوی تکرارشونده ساخته شدهاند. شناختن این الگوها از حفظ کردن سینتکس ارزشمندتر است، چون هر مسئلهی جدید را به یکی از آنها تبدیل میکند. در این بخش شش الگوی اصلی را میبینیم:
| الگو | پرسش اصلی | نمونه |
|---|---|---|
| Counter | چند مورد شرط را دارد؟ | تعداد مضربهای ۳ |
| Accumulator | مجموع (یا حاصلضرب) چیست؟ | جمع نمرات |
| Min / Max | کوچکترین یا بزرگترین کدام است؟ | بیشترین نمره |
| Search + Flag | آیا وجود دارد؟ اولین مورد کدام است؟ | عدد اول بودن |
| Sentinel | تا کی داده میآید؟ | ورودی تا -1 |
| Convergence | تا کی تکرار کنیم تا جواب به اندازهی کافی خوب شود؟ | ب.م.م، ریشهی دوم |
Pattern 1 & 2 - Counter و Accumulator¶
مسئله (مثال کلاسیک): مجموع و تعداد همهی اعداد کوچکتر از ۱۰۰۰ که مضرب ۳ یا ۵ هستند. الگو: بگذرد از همهی اعداد؛ برای هر عدد یک شرط بسنج؛ اگر برقرار بود، شمارنده را یکی بالا ببر و عدد را به جمع اضافه کن. دو متغیر کمکی (count و sum) را قبل از حلقه صفر میکنیم.
%%writefile src/p04_c09_11_pattern_counter_acc.c
#include <stdio.h>
int main(void)
{
int count = 0;
int sum = 0;
for (int i = 1; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0) {
count++;
sum += i;
}
}
printf("count = %d, sum = %d\n", count, sum);
return 0;
}
Writing src/p04_c09_11_pattern_counter_acc.c
!gcc -Wall -o bin/p04_c09_11_pattern_counter_acc src/p04_c09_11_pattern_counter_acc.c && ./bin/p04_c09_11_pattern_counter_acccount = 466, sum = 233168
چرا شرط i % 3 == 0 || i % 5 == 0 را با || نوشتهایم و دو if جدا نگذاشتهایم؟
اگر دو if مستقل میگذاشتیم، اعداد مضرب ۱۵ (مثل ۱۵ و ۳۰) دو بار شمرده میشدند. || هر عدد را فقط یکبار بررسی میکند. این همان تمایز «شرطهای مستقل» در فصل قبل است، این بار در نقش یک اشتباه رایج.
چرا حلقه تا i < 1000 میرود، نه i <= 1000؟
چون صورت مسئله «کوچکتر از ۱۰۰۰» را میگوید. اگر <= میگذاشتیم، ۱۰۰۰ (که مضرب ۵ است) هم اضافه میشد. نوع مرز در صورت مسئله مستقیماً تعیینکنندهی علامت شرط است.
Pattern 3 - Min / Max روی دنبالهی ورودی¶
اگر همهی دادهها را همزمان در حافظه نداشته باشیم (چون هنوز آرایه نمیشناسیم)، میتوانیم حین خواندن، «بهترین تا اینجا» را نگه داریم. نکتهی کلیدی: مقدار اولیهی max و min را با اولین دادهی واقعی بسازیم، نه با یک عدد دلخواه مثل 0؛ در غیر این صورت، اگر همهی دادهها منفی باشند، نتیجه غلط میشود.
Pseudocode¶
count ← 0
for each value x in the input:
if count = 0: min ← x, max ← x // first value initialises both
else:
if x < min: min ← x
if x > max: max ← x
count ← count + 1%%writefile src/p04_c09_12_pattern_minmax.c
#include <stdio.h>
int main(void)
{
int x, min = 0, max = 0, count = 0;
while (scanf("%d", &x) == 1) {
if (count == 0) {
min = x;
max = x;
} else {
if (x < min) {
min = x;
}
if (x > max) {
max = x;
}
}
count++;
}
if (count == 0) {
printf("No data\n");
} else {
printf("count = %d, min = %d, max = %d\n", count, min, max);
}
return 0;
}
Writing src/p04_c09_12_pattern_minmax.c
%%bash
gcc -Wall -o bin/p04_c09_12_pattern_minmax src/p04_c09_12_pattern_minmax.c || exit 1
echo "7 -3 12 0 9" | ./bin/p04_c09_12_pattern_minmax
echo "5" | ./bin/p04_c09_12_pattern_minmax
echo "-8 -2 -15" | ./bin/p04_c09_12_pattern_minmax
echo "" | ./bin/p04_c09_12_pattern_minmaxcount = 5, min = -3, max = 12
count = 1, min = 5, max = 5
count = 3, min = -15, max = -2
No data
چهار ورودی چهار مسیر متفاوت را آزمایش میکنند: حالت عادی، تکعنصری (کوچکترین و بزرگترین یکیاند)، همه منفی (اگر max را با 0 شروع میکردیم، 0 بهاشتباه بیشترین میشد) و ورودی خالی (باید «No data» چاپ شود، نه مقدار بیمعنی).
Pattern 4 - Search + Flag: آیا عدد n اول است؟¶
عدد اول، عددی بزرگتر از ۱ است که فقط بر ۱ و خودش بخشپذیر است. الگوریتم: برای d از ۲ به بعد، ببین آیا n بر d بخشپذیر است؛ اگر حتی یک مقسومعلیه پیدا شد، جواب «اول نیست» است و دیگر ادامه دادن بیمعنی است. این همان الگوی جستجو با پرچم: یک متغیر is_prime با فرض اولیهی «اول است» و در صورت یافتن شاهد مخالف، تغییر میکند و حلقه با break متوقف میشود.
بهبود الگوریتمی مهم: اگر n = a × b باشد، دستکم یکی از a و b از √n بیشتر نیست. پس کافی است d را فقط تا √n بررسی کنیم (شرط d * d <= n). این کار تعداد گامها را از حدود n به حدود √n کاهش میدهد.
Pseudocode¶
if n < 2: return NOT PRIME
is_prime ← TRUE
for d from 2 while d × d ≤ n:
if n mod d = 0:
is_prime ← FALSE
break
return is_prime%%writefile src/p04_c09_13_prime_check.c
#include <stdio.h>
int main(void)
{
int n;
if (scanf("%d", &n) != 1) {
return 1;
}
if (n < 2) {
printf("%d: not prime (must be at least 2)\n", n);
return 0;
}
/* Version 1: try every d from 2 to n-1 */
int prime_slow = 1, steps_slow = 0;
for (int d = 2; d < n; d++) {
steps_slow++;
if (n % d == 0) {
prime_slow = 0;
break;
}
}
/* Version 2: try d only while d*d <= n */
int prime_fast = 1, steps_fast = 0;
for (int d = 2; (long long)d * d <= n; d++) {
steps_fast++;
if (n % d == 0) {
prime_fast = 0;
break;
}
}
printf("%d: %s | steps: slow = %d, fast = %d%s\n", n,
prime_fast ? "prime" : "not prime", steps_slow, steps_fast,
prime_slow != prime_fast ? " MISMATCH!" : "");
return 0;
}
Writing src/p04_c09_13_prime_check.c
%%bash
gcc -Wall -o bin/p04_c09_13_prime_check src/p04_c09_13_prime_check.c || exit 1
echo "1" | ./bin/p04_c09_13_prime_check
echo "2" | ./bin/p04_c09_13_prime_check
echo "17" | ./bin/p04_c09_13_prime_check
echo "21" | ./bin/p04_c09_13_prime_check
echo "97" | ./bin/p04_c09_13_prime_check
echo "1000003" | ./bin/p04_c09_13_prime_check1: not prime (must be at least 2)
2: prime | steps: slow = 0, fast = 0
17: prime | steps: slow = 15, fast = 3
21: not prime | steps: slow = 2, fast = 2
97: prime | steps: slow = 95, fast = 8
1000003: prime | steps: slow = 1000001, fast = 999
چرا برای 21 هر دو نسخه خیلی سریع تمام میشوند؟
چون 21 = 3 × 7 و در گام دوم (d = 3) مقسومعلیه پیدا شده و break حلقه را قطع کرده است. حلقه فقط در بدترین حالت تا آخر میرود، و بدترین حالت برای این الگوریتم همان اعداد اول هستند (هیچ شاهدی پیدا نمیشود).
چرا برای 2 و 3 نسخهی سریع هیچ گامی برنمیدارد؟
برای n = 2 شرط 2 × 2 <= 2 از همان ابتدا نادرست است؛ حلقه اجرا نمیشود و is_prime همان مقدار اولیهی 1 میماند، که درست است. حالت مرزی بدون کد اضافه حل شده است.
چرا (long long)d * d نوشته شده است؟
برای n های بزرگ (نزدیک به حد int)، d * d میتواند از ظرفیت int بگذرد. تبدیل به long long از سرریز جلوگیری میکند.
تفاوت دو نسخه را برای 1000003 ببینید: نسخهی کند حدود یک میلیون گام برمیدارد و نسخهی سریع حدود هزار. این تفاوت تفاوت مرتبهی رشد است: O(n) در برابر O(√n).
import math
def next_prime(m):
while True:
if m > 1 and all(m % d for d in range(2, math.isqrt(m) + 1)):
return m
m += 1
rows = []
for t in [100, 1000, 10000, 100000, 1000000]:
p = next_prime(t)
slow, fast = p - 2, math.isqrt(p) - 1
rows.append(dict(name=f"n = {p}", sub="عدد اول؛ بدترین حالت",
metrics=[("d = 2 … n-1 O(n)", slow, slow), ("d·d ≤ n O(√n)", fast, slow)]))
display(fig_bars("Primality test: number of loop iterations", rows,
"طول هر نوار نسبت به نسخهی کند همان ردیف سنجیده شده است. هرچه n بزرگتر شود، نسخهی √n نسبتاً کوچکتر میشود: برای حدود یک میلیون، فقط حدود <code dir='ltr'>1000</code> گام بهجای <code dir='ltr'>1000000</code> گام."))
Pattern 6 - Convergence: الگوریتم اقلیدس (ب.م.م)¶
بزرگترین مقسومعلیه مشترک (gcd) دو عدد، قدیمیترین الگوریتم مشهور تاریخ است (حدود ۳۰۰ سال پیش از میلاد). ایده: gcd(a, b) = gcd(b, a mod b)؛ یعنی مسئله را هر بار به یک مسئلهی کوچکتر با همان جواب تبدیل میکنیم تا به حالت b = 0 برسیم که در آن جواب همان a است. این یک حلقهی همگرا است: شرط ادامه b != 0 است و هر تکرار b را اکیداً کوچکتر میکند (چون a mod b < b) ؛ پس تمام شدن حلقه تضمینشده است.
%%writefile src/p04_c09_14_euclid_gcd.c
#include <stdio.h>
int main(void)
{
int a, b;
if (scanf("%d %d", &a, &b) != 2 || a < 0 || b < 0) {
printf("Please enter two non-negative integers\n");
return 1;
}
int x = a, y = b, steps = 0;
while (y != 0) {
int r = x % y;
x = y;
y = r;
steps++;
}
printf("gcd(%d, %d) = %d (%d step(s))\n", a, b, x, steps);
return 0;
}
Writing src/p04_c09_14_euclid_gcd.c
%%bash
gcc -Wall -o bin/p04_c09_14_euclid_gcd src/p04_c09_14_euclid_gcd.c || exit 1
echo "48 18" | ./bin/p04_c09_14_euclid_gcd
echo "17 5" | ./bin/p04_c09_14_euclid_gcd
echo "100 0" | ./bin/p04_c09_14_euclid_gcd
echo "0 7" | ./bin/p04_c09_14_euclid_gcd
echo "270 192" | ./bin/p04_c09_14_euclid_gcd
echo "13 13" | ./bin/p04_c09_14_euclid_gcdgcd(48, 18) = 6 (3 step(s))
gcd(17, 5) = 1 (3 step(s))
gcd(100, 0) = 100 (0 step(s))
gcd(0, 7) = 7 (1 step(s))
gcd(270, 192) = 6 (4 step(s))
gcd(13, 13) = 13 (1 step(s))
code_e = ["while (b != 0) {",
" r = a % b;",
" a = b;",
" b = r;",
"}",
"printf(\"%d\", a);"]
LG_EU = [["cmp", "a (مقسوم)"], ["key", "b (مقسومعلیه)"], ["ok", "باقیماندهی جدید"], ["vis", "دیگر استفاده نمیشود"], ["i", "هنوز محاسبه نشده"]]
chain = [48, 18]
while chain[-1] != 0:
chain.append(chain[-2] % chain[-1])
r = Rec("Euclid's algorithm: gcd(48, 18)", code_e, chain, LG_EU,
labels=["a0", "b0", "r1", "r2", "r3"][:len(chain)])
known = 2
def vals(): return [str(chain[i]) if i < known else "?" for i in range(len(chain))]
a, b = 48, 18
r.var(a=a, b=b, r="—"); r.mark({0: "cmp", 1: "key"}); r.ptr(a=0, b=1)
r.at(1, f"شروع با {_c('a = 48')} و {_c('b = 18')}. فقط این دو مقدار را میدانیم؛ هر باقیماندهی بعدی را حلقه خواهد ساخت.", vals=vals())
k = 0
while b != 0:
r.at(1, f"{_c('b != 0')} ← {_c(f'{b} != 0')} درست است؛ وارد بدنه میشویم.", vals=vals())
rem = a % b; known += 1; r.var(r=rem); r.mark(k + 2, "ok")
r.at(2, f"{_c('r = a % b')} ← {_c(f'{a} % {b}')} = {_c(rem)}. باقیمانده همیشه از {_c('b')} کوچکتر است؛ پس دنبالهی ما اکیداً نزولی است.", vals=vals())
a = b; r.var(a=a); r.mark(k, "vis"); r.mark(k + 1, "cmp"); r.ptr(a=k + 1)
r.at(3, f"{_c('a = b')} ← مقسوم قبلی دور ریخته میشود و {_c('a')} میشود {_c(a)}.", vals=vals())
b = rem; r.var(b=b); r.mark(k + 2, "key"); r.ptr(b=k + 2)
r.at(4, f"{_c('b = r')} ← {_c('b')} میشود {_c(b)}.", vals=vals())
k += 1
r.at(1, f"{_c('b != 0')} ← {_c('0 != 0')} نادرست است؛ حلقه تمام شد. آخرین مقدار {_c('a')} همان ب.م.م است.", vals=vals())
r.echo(str(a)); r.mark(k, "ok")
r.at(6, f"{_c('printf')} ← gcd(48, 18) = {_c(a)}. ({k} بار بدنه اجرا شد.)", vals=vals())
display(r.show())
چرا ورودی 100 0 جواب 100 میدهد؟
چون b = 0 از همان ابتدا شرط حلقه را نادرست میکند و a (یعنی ۱۰۰) بهعنوان جواب بازمیگردد؛ و این از نظر ریاضی هم درست است (هر عدد، مقسومعلیه ۰ است). همچنین 0 7 در یک گام (a = 7, b = 0) به همان 7 میرسد: اگر a < b باشد، اولین تکرار فقط جای دو عدد را عوض میکند.
از کجا بدانیم حلقه حتماً تمام میشود؟
باید یک کمیت نزولی پیدا کنیم که در هر تکرار اکیداً کم شود و هرگز از صفر پایینتر نرود؛ این اثبات پایانپذیری حلقه است. اینجا b چنین کمیتی است. هر حلقهای که چنین کمیتی نداشته باشد، «شاید» تمام نشود.
Pattern 6b - Convergence: ریشهی دوم با روش نیوتن¶
گاهی جواب دقیق نداریم و فقط میتوانیم «هر بار بهتر» شویم. برای √x تقریب اولیه g را میگیریم و آن را با g = (g + x / g) / 2 بهبود میدهیم. حلقه تا وقتی ادامه دارد که خطا از یک تلورانس کوچک بیشتر باشد. توجه کنید شرط توقف «برابر شدن» نیست (در اعداد اعشاری نمیتوان به آن اعتماد کرد)، بلکه «به اندازهی کافی نزدیک شدن» است.
%%writefile src/p04_c09_15_newton_sqrt.c
#include <stdio.h>
int main(void)
{
double x = 2.0;
double g = x; /* initial guess */
double eps = 1e-9;
int steps = 0;
double err = g * g - x;
err = (err < 0) ? -err : err; /* absolute value via ?: */
while (err > eps && steps < 50) { /* 50 = safety cap */
g = (g + x / g) / 2.0;
err = g * g - x;
err = (err < 0) ? -err : err;
steps++;
printf("step %d: g = %.10f, error = %.3e\n", steps, g, err);
}
printf("sqrt(%.1f) ~ %.10f after %d step(s)\n", x, g, steps);
return 0;
}
Writing src/p04_c09_15_newton_sqrt.c
!gcc -Wall -o bin/p04_c09_15_newton_sqrt src/p04_c09_15_newton_sqrt.c && ./bin/p04_c09_15_newton_sqrtstep 1: g = 1.5000000000, error = 2.500e-01
step 2: g = 1.4166666667, error = 6.944e-03
step 3: g = 1.4142156863, error = 6.007e-06
step 4: g = 1.4142135624, error = 4.511e-12
sqrt(2.0) ~ 1.4142135624 after 4 step(s)
خطا در هر گام تقریباً مجذور میشود (به همین دلیل از «۱.۴» به «۱.۴۱۴۲۱۳۵» بسیار سریع میرسیم): در کمتر از ۱۰ گام به دقت بالا میرسیم. سقف steps < 50 یک شبکهی ایمنی است؛ هر حلقهای که به «همگرایی» تکیه دارد، بهتر است سقف تکرار هم داشته باشد تا اگر مسئله شرطهای روش را نقض کرد، برنامه برای همیشه نایستد.
Example - Tricky: حلقهای که نمیدانیم حتماً تمام میشود (Collatz)¶
الگوریتم: عدد n را بگیر؛ تا وقتی n != 1 است، اگر زوج بود نصفش کن، وگرنه 3n + 1 کن. حدس معروف Collatz میگوید این حلقه برای هر عدد مثبتی تمام میشود، اما هنوز ثابت نشده است! این مثال نشان میدهد چرا «کمیت نزولی» در حلقهها چنین اهمیتی دارد: در اینجا چنین کمیتی نمیشناسیم.
%%writefile src/p04_c09_16_collatz.c
#include <stdio.h>
int main(void)
{
int start;
if (scanf("%d", &start) != 1 || start < 1) {
return 1;
}
long long n = start;
long long peak = n;
int steps = 0;
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n = 3 * n + 1;
}
if (n > peak) {
peak = n;
}
steps++;
}
printf("start = %d: %d step(s), peak value = %lld\n", start, steps, peak);
return 0;
}
Writing src/p04_c09_16_collatz.c
%%bash
gcc -Wall -o bin/p04_c09_16_collatz src/p04_c09_16_collatz.c || exit 1
echo "1" | ./bin/p04_c09_16_collatz
echo "6" | ./bin/p04_c09_16_collatz
echo "27" | ./bin/p04_c09_16_collatz
echo "97" | ./bin/p04_c09_16_collatzstart = 1: 0 step(s), peak value = 1
start = 6: 8 step(s), peak value = 16
start = 27: 111 step(s), peak value = 9232
start = 97: 118 step(s), peak value = 9232
seq = [27]
while seq[-1] != 1:
n = seq[-1]
seq.append(n // 2 if n % 2 == 0 else 3 * n + 1)
pts = [(i, seq[i]) for i in range(0, len(seq), 10)]
if pts[-1][0] != len(seq) - 1:
pts.append((len(seq) - 1, seq[-1]))
display(fig_line("Collatz trajectory of 27", pts, "step", "value", 10000, [0, 2500, 5000, 7500, 10000],
f"عدد ۲۷ پس از <code dir='ltr'>{len(seq) - 1}</code> گام به ۱ میرسد و در میانهی راه تا <code dir='ltr'>{max(seq)}</code> بالا میرود: حلقهای که نمیتوانیم از روی «کوچک شدن مقدار» پایان آن را تضمین کنیم."))
تمرین درون فصل ۹.۵¶
نوع تمرین: Trace
الگوریتم اقلیدس را برای a = 84 و b = 36 دستی دنبال کنید و جدولی با ستونهای a ، b ، r بسازید. در چه گامی b صفر میشود و جواب چیست؟
تمرین درون فصل ۹.۶ : چرا max را با اولین داده شروع میکنیم؟¶
نوع تمرین: Explain Why
اگر در الگوریتم Min/Max مقدار اولیهی max را صفر بگیریم و ورودی -8 -2 -15 باشد، نتیجه چه میشود؟ یک مقدار اولیهی دیگر پیشنهاد دهید که بدون استفاده از اولین داده هم درست باشد و بگویید چرا آن معمولاً ایدهی بدی است (راهنمایی: INT_MIN در limits.h).
تمرینهای پایانی زیربخش: الگوهای حلقه¶
★ سطح پایه
Small Implementation (Counter):
تعداد اعداد زوج بین ۱ تا ۱۰۰ را بشمارید.Small Implementation (Accumulator):
حاصلضرب اعداد فرد از ۱ تا ۹ را با یک حلقه حساب کنید.
★★ سطح متوسط
Find the Bug:
int max = 0, x;
while (scanf("%d", &x) == 1) {
if (x > max) max = x;
}کد برای کدام ورودیها جواب غلط میدهد؟
Modify the Algorithm:
الگوریتم عدد اول را طوری تغییر دهید که علاوه بر «اول است یا نه»، کوچکترین مقسومعلیه را هم چاپ کند.Small Implementation:
با الگوی Counter، تعداد ارقام زوج یک عدد را بشمارید (مثلاً2846← ۴).Design:
با استفاده از gcd، کوچکترین مضرب مشترک (lcm) دو عدد را با فرمولlcm = a / gcd * bحساب کنید. چرا ابتدا تقسیم و بعد ضرب بهتر ازa * b / gcdاست؟
★★★ سطح چالشی
Algorithm Design:
تعداد جفتهای(i, j)با1 ≤ i < j ≤ 20را پیدا کنید کهgcd(i, j) = 1باشد. (مجبور به استفاده از حلقهی تودرتو هستید؛ بخش بعد را ببینید.)Complexity Reasoning:
در الگوریتم عدد اول با√n، برایn = 10^12چند تکرار لازم است؟ آیا این در یک ثانیه قابل اجراست؟ با نسخهی کند مقایسه کنید.
9.6 حلقههای تودرتو (Nested Loops)¶
ایده الگوریتم¶
بسیاری از دادهها و مسئلهها ذاتاً «دوبعدی» هستند: جدول ضرب (سطر × ستون)، جفتهای ممکن بین دو مجموعه، الگوهای تصویری. برای اینها یک حلقه کافی نیست. وقتی یک حلقه را داخل بدنهی حلقهی دیگر میگذاریم، حلقهی داخلی برای هر تکرار حلقهی بیرونی، یکبار کامل اجرا میشود. تشبیه خوب: عقربهی ساعتشمار و دقیقهشمار؛ دقیقهشمار برای هر قدم ساعتشمار یک دور کامل میچرخد.
Pseudocode¶
for i from 1 to n: // outer: runs n times
for j from 1 to m: // inner: runs m times, FOR EACH i
body
// body runs n × m times in totalExample A - Simple: الگوهای ستارهای¶
%%writefile src/p04_c09_17_nested_patterns.c
#include <stdio.h>
int main(void)
{
int n = 4;
printf("Rectangle (3 x 5):\n");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 5; j++) {
printf("*");
}
printf("\n");
}
printf("\nRight triangle (n = %d):\n", n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
printf("*");
}
printf("\n");
}
printf("\nPyramid (n = %d):\n", n);
for (int i = 1; i <= n; i++) {
for (int s = 0; s < n - i; s++) {
printf(" ");
}
for (int j = 0; j < 2 * i - 1; j++) {
printf("*");
}
printf("\n");
}
return 0;
}
Writing src/p04_c09_17_nested_patterns.c
!gcc -Wall -o bin/p04_c09_17_nested_patterns src/p04_c09_17_nested_patterns.c && ./bin/p04_c09_17_nested_patternsRectangle (3 x 5):
*****
*****
*****
Right triangle (n = 4):
*
**
***
****
Pyramid (n = 4):
*
***
*****
*******
الگوی ذهنی: **حلقهی بیرونی «سطرها» و حلقهی داخلی «ستونها» را تعیین میکند؛ و printf("\n") بعد از پایان حلقهی داخلی (و نه داخل آن) سطر را میبندد. در مستطیل، تعداد ستون ثابت است؛ در مثلث، شرط حلقهی داخلی به متغیر بیرونی وابسته است** (j <= i)، و همین وابستگی شکل را تعیین میکند. در هرم، برای هر سطر سه کار انجام میدهیم: فاصله، ستاره، خط جدید، و تعداد ستاره از فرمول 2i - 1 میآید.
code_tri = ["for (int i = 1; i <= 4; i++) {",
" for (int j = 1; j <= i; j++) {",
" printf(\"*\");",
" }",
" printf(\"\\n\");",
"}"]
LG_GRID = [["cur", "تکرار جاری"], ["vis", "ستاره چاپ شد"], ["dim", "خارج از j ≤ i"], ["i", "هنوز نرسیدهایم"]]
R = 4
r = Rec("Nested loops: right triangle (n = 4)", code_tri, ["·"] * (R * R), LG_GRID,
grid=dict(r=R, c=R, rl=[f"i={x}" for x in range(1, R + 1)], cl=[f"j={x}" for x in range(1, R + 1)]),
interval=700)
shown = ["·"] * (R * R)
count = 0
r.var(i="—", j="—", iterations=0)
r.at(1, f"شبکهی ۴×۴ را در نظر بگیرید: سطر ← حلقهی بیرونی ({_c('i')}) و ستون ← حلقهی داخلی ({_c('j')}). فقط خانههایی که {_c('j <= i')} هستند ستاره میگیرند.", vals=shown)
for i in range(1, R + 1):
for j in range(i + 1, R + 1):
r.mark((i - 1) * R + (j - 1), "dim")
r.var(i=i, j="—")
r.at(2, f"حلقهی بیرونی: {_c(f'i = {i}')}. حلقهی داخلی برای این سطر از {_c('j = 1')} تا {_c(f'j = {i}')} (یعنی {i} بار) اجرا میشود.", row=i - 1, vals=shown)
for j in range(1, i + 1):
idx = (i - 1) * R + (j - 1)
count += 1
r.mark(idx, "cur"); shown[idx] = "*"; r.var(j=j, iterations=count); r.echo("*")
r.at(3, f"{_c(f'i = {i}, j = {j}')}: شرط {_c(f'j <= i')} درست است و یک ستاره چاپ میشود. تعداد کل تکرارهای بدنه تا الان: {_c(count)}.", row=i - 1, col=j - 1, vals=shown)
r.mark(idx, "vis")
r.echo("\n")
r.at(5, f"{_c(f'j = {i + 1}')} شرط حلقهی داخلی را نادرست کرد. {_c('printf(\"\\\\n\")')} خط را میبندد (بیرون از حلقهی داخلی) و {_c('i++')} اجرا میشود.", row=i - 1, vals=shown)
r.at(6, f"پایان: بدنهی درونی در مجموع {_c(count)} بار اجرا شد؛ یعنی {_c('1 + 2 + 3 + 4 = 10')}، نه {_c('4 × 4 = 16')}.", vals=shown)
display(r.show())
Example B - Real: جدول ضرب¶
%%writefile src/p04_c09_18_mult_table.c
#include <stdio.h>
int main(void)
{
printf(" ");
for (int j = 1; j <= 5; j++) {
printf("%4d", j);
}
printf("\n");
for (int i = 1; i <= 5; i++) {
printf("%4d", i);
for (int j = 1; j <= 5; j++) {
printf("%4d", i * j);
}
printf("\n");
}
return 0;
}
Writing src/p04_c09_18_mult_table.c
!gcc -Wall -o bin/p04_c09_18_mult_table src/p04_c09_18_mult_table.c && ./bin/p04_c09_18_mult_table 1 2 3 4 5
1 1 2 3 4 5
2 2 4 6 8 10
3 3 6 9 12 15
4 4 8 12 16 20
5 5 10 15 20 25
Example C - Real: همهی اعداد اول تا ۵۰ (حلقهی تودرتو + break)¶
%%writefile src/p04_c09_19_nested_primes.c
#include <stdio.h>
int main(void)
{
for (int n = 2; n <= 50; n++) {
int prime = 1;
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) {
prime = 0;
break; /* leaves only the inner loop */
}
}
if (prime) {
printf("%d ", n);
}
}
printf("\n");
return 0;
}
Writing src/p04_c09_19_nested_primes.c
!gcc -Wall -o bin/p04_c09_19_nested_primes src/p04_c09_19_nested_primes.c && ./bin/p04_c09_19_nested_primes2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
حلقهی بیرونی همهی عددها را میپیماید و حلقهی داخلی برای هر کدام همان آزمون اول بودن را اجرا میکند. دقت کنید prime = 1 داخل حلقهی بیرونی مقداردهی میشود، چون هر عدد جدید باید از «فرض اول بودن» شروع کند. اگر آن را بیرون از حلقهی بیرونی میگذاشتیم، بعد از اولین عدد غیراول، همهی اعداد بعدی هم غیراول تلقی میشدند.
Complexity: هزینهی حلقهی تودرتو¶
%%writefile src/p04_c09_20_nested_count.c
#include <stdio.h>
int main(void)
{
int n = 10;
int square = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
square++;
}
}
int triangle = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
triangle++;
}
}
printf("n = %d\n", n);
printf("full square : %d iterations (n * n)\n", square);
printf("triangle j<=i : %d iterations (n(n+1)/2 = %d)\n", triangle, n * (n + 1) / 2);
return 0;
}
Writing src/p04_c09_20_nested_count.c
!gcc -Wall -o bin/p04_c09_20_nested_count src/p04_c09_20_nested_count.c && ./bin/p04_c09_20_nested_countn = 10
full square : 100 iterations (n * n)
triangle j<=i : 55 iterations (n(n+1)/2 = 55)
اگر حلقهی بیرونی n بار و حلقهی داخلی (مستقل از آن) m بار اجرا شود، کل اجرای بدنه n × m است. اگر حلقهی داخلی به متغیر بیرونی وابسته باشد (مثلث)، کل برابر مجموع 1 + 2 + ... + n = n(n+1)/2 میشود؛ که از نظر مرتبهی رشد هنوز O(n²) است (ثابت 1/2 در مرتبهی رشد بیاهمیت است). مهمترین نتیجه: **دو حلقهی تودرتو روی n عنصر، با دو برابر شدن n زمان را چهار برابر میکند.**
خطاهای رایج در حلقههای تودرتو¶
❌ اشتباه ۱: استفاده از یک شمارنده برای هر دو حلقه
for (int i = 0; i < 3; i++) {
for (i = 0; i < 3; i++) {
printf("*");
}
}چرا اشتباه است؟
حلقهی داخلی همان i بیرونی را دستکاری میکند: بعد از پایان داخلی، i برابر 3 است و حلقهی بیرونی هم تمام میشود؛ پس بهجای ۹ ستاره فقط ۳ ستاره چاپ میشود (و در حالتهای دیگر ممکن است حلقه بینهایت شود).
✅ نسخه صحیح: از j برای حلقهی داخلی استفاده کنید.
**❌ اشتباه ۲: break برای خروج از هر دو حلقه**
چرا اشتباه است؟
break فقط از نزدیکترین حلقهی دربرگیرنده خارج میشود. برای خروج از هر دو، به یک پرچم یا ساختاری دیگر نیاز داریم (در ۹.۹ میبینیم).
تمرین درون فصل ۹.۷¶
نوع تمرین: Predict the Output
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (i == j) printf("%d ", i);
}
}خروجی چیست؟ بدنهی printf در مجموع چند بار اجرا میشود و شرط i == j چند بار درست است؟
تمرینهای پایانی زیربخش: حلقههای تودرتو¶
★ سطح پایه
Small Implementation:
مربع توپُرn × nاز ستاره را چاپ کنید (nرا ثابت بگیرید).Trace:
برایn = 3در الگوی مثلث، ترتیب(i, j)ها را بنویسید و تعداد کل تکرار بدنه را بشمارید.
★★ سطح متوسط
Small Implementation:
مثلث «وارونه» (سطر اولnستاره، سطر آخر ۱ ستاره) را چاپ کنید.Modify the Algorithm:
جدول ضرب را طوری تغییر دهید که فقط نیمهی بالایی مثلث (j >= i) چاپ شود.Find the Bug:
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= i; j++) {
printf("*");
printf("\n");
}
}خروجی اشتباه چیست و printf("\n") را کجا باید گذاشت؟
★★★ سطح چالشی
Design:
الگوی «لوزی» (هرم و هرم وارونه زیر آن) را با حلقههای تودرتو چاپ کنید.Complexity Reasoning:
اگر برای هر جفت(i, j)با1 ≤ i < j ≤ nیک کار انجام شود، تعداد کل جفتها چقدر است؟ (راهنمایی:n(n-1)/2.) برایn = 1000چند میلیون جفت داریم؟Design:
همهی سهتاییهای فیثاغورسی(a, b, c)با1 ≤ a < b < c ≤ 50را با سه حلقهی تودرتو پیدا کنید. چگونه میتوان با حذف حلقهی سوم (محاسبهیcاز رویaوb) آن را سریعتر کرد؟
9.7 دستورهای break و continue¶
ایده الگوریتم¶
گاهی در میانهی یک تکرار میفهمیم باید رفتار حلقه را تغییر دهیم:
**
break**: «کار تمام شد؛ همین الان کل حلقه را ترک کن.» (مثلاً پاسخ را پیدا کردیم.)**
continue**: «این تکرار را رها کن و برو به تکرار بعدی.» (مثلاً این مورد مشمول پردازش نیست.)
تفاوت کلیدی: break کل حلقه را قطع میکند و continue فقط این دور را. هر دو فقط روی نزدیکترین حلقهی دربرگیرنده اثر میگذارند. توجه: وقتی continue در for اجرا شود، قسمت بهروزرسانی هنوز اجرا میشود؛ اما در while و do-while کنترل مستقیماً به بررسی شرط میرود و هر بهروزرسانیِ بعد از continue نادیده میماند.
Flowchart¶
Example A - Simple: پیدا کردن اولین مورد (break)¶
%%writefile src/p04_c09_21_break_demo.c
#include <stdio.h>
int main(void)
{
/* first number greater than 100 that is divisible by both 7 and 11 */
int found = -1;
for (int i = 101; i <= 1000; i++) {
if (i % 7 == 0 && i % 11 == 0) {
found = i;
break;
}
}
printf("first match = %d\n", found);
/* break leaves only the INNER loop */
printf("pairs:");
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (j == 2) {
break;
}
printf(" (%d,%d)", i, j);
}
}
printf("\n");
return 0;
}
Writing src/p04_c09_21_break_demo.c
!gcc -Wall -o bin/p04_c09_21_break_demo src/p04_c09_21_break_demo.c && ./bin/p04_c09_21_break_demofirst match = 154
pairs: (1,1) (2,1) (3,1)
مثال اول، همان الگوی «جستجو + break» است که در عدد اول دیدیم: بدون break حلقه تا ۱۰۰۰ ادامه میداد و found دوباره نوشته میشد (آخرین مضرب مشترک را بهجای اولین میگرفتیم!). مثال دوم نشان میدهد break فقط حلقهی داخلی را قطع کرده است: برای هر i، فقط j = 1 چاپ شده و بعد حلقهی داخلی تمام شده، اما حلقهی بیرونی ادامه داده است.
Example B - Real: پرش از روی موارد نامطلوب (continue)¶
%%writefile src/p04_c09_22_continue_demo.c
#include <stdio.h>
int main(void)
{
int sum = 0;
for (int i = 1; i <= 10; i++) {
if (i % 3 == 0) {
continue; /* skip multiples of 3 */
}
sum += i;
}
printf("sum of 1..10 without multiples of 3 = %d\n", sum);
return 0;
}
Writing src/p04_c09_22_continue_demo.c
!gcc -Wall -o bin/p04_c09_22_continue_demo src/p04_c09_22_continue_demo.c && ./bin/p04_c09_22_continue_demosum of 1..10 without multiples of 3 = 37
code_bc = ["for (i = 1; i <= 8; i++) {",
" if (i % 3 == 0) continue;",
" if (i == 7) break;",
" sum += i;",
"}",
"printf(\"%d\", sum);"]
LG_BC = [["cur", "تکرار جاری"], ["ok", "به sum اضافه شد"], ["dim", "continue: این دور رها شد"], ["min", "break: حلقه قطع شد"], ["i", "هنوز اجرا نشده"]]
r = Rec("break and continue inside one loop", code_bc, list(range(1, 9)), LG_BC, labels=[f"i={x}" for x in range(1, 9)])
s = 0
r.var(i=1, sum=0)
for i in range(1, 9):
r.var(i=i); r.mark(i - 1, "cur"); r.ptr(i=i - 1)
r.at(1, f"شروع تکرار با {_c(f'i = {i}')}.")
if i % 3 == 0:
r.mark(i - 1, "dim")
r.at(2, f"{_c(f'{i} % 3 == 0')} درست است ← {_c('continue')}: بقیهی بدنه رد میشود و کنترل به <b>بهروزرسانی</b> ({_c('i++')}) میرود.")
continue
r.at(2, f"{_c(f'{i} % 3 == 0')} نادرست است؛ ادامه میدهیم.")
if i == 7:
r.mark(i - 1, "min")
r.at(3, f"{_c('i == 7')} درست است ← {_c('break')}: کل حلقه فوراً قطع میشود (حتی با اینکه شرط {_c('i <= 8')} هنوز برقرار است).")
break
r.at(3, f"{_c(f'{i} == 7')} نادرست است؛ ادامه میدهیم.")
s += i; r.var(sum=s); r.mark(i - 1, "ok")
r.at(4, f"{_c(f'sum += {i}')} ← {_c('sum')} میشود {_c(s)}.")
r.echo(str(s))
r.at(6, f"پایان حلقه. مجموع {_c(s)} است: مقدارهای {_c('1 2 4 5')} اضافه شدند، ۳ و ۶ با {_c('continue')} رد شدند و ۷ و ۸ هرگز به {_c('sum')} نرسیدند.")
display(r.show())
Example C - Tricky: continue در while و خطر حلقهی بینهایت¶
%%writefile src/p04_c09_23_continue_trap.c
#include <stdio.h>
int main(void)
{
/* BUGGY: continue skips "i++" so i stays 0 forever.
guard < 5 is only a safety cap for this demo. */
int i = 0, guard = 0;
while (i < 10 && guard < 5) {
guard++;
if (i % 2 == 0) {
continue;
}
i++;
}
printf("buggy version : after %d iterations i = %d (stuck)\n", guard, i);
/* FIXED: update before continue */
int sum = 0;
int k = 0;
while (k < 10) {
k++;
if (k % 2 == 0) {
continue;
}
sum += k;
}
printf("fixed version : sum of odd numbers up to 10 = %d\n", sum);
return 0;
}
Writing src/p04_c09_23_continue_trap.c
!gcc -Wall -o bin/p04_c09_23_continue_trap src/p04_c09_23_continue_trap.c && ./bin/p04_c09_23_continue_trapbuggy version : after 5 iterations i = 0 (stuck)
fixed version : sum of odd numbers up to 10 = 25
در نسخهی اول، continue قبل از i++ اجرا میشود و چون i هرگز تغییر نمیکند، شرط i % 2 == 0 همیشه درست میماند؛ بدون سقف ایمنی، این حلقه بینهایت میشد. در for این مشکل پیش نمیآید چون بهروزرسانی در سرِ حلقه است. قاعده: در while اگر continue دارید، مطمئن شوید بهروزرسانی قبل از آن انجام شده است.
مقایسهی break، continue و return¶
| دستور | اثر | محدوده |
|---|---|---|
break | کل حلقه (یا switch) را ترک میکند | نزدیکترین حلقه/switch |
continue | تکرار فعلی را رها میکند | نزدیکترین حلقه |
return | کل تابع (اینجا main) را تمام میکند | تمام توابع و حلقهها |
تمرین درون فصل ۹.۸¶
نوع تمرین: Predict the Output
for (int i = 1; i <= 6; i++) {
if (i == 2) continue;
if (i == 5) break;
printf("%d ", i);
}خروجی چیست و i پس از خروج از حلقه چه مقداری دارد؟ (اگر i بیرون از حلقه تعریف شده باشد.)
تمرینهای پایانی زیربخش: break و continue¶
★ سطح پایه
Small Implementation:
باbreak، اولین مضرب ۱۳ بعد از ۱۰۰ را پیدا کنید.Small Implementation:
باcontinue، فقط اعداد زوج بین ۱ تا ۱۰ را چاپ کنید.
★★ سطح متوسط
Find the Bug:
int i = 0;
while (i < 10) {
if (i == 5) continue;
printf("%d ", i);
i++;
}چه مشکلی دارد؟ دو راه اصلاح بنویسید.
Modify the Algorithm:
در برنامهی میانگین با Sentinel، نمرههای نامعتبر (خارج از ۰ تا ۲۰) را باcontinueنادیده بگیرید و فقط نمرههای معتبر را به میانگین اضافه کنید.
★★★ سطح چالشی
Design:
عددnرا بگیرید و بزرگترین مقسومعلیه آن که از خودش کوچکتر است را با حلقهی معکوس وbreakپیدا کنید. چرا حلقهی معکوس اینجا از حلقهی صعودی سادهتر است؟Compare Approaches:
یک حلقهی دارایcontinueرا بدونcontinue(باifمعکوس) بازنویسی کنید. در چه شرایطی نسخهی باcontinueخواناتر است؟
9.8 حلقههای بینهایت (عمدی و سهوی)¶
بینهایت سهوی¶
حلقهای که شرطش هرگز نادرست نمیشود. چهار علت رایج: (۱) فراموش کردن بهروزرسانی، (۲) بهروزرسانی در جهت اشتباه (i-- در حلقهای که شرطش i < n است)، (۳) شرطی که با نوع داده جور نیست (شمارندهی unsigned با i >= 0، یا مقایسهی دقیق اعشاری)، (۴) continue پیش از بهروزرسانی در while. راه کشف: برای حلقهی مشکوک، مقادیر متغیرهای شرط را داخل حلقه چاپ کنید و ببینید آیا به سمت پایان حرکت میکنند.
بینهایت عمدی¶
گاهی ساختار «تا ابد تکرار کن مگر وقتی که...» بهترین شکل مسئله است؛ مثل منو یا سروری که منتظر درخواست میماند. در این حالت شرط را ثابت درست (while (1)) میگذاریم و از داخل بدنه با break (یا return) خارج میشویم:
%%writefile src/p04_c09_24_infinite_loop_break.c
#include <stdio.h>
int main(void)
{
int x, total = 0;
while (1) {
if (scanf("%d", &x) != 1) {
printf("input ended\n");
break;
}
if (x == 0) {
printf("zero received: stop\n");
break;
}
total += x;
printf("running total = %d\n", total);
}
printf("final total = %d\n", total);
return 0;
}
Writing src/p04_c09_24_infinite_loop_break.c
%%bash
gcc -Wall -o bin/p04_c09_24_infinite_loop_break src/p04_c09_24_infinite_loop_break.c || exit 1
echo "5 10 -2 0 99" | ./bin/p04_c09_24_infinite_loop_break
echo "4 6" | ./bin/p04_c09_24_infinite_loop_breakrunning total = 5
running total = 15
running total = 13
zero received: stop
final total = 13
running total = 4
running total = 10
input ended
final total = 10
مزیت این شکل: دو شرط توقف مستقل (پایان ورودی و مقدار صفر) هرکدام جای مشخص و پیام مخصوص خود را دارند؛ فشرده کردن هر دو در شرط while باعث میشد خواندن کد سختتر شود. هزینه: خواننده باید **همهی breakهای بدنه** را بررسی کند تا بفهمد حلقه چگونه تمام میشود. پس این الگو را فقط وقتی استفاده کنید که شرطهای توقف متعدد یا میانهی بدنه باشند.
%%writefile src/p04_c09_25_loop_pitfalls.c
#include <stdio.h>
int main(void)
{
/* 1. off-by-one: < versus <= */
int sum_lt = 0, sum_le = 0, it_lt = 0, it_le = 0;
for (int i = 1; i < 10; i++) { sum_lt += i; it_lt++; }
for (int i = 1; i <= 10; i++) { sum_le += i; it_le++; }
printf("1) i < 10 : %d iterations, sum = %d\n", it_lt, sum_lt);
printf(" i <= 10 : %d iterations, sum = %d\n", it_le, sum_le);
/* 2. unsigned counter: i >= 0 is always true (capped here at 5 iterations) */
printf("2) unsigned countdown from 2:");
int guard = 0;
for (unsigned int u = 2; u >= 0 && guard < 5; u--, guard++) {
printf(" %u", u);
}
printf("\n");
/* 3. a stray semicolon turns the body into an empty statement */
int count = 0;
for (int i = 0; i < 5; i++);
{
count++;
}
printf("3) count = %d (expected 5)\n", count);
return 0;
}
Writing src/p04_c09_25_loop_pitfalls.c
!gcc -Wall -o bin/p04_c09_25_loop_pitfalls src/p04_c09_25_loop_pitfalls.c && ./bin/p04_c09_25_loop_pitfallssrc/p04_c09_25_loop_pitfalls.c: In function ‘main’:
src/p04_c09_25_loop_pitfalls.c:22:5: warning: this ‘for’ clause does not guard... []8;;https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#index-Wmisleading-indentation-Wmisleading-indentation]8;;]
22 | for (int i = 0; i < 5; i++);
| ^~~
src/p04_c09_25_loop_pitfalls.c:23:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
23 | {
| ^
1) i < 10 : 9 iterations, sum = 45
i <= 10 : 10 iterations, sum = 55
2) unsigned countdown from 2: 2 1 0 4294967295 4294967294
3) count = 1 (expected 5)
خروجی سه خطا را یکجا نشان میدهد. کامپایلر فقط برای مورد سوم هشدار داده، آن هم بهدلیل تورفتگی گمراهکننده؛ دو مورد دیگر کاملاً بیصدا هستند. پس به نبودن هشدار اکتفا نکنید و به خروجی هم شک کنید: مقدار count برابر ۱ شد، نه ۵.
9.9 دستور goto و دلیل پرهیز از آن¶
goto چیست؟¶
زبان C دستوری به نام goto دارد که کنترل برنامه را بدون هیچ شرط ساختاری به یک برچسب (Label) دلخواه در همان تابع میبرد:
goto label_name;
...
label_name:
statement;هر ساختاری که تا اینجا دیدیم (if، while، for، switch) را میتوان با ترکیب goto و if ساخت؛ در واقع کامپایلر در پایینترین سطح دقیقاً همین کار را میکند. برای مقایسه، یک حلقهی جمع ۱ تا ۵ با goto و همان حلقه با while:
%%writefile src/p04_c09_26_goto_vs_while.c
#include <stdio.h>
int main(void)
{
/* version 1: a loop built from goto */
int i = 1, sum1 = 0;
loop:
if (i > 5) {
goto done;
}
sum1 += i;
i++;
goto loop;
done:
printf("goto version: sum = %d\n", sum1);
/* version 2: the same loop with while */
int sum2 = 0;
int k = 1;
while (k <= 5) {
sum2 += k;
k++;
}
printf("while version: sum = %d\n", sum2);
return 0;
}
Writing src/p04_c09_26_goto_vs_while.c
!gcc -Wall -o bin/p04_c09_26_goto_vs_while src/p04_c09_26_goto_vs_while.c && ./bin/p04_c09_26_goto_vs_whilegoto version: sum = 15
while version: sum = 15
خروجی دو نسخه یکی است؛ پس goto از نظر قدرت چیزی کم ندارد. مشکل در قابل فهم بودن است:
در نسخهی
whileبا یک نگاه میبینید شروع حلقه کجاست، شرط چیست و بدنه کجا تمام میشود. در نسخهیgotoباید برچسبها را پیدا کنید و مسیر پرشها را در ذهن دنبال کنید.با
goto، کنترل میتواند از هر جای تابع به هر جای دیگر بپرد؛ پس برای فهم یک خط باید همهی راههای ممکن رسیدن به آن را بشناسید. نامتغیرهای حلقه (آنچه در ابتدای هر تکرار درست است) دیگر قابل استدلال نیستند.هر چه تعداد
gotoها بیشتر شود، کد به کد اسپاگتی (Spaghetti Code) نزدیکتر میشود: مسیر اجرا مثل یک کلاف درهم.
تفاوت ساختار را در دو Flowchart زیر ببینید؛ سمت اول یک برنامهی ساختیافته (هر بلوک یک ورودی و یک خروجی دارد) و سمت دوم یک برنامهی پرشی:
داستان تاریخی¶
در سال ۱۹۶۸، دانشمند هلندی ادسخر دایکسترا (Edsger W. Dijkstra) نامهای کوتاه در مجلهی Communications of the ACM منتشر کرد که عنوان معروف آن «Go To Statement Considered Harmful» (دستور goto زیانبار شمرده میشود) بود. استدلال او: فاصلهی بین متن برنامه و رفتار آن در زمان اجرا باید تا حد امکان کم باشد؛ goto این فاصله را بینهایت زیاد میکند. دو سال پیشتر (۱۹۶۶)، بوهم و ژاکوپینی ثابت کرده بودند هر برنامهی قابل محاسبه را میتوان تنها با سه ساختار ترتیب، انتخاب و تکرار نوشت؛ یعنی goto از نظر نظری هیچوقت لازم نیست. این دقیقاً همان سه ساختاری است که در این بخش از ابتدا دیدید.
جایگزینهای goto¶
مورد رایجی که وسوسه میشویم goto بزنیم، خروج از حلقههای تودرتو است. سه راه ساختیافته: ۱) یک پرچم، ۲) انتقال حلقهها به تابع و return (بعد از توابع)، ۳) بازنگری شرطها. برنامهی زیر همین مسئله (پیدا کردن اولین جفت (i, j) با i * j == 24 و i + j == 10) را با goto و با پرچم حل میکند:
%%writefile src/p04_c09_27_nested_exit.c
#include <stdio.h>
int main(void)
{
/* Version 1: goto out of both loops */
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
if (i * j == 24 && i + j == 10) {
printf("goto version: i = %d, j = %d\n", i, j);
goto found;
}
}
}
printf("goto version: not found\n");
found:
/* Version 2: a flag in both loop conditions */
int fi = 0, fj = 0, done = 0;
for (int i = 1; i <= 9 && !done; i++) {
for (int j = 1; j <= 9 && !done; j++) {
if (i * j == 24 && i + j == 10) {
fi = i;
fj = j;
done = 1;
}
}
}
if (done) {
printf("flag version: i = %d, j = %d\n", fi, fj);
} else {
printf("flag version: not found\n");
}
return 0;
}
Writing src/p04_c09_27_nested_exit.c
!gcc -Wall -o bin/p04_c09_27_nested_exit src/p04_c09_27_nested_exit.c && ./bin/p04_c09_27_nested_exitgoto version: i = 4, j = 6
flag version: i = 4, j = 6
هر دو نسخه یک جواب میدهند. نسخهی پرچم کمی بلندتر است، اما هر حلقه شرط خروج خودش را صریحاً دارد و خواننده بدون دنبال کردن برچسب میفهمد حلقه کی تمام میشود.
استثنای مشهور: پاکسازی خطا¶
در برخی کدهای حرفهای زبان C (مثلاً هستهی سیستمعاملها) از goto در یک الگوی بسیار محدود استفاده میشود: وقتی چند منبع را پشتسرهم باز میکنیم و در هر مرحله ممکن است خطا رخ دهد، همهی خطاها به یک برچسب cleanup: در انتهای تابع میپرند تا منابع آزاد شوند. این استفادهی بهشدت قاعدهمند (فقط پرش رو به جلو، فقط به انتهای تابع) با اسپاگتی فرق دارد. اما در این درس شما goto لازم ندارید: **قاعدهی عملی: برای هر وسوسهی goto، ابتدا بازنویسی با حلقه، break، پرچم یا تابع را امتحان کنید.**
تمرین درون فصل ۹.۹¶
نوع تمرین: Explain Why
حلقهی goto برنامهی goto_vs_while را در نظر بگیرید. چرا فهمیدن «اینجا کدام مقادیر i ممکن است؟» در نسخهی while سادهتر است؟ نامتغیر حلقه را برای هر دو نسخه بنویسید.
تمرینهای پایانی زیربخش: goto¶
★ سطح پایه
Refactoring:
کد زیر را باwhileبازنویسی کنید:
int n = 5;
again:
if (n == 0) goto end;
printf("%d ", n);
n--;
goto again;
end:★★ سطح متوسط
Find the Bug:
int i = 0;
start:
printf("%d\n", i);
if (i < 3) goto start;این کد چه خروجی دارد؟ و چرا ممکن است نویسنده انتظار چیز دیگری داشته باشد؟ (توجه: i هرگز تغییر نمیکند.)
Compare Approaches:
مسئلهی «پیدا کردن اولین عنصر مشترک بین دو بازهی عددی با دو حلقهی تودرتو» را باgotoو با پرچم بنویسید و خوانایی را مقایسه کنید.
★★★ سطح چالشی
Reverse Engineering:
توضیح دهید چرا قضیهی بوهم–ژاکوپینی نمیگوید «gotoبد است»، بلکه چیز دیگری را ثابت میکند. این قضیه چه چیزی دربارهی «لازم بودن»gotoمیگوید؟Design:
یک الگوریتم «باز کردن سه منبع پشتسرهم با خروج در هر مرحلهی خطا» را باifتودرتو، با پرچم، و باgoto cleanupبنویسید (بهصورت شبهکد). هر سه را از نظر خوانایی مقایسه کنید و بگویید در کدام استفاده ازgotoقابل دفاع است.
9.10 هزینهی حلقهها: شمردن تکرارها¶
برای مقایسهی الگوریتمها، نیاز به معیاری داریم که به سرعت کامپیوتر وابسته نباشد. سادهترین معیار: بدنهی حلقه چند بار اجرا میشود؟ این عدد را بهعنوان تابعی از اندازهی ورودی n بنویسید:
%%writefile src/p04_c09_28_iteration_counts.c
#include <stdio.h>
int main(void)
{
int n = 1000;
int linear = 0;
for (int i = 0; i < n; i++) {
linear++;
}
int halving = 0;
for (int m = n; m > 1; m /= 2) {
halving++;
}
long long quadratic = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
quadratic++;
}
}
printf("n = %d\n", n);
printf("single loop : %d iterations -> O(n)\n", linear);
printf("halving loop : %d iterations -> O(log n)\n", halving);
printf("two nested loops : %lld iterations -> O(n^2)\n", quadratic);
return 0;
}
Writing src/p04_c09_28_iteration_counts.c
!gcc -Wall -o bin/p04_c09_28_iteration_counts src/p04_c09_28_iteration_counts.c && ./bin/p04_c09_28_iteration_countsn = 1000
single loop : 1000 iterations -> O(n)
halving loop : 9 iterations -> O(log n)
two nested loops : 1000000 iterations -> O(n^2)
import math
rows = []
for n in (10, 100, 1000):
rows.append(dict(name=f"n = {n}", sub="تعداد تکرار بدنه",
metrics=[("حلقهی نصفشونده O(log n)", int(math.log2(n)), n * n),
("حلقهی ساده O(n)", n, n * n),
("دو حلقهی تودرتو O(n²)", n * n, n * n)]))
display(fig_bars("How the number of iterations grows with n", rows,
"در هر ردیف طول نوارها نسبت به <code dir='ltr'>n²</code> سنجیده شده است. با ۱۰۰ برابر شدن <code dir='ltr'>n</code>، حلقهی ساده ۱۰۰ برابر و حلقهی تودرتو ۱۰۰۰۰ برابر کار میکند؛ اما حلقهی نصفشونده فقط چند گام بیشتر."))
مهمترین عادتهای هزینهسنجی حلقه:
یک حلقهی ساده با گام ثابت روی
nمورد:O(n).حلقهای که مقدار را در هر گام نصف (یا دو برابر) میکند:
O(log n)(خیلی سریع).**دو حلقهی تودرتو روی
n:**O(n²)؛ سهتایی:O(n³).**حلقه تا
√n** (مثل آزمون اول بودن):O(√n).**حلقهی با
break:** بدترین حالت همانقدر است، اما حالت میانگین ممکن است خیلی بهتر باشد.
تمرین درون فصل ۹.۱۰¶
نوع تمرین: Complexity Reasoning
هر یک از حلقههای زیر چند بار بدنه را اجرا میکند (برحسب n) و از چه مرتبهای است؟
for (int i = 1; i < n; i *= 2) { ... } // الف
for (int i = 0; i < n; i += 3) { ... } // ب
for (int i = 0; i < n; i++)
for (int j = 0; j < 5; j++) { ... } // ج9.11 خطاهای رایج در حلقهها (جمعبندی)¶
Off-by-One: اشتباه بین
<و<=، یا شروع از ۰ و ۱. درمان: پیش از نوشتن، تعداد تکرار موردنیاز را بنویسید و با فرمول بازه بسنجید.فراموش کردن بهروزرسانی / جهت اشتباه: حلقه هرگز تمام نمیشود. درمان: برای هر حلقه بپرسید «کدام کمیت هر بار به پایان نزدیکتر میشود؟»
**نقطهویرگول بعد از
forیاwhile:** بدنه به یک دستور خالی تبدیل میشود.**شمارندهی اعشاری یا
unsigned:**x != 1.0یاu >= 0ممکن است هرگز نادرست نشود.**تغییر شمارنده داخل بدنهی
for:** پیشبینی رفتار حلقه را سخت میکند.مقداردهی اولیهی اشتباه:
max = 0بهجای اولین داده؛prime = 1بیرون از حلقهی بیرونی.**استفاده از
continueپیش از بهروزرسانی درwhile.**سرریز در Accumulator: مجموع یا حاصلضرب بزرگ در
int.عدم رسیدگی به ورودی خالی: تقسیم بر
countوقتیcount = 0.
9.12 کاربردهای واقعی حلقهها¶
پردازش همهی رکوردهای یک پایگاهداده یا خطوط یک فایل (خواندن تا پایان فایل).
حلقهی اصلی بازیها و برنامههای گرافیکی (دریافت ورودی ← بهروزرسانی ← رسم، تا بسته شدن برنامه).
شبیهسازیهای علمی: تکرار یک گام زمانی هزاران بار.
روشهای عددی (نیوتن، نیمهکردن بازه) که تا رسیدن به دقت مطلوب تکرار میشوند.
سرورها و سیستمهای ایمبدد که برای همیشه منتظر رویداد میمانند (
while (1)عمدی)....
تمرینهای پایانی فصل ۹¶
توجه: این تمرینها با آنچه در تمرینهای زیربخش دیدید تفاوت دارند و انواع حلقه، الگوهای حلقه و حالتهای مرزی را با هم ترکیب میکنند.
Predict the Output:
int x = 20, count = 0;
while (x > 1) {
x /= 2;
count++;
}
printf("%d %d\n", x, count);خروجی را پیشبینی کنید و مرتبهی رشد count را برحسب مقدار اولیهی x بنویسید.
Trace:
برایfor (int i = 1; i <= 4; i++) for (int j = i; j <= 4; j++) count++;تعداد نهاییcountرا با دنبال کردن جدول(i, j)بهدست آورید و با فرمول مجموع مقایسه کنید.Find the Bug:
int n = 10, sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
double avg = sum / n;
printf("%.2f\n", avg);حلقه درست است، اما میانگین چاپشده برای n = 10 دقیق نیست. خطا را پیدا کنید. (راهنمایی: به نوع تقسیم نگاه کنید.)
Edge Case Reasoning:
برای الگوریتمهای «جمع ارقام»، «عدد اول» و «Min/Max» مشخص کنید ورودیهای0،1، یک عدد منفی و یک عدد خیلی بزرگ چه رفتاری دارند و کدام یک مشکلدارند.Algorithm Design:
برنامهای بنویسید که تعداد ارقام1را در نمایش دودویی یک عدد بشمارد (راهنمایی:n % 2وn / 2در یک حلقهیwhile).Design + Implementation:
تعداد اعداد کامل (Perfect Number: عددی که برابر مجموع مقسومعلیههای کوچکتر از خود است، مثل ۶ و ۲۸) در بازهی ۱ تا ۱۰۰۰ را بیابید. تعداد کل تکرارهای حلقهی داخلی را برآورد کنید. چطور میتوان آن را با√nسریعتر کرد؟Modify the Algorithm:
الگوریتم عدد اول را طوری تغییر دهید که فقط2و سپس اعداد فرد را امتحان کند. تعداد گامها تقریباً چند برابر کم میشود؟Compare Approaches:
مسئلهی «چاپ اعداد ۱ تا ۱۰۰ که هم مربع کاملاند و هم زوج» را (الف) باforوif، (ب) باforکه مستقیماً مربعها را میسازد (i * i) بنویسید. کدام تعداد تکرار کمتری دارد؟Refactoring:
حلقهیwhile (1)با دوbreakدر برنامهیinfinite_loop_breakرا به یکwhileبا شرط مرکب تبدیل کنید. چه چیزی از خوانایی کم میشود؟
Retrieval Practice فصل ۹¶
چهار بخش آناتومی یک حلقه چیست؟ در
forهرکدام کجا نوشته میشود؟چه تفاوتی بین
whileوdo-whileاز نظر حداقل تعداد اجرای بدنه وجود دارد؟نامتغیر حلقه (Loop Invariant) یعنی چه؟ برای جمع ۱ تا n آن را بنویسید.
چرا الگوی Min/Max را با اولین داده شروع میکنیم، نه
0؟چرا در آزمون اول بودن کافی است تا
√nبررسی کنیم؟چرا الگوریتم اقلیدس حتماً تمام میشود؟ کمیت نزولی آن چیست؟
حلقهی داخلی در حلقههای تودرتو چند بار اجرا میشود و کل تکرارها چگونه حساب میشود؟
breakوcontinueهرکدام روی کدام حلقه اثر میگذارند؟چرا
continueدرwhileبدون بهروزرسانی خطرناک است؟دو دلیل برای پرهیز از
gotoو دو جایگزین ساختیافته را نام ببرید.
9.13 جمعبندی فصل ۹¶
در این فصل یاد گرفتیم چرا تکرار دستی دستورها با رشد مسئله ناممکن میشود و حلقه چگونه با چهار بخش (مقداردهی، شرط، بدنه، بهروزرسانی) آن را حل میکند. سه حلقهی while (شرط اول، ممکن است هرگز اجرا نشود)، do-while (شرط آخر، حداقل یکبار) و for (برای شمارندهی مشخص) را شناختیم و دیدیم انتخاب بین آنها گاهی درستی الگوریتم را تعیین میکند. با شش الگوی حلقه (Counter، Accumulator، Min/Max، Search با Flag، Sentinel، Convergence) دیدیم بیشتر مسئلهها ترکیبی از چند الگوی آشنا هستند. حلقههای تودرتو را برای دادههای دوبعدی و جفتها به کار بردیم و فهمیدیم هزینهی آنها ضرب میشود. با break و continue رفتار حلقه را در میانهی تکرار تغییر دادیم و خطرهای حلقهی بینهایت را بررسی کردیم. در پایان دلیل پرهیز از goto را از دید خوانایی و استدلالپذیری و با نگاهی تاریخی دیدیم. همچنین یاد گرفتیم تکرارها را بشماریم و الگوریتمها را با O(log n)، O(√n)، O(n) و O(n²) مقایسه کنیم.
جمعبندی بخش چهارم¶
نقشه مفهومی¶
Sequence (اجرای ترتیبی)
│
┌─────────────────┴─────────────────┐
▼ ▼
Selection (تصمیمگیری) Iteration (تکرار)
│ │
┌──────┬───────┼───────┬────────┐ ┌─────────┼──────────┐
▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼
if if-else else-if ?: switch while do-while for
│ │
ترتیب شرطها مهم است الگوهای حلقه
Counter / Accumulator / Min-Max
Search+Flag / Sentinel / Convergence
│
┌──────────────────┼──────────────────┐
▼ ▼ ▼
Nested Loops break / continue goto
(هزینه ضربشونده) (نزدیکترین حلقه) (پرهیز؛ جایگزین: پرچم/تابع)جدول مرور سریع¶
| مفهوم | نکته کلیدی | هزینه (در صورت وجود) |
|---|---|---|
| شرط در C | صفر = نادرست، غیرصفر = درست؛ && و || کوتاهمدارند | - |
| قوانین دمورگان | !(A && B) = !A || !B | - |
else if | اولین شرط درست برنده است؛ ترتیب بخشی از منطق است | بدترین حالت: k مقایسه |
| تست مرزی | روی مرز هر شرط: قبل، خود مرز، بعد | - |
| Guard Clause | خطاها را زودتر رد کن؛ تو در تویی را کم کن | - |
?: | یک عبارت است (مقدار دارد)؛ همیشه پرانتز بگذار | - |
switch | فقط تساوی با ثابت صحیح؛ break را فراموش نکن | - |
while | شرط قبل از بدنه؛ ممکن است صفر بار اجرا شود | بسته به مسئله |
do-while | شرط بعد از بدنه؛ حداقل یکبار | بسته به مسئله |
for | شمارندهی مشخص؛ مراقب off-by-one باش | حلقهی ساده: O(n) |
| Min/Max | با اولین داده شروع کن | O(n) |
| عدد اول | فقط تا √n بررسی کن | O(√n) |
| ب.م.م اقلیدس | gcd(a,b) = gcd(b, a mod b) | O(log n) |
| حلقهی تودرتو | تعداد تکرارها ضرب میشود | دو سطح: O(n²) |
break / continue | فقط نزدیکترین حلقه | - |
goto | از نظر نظری لازم نیست؛ خوانایی را نابود میکند | - |
Retrieval Practice جامع بخش چهارم¶
چرا عبارت
x == 1 || 2همیشه درست است؟چرا در یک زنجیرهی
else ifفقط یک شاخه اجرا میشود، و در چندifپشتسرهم ممکن است چند شاخه اجرا شود؟چه تفاوتی بین «پوشش مسیرها» و «تست مرزی» است؟
چرا ترفند
switch (score / 10)بدون اعتبارسنجی ورودی خطرناک است؟چرا میگوییم
breakدرswitchوbreakدر حلقه یک کار شبیه ولی نه یکسان انجام میدهند؟کدام الگوی حلقه برای «پیدا کردن بزرگترین» و کدام برای «پیدا کردن اولین» مناسب است؟
چرا هر حلقهی همگرا باید سقف تکرار هم داشته باشد؟
تمرینهای نهایی بخش چهارم¶
توجه: این تمرینها با مثالهای داخل درس متفاوتاند و نیازمند ترکیب چند مفهوم هستند.
Level 1 : Fundamental¶
برنامهای بنویسید که یک عدد صحیح بخواند و بگوید مثبت، منفی یا صفر است.
با یک حلقهی
for، مجموع همهی اعداد فرد بین ۱ تا ۹۹ را چاپ کنید.برنامهای بنویسید که عدد
nرا بخواند وnبار پیام «Hello» را چاپ کند (برایn ≤ 0هیچ پیامی چاپ نشود).
Level 2 : Intermediate¶
برنامهای بنویسید که ساعت و دقیقهی یک رویداد را بخواند، آنها را اعتبارسنجی کند (ساعت ۰ تا ۲۳، دقیقه ۰ تا ۵۹) و بگوید «صبح»، «بعدازظهر» یا «شب» است.
اعداد ورودی را تا رسیدن به صفر بخوانید و تعداد اعداد مثبت، منفی و میانگین کل را چاپ کنید (با مدیریت حالت ورودی خالی).
فاکتوریل
nرا باlong longحساب کنید و برایnکه از ظرفیت نوع بیشتر است پیام خطا بدهید.
Level 3 : Advanced¶
برنامهای بنویسید که همهی اعداد «آرمسترانگ» ۳ رقمی (عددی که مجموع مکعب ارقامش برابر خودش است، مثل ۱۵۳) را بین ۱۰۰ تا ۹۹۹ پیدا کند.
برنامهای بنویسید که
nرا بخواند وnجملهی اول دنبالهی فیبوناچی را چاپ کند (بدون آرایه، با دو متغیر کمکی). برای چهnای ازintسرریز میکند؟
Level 4 : Challenge¶
بازی «حدس عدد با جستجوی دودویی»: برنامه عددی بین ۱ تا ۱۰۰۰ را (ثابت، مثلاً ۷۳۷) در نظر میگیرد و حدسها را از ورودی میخواند. پس از هر حدس، «Higher» یا «Lower» چاپ میکند. سپس برنامهی دومی بنویسید که خودش با روش نصفکردن بازه (
low،high،mid) عدد را پیدا کند و تعداد حدسها را بشمارد. بیشترین تعداد حدس لازم چند است؟ (راهنمایی:log₂ 1000.)
Final Challenge : مسئله جامع بخش چهارم¶
برنامهی تحلیل نمرات کلاس
برنامهای بنویسید که یک منوی تعاملی داشته باشد:
افزودن نمره: یک نمره از ورودی بخواند. اگر خارج از بازهی ۰ تا ۲۰ بود، تا گرفتن نمرهی معتبر دوباره بپرسد (حداکثر با ورودی تمامشدنی). نمرهی معتبر باید در آمار ثبت شود.
نمایش آمار: تعداد نمرهها، میانگین، بیشترین و کمترین را چاپ کند. اگر هنوز نمرهای وارد نشده، پیام مناسب بدهد (و تقسیم بر صفر نکند).
نمایش توزیع: تعداد نمرهها در هر دسته (مردود: زیر ۱۰، قبول: ۱۰ تا ۱۳، خوب: ۱۴ تا ۱۶، عالی: ۱۷ تا ۲۰) را بهصورت هیستوگرام ستارهای چاپ کند (یک سطر برای هر دسته، بهتعداد نمرهها ستاره).
خروج.
این مسئله عمداً چند مفهوم بخش را ترکیب میکند: منو با do-while (یا while (1)) و switch؛ اعتبارسنجی نمره با do-while؛ آمار با الگوهای Counter/Accumulator/Min-Max (بدون آرایه، با متغیرهای کمکی)؛ درجهبندی با زنجیرهی else if مرتبشده؛ و هیستوگرام با حلقههای تودرتو.
پیش از دیدن راهنماییها، سعی کنید مسئله را خودتان تحلیل و پیادهسازی کنید. اگر گیر کردید، بهترتیب از راهنماییهای زیر استفاده کنید:
راهنمایی 1:
برای نگهداری آمار بدون آرایه، قبل از حلقهی منو این متغیرها را تعریف کنید: count، sum، min، max، و چهار شمارندهی fail، pass، good، excellent. فراموش نکنید min و max را با اولین نمره مقداردهی کنید، نه با یک عدد دلخواه (چطور میفهمید اولین نمره است؟ از count == 0).
راهنمایی 2:
چون منو باید حداقل یکبار نمایش داده شود، ساختار کلی do { ...نمایش منو، خواندن انتخاب، switch... } while (choice != 4); مناسب است. مراقب باشید scanf در پایان ورودی شکست میخورد؛ این حالت را با یک break یا return مدیریت کنید تا حلقه بینهایت نشود.
راهنمایی 3:
برای هیستوگرام، برای هر دسته یک printf برای نام دسته و سپس یک for ساده برای چاپ ستارهها بنویسید. اگر بخواهید همین کار را برای چهار دسته با کمتر تکرار کد انجام دهید، فعلاً کد تکراری قابل قبول است؛ در بخش توابع، راه تمیزتری یاد میگیرید.
راهنمایی 4:
حالتهای مرزی را حتماً تست کنید: خروج بدون هیچ نمرهای، نمایش آمار قبل از ثبت نمره، نمرهی 0 و 20 (مرزهای بازه)، و نمرههای 9، 10، 13، 14، 16، 17 که مرزهای دستهبندیاند.
با پایان این بخش، شما اکنون دو ابزار بنیادین برنامهنویسی را در اختیار دارید: تصمیمگیری (Selection) و تکرار (Iteration). همراه با اجرای ترتیبی، این سه ساختار برای نوشتن هر الگوریتمی کافیاند. اما شما فقط سینتکس را یاد نگرفتید؛ شما یاد گرفتید یک مسئله را به الگوی مناسب تبدیل کنید، درستی آن را با Trace و تست مرزی بسنجید و هزینهاش را بشمارید. این مهارتها پایهی بسیاری از موضوعهای بعدی (آرایهها، جستجو، مرتبسازی) هستند، که هر کدام با یک حلقه روی مجموعهای از داده شروع میشوند.
نگاهی به یک دانشمند تأثیرگذار در این حوزه¶
خب، حالا که با ساختارهای تصمیم و تکرار آشنا شدیم و دیدیم چرا از goto پرهیز میکنیم، بد نیست کمی هم با دانشمندی آشنا شویم که این نگاه را در علوم کامپیوتر جا انداخت.
ادسخر ویبه دایکسترا (Edsger W. Dijkstra) دانشمند علوم کامپیوتر هلندی (۱۹۳۰ تا ۲۰۰۲) بود. او الگوریتم معروف کوتاهترین مسیر در گرافها را (که تقریباً هر نقشهیاب امروزی ریشهای از آن دارد) در دههی ۱۹۵۰ ابداع کرد. اما شاید تأثیرگذارترین کار او در نگاه ما به «ساختار برنامه» باشد: در سال ۱۹۶۸ نامهی کوتاه او دربارهی دستور goto منتشر شد و بحثی را آغاز کرد که به برنامهنویسی ساختیافته (Structured Programming) انجامید. استدلال او فنی بود، نه سلیقهای: اگر نتوانیم از روی متن برنامه رفتار آن در زمان اجرا را پیشبینی کنیم، نمیتوانیم درستیاش را اثبات یا حتی با اطمینان بررسی کنیم. او در سال ۱۹۷۲ جایزهی تورینگ را دریافت کرد.
جالب است که اگر به کاری که در این بخش کردیم نگاه کنیم، مسیر فکری دایکسترا چندان دور از آن نیست: یک برنامهی پیچیده ← تشخیص اینکه فهمش سخت است ← پیدا کردن ساختارهایی که استدلال دربارهی آنها آسان است (یک ورودی، یک خروجی) ← ساختن همهچیز از همانها. نامتغیر حلقه، شرط توقف و Trace که در این بخش تمرین کردید، همه ابزارهای همین نگاهاند.
شاید یکی از نکات جالب این داستان این باشد که یکی از مؤثرترین ایدههای برنامهنویسی، نه افزودن یک قابلیت جدید، بلکه «محدود کردن» قدرت برنامهنویس به ساختارهای قابل فهم بود.