مساله 78 - صفحه 70 کتاب «مساله‌های الگوریتمی»: چاپ‌گر خطی

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

برنامه‌ای بنویسید که کار چنین چاپگری را شبیه سازی کند و زمان چاپ متن داده شده را به‌دست آورد.

اطلاعات مربوط به چاپ‌گر در فایل ورودی INPUT.TXT نوشته شده است. در این فایل، در یک سطر به‌ترتیب نویسه‌هایی که روی تسمه حک شده‌اند نوشته شده است. فرض کنید که همه‌ی این نویسه‌ها دارای کد اسکی بین 30 و 127 هستند. توجه کنید که هر نویسه ممکن است در بیش از یک جای تسمه حک شده باشد. همچنین دقت کنید که تسمه بصورت حلقه‌ای است، یعنی نویسه‌ی آخر این سطر روی تسمه در مجاورت نویسه‌ی اول است. چرخش تسمه به‌این صورت است که در لحظه t = 0، نویسه‌ی اول سطر در مقابل موقعیت اول، نویسه‌ی دوم در مقابل موقعیت دوم و... قرار گرفته است و در لحظه‌ی t = 1، نویسه‌ی دوم سطر در مقابل موقعیت اول، نویسه سوم در مقابل موقعیت دوم و... قرار گرفته است. تعداد نویسه‌های حک شده روی تسمه از 255 تا بیشتر نیست.

فایلی که باید چاپ شود FILE.TXT نام دارد. فرض کنید که این فایل حداکثر 1000 سطر و هر سطر آن حداکثر 100 نویسه دارد. همچنین فرض کنید که طول هر سطر این فایل از نصف تعداد نویسه‌های روی تسمه بیشتر نیست.

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

حل مساله

سورس برنامه به زبان C++ را در پایین ملاحظه می‌کنید:

1#include <fstream>
2#include <string.h>
3using namespace std;
4void main() {
5  char CHARS[256], LINE[101];
6  int CH_COUNT, PRINT, LL, POINT = 0, TIME = 0, I;
7  fstream IN, FILE, OUT;
8  IN.open("INPUT.txt", ios::in);
9  IN.getline(CHARS, 255);
10  IN.close();
11  CH_COUNT = strlen(CHARS);
12  FILE.open("FILE.txt", ios::in);
13  while (!FILE.eof()) {
14    FILE.getline(LINE, 100);
15    LL = strlen(LINE);
16    PRINT = 0;
17    while (PRINT < LL) {
18      for (I = 0; I < LL; I++)
19        if (LINE[I] == CHARS[(I + POINT) % CH_COUNT]) {
20          LINE[I] = 0;
21          PRINT++;
22        }
23      POINT = (POINT + 1) % CH_COUNT;
24      TIME++;
25    }
26  }
27  FILE.close();
28  OUT.open("OUTPUT.txt", ios::out);
29  OUT << TIME - 1;
30  OUT.close();
31}