تکنیک های حل الگوریتم به زبان ساده — بخش اول

در این نوشته به معرفی تکنیک‌های بنیادینی می‌پردازیم که هنگام حل همه نوع مسائل الگوریتم به کار می‌آید. البته این نوشته به هیچ وجه یک فهرست جامع محسوب نمی‌شود و مطمئناً می‌توان آن را کامل‌تر کرد. اما به هر جهت در آن تلاش شده تا بسیاری از نکات کلیدی ذکر شوند.

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

ایجاد متغیر شمارنده (Counter)

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

فیلم آموزش طراحی الگوریتم – مرور و تست کنکور ارشد در فرادرس

کلیک کنید

مثلاً ممکن است الگوریتمی از شما بخواهد که تعداد دفعاتی که یک عدد صحیح در آرایه‌ای از اعداد صحیح ظاهر شده است را بشمارید:

function countOfNums(array, num) {
  var count = 0;

for(var i = 0; i < array.length; i++) {
    if(array[i] === num) {
      count++;
    }
  }

return count;
}

var values = [1,2,3,4,3];
var num = 3;

// returns 2
countOfNums(values, num);

همان طور که مشاهده می‌کنید می‌توانیم از متغیر count استفاده کرده و مقدار آن را برابر با 0 قرار دهیم. وقتی که روی آرایه‌ای از اعداد صحیح حلقه‌ای تعریف می‌کنیم و به مقداری که برابر با num باشد می‌رسیم، متغیر count را 1 واحد افزایش می‌دهیم (++count).

محل دیگری که این تکنیک می‌تواند مفید واقع شود، جایی است که الگوریتم از شما می‌خواهد که مجموع مقادیری را بازگردانید. برای نمونه مجموع آرایه‌ای از مقادیر.

function sumOfArray(array) {
  var sum = 0;

for(var i = 0; i < array.length; i++) {
    sum += array[i];
}

return sum;
}

var values = [1,2,3,4,5];

// returns 15
sumOfArray(values);

در این حالت ما sum = 0 قرار می‌دهیم. سپس روی آرایه، حلقه‌ای تعریف می‌کنیم و مقدار [array[i را به مقدار کنونی sum اضافه می‌کنیم.

ایجاد اشاره‌گر سریع و کند

در این تکنیک دو اشاره‌گر را مقداردهی اولیه می‌کنیم که یکی 1 واحد و دیگری 2 واحد افزایش می‌یابد. همین طور که روی فهرستی از مقادیر حرکت می‌کنید، می‌توانید موقعیت هر اشاره‌گر را به‌روزرسانی کرده و اطلاعات مفیدی به دست آورید که می‌تواند برای کارهایی مانند یافتن نقطه میانی فهرست مقادیر مورد استفاده قرار گیرد.

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

function getMiddleElement(linkedList) {
   var node = getHead(linkedList);

   var slow = node;
   var fast = node;

while(fast!=null && fast.next!=null) {
   fast = fast.next.next;
   slow = slow.next;
}

   return slow.data;
}

فرض کنید یک تابع کمکی به نام ()getHead داشته باشیم که گره رأس لیست پیوندی را بازمی‌گرداند و گره ما دارای خصوصیت data باشد که می‌تواند اشاره‌گرهای کند و سریع مورد استفاده برای یافتن عنصر میانی لیست پیوندی را بازگرداند.

از آنجا که افزایش اشاره‌گر سریع دو برابر اشاره‌گر کند است، زمانی که اشاره‌گر سریع به انتهای لیست برسد، اشاره‌گر کند در میانه لیست خواهد بود و بدین ترتیب می‌توانیم slow.data را بازگردانیم که عنصر میانی لیست خواهد بود. برای این که تصویر بهتری از این مفهوم داشته باشید، می‌توانید از این راهنمای کدربایت (+) استفاده کنید.

تعریف حلقه معکوس روی آرایه

همگی ما روش تعریف حلقه از آغاز تا انتهای یک آرایه را می‌دانیم:

for(var i = 0; i < array.length; i++) {
  console.log(array[i]);
}

اما می‌توان به صورت معکوس نیز حلقه‌ای روی یک آرایه تعریف کرد:

for(var i = array.length - 1; i >= 0; i--) {
  console.log(array[i]);
}

با تعیین مقدار i = array.length از انتهای آرایه شروع به چرخش می‌کنیم. سپس پارامتری به صورت i >= 0 تعریف می‌کنیم که به معنی این است که [array[0 قبلی را نباید بررسی کند. سپس با استفاده از --i متغیر را کاهش می‌دهیم. بدین ترتیب می‌توانیم از انتهای آرایه شروع کرده و به سمت آغاز حلقه‌ای تعریف کنیم. در مثال بعدی این وضعیت را به صورت عملی نشان داده‌ایم.

استفاده از یک آرایه ثانویه

استفاده از یک آرایه ثانویه برای حل بسیاری از مسائل الگوریتمی به روش سریع کاملاً مفید خواهد بود. برای نمونه اگر از شما خواسته شود که ترتیب یک آرایه را معکوس کنید، می‌توانید به سادگی حلقه‌ای از انتهای آرایه به سمت ابتدا تعریف کنید و هر مقدار را به arrayTwo ارسال کنید. در نهایت مقدار arrayTwo را بازمی‌گردانید و بدین صورت، ترتیب عناصر آرایه array معکوس شده است:

function reverseArray(array) {
  var arrayTwo = [];

  for(var i = array.length - 1; i >= 0; i--) {
    arrayTwo.push(array[i]);
  }

array = arrayTwo;
  return array;
}

var values = [1,2,3];

// [ 3, 2, 1 ]
reverseArray(values);

در برخی مصاحبه‌های شغلی این مسئله به عنوان یک آزمون مطرح می‌شود و این شرط نیز گذاشته می‌شود که نمی‌توانید از آرایه ثانویه استفاده کنید و باید آرایه اصلی را به صورت درجا معکوس کنید. بدیهی است که این وضعیت نیازمند گام‌های بیشتری است.

با این وجود اگر بتوانید از یک آرایه ثانویه استفاده کنید، زمان و تلاش زیادی را صرفه‌جویی می‌کنید و می‌توانید مسئله‌ای را که ممکن بود بسیار پیچیده باشد، به سادگی حل کنید. بنابراین همواره به استفاده از آرایه ثانویه فکر کنید تا مسائل را به روشی بسیار آسان‌تر حل کنید.

سخن پایانی

چیزی که باعث می‌شود افراد دارای قابلیت‌های ابتدایی حل مسئله از افراد خبره در این زمینه متمایز شوند، صرفاً بهره‌گیری از تکنیک‌های حل الگوریتم بیشتر برای حل کردن مسائل مختلف است. هر چه از این تکنیک‌ها بیشتر استفاده کنید، تنوع راه‌حل‌ها بیشتر می‌شود و از این رو توانایی‌های حل مسئله شما افزایش می‌یابد. همچنین هر چه بتوانید در مورد الگوریتم‌های بیشتری تفکر کرده و حل کنید، در این زمینه تبحر بیشتری می‌یابید. ادامه این مطلب را دربخش دوم (+) می توانید مطالعه کنید.

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم – از دروس دانشگاهی تا کاربردی در فرادرس

کلیک کنید

اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های علوم کامپیوتر
• آموزش طراحی الگوریتم
• مجموعه آموزش‌های مهندسی نرم‌افزار
• الگوریتم ژنتیک و محاسبات تکاملی

==