شماره ویژه

چه چیزهایی می توانند در مورد یک عدد بسیار خاص باشند؟ بگذارید بفهمیم ما یک آرایه از اعداد N داریم. اگر یک عدد بر یک یا چند عدد قابل تقسیم باشد به جز خود عدد ، می تواند خاص باشد. ابتدا اجازه دهید این را با چند مثال قبل از آن روشن کنیم ...

ادامه مطلب

برج هانوی

برج هانوی یک مسئله ریاضی با شرایط زیر است:

  • سه برج وجود دارد
  • ممکن است تعداد n حلقه وجود داشته باشد
  • حلقه ها در اندازه های مختلف هستند
  • همزمان فقط یک دیسک قابل جابجایی است
  • هر دیسک را فقط می توان در بالای دیسک بزرگتر جابجا کرد
  • فقط دیسک بالا را می توان حذف کرد

توضیح  

بگذارید ببینیم وقتی دو دیسک داریم چگونه می توان از پس این مشکل برآمد

برج هانوی توضیح داده شده است

دیسک بالا (کوچک) را به برج بعدی منتقل می کنیم و پس از آن دیسک دوم را به برج سوم منتقل می کنیم و سپس در نهایت دیسک اول را نیز به برج سوم منتقل می کنیم. (3 حرکت)

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

به همین ترتیب وقتی با 3 دیسک کار می کنیم. برای انتقال همه آنها به حلقه سوم به 7 مرحله نیاز داریم.

  • دیسک 1 از 1 به 3 منتقل شدبرج هانوی
  • اکنون دیسک 2 از 1 به 2 منتقل شدبرج هانوی
  • دیسک 1 از 3 به 2 منتقل شدبرج هانوی
  • دیسک 3 از 1 به 3 منتقل شدبرج هانوی
  • اکنون دیسک 1 از 2 به 1 منتقل شد
  • دیسک 2 از 2 به 3 منتقل شد
  • دیسک 1 از 1 به 3 منتقل شد

بنابراین ما دیسک های n-1 را به برج دوم ، آخرین دیسک به برج سوم و n-1 دیسک ها را به دیسک اول منتقل می کنیم ، بنابراین تغییر کار را انجام می دهیم.

بگذارید اکنون به یک نگاه کنیم بازگشتی اجرای همان.

برنامه JAVA برای برج هانوی  

public class hanoi
{
  public static void hanoi(int n,char from,char mid,char to)
  {
    if(n==1)
    {
      //Moving disk1 on to the first rod
      System.out.println("Moving disk "+n+"From rod:"+from+"To Rod"+to);
      return;
    }
    //Moving n-1 disks to the second rod
    hanoi(n-1,from,to,mid);
    System.out.println("Moving disk "+n+"From rod:"+from+"To Rod"+to);
    //Moving the disks on top of already moved first disk
    hanoi(n-1,mid,from,to);
  }
  public static void main(String args[])
  {
    int n=3;
    hanoi(n,'A','B','C');
  }
}

برنامه C ++ برای برج هانوی  

#include<iostream>
using namespace std;
  void hanoi(int n,char from,char mid,char to)
  {
    if(n==1)
    {
      //Moving disk1 on to the first rod
      cout<<"Moving disk "<< n <<"From rod:"<< from <<" To Rod:"<< to <<endl;
      return;
    }
    //Moving n-1 disks to the second rod
    hanoi(n-1,from,to,mid);
    cout<<"Moving disk "<< n <<"From rod:"<< from <<" To Rod:"<< to <<endl;
    //Moving the disks on top of already moved first disk
    hanoi(n-1,mid,from,to);
  }
  int main()
  {
    int n=4;
    hanoi(n,'A','B','C');
  }
Moving disk 1From rod: A To Rod: B
Moving disk 2From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C
Moving disk 3From rod: A To Rod: B
Moving disk 1From rod:C To Rod:A
Moving disk 2From rod:C To Rod:B
Moving disk 1From rod: A To Rod: B
Moving disk 4From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C
Moving disk 2From rod: B To Rod: A
Moving disk 1From rod:C To Rod:A
Moving disk 3From rod:B To Rod:C
Moving disk 1From rod: A To Rod: B
Moving disk 2From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C

نتیجه گیری برای برج هانوی  

بنابراین ما به این نتیجه می رسیم:

15 حرکت برای 4 دیسک

31 حرکت برای 5 دیسک

بنابراین ، ما به این نتیجه رسیدیم که برای n دیسک ما باید بسازیم (2 ^ n) -1 حرکت می کند.

2 disks=(2*2)-1=2 moves

3 disks=(2^3)-1=7 moves

4 disks=(2^4)-1=15 moves

و الی آخر.

تحلیل پیچیدگی برای برج هانوی  

پیچیدگی زمان

معادله بازگشتی:  T (n) = 2T (n-1) + 1

T (n) = O (2 ^ {(n + 1)} - 1)، یا می توانید بگویید O (2 ^ n) که نمایی است

پیچیدگی فضا

T (n) = T (n-1) + k
T (0) = k
T (1) = 2k
T (2) = 3k
T (3) = 4k
بنابراین پیچیدگی فضا O (n) است.

منابع

GCD از دو عدد

بزرگترین عامل مشترک چیست؟ GCD دو عددی بزرگترین عددی است که هر دو را تقسیم می کند. Approach-1 Brute Force پیدا کردن همه عوامل اصلی هر دو عدد ، و سپس حاصلضرب تقاطع. یافتن بزرگترین عددی که هر دو عدد را تقسیم می کند. آن چیست …

ادامه مطلب

صف دایره ای

صف دایره ای شکل پیشرفته صف خطی است. اگر عقب به آخرین شاخص صف اشاره داشته باشد و صف کاملاً پر نشده باشد ، در صف خطی نمی توانیم عنصری را در صف قرار دهیم. این باعث هدر رفتن حافظه می شود. برای غلبه بر این ...

ادامه مطلب

تفریق دو ماتریس

Problem Statement   In the “Subtraction of Two Matrices” problem, we have given two matrices a and b. We have to find the final matrix after subtracting matrix b from matrix a. If the order is the same for both the matrices then only we can subtract them otherwise we can’t. …

ادامه مطلب

بررسی کنید آیا دو ماتریس داده شده یکسان هستند

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

ادامه مطلب

اضافه شدن دو ماتریس

بیان مسأله در مسئله "افزودن دو ماتریس" ، دو ماتریس a و b داده ایم. ما باید ماتریس نهایی را پس از افزودن ماتریس b در ماتریس a پیدا کنیم. اگر ترتیب هر دو ماتریس یکسان باشد ، فقط ما می توانیم آنها را اضافه کنیم در غیر این صورت نمی توانیم. …

ادامه مطلب

انتقال یک ماتریس

Problem Statement   In the “Transpose of a Matrix” problem, we have given a matrix. We need to find the transpose of the matrix and print it. Note:  The transpose_of a matrix is a matrix whose rows are the columns and columns are the rows of the original_matrix. Input Format   The …

ادامه مطلب