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

در بخش قبلی این نوشته با عنوان «تکنیک های حل الگوریتم به زبان ساده» به بررسی برخی از تکنیک‌های حل الگوریتم رایج پرداختیم. در این نوشته ادامه مبحث را پی می‌گیریم.

استفاده از حلقه for تو در تو

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

function bubbleSort(array) {
  for (var i = 0; i < array.length; i++) {
    for(var j = 0; j < array.length; j++) {
      if(array[i]<array[j]) {
        // swap values
        var temp = array[j];
        array[j] = array[i];
        array[i] = temp;
      }
     }
  }
  return array;
}
var nums = [3,4,1];
// returns [1,3,4];
bubbleSort(nums);

حلقه for تو در تو روی یک آرایه می‌چرخد و یک بار به همه عناصر آرایه سر می‌زند. بنابراین اگر آرایه‌ای به صورت [3, 2, 1] داشته باشیم، وقتی i=0 باشد، حلقه for دوم یک بار دیگر روی همه عناصر آرایه می‌چرخد و زمانی i=1 باشد، مجدداً حلقه for دوم روی همه عناصر می‌چرخد.

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

همان طور که می‌توانید تصور کنید این فرایند بسیار زمان‌بر است و خسته‌کننده است. به همین دلیل است که پیچیدگی زمانی اجرای الگوریتم‌هایی که از حلقه‌های for تو در تو استفاده می‌کنند، به صورت (O(n² است. اگر به این مبحث علاقه‌مند هستید در «آموزش طراحی الگوریتم به همراه حل مثال‌های عملی» می‌توانید اطلاعات بیشتری در این خصوص کسب کنید.

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

در هر حال، این حلقه‌ها ابزاری هستند که هر توسعه‌دهنده‌ای باید از آن‌ها آگاه باشد. این تکنیک در رویکردهای تهاجمی (brute-force) برای حل الگوریتم‌ها مورد استفاده قرار می‌گیرد. استفاده از یک رویکرد تهاجمی به عنوان نخستین راه‌حل می‌تواند بینش خوبی در خصوص مسئله مورد بررسی به دست بدهد. این بینش‌ها به ما امکان می‌دهند که مسئله را با دقت بیشتری ارزیابی کنیم و راه‌حل بهتری بیابیم.

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

هیچ چیز بدتر از این نیست که شروع به کار روی یک مسئله بکنید و مطلقاً هیچ روشی برای سوق دادن مسئله به سمت یک راه‌حل در ذهن خود نداشته باشید.

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

جایگزینی مقادیر با استفاده از متغیر موقت (temp)

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

• (array.push(value: یک مقدار را به انتهای آرایه اضافه می‌کند.
• (array.pop(value: یک مقدار را از ابتدای آرایه حذف می‌کند.
• (array.split(index1, index2: یک مقدار را از مکان مشخصی در آرایه اضافه یا حذف می‌کند.

اما چگونه می‌توان مقادیر را به صورت دستی جایگزین کرد؟ این کار از طریق یک عملیات swap ساده ممکن است:

var temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;

ابتدا یک متغیر به نام temp را مقداردهی اولیه بکنید و آن را معادل مقداری که می‌خواهید به صورت موقت نگه‌داری کنید قرار دهید. سپس [array[i را معادل [array[i+1 قرار دهید. در نهایت [array[i+1 را معادل temp قرار دهید.

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

استفاده از یک hash

در جاوا اسکریپت یک hash صرفاً یک شیء محسوب می‌شود. می‌توان یک هش خالی با ساختار زیر استفاده کرد:

var dictionary = {};

همچنین می‌توان این هش را با ساختار زیر اضافه کرد:

dictionary['apples'] = 5;
dictionary['oranges'] = 7;

که نتیجه زیر را ایجاد می‌کند:

{
'apples': 5,
'oranges': 7
}

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

همانند مثال فوق می‌توانید کلماتی که در یک آرایه ظاهر می‌شوند و تعداد حروف هر کلمه را ردگیری کنید (کلمه apple پنج حرف دارد و oranges هفت حرف دارد.)

همچنین می‌توانید از یک هش برای ردگیری تعداد دفعاتی که هر عدد صحیح در یک آرایه ظاهر شده است استفاده کنید و سپس از هش برای ایجاد فهرستی از 5 عدد صحیح که بیشترین حضور را دارند استفاده کنید.

نمونه‌ای از این وضعیت به صورت زیر است:

function countOfElement(arr, N){
var encounteredNums = {};
  var num;
  for(var i = 0; i < arr.length; i++) {
    num = arr[i];
    if(encounteredNums[num]) {
      // value already encountered, count++
      encounteredNums[num]++;
    } else {
      // first encounter, initialize count
      encounteredNums[num] = 1;
    }
  }
  return encounteredNums[N] || 0;
}
// returns 6
countOfElement([3,4,2,3,2,2,2,2,3,2], 2);

سخن پایانی

اگر هدف شما این است که در زمینه تکنیک‌های حل الگوریتم مهارت کسب کنید، نباید نگران این باشید که مردم در مورد حلقه‌های for تو در تو یا امثال آن چه نظری دارند. توجه کردن به این نظرات مانند آن است که به پای خود شلیک کنید. حل مسئله به استفاده خلاقانه از روش‌های اثبات شده مربوط است. این فرایند نیازمند طی مراحلی است که از رویکردهای تهاجمی شروع شده و به سرزمین موعود بهینه‌سازی و راه‌حل‌های ایده‌آل منتهی می‌شود.

سعی کنید تا با تمرین مداوم این تکنیک‌های ساده، مهارت‌های خود را بهبود بدهید و پایه‌ای برای کمک به حل مسائل پیچیده‌تر ایجاد کنید.

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

• مجموعه آموزش‌های دروس مهندسی کامپیوتر
• آموزش حل مسأله کوله پشتی با الگوریتم ژنتیک
• مجموعه آموزش‌های برنامه‌نویسی
• آموزش روش حریصانه در طراحی الگوریتم
• مجموعه آموزش های الگوریتم PSO — شامل مباحث تئوری و عملی
• آموزش حل مسائل گسسته با استفاده از الگوریتم PSO
• آموزش الگوریتم تکامل تفاضلی — شامل مباحث تئوری و عملی

==