C++でn番目の醜い数を見つけるプログラム

数nがあるとします。 n番目の醜い数を見つけなければなりません。醜い数は、素因数が2、3、5しかない数であることがわかっているので、10 ^th を見つけたい場合は 醜い数字の場合、出力は12になります。最初のいくつかの醜い数字は、1、2、3、4、5、6、8、9、10、12などです。

これを解決するには、次の手順に従います。

• size（n + 1）の配列vを定義します
• nが1と同じ場合、次のようになります。
  • 1を返す
• 2：=2、3：=3、5：=5
• twoIdx：=2、threeIdx：=2、fiveIdx：=2
• iを初期化する場合：=2、i <=nの場合、更新（iを1つ増やす）、次のようにします。
  • curr：=最低2、3、5
  • v [i]：=curr
  • currが2と同じ場合、次のようになります。
    • two：=v [twoIdx] * 2;
    • （twoIdxを1増やします）
  • currが3と同じ場合、次のようになります。
    • three：=v [threeIdx] * 3
    • （threeIdxを1増やします）
  • currが5と同じ場合、次のようになります。
    • 5：=v [fiveIdx] * 5
    • （fiveIdxを1増やします）
• return v [n]

理解を深めるために、次の実装を見てみましょう。

例

#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));
}

入力

15

出力

24