Рубрики

Учитывая число, найдите следующий наименьший палиндром

По заданному числу найдите следующий наименьший палиндром, который больше этого числа. Например, если входное число равно «2 3 5 4 5», выходное значение должно быть «2 3 6 3 2». И если номер входа «9 9 9», выход должен быть «1 0 0 1».

Предполагается, что входные данные являются массивом. Каждая запись в массиве представляет собой цифру во входном номере. Пусть массив будет 'num []', а размер массива будет 'n'

Может быть три различных типа входов, которые должны обрабатываться отдельно.
1) Номер ввода — палиндром и имеет все 9. Например «9 9 9». Выход должен быть «1 0 0 1»
2) Вводимый номер не является палиндромом. Например, «1 2 3 4». Выход должен быть «1 3 3 1»
3) Номер ввода — палиндром и не имеет всех 9. Например, «1 2 2 1». Выход должен быть «1 3 3 1».

Решение для ввода типа 1 легко. Вывод содержит n + 1 цифр, где угловые цифры равны 1, а все цифры между угловыми цифрами равны 0.

Теперь давайте сначала поговорим о типах ввода 2 и 3. Как преобразовать данное число в больший палиндром? Чтобы понять решение, давайте сначала определим следующие два термина:
Левая сторона: левая половина заданного числа. Левая сторона «1 2 3 4 5 6» — «1 2 3», а левая сторона «1 2 3 4 5» — «1 2»
Правая сторона: правая половина данного числа. Правая сторона «1 2 3 4 5 6» — «4 5 6», а правая сторона «1 2 3 4 5» — «4 5»
Чтобы преобразовать в палиндром, мы можем либо взять зеркало его левой стороны, либо взять зеркало его правой стороны. Однако, если мы возьмем зеркало с правой стороны, то сформированный таким образом палиндром не обязательно будет следующим большим палиндромом. Итак, мы должны взять зеркало левой стороны и скопировать его на правую сторону. Но есть некоторые случаи, которые должны рассматриваться по-разному. Смотрите следующие шаги.

Начнем с двух индексов i и j. я указываю на два средних элемента (или на два элемента вокруг среднего элемента, если n нечетно). Мы один за другим отдаляем друг от друга i и j.

Шаг 1. Сначала игнорируйте часть левой стороны, которая совпадает с соответствующей частью правой стороны. Например, если число равно «8 3 4 2 2 4 6 9», мы игнорируем четыре средних элемента. Теперь я указываю на элемент 3, а j — на элемент 6.

Шаг 2. После шага 1 возникают следующие случаи:

Случай 1: индексы i & j пересекают границу.
Этот случай возникает, когда вводится число палиндром. В этом случае мы просто добавляем 1 к средней цифре (или цифры в случае, если n четное), распространяем перенос в направлении цифры MSB левой стороны и одновременно копируем зеркало левой стороны в правую сторону.
Например, если задано число «1 2 9 2 1», мы увеличиваем 9 до 10 и распространяем перенос. Таким образом, число становится «1 3 0 3 1»

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

2.1) Достаточно скопировать левую сторону в правую, нам не нужно увеличивать какие-либо цифры, и в результате мы получим только зеркало левой стороны. Ниже приведены некоторые примеры этого варианта.
Следующий палиндром для «7 8 3 3 2 2 ″ -« 7 8 3 3 8 7 »
Следующий палиндром для «1 2 5 3 2 2» — «1 2 5 5 2 1»
Следующий палиндром для «1 4 5 8 7 6 7 8 3 2 2» равен «1 4 5 8 7 6 7 8 5 4 1»
Как мы проверяем этот случай? Все, что нам нужно проверить — это цифра сразу после пропущенной части в шаге 1. Эта цифра выделена в приведенных выше примерах. Если эта цифра больше, чем соответствующая цифра в правой части, то достаточно скопировать левую сторону в правую, и нам больше ничего не нужно делать.

2.2) Копирование с левой стороны на правую сторону НЕ является достаточным. Это происходит, когда указанная выше цифра на левой стороне меньше. Ниже приведены некоторые примеры этого случая.
Следующий палиндром для «7 1 3 3 2 2 ″ -« 7 1 4 4 1 7 »
Следующий палиндром для «1 2 3 4 6 2 8» — «1 2 3 5 3 2 1»
Следующий палиндром для «9 4 1 8 7 9 7 8 3 2 2» равен «9 4 1 8 8 0 8 8 1 4 9»
Мы обрабатываем этот подслучайный случай, как в случае 1. Мы просто добавляем 1 к средней цифре (или цифры в случае, если n четное), распространяем перенос в направлении цифры MSB левой стороны и одновременно копируем зеркало левой стороны в правую сторону.

C ++

#include <stdio.h>

  
// Вспомогательная функция для печати массива

void printArray (int arr[], int n);

  
// Вспомогательная функция, чтобы проверить, есть ли у num все 9

int AreAll9s (int num[], int n );

  
// Возвращает следующий палиндром заданного числа num [].
// Эта функция предназначена для типов ввода 2 и 3

void generateNextPalindromeUtil (int num[], int n )

{

    // найти индекс средней цифры

    int mid = n/2;

  

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

    bool leftsmaller = false;

  

    // конец левой стороны всегда 'середина -1'

    int i = mid - 1;

  

    // Начало правой части зависит, является ли n нечетным или четным

    int j = (n % 2)? mid + 1 : mid;

  

   // Изначально игнорируем средние одинаковые цифры

    while (i >= 0 && num[i] == num[j])

        i--,j++;

  

    // Находим, нужно ли увеличивать среднюю цифру (ы) или нет (или копирование влево)

    // сторона не достаточна)

    if ( i < 0 || num[i] < num[j])

        leftsmaller = true;

  

    // Копируем зеркало слева в туго

    while (i >= 0)

    {

        num[j] = num[i];

        j++;

        i--;

    }

  

    // Обработка случая, когда средняя цифра (ы) должна быть увеличена.

    // Эта часть кода предназначена для случаев 1 и 2.2

    if (leftsmaller == true)

    {

        int carry = 1;

        i = mid - 1;

  

        // Если есть нечетные цифры, то приращение

        // средняя цифра и сохранение переноса

        if (n%2 == 1)

        {

            num[mid] += carry;

            carry = num[mid] / 10;

            num[mid] %= 10;

            j = mid + 1;

        }

        else

            j = mid;

  

        // Добавляем 1 к крайней правой цифре левой стороны, распространяем перенос

        // по направлению к цифре MSB и одновременному копированию зеркала левой стороны

        // с правой стороны.

        while (i >= 0)

        {

            num[i] += carry;

            carry = num[i] / 10;

            num[i] %= 10;

            num[j++] = num[i--]; // копировать зеркало вправо

        }

    }

}

  
// Функция, которая печатает следующий палиндром с заданным числом num []
// с n цифрами.

void generateNextPalindrome( int num[], int n )

{

    int i;

  

    printf("Next palindrome is:");

  

    // Тип ввода 1: все цифры 9, просто o / p 1

    // с последующими n-1 0 и 1.

    if( AreAll9s( num, n ) )

    {

        printf( "1 ");

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

            printf( "0 " );

        printf( "1" );

    }

  

    // Типы ввода 2 и 3

    else

    {

        generateNextPalindromeUtil ( num, n );

  

        // распечатать результат

        printArray (num, n);

    }

}

  
// Вспомогательная функция, чтобы проверить, есть ли у num все 9

int AreAll9s( int* num, int n )

{

    int i;

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

        if( num[i] != 9 )

            return 0;

    return 1;

}

  
/ * Утилита, которая печатает массив в строке * /

void printArray(int arr[], int n)

{

    int i;

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

        printf("%d ", arr[i]);

    printf("\n");

}

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

int main()

{

    int num[] = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2};

  

    int n = sizeof (num)/ sizeof(num[0]);

  

    generateNextPalindrome( num, n );

  

    return 0;

}

Джава

// Java-программа для поиска следующей самой маленькой
// палиндром

  

public class nextplaindrome 

{

    // Возвращает следующий палиндром данного

    // номер num []. Эта функция предназначена для

    // вводим 2 и 3

    static void generateNextPalindromeUtil(int num[], int n) 

    {

        int mid = n / 2;

  

        // конец левой стороны всегда 'середина -1'

        int i = mid - 1;

          

        // Начало правой части зависит

        // если n нечетно или четно

        int j = (n % 2 == 0) ? mid : mid + 1;

          

        // переменная bool для проверки наличия левой копии

        // сторона справа

        // достаточно или нет

        boolean leftsmaller = false;

  

        // Изначально игнорируем средние одинаковые цифры

        while (i >= 0 && num[i] == num[j]) 

        {

            i--;

            j++;

        }

          

        // Находим, нужна ли средняя цифра

        // увеличивается или нет (или копирование влево

        // сторона не достаточна)

        if (i < 0 || num[i] < num[j]) 

        {

            leftsmaller = true;

        }

          

        // Копируем зеркало слева в туго

        while (i >= 0

        {

            num[j++] = num[i--];

        }

          

        // Обрабатываем случай, когда средняя цифра (ы)

        // должен быть увеличен Эта часть кода

        // для случая 1 и случая 2.2

        if (leftsmaller) 

        {

            int carry = 1;

          

            // Если есть нечетные цифры, то приращение

            // средняя цифра и сохранение переноса

            if (n % 2 == 1) {

                num[mid] += 1;

                carry = num[mid] / 10;

                num[mid] %= 10;

            }

            i = mid - 1;

            j = (n % 2 == 0 ? mid : mid + 1);

              

            // Добавить 1 к крайней правой цифре слева

            // сторона, распространение переноса на цифру MSB

            // и одновременно копируем зеркало

            // слева направо

            while (i >= 0

            {

                num[i] = num[i] + carry;

                carry = num[i] / 10;

                num[i] %= 10;

                num[j] = num[i];// копировать зеркало вправо

                i--;

                j++;

            }

  

        }

    }

  

    // Функция, которая печатает следующий палиндром

    // данного числа num [] с n цифрами.

    static void generateNextPalindrome(int num[], int n) 

    {

        System.out.println("Next Palindrome is:");

          

        // Тип ввода 1: все цифры 9,

        // просто o / p 1, за которым следуют n-1 0

        // с последующим 1.

        if (isAll9(num, n)) {

            System.out.print("1");

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

                System.out.print("0");

            System.out.println("1");

  

        }

      

        // Типы ввода 2 и 3

        else {

            generateNextPalindromeUtil(num, n);

            printarray(num);

        }

    }

  

    // Вспомогательная функция, чтобы проверить, есть ли у num все 9

    static boolean isAll9(int num[], int n) {

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

            if (num[i] != 9)

                return false;

        return true;

    }

  

    / * Утилита, которая печатает массив в строке * /

    static void printarray(int num[]) {

        for (int i = 0; i < num.length; i++)

            System.out.print(num[i]);

        System.out.println();

    }

  

    public static void main(String[] args) 

    {

        int num[] = { 9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2 };

        generateNextPalindrome(num, num.length);

    }

}

python3

# Возвращает следующий палиндром заданного числа num [].
# Эта функция предназначена для типов ввода 2 и 3

def generateNextPalindromeUtil (num, n) :

  

    # найти индекс средней цифры

    mid = int(n/2 )

  

    # Переменная bool для проверки наличия левой копии

    # сторона справа достаточно или нет

    leftsmaller = False

  

    # конец левой стороны всегда 'середина -1'

    i = mid - 1

  

    # Начало правой стороны зависит

    # если n нечетно или четно

    j = mid + 1 if (n % 2) else mid 

  

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

    while (i >= 0 and num[i] == num[j]) :

        i-=1

        j+=1

  

    # Найдите, должны ли быть средние цифры

    # увеличивается или нет (или копирование влево

    # стороны не достаточно)

    if ( i < 0 or num[i] < num[j]): 

        leftsmaller = True

  

    # Скопировать зеркало слева, чтобы плотно

    while (i >= 0) :

      

        num[j] = num[i] 

        j+=1

        i-=1

      

  

    # Обработать случай, когда средний

    Цифра # должна быть увеличена.

    # Эта часть кода предназначена для случаев 1 и 2.2.

    if (leftsmaller == True) :

      

        carry = 1

        i = mid - 1

  

        # Если есть нечетные цифры, то приращение

        # средняя цифра и сохранить керри

        if (n%2 == 1) :

          

            num[mid] += carry 

            carry = int(num[mid] / 10 )

            num[mid] %= 10

            j = mid + 1

          

        else:

            j = mid 

  

        # Добавьте 1 к крайней правой цифре

        # левая сторона, распространяйте перенос

        # к цифре MSB и одновременно

        # копирующее зеркало левой стороны

        # с правой стороны.

        while (i >= 0) :

          

            num[i] += carry 

            carry = num[i] / 10

            num[i] %= 10

            num[j] = num[i] # скопировать зеркало вправо

            j+=1

            i-=1

          
# Функция, которая печатает затем
# палиндром данного числа num []
# с n цифрами.

def generateNextPalindrome(num, n ) :

  

    print("\nNext palindrome is:"

  

    # Тип ввода 1: все цифры 9, просто o / p 1

    # с последующими n-1 0 и 1.

    if( AreAll9s( num, n ) == True) :

      

        print( "1"

        for i in range(1, n): 

            print( "0"

        print( "1"

      

  

    # Типы ввода 2 и 3

    else:

      

        generateNextPalindromeUtil ( num, n ) 

  

        # распечатать результат

        printArray (num, n) 

      
# Полезная функция, чтобы проверить, есть ли у num все 9

def AreAll9s(num, n ): 

    for i in range(1, n):

        if( num[i] != 9 ) :

            return 0

    return 1

  

  
# Утилита, которая печатает массив в строке

def printArray(arr, n): 

  

    for i in range(0, n): 

        print(int(arr[i]),end=" "

    print() 

  

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

if __name__ == "__main__":

    num = [9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2]

    n = len(num)

    generateNextPalindrome( num, n ) 

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для поиска следующего наименьшего палиндрома

using System;

public class GFG {

      

    // Возвращает следующий палиндром данного

    // номер num []. Эта функция предназначена для

    // вводим 2 и 3

    static void generateNextPalindromeUtil(int []num, int n) 

    {

        int mid = n / 2;

  

        // конец левой стороны всегда 'середина -1'

        int i = mid - 1;

          

        // Начало правой части зависит

        // если n нечетно или четно

        int j = (n % 2 == 0) ? mid : mid + 1;

          

        // переменная bool для проверки наличия левой копии

        // сторона справа

        // достаточно или нет

        bool leftsmaller = false;

  

        // Изначально игнорируем средние одинаковые цифры

        while (i >= 0 && num[i] == num[j]) 

        {

            i--;

            j++;

        }

          

        // Находим, нужна ли средняя цифра

        // увеличивается или нет (или копирование влево

        // сторона не достаточна)

        if (i < 0 || num[i] < num[j]) 

        {

            leftsmaller = true;

        }

          

        // Копируем зеркало слева в туго

        while (i >= 0) 

        {

            num[j++] = num[i--];

        }

          

        // Обрабатываем случай, когда средняя цифра (ы)

        // должен быть увеличен Эта часть кода

        // для случая 1 и случая 2.2

        if (leftsmaller) 

        {

            int carry = 1;

          

            // Если есть нечетные цифры, то приращение

            // средняя цифра и сохранение переноса

            if (n % 2 == 1) {

                num[mid] += 1;

                carry = num[mid] / 10;

                num[mid] %= 10;

            }

            i = mid - 1;

            j = (n % 2 == 0 ? mid : mid + 1);

              

            // Добавить 1 к крайней правой цифре слева

            // сторона, распространение переноса на цифру MSB

            // и одновременно копируем зеркало

            // слева направо

            while (i >= 0) 

            {

                num[i] = num[i] + carry;

                carry = num[i] / 10;

                num[i] %= 10;

                num[j] = num[i];// копировать зеркало вправо

                i--;

                j++;

            }

  

        }

    }

  

    // Функция, которая печатает следующий палиндром

    // данного числа num [] с n цифрами.

    static void generateNextPalindrome(int []num, int n) 

    {

        Console.WriteLine("Next Palindrome is:");

          

        // Тип ввода 1: все цифры 9,

        // просто o / p 1, за которым следуют n-1 0

        // с последующим 1.

        if (isAll9(num, n)) {

            Console.Write("1");

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

                Console.Write("0");

            Console.Write("1");

  

        }

      

        // Типы ввода 2 и 3

        else {

            generateNextPalindromeUtil(num, n);

            printarray(num);

        }

    }

  

    // Вспомогательная функция, чтобы проверить, есть ли у num все 9

    static bool isAll9(int[] num, int n) {

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

            if (num[i] != 9)

                return false;

        return true;

    }

  

    / * Утилита, которая печатает массив в строке * /

    static void printarray(int []num) {

        for (int i = 0; i < num.Length; i++)

            Console.Write(num[i]+ " ");

        Console.Write(" ");

    }

  

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

    public static void Main() 

    {

        int []num = { 9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2 };

        generateNextPalindrome(num, num.Length);

    }

}

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

PHP

<?php
// PHP программа для поиска следующего
// маленький палиндром

  
// Возвращает следующий палиндром
// данного числа num [].
// Эта функция для
// вводим 2 и 3

function generateNextPalindromeUtil($num, $n

{

    $mid = (int)($n / 2);

  

    // конец левой стороны

    // всегда 'середина -1'

    $i = $mid - 1;

      

    // Начало права

    // сторона зависит, если n

    // нечетное или четное

    $j = ($n % 2 == 0) ? 

                  $mid : ($mid + 1);

      

    // переменная bool для проверки

    // если копия левой стороны

    // право достаточно или нет

    $leftsmaller = false;

  

    // Первоначально игнорируем

    // средние одинаковые цифры

    while ($i >= 0 && 

           $num[$i] == $num[$j]) 

    {

        $i--;

        $j++;

    }

      

    // Найти среднюю цифру (ы)

    // нужно увеличить или

    // нет (или копируем левую сторону

    // не достаточно)

    if ($i < 0 || $num[$i] < $num[$j]) 

    {

        $leftsmaller = true;

    }

      

    // Копируем зеркало

    // слева направо

    while ($i >= 0) 

    {

        $num[$j++] = $num[$i--];

    }

      

    // Обрабатываем случай, когда

    // средняя цифра (и) должна быть

    // увеличивается. Эта часть

    // кода для случая 1

    // и ДЕЛО 2.2

    if ($leftsmaller

    {

        $carry = 1;

      

        // Если есть нечетные цифры,

        // затем увеличиваем середину

        // оцифровка и сохранение переноса

        if ($n % 2 == 1) 

        {

            $num[$mid] += 1;

            $carry = (int)($num[$mid] / 10);

            $num[$mid] %= 10;

        }

        $i = $mid - 1;

        $j = ($n % 2 == 0 ? 

                     $mid : $mid + 1);

          

        // Добавить 1 к самой правой цифре

        // с левой стороны, размножение

        // перенос на цифру MSB

        // и одновременно копировать

        // зеркало левой стороны

        // правая сторона.

        while ($i >= 0) 

        {

            $num[$i] = $num[$i] + $carry;

            $carry = (int)($num[$i] / 10);

            $num[$i] %= 10;

              

            // копировать зеркало вправо

            $num[$j] = $num[$i]; 

            $i--;

            $j++;

        }

  

    }

return $num;

}

  
// Функция, которая печатает
// следующий палиндром данного
// номер num [] с n цифрами.

function generateNextPalindrome($num, $n

{

    echo "Next Palindrome is:\n";

      

    // Тип ввода 1: Все

    // цифры 9, просто

    // o / p 1, за которым следует n-1

    // 0 с последующим 1.

    if (isAll9($num, $n))

    {

        echo "1";

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

            echo "0";

        echo "1";

  

    }

  

    // Типы ввода 2 и 3

    else 

    {

        $num = generateNextPalindromeUtil($num, $n);

            printarray($num);

    }

}

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

function isAll9($num, $n

{

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

        if ($num[$i] != 9)

            return false;

    return true;

}

  
/ * Утилита, которая печатает
массив в строке * /

function printarray($num

{

    for ($i = 0; 

         $i < count($num); $i++)

        echo $num[$i];

    echo "\n";

}

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

$num = array(9, 4, 1, 8, 7, 

             9, 7, 8, 3, 2, 2);

generateNextPalindrome($num

               count($num));

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


Выход:

Next palindrome is:
9 4 1 8 8 0 8 8 1 4 9

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

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

Учитывая число, найдите следующий наименьший палиндром

0.00 (0%) 0 votes