슈퍼 추한 번호

난이도 중급
자주 묻는 질문 구글
더미 수학조회수 28

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의 포인터 배열을 초기화합니다. 여기서 pointer [i]는 i의 포인터를 나타냅니다.th 주어진 배열의 소수.
  4. 2에서 n 사이의 i에 대해 루프를 실행합니다.
    • dp [pointer [j]] * primes [j]의 최소값을 찾기 위해 0에서 k-1 범위의 j에 대해 루프를 실행합니다.
    • 업데이트 dp [i] = 최소값.
    • 포인터 배열을 반복하고 값이 최소값과 같은 인덱스를 1 씩 증가시킵니다.
  5. dp [n]을 반환합니다.

실시

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

nth super ugly number를위한 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이고 다른 하나는 크기이므로 공간 복잡도는 O (n + k).

참조

Translate »