Рубрики

Уродливые числа

Уродливые числа — это числа, единственными простыми множителями которых являются 2, 3 или 5. Последовательность 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,… показывает первые 11 уродливых чисел. По договоренности 1 включено.

По заданному номеру n задача состоит в том, чтобы найти n-ное уродливое число.

Примеры:

Input  : n = 7
Output : 8

Input  : n = 10
Output : 12

Input  : n = 15
Output : 24

Input  : n = 150
Output : 5832

Способ 1 (простой)
Цикл для всех натуральных чисел до тех пор, пока количество некрасивых чисел не станет меньше n, если целое число некрасиво, чем приращение количества некрасивых чисел.

Чтобы проверить, является ли число некрасивым, разделите число на наибольшие делимые степени 2, 3 и 5, если число становится 1, то в противном случае это ужасное число.

Например, давайте посмотрим, как проверить на 300 уродливо или нет. Наибольшая делимая сила 2 равна 4, после деления 300 на 4 мы получаем 75. Наибольшая делимая сила 3 — 3, после деления 75 на 3 мы получаем 25. Наибольшая делимая сила 5 — 25, после деления 25 на 25 мы получаем 1 Так как мы наконец получаем 1, 300 — это ужасное число.

Реализация:

C / C ++

// Программа CPP для поиска n-го уродливого номера
# include<stdio.h>
# include<stdlib.h>

  
/ * Эта функция делит на наибольшее делимое

  мощность б * /

int maxDivide(int a, int b)

{

  while (a%b == 0)

   a = a/b; 

  return a;

}    

  
/ * Функция, чтобы проверить, уродлив ли число или нет * /

int isUgly(int no)

{

  no = maxDivide(no, 2);

  no = maxDivide(no, 3);

  no = maxDivide(no, 5);

    

  return (no == 1)? 1 : 0;

}    

  
/ * Функция для получения n-го уродливого числа * /

int getNthUglyNo(int n)

{

  int i = 1; 

  int count = 1;   / * количество некрасивых чисел * / 

  

  / * Проверять все целые числа до безобразного подсчета

    становится n * / 

  while (n > count)

  {

    i++;      

    if (isUgly(i))

      count++; 

  }

  return i;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    unsigned no = getNthUglyNo(150);

    printf("150th ugly no. is %d ",  no);

    getchar();

    return 0;

}

Джава

// Java-программа для поиска n-го уродливого числа

class GFG {

      

    / * Эта функция делит на наибольшее

    делимая сила b * /

    static int maxDivide(int a, int b)

    {

        while(a % b == 0)

            a = a/b;

        return a;

    }

      

    / * Функция для проверки, если число

    некрасиво или нет * /

    static int isUgly(int no)

    {

        no = maxDivide(no, 2);

        no = maxDivide(no, 3);

        no = maxDivide(no, 5);

          

        return (no == 1)? 1 : 0;

    }

      

    / * Функция, чтобы получить н-уродливый

    число*/

    static int getNthUglyNo(int n)

    {

        int i = 1;

          

        // количество некрасивых чисел

        int count = 1

          

        // проверяем все целые числа

        // пока счет не станет n

        while(n > count)

        {

            i++;

            if(isUgly(i) == 1)

                count++;

        }

        return i;

    }

      

    / * Программа драйвера для тестирования выше

    функции * /

    public static void main(String args[])

    {

        int no = getNthUglyNo(150);

        System.out.println("150th ugly "

                       + "no. is "+ no);

    }

}

  
// Этот код был добавлен
// Амит Хандельвал (Amit Khandelwal 1)

python3

# Python3 код для поиска n-го уродливого числа

  
# Эта функция делит на наибольшее
делимая сила b

def maxDivide( a, b ):

    while a % b == 0:

        a = a / b

    return

  
# Функция для проверки, если число
# уродлив или нет

def isUgly( no ):

    no = maxDivide(no, 2)

    no = maxDivide(no, 3)

    no = maxDivide(no, 5)

    return 1 if no == 1 else 0

  
# Функция для получения n-го уродливого числа

def getNthUglyNo( n ):

    i = 1

    count = 1 # количество некрасивых чисел

  

    # Проверьте все целые числа до

    # безобразный счет становится п

    while n > count:

        i += 1

        if isUgly(i):

            count += 1

    return i

  
# Код драйвера для проверки вышеуказанных функций

no = getNthUglyNo(150)

print("150th ugly no. is ", no)

  
# Этот код предоставлен "Sharad_Bhardwaj".

C #

// C # программа для поиска n-го уродливого числа

using System;

  

class GFG {

  

    / * Эта функция делит на

    наибольшая делимая сила b * /

    static int maxDivide(int a, int b)

    {

        while(a % b == 0)

            a = a / b;

        return a;

    }

      

    / * Функция для проверки, если число

    некрасиво или нет * /

    static int isUgly(int no)

    {

        no = maxDivide(no, 2);

        no = maxDivide(no, 3);

        no = maxDivide(no, 5);

          

        return (no == 1)? 1 : 0;

    }

      

    / * Функция, чтобы получить н-уродливый

    число*/

    static int getNthUglyNo(int n)

    {

        int i = 1;

          

        // количество некрасивых чисел

        int count = 1; 

          

        // проверяем все целые числа

        // пока счет не станет n

        while(n > count)

        {

            i++;

            if(isUgly(i) == 1)

                count++;

        }

        return i;

    }

      

    // Код драйвера

    public static void Main()

    {

        int no = getNthUglyNo(150);

          

        Console.WriteLine("150th ugly"

                  + " no. is " + no);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для поиска n-го уродливого числа

  
// Эта функция делит на
// наибольшая делимая сила б

function maxDivide($a, $b)

{

    while ($a % $b == 0)

    $a = $a / $b

    return $a;

  
// Функция для проверки, если
// номер уродлив или нет

function isUgly($no)

{

    $no = maxDivide($no, 2);

    $no = maxDivide($no, 3);

    $no = maxDivide($no, 5);

      

    return ($no == 1)? 1 : 0;

  
// Функция для получения nth
// некрасивое число

function getNthUglyNo($n)

{

    $i = 1; 

      

    // количество некрасивых чисел

    $count = 1; 

  
// Проверяем все целые числа
// до тех пор, пока счетчик не станет п

while ($n > $count)

{

    $i++;     

    if (isUgly($i))

    $count++; 

}

return $i;

}

  

    // Код драйвера

    $no = getNthUglyNo(150);

    echo "150th ugly no. is ". $no;

  
// Этот код предоставлен Sam007
?>


Выход:

150th ugly no. is 5832 

Этот метод не эффективен по времени, так как он проверяет все целые числа, пока количество некрасивых чисел не станет n, но сложность этого метода в пространстве равна O (1)

Способ 2 (использовать динамическое программирование)
Вот эффективное по времени решение с O (n) дополнительным пространством. Последовательность уродливых чисел: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,…
Поскольку каждое число может быть разделено только на 2, 3, 5, один из способов взглянуть на последовательность состоит в том, чтобы разделить последовательность на три группы, как показано ниже:
(1) 1 × 2, 2 × 2, 3 × 2, 4 × 2, 5 × 2,…
(2) 1 × 3, 2 × 3, 3 × 3, 4 × 3, 5 × 3,…
(3) 1 × 5, 2 × 5, 3 × 5, 4 × 5, 5 × 5,…

Мы можем обнаружить, что каждая подпоследовательность является самой уродливой последовательностью (1, 2, 3, 4, 5,…), умножаем 2, 3, 5. Затем мы используем аналогичный метод слияния, как сортировка слиянием, чтобы получить каждое уродливое число из трех подпоследовательности. Каждый шаг мы выбираем самый маленький и переходим на один шаг позже.

1 Declare an array for ugly numbers:  ugly[n]
2 Initialize first ugly no:  ugly[0] = 1
3 Initialize three array index variables i2, i3, i5 to point to 
   1st element of the ugly array: 
        i2 = i3 = i5 =0; 
4 Initialize 3 choices for the next ugly no:
         next_mulitple_of_2 = ugly[i2]*2;
         next_mulitple_of_3 = ugly[i3]*3
         next_mulitple_of_5 = ugly[i5]*5;
5 Now go in a loop to fill all ugly numbers till 150:
For (i = 1; i < 150; i++ ) 
{
    /* These small steps are not optimized for good 
      readability. Will optimize them in C program */
    next_ugly_no  = Min(next_mulitple_of_2,
                        next_mulitple_of_3,
                        next_mulitple_of_5); 

    ugly[i] =  next_ugly_no       

    if (next_ugly_no  == next_mulitple_of_2) 
    {             
        i2 = i2 + 1;        
        next_mulitple_of_2 = ugly[i2]*2;
    } 
    if (next_ugly_no  == next_mulitple_of_3) 
    {             
        i3 = i3 + 1;        
        next_mulitple_of_3 = ugly[i3]*3;
     }            
     if (next_ugly_no  == next_mulitple_of_5)
     {    
        i5 = i5 + 1;        
        next_mulitple_of_5 = ugly[i5]*5;
     } 
     
}/* end of for loop */ 
6.return next_ugly_no

Пример:
Давайте посмотрим, как это работает

initialize
   ugly[] =  | 1 |
   i2 =  i3 = i5 = 0;

First iteration
   ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
            = Min(2, 3, 5)
            = 2
   ugly[] =  | 1 | 2 |
   i2 = 1,  i3 = i5 = 0  (i2 got incremented ) 

Second iteration
    ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 3, 5)
             = 3
    ugly[] =  | 1 | 2 | 3 |
    i2 = 1,  i3 =  1, i5 = 0  (i3 got incremented ) 

Third iteration
    ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 6, 5)
             = 4
    ugly[] =  | 1 | 2 | 3 |  4 |
    i2 = 2,  i3 =  1, i5 = 0  (i2 got incremented )

Fourth iteration
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 5)
              = 5
    ugly[] =  | 1 | 2 | 3 |  4 | 5 |
    i2 = 2,  i3 =  1, i5 = 1  (i5 got incremented )

Fifth iteration
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 10)
              = 6
    ugly[] =  | 1 | 2 | 3 |  4 | 5 | 6 |
    i2 = 3,  i3 =  2, i5 = 1  (i2 and i3 got incremented )

Will continue same way till I < 150

C / C ++

// C ++ программа для поиска n-го уродливого числа
# include<bits/stdc++.h>

using namespace std;

  
/ * Функция для получения n-го уродливого числа * /
unsigned getNthUglyNo(unsigned n)
{

    unsigned ugly[n]; // Хранить некрасивые числа

    unsigned i2 = 0, i3 = 0, i5 = 0;

    unsigned next_multiple_of_2 = 2;

    unsigned next_multiple_of_3 = 3;

    unsigned next_multiple_of_5 = 5;

    unsigned next_ugly_no = 1;

  

    ugly[0] = 1;

    for (int i=1; i<n; i++)

    {

       next_ugly_no = min(next_multiple_of_2,

                           min(next_multiple_of_3,

                               next_multiple_of_5));

       ugly[i] = next_ugly_no;

       if (next_ugly_no == next_multiple_of_2)

       {

           i2 = i2+1;

           next_multiple_of_2 = ugly[i2]*2;

       }

       if (next_ugly_no == next_multiple_of_3)

       {

           i3 = i3+1;

           next_multiple_of_3 = ugly[i3]*3;

       }

       if (next_ugly_no == next_multiple_of_5)

       {

           i5 = i5+1;

           next_multiple_of_5 = ugly[i5]*5;

       }

    } / * Конец цикла for (i = 1; i <n; i ++) * /

    return next_ugly_no;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int n = 150;

    cout << getNthUglyNo(n);

    return 0;

}

Джава

// Java-программа для поиска n-го уродливого числа

import java.lang.Math;

  

class UglyNumber

{

    / * Функция для получения n-го уродливого числа * /

    int getNthUglyNo(int n)

    {

        int ugly[] = new int[n];  // Хранить некрасивые числа

        int i2 = 0, i3 = 0, i5 = 0;

        int next_multiple_of_2 = 2;

        int next_multiple_of_3 = 3;

        int next_multiple_of_5 = 5;

        int next_ugly_no = 1;

          

        ugly[0] = 1;

          

        for(int i = 1; i < n; i++)

        {

            next_ugly_no = Math.min(next_multiple_of_2,

                                  Math.min(next_multiple_of_3,

                                        next_multiple_of_5));

              

            ugly[i] = next_ugly_no;

            if (next_ugly_no == next_multiple_of_2)

            {

               i2 = i2+1;

               next_multiple_of_2 = ugly[i2]*2;

            }

            if (next_ugly_no == next_multiple_of_3)

            {

               i3 = i3+1;

               next_multiple_of_3 = ugly[i3]*3;

            }

            if (next_ugly_no == next_multiple_of_5)

            {

               i5 = i5+1;

               next_multiple_of_5 = ugly[i5]*5;

            }

        } / * Конец цикла for (i = 1; i <n; i ++) * /

        return next_ugly_no;

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String args[])

    {

        int n = 150;

        UglyNumber obj = new UglyNumber();

        System.out.println(obj.getNthUglyNo(n));

    }

}

  
// Этот код предоставлен Амитом Хандельвалом (Amit Khandelwal 1)

питон

# Программа Python для поиска n-го уродливого числа

  
# Функция для получения n-го уродливого числа

def getNthUglyNo(n):

  

    ugly = [0] * n # Хранить некрасивые номера

  

    № 1 - первое уродливое число

    ugly[0] = 1

  

    # i2, i3, i5 будут обозначать индексы соответственно 2,3,5

    i2 = i3 =i5 = 0

  

    # установить начальное множественное значение

    next_multiple_of_2 = 2

    next_multiple_of_3 = 3

    next_multiple_of_5 = 5

  

    # цикл запуска, чтобы найти значение от уродливого [1] до уродливого [n]

    for l in range(1, n):

  

        # выберите минимальное значение всех доступных кратных

        ugly[l] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)

  

        # увеличить значение индекса соответственно

        if ugly[l] == next_multiple_of_2:

            i2 += 1

            next_multiple_of_2 = ugly[i2] * 2

  

        if ugly[l] == next_multiple_of_3:

            i3 += 1

            next_multiple_of_3 = ugly[i3] * 3

  

        if ugly[l] == next_multiple_of_5: 

            i5 += 1

            next_multiple_of_5 = ugly[i5] * 5

  

    # вернуть уродливое [n] значение

    return ugly[-1]

  

def main():

  

    n = 150

  

    print getNthUglyNo(n)

  

  

if __name__ == '__main__':

    main()

  
# Этот код предоставлен Ниламом Ядавом

C #

// C # программа для подсчета инверсий в массиве

using System;

using System.Collections.Generic;

  

class GFG {

  

    / * Функция для получения n-го уродливого числа * /

    static int getNthUglyNo(int n)

    {

          

        // Хранить некрасивые числа

        int []ugly = new int[n]; 

        int i2 = 0, i3 = 0, i5 = 0;

        int next_multiple_of_2 = 2;

        int next_multiple_of_3 = 3;

        int next_multiple_of_5 = 5;

        int next_ugly_no = 1;

          

        ugly[0] = 1;

          

        for(int i = 1; i < n; i++)

        {

            next_ugly_no = Math.Min(next_multiple_of_2,

                           Math.Min(next_multiple_of_3,

                                  next_multiple_of_5));

              

            ugly[i] = next_ugly_no;

              

            if (next_ugly_no == next_multiple_of_2)

            {

                i2 = i2 + 1;

                next_multiple_of_2 = ugly[i2] * 2;

            }

              

            if (next_ugly_no == next_multiple_of_3)

            {

                i3 = i3 + 1;

                next_multiple_of_3 = ugly[i3] * 3;

            }

            if (next_ugly_no == next_multiple_of_5)

            {

                i5 = i5 + 1;

                next_multiple_of_5 = ugly[i5] * 5;

            }

        

          

        return next_ugly_no;

    }

      

    // Код драйвера

    public static void Main()

    {

        int n = 150;

        Console.WriteLine(getNthUglyNo(n));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска
// уродливое число

  
// Функция для получения
// уродливое число

function getNthUglyNo($n)

{

    // Хранить некрасивые числа

    $ugly = array_fill(0, $n, 0);

    $i2 = 0;

    $i3 = 0;

    $i5 = 0;

    $next_multiple_of_2 = 2;

    $next_multiple_of_3 = 3;

    $next_multiple_of_5 = 5;

    $next_ugly_no = 1;

  

    $ugly[0] = 1;

    for ($i = 1; $i < $n; $i++)

    {

    $next_ugly_no = min($next_multiple_of_2,

                    min($next_multiple_of_3,

                        $next_multiple_of_5));

    $ugly[$i] = $next_ugly_no;

    if ($next_ugly_no == 

        $next_multiple_of_2)

    {

        $i2 = $i2 + 1;

        $next_multiple_of_2 = $ugly[$i2] * 2;

    }

    if ($next_ugly_no == 

        $next_multiple_of_3)

    {

        $i3 = $i3 + 1;

        $next_multiple_of_3 = $ugly[$i3] * 3;

    }

    if ($next_ugly_no == 

        $next_multiple_of_5)

    {

        $i5 = $i5 + 1;

        $next_multiple_of_5 = $ugly[$i5] * 5;

    }

    } / * Конец цикла for (i = 1; i <n; i ++) * /

    return $next_ugly_no;

}

  
// Код драйвера

$n = 150;

echo getNthUglyNo($n);

  
// Этот код предоставлен mits
?>


Выход :

5832

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Super Ugly Number (Число, чьи главные факторы в данном наборе)

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в вышеуказанной программе или другие способы решения той же проблемы.

Рекомендуемые посты:

Уродливые числа

0.00 (0%) 0 votes