ລໍາດັບ Newman-Conway


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Honeywell
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ຄະນິດສາດ ລໍາດັບ

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

ບັນຫາ“ ລຳ ດັບ Newman-Conway Sequence” ລະບຸວ່າທ່ານໄດ້ຖືກມອບໃຫ້ໃສ່ຕົວເລກການປ້ອນຂໍ້ມູນ“ n”. ຫຼັງຈາກນັ້ນທ່ານ ຈຳ ເປັນຕ້ອງໄດ້ພິມສ່ວນປະກອບ ທຳ ອິດຂອງ ລຳ ດັບ Newman-Conway Sequence.

ຍົກຕົວຢ່າງ

n = 6
4
n = 10
6

ຄໍາອະທິບາຍ

ນັບຕັ້ງແຕ່ອົງປະກອບຜົນຜະລິດເປັນຕົວແທນຂອງອົງປະກອບທີ VI ແລະສິບຂອງ Newman-Conway Sequence. ຜົນໄດ້ຮັບແມ່ນຖືກຕ້ອງແທ້ໆ.

ວິທີການເພື່ອຊອກຫາ Newman-Conway Sequence

ລຳ ດັບ Newman-Conway ແມ່ນ ລຳ ດັບເຊິ່ງແຕ່ລະໄລຍະຕອບສະ ໜອງ ຄວາມ ສຳ ພັນກັບການເກີດຂື້ນຕໍ່ໄປນີ້.
P (1) = P (2) = 1

ລໍາດັບ Newman-Conway

 

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

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

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາອົງປະກອບ ລຳ ດັບ Newman-Conway Sequence

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

int main(){
  // element to be printed
  int n;cin>>n;
  int dp[n+1];
  dp[0] = 0;
  dp[1] = dp[2] = 1;
  for(int i=3;i<=n;i++)
    dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
  cout<<dp[n];
}
6
4

ລະຫັດ Java ເພື່ອຊອກຫາສ່ວນປະກອບ ລຳ ດັບ Newman-Conway Sequence

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // eleemnt to be printed
    int n = sc.nextInt();
    int dp[] = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for(int i=3;i<=n;i++)
      dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
    System.out.print(dp[n]);
  }
}
6
4

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

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

ໂອ (N), ເພາະວ່າພວກເຮົາພຽງແຕ່ແລ່ນວົງດຽວເພື່ອຊອກຫາສ່ວນປະກອບຂອງ ລຳ ດັບ. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນເປັນເສັ້ນ.

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

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ ນຳ ໃຊ້ອາເລ DP ເພື່ອເກັບຮັກສາຜົນໄດ້ຮັບລະດັບກາງເຊິ່ງ ຈຳ ເປັນ ສຳ ລັບການ ຄຳ ນວນຂອງອົງປະກອບ nth. ຄວາມສັບສົນຂອງພື້ນທີ່ຍັງເປັນເສັ້ນ.

ເອກະສານ