Рубрики

Проблема с цифровой клавиатурой

Динамическое программирование, Матрицы, Строки

Учитывая мобильную цифровую клавиатуру. Вы можете нажимать только кнопки вверх, влево, вправо или вниз до текущей кнопки. Вам не разрешается нажимать кнопки в нижнем ряду (например, * и #).


Дано число N, узнать количество возможных чисел заданной длины.

Примеры:
Для N = 1 число возможных чисел будет 10 (0, 1, 2, 3,…, 9)
Для N = 2 число возможных чисел будет 36
Возможные номера: 00,08 11,12,14 22,21,23,25 и так далее.
Если мы начнем с 0, действительные числа будут 00, 08 (количество: 2)
Если мы начнем с 1, действительные числа будут 11, 12, 14 (количество: 3)
Если мы начнем с 2, действительные числа будут 22, 21, 23,25 (количество: 4)
Если мы начнем с 3, действительные числа будут 33, 32, 36 (количество: 3)
Если мы начнем с 4, действительные числа будут 44,41,45,47 (количество: 4)
Если мы начнем с 5, действительные числа будут 55,54,52,56,58 (количество: 5)
………………………………
………………………………

Нам нужно распечатать количество возможных номеров.

N = 1 — тривиальный случай, число возможных чисел будет равно 10 (0, 1, 2, 3,…, 9)
Для N> 1 нам нужно начать с какой-то кнопки, затем перейти в любое из четырех направлений (вверх, влево, вправо или вниз), что приводит к действительной кнопке (не следует переходить к *, #). Продолжайте делать это до тех пор, пока не получите номер длины N (первый проход по глубине).

Рекурсивное решение:
Мобильная клавиатура представляет собой прямоугольную сетку 4X3 (4 ряда и 3 столбца)
Допустим, что Count (i, j, N) представляет собой количество N длинных чисел, начиная с позиции (i, j)

If N = 1
  Count(i, j, N) = 10  
Else
  Count(i, j, N) = Sum of all Count(r, c, N-1) where (r, c) is new 
                   position after valid move of length 1 from current 
                   position (i, j)

Ниже приведена реализация приведенной выше рекурсивной формулы.

C ++

// Наивная рекурсивная программа на C для подсчета количества возможных чисел
// заданной длины
#include <stdio.h>

  
// влево, вверх, вправо, вниз от текущего местоположения

int row[] = {0, 0, -1, 0, 1};

int col[] = {0, -1, 0, 1, 0};

  
// Возвращает количество чисел длины n, начиная с ключевой позиции
// (i, j) на цифровой клавиатуре.

int getCountUtil(char keypad[][3], int i, int j, int n)

{

    if (keypad == NULL || n <= 0)

        return 0;

  

    // Из данного ключа возможен только один номер длины 1

    if (n == 1)

        return 1;

  

    int k=0, move=0, ro=0, co=0, totalCount = 0;

  

    // двигаться влево, вверх, вправо, вниз от текущего местоположения, и если

    // новое местоположение является действительным, затем получаем число по длине

    // (n-1) из этой новой позиции и добавляем подсчет, полученный до сих пор

    for (move=0; move<5; move++)

    {

        ro = i + row[move];

        co = j + col[move];

        if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 &&

           keypad[ro][co] != '*' && keypad[ro][co] != '#')

        {

            totalCount += getCountUtil(keypad, ro, co, n-1);

        }

    }

  

    return totalCount;

}

  
// Возвращаем количество всех возможных чисел длины n
// в заданной цифровой клавиатуре

int getCount(char keypad[][3], int n)

{

    // Базовые случаи

    if (keypad == NULL || n <= 0)

        return 0;

    if (n == 1)

        return 10;

  

    int i=0, j=0, totalCount = 0;

    for (i=0; i<4; i++)  // Цикл в строке клавиатуры

    {

        for (j=0; j<3; j++)   // Цикл на колонке клавиатуры

        {

            // Обработка от 0 до 9 цифр

            if (keypad[i][j] != '*' && keypad[i][j] != '#')

            {

                // Получить счетчик, когда число начинается с ключа

                // позиция (i, j) и добавление в подсчет, полученный до сих пор

                totalCount += getCountUtil(keypad, i, j, n);

            }

        }

    }

    return totalCount;

}

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

int main(int argc, char *argv[])

{

   char keypad[4][3] = {{'1','2','3'},

                        {'4','5','6'},

                        {'7','8','9'},

                        {'*','0','#'}};

   printf("Count for numbers of length %d: %dn", 1, getCount(keypad, 1));

   printf("Count for numbers of length %d: %dn", 2, getCount(keypad, 2));

   printf("Count for numbers of length %d: %dn", 3, getCount(keypad, 3));

   printf("Count for numbers of length %d: %dn", 4, getCount(keypad, 4));

   printf("Count for numbers of length %d: %dn", 5, getCount(keypad, 5));

  

   return 0;

}

Джава

// Наивная рекурсивная Java-программа
// посчитать количество возможных
// числа заданной длины

class GfG

{

  
// влево, вверх, вправо, вниз
// переместиться из текущего местоположения

static int row[] = {0, 0, -1, 0, 1};

static int col[] = {0, -1, 0, 1, 0};

  
// Возвращает количество чисел длины
// n начиная с ключевой позиции
// (i, j) на цифровой клавиатуре.

static int getCountUtil(char keypad[][], 

                        int i, int j, int n)

{

    if (keypad == null || n <= 0)

        return 0;

  

    // из данного ключа только один

    // возможно число длины 1

    if (n == 1)

        return 1;

  

    int k = 0, move = 0, ro = 0, co = 0, totalCount = 0;

  

    // двигаться влево, вверх, вправо, вниз

    // из текущего местоположения и если

    // новое местоположение действительно, тогда

    // получаем число по длине

    // (n-1) из этой новой позиции

    // и добавить в подсчет, полученный до сих пор

    for (move=0; move<5; move++)

    {

        ro = i + row[move];

        co = j + col[move];

        if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 &&

        keypad[ro][co] != '*' && keypad[ro][co] != '#')

        {

            totalCount += getCountUtil(keypad, ro, co, n - 1);

        }

    }

    return totalCount;

}

  
// Возвращаем количество всех возможных чисел длины n
// в заданной цифровой клавиатуре

static int getCount(char keypad[][], int n)

{

    // Базовые случаи

    if (keypad == null || n <= 0)

        return 0;

    if (n == 1)

        return 10;

  

    int i = 0, j = 0, totalCount = 0;

    for (i = 0; i < 4; i++) // Цикл в строке клавиатуры

    {

        for (j=0; j<3; j++) // Цикл на колонке клавиатуры

        {

            // Обработка от 0 до 9 цифр

            if (keypad[i][j] != '*' && keypad[i][j] != '#')

            {

                // Получить счетчик, когда число начинается с ключа

                // позиция (i, j) и добавление в подсчет, полученный до сих пор

                totalCount += getCountUtil(keypad, i, j, n);

            }

        }

    }

    return totalCount;

}

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

public static void main(String[] args) 

{

    char keypad[][] = {{'1','2','3'},

                        {'4','5','6'},

                        {'7','8','9'},

                        {'*','0','#'}};

    System.out.printf("Count for numbers of"+

                    " length %d: %d", 1, getCount(keypad, 1));

    System.out.printf("\nCount for numbers of" + 

                    "length %d: %d", 2, getCount(keypad, 2));

    System.out.printf("\nCount for numbers of" + 

                    "length %d: %d", 3, getCount(keypad, 3));

    System.out.printf("\nCount for numbers of" + 

                    "length %d: %d", 4, getCount(keypad, 4));

    System.out.printf("\nCount for numbers of" + 

                    "length %d: %d", 5, getCount(keypad, 5));

}
}

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

C #

// Наивная рекурсивная программа на C #
// посчитать количество возможных
// числа заданной длины

using System;

  

class GfG

{

  
// влево, вверх, вправо, вниз
// переместиться из текущего местоположения

static int []row = {0, 0, -1, 0, 1};

static int []col = {0, -1, 0, 1, 0};

  
// Возвращает количество чисел длины
// n начиная с ключевой позиции
// (i, j) на цифровой клавиатуре.

static int getCountUtil(char [,]keypad, 

                        int i, int j, int n)

{

    if (keypad == null || n <= 0)

        return 0;

  

    // из данного ключа только один

    // возможно число длины 1

    if (n == 1)

        return 1;

  

    int k = 0, move = 0, ro = 0, co = 0, totalCount = 0;

  

    // двигаться влево, вверх, вправо, вниз

    // из текущего местоположения и если

    // новое местоположение действительно, тогда

    // получаем число по длине

    // (n-1) из этой новой позиции

    // и добавить в подсчет, полученный до сих пор

    for (move=0; move<5; move++)

    {

        ro = i + row[move];

        co = j + col[move];

        if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 &&

        keypad[ro,co] != '*' && keypad[ro,co] != '#')

        {

            totalCount += getCountUtil(keypad, ro, co, n - 1);

        }

    }

    return totalCount;

}

  
// Возвращаем количество всех возможных чисел длины n
// в заданной цифровой клавиатуре

static int getCount(char [,]keypad, int n)

{

    // Базовые случаи

    if (keypad == null || n <= 0)

        return 0;

    if (n == 1)

        return 10;

  

    int i = 0, j = 0, totalCount = 0;

    for (i = 0; i < 4; i++) // Цикл в строке клавиатуры

    {

        for (j = 0; j < 3; j++) // Цикл на колонке клавиатуры

        {

            // Обработка от 0 до 9 цифр

            if (keypad[i, j] != '*' && keypad[i, j] != '#')

            {

                // Получить счетчик, когда число начинается с ключа

                // позиция (i, j) и добавление в подсчет, полученный до сих пор

                totalCount += getCountUtil(keypad, i, j, n);

            }

        }

    }

    return totalCount;

}

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

public static void Main() 

{

    char [,]keypad = {{'1','2','3'},

                        {'4','5','6'},

                        {'7','8','9'},

                        {'*','0','#'}};

    Console.Write("Count for numbers of"+

                    " length {0}: {1}", 1, getCount(keypad, 1));

    Console.Write("\nCount for numbers of" + 

                    "length {0}: {1}", 2, getCount(keypad, 2));

    Console.Write("\nCount for numbers of" + 

                    "length {0}: {1}", 3, getCount(keypad, 3));

    Console.Write("\nCount for numbers of" + 

                    "length {0}: {1}", 4, getCount(keypad, 4));

    Console.Write("\nCount for numbers of" + 

                    "length {0}: {1}", 5, getCount(keypad, 5));

}
}

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

PHP

<?php
// Наивная рекурсивная PHP-программа
// посчитать количество возможных
// числа заданной длины
// влево, вверх, вправо, вниз
// переместиться из текущего местоположения
// static $ row = array (0, 0, -1, 0, 1);
// static $ col = array (0, -1, 0, 1, 0);

  
// Возвращает количество чисел длины
// n начиная с ключевой позиции
// (i, j) на цифровой клавиатуре.

function getCountUtil($keypad, 

                        $i, $j, $n)

{

    static $row= array(0,0,-1,0,1);

    static $col= array(0,-1,0,1,0);

    if ($keypad == null || $n <= 0)

        return 0;

  

    // из данного ключа только один

    // возможно число длины 1

    if ($n == 1)

        return 1;

  

    $k = 0; $move = 0; $ro = 0; $co = 0; $totalCount = 0;

  

    // двигаться влево, вверх, вправо, вниз

    // из текущего местоположения и если

    // новое местоположение действительно, тогда

    // получаем число по длине

    // (n-1) из этой новой позиции

    // и добавить в подсчет, полученный до сих пор

    for ($move = 0; $move < 5; $move++)

    {

        $ro = $i + $row[$move];

        $co = $j + $col[$move];

        if ($ro >= 0 && $ro <= 3 && $co >=0 && $co <= 2 &&

        $keypad[$ro][$co] != '*' && $keypad[$ro][$co] != '#')

        {

            $totalCount += getCountUtil($keypad, $ro, $co, $n - 1);

        }

    }

    return $totalCount;

}

  
// Возвращаем количество всех возможных чисел длины n
// в заданной цифровой клавиатуре

function getCount($keypad, $n)

{

    // Базовые случаи

    if ($keypad == null || $n <= 0)

        return 0;

    if ($n == 1)

        return 10;

  

    $i = 0; $j = 0; $totalCount = 0;

    for ($i = 0; $i < 4; $i++) // Цикл в строке клавиатуры

    {

        for ($j = 0; $j < 3; $j++) // Цикл на колонке клавиатуры

        {

            // Обработка от 0 до 9 цифр

            if ($keypad[$i][$j] != '*' && $keypad[$i][$j] != '#')

            {

                // Получить счетчик, когда число начинается с ключа

                // позиция (i, j) и добавление в подсчет, полученный до сих пор

                $totalCount += getCountUtil($keypad, $i, $j, $n);

            }

        }

    }

    return $totalCount;

}

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

    $keypad = array(array('1','2','3'),

                        array('4','5','6'),

                        array('7','8','9'),

                        array('*','0','#'));

    echo("Count for numbers of"." length". getCount($keypad, 1)); 

    echo("\nCount for numbers of" . 

                    " length ". getCount($keypad, 2));

    echo("\nCount for numbers of" . 

                    " length ".getCount($keypad, 3));

    echo("\nCount for numbers of" .

                    " length ".getCount($keypad, 4));

    echo("\nCount for numbers of" . 

                    " length ".getCount($keypad, 5));

}

  
// Этот код был добавлен Code_Mech.

Выход:

Count for numbers of length 1: 10
Count for numbers of length 2: 36
Count for numbers of length 3: 138
Count for numbers of length 4: 532
Count for numbers of length 5: 2062

Динамическое программирование
Существует много повторных обходов на меньших путях (обход для меньших N), чтобы найти все возможные более длинные пути (обход для больших N). Смотрите следующие две диаграммы, например. В этом обходе для N = 4 из двух начальных позиций (кнопки «4» и «8») мы видим, что существует несколько повторных обходов для N = 2 (например, 4 -> 1, 6 -> 3, 8 -> 9, 8 -> 7 и т. Д.).

Поскольку проблема имеет оба свойства: оптимальная подструктура и перекрывающиеся подзадачи , ее можно эффективно решить с помощью динамического программирования.

Ниже приводится программа для реализации динамического программирования.

C ++

// Программа C на основе динамического программирования для подсчета количества
// возможные числа заданной длины
#include <stdio.h>

  
// Возвращаем количество всех возможных чисел длины n
// в заданной цифровой клавиатуре

int getCount(char keypad[][3], int n)

{

    if(keypad == NULL || n <= 0)

        return 0;

    if(n == 1)

        return 10;

  

    // влево, вверх, вправо, вниз от текущего местоположения

    int row[] = {0, 0, -1, 0, 1};

    int col[] = {0, -1, 0, 1, 0};

  

    // берём n + 1 для простоты - count [i] [j] сохранит

    // число, начинающееся с цифры i и длины j

    int count[10][n+1];

    int i=0, j=0, k=0, move=0, ro=0, co=0, num = 0;

    int nextNum=0, totalCount = 0;

  

    // считать числа, начинающиеся с цифры i и длины 0 и 1

    for (i=0; i<=9; i++)

    {

        count[i][0] = 0;

        count[i][1] = 1;

    }

  

    // снизу вверх - получаем счетчик чисел длины 2, 3, 4, ..., n

    for (k=2; k<=n; k++)

    {

        for (i=0; i<4; i++)  // Цикл в строке клавиатуры

        {

            for (j=0; j<3; j++)   // Цикл на колонке клавиатуры

            {

                // Обработка от 0 до 9 цифр

                if (keypad[i][j] != '*' && keypad[i][j] != '#')

                {

                    // Здесь мы считаем числа, начинающиеся с

                    // цифровая клавиатура [i] [j] и длина клавиатуры k [i] [j]

                    // станет первой цифрой, и нам нужно искать

                    // (k-1) больше цифр

                    num = keypad[i][j] - '0';

                    count[num][k] = 0;

  

                    // двигаться влево, вверх, вправо, вниз от текущего местоположения

                    // и если новое местоположение действительно, тогда получить номер

                    // отсчет длины (k-1) от этой новой цифры и

                    // добавить количество, которое мы нашли до сих пор

                    for (move=0; move<5; move++)

                    {

                        ro = i + row[move];

                        co = j + col[move];

                        if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 &&

                           keypad[ro][co] != '*' && keypad[ro][co] != '#')

                        {

                            nextNum = keypad[ro][co] - '0';

                            count[num][k] += count[nextNum][k-1];

                        }

                    }

                }

            }

        }

    }

  

    // Получить отсчет всех возможных чисел длины "n" начиная

    // с цифрой 0, 1, 2, ..., 9

    totalCount = 0;

    for (i=0; i<=9; i++)

        totalCount += count[i][n];

    return totalCount;

}

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

int main(int argc, char *argv[])

{

   char keypad[4][3] = {{'1','2','3'},

                        {'4','5','6'},

                        {'7','8','9'},

                        {'*','0','#'}};

   printf("Count for numbers of length %d: %dn", 1, getCount(keypad, 1));

   printf("Count for numbers of length %d: %dn", 2, getCount(keypad, 2));

   printf("Count for numbers of length %d: %dn", 3, getCount(keypad, 3));

   printf("Count for numbers of length %d: %dn", 4, getCount(keypad, 4));

   printf("Count for numbers of length %d: %dn", 5, getCount(keypad, 5));

  

   return 0;

}

Джава

// Java-программа на основе динамического программирования для
// подсчитать количество возможных чисел заданной длины

class GFG

{

      
// Возвращаем количество всех возможных чисел длины n
// в заданной цифровой клавиатуре

static int getCount(char keypad[][], int n)

{

    if(keypad == null || n <= 0)

        return 0;

    if(n == 1)

        return 10;

  

    // влево, вверх, вправо, вниз от текущего местоположения

    int row[] = {0, 0, -1, 0, 1};

    int col[] = {0, -1, 0, 1, 0};

  

    // берём n + 1 для простоты - count [i] [j] сохранит

    // число, начинающееся с цифры i и длины j

    int [][]count = new int[10][n + 1];

    int i = 0, j = 0, k = 0, move = 0, 

             ro = 0, co = 0, num = 0;

    int nextNum = 0, totalCount = 0;

  

    // считать числа, начинающиеся с цифры i

    // и длины 0 и 1

    for (i = 0; i <= 9; i++)

    {

        count[i][0] = 0;

        count[i][1] = 1;

    }

  

    // снизу вверх - получаем счетчик чисел длины 2, 3, 4, ..., n

    for (k = 2; k <= n; k++)

    {

        for (i = 0; i < 4; i++) // Цикл в строке клавиатуры

        {

            for (j = 0; j < 3; j++) // Цикл на колонке клавиатуры

            {

                // Обработка от 0 до 9 цифр

                if (keypad[i][j] != '*' && 

                    keypad[i][j] != '#')

                {

                    // Здесь мы считаем числа, начинающиеся с

                    // цифровая клавиатура [i] [j] и длина клавиатуры k [i] [j]

                    // станет первой цифрой, и нам нужно искать

                    // (k-1) больше цифр

                    num = keypad[i][j] - '0';

                    count[num][k] = 0;

  

                    // двигаться влево, вверх, вправо, вниз от текущего местоположения

                    // и если новое местоположение действительно, тогда получить номер

                    // отсчет длины (k-1) от этой новой цифры и

                    // добавить количество, которое мы нашли до сих пор

                    for (move = 0; move < 5; move++)

                    {

                        ro = i + row[move];

                        co = j + col[move];

                        if (ro >= 0 && ro <= 3 && co >= 0 && 

                            co <= 2 && keypad[ro][co] != '*' && 

                                       keypad[ro][co] != '#')

                        {

                            nextNum = keypad[ro][co] - '0';

                            count[num][k] += count[nextNum][k - 1];

                        }

                    }

                }

            }

        }

    }

  

    // Получить количество всех возможных чисел длины "n"

    // начиная с цифры 0, 1, 2, ..., 9

    totalCount = 0;

    for (i = 0; i <= 9; i++)

        totalCount += count[i][n];

    return totalCount;

}

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

public static void main(String[] args)

{

    char keypad[][] = {{'1','2','3'},

                       {'4','5','6'},

                       {'7','8','9'},

                       {'*','0','#'}};

    System.out.printf("Count for numbers of length %d: %d\n", 1, 

                                           getCount(keypad, 1));

    System.out.printf("Count for numbers of length %d: %d\n", 2,

                                           getCount(keypad, 2));

    System.out.printf("Count for numbers of length %d: %d\n", 3, 

                                           getCount(keypad, 3));

    System.out.printf("Count for numbers of length %d: %d\n", 4, 

                                           getCount(keypad, 4));

    System.out.printf("Count for numbers of length %d: %d\n", 5,

                                           getCount(keypad, 5));

}
}

  
// Этот код предоставлен Rajput-Ji

C #

// Программа C # на основе динамического программирования для
// подсчитать количество возможных чисел заданной длины

using System;

  

class GFG

{

      
// Возвращаем количество всех возможных чисел длины n
// в заданной цифровой клавиатуре

static int getCount(char [,]keypad, int n)

{

    if(keypad == null || n <= 0)

        return 0;

    if(n == 1)

        return 10;

  

    // влево, вверх, вправо, вниз

    // из текущего местоположения

    int []row = {0, 0, -1, 0, 1};

    int []col = {0, -1, 0, 1, 0};

  

    // берём n + 1 для простоты - считай [i, j]

    // будем хранить число, начиная с

    // цифра i и. длина j

    int [,]count = new int[10,n + 1];

    int i = 0, j = 0, k = 0, move = 0, 

              ro = 0, co = 0, num = 0;

    int nextNum = 0, totalCount = 0;

  

    // считать числа, начинающиеся с цифры i

    // и of.Lengths 0 и 1

    for (i = 0; i <= 9; i++)

    {

        count[i, 0] = 0;

        count[i, 1] = 1;

    }

  

    // снизу вверх - получить число

    // Длина 2, 3, 4, ..., n

    for (k = 2; k <= n; k++)

    {

        for (i = 0; i < 4; i++) // Цикл в строке клавиатуры

        {

            for (j = 0; j < 3; j++) // Цикл на колонке клавиатуры

            {

                // Обработка от 0 до 9 цифр

                if (keypad[i, j] != '*' && 

                    keypad[i, j] != '#')

                {

                    // Здесь мы считаем числа, начинающиеся с

                    // цифровая клавиатура [i, j] и of.Longth k клавиатура [i, j]

                    // станет первой цифрой, и нам нужно искать

                    // (k-1) больше цифр

                    num = keypad[i, j] - '0';

                    count[num, k] = 0;

  

                    // двигаться влево, вверх, вправо, вниз от текущего местоположения

                    // и если новое местоположение действительно, тогда получить номер

                    // отсчет. Длина (k-1) от этой новой цифры и

                    //.Добавить в счет мы нашли до сих пор

                    for (move = 0; move < 5; move++)

                    {

                        ro = i + row[move];

                        co = j + col[move];

                        if (ro >= 0 && ro <= 3 && co >= 0 && 

                            co <= 2 && keypad[ro, co] != '*' && 

                                       keypad[ro, co] != '#')

                        {

                            nextNum = keypad[ro, co] - '0';

                            count[num, k] += count[nextNum, k - 1];

                        }

                    }

                }

            }

        }

    }

  

    // Получить количество всех возможных чисел. Длина "n"

    // начиная с цифры 0, 1, 2, ..., 9

    totalCount = 0;

    for (i = 0; i <= 9; i++)

        totalCount += count[i, n];

    return totalCount;

}

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

public static void Main(String[] args)

{

    char [,]keypad = {{'1', '2', '3'},

                      {'4', '5', '6'},

                      {'7', '8', '9'},

                      {'*', '0', '#'}};

    Console.Write("Count for numbers of.Length {0}: {1}\n", 1, 

                                        getCount(keypad, 1));

    Console.Write("Count for numbers of.Length {0}: {1}\n", 2,

                                        getCount(keypad, 2));

    Console.Write("Count for numbers of.Length {0}: {1}\n", 3, 

                                        getCount(keypad, 3));

    Console.Write("Count for numbers of.Length {0}: {1}\n", 4, 

                                        getCount(keypad, 4));

    Console.Write("Count for numbers of.Length {0}: {1}\n", 5,

                                        getCount(keypad, 5));

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

Count for numbers of length 1: 10
Count for numbers of length 2: 36
Count for numbers of length 3: 138
Count for numbers of length 4: 532
Count for numbers of length 5: 2062

Оптимизированное для космоса решение:
Вышеупомянутый подход динамического программирования также выполняется за время O (n) и требует O (n) вспомогательного пространства, поскольку только один для циклов выполняется n раз, другой для циклов выполняется в течение постоянного времени. Мы можем видеть, что для n-й итерации нужны данные только из (n-1) -й итерации, поэтому нам не нужно хранить данные из более старых итераций. У нас может быть подход динамического программирования с эффективным использованием пространства только с двумя массивами размером 10. Спасибо Nik за предложение этого решения.

C ++

// Программа Space C Optimized для подсчета количества возможных чисел
// заданной длины
#include <stdio.h>

  
// Возвращаем количество всех возможных чисел длины n
// в заданной цифровой клавиатуре

int getCount(char keypad[][3], int n)

{

    if(keypad == NULL || n <= 0)

        return 0;

    if(n == 1)

        return 10;

  

    // нечетные [i], четные [i] массивы представляют количество начальных чисел

    // с цифрой i для любой длины j

    int odd[10], even[10];

    int i = 0, j = 0, useOdd = 0, totalCount = 0;

  

    for (i=0; i<=9; i++)

        odd[i] = 1;  // для j = 1

  

    for (j=2; j<=n; j++) // Расчет снизу вверх от j = 2 до n

    {

        useOdd = 1 - useOdd;

  

        // Здесь мы явно пишем строки для каждого числа 0

        // до 9. Но это всегда можно записать как DFS на сетке 4X3

        // используя строки, массивы столбцов, допустимые перемещения

        if(useOdd == 1)

        {

            even[0] = odd[0] + odd[8];

            even[1] = odd[1] + odd[2] + odd[4];

            even[2] = odd[2] + odd[1] + odd[3] + odd[5];

            even[3] = odd[3] + odd[2] + odd[6];

            even[4] = odd[4] + odd[1] + odd[5] + odd[7];

            even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6];

            even[6] = odd[6] + odd[3] + odd[5] + odd[9];

            even[7] = odd[7] + odd[4] + odd[8];

            even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9];

            even[9] = odd[9] + odd[6] + odd[8];

        }

        else

        {

            odd[0] = even[0] + even[8];

            odd[1] = even[1] + even[2] + even[4];

            odd[2] = even[2] + even[1] + even[3] + even[5];

            odd[3] = even[3] + even[2] + even[6];

            odd[4] = even[4] + even[1] + even[5] + even[7];

            odd[5] = even[5] + even[2] + even[4] + even[8] + even[6];

            odd[6] = even[6] + even[3] + even[5] + even[9];

            odd[7] = even[7] + even[4] + even[8];

            odd[8] = even[8] + even[0] + even[5] + even[7] + even[9];

            odd[9] = even[9] + even[6] + even[8];

        }

    }

  

    // Получить отсчет всех возможных чисел длины "n" начиная

    // с цифрой 0, 1, 2, ..., 9

    totalCount = 0;

    if(useOdd == 1)

    {

        for (i=0; i<=9; i++)

            totalCount += even[i];

    }

    else

    {

        for (i=0; i<=9; i++)

            totalCount += odd[i];

    }

    return totalCount;

}

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

int main()

{

    char keypad[4][3] = {{'1','2','3'},

        {'4','5','6'},

        {'7','8','9'},

        {'*','0','#'}

    };

    printf("Count for numbers of length %d: %dn", 1, getCount(keypad, 1));

    printf("Count for numbers of length %d: %dn", 2, getCount(keypad, 2));

    printf("Count for numbers of length %d: %dn", 3, getCount(keypad, 3));

    printf("Count for numbers of length %d: %dn", 4, getCount(keypad, 4));

    printf("Count for numbers of length %d: %dn", 5, getCount(keypad, 5));

  

    return 0;

}

Джава

// Пространственно оптимизированная Java-программа для
// подсчитать количество возможных чисел
// заданной длины

class GFG 

{

  
// Возвращаем количество всех возможных чисел
// длина n в заданной числовой клавиатуре

static int getCount(char keypad[][], int n)

{

    if(keypad == null || n <= 0)

        return 0;

    if(n == 1)

        return 10;

  

    // нечетные [i], четные [i] массивы представляют количество

    // числа, начинающиеся с цифры i для любой длины j

    int []odd = new int[10];

    int []even = new int[10];

    int i = 0, j = 0, useOdd = 0, totalCount = 0;

  

    for (i = 0; i <= 9; i++)

        odd[i] = 1; // для j = 1

      

    // Расчет снизу вверх от j = 2 до n

    for (j = 2; j <= n; j++) 

    {

        useOdd = 1 - useOdd;

  

        // Здесь мы явно пишем строки

        // для каждого числа от 0 до 9. Но это всегда может быть

        // записывается как DFS в сетке 4X3 с использованием строки,

        // массив столбцов допустимые ходы

        if(useOdd == 1)

        {

            even[0] = odd[0] + odd[8];

            even[1] = odd[1] + odd[2] + odd[4];

            even[2] = odd[2] + odd[1] + 

                      odd[3] + odd[5];

            even[3] = odd[3] + odd[2] + odd[6];

            even[4] = odd[4] + odd[1] + 

                      odd[5] + odd[7];

            even[5] = odd[5] + odd[2] + odd[4] + 

                               odd[8] + odd[6];

            even[6] = odd[6] + odd[3] + 

                      odd[5] + odd[9];

            even[7] = odd[7] + odd[4] + odd[8];

            even[8] = odd[8] + odd[0] + odd[5] + 

                               odd[7] + odd[9];

            even[9] = odd[9] + odd[6] + odd[8];

        }

        else

        {

            odd[0] = even[0] + even[8];

            odd[1] = even[1] + even[2] + even[4];

            odd[2] = even[2] + even[1] + 

                     even[3] + even[5];

            odd[3] = even[3] + even[2] + even[6];

            odd[4] = even[4] + even[1] + 

                     even[5] + even[7];

            odd[5] = even[5] + even[2] + even[4] + 

                               even[8] + even[6];

            odd[6] = even[6] + even[3] + 

                     even[5] + even[9];

            odd[7] = even[7] + even[4] + even[8];

            odd[8] = even[8] + even[0] + even[5] + 

                               even[7] + even[9];

            odd[9] = even[9] + even[6] + even[8];

        }

    }

  

    // Получить количество всех возможных чисел

    // длина "n", начинающаяся с цифры 0, 1, 2, ..., 9

    totalCount = 0;

    if(useOdd == 1)

    {

        for (i = 0; i <= 9; i++)

            totalCount += even[i];

    }

    else

    {

        for (i = 0; i <= 9; i++)

            totalCount += odd[i];

    }

    return totalCount;

}

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

public static void main(String[] args) 

{

    char keypad[][] = {{'1','2','3'},

                       {'4','5','6'},

                       {'7','8','9'},

                       {'*','0','#'}};

    System.out.printf("Count for numbers of length %d: %d\n", 1, 

                                           getCount(keypad, 1));

    System.out.printf("Count for numbers of length %d: %d\n", 2, 

                                           getCount(keypad, 2));

    System.out.printf("Count for numbers of length %d: %d\n", 3,

                                           getCount(keypad, 3));

    System.out.printf("Count for numbers of length %d: %d\n", 4,

                                           getCount(keypad, 4));

    System.out.printf("Count for numbers of length %d: %d\n", 5,

                                           getCount(keypad, 5));

}
}

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

Python 3

# Космическая оптимизированная программа Python для подсчета
# количество возможных номеров
# заданной длины

  
# Возвращаем количество всех возможных чисел
№ длины n
# в данной числовой клавиатуре

def getCount(keypad, n):

  

    if(not keypad or n <= 0):

        return 0

    if(n == 1):

        return 10

  

    # odd [i], четные [i] массивы представляют

    # количество начальных чисел

    # с цифрой i для любой длины j

    odd = [0]*10

    even = [0]*10

    i = 0

    j = 0

    useOdd = 0

    totalCount = 0

  

    for i in range(10):

        odd[i] = 1 # для j = 1

  

    for j in range(2,n+1): Расчет снизу вверх от j = 2 до n

      

        useOdd = 1 - useOdd

  

        # Здесь мы явно пишем строки для каждого числа 0

        # до 9. Но это всегда можно записать как DFS на сетке 4X3

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

        if(useOdd == 1):

          

            even[0] = odd[0] + odd[8]

            even[1] = odd[1] + odd[2] + odd[4]

            even[2] = odd[2] + odd[1] + odd[3] + odd[5]

            even[3] = odd[3] + odd[2] + odd[6]

            even[4] = odd[4] + odd[1] + odd[5] + odd[7]

            even[5] = odd[5] + odd[2] + odd[4] + odd[8] + odd[6]

            even[6] = odd[6] + odd[3] + odd[5] + odd[9]

            even[7] = odd[7] + odd[4] + odd[8]

            even[8] = odd[8] + odd[0] + odd[5] + odd[7] + odd[9]

            even[9] = odd[9] + odd[6] + odd[8]

          

        else:

          

            odd[0] = even[0] + even[8]

            odd[1] = even[1] + even[2] + even[4]

            odd[2] = even[2] + even[1] + even[3] + even[5]

            odd[3] = even[3] + even[2] + even[6]

            odd[4] = even[4] + even[1] + even[5] + even[7]

            odd[5] = even[5] + even[2] + even[4] + even[8] + even[6]

            odd[6] = even[6] + even[3] + even[5] + even[9]

            odd[7] = even[7] + even[4] + even[8]

            odd[8] = even[8] + even[0] + even[5] + even[7] + even[9]

            odd[9] = even[9] + even[6] + even[8]

  

    # Получить количество всех возможных чисел длины "n", начиная

    # с цифрой 0, 1, 2, ..., 9

    totalCount = 0

    if(useOdd == 1):

        for i in range(10):

            totalCount += even[i]

      

    else:

        for i in range(10):

            totalCount += odd[i]

  

    return totalCount

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

if __name__ == "__main__":

    keypad = [['1','2','3'],

            ['4','5','6'],

            ['7','8','9'],

            ['*','0','#']]

      

    print("Count for numbers of length ",1,": ", getCount(keypad, 1))

    print("Count for numbers of length ",2,": ", getCount(keypad, 2))

    print("Count for numbers of length ",3,": ", getCount(keypad, 3))

    print("Count for numbers of length ",4,": ", getCount(keypad, 4))

    print("Count for numbers of length ",5,": ", getCount(keypad, 5))

      
# Этот код предоставлен
# ChitraNayal

C #

// Программа C # для оптимизации пространства
// подсчитать количество возможных чисел
// заданной длины

using System;

      

class GFG 

{

  
// Возвращаем количество всех возможных чисел
// длина n в заданной числовой клавиатуре

static int getCount(char [,]keypad, int n)

{

    if(keypad == null || n <= 0)

        return 0;

    if(n == 1)

        return 10;

  

    // нечетные [i], четные [i] массивы представляют количество

    // числа, начинающиеся с цифры i для любой длины j

    int []odd = new int[10];

    int []even = new int[10];

    int i = 0, j = 0, useOdd = 0, totalCount = 0;

  

    for (i = 0; i <= 9; i++)

        odd[i] = 1; // для j = 1

      

    // Расчет снизу вверх от j = 2 до n

    for (j = 2; j <= n; j++) 

    {

        useOdd = 1 - useOdd;

  

        // Здесь мы явно пишем строки

        // для каждого числа от 0 до 9. Но это всегда может быть

        // записывается как DFS в сетке 4X3 с использованием строки,

        // массив столбцов допустимые ходы

        if(useOdd == 1)

        {

            even[0] = odd[0] + odd[8];

            even[1] = odd[1] + odd[2] + odd[4];

            even[2] = odd[2] + odd[1] + 

                      odd[3] + odd[5];

            even[3] = odd[3] + odd[2] + odd[6];

            even[4] = odd[4] + odd[1] + 

                      odd[5] + odd[7];

            even[5] = odd[5] + odd[2] + odd[4] + 

                               odd[8] + odd[6];

            even[6] = odd[6] + odd[3] + 

                      odd[5] + odd[9];

            even[7] = odd[7] + odd[4] + odd[8];

            even[8] = odd[8] + odd[0] + odd[5] + 

                               odd[7] + odd[9];

            even[9] = odd[9] + odd[6] + odd[8];

        }

        else

        {

            odd[0] = even[0] + even[8];

            odd[1] = even[1] + even[2] + even[4];

            odd[2] = even[2] + even[1] + 

                     even[3] + even[5];

            odd[3] = even[3] + even[2] + even[6];

            odd[4] = even[4] + even[1] + 

                     even[5] + even[7];

            odd[5] = even[5] + even[2] + even[4] + 

                               even[8] + even[6];

            odd[6] = even[6] + even[3] + 

                     even[5] + even[9];

            odd[7] = even[7] + even[4] + even[8];

            odd[8] = even[8] + even[0] + even[5] + 

                               even[7] + even[9];

            odd[9] = even[9] + even[6] + even[8];

        }

    }

  

    // Получить количество всех возможных чисел

    // длина "n", начинающаяся с цифры 0, 1, 2, ..., 9

    totalCount = 0;

    if(useOdd == 1)

    {

        for (i = 0; i <= 9; i++)

            totalCount += even[i];

    }

    else

    {

        for (i = 0; i <= 9; i++)

            totalCount += odd[i];

    }

    return totalCount;

}

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

public static void Main(String[] args) 

{

    char [,]keypad = {{'1','2','3'},

                      {'4','5','6'},

                      {'7','8','9'},

                      {'*','0','#'}};

    Console.Write("Count for numbers of length {0}: {1}\n", 1, 

                                        getCount(keypad, 1));

    Console.Write("Count for numbers of length {0}: {1}\n", 2, 

                                        getCount(keypad, 2));

    Console.Write("Count for numbers of length {0}: {1}\n", 3,

                                        getCount(keypad, 3));

    Console.Write("Count for numbers of length {0}: {1}\n", 4,

                                        getCount(keypad, 4));

    Console.Write("Count for numbers of length {0}: {1}\n", 5,

                                        getCount(keypad, 5));

}
}

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


Выход:

Count for numbers of length 1: 10
Count for numbers of length 2: 36
Count for numbers of length 3: 138
Count for numbers of length 4: 532
Count for numbers of length 5: 2062

Эта статья предоставлена Анураг Сингх . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Проблема с цифровой клавиатурой

0.00 (0%) 0 votes