Chương trình tìm số xấu thứ n trong C ++

Giả sử chúng ta có một số n; chúng ta phải tìm số xấu thứ n. Như chúng ta biết rằng số xấu là những số có thừa số nguyên tố chỉ là 2, 3 và 5. Vì vậy, nếu chúng ta muốn tìm 10 số xấu, đầu ra sẽ là 12, vì một số số xấu đầu tiên là 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, v.v.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• Xác định một mảng v có kích thước (n + 1)
• nếu n giống 1, thì:
  • trả lại 1
• hai:=2, ba:=3, năm:=5
• haiIdx:=2, baIdx:=2, nămIdx:=2
• để khởi tạo i:=2, khi i <=n, cập nhật (tăng i lên 1), thực hiện:
  • curr:=tối thiểu là hai, ba và năm
  • v [i]:=curr
  • nếu curr giống như hai, thì:
    • hai:=v [twoIdx] * 2;
    • (tăng haiIdx lên 1)
  • nếu curr giống với ba, thì:
    • ba:=v [baIdx] * 3
    • (tăng baIdx lên 1)
  • nếu curr giống với năm, thì:
    • năm:=v [fiveIdx] * 5
    • (tăng nămIdx lên 1)
• return v [n]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

#include
using namespace std;
class Solution {
   public:
   int nthUglyNumber(int n) {
      vector v(n + 1);
      if(n == 1){
         return 1;
      }
      int two = 2, three = 3, five = 5;
      int twoIdx = 2;
      int threeIdx = 2;
      int fiveIdx = 2;
      for(int i = 2; i <= n; i++){
         int curr = min({two, three, five});
         v[i] = curr;
         if(curr == two){
            two = v[twoIdx] * 2;;
            twoIdx++;
         }
         if(curr == three){
            three = v[threeIdx] * 3;
            threeIdx++;
         }
         if(curr == five){
            five = v[fiveIdx] * 5;
            fiveIdx++;
         }
      }
   return v[n];
   }
};
main(){
   Solution ob;
   cout << (ob.nthUglyNumber(15));
}

Đầu vào

15

Đầu ra

24