وب سایت شخصی سجاد رفاقت

شمارنده‌ی چندرقمی همه‌کاره

گاهی وقت‌ها لازم است حلقه‌های تکرار تودرتو برای شبیه‌سازی شمارنده بکار ببریم. اگر تعداد این حلقه‌ها از قبل مشخص نباشد چگونه می‌توان این‌کار را انجام داد؟ ابتدا به یک مسئله‌ی نمونه توجه کنید:

برنامه‌ای بنویسید که با دریافت عدد مثبت تک رقمی n، کلیه‌ی عددهای طبیعی که با ارقام 2، 3، 4، 5 و 7 ساخته می‌شوند را در خروجی چاپ کند. برای راحتی کار فرض کنید که تکرار ارقام مجاز است.

مثلا به ازای n = 2 باید اعداد 22، 23، 24، 25، 27، 32، 33، 34، 35، 37، 42، 43، 44، 45، 47، 52، 53، 54، 55، 57، 72، 73، 74، 75 و 77 را تولید کند.

اگر از قبل مقدار n برابر 2 تعیین شود، یک نمونه پیاده سازی به زبان C++ می‌تواند اینگونه باشد:

Copy #include <iostream>
using namespace std;
int main() {
  int D[] = { 2, 3, 4, 5, 7 }, DG_COUNT = 5, I, J, M;
  for (I = 0; I < DG_COUNT; I++)
    for (J = 0; J < DG_COUNT; J++) {
      M = D[I] * 10 + D[J];
      cout << M << " ";
    }
}

حال اگر مقدار n را برابر 4 در نظر بگیریم، حلقه‌های تودرتو را باید به 4 افزایش دهیم:

Copy #include <iostream>
using namespace std;
int main() {
  int D[] = { 2, 3, 4, 5, 7 }, DG_COUNT = 5, I, J, K, L, M;
  for (I = 0; I < DG_COUNT; I++)
    for (J = 0; J < DG_COUNT; J++)
      for (K = 0; K < DG_COUNT; K++)
        for (L = 0; L < DG_COUNT; L++) {
          M = D[I] * 1000 + D[J] * 100 + D[K] * 10 + D[L];
          cout << M << " ";
        }
}

می‌خواهیم روش کلی و مستقل از n پیدا کنیم و در زمان اجرا بتوانیم بر حسب nهای دلخواه مسئله را حل کنیم لذا نمی‌توان از حلقه‌های تودرتو استفاده کرد و به سراغ روش‌های دیگری می‌رویم.

بنظرم استفاده از شمارنده ایده‌ی خوبی برای پیاده‌سازی اینگونه مسائل باشد. شمارنده‌ای که بتوان تعداد ارقام آن و همچنین مقادیر مجاز ارقام را بطور دلخواه در زمان اجرای برنامه تعیین کرد. کلاس Counter یک شمارنده‌ی چند رقمی را ارائه می‌کند (فایل Counter.h):

Copy #pragma once
class Counter {
public:
  Counter(int);
  int getLEN();
  void setDigits(int, int[]);
  void Reset();
  int getVolume();
  int getValue(int);
  int getCounter();
  void Inc();
private:
  int D[9], LEN, DIGIT_COUNT, DIGIT[9];
};

من متدهای لازم را برای داشتن یک شمارنده‌ی ساده را در این کلاس قرار داده‌ام، شاید شما بخواهید آن را کمی ارتقاء دهید. مثلا اضافه کردن متد Dec() برای شمارش معکوس، یا Initialize(int) برای تنظیم مقدار اولیه‌ی دلخواه بجای شروع از صفر و...
به هر حال پیاده سازی متدهای کلاس (فایل Counter.cpp) به قرار زیر است:

Copy #include "Counter.h"
#include <math.h>
Counter::Counter(int Length) {
  LEN = Length;
  Reset();
}
int Counter::getLEN() {
  return LEN;
}
void Counter::setDigits(int DigitsCount, int Digits[]) {
  DIGIT_COUNT = DigitsCount;
  for (int i = 0; i < 9; i++)
    DIGIT[i] = Digits[i];
}
void Counter::Reset() {
  for (int i = 0; i < LEN; i++)
  D[i] = 0;
}
int Counter::getVolume() {
  return pow(DIGIT_COUNT, LEN);
}
int Counter::getValue(int Digit) {
  return DIGIT[D[Digit]];
}
int Counter::getCounter() {
  int COUNTER = 0;
  for (int I = LEN - 1; I >= 0; I--)
    COUNTER = COUNTER * 10 + getValue(I);
  return COUNTER;
}
void Counter::Inc() {
  int I = 0, FLAG = 0;
  D[0]++;
  while (D[I] > DIGIT_COUNT - 1) {
    I++;
    if (I < LEN)
      D[I]++;
    for (int J = 0; J < I; J++)
      D[J] = 0;
  }
}

با این شمارنده، هر تعداد رقم را فقط با یک حلقه تکرار می‌توان تولید کرد. بطور مثال اگر بخواهیم با همان ارقام 2، 3، 4، 5 و 7 همه‌ی اعداد 4 رقمی را تولید کنیم، برنامه‌ی زیر این کار را انجام می‌دهد:

Copy #include <iostream>
using namespace std;
int main() {
  Counter C(4);
  int R[] = { 2, 3, 4, 5, 7 };
  C.setDigits(5, R);
  for (int i = 0; i < C.getVolume(); i++) {
    cout << C.getCounter() << " ";
    C.Inc();
  }
}

خروجی برنامه فوق به این شکل است: