ລໍາດັບ Moser-de Bruijn


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ FreeCharge Snapdeal ອິນເຕີເນັດ Times Times
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ລໍາດັບ

ໃນບັນຫານີ້, ທ່ານໄດ້ຮັບການປ້ອນເລກ integer n. ໃນປັດຈຸບັນທ່ານຈໍາເປັນຕ້ອງພິມອົງປະກອບ n ທໍາອິດຂອງ Moser-de Bruijn ລໍາດັບ.

ຍົກຕົວຢ່າງ

7
0, 1, 4, 5, 16, 17, 20

ຄໍາອະທິບາຍ

ລໍາດັບຜົນຜະລິດມີເຈັດອົງປະກອບທໍາອິດຂອງ Moser-de Bruijn ລໍາດັບ. ດັ່ງນັ້ນຜົນຜະລິດແມ່ນຖືກຕ້ອງແທ້ໆ.

ວິທີການ

In ທິດສະດີເລກ, ການ ລຳ ດັບ Moser – de Bruijn ເປັນ ລໍາດັບເລກເຕັມ ຊື່ຫຼັງ Leo Moser ແລະ ນິໂກລາສ Govert de Bruijn, ປະກອບດ້ວຍຜົນລວມຂອງ ອຳ ນາດທີ່ແຕກຕ່າງກັນຂອງ 4. ດັ່ງນັ້ນ ໝາຍ ຄວາມວ່າມັນຈະມີຕົວເລກທັງ ໝົດ ທີ່ສາມາດເປັນຕົວແທນໂດຍໃຊ້ ອຳ ນາດທີ່ແຕກຕ່າງ 4.

ພວກເຮົາຍັງສາມາດ ກຳ ນົດຕົວເລກທີ່ປະກອບເປັນ ລຳ ດັບ Moser-de Bruijn ໃນລັກສະນະທີ່ແຕກຕ່າງກັນເລັກນ້ອຍ. ຖ້າຫາກວ່າຕົວເລກທີ່ຖືກປ່ຽນເປັນລະບົບເລກ -4 ມີພຽງ 0 ຫຼື 1. ແລ້ວພວກເຮົາເວົ້າວ່າ ຈຳ ນວນດັ່ງກ່າວມີຢູ່ໃນ Moser-de Bruijn Sequence. ມັນບໍ່ໄດ້ ໝາຍ ຄວາມວ່າລະບົບ ໝາຍ ເລກ 4 ຂອງຖານມີພຽງ 0 ແລະ 1 ເທົ່າກັບຕົວເລກຂອງມັນ. ຕົວແທນຖານ -4 ປະກອບດ້ວຍ 0, 1, 2, ແລະ 3. ແຕ່ຖ້າ ຈຳ ນວນດັ່ງກ່າວມີຢູ່ໃນ ລຳ ດັບຂອງພວກເຮົາ. ມັນ ຈຳ ເປັນຕ້ອງປະຕິບັດຕາມເງື່ອນໄຂເບື້ອງຕົ້ນບາງຢ່າງເຊິ່ງຕ້ອງມີພຽງແຕ່ 0 ຫຼື 1 ໃນຕົວແທນຖານ 4. ສະນັ້ນດຽວນີ້ພວກເຮົາຄຸ້ນເຄີຍກັບຕົວເລກປະເພດໃດທີ່ເປັນ ລຳ ດັບ. ແຕ່ພວກເຮົາຈະສ້າງຕົວເລກດັ່ງກ່າວໄດ້ແນວໃດ?

ວິທີງ່າຍໆ ໜຶ່ງ ແມ່ນການ ນຳ ໃຊ້ສູດສູດທີ່ເກີດຂື້ນ ໃໝ່ ເຊິ່ງຖືກ ນຳ ໃຊ້ເພື່ອສ້າງ ຈຳ ນວນຂອງ ລຳ ດັບ. ແຕ່ມີການຈັບ.

ຄວາມ ສຳ ພັນກັບການເກີດຂື້ນ

ລໍາດັບ Moser-de Bruijn

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

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຜະລິດ ລຳ ດັບ Moser-de Bruijn

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

int main(){
  // number of elements to be generated
  int n;cin>>n;
  if(n >= 1)cout<<0<<" ";
  if(n >= 2)cout<<1<<" ";
  if(n >= 3) {
    int dp[n];
    dp[0] = 0,dp[1] = 1;
    for(int i=2; i<n;i++){
      if(i%2 == 0)
        dp[i] = 4*dp[i/2];
      else
        dp[i] = 4*dp[i/2] + 1;
      cout<<dp[i]<<" ";
    }
  }
}
6
0 1 4 5 16 17

ລະຫັດ Java ເພື່ອຜະລິດ Moser-de Bruijn Sequence

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements to be generated
    int n = sc.nextInt();
    if(n >= 1)System.out.print("0 ");
    if(n >= 2)System.out.print("1 ");
    if(n >= 3) {
      int dp[] = new int[n];
      dp[0] = 0;dp[1] = 1;
      for(int i=2; i<n;i++){
        if(i%2 == 0)
          dp[i] = 4*dp[i/2];
        else
          dp[i] = 4*dp[i/2] + 1;
        System.out.print(dp[i]+" ");
      }
    }
  }
}
6
0 1 4 5 16 17

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

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

ໂອ (N), ເພາະວ່າເມື່ອຄິດໄລ່ເລກ ໜຶ່ງ ແລ້ວ, ມັນບໍ່ມີເວລາທີ່ຈະໃຊ້ໃນການຄິດໄລ່ຫຼັງຈາກນັ້ນ. ເນື່ອງຈາກການຄິດໄລ່ລ່ວງ ໜ້າ ຕ້ອງໃຊ້ເວລາ O (N). ເວລາ, ຄວາມສັບສົນແມ່ນເປັນເສັ້ນ.

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

ໂອ (N), ເພາະວ່າພວກເຮົາໄດ້ສ້າງສິ່ງ ໃໝ່ DP ອາເລທີ່ຂຶ້ນກັບວັດສະດຸປ້ອນ. ຄວາມສັບສົນຂອງພື້ນທີ່ ສຳ ລັບບັນຫາແມ່ນເປັນເສັ້ນ.