Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

بخش اول: مبانی و مقدمات

Authors
Affiliations
دانشگاه فردوسی مشهد
دانشگاه فردوسی مشهد
دانشگاه فردوسی مشهد

مقدمه

عددی بین ۱ تا ۱۰۰ در ذهن بگیرید و از دوستتان بخواهید حدس بزند. بعد از هر حدس فقط یکی از سه جواب را می‌شنود: «درست است»، «عدد من بزرگ‌تر است» یا «عدد من کوچک‌تر است». اگر حدس‌ها را تصادفی بزند، شاید ده‌ها بار لازم شود. اما اگر هوشمندانه حدس بزند، حداکثر ۷ حدس کافی است. این «هوشمندانه» فقط یک ایده‌ی خوب نیست؛ روشی دقیق و تکرارپذیر است که کامپیوتر هم می‌تواند اجرا کند. اسم چنین روشی الگوریتم است. خودتان امتحانش کنید و ببینید بازه‌ی ممکن بعد از هر حدس چطور نصف می‌شود:

Loading...

برنامه‌نویسی یعنی پیدا کردن چنین روش‌هایی و گفتنشان به کامپیوتر. این بخش مسیر کامل را از ایده تا برنامه‌ی در حال اجرا نشان می‌دهد. در فصل ۱ یاد می‌گیریم یک روش حل مسئله را چطور دقیق بنویسیم و بکشیم. در فصل ۲ می‌بینیم کامپیوتر چطور آن را اجرا می‌کند و اعداد و متن را چطور نگه می‌دارد. در فصل ۳ اولین برنامه‌ی C را می‌نویسیم، اجرا می‌کنیم و یاد می‌گیریم وقتی کار نکرد چه کنیم.

نقشه کلی بخش:

Problem ──► Algorithm ──► Flowchart / Pseudocode ──► C code ──► Compile ──► Run
└──────────── chapter 1 ───────────────┘            └─ chapter 3 ─┘
                  chapter 2: CPU, memory, numbers, text

فصل ۱ : Algorithm

1.1 الگوریتم چیست؟

الگوریتم دنباله‌ای محدود از دستورهای دقیق است که ورودی را گام‌به‌گام به خروجی می‌رساند. دستور پخت یک غذا شبیه آن است، با یک تفاوت مهم: کامپیوتر هیچ شمّ و حدسی ندارد. «کمی نمک بریز» برای یک آدم کافی است، اما برای کامپیوتر باید دقیقاً گفته شود چه مقدار و در کدام لحظه. هر چیزی که می‌خواهیم کامپیوتر انجام دهد باید بی‌ابهام و کامل نوشته شود.

یک نکته‌ی تاریخی: واژه‌ی algorithm از نام محمد بن موسی خوارزمی، دانشمند ایرانی قرن سوم هجری، آمده است. کتاب او درباره‌ی محاسبه با اعداد هندی به لاتین ترجمه شد و نام او در اروپا به شکل «Algoritmi» به یادگار ماند.

یک الگوریتم خوب این ویژگی‌ها را دارد:

ویژگییعنی چه؟نمونه‌ی نقض
ورودی و خروجیمشخص است چه می‌گیرد و چه می‌دهدروشی که معلوم نیست چه نتیجه‌ای می‌دهد
دقت (بی‌ابهامی)هر گام فقط یک معنی دارد«کمی نمک بریز»
پایان‌پذیریبعد از تعداد محدودی گام تمام می‌شود«تا ابد تکرار کن»
اجرایی بودنهر گام واقعاً قابل انجام است«بزرگ‌ترین عدد صحیح را بنویس»

علاوه بر این‌ها، دو الگوریتمِ درست می‌توانند از نظر سرعت خیلی فرق کنند؛ در بخش 1.4 همین را می‌بینیم. بیشتر الگوریتم‌هایی که امروز استفاده می‌شوند جدیدند، اما بعضی بسیار قدیمی‌اند: الگوریتم اقلیدس برای پیدا کردن بزرگ‌ترین مقسوم‌علیه مشترک دو عدد بیش از ۲۰۰۰ سال قدمت دارد و هنوز در کامپیوترها اجرا می‌شود.

1.2 شبه‌کد

برای نوشتن الگوریتم دو راه رایج داریم. راه اول شبه‌کد است: توصیف مرحله‌ها با کلمه‌های ساده، بدون قوانین سخت یک زبان برنامه‌نویسی. هدف شبه‌کد این است که یک آدم آن را به‌راحتی بخواند. ما از چند کلمه‌ی ثابت استفاده می‌کنیم: «بخوان»، «چاپ کن»، «اگر … آنگاه»، «تکرار کن»، و فلش ‎←‎ برای قرار دادن مقدار در یک متغیر؛ یعنی ‎max ← x‎ می‌گوید مقدار x را در max بگذار. مثال: پیدا کردن بزرگ‌ترین عدد از میان چند عدد.

  1. عدد اول را بخوان و در max بگذار.

  2. تا وقتی عدد دیگری مانده است، تکرار کن:

    • عدد بعدی را بخوان و در x بگذار.

    • اگر ‎x > max‎ باشد، آنگاه ‎max ← x‎.

  3. مقدار max را چاپ کن.

متغیر max همیشه «بزرگ‌ترین عددِ دیده‌شده تا اینجا» را نگه می‌دارد. اگر عدد تازه از آن بزرگ‌تر بود، جایش را می‌گیرد. با ذهنتان امتحان کنید: برای عددهای ۱۲، ۷، ۲۵، ۹، ۱۸ مقدار max چه مراحلی را طی می‌کند؟

1.3 فلوچارت

راه دوم فلوچارت است: همان الگوریتم، ولی با شکل و فلش. چشم ما جریان را روی کاغذ راحت‌تر دنبال می‌کند، مخصوصاً وقتی مسیرها شاخه‌شاخه می‌شوند. شکل‌ها استاندارد هستند:

Loading...

قاعده‌ها ساده‌اند: فقط یک «شروع» داریم، جریان همیشه با فلش نشان داده می‌شود، و هر لوزی (تصمیم) دقیقاً دو خروجی «بله» و «خیر» دارد. هر مسیر در نهایت به «پایان» می‌رسد. اولین مثال یک تصمیم ساده است: تعیین قبول یا مردود شدن با نمره. دکمه‌ی پخش را بزنید و مسیری را که کامپیوتر طی می‌کند دنبال کنید. اجرا دو بار انجام می‌شود تا هر دو شاخه را ببینید:

Loading...

یک فلوچارت برای همه‌ی ورودی‌ها کار می‌کند؛ هر ورودی فقط یکی از دو مسیر را می‌رود. مثال بعدی همان الگوریتم بزرگ‌ترین عدد است. این‌جا یک فلش برگشتی داریم که کار «تکرار» را انجام می‌دهد: تا وقتی عدد دیگری مانده است، مسیر به بالا برمی‌گردد.

Loading...

از فلوچارت تا کد

وقتی الگوریتم روی کاغذ درست شد، نوشتن کد آسان می‌شود. برنامه‌های زیر همان دو فلوچارت را به زبان C نوشته‌اند. لازم نیست الان همه‌ی کلمه‌هایشان را بفهمید؛ فقط توجه کنید که ساختار کد همان ساختار فلوچارت است: لوزی تبدیل شده به if و فلش برگشتی به for.

#include <stdio.h>

int main(void)
{
    int score;

    scanf("%d", &score);

    if (score >= 10)
        printf("pass\n");
    else
        printf("fail\n");
    return 0;
}

با ورودی ‎14‎ و بعد ‎7‎:

14
pass
7
fail
#include <stdio.h>

int main(void)
{
    int x, max;

    scanf("%d", &max);
    for (int i = 1; i < 5; i++) {
        scanf("%d", &x);
        if (x > max)
            max = x;
    }
    printf("max = %d\n", max);
    return 0;
}

با ورودی ‎12 7 25 9 18‎:

max = 25

1.4 یک الگوریتم هوشمند: حدس عدد

حالا به بازی ابتدای بخش برگردیم. روش هوشمندانه این است: همیشه وسط بازه‌ی ممکن را حدس بزن. اگر جواب «عدد من بزرگ‌تر است» بود، همه‌ی عددهای کوچک‌تر از حدس حذف می‌شوند، و اگر «کوچک‌تر» بود، همه‌ی عددهای بزرگ‌تر. در هر حدس، نصف عددهای ممکن دور ریخته می‌شود. فلوچارت زیر این روش را برای عدد پنهان ۷۳ اجرا می‌کند؛ توجه کنید که بازه‌ی low تا high چطور کوچک می‌شود:

Loading...

همین الگوریتم به زبان C، با همان عدد پنهان:

#include <stdio.h>

int main(void)
{
    int secret = 73;
    int low = 1, high = 100, count = 0;

    while (1) {
        int guess = (low + high) / 2;

        count++;
        printf("guess %d: %d\n", count, guess);

        if (guess < secret)
            low = guess + 1;
        else if (guess > secret)
            high = guess - 1;
        else
            break;
    }
    printf("found in %d guesses\n", count);
    return 0;
}
guess 1: 50
guess 2: 75
guess 3: 62
guess 4: 68
guess 5: 71
guess 6: 73
found in 6 guesses

حدس‌ها (۵۰، ۷۵، ۶۲، ۶۸، ۷۱، ۷۳) دقیقاً همان‌هایی هستند که در فلوچارت دیدید. حالا ببینید این روش با بزرگ شدن مسئله چقدر مؤثر است:

تعداد عددهای ممکنحدس یکی‌یکی (بدترین حالت)حدس با نیم‌کردن (بدترین حالت)
۱۰۰۱۰۰۷
۱٬۰۰۰۱٬۰۰۰۱۰
۱٬۰۰۰٬۰۰۰۱٬۰۰۰٬۰۰۰۲۰
۸٬۰۰۰٬۰۰۰٬۰۰۰۸٬۰۰۰٬۰۰۰٬۰۰۰۳۳

یعنی با فقط ۳۳ پرسش بله و خیر می‌شود یک نفر را از میان حدود ۸ میلیارد آدم پیدا کرد. هر بار که تعداد عددها ۲ برابر شود، فقط یک حدس اضافه لازم است. این ایده در بخش پنجم با اسم جستجوی دودویی برمی‌گردد. کارایی یک الگوریتم یعنی با بزرگ شدن ورودی، تعداد گام‌هایش چقدر زیاد می‌شود. در بخش‌های بعد وقتی الگوریتم‌های مختلف را مقایسه می‌کنیم، همین معیار را به کار می‌بریم.

1.5 تمرین

تمرین ۱. الگوریتمی به شبه‌کد بنویسید که یک عدد صحیح را بگیرد و بگوید زوج است یا فرد. (راهنمایی: عدد زوج است اگر باقی‌مانده‌ی تقسیمش بر ۲ صفر باشد.)

تمرین ۲. الگوریتمی بنویسید که عدد n را بگیرد و جمع عددهای ۱ تا n را چاپ کند. آن را برای ‎n = 4‎ دستی اجرا کنید.

تمرین ۳. این الگوریتم چه ایرادی دارد؟ ورودی ۷ را در نظر بگیرید: «x را بخوان. تا وقتی ‎x ≠ 0‎ است، ‎x ← x − 2‎ را تکرار کن. پایان.»

تمرین ۴. در بازی حدس عدد، عدد پنهان ۱۰ و بازه از ۱ تا ۱۶ است. روش نیم‌کردن چند حدس نیاز دارد؟ حدس‌ها چیست؟


فصل ۲ : Computer و Data

2.1 کامپیوتر از درون

یک الگوریتم تا وقتی کسی اجرایش نکند فقط روی کاغذ است. اجراکننده‌ی آن در کامپیوتر چند بخش اصلی دارد:

بخشکارویژگی
پردازنده (CPU)دستورها را یکی‌یکی اجرا می‌کندبسیار سریع
حافظه‌ی اصلی (RAM)برنامه و داده‌ی در حال اجرا را نگه می‌داردسریع، با خاموش شدن پاک می‌شود
حافظه‌ی دائمی (SSD یا HDD)فایل‌ها و برنامه‌ها را نگه می‌داردکندتر، ماندگار
ورودی و خروجیارتباط با کاربر (صفحه‌کلید، صفحه‌نمایش، …)وابسته به دستگاه

نکته‌ی مهم این است که خود برنامه هم داده است. وقتی برنامه‌ای اجرا می‌شود، دستورهایش به‌صورت عدد در حافظه‌ی اصلی قرار می‌گیرند و پردازنده آن‌ها را از همان‌جا می‌خواند. کامپیوتر فقط عدد می‌فهمد؛ متن، تصویر و صدا هم باید قبل از ذخیره به عدد تبدیل شوند. بقیه‌ی این فصل نشان می‌دهد پردازنده دستورها را چطور اجرا می‌کند و عددها و متن چطور نگه داشته می‌شوند.

2.2 چرخه‌ی واکشی، رمزگشایی و اجرا

پردازنده فقط یک کار را بی‌وقفه تکرار می‌کند: دستور بعدی را از حافظه می‌آورد (Fetch)، می‌فهمد چه می‌خواهد (Decode) و آن را انجام می‌دهد (Execute). برای اینکه بداند دستور بعدی کجاست، یک شمارنده به نام PC (Program Counter) دارد که بعد از هر واکشی یکی زیاد می‌شود. دستورِ واکشی‌شده در ثباتی به نام IR و نتیجه‌ی محاسبه‌ها در ثباتی به نام A (انباره) می‌ماند. ثبات‌ها حافظه‌های بسیار کوچک و سریعِ داخل خود پردازنده‌اند.

مثال زیر یک پردازنده‌ی ساده‌شده است که معادل دستور ‎x = a + b‎ را اجرا می‌کند. دکمه‌ی پخش را بزنید و حرکت داده‌ها را میان حافظه و پردازنده دنبال کنید:

Loading...

پردازنده‌ی واقعی ده‌ها ثبات و صدها نوع دستور دارد، اما اساس کارش همین چرخه است. سرعت ساعتِ پردازنده‌های امروزی چند گیگاهرتز است، یعنی چند میلیارد گام در هر ثانیه. در بخش 3.4 می‌بینیم که کامپایلر یک خط C را چطور به چنین دستورهایی تبدیل می‌کند.

2.3 سیستم‌های عددی

ما عددها را در مبنای ۱۰ می‌نویسیم، شاید چون ده انگشت داریم. در هر مبنا، ارزش هر رقم به جایگاهش بستگی دارد: عدد ‎407‎ یعنی ‎4×100 + 0×10 + 7×1‎، و هر جایگاه ده برابر جایگاه سمت راستش است. کامپیوتر به دلیل ساده‌ای از مبنای ۲ استفاده می‌کند: ساختن مداری که فقط دو حالت (خاموش و روشن، یا ولتاژ پایین و بالا) را تشخیص دهد بسیار ساده‌تر و مطمئن‌تر از مداری با ده حالت است. در مبنای ۲ فقط رقم‌های ‎0‎ و ‎1‎ داریم و ارزش جایگاه‌ها ۱، ۲، ۴، ۸، ۱۶ و … است.

مبنارقم‌هاکاربرد
دهدهی (۱۰)0 تا 9زندگی روزمره
دودویی (۲)0 و 1سخت‌افزار و مدارها
اکتال (۸)0 تا 7کاربرد محدود، مثلاً مجوز فایل‌ها در لینوکس
هگزادسیمال (۱۶)0 تا 9 و A تا Fنوشتن کوتاه بیت‌ها، آدرس‌ها و رنگ‌ها

به هر رقم دودویی یک بیت (bit) می‌گویند و هر ۸ بیت را یک بایت (byte) می‌نامند. (واژه‌ی bit کوتاه‌شده‌ی binary digit است؛ جان توکی آن را ساخت و کلود شانون در مقاله‌ی معروف خود در ۱۹۴۸ رایجش کرد.) در ابزار زیر هشت بیت یک بایت را می‌بینید. روی بیت‌ها کلیک کنید، یا یکی از عددهای نمونه را بزنید، و ببینید مقدار در همه‌ی مبناها چطور عوض می‌شود. دکمه‌ی «۱+» را روی ۲۵۵ امتحان کنید:

Loading...

تبدیل بین مبناها

دودویی به دهدهی: وزن بیت‌های روشن را جمع می‌کنیم. عدد ‎1011‎ یعنی ‎8 + 0 + 2 + 1 = 11‎.

دهدهی به دودویی: عدد را مدام بر ۲ تقسیم می‌کنیم و باقی‌مانده‌ها را از آخر به اول می‌خوانیم. برای عدد ۱۳:

تقسیمخارج‌قسمتباقی‌مانده
13 ÷ 261
6 ÷ 230
3 ÷ 211
1 ÷ 201

باقی‌مانده‌ها از پایین به بالا ‎1101‎ می‌شود، یعنی ‎8 + 4 + 0 + 1 = 13‎.

هگزادسیمال: هر رقم هگز دقیقاً چهار بیت است (مقدار A تا F برابر ۱۰ تا ۱۵ است)، پس تبدیل با گروه‌بندی انجام می‌شود، بدون هیچ حساب‌وکتاب: ‎2F‎ برابر ‎0010 1111‎ و C8 برابر ‎1100 1000‎ است. برای همین برنامه‌نویس‌ها برای نوشتن بایت‌ها از هگز استفاده می‌کنند: دو رقم هگز، یک بایت. در C هم می‌توان یک عدد را در مبناهای مختلف چاپ کرد:

#include <stdio.h>

int main(void)
{
    int n = 65;

    printf("decimal : %d\n", n);
    printf("hex     : %x\n", n);
    printf("octal   : %o\n", n);
    printf("char    : %c\n", n);
    return 0;
}
decimal : 65
hex     : 41
octal   : 101
char    : A

عدد ۶۵ در مبنای ۱۶ برابر ‎41‎ و در مبنای ۸ برابر ‎101‎ است. خط آخر نشان می‌دهد همین عدد به‌عنوان یک نویسه چاپ شود، A است؛ دلیلش را در بخش 2.7 می‌بینیم.

2.4 جمع و تفریق دودویی

جمع دودویی دقیقاً مثل جمع کاغذی ده‌دهی است: از راست‌ترین ستون شروع می‌کنیم و رقم نقلی را به ستون بعد می‌بریم. فقط قاعده ساده‌تر است، چون فقط چهار حالت داریم:

جمع ستونحاصل ستونرقم نقلی
0 + 000
0 + 110
1 + 101
1 + 1 + 111

یعنی ‎1 + 1‎ در دودویی برابر ‎10‎ است: ۰ می‌نویسیم و ۱ را به ستون بعد می‌بریم. جمع ۱۳ و ۷ را قدم‌به‌قدم ببینید:

Loading...

پردازنده‌ی کامپیوتر همین قاعده‌ی ساده را با مدارهای کوچکی به نام «جمع‌کننده» انجام می‌دهد. تفریق هم جدا لازم نیست: ‎a − b‎ را به‌صورت ‎a + (−b)‎ حساب می‌کنیم. برای این کار باید بدانیم عدد منفی را چطور در بیت‌ها نشان بدهیم، که موضوع بخش بعد است.

2.5 اعداد صحیح با علامت

با بیت‌ها فقط عدد غیرمنفی می‌توان نوشت. برای عدد منفی ساده‌ترین ایده این است که یک بیت را به علامت اختصاص دهیم، اما این روش دو صفر دارد (‎+0‎ و ‎-0‎) و جمع کردن را سخت می‌کند. روشی که تقریباً همه‌ی کامپیوترها استفاده می‌کنند مکمل ۲ (two’s complement) است. ایده این است که وزن بیت سمت چپ را منفی بگیریم: در یک بایت وزن‌ها ‎-128, 64, 32, 16, 8, 4, 2, 1‎ می‌شوند. نتیجه:

  • بیت سمت چپ ۱ باشد، عدد منفی است.

  • بازه‌ی یک بایت از ‎-128‎ تا ‎127‎ است (در حالت کلی برای n بیت از ‎-2^(n-1)‎ تا ‎2^(n-1)-1‎).

  • عدد ‎11111111‎ برابر ‎-128 + 127 = -1‎ است.

برای ساختن قرینه‌ی یک عدد، همه‌ی بیت‌ها را برعکس می‌کنیم و ۱ جمع می‌کنیم. در ابزار زیر حالت «با علامت» روشن است. عدد ‎251‎ همان ‎-5‎ است. دکمه‌ی «قرینه» را بزنید و دوباره بزنید. بعد عدد ‎127‎ را بزنید و «۱+» را امتحان کنید:

Loading...

زیبایی مکمل ۲ این است که همان مدار جمع‌کننده برای عددهای مثبت و منفی کار می‌کند. مثلاً ‎13 - 7‎ را به‌صورت ‎13 + (-7)‎ در هشت بیت حساب می‌کنیم: عدد ۷ برابر ‎00000111‎ است، پس ‎-7‎ برابر ‎11111001‎ می‌شود (معکوس: ‎11111000‎ و بعد ۱ جمع می‌کنیم). حالا ‎00001101 + 11111001 = 1 00000110‎. بیت نهم (رقم نقلی) دور ریخته می‌شود و ‎00000110‎ یعنی ۶ می‌ماند، که جواب درست است.

سرریز

هشت بیت فقط ۲۵۶ حالت دارد. اگر نتیجه از بازه بیرون برود، سرریز (overflow) رخ می‌دهد و شمارش از ابتدا ادامه می‌یابد، مثل کیلومترشمار ماشین که بعد از ۹۹۹۹۹ به ۰ برمی‌گردد. در C برای نوع‌های unsigned این رفتار دقیقاً همین است:

#include <stdio.h>

int main(void)
{
    unsigned char c = 255;

    c = c + 1;
    printf("%d\n", c);
    return 0;
}
0

برای int علامت‌دار، استاندارد C سرریز را «رفتار تعریف‌نشده» می‌داند؛ یعنی هر اتفاقی ممکن است بیفتد. یک نمونه‌ی واقعی: در دسامبر ۲۰۱۴ شمارنده‌ی بازدید یوتیوب برای یک ویدیوی بسیار پربازدید از ‎2147483647‎ (بزرگ‌ترین عدد صحیح علامت‌دار ۳۲ بیتی) گذشت و یوتیوب اعلام کرد شمارنده را به ۶۴ بیت ارتقا داده است.

2.6 اعداد اعشاری

عدد اعشاری را چطور در بیت‌ها بنویسیم؟ مثل نمادگذاری علمی: ‎-2.5‎ را می‌توان ‎-1.25 × 2¹‎ نوشت. استاندارد IEEE 754 همین ایده را دارد و عدد را در سه فیلد نگه می‌دارد: علامت (۱ بیت)، توان (۸ بیت) و مانتیس یعنی رقم‌های بعد از ممیز (۲۳ بیت). این قالب ۳۲ بیتی نوع float است؛ نوع double در ۶۴ بیت (۱ بیت علامت، ۱۱ بیت توان و ۵۲ بیت مانتیس) دقت بیشتری دارد. مقدار عدد از این فرمول به دست می‌آید:

value = (-1)^sign × 1.mantissa × 2^(exponent - 127)

عدد ‎0.1‎ را در ابزار زیر ببینید و بیت‌ها را خودتان هم عوض کنید. عدد دلخواه دیگری هم می‌توانید بنویسید:

Loading...

دقت کنید که ابزار می‌گوید ‎0.1‎ دقیقاً قابل ذخیره نیست. دلیلش این است که ‎0.1‎ در مبنای ۲ یک عدد اعشاریِ بی‌پایان است (‎0.000110011001100…‎)، مثل ‎1/3‎ که در مبنای ۱۰ بی‌پایان می‌شود. پس فقط نزدیک‌ترین عدد قابل‌ذخیره نگه داشته می‌شود. این موضوع در برنامه‌ها نتیجه‌ی عجیبی می‌دهد:

#include <stdio.h>

int main(void)
{
    double a = 0.1, b = 0.2;

    printf("%.17g\n", a + b);
    printf("equal to 0.3? %d\n", a + b == 0.3);
    return 0;
}
0.30000000000000004
equal to 0.3? 0

مجموع ‎0.1 + 0.2‎ در کامپیوتر دقیقاً ‎0.3‎ نیست و مقایسه‌ی آن‌ها با ‎==‎ نادرست می‌شود. قاعده‌ی کلی: اعداد اعشاری را با ‎==‎ مقایسه نکنید؛ بررسی کنید که اختلافشان از یک مقدار بسیار کوچک کمتر باشد. اعداد صحیح بزرگ هم محدودیت دارند: float از ۲²⁴ = ۱۶٬۷۷۷٬۲۱۶ به بعد نمی‌تواند همه‌ی عددهای صحیح را نگه دارد، و عدد نمونه‌ی ‎16777217‎ در ابزار بالا همین را نشان می‌دهد.

2.7 داده در حافظه

حافظه‌ی اصلی را می‌توان صف بلندی از بایت‌ها تصور کرد که هر کدام شماره‌ای دارند؛ این شماره آدرس بایت است و در بخش ششم زیاد از آن استفاده می‌کنیم. هر متغیری که در برنامه تعریف می‌کنیم تعدادی بایت اشغال می‌کند. اندازه‌ی نوع‌های پایه در یک سیستم رایج این است:

#include <stdio.h>

int main(void)
{
    printf("char   : %zu byte\n", sizeof(char));
    printf("int    : %zu bytes\n", sizeof(int));
    printf("float  : %zu bytes\n", sizeof(float));
    printf("double : %zu bytes\n", sizeof(double));
    return 0;
}
char   : 1 byte
int    : 4 bytes
float  : 4 bytes
double : 8 bytes

(این اندازه‌ها روی همه‌ی سیستم‌ها یکسان نیستند؛ فقط char همیشه یک بایت است.) پس یک int در چهار بایت یعنی ۳۲ بیت جا می‌گیرد و با همان مکمل ۲ نوشته می‌شود.

متن هم عدد است

برای نگه داشتن متن، به هر نویسه یک عدد نسبت می‌دهیم. قدیمی‌ترین جدول رایج ASCII است که هر نویسه‌ی انگلیسی را با یک بایت نشان می‌دهد: A برابر ۶۵، B برابر ۶۶ و a برابر ۹۷ است. در C نوع char در واقع یک عدد صحیح کوچک است، و این برنامه همان عدد را به‌صورت نویسه و عدد چاپ می‌کند:

#include <stdio.h>

int main(void)
{
    char c = 'A';

    printf("%c = %d\n", c, c);
    printf("%c = %d\n", c + 1, c + 1);
    printf("%c = %d\n", 'a', 'a');
    return 0;
}
A = 65
B = 66
a = 97

برای حرف‌های فارسی و زبان‌های دیگر یک بایت کافی نیست. امروز قالب UTF-8 رایج‌ترین روش است: نویسه‌های انگلیسی همان یک بایت ASCII را دارند، ولی حرف‌های فارسی معمولاً دو بایت و بعضی نمادها تا چهار بایت جا می‌گیرند. در ابزار زیر هر متنی بنویسید و بایت‌های واقعی‌اش را ببینید. بخش کم‌رنگِ هر بایت، بیت‌های ثابتِ قالب UTF-8 است که طول نویسه را مشخص می‌کنند:

Loading...

2.8 تمرین

تمرین ۱. عدد دودویی ‎101101‎ را به دهدهی تبدیل کنید. بزرگ‌ترین عدد بدون علامتی که با ۱۰ بیت می‌توان نوشت چیست؟

تمرین ۲. عدد ۲۰۰ را به دودویی و هگزادسیمال تبدیل کنید. سپس عدد ‎0x3F‎ را به دودویی و دهدهی تبدیل کنید.

تمرین ۳. مقدار ‎-5‎ را در یک بایت با مکمل ۲ بنویسید. سپس ‎1011 + 0110‎ را در دودویی جمع کنید و حاصل را به دهدهی برگردانید.

تمرین ۴. کلمه‌ی Hi و کلمه‌ی «سلام» هر کدام در UTF-8 چند بایت جا می‌گیرند؟ چرا؟


فصل ۳ : C و محیط برنامه‌نویسی

3.1 زبان C

زبان C را دنیس ریچی حدود سال‌های ۱۹۷۲ و ۱۹۷۳ در آزمایشگاه‌های بل ساخت تا با آن سیستم‌عامل یونیکس را بنویسد. نتیجه چنان موفق بود که هسته‌ی یونیکس به C بازنویسی شد و همین رویکرد در سیستم‌عامل‌های بعدی، از جمله لینوکس، ادامه پیدا کرد. بیش از پنجاه سال بعد، C هنوز در هسته‌ی سیستم‌عامل‌ها، سیستم‌های نهفته (مثل کنترلر ماشین لباسشویی و خودرو) و بخش‌های سنگین بسیاری از نرم‌افزارها به کار می‌رود، و نحو زبان‌هایی مثل C++، Java و JavaScript از آن الهام گرفته است.

چرا درس برنامه‌سازی را با C شروع می‌کنیم؟ چون زبان کوچکی است و به سخت‌افزار نزدیک است: همان چیزهایی که در فصل ۲ دیدیم، مثل بایت‌ها، اندازه‌ی نوع‌ها و آدرس‌های حافظه، در C مستقیم دیده می‌شوند. کسی که C را خوب بفهمد، زبان‌های دیگر را راحت‌تر یاد می‌گیرد.

3.2 اولین برنامه

سنت برنامه‌نویسی این است که اولین برنامه‌ی هر زبان چاپ جمله‌ی «Hello, world» باشد. (این سنت از آموزش‌های برایان کرنیگان در دهه‌ی ۱۹۷۰ شروع شد و با کتاب «زبان برنامه‌نویسی C» مشهور شد.)

#include <stdio.h>

int main(void)
{
    printf("Hello, world\n");
    return 0;
}
Hello, world

برنامه فقط هفت خط است، ولی همه‌ی ساختار اصلی یک برنامه‌ی C را دارد:

  • خطِ ‎#include <stdio.h>‎ به کامپایلر می‌گوید توضیحاتِ توابع ورودی و خروجی را از فایل ‎stdio.h‎ بیاورد. بدون آن، printf ناشناخته است.

  • بخش ‎int main(void)‎ تابع اصلی است؛ اجرای برنامه همیشه از اولین خطِ main شروع می‌شود. int یعنی main در پایان یک عدد صحیح به سیستم‌عامل برمی‌گرداند، و void یعنی ورودی ندارد.

  • آکولادها ‎{ }‎ مرز بدنه‌ی تابع را مشخص می‌کنند. دستورهای داخل آن به ترتیب اجرا می‌شوند.

  • دستور printf متن را چاپ می‌کند، و ‎\n‎ نویسه‌ی «خط جدید» است. هر دستور با ‎;‎ تمام می‌شود.

  • دستور ‎return 0‎ برنامه را تمام می‌کند و صفر، یعنی «همه‌چیز درست بود»، را به سیستم‌عامل می‌دهد.

برنامه را قدم‌به‌قدم دنبال کنید:

Loading...

3.3 محیط برنامه‌نویسی

برای نوشتن و اجرای برنامه‌ی C به یک کامپایلر و یک ویرایشگر نیاز داریم. پرکاربردترین کامپایلر gcc است. نصب آن:

سیستم‌عاملنصب
لینوکس (Debian و Ubuntu)دستور ‎sudo apt install gcc‎
لینوکس (Fedora)دستور ‎sudo dnf install gcc‎
لینوکس (Arch)دستور ‎sudo pacman -S gcc‎
سیستم‌عامل macOSدستور ‎xcode-select --install‎ (کامپایلر Apple با نام gcc نصب می‌شود)
ویندوزنصب MSYS2 (MinGW-w64)، یا فعال‌سازی WSL با دستور ‎wsl --install‎ و استفاده از دستورهای لینوکس

بعد از نصب، کد را در فایلی مثل ‎hello.c‎ ذخیره می‌کنیم و در ترمینال می‌نویسیم:

gcc -Wall -Wextra -std=c11 hello.c -o hello
./hello

دستور اول برنامه را کامپایل می‌کند و فایل اجرایی hello را می‌سازد (در ویندوز ‎hello.exe‎)، و دستور دوم آن را اجرا می‌کند. گزینه‌های ‎-Wall‎ و ‎-Wextra‎ کامپایلر را وادار می‌کنند درباره‌ی کدهای مشکوک هشدار بدهد؛ همیشه از آن‌ها استفاده کنید. برای نوشتن کد یک ویرایشگر ساده (مثل VS Code) کافی است، یا یک IDE مثل Code::Blocks که ویرایشگر، کامپایلر و اجرا را در یک برنامه جمع می‌کند. اگر فعلاً نمی‌خواهید چیزی نصب کنید، کامپایلرهای آنلاین مثل Compiler Explorer و OnlineGDB هم برای شروع مناسب‌اند.

3.4 کامپایلر و مفسر

پردازنده C را نمی‌فهمد؛ فقط دستورهای عددیِ خودش را اجرا می‌کند. پس کسی باید برنامه را ترجمه کند. دو روش کلی وجود دارد. کامپایلر مثل مترجمی است که کل کتاب را یک‌بار ترجمه می‌کند و نسخه‌ی ترجمه‌شده را تحویل می‌دهد؛ بعد از آن هر بار فقط همان نسخه خوانده می‌شود. مفسر مثل مترجم هم‌زمان است که هر بار جمله‌به‌جمله ترجمه می‌کند و اجرا می‌کند.

کامپایلرمفسر
زمان ترجمهیک‌بار، قبل از اجراهنگام اجرا، دستور به دستور
نتیجهیک فایل اجرایی مستقلچیزی ساخته نمی‌شود و برای اجرا مفسر لازم است
سرعت اجرامعمولاً سریع‌ترمعمولاً کندتر
نمونهزبان Cزبان Python

کامپایل کردن یک برنامه‌ی C در واقع چهار مرحله دارد که دستور gcc همه را پشت‌سرهم انجام می‌دهد. در ابزار زیر به‌جای نمونه‌ی ساختگی، محتوای واقعیِ فایل‌های هر مرحله را برای همین ‎hello.c‎ می‌بینید:

Loading...

(محتوای مرحله‌های میانی بسته به سیستم و کامپایلر شما فرق می‌کند؛ این‌ها روی لینوکس x86-64 با gcc گرفته شده‌اند. فایل‌های میانی را می‌توانید خودتان با گزینه‌های ‎-E‎، ‎-S‎ و ‎-c‎ بسازید.) مهم‌ترین نکته این است که در پایان یک فایل اجرایی داریم که برای اجرا دیگر به C و کامپایلر نیاز ندارد.

3.5 وقتی برنامه کار نمی‌کند

همه‌ی برنامه‌نویس‌ها خطا می‌کنند؛ مهارت واقعی پیدا کردن و رفع سریع آن است. به خطا در برنامه‌ها معمولاً «باگ» می‌گویند. یک داستان معروف: در سال ۱۹۴۷ گروه گریس هوپر پروانه‌ای را که در یکی از رله‌های کامپیوتر Harvard Mark II گیر کرده بود در دفتر ثبت چسباند و نوشت «اولین مورد واقعیِ پیدا شدن باگ». البته واژه‌ی bug پیش‌تر هم برای ایرادهای فنی به کار می‌رفت. سه نوع خطا داریم که مهم است آن‌ها را از هم تشخیص دهید.

خطای نحوی (Syntax Error)

نوشتن برنامه برخلاف قاعده‌ی زبان، مثل غلط نوشتن یک جمله. کامپایلر چنین برنامه‌ای را اصلاً کامپایل نمی‌کند و محل خطا را گزارش می‌دهد. این کد بعد از printf یک ‎;‎ کم دارد:

#include <stdio.h>

int main(void)
{
    printf("Hello, world\n")
    return 0;
}

پیام کامپایلر:

error_syntax.c: In function ‘main’:
error_syntax.c:5:29: error: expected ‘;’ before ‘return’
    5 |     printf("Hello, world\n")
      |                             ^
      |                             ;
    6 |     return 0;

پیام را بخوانید: ‎5:29‎ یعنی خط ۵، ستون ۲۹، و می‌گوید پیش از return یک ‎;‎ انتظار داشت. گاهی کامپایلر خطا را در خطِ بعد از ایراد واقعی گزارش می‌کند، پس اگر در خطِ گزارش‌شده چیزی ندیدید، خطِ قبلش را هم نگاه کنید.

خطای زمان اجرا (Runtime Error)

برنامه کامپایل می‌شود و شروع به اجرا می‌کند، ولی وسط کار چیزی غیرممکن از آن خواسته می‌شود و می‌ایستد. مثلاً تقسیم بر صفر:

#include <stdio.h>

int main(void)
{
    int d;

    scanf("%d", &d);
    printf("%d\n", 100 / d);
    return 0;
}

اگر کاربر ‎0‎ را وارد کند، پردازنده نمی‌تواند تقسیم کند و سیستم‌عامل برنامه را می‌بندد:

0
Floating point exception (core dumped)

(متن دقیق پیام به سیستم و پوسته بستگی دارد؛ نام «Floating point» تاریخی است و برای تقسیم صحیح بر صفر هم دیده می‌شود.)

خطای منطقی (Logic Error)

برنامه کامپایل می‌شود، اجرا می‌شود، تمام می‌شود، ولی جواب غلط است. کامپیوتر هیچ خبری نمی‌دهد، چون دقیقاً همان کاری را که نوشته‌اید انجام داده است. این برنامه باید میانگین ۱۸ و ۱۲ را حساب کند:

#include <stdio.h>

int main(void)
{
    int a = 18, b = 12;

    printf("average = %d\n", a + b / 2);
    return 0;
}
average = 24

جواب باید ‎15‎ باشد. مشکل اولویت عملگرهاست: تقسیم قبل از جمع انجام می‌شود، پس ‎a + b / 2‎ یعنی ‎18 + 6‎. باید ‎(a + b) / 2‎ نوشت. این نوع خطا سخت‌ترین است، چون فقط وقتی پیدایش می‌کنید که خروجی را با جواب درستِ مورد انتظار مقایسه کنید.

نوع خطاکی پیدا می‌شود؟کامپیوتر خبر می‌دهد؟
نحویهنگام کامپایلبله، با پیام و شماره‌ی خط
زمان اجراهنگام اجرابله، برنامه با پیام می‌ایستد
منطقیبا مقایسه‌ی خروجی با جواب درستنه

3.6 ابزارهای خطایابی و تست

چند ابزار ساده کار پیدا کردن خطا را خیلی راحت می‌کنند.

هشدارهای کامپایلر. با گزینه‌های ‎-Wall -Wextra‎ کامپایلر کدهای مشکوکِ بدون خطا را هم گزارش می‌دهد. برنامه‌ای که مقدار یک متغیر را پیش از مقداردهی چاپ می‌کند:

#include <stdio.h>

int main(void)
{
    int x;

    printf("%d\n", x);
    return 0;
}

کامپایل با ‎-Wall -Wextra‎:

warning_uninit.c: In function ‘main’:
warning_uninit.c:7:5: warning: ‘x’ is used uninitialized [-Wuninitialized]
    7 |     printf("%d\n", x);
      |     ^~~~~~~~~~~~~~~~~
warning_uninit.c:5:9: note: ‘x’ was declared here
    5 |     int x;
      |         ^

هشدار را جدی بگیرید: متغیر x هیچ مقداری ندارد و چاپ آن نتیجه‌ی نامعلومی می‌دهد. اکثر هشدارها نشانه‌ی خطای منطقی‌اند.

چاپ برای ردیابی. ساده‌ترین روش خطایابی این است که در چند نقطه‌ی برنامه با printf مقدار متغیرها را چاپ کنید و ببینید از کجا به بعد از مقدار مورد انتظار فاصله می‌گیرند.

دستور assert. با نوشتن ‎assert(condition)‎ می‌گویید «این شرط همیشه باید درست باشد». اگر نبود، برنامه همان‌جا با پیام روشنی می‌ایستد:

#include <assert.h>
#include <stdio.h>

int main(void)
{
    int n = -5;

    assert(n > 0);
    printf("n is positive\n");
    return 0;
}
assert_demo: assert_demo.c:8: main: Assertion `n > 0' failed.

دیباگر. برنامه‌ی gdb اجازه می‌دهد اجرا را متوقف کنید و مقدار متغیرها را ببینید. برنامه را با گزینه‌ی ‎-g‎ کامپایل کنید و این دستورها را به کار ببرید: ‎gdb ./prog‎ برای شروع، ‎break main‎ برای توقف ابتدای main، run برای اجرا، next برای رفتن به خط بعد، ‎print x‎ برای دیدن مقدار x و quit برای خروج.

تست با ورودی‌های مختلف. یک برنامه که برای یک ورودی کار می‌کند لزوماً درست نیست. همیشه حالت‌های خاص را امتحان کنید: صفر، عدد منفی، عدد خیلی بزرگ، و ورودی‌ای که مسیر «خیر» را فعال می‌کند.

3.7 کد تمیز

برای کامپایلر فرقی نمی‌کند که برنامه را چطور بنویسید، اما برای شما و هر کس دیگری که کد را می‌خواند فرق بزرگی دارد. این دو برنامه دقیقاً یک کار می‌کنند:

#include <stdio.h>
int main(void){int a=18,b=15,c=17;double x=(a+b+c)/3.0;printf("average = %.2f\n",x);return 0;}
#include <stdio.h>

int main(void)
{
    int score1 = 18, score2 = 15, score3 = 17;
    double average = (score1 + score2 + score3) / 3.0;

    printf("average = %.2f\n", average);
    return 0;
}
messy → average = 16.67
clean → average = 16.67

برنامه‌ی دوم را راحت‌تر می‌شود خواند، تغییر داد و ایرادش را پیدا کرد. قاعده‌های اصلی کد تمیز:

  • اسم متغیر معنی داشته باشد: score1 بهتر از a، و average بهتر از x.

  • هر دستور در یک خط باشد و داخل آکولادها چهار فاصله تورفتگی داشته باشد.

  • بین بخش‌های منطقی کد یک خط خالی بگذارید.

  • توضیح (comment) را برای «چرا» بنویسید، نه «چه»: با ‎/* … */‎ یا ‎// …‎ می‌توان توضیح نوشت و کامپایلر آن را نادیده می‌گیرد.

  • سبک نوشتن در کل برنامه یکسان باشد (جای آکولاد، اسم‌گذاری و …).

از همین حالا عادت کنید کد تمیز بنویسید. آدم‌ها کد را بیشتر از آنچه می‌نویسند می‌خوانند.

3.8 تمرین

تمرین ۱. برنامه‌ای بنویسید که در دو خط جداگانه اسم شما و یک جمله‌ی دلخواه را چاپ کند.

تمرین ۲. این برنامه سه خطای نحوی دارد. پیدا و اصلاحشان کنید.

#include <stdio.h>

int main(void)
{
    printf("Hello")
    printf("world\n);
    return 0
}

تمرین ۳. نوع هر خطا را مشخص کنید: (الف) برنامه به‌خاطر یک ‎;‎ فراموش‌شده کامپایل نمی‌شود. (ب) برنامه برای ورودی ‎0‎ می‌ایستد. (پ) برنامه میانگین را ۲۴ چاپ می‌کند و باید ۱۵ باشد.

تمرین ۴. الگوریتم تمرین ۱ فصل ۱ (زوج یا فرد بودن) را به C بنویسید. علامت ‎%‎ باقی‌مانده‌ی تقسیم را می‌دهد.


جمع‌بندی بخش

در این بخش یک مسیر کامل را طی کردیم: از ایده‌ی یک روش حل مسئله، تا نوشتن و کشیدنش، تا فهمیدن اینکه کامپیوتر چطور آن را اجرا می‌کند، و در نهایت اولین برنامه‌ی C. مهم‌ترین نکته‌ها:

فصل ۱: الگوریتم

  • الگوریتم: دنباله‌ی محدودی از دستورهای دقیق و بی‌ابهام که ورودی را به خروجی می‌رساند و حتماً تمام می‌شود.

  • شبه‌کد و فلوچارت: دو راه برای نوشتن و کشیدن الگوریتم. لوزی تصمیم است و فلش برگشتی حلقه.

  • کارایی: دو الگوریتم درست می‌توانند خیلی از نظر سرعت فرق کنند. در بازی حدس عدد، نیم‌کردن بازه، ۱۰۰ حدس را به ۷ حدس می‌رساند.

فصل ۲: کامپیوتر و داده

  • چرخه‌ی پردازنده: واکشی، رمزگشایی و اجرا. برنامه هم مثل داده در حافظه نگه داشته می‌شود.

  • مبناها: کامپیوتر دودویی است؛ هگز راه کوتاه نوشتن بیت‌هاست و هر رقمش چهار بیت است.

  • عدد صحیح با علامت: مکمل ۲ با وزن منفی برای بیت سمت چپ. اگر نتیجه از بازه بیرون برود، سرریز رخ می‌دهد.

  • عدد اعشاری: قالب IEEE 754 با علامت، توان و مانتیس. خیلی از اعداد (مثل ‎0.1‎) دقیقاً قابل ذخیره نیستند.

  • متن: هر نویسه یک عدد است. ASCII یک بایت و UTF-8 برای حرف‌های فارسی معمولاً دو بایت.

فصل ۳: C و ابزارها

  • هر برنامه‌ی C از main شروع می‌شود و دستورهایش با ‎;‎ تمام می‌شوند.

  • کامپایل چهار مرحله دارد: پیش‌پردازش، کامپایل، اسمبل و پیوند. نتیجه یک فایل اجرایی مستقل است.

  • سه نوع خطا: نحوی (کامپایلر خبر می‌دهد)، زمان اجرا (برنامه می‌ایستد) و منطقی (هیچ خبری نمی‌آید).

  • ابزارها: هشدارهای ‎-Wall -Wextra‎، چاپ برای ردیابی، assert و دیباگر.

اشتباه‌های رایج

اشتباهچه می‌شود؟راه درست
فراموش‌کردن ‎;‎ در پایان دستورخطای نحوی با پیام ‎expected ';'‎خواندن پیام و نگاه به خط گزارش‌شده و خط قبل از آن
نادیده‌گرفتن هشدارهای کامپایلرخطای منطقی پنهانکامپایل با ‎-Wall -Wextra‎ و رفع همه‌ی هشدارها
مقایسه‌ی اعداد اعشاری با ‎==‎نتیجه‌ی غیرمنتظره، مثل ‎0.1 + 0.2‎مقایسه‌ی اختلاف با یک مقدار بسیار کوچک
فراموش‌کردن محدودیت بازه‌ی عددسرریز و دور زدن مقدارانتخاب نوعی که بازه‌ی کافی دارد
نوشتن الگوریتم بدون شرط پایانحلقه‌ی بی‌پایانبررسی ویژگی پایان‌پذیری پیش از کدنویسی
اعتماد به خروجی بدون آزمونخطای منطقیامتحان با چند ورودی، از جمله حالت‌های خاص

بخش بعد

در بخش بعد با متغیرها و نوع‌های داده (int، float، double، char) و عملگرها آشنا می‌شویم. هر چیزی که در فصل ۲ درباره‌ی بیت‌ها، بازه‌ی عددها و سرریز دیدید، آن‌جا مستقیم به کار می‌آید. همچنین ورودی و خروجی با printf و scanf را که این‌جا دیدید، دقیق‌تر یاد می‌گیریم.