حسین می‌خواهد تعداد زیادی عدد صحیح را که هرکدام در بازه‌ی ‎$[0‎, ‎2^{28}-1]$‎ قرار دارند (با یک ترتیب خاص) نگه‌داری کند. بالطبع حسین هم، مانند ما، می‌داند که یک روش نگه‌داری این اعداد استفاده از یک آرایه‌ی int‎ است؛ اما از آن‌جا که تعداد زیادی از اعداد حسین کوچک هستند (و مثلاً در حالت طبیعی در char یا ‎short‎ جا می‌شوند)، حسین نمی‌خواهد برای همه‌ی اعداد ‎۴‎ بایت حافظه مصرف کند.

پس از بررسی‌های زیاد، حسین تصمیم گرفت هر عدد را به‌صورت ‎«چند بایت متوالی‎» کد کند که اوّلاً حافظه‌ی کم‌تری (در مقایسه با حالت تمام int‎ مصرف شود)، ثانیاً آرایه‌ی بایت‌های متوالی (حاصل از چسباندن کدهای این اعداد) قابل تفکیک باشد. دقت کنید که اگر برای مثال، حسین تنها به نوشتن اعداد در حداقل تعداد بایت و چسباندن آن‌ها به‌هم اکتفا کند، آن‌وقت معلوم نیست آرایه‌ی ‎$\{\underline{0000 0001}‎, ‎\ \underline{1111 1110}‎, ‎\ \dots\}$‎ با دو عنصر ‎۱‎ و ‎۲۵۴ (از چپ به راست) شروع می‌شود یا یک عنصر ‎۵۱۰‎ یا مقادیر دیگر.

روش حسین چنین است که برای هر یک از اعداد، ابتدا آن عدد را در مبنای دو می‌نویسد. سپس بیت‌های آن‌را در دسته‌های ‎۷‎ بیتی (و نه ‎۸‎‎ بیتی) دسته‌بندی می‌کند. نهایتاً قبل از ‎۷‎ بیتِ دسته‌ی آخر ‎(کم‌ارزش‌ترین)‎ یک بیت صفر و قبل از ‎۷‎ بیتِ سایر دسته‌ها (در صورت وجود) یک بیت ‎۱‎ قرار می‌دهد. برای مثال عدد ‎$1387 = (1010\ 1101011)_2$‎ به‌صورت دو دسته‌ی ‎$\{00001010‎, ‎1101011\}$‎ در می‌آید که حسین قبل از دسته‌ی‌آخر ‎($1101011$)‎ یک بیت صفر و قبل از سایر دسته‌ها یک بیت ‎۱‎ قرار می‌دهد تا در پایان کار ‎$1387$‎ را با دو بایت ‎$10001010‎, ‎01101011$‎ نمایش بدهد. هم‌چنین عدد ‎$42051 = (10\ 1001000\ 1000011)_2$‎ با ‎۳‎ بایت به‌صورت ‎$1000 0010‎, ‎1100 1000‎, ‎0100 0011$‎ نمایش داده می‌شود.

الف) چرا در این روش مقدار حافظه‌ی مصرفی از حالتی که تمام اعداد در ‎int‎ ذخیره شوند، بیش‌تر نمی‌شود؟

ب) آیا یک آرایه‌ی بایت‌های متوالی از اعداد کد شده به‌این روش، قابل تفکیک (بازگشت به اعداد اوّلیه) است؟ برای این‌کارالگوریتمی به‌زبان فارسی نوشته و آن را روی آرایه‌ی ‎$\{1100 1011‎, ‎1000 0000‎, ‎0000 0001‎, ‎0111 1110‎, ‎0000 0001‎, ‎1000 1000‎, ‎0111 0111\}$‎ اجرا کنید تا اعداد اوّلیه به‌دست بیایند. لازم نیست اعداد اوّلیه را به مبنای ‎۱۰‎ برگردانید‎!‎

ج) تابع int CodeThis(int number‎, ‎unsigned char c) را برای کد کردن اعداد بنویسید.

در این تابع number عدد مورد نظر (مثل ‎۱۳۸۷‎ در بالا) است. این تابع باید بایت‌های ساخته شده را (از پرارزش به کم‌ارزش) در آرایه‌ی ‎c ریخته و نهایتاً به‌عنوان خروجی تعداد این بایت‌ها را برگرداند. برای مثال خروجی برنامه‌ی روبه‌رو باید 107 138 باشد، که ‎$138=(10001010)_2$‎ و ‎$107=(01101011)_2$‎.

#include <cstdio>
 
int CodeThis(int number, unsigned char c[]) {
  /* You must write the body of this func! */
}
 
int main() {
   unsigned char code[4];
   int codelen = CodeThis(1387, code);
   for (int i=0; i<codelen; i++)
      printf("%d ", (int)code[i]);
   printf("\n");
   return 0;
}

د) یکی از مزایای این شیوه‌ی ارسال و دریافت متغیرها به‌عنوان ورودی و خروجی تابع ‎CodeThis (این‌که خروجی تابع تعداد بایت‌های کد شده است) امکان کد کردن متوالی چند عدد در یک دستور است، طوری که کدهای آن‌ها پشت سر هم قرار بگیرند.

در یک دستور (یک خط کد C‎) با ‎۳‎ بار فراخوانی تابع CodeThis، ‎۳‎ عدد ‎۶۶‎ و سپس ‎۳۶۵‎ و نهایتاً ‎۷۸۵‎ را به‌صورت کد شده در یک آرایه‌ی ‎۵‎ بایتی قرار دهید، طوری که ابتدا یک بایت کد عدد ‎۶۶‎، سپس دو بایت ‎۳۶۵‎ و بعد از آن نیز دو بایت ‎۷۸۵‎ قرار بگیرد.

ه‍) تابع ‎int DecodeThis(unsigned char c ‎, ‎int clen‎, ‎int a )‎ را برای تبدیل یک آرایه‌ی کد به آرایه‌ای از اعداد صحیح (عکس عمل CodeThis) بنویسید.

در این تابع c‎ آرایه‌ی بایت‌های کد مورد نظر و clen‎ تعداد بایت‌های آن است. این تابع باید اعداد اولیه را به‌دست آورده و آن‌ها را به همان ترتیب در آرایه‌ی ‎a ریخته و به‌عنوان خروجی تعداد این اعداد را برگرداند. برای مثال خروجی برنامه‌ی زیر باید 13 1387‎ باشد.

#include <cstdio>
 
int CodeThis(int number, unsigned char c[]) {
  /* You must write the body of this func! */
}
 
int DecodeThis(unsigned char c[], int clen, int a[]) {
  /* You must write the body of this func, too! */
}
 
int main() {
  unsigned char code[100];
  int codelen = CodeThis(1387, code);
  int newcodelen = CodeThis(13, code+codelen);
  // now code is {138 107 13}
  //           = {10001010 01101011 00001101}
 
  int a[100];
  int numlen = DecodeThis(code, newcodelen, a);
  for (int i=0; i<numlen; i++)
    printf("%d ", a[i]);
  return 0;
}

و) برنامه‌ی بنویسید که ابتدا یک عدد ‎$n$‎ و سپس ‎$n$‎ عدد صحیح مثبت و کوچک‌تر از ‎$2^{28}$‎ از ورودی بخواند و آن‌ها را در یک آرایه‌ی unsigned char c کد کند و در خروجی ابتدا درصد حجم کاهش یافته در مقایسه با روش نگه‌داری به‌صورت int‎ چهاربایتی تا ‎۳‎ رقم اعشار ‎ چاپ کند. سپس اعداد را از آرایه‌ی c‎ بازگرداند و آن‌ها را در خروجی چاپ کند. فرض کنید ‎$n \le 1000$‎ است.

شما می‌توانید این برنامه را مستقل از قسمت‌های ج و د و با فرض وجود آن دو تابع بنویسید‎.‎

ز) می‌دانیم هر عنصر آرایه‌ی ‎c‎ یک بایت ‎۸‎ بیتی است که ‎$2^8 = 256$‎ حالت می‌تواند داشته باشد؛ اما یکی از این ‎۲۵۶‎ حالت هرگز در هیچ‌کجای رشته‌ی کد شده ‎©‎ ظاهر نمی‌شود‎!‎ آن عدد کدام است؟

ح) حسین باز هم حجم کم‌تری می‌خواست‎!‎ با بررسی دنباله‌ی اعداد، حسین متوجه شد که تعدادی عدد صفر متوالی (در اعداد صحیح ورودی) وجود دارد. با کمک قسمت و، آیا می‌توانید الگوریتم حسین را طوری بهبود ببخشید که در صورتی که در اعداد وردی تعدادی صفر متوالی وجود داشت، اندازه‌ی کد از اینی که هست هم کوچک‌تر شود؟ دقت کنید که در الگوریتم جدید طول رشته هرگز نباید از طول رشته‌ی الگوریتم قبلی بیش‌تر بشود و بهبودی شما باید برای تمام ورودی طول کم‌تر یا مساوی را ضمانت کند.

در این قسمت نیازی به نوشتن کد نیست و صرف توضیح فارسی کفایت می‌کند.

• سوال بعد