Спецыяльны нумар

Што можа быць такога асаблівага ў нумары? Давайце даведаемся. У нас ёсць масіў з 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 дыскі

Такім чынам, мы прыходзім да высновы, што для п дыскаў нам трэба зрабіць (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 Грубая сіла Знаходжанне ўсіх асноўных множнікаў абодвух лікаў, а затым здабытак перасячэння. Знаходжанне найбольшага ліку, які дзеліць абодва лікі. Што гэта ...

больш падрабязна

Кругавая чарга

Кругавая чарга - гэта пашыраная форма лінейнай чаргі. У лінейнай чарзе мы не можам ўставіць элемент у чаргу, калі тыл паказвае на апошні індэкс чаргі, а чарга запоўнена не цалкам. Гэта прыводзіць да страты памяці. Каб пераадолець гэта ...

больш падрабязна

Адніманне дзвюх матрыц

Пастаноўка задачы У задачы "Адніманне дзвюх матрыц" мы прывялі дзве матрыцы a і b. Мы павінны знайсці канчатковую матрыцу пасля аднімання матрыцы b з матрыцы a. Калі парадак аднолькавы для абедзвюх матрыц, то толькі мы можам адняць іх, інакш мы не можам. ...

больш падрабязна

Праверце, ці аднолькавыя дзве дадзеныя матрыцы

Пастаноўка задачы Улічваючы дзве матрыцы, мы напішам функцыю, каб праверыць, ці ідэнтычныя дзве матрыцы. Гэта значыць, калі ўсе элементы ў адпаведных пазіцыях дзвюх матрыц аднолькавыя, то мы кажам, што яны аднолькавыя. Уваходны фармат Першы радок, які змяшчае ...

больш падрабязна

Складанне дзвюх матрыц

Пастаноўка задачы У задачы "Даданне дзвюх матрыц" мы прывялі дзве матрыцы a і b. Мы павінны знайсці канчатковую матрыцу пасля дадання матрыцы b у матрыцу a. Калі парадак аднолькавы для абедзвюх матрыц, то толькі мы можам дадаць іх, інакш мы не можам. ...

больш падрабязна

Транспанаванне матрыцы

Пастаноўка праблемы У задачы "Транспанаванне матрыцы" мы далі матрыцу. Нам трэба знайсці транспартаванне матрыцы і раздрукаваць яе. Заўвага: Transpose_of матрыцы - гэта матрыца, радкі якой з'яўляюцца слупкамі, а слупкі - радкамі зыходнай_матрыцы. Уваходны фармат ...

больш падрабязна