Рақами махсус

Дар байни рақам чӣ чизи хосе дошта метавонад? Биёед бифаҳмем. Мо бо худ як қатор 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 ++ барои Tower Of Hanoi

#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

ва ғайра.

Таҳлили мураккабӣ барои Tower Of Hanoi

Мураккабии вақт

Муодилаи рекурсивӣ:  T (n) = 2T (n-1) + 1

T (n) = O (2 ^ {(n + 1)} - 1), ё шумо метавонед бигӯед О (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 Қувваи бераҳм Дарёфти ҳама омилҳои ибтидоии ҳарду адад, пас ҳосили чорроҳа. Ҷустуҷӯи бузургтарин ададе, ки ҳарду рақамро тақсим мекунад. Ин чист ...

Бештар

Навбати даврӣ

Навбати даврашакл шакли пешрафтаи навбати хаттӣ мебошад. Дар навбати хатӣ, мо элементро дар навбат гузошта наметавонем, агар ақраб ба индекси охирини навбат ишора карда бошад ва навбат пурра пур нашуда бошад. Ин боиси беҳудаи хотира мегардад. Барои рафъи ин…

Бештар

Хориҷ кардани ду матрица

Гуфтори масъала Дар масъалаи "Тарҳ кардани ду матритса" мо ду матриси а ва б-ро додем. Мо бояд матритсаи ниҳоиро пас аз тарки матритсаи б аз матритсаи а пайдо кунем. Агар фармоиш барои ҳарду матритса яксон бошад, танҳо мо метавонем онҳоро коҳиш диҳем, вагарна наметавонем. …

Бештар

Санҷед, ки оё ду матритсаи додашуда шабеҳанд

Гузориши масъала Бо назардошти ду матритса, мо вазифае хоҳем навишт, ки ду матритса якхела аст ё не. Яъне, агар ҳамаи элементҳо дар ҷойгоҳҳои мувофиқи ду матритса як бошанд, пас мо мегӯем, ки онҳо якхелаанд. Формати вуруд Сатри аввал дорои…

Бештар

Илова кардани ду матритса

Изҳороти масъала Дар масъалаи "Илова кардани ду матритса", мо ду матритсаи a ва b додем. Мо бояд матритсаи ниҳоиро пас аз илова кардани матритсаи б дар матритсаи а пайдо кунем. Агар фармоиш барои ҳарду матритса як бошад, танҳо мо метавонем онҳоро илова кунем, вагарна наметавонем. …

Бештар

Гузаронидани матритса

Баёни масъала Дар масъалаи "Transpose of Matrix" мо матритса додем. Мо бояд транспозитсияи матритсаро ёбем ва чоп кунем. Эзоҳ: Транспорти_матрица матритсаест, ки сатрҳо сутунҳо ва сутунҳо сатрҳои аслӣ мебошанд. Формати вуруд…

Бештар