ເພື່ອນບັນຫາຄູ່


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Expedia GE Healthcare ກູໂກ Honeywell JP Morgan
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ Modular Arithmetic

ຖະແຫຼງການບັນຫາ

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

ຍົກຕົວຢ່າງ

3
4

ເພື່ອນບັນຫາຄູ່
ວິທີການແກ້ໄຂບັນຫາການຫາເພື່ອນ

ແທນທີ່ຈະຄິດກ່ຽວກັບມັນເປັນບັນຫາໃຫຍ່. ທຳ ອິດໃຫ້ພະຍາຍາມແກ້ໄຂ ສຳ ລັບ N. ນ້ອຍໆ ສຳ ລັບ N = 1, ຄຳ ຕອບແມ່ນ 1. ສຳ ລັບ N = 2, ຄຳ ຕອບແມ່ນ 2. ສຳ ລັບ N = 3, ບໍ່ວ່າເພື່ອນຄົນທີສາມກໍ່ສາມາດຢູ່ຄົນດຽວ. ສະນັ້ນ ສຳ ລັບ ຄຳ ຕອບນັ້ນຄວນເປັນ ຄຳ ຕອບຂອງບັນຫາກັບ N = 2. ເປັນສາເຫດໃນທຸກໆກໍລະນີເຫຼົ່ານັ້ນເພື່ອນຄົນທີສາມຂອງພວກເຮົາສາມາດຢູ່ຄົນດຽວ. ແລະ ສຳ ລັບການຈັບຄູ່, ມັນສາມາດເລືອກ ໝູ່ ໃດ ໜຶ່ງ. ສະນັ້ນເລືອກ ໝູ່ 1 ຄົນຈາກ ໝູ່ N-1 ແລະຫຼັງຈາກນັ້ນ ຈຳ ນວນວິທີທີ່ຄົນອື່ນສາມາດຈັບຄູ່ / ຢູ່ຄົນດຽວ = (N-1) * F (N-2). ໃນປັດຈຸບັນ, ພວກເຮົາສາມາດຄິດເຖິງສູດສູດທີ່ເອີ້ນຄືນ ສຳ ລັບບັນຫາ.

F(N)     =     F(N-1)   +   (N-1)*F(N-2)
                  ^              ^
                  |              |
Nth friend (stays single) (pairs with N-1 friends)

ຈາກ ສູດປະຕິບັດ, ພວກເຮົາສາມາດເຫັນໄດ້ວ່າໃນຂະນະທີ່ຄອມພິວເຕີ້ F (N) ພວກເຮົາຄິດໄລ່ F (N-2). ແລະຫຼັງຈາກນັ້ນ ສຳ ລັບ F (N-1) ເຊັ່ນດຽວກັນ, ພວກເຮົາຄິດໄລ່ F (N-2). ສະນັ້ນແທນທີ່ຈະແນະ ນຳ ຄ່າຕ່າງໆ, ພວກເຮົາຄວນ ນຳ ໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ. ໃນທີ່ນີ້, ພວກເຮົາສາມາດເກັບຄ່າ F (N) ທັງ ໝົດ ຈາກ 0 ເຖິງ N. ແຕ່ມັນບໍ່ ຈຳ ເປັນ. ເນື່ອງຈາກວ່າມູນຄ່າຂອງ F (N) ແມ່ນຂື້ນກັບ F (N-1) ແລະ F (N-2) ເທົ່າກັບ 2 ຄ່າສຸດທ້າຍເທົ່ານັ້ນ. ສະນັ້ນພວກເຮົາຈະສືບຕໍ່ເກັບຮັກສາ 2 ຄ່າສຸດທ້າຍ. ສາເຫດທີ່ຈະຊ່ວຍປະຢັດພື້ນທີ່ໃຫ້ພວກເຮົາ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບບັນຫາການຈັບຄູ່

#include<bits/stdc++.h>
using namespace std;

int main()
{
  // number of friends
  int n;cin>>n;

  int last = 2, lastTolast = 1;
  // here last denotes F(N-1) and lastTolast denotes F(N-2)
  // we can also use a dp array but that will only increase space complexity
  // and from the recursive formula we can see that
  // F(N) is dependent only on F(N-1) and F(N-2)
  int current;
  for(int i=3;i<=n;i++){
    current = last + (i-1)*lastTolast;
    lastTolast = last;
    last = current;
  }
  cout<<current<<endl;
}E
4
10

ລະຫັດ Java ສຳ ລັບບັນຫາການຈັບຄູ່

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();// number of friends

    int last = 2, lastTolast = 1;
    // here last denotes F(N-1) and lastTolast denotes F(N-2)
    // we can also use a dp array but that will only increase space complexity
    // and from the recursive formula we can see that
    // F(N) is dependent only on F(N-1) and F(N-2)
    int current;
    for(int i=3;i<=n;i++){
      current = last + (i-1)*lastTolast;
      lastTolast = last;
      last = current;
    }
    System.out.println(current);
  }
}
4
10

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ເພາະວ່າພວກເຮົາຕ້ອງໄດ້ແລ່ນ loop ຈົນ N ເພື່ອຊອກຫາມັນ. ເນື່ອງຈາກ F (N) ຂື້ນກັບ F (N-1) ແລະ F (N-2).

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

ໂອ (1), ພວກເຮົາໃຊ້ພຽງສາມຕົວແປ ສຳ ລັບການ ຄຳ ນວນແລະດັ່ງນັ້ນສະຖານທີ່ທີ່ ຈຳ ເປັນຕ້ອງມີຢູ່ເລື້ອຍໆ.