Тусгай дугаар

Тооны талаар ямар онцгой зүйл байж болох вэ? Үүнийг олж мэдье. Бидэнд 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

Tower Of Hanoi-ийн дүгнэлт

Тиймээс бид дараах дүгнэлтэд хүрч байна.

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 нь хоёуланг нь хуваадаг хамгийн том тоо юм. Хандлага-1 Brute Force Хоёр тооны бүх үндсэн хүчин зүйлийг олох, дараа нь огтлолцлын үржвэрийг олох. Тоог хоёуланг нь хуваадаг хамгийн том тоог олох. Энэ юу вэ ...

Цааш нь

Дугуй дараалал

Дугуй дараалал нь шугаман дарааллын дэвшилтэт хэлбэр юм. Шугаман дараалалд, арын хэсэг нь дарааллын сүүлчийн индексийг зааж байгаа бөгөөд дарааллыг бүрэн бөглөөгүй тохиолдолд бид дараалалд элемент оруулах боломжгүй. Энэ нь ой санамжийг алдах шалтгаан болдог. Үүнийг даван туулахын тулд ...

Цааш нь

Хоёр матрицыг хасах

Бодлогын мэдэгдэл “Хоёр матрицыг хасах” бодлогод бид а, б гэсэн хоёр матриц өгсөн болно. А матрицаас б матрицыг хасаад эцсийн матрицыг олох ёстой. Хэрэв матрицын аль алиных нь дараалал ижил байвал зөвхөн бид тэдгээрийг хасах болно, тэгэхгүй бол чадахгүй. ...

Цааш нь

Өгөгдсөн хоёр матриц ижил байгаа эсэхийг шалгана уу

Бодлогын мэдэгдэл Хоёр матриц өгөгдсөн тул бид хоёр матриц ижил байна уу үгүй ​​юу гэдгийг шалгах функц бичих болно. Өөрөөр хэлбэл, хоёр матрицын байрлал дахь бүх элементүүд ижил байвал бид тэдгээрийг ижил гэж хэлье. Оролтын формат ... агуулсан эхний мөр.

Цааш нь

Хоёр матрицын нэмэлт

Бодлогын мэдэгдэл “Хоёр матрицын нэмэгдэл” бодлогод бид хоёр а, б матриц өгсөн болно. A матрицад b матриц нэмсний дараа бид эцсийн матрицыг олох ёстой. Хэрэв матрицын аль алиных нь дараалал ижил байвал зөвхөн бид тэдгээрийг нэмж болно, эс тэгвэл бид чадахгүй. ...

Цааш нь

Матрицыг шилжүүлэх

Асуудлын мэдэгдэл “Матрицын хэлбэрт шилжих” бодлогод бид матриц өгсөн болно. Бид матрицын транспозицийг олж, хэвлэх хэрэгтэй. Тэмдэглэл: Матрицын шилжүүлэн суулгах нь мөр нь багана, багана нь анхны_матрицын мөр байх матриц юм. Оролтын формат

Цааш нь