تجربه‌های پراکنده‌ی یک مسعود
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.

نکته‌ای در مورد کلاس‌ها و مجموعه‌ها در ++C

[بازگشت به فهرست]
بررسی روش تعریف کلاس برای قابلیت استفاده از ظرف‌های مجموعه (set و unordered_set) در زبان برنامه‌نویسی ++C

زبان برنامه‌نویسی ++C دو کلاس set و unordered_set رو برای پیاده‌سازی مفهوم مجموعه (ظرفی با عناصر غیرتکراری) داره.

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

    کلاس unordered_set از hashing برای بررسی یکسان بودن عناصر استفاده می‌کنه. بنابراین باید عملکرد hash برای کلاس دلخواه خودمون رو تعریف کنیم. اما طراحی عملگر hash کارا و بدون تداخل لزوما راحت نیست و ممکن‌ه عناصر متفاوت، hash یکسانی رو تولید کنن. به همین دلیل علاوه بر پیاده‌سازی متد hash باید عملگر == هم پیاده شه تا در صورت برابر بودن hash دو عنصر، یکسان بودن اون دو از طریق عملگر == هم بررسی شه. این کار یک حسن بزرگ داره که لازم نیست درگیر طراحی hash دقیق و بدون تداخل باشیم و حتی اگر تداخلی داشتیم، عملگر == هم برای تشخیص تمایز فراخوانی می‌شه.

ادامه ...


نکته‌ای در استفاده از map

[بازگشت به فهرست]
نکته‌ای در مورد استفاده از ساختمان داده‌ی map با مثالی به زبان برنامه‌نویسی ++C

ساختمان داده‌ی map (یا dictionary) از ابزارهای مهم و کاربردی هر زبان برنامه‌نویسی‌ه که برای برقراری نگاشت بین هر نوع کلید و مقدار متناظر استفاده می‌شه. آرایه‌های معمولی یه عدد صحیح رو به عنوان کلید به یه مقدار از هر نوع کلاس یا نوع داده نگاشت می‌کنن. اما وقتی از map استفاده می‌کنیم، این امکان بهمون داده می‌شه که از اشیاء کلاس‌ها و انواع داده‌های پیش‌فرض هر زبان برنامه‌نویسی به عنوان کلید استفاده کنیم. پس مشخصه که پیاده‌سازی خیلی از عملیات‌ها رو ساده‌تر می‌کنه و کمک بزرگی به حساب می‌یاد.

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

 1  int main(){
 2      const int size = 700000;
 3      int a[size];
 4      map<int, int> b;
 5      clock_t tStart;
 6      double cps = CLOCKS_PER_SEC;
 7      a[0] = b[0] = 0;
 8      a[1] = b[1] = 1;
 9      tStart = clock();
10      for(int i = 2 ; i < size ; i++)
11          a[i] = a[i - 1] + a[i - 2];
12      cout << "Time for array: " << (clock() - tStart) / cps << "s" <<  endl;
13      tStart = clock();
14      for(int i = 2 ; i < size ; i++)
15          b[i] = b[i - 1] + b[i - 2];
16      cout << "Time for map: " << (clock() - tStart) / cps << "s" << endl;
17      return 0;
18  }

ادامه ...


محاسبه‌ی فاکتوریل اعداد بزرگ

[بازگشت به فهرست]
چطور شاخ غول فاکتوریل را بشکنیم

چند روز پیش که با بچه‌ها نمونه سوالات ACM رو حل می‌کردیم، یه جایی به عدد 123456789 خوردیم و این سوال پیش اومد که می‌شه فاکتوریل این عدد رو حساب کرد؟

    ما معمولا برای توضیح رشد با سرعت زیاد از عبارت «رشد نمایی» استفاده می‌کنیم. رشد نمایی یعنی هر گام که پیش می‌ریم، از گام $n$ به گام $n + 1$، اندازه دو یا هر چند برابری می‌شه که به اون پایه یا مبنای رشد هم می‌گن. این پایه همیشه ثابت می‌مونه. یعنی چه مرحله‌ی اول باشیم و چه مرحله‌ی هزارم، همیشه مرحله‌ی بعدی ضرب در عدد ثابتی می‌شه. در حالت کلی می‌شه نوشت:

\[ f(n ) = b \times f(n - 1 ),\; f(0) = c \]

    منظور از b همون پایه‌ی رشد هست. مثلا اگه $b = 2$ باشه و $f(0 ) = 1$، به تابع $f(n) = 2^n$ می‌رسیم. این تعریف رو با تعریف فاکتوریل مقایسه کنید:

ادامه ...