ເບີພິເສດ

ສິ່ງທີ່ສາມາດພິເສດສະເພາະກ່ຽວກັບຕົວເລກໃດ ໜຶ່ງ? ໃຫ້ພວກເຮົາຊອກຫາ. ພວກເຮົາມີຕົວເລກ N ຂອງພວກເຮົາກັບພວກເຮົາ. ຕົວເລກສາມາດພິເສດຖ້າມັນສາມາດແບ່ງອອກໂດຍຕົວເລກ ໜຶ່ງ ຫຼືຫຼາຍຂໍ້ຍົກເວັ້ນແຕ່ຕົວເລກຕົວມັນເອງ. ທຳ ອິດໃຫ້ພວກເຮົາລຶບລ້າງສິ່ງນີ້ດ້ວຍຕົວຢ່າງສອງສາມຢ່າງກ່ອນ…

ອ່ານ​ເພິ່ມ​ເຕິມ

Tower ຂອງຮ່າໂນ້ຍ

Tower ຂອງຮ່າໂນ້ຍແມ່ນບັນຫາທາງຄະນິດສາດທີ່ມີເງື່ອນໄຂດັ່ງຕໍ່ໄປນີ້:

  • ມີສາມຫໍ
  • ມັນອາດຈະມີ ຈຳ ນວນແຫວນປະຈຸບັນ
  • ແຫວນມີຂະ ໜາດ ຕ່າງກັນ
  • ພຽງແຕ່ແຜ່ນດຽວເທົ່ານັ້ນທີ່ສາມາດຍ້າຍໄດ້ໃນຄັ້ງດຽວ
  • ແຜ່ນໃດກໍ່ສາມາດຖືກຍ້າຍຢູ່ເທິງສຸດຂອງແຜ່ນໃຫຍ່ເທົ່ານັ້ນ
  • ມີພຽງແຜ່ນດິດທາງເທິງເທົ່ານັ້ນທີ່ສາມາດເອົາອອກໄດ້

ຄໍາອະທິບາຍ

ໃຫ້ພວກເຮົາເບິ່ງວິທີການແກ້ໄຂບັນຫານີ້ເມື່ອພວກເຮົາມີສອງແຜ່ນ

Tower Of Hanoi ອະທິບາຍ

ພວກເຮົາຍ້າຍແຜ່ນດິດດ້ານເທິງ (ຂະ ໜາດ ນ້ອຍ) ລົງໃສ່ຫໍຄອຍຕໍ່ໄປຫລັງຈາກນັ້ນພວກເຮົາຍ້າຍແຜ່ນທີສອງໄປຫາຫໍຄອຍທີສາມແລະຈາກນັ້ນກໍ່ປ່ຽນແຜ່ນດິດ ທຳ ອິດເຊັ່ນດຽວກັນໄປຫາຫໍຄອຍທີສາມ. (3 ຍ້າຍ)

ສົມມຸດຕິຖານ: ແຜ່ນຖາດໄດ້ຖືກຈັດລຽງໃນເບື້ອງຕົ້ນ

ຄ້າຍຄືກັນເມື່ອພວກເຮົາເຮັດວຽກກັບ 3 ແຜ່ນ. ພວກເຮົາຕ້ອງການ 7 ຂັ້ນຕອນເພື່ອປ່ຽນວົງແຫວນທັງ ໝົດ ໃຫ້ເປັນແຫວນທີສາມ.

  • ແຜ່ນ 1 ຍ້າຍຈາກ 1 ເຖິງ 3Tower ຂອງຮ່າໂນ້ຍ
  • ໃນປັດຈຸບັນ, ແຜ່ນ 2 ໄດ້ຍ້າຍຈາກ 1 ໄປ 2Tower ຂອງຮ່າໂນ້ຍ
  • ແຜ່ນ 1 ຍ້າຍຈາກ 3 ເຖິງ 2Tower ຂອງຮ່າໂນ້ຍ
  • ແຜ່ນ 3 ຍ້າຍຈາກ 1 ເຖິງ 3Tower ຂອງຮ່າໂນ້ຍ
  • ໃນປັດຈຸບັນ, ແຜ່ນ 1 ໄດ້ຍ້າຍຈາກ 2 ໄປ 1
  • ແຜ່ນ 2 ຍ້າຍຈາກ 2 ເຖິງ 3
  • ແຜ່ນ 1 ຍ້າຍຈາກ 1 ເຖິງ 3

ພວກເຮົາ ກຳ ລັງຍ້າຍແຜ່ນ n-1 ໄປທີ່ຫໍຄອຍທີສອງ, ແຜ່ນສຸດທ້າຍໃສ່ຫໍຄອຍທີສາມແລະແຜ່ນ n-1 ໃສ່ແຜ່ນ ທຳ ອິດດັ່ງນັ້ນຈຶ່ງ ສຳ ເລັດການປ່ຽນ.

ຕອນນີ້ໃຫ້ພວກເຮົາເບິ່ງ a ຮຽກຮ້ອງ ການປະຕິບັດດຽວກັນ.

ໂຄງການ JAVA ສຳ ລັບ Tower Of Hanoi

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

ບົດສະຫຼຸບ ສຳ ລັບ Tower Of ຮ່າໂນ້ຍ

ພວກເຮົາມາຮອດສະຫລຸບດັ່ງນີ້:

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), ຫຼືທ່ານສາມາດເວົ້າ O (2 ^ n) ເຊິ່ງເປັນເລກ ກຳ ລັງ

ຄວາມສັບສົນໃນອະວະກາດ

T (n) = T (n-1) + ກ
ທ (0) = ກ
ທ (1) = 2 ກ
ທ (2) = 3 ກ
ທ (3) = 4 ກ
ດັ່ງນັ້ນຄວາມສັບສົນໃນອະວະກາດແມ່ນ O (n).

ເອກະສານ

GCD ຂອງສອງເລກ

ປັດໃຈ ທຳ ມະດາທີ່ຍິ່ງໃຫຍ່ທີ່ສຸດແມ່ນຫຍັງ? GCD ຂອງສອງຕົວເລກແມ່ນຕົວເລກທີ່ໃຫຍ່ທີ່ສຸດທີ່ແບ່ງທັງສອງ. Approach-1 Brute Force ການຄົ້ນຫາປັດໄຈທີ່ ສຳ ຄັນທັງສອງຕົວເລກ, ຈາກນັ້ນຊອກຫາຜະລິດຕະພັນຂອງການຕັດກັນ. ຊອກຫາຕົວເລກທີ່ໃຫຍ່ທີ່ສຸດທີ່ແບ່ງທັງສອງຕົວເລກ. ມັນແມ່ນຫຍັງທີ່…

ອ່ານ​ເພິ່ມ​ເຕິມ

ແຖວວົງວຽນ

ແຖວເປັນວົງກົມແມ່ນຮູບແບບທີ່ກ້າວ ໜ້າ ຂອງແຖວແຖວ. ໃນແຖວແຖວ, ພວກເຮົາບໍ່ສາມາດໃສ່ສ່ວນປະກອບໃນແຖວຖ້າທາງດ້ານຫຼັງແມ່ນຊີ້ໄປຫາດັດສະນີສຸດທ້າຍຂອງແຖວແລະແຖວນັ້ນຍັງບໍ່ໄດ້ເຕີມເຕັມ. ນີ້ເປັນສາເຫດຂອງການສູນເສຍຄວາມຊົງ ຈຳ. ເພື່ອເອົາຊະນະສິ່ງນີ້…

ອ່ານ​ເພິ່ມ​ເຕິມ

ການຫັກລົບຂອງສອງ Matrices

ຖະແຫຼງການບັນຫາໃນບັນຫາ“ ການຫັກລົບສອງຄະນິດ”, ພວກເຮົາໄດ້ມອບສອງມັດທະຍົມ a ແລະ b. ພວກເຮົາຕ້ອງຊອກຫາມາຕຣິກເບື້ອງສຸດທ້າຍຫລັງຈາກຫັກອອກມາຈາກຕາຕະລາງກ. ຖ້າ ຄຳ ສັ່ງແມ່ນດຽວກັນ ສຳ ລັບທັງສອງມັດທະຍົມຫຼັງຈາກນັ້ນພຽງແຕ່ພວກເຮົາສາມາດຫັກລົບພວກມັນຖ້າບໍ່ດັ່ງນັ້ນພວກເຮົາບໍ່ສາມາດເຮັດໄດ້. …

ອ່ານ​ເພິ່ມ​ເຕິມ

ກວດເບິ່ງວ່າ Matrices ທີ່ຖືກມອບໃຫ້ສອງຢ່າງແມ່ນເປັນຕົວຕົນໄດ້ບໍ

ຖະແຫຼງການກ່ຽວກັບບັນຫາໃນສອງຫຼັກການ, ພວກເຮົາຈະຂຽນ ໜ້າ ທີ່ເພື່ອກວດສອບວ່າສອງ matrices ແມ່ນຄືກັນຫຼືບໍ່. ນັ້ນແມ່ນ, ຖ້າວ່າທຸກໆອົງປະກອບທີ່ຢູ່ໃນ ຕຳ ແໜ່ງ ທີ່ກ່ຽວຂ້ອງຂອງສອງ matrices ແມ່ນອັນດຽວກັນ, ຫຼັງຈາກນັ້ນພວກເຮົາເວົ້າວ່າມັນແມ່ນອັນດຽວກັນ. ຮູບແບບການປ້ອນຂໍ້ມູນເສັ້ນ ທຳ ອິດບັນຈຸ…

ອ່ານ​ເພິ່ມ​ເຕິມ

ການຕື່ມສອງ Matrices

ຖະແຫຼງການບັນຫາໃນບັນຫາ“ ການເພີ່ມເຕີມສອງ Matrices”, ພວກເຮົາໄດ້ມອບສອງຫຼັກ ໝາຍ a ແລະ b. ພວກເຮົາຕ້ອງຊອກຫາຕາຕະລາງສຸດທ້າຍຫຼັງຈາກເພີ່ມມາຕຣິກເບື້ອງ b ໃນຕາຕະລາງກ. ຖ້າ ຄຳ ສັ່ງແມ່ນດຽວກັນ ສຳ ລັບທັງສອງມັດທະຍົມຫຼັງຈາກນັ້ນພຽງແຕ່ພວກເຮົາສາມາດເພີ່ມພວກມັນໄດ້ຖ້າບໍ່ດັ່ງນັ້ນພວກເຮົາບໍ່ສາມາດເຮັດໄດ້. …

ອ່ານ​ເພິ່ມ​ເຕິມ

Transpose ຂອງມາຕຣິກເບື້ອງ

ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາໃນ“ ການຫັນປ່ຽນຂອງມາຕຣິກເບື້ອງ”, ພວກເຮົາໄດ້ມອບຕາຕະລາງມາໃຫ້. ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາການຍ້າຍຂອງມາຕຣິກເບື້ອງແລະພິມມັນ. ໝາຍ ເຫດ: transpose_of matrix ແມ່ນຕາຕະລາງ ໜຶ່ງ ທີ່ແຖວຂອງມັນແມ່ນແຖວແລະຖັນແມ່ນແຖວຂອງແຖວຕົ້ນສະບັບ _. ຮູບແບບການປ້ອນຂໍ້ມູນ…

ອ່ານ​ເພິ່ມ​ເຕິມ