Contar números de n dígitos que son monótonos – Part 1

Posted on by Rudeus Greyrat

Llame monótono a un número decimal si:  D[\, i]\, \leqslant D[\, i+1]\, 0 \leqslant i \leqslant |D| . Escriba un programa que tome un número positivo n en la entrada y devuelva una cantidad de números decimales de longitud n que sean monótonos. Los números no pueden comenzar con 0. Ejemplos:

Input : 1
Output : 9
Numbers are 1, 2, 3, ... 9

Input : 2
Output : 45
Numbers are 11, 12, 13, .... 22, 23
...29, 33, 34, ... 39.
Count is 9 + 8 + 7 ... + 1 = 45

Explicación: Comencemos con un ejemplo de números monótonos: \{111\}, \{123\}, \{12223333444\} todos esos números son monótonos ya que cada dígito en un lugar más alto es  \geq el anterior. ¿Cuáles son los números monótonos de longitud 1 y dígitos 1 o 2? Es una pregunta que debes hacerte desde el principio. Podemos ver que los números posibles son:  \{1\}, \{2\} Eso fue fácil, ahora ampliemos la pregunta a los dígitos 1, 2 y 3:  \{1\}, \{2\}, \{3\} Ahora una pregunta diferente, ¿cuáles son los diferentes números monótonos que consisten en solo 1 y longitud 3 que hay? \{111\} Intentemos ahora dibujar esta observación muy simple en una array bidimensional para el número de longitud 3, donde la primera columna es la longitud de la string y la primera fila son los dígitos posibles: \begin{array}{c c c c c c c c c c} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\\ 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\\ \end{array} Intentemos llenar la tercera fila, la tercera columna (cantidad de números monótonos que consisten en los números 1 o 2 con una longitud de 2). Esto debería ser:  \{11\}, \{12\}, \{22\} Si miramos más de cerca, ya tenemos subconjuntos de este conjunto, es decir:  \{11\}, \{12\} – Números monótonos que tienen una longitud de 2 y consisten en 1 o 2  \{22\} – Números monótonos de longitud 2 y que consisten en el número 2 Solo necesitamos agregar los valores anteriores a conseguir el más largo. La array final debería verse así: \begin{array}{c c c c c c c c c c} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\\ 2 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 47 &\\ 3 & 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 & 167 &\\ \end{array}

C++

// CPP program to count numbers of n digits
// that are  monotone.
#include <cstring>
#include <iostream>
 
// Considering all possible digits as {1, 2, 3, ..9}
int static const DP_s = 9;
 
int getNumMonotone(int len)
{
    // DP[i][j] is going to store monotone numbers of length
    // i+1 considering j+1 digits.
    int DP[len][DP_s];
    memset(DP, 0, sizeof(DP));
    // Unit length numbers
    for (int i = 0; i < DP_s; ++i)
        DP[0][i] = i + 1;
    // Single digit numbers
    for (int i = 0; i < len; ++i)
        DP[i][0] = 1;
    // Filling rest of the entries in bottom
    // up manner.
    for (int i = 1; i < len; ++i)
        for (int j = 1; j < DP_s; ++j)
            DP[i][j] = DP[i - 1][j] + DP[i][j - 1];
    return DP[len - 1][DP_s - 1];
}
 
// Driver code.
int main()
{
    std::cout << getNumMonotone(10);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

C

// C program to count numbers of n digits
// that are monotone.
#include <stdio.h>
#include <string.h>
 
// Considering all possible digits as
// {1, 2, 3, ..9}
int static const DP_s = 9;
 
int getNumMonotone(int len)
{
 
    // DP[i][j] is going to store monotone numbers of length
    // i+1 considering j+1 digits.
    int DP[len][DP_s];
    memset(DP, 0, sizeof(DP));
 
    // Unit length numbers
    for (int i = 0; i < DP_s; ++i)
        DP[0][i] = i + 1;
 
    // Single digit numbers
    for (int i = 0; i < len; ++i)
        DP[i][0] = 1;
 
    // Filling rest of the entries in bottom up manner.
    for (int i = 1; i < len; ++i)
        for (int j = 1; j < DP_s; ++j)
            DP[i][j] = DP[i - 1][j] + DP[i][j - 1];
 
    return DP[len - 1][DP_s - 1];
}
 
// Driver code.
int main()
{
    printf("%d", getNumMonotone(10));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

Java

// Java program to count numbers
// of n digits that are monotone.
 
class GFG
{
    // Considering all possible
    // digits as {1, 2, 3, ..9}
    static final int DP_s = 9;
     
    static int getNumMonotone(int len)
    {
     
        // DP[i][j] is going to store
        // monotone numbers of length
        // i+1 considering j+1 digits.
        int[][] DP = new int[len][DP_s];
     
        // Unit length numbers
        for (int i = 0; i < DP_s; ++i)
            DP[0][i] = i + 1;
     
        // Single digit numbers
        for (int i = 0; i < len; ++i)
            DP[i][0] = 1;
     
        // Filling rest of the entries
        // in bottom up manner.
        for (int i = 1; i < len; ++i)
            for (int j = 1; j < DP_s; ++j)
                DP[i][j] = DP[i - 1][j]
                           + DP[i][j - 1];
     
        return DP[len - 1][DP_s - 1];
    }
     
    // Driver code.
    public static void main (String[] args)
    {
        System.out.println(getNumMonotone(10));
    }
}
 
// This code is contributed by Ansu Kumari.

Python3

# Python3 program to count numbers of n
# digits that are monotone.
 
# Considering all possible digits as
# {1, 2, 3, ..9}
DP_s = 9
 
def getNumMonotone(ln):
 
    # DP[i][j] is going to store monotone
    # numbers of length i+1 considering
    # j+1 digits.
    DP = [[0]*DP_s for i in range(ln)]
 
    # Unit length numbers
    for i in range(DP_s):
        DP[0][i] = i + 1
 
    # Single digit numbers
    for i in range(ln):
        DP[i][0] = 1
 
    # Filling rest of the entries 
    # in bottom up manner.
    for i in range(1, ln):
 
        for j in range(1, DP_s):
            DP[i][j] = DP[i - 1][j] + DP[i][j - 1]
 
    return DP[ln - 1][DP_s - 1]
 
 
# Driver code
print(getNumMonotone(10))
 
 
# This code is contributed by Ansu Kumari

C#

// C# program to count numbers
// of n digits that are monotone.
using System;
 
class GFG
{
    // Considering all possible
    // digits as {1, 2, 3, ..9}
    static int DP_s = 9;
     
    static int getNumMonotone(int len)
    {
     
        // DP[i][j] is going to store
        // monotone numbers of length
        // i+1 considering j+1 digits.
        int[,] DP = new int[len,DP_s];
     
        // Unit length numbers
        for (int i = 0; i < DP_s; ++i)
            DP[0,i] = i + 1;
     
        // Single digit numbers
        for (int i = 0; i < len; ++i)
            DP[i,0] = 1;
     
        // Filling rest of the entries
        // in bottom up manner.
        for (int i = 1; i < len; ++i)
            for (int j = 1; j < DP_s; ++j)
                DP[i,j] = DP[i - 1,j]
                        + DP[i,j - 1];
     
        return DP[len - 1,DP_s - 1];
    }
     
    // Driver code.
    public static void Main ()
    {
        Console.WriteLine(getNumMonotone(10));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to count numbers
// of n digits that are monotone.
function getNumMonotone($len)
{
    // Considering all possible
    // digits as {1, 2, 3, ..9}
    $DP_s = 9;
 
 
    // DP[i][j] is going to store
    // monotone numbers of length
    // i+1 considering j+1 digits.
    $DP = array(array_fill(0, $len, 0),
                array_fill(0, $len, 0));
 
    // Unit length numbers
    for ($i = 0; $i < $DP_s; ++$i)
        $DP[0][$i] = $i + 1;
 
    // Single digit numbers
    for ($i = 0; $i < $len; ++$i)
        $DP[$i][0] = 1;
 
    // Filling rest of the entries
    // in bottom up manner.
    for ($i = 1; $i < $len; ++$i)
        for ($j = 1; $j < $DP_s; ++$j)
            $DP[$i][$j] = $DP[$i - 1][$j] +
                          $DP[$i][$j - 1];
 
    return $DP[$len - 1][$DP_s - 1];
}
 
// Driver code
echo getNumMonotone(10);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// JavaScript program to count numbers of n
// digits that are monotone.
 
// Considering all possible digits as
// {1, 2, 3, ..9}
let DP_s = 9
 
function getNumMonotone(ln){
 
    // DP[i][j] is going to store monotone
    // numbers of length i+1 considering
    // j+1 digits.
    let DP = new Array(ln).fill(0).map(()=>new Array(DP_s).fill(0))
 
    // Unit length numbers
    for(let i=0;i<DP_s;i++){
        DP[0][i] = i + 1
    }
 
    // Single digit numbers
    for(let i=0;i<ln;i++)
        DP[i][0] = 1
 
    // Filling rest of the entries
    // in bottom up manner.
    for(let i=1;i<ln;i++){
 
        for(let j=1;j<DP_s;j++){
            DP[i][j] = DP[i - 1][j] + DP[i][j - 1]
        }
    }
 
    return DP[ln - 1][DP_s - 1]
}
 
 
// Driver code
document.write(getNumMonotone(10),"</br>")
 
 
// This code is contributed by shinjanpatra
 
</script>

Producción :

43758

Publicación traducida automáticamente

Artículo escrito por Mateusz_Wojtczak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *