Super çirkin nömrə

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur google
Yığın RiyaziyyatBaxılıb 27

N-i tapmaq üçün bir proqram yazınth super çirkin nömrə. Super çirkin rəqəmlər, bütün əsas amillər k ölçüsündə verilən əsas siyahıların əsaslarında olan müsbət ədədlərdir.

Qeyd:  1 ilk super çirkin nömrə sayılır.

Yanaşma 1: Kobud güc

Əsas fikir

1-dən olan bütün təbii ədədlər üzərində təkrarlayacağıq və tapdığımız çirkin rəqəmlərin sayını və sayının n-ə bərabər olacağını hesablayan bir sayma dəyişənini qoruyacağıq, bu ədədi çap edəcəyik.

Nömrənin super çirkin bir rəqəm olub olmadığını necə yoxlamaq olar?

Ədədin bütün əsas bölmələrini tapacağıq və onun bütün əsas bölmələri verilmiş 'əsaslar' siyahısında olduqda, rəqəm çox çirkin bir rəqəmdir və əksinə.

Yanaşma 2: Dinamik proqramlaşdırma 

Həll

Bu sual K sıralanmış massivlərin birləşməsi ilə eynidir.

Məsələnbiz var

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

Output: 21

Siyahımız belə davam edəcək:

Super çirkin nömrəPin

Alqoritm

  1. Bir dp elan edin array burada dp [i] i-ni təmsil edirth super çirkin nömrə.
  2. Dp [1] = 1 başlayın.
  3. [İ] göstəricisinin i göstəricisini təmsil etdiyi k ölçülü bir göstərici massivini işə salınth verilmiş massivdə əsas nömrə.
  4. 2-dən n aralığında i üçün bir döngə işlədin:
    • Dp [göstərici [j]] * əsaslarının [j] minimum dəyərini tapmaq üçün 0-dan k-1 aralığında j üçün bir döngə işlədin.
    • Dp [i] = minimum dəyərini yeniləyin.
    • Göstərici massivi üzərində təkrarlayın və dəyəri minimum dəyərə bərabər olan bu göstəriciləri 1 artırın.
  5. Dp [n] qayıdın.

Həyata keçirilməsi

Üçüncü super çirkin nömrələr üçün C ++ proqramı

#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

Ninci super çirkin nömrə üçün JAVA proqramı

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

Üçüncü super çirkin rəqəmlər üçün mürəkkəblik analizi

Zaman mürəkkəbliyi

Əvvəlcə 2-dən N-ə, ikincisi 0-dan k-1-ə qədər iki iç içə döngə var, buna görə zamanın mürəkkəbliyi O (n * k).

Kosmik mürəkkəblik

Biri n, digəri k ölçülü iki massiv, beləliklə kosmik mürəkkəblikdir O (n + k).

References

Translate »