شماره فوق العاده زشت


سطح دشواری متوسط
اغلب در گوگل
پشته ریاضی

برای یافتن n برنامه ای بنویسیدth عدد فوق العاده زشت. اعداد فوق العاده زشت اعداد مثبتی هستند که تمام فاکتورهای اصلی آنها در اعداد اول با توجه به k وجود دارد

توجه داشته باشید:  1 اولین عدد فوق العاده زشت در نظر گرفته شده است.

رویکرد 1: نیروی بی رحم

ایده اصلی

ما تمام اعداد طبیعی را از 1 تکرار خواهیم کرد و یک متغیر شمارش را حفظ خواهیم کرد که تعداد اعداد زشتی را که پیدا کرده ایم و تعداد آن را برابر با n می شمارد ، آن عدد را چاپ خواهیم کرد.

چگونه می توان بررسی کرد که یک عدد فوق العاده زشت است؟

ما تمام تقسیم کننده های اصلی عدد را پیدا خواهیم کرد و اگر همه تقسیم کنندگان اصلی آن لیست داده شده از "اعداد اول" را داشته باشند ، عدد فوق العاده زشت است و برعکس.

رویکرد 2: برنامه نویسی پویا 

راه حل

این سوال همان ادغام آرایه های مرتب شده K است.

مثلا، ما داریم

Input:  n=7 and  primes = [3, 7, 11, 13]

Output: 21

لیست ما اینگونه ادامه خواهد یافت:

شماره فوق العاده زشت

الگوریتم

  1. یک dp اعلام کنید صف که در آن dp [i] نمایانگر i استth عدد فوق العاده زشت.
  2. dp [1] = 1 را شروع کنید.
  3. یک آرایه اشاره گر به اندازه k را در جایی که نشانگر [i] نشانگر i است ، شروع کنیدth عدد اول در آرایه داده شده.
  4. یک حلقه برای i در محدوده 2 تا n اجرا کنید:
    • یک حلقه را برای j در محدوده 0 تا k-1 اجرا کنید تا حداقل مقدار dp [اشاره گر [j]] * اعداد اول [j] را پیدا کنید.
    • dp [i] را به روز کنید = حداقل مقدار.
    • تعداد آرایه های نشانگر را تکرار کرده و آن شاخص ها را با عدد 1 افزایش دهید که مقدار آنها برابر با حداقل مقدار است.
  5. dp [n] را برگردانید.

پیاده سازی

برنامه C ++ برای شماره نهم فوق العاده زشت

#include <bits/stdc++.h>
using namespace std;
int nthSuperUglyNumber(int n, vector<int> &primes)
{
    vector<long long> dp(n + 1, 1);
    int k = primes.size();
    vector<int> pointer(k, 1);
    for (int i = 2; i <= n; i++)
    {
        long long mi = (1e18);
        for (int j = 0; j < k; j++)
        {
            long long temp = dp[pointer[j]] * primes[j];
            mi = min(mi, temp);
        }
        dp[i] = mi;
        for (int j = 0; j < k; j++)
        {
            long long temp = dp[pointer[j]] * primes[j];
            if (temp == mi)
            {
                pointer[j]++;
            }
        }
    }
    return dp[n];
}
int main()
{
    int n;
    cin >> n;
    int k;
    cin >> k;
    vector<int> primes(k);
    for (int i = 0; i < k; i++)
    {
        cin >> primes[i];
    }
    cout << "The nth super ugly number is: "<<nthSuperUglyNumber(n, primes) << endl;
}
7
4
3 7 11 13
The nth super ugly number is: 21

برنامه JAVA برای شماره نهم فوق العاده زشت

import java.util.*;
public class Main
{
    public static int nthSuperUglyNumber(int n,int[] primes)
    {
        int[] dp=new int[n+1];
        for(int i=0;i<=n;i++){
            dp[i]=1;
        }
        int k = primes.length;
        int[] pointer = new int[k];
        for(int i=0;i<k;i++){
            pointer[i]=1;
        }
        for (int i = 2; i <= n; i++)
        {
            int mi = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++)
            {
                int temp = dp[pointer[j]] * primes[j];
                mi = Math.min(mi, temp);
            }
            dp[i] = mi;
            for (int j = 0; j < k; j++)
            {
                int temp = dp[pointer[j]] * primes[j];
                if (temp == mi)
                {
                    pointer[j]++;
                }
            }
        }
        return dp[n];
    }

  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int k = sc.nextInt();
      int[] primes = new int[k];
      for(int i=0;i<k;i++){
            primes[i] = sc.nextInt();
        }
    System.out.println("The nth super ugly number is: "+nthSuperUglyNumber(n,primes));
  }
}
6
5
2 3 5 7 17
The nth super ugly number is: 6

تجزیه و تحلیل پیچیدگی برای n شماره فوق العاده زشت

پیچیدگی زمانی

دو حلقه تو در تو وجود دارد ، اول از 2 به N و دوم از 0 به k-1 ، بنابراین پیچیدگی زمان O (n * k).

پیچیدگی فضا

دو آرایه ، یکی با اندازه n و دیگری با اندازه k ، بنابراین پیچیدگی فضا است O (n + k).

منابع