Здесь представлены упражнения по алгоритмам — от простых до сложных, которые подойдут для любого уровня подготовки. Эти задачи помогут отработать навыки решения алгоритмических задач, поддерживать форму в программировании и интересно провести время.
Что было раньше:
В предыдущей части мы решили:
- Sort and Star (Сортировка и звездочка)
- Simple consecutive pairs (Простые последовательные пары)
- Simple Fun #384: Is Turing's Equation? (Простое развлечение)
- Single character palindromes (Односимвольные палиндромы)
- Simple Fun #128: Doubly Not Less (Простое развлечение)
Решение новых задач:
Задача 1
Платформа: CodeWars
Название задачи: Welcome! (Добро пожаловать!)
Ссылка на задачу: https://www.codewars.com/kata/577ff15ad648a14b780000e7
Сложность: 8 kyu
Уже решили (На момент написания статьи): 56 756 из 160 709
Тэги: Основы
Оригинальное описание задачи:
Your start-up's BA has told marketing that your website has a large audience in Scandinavia and surrounding countries. Marketing thinks it would be great to welcome visitors to the site in their own language. Luckily you already use an API that detects the user's location, so this is an easy win.
The Task
- Think of a way to store the languages as a database. The languages are listed below so you can copy and paste!
- Write a 'welcome' function that takes a parameter 'language', with a type `String`, and returns a greeting - if you have it in your database. It should default to English if the language is not in the database, or in the event of an invalid input.
The Database
Please modify this as appropriate for your language.
("english", "Welcome")
("czech", "Vitejte")
("danish", "Velkomst")
("dutch", "Welkom")
("estonian", "Tere tulemast")
("finnish", "Tervetuloa")
("flemish", "Welgekomen")
("french", "Bienvenue")
("german", "Willkommen")
("irish", "Failte")
("italian", "Benvenuto")
("latvian", "Gaidits")
("lithuanian", "Laukiamas")
("polish", "Witamy")
("spanish", "Bienvenido")
("swedish", "Valkommen")
("welsh", "Croeso")
Possible invalid inputs include:
IP_ADDRESS_INVALID - not a valid ipv4 or ipv6 ip address
IP_ADDRESS_NOT_FOUND - ip address not in the database
IP_ADDRESS_REQUIRED - no ip address was supplied
Пояснение задачи:
Задача состоит в следующем:
Необходимо разработать функцию приветствия (`welcome`), принимающую параметр типа строка (`String`) — название языка, и возвращающую соответствующее приветственное сообщение.
Если указанный язык отсутствует в базе данных, функция должна возвращать приветствие на английском языке («Welcome»).
Дополнительно предусмотрено, что в случае некорректного ввода (например, неверное название языка или отсутствие IP-адреса) функция должна корректно обрабатывать такие ситуации и возвращать стандартное английское приветствие.
Пример базы данных:
("english", "Welcome")
("czech", "Vitejte")
("danish", "Velkomst")
(“dutch”, “Welkom”)
(“estonian”, “Tere tulemast”)
(“finnish”, “Tervetuloa”)
(“flemish”, “Welgekomen”)
(“french”, “Bienvenue”)
(“german”, “Willkommen”)
(“irish”, “Failte”)
(“italian”, “Benvenuto”)
(“latvian”, “Gaidits”)
(“lithuanian”, “Laukiamas”)
(“polish”, “Witamy”)
(“spanish”, “Bienvenido”)
(“swedish”, “Valkommen”)
(“welsh”, “Croeso”)
Основные требования:
- Функция должна принимать строку с названием языка и возвращать соответствующее приветствие.
- Если указанного языка нет в базе данных, используется английский язык («Welcome»).
- Для некорректных входных значений (например, отсутствующий IP-адрес или недопустимый язык) функция возвращает «Welcome».
Примеры работы функции:
welcome("finnish") → "Tervetuloa"
welcome("norwegian") → "Welcome"
(так как норвежского языка нет в списке) welcome("IP_ADDRESS_INVALID") → "Welcome" (некорректный IP-адрес)
Таким образом, задача сводится к созданию функции, которая извлекает приветствие из заранее подготовленной базы данных, либо возвращает стандартный английский вариант, если нужного языка нет или ввод некорректен.
Задача 2
Платформа: CodeWars
Название задачи: Eliminate the intruders! Bit manipulation (Уничтожьте злоумышленников! Битовые манипуляции)
Ссылка на задачу: https://www.codewars.com/kata/5a0d38c9697598b67a000041
Сложность: 7 kyu
Уже решили (На момент написания статьи): 5 362 из 18 995
Тэги: Биты, строки, основы
Оригинальное описание задачи:
Task You are given a string representing a number in binary.
Your task is to delete all the unset bits in this string and return the corresponding number (after keeping only the '1's).
Examples
"11010101010101" -> 255 (= 0b11111111)
"111" -> 7
"1000000" -> 1
"000" -> 0
Пояснение задачи:
Задача состоит в следующем:
Дана строка, представляющая двоичное число (например, "11010101010101").
Нужно удалить все символы, обозначающие нули (`'0'`), оставив только единицы (`'1'`).
Затем преобразовать получившуюся строку обратно в десятичное число.
Примеры:
"11010101010101" → 255 (двоичное представление числа 255 — 0b11111111)
"111" → 7 (0b111 = 7)
"1000000" → 1 (0b1 = 1)
"000" → 0 (нет единиц, значит результат будет нулём)
Пояснение:
Основная идея решения заключается в том, чтобы пройтись по строке и собрать только те символы, которые равны единице (`'1'`), игнорируя остальные («нулевые» символы). После этого объединяем оставшиеся символы в новую строку и преобразуем её обратно в целое число.
Пример пошагового выполнения:
Пусть дана строка "11010101010101".
- Удаляем все нули, остаётся "11111111".
- Преобразуем строку в число: 0b11111111 = 255.
Задача 3
Платформа: CodeWars
Название задачи: Two Sum (Две суммы)
Ссылка на задачу: https://www.codewars.com/kata/52c31f8e6605bcc646000082
Сложность: 6 kyu
Уже решили (На момент написания статьи): 95 902 из 295 875
Тэги: Массивы, основы, алгоритмы
Оригинальное описание задачи:
Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value.The indexes of these items should then be returned in a tuple / list (depending on your language) like so: `(index1, index2)`.
For the purposes of this kata, some tests may have multiple answers; any valid solutions will be accepted.
The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; target will always be the sum of two different items from that array).
two_sum([1, 2, 3], 4) == {0, 2}
two_sum([3, 2, 4], 6) == {1, 2}
Пояснение задачи:
Задача состоит в написании функции, принимающей на вход:
- Массив целых чисел (`array`)
- Целое число (`target`) — искомую сумму двух элементов массива Функция должна вернуть пару индексов элементов исходного массива, сумма которых равна заданному числу.
При этом важно учитывать следующие условия:
- Индексы должны быть разными (нельзя использовать один и тот же элемент дважды)
- Возвращаемые индексы могут быть представлены в любом порядке (например, пара (0, 2) эквивалентна паре (2, 0)
- Если в массиве нет подходящих элементов, функция должна вернуть недопустимые значения (например, пустую пару или специальную константу)
Пример:
two_sum([1, 2, 3], 4) → (0, 2) или (2, 0)
two_sum([3, 2, 4], 6) → (1, 2) или (2, 1)
Подход к решению:
Для эффективной работы лучше всего воспользоваться словарём (хэш-таблицей):
1. Создадим словарь, где ключом является значение элемента массива, а значением — его индекс.
2. Проходим по массиву и проверяем, есть ли разность между целевым числом и текущим элементом уже в словаре.
- Если такая разность найдена, возвращаем индексы текущего элемента и найденного ранее.
- Иначе добавляем текущий элемент в словарь.
Такой подход позволяет получить время выполнения O(n), что значительно эффективнее простого перебора пар элементов.
Дополнительное замечание:
Поскольку порядок индексов не важен, достаточно вернуть любую допустимую пару индексов.
Например, в случае нескольких возможных решений, можно вернуть первое попавшееся подходящее сочетание.
Задача 4
Платформа: CodeWars
Название задачи: The Deaf Rats of Hamelin (Глухие крысы Гамельна)
Ссылка на задачу: https://www.codewars.com/kata/598106cb34e205e074000031
Сложность: 6 kyu
Уже решили (На момент написания статьи): 7 138 из 40 373
Тэги: Основы, строки, алгоритмы, очереди, структуры данных
Оригинальное описание задачи:
Story The Pied Piper has been enlisted to play his magical tune and coax all the rats out of town.
But some of the rats are deaf and are going the wrong way!
Kata Task
How many deaf rats are there?
Legend P = The Pied Piper
O~ = Rat going left
~O = Rat going right
Example
ex1 ~O~O~O~O P has 0 deaf rats
ex2 P O~ O~ ~O O~ has 1 deaf rat
ex3 ~O~O~O~OP~O~OO~ has 2 deaf rats
Пояснение задачи:
Задача состоит в подсчёте количества глухих («глухонемых») крыс в городе Хамельн после выступления Pied Piper.
Описание:
На входе дан список символов, представляющих движение крыс и присутствие Pied Piper (`P`).
Крыс обозначают следующим образом:
- `O~`: крыса движется направо -
`~O`: крыса движется налево
Пied Piper способен управлять движением всех крыс, кроме тех, кто уже глухой (не слышит его музыки).
Глухие крысы — это те крысы, которые двигаются в противоположную сторону относительно направления, указанного Pied Piper'ом.
Например, если Pied Piper играет мелодию, заставляющую всех двигаться вправо, глухая крыса будет продолжать двигаться влево.
Подход к решению:
Для нахождения глухих крыс достаточно пройтись по списку символов и проверить направление движения каждой крысы относительно позиции Пied Piper:
- Если крыса слева от Pied Piper и движется влево (`O~`), она не считается глухой, поскольку Pied Piper не влияет на её движение.
- Если крыса справа от Pied Piper и движется вправо (`~O`), она также не считается глухой.
- Глухими считаются крысы, находящиеся справа от Pied Piper и двигающиеся влево (`~O`) или слева от Pied Piper и двигающиеся вправо (`O~`).
Пример
- Вход: `~O~O~O~O P` -
Результат: 0 глухих крыс (все крысы движутся в правильном направлении относительно Pied Piper)
- Вход: `P O~ O~ ~O O~`
- Результат: 1 глухая крыса (`~O`, находится справа от Pied Piper и движется влево)
- Вход: `~O~O~O~OP~O~OO~`
- Результат: 2 глухие крысы (`~O` и `O~`)
Важные моменты:
- Важно учитывать позицию Pied Piper относительно крыс. Все крысы до Pied Piper (слева от него) не считаются глухими, независимо от своего направления движения.
- Крысы, расположенные справа от Pied Piper, считаются глухими только тогда, когда они движутся в противоположном направлении относительно его команды.
Задача 5
Платформа: CodeWars
Название задачи: Factorial decomposition (Факториальное разложение)
Ссылка на задачу: https://www.codewars.com/kata/5a045fee46d843effa000070
Сложность: 5 kyu
Уже решили (На момент написания статьи): 8 118 из 30 324
Тэги: Основы
Оригинальное описание задачи:
The aim of the kata is to decompose `n!` (factorial n) into its prime factors.
Examples:
n = 12; decomp(12) -> "2^10 * 3^5 * 5^2 * 7 * 11"
since 12! is divisible by 2 ten times, by 3 five times, by 5 two times and by 7 and 11 only once.
n = 22; decomp(22) -> "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"
n = 25; decomp(25) -> 2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23
Prime numbers should be in increasing order. When the exponent of a prime is 1 don't put the exponent.
Notes
- the function is `decomp(n)` and should return the decomposition of `n!` into its prime factors in increasing order of the primes, as a string.
- factorial can be a very big number (`4000! has 12674 digits`, n can go from 300 to 4000).
- In Fortran - as in any other language- the returned string is not permitted to contain any redundant trailing whitespace: you can use `dynamically allocated character strings`.
Пояснение задачи:
Задача состоит в разложении факториала числа n (n) на простые множители и представлении результата в виде строки, где каждый простой множитель сопровождается степенью (количеством раз, которое число входит в разложение), причём множители записаны в порядке возрастания.
Пример:
- Для n=12 факториал равен 12=479\,001\,600, который делится на простые числа следующим образом:
12 = 2^{10} * 3^5 * 5^2 * 7 * 11
Результат разложения:
"2^10 * 3^5 * 5^2 * 7 * 11"
- Для n=22 факториал 22 содержит следующие простые множители:
22 = 2^{19} * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19
Результат разложения: "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"
- Для n=25 факториал 25 включает следующие простые множители:
25 = 2^{22} * 3^{10} * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23
Результат разложения:
"2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23"
Требования:
- Простые множители должны быть отсортированы по возрастанию.
- Если степень простого множителя равна единице, она не указывается (например, 3^1 будет просто записано как 3).
- Необходимо учитывать большие значения n (до 4000), где факториалы имеют тысячи цифр.
- Строка результата не должна содержать лишних пробелов
Заключение:
Платформа: CodeWars
Название задачи: Welcome! (Добро пожаловать!)
Ссылка на задачу: https://www.codewars.com/kata/577ff15ad648a14b780000e7
Сложность: 8 kyu
Уже решили (На момент написания статьи): 56 756 из 160 709
Тэги: Основы
Оригинальное описание задачи:
Your start-up's BA has told marketing that your website has a large audience in Scandinavia and surrounding countries. Marketing thinks it would be great to welcome visitors to the site in their own language. Luckily you already use an API that detects the user's location, so this is an easy win.
The Task
- Think of a way to store the languages as a database. The languages are listed below so you can copy and paste!
- Write a 'welcome' function that takes a parameter 'language', with a type `String`, and returns a greeting - if you have it in your database. It should default to English if the language is not in the database, or in the event of an invalid input.
The Database
Please modify this as appropriate for your language.
("english", "Welcome")
("czech", "Vitejte")
("danish", "Velkomst")
("dutch", "Welkom")
("estonian", "Tere tulemast")
("finnish", "Tervetuloa")
("flemish", "Welgekomen")
("french", "Bienvenue")
("german", "Willkommen")
("irish", "Failte")
("italian", "Benvenuto")
("latvian", "Gaidits")
("lithuanian", "Laukiamas")
("polish", "Witamy")
("spanish", "Bienvenido")
("swedish", "Valkommen")
("welsh", "Croeso")
Possible invalid inputs include:
IP_ADDRESS_INVALID - not a valid ipv4 or ipv6 ip address
IP_ADDRESS_NOT_FOUND - ip address not in the database
IP_ADDRESS_REQUIRED - no ip address was supplied
Пояснение задачи:
Задача состоит в следующем:
Необходимо разработать функцию приветствия (`welcome`), принимающую параметр типа строка (`String`) — название языка, и возвращающую соответствующее приветственное сообщение.
Если указанный язык отсутствует в базе данных, функция должна возвращать приветствие на английском языке («Welcome»).
Дополнительно предусмотрено, что в случае некорректного ввода (например, неверное название языка или отсутствие IP-адреса) функция должна корректно обрабатывать такие ситуации и возвращать стандартное английское приветствие.
Пример базы данных:
("english", "Welcome")
("czech", "Vitejte")
("danish", "Velkomst")
(“dutch”, “Welkom”)
(“estonian”, “Tere tulemast”)
(“finnish”, “Tervetuloa”)
(“flemish”, “Welgekomen”)
(“french”, “Bienvenue”)
(“german”, “Willkommen”)
(“irish”, “Failte”)
(“italian”, “Benvenuto”)
(“latvian”, “Gaidits”)
(“lithuanian”, “Laukiamas”)
(“polish”, “Witamy”)
(“spanish”, “Bienvenido”)
(“swedish”, “Valkommen”)
(“welsh”, “Croeso”)
Основные требования:
- Функция должна принимать строку с названием языка и возвращать соответствующее приветствие.
- Если указанного языка нет в базе данных, используется английский язык («Welcome»).
- Для некорректных входных значений (например, отсутствующий IP-адрес или недопустимый язык) функция возвращает «Welcome».
Примеры работы функции:
welcome("finnish") → "Tervetuloa"
welcome("norwegian") → "Welcome"
(так как норвежского языка нет в списке) welcome("IP_ADDRESS_INVALID") → "Welcome" (некорректный IP-адрес)
Таким образом, задача сводится к созданию функции, которая извлекает приветствие из заранее подготовленной базы данных, либо возвращает стандартный английский вариант, если нужного языка нет или ввод некорректен.
Платформа: CodeWars
Название задачи: Eliminate the intruders! Bit manipulation (Уничтожьте злоумышленников! Битовые манипуляции)
Ссылка на задачу: https://www.codewars.com/kata/5a0d38c9697598b67a000041
Сложность: 7 kyu
Уже решили (На момент написания статьи): 5 362 из 18 995
Тэги: Биты, строки, основы
Оригинальное описание задачи:
Task You are given a string representing a number in binary.
Your task is to delete all the unset bits in this string and return the corresponding number (after keeping only the '1's).
Examples
"11010101010101" -> 255 (= 0b11111111)
"111" -> 7
"1000000" -> 1
"000" -> 0
Пояснение задачи:
Задача состоит в следующем:
Дана строка, представляющая двоичное число (например, "11010101010101").
Нужно удалить все символы, обозначающие нули (`'0'`), оставив только единицы (`'1'`).
Затем преобразовать получившуюся строку обратно в десятичное число.
Примеры:
"11010101010101" → 255 (двоичное представление числа 255 — 0b11111111)
"111" → 7 (0b111 = 7)
"1000000" → 1 (0b1 = 1)
"000" → 0 (нет единиц, значит результат будет нулём)
Пояснение:
Основная идея решения заключается в том, чтобы пройтись по строке и собрать только те символы, которые равны единице (`'1'`), игнорируя остальные («нулевые» символы). После этого объединяем оставшиеся символы в новую строку и преобразуем её обратно в целое число.
Пример пошагового выполнения:
Пусть дана строка "11010101010101".
- Удаляем все нули, остаётся "11111111".
- Преобразуем строку в число: 0b11111111 = 255.
Платформа: CodeWars
Название задачи: Two Sum (Две суммы)
Ссылка на задачу: https://www.codewars.com/kata/52c31f8e6605bcc646000082
Сложность: 6 kyu
Уже решили (На момент написания статьи): 95 902 из 295 875
Тэги: Массивы, основы, алгоритмы
Оригинальное описание задачи:
Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value.The indexes of these items should then be returned in a tuple / list (depending on your language) like so: `(index1, index2)`.
For the purposes of this kata, some tests may have multiple answers; any valid solutions will be accepted.
The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; target will always be the sum of two different items from that array).
two_sum([1, 2, 3], 4) == {0, 2}
two_sum([3, 2, 4], 6) == {1, 2}
Пояснение задачи:
Задача состоит в написании функции, принимающей на вход:
- Массив целых чисел (`array`)
- Целое число (`target`) — искомую сумму двух элементов массива Функция должна вернуть пару индексов элементов исходного массива, сумма которых равна заданному числу.
При этом важно учитывать следующие условия:
- Индексы должны быть разными (нельзя использовать один и тот же элемент дважды)
- Возвращаемые индексы могут быть представлены в любом порядке (например, пара (0, 2) эквивалентна паре (2, 0)
- Если в массиве нет подходящих элементов, функция должна вернуть недопустимые значения (например, пустую пару или специальную константу)
Пример:
two_sum([1, 2, 3], 4) → (0, 2) или (2, 0)
two_sum([3, 2, 4], 6) → (1, 2) или (2, 1)
Подход к решению:
Для эффективной работы лучше всего воспользоваться словарём (хэш-таблицей):
1. Создадим словарь, где ключом является значение элемента массива, а значением — его индекс.
2. Проходим по массиву и проверяем, есть ли разность между целевым числом и текущим элементом уже в словаре.
- Если такая разность найдена, возвращаем индексы текущего элемента и найденного ранее.
- Иначе добавляем текущий элемент в словарь.
Такой подход позволяет получить время выполнения O(n), что значительно эффективнее простого перебора пар элементов.
Дополнительное замечание:
Поскольку порядок индексов не важен, достаточно вернуть любую допустимую пару индексов.
Например, в случае нескольких возможных решений, можно вернуть первое попавшееся подходящее сочетание.
Платформа: CodeWars
Название задачи: The Deaf Rats of Hamelin (Глухие крысы Гамельна)
Ссылка на задачу: https://www.codewars.com/kata/598106cb34e205e074000031
Сложность: 6 kyu
Уже решили (На момент написания статьи): 7 138 из 40 373
Тэги: Основы, строки, алгоритмы, очереди, структуры данных
Оригинальное описание задачи:
Story The Pied Piper has been enlisted to play his magical tune and coax all the rats out of town.
But some of the rats are deaf and are going the wrong way!
Kata Task
How many deaf rats are there?
Legend P = The Pied Piper
O~ = Rat going left
~O = Rat going right
Example
ex1 ~O~O~O~O P has 0 deaf rats
ex2 P O~ O~ ~O O~ has 1 deaf rat
ex3 ~O~O~O~OP~O~OO~ has 2 deaf rats
Пояснение задачи:
Задача состоит в подсчёте количества глухих («глухонемых») крыс в городе Хамельн после выступления Pied Piper.
Описание:
На входе дан список символов, представляющих движение крыс и присутствие Pied Piper (`P`).
Крыс обозначают следующим образом:
- `O~`: крыса движется направо -
`~O`: крыса движется налево
Пied Piper способен управлять движением всех крыс, кроме тех, кто уже глухой (не слышит его музыки).
Глухие крысы — это те крысы, которые двигаются в противоположную сторону относительно направления, указанного Pied Piper'ом.
Например, если Pied Piper играет мелодию, заставляющую всех двигаться вправо, глухая крыса будет продолжать двигаться влево.
Подход к решению:
Для нахождения глухих крыс достаточно пройтись по списку символов и проверить направление движения каждой крысы относительно позиции Пied Piper:
- Если крыса слева от Pied Piper и движется влево (`O~`), она не считается глухой, поскольку Pied Piper не влияет на её движение.
- Если крыса справа от Pied Piper и движется вправо (`~O`), она также не считается глухой.
- Глухими считаются крысы, находящиеся справа от Pied Piper и двигающиеся влево (`~O`) или слева от Pied Piper и двигающиеся вправо (`O~`).
Пример
- Вход: `~O~O~O~O P` -
Результат: 0 глухих крыс (все крысы движутся в правильном направлении относительно Pied Piper)
- Вход: `P O~ O~ ~O O~`
- Результат: 1 глухая крыса (`~O`, находится справа от Pied Piper и движется влево)
- Вход: `~O~O~O~OP~O~OO~`
- Результат: 2 глухие крысы (`~O` и `O~`)
Важные моменты:
- Важно учитывать позицию Pied Piper относительно крыс. Все крысы до Pied Piper (слева от него) не считаются глухими, независимо от своего направления движения.
- Крысы, расположенные справа от Pied Piper, считаются глухими только тогда, когда они движутся в противоположном направлении относительно его команды.
Платформа: CodeWars
Название задачи: Factorial decomposition (Факториальное разложение)
Ссылка на задачу: https://www.codewars.com/kata/5a045fee46d843effa000070
Сложность: 5 kyu
Уже решили (На момент написания статьи): 8 118 из 30 324
Тэги: Основы
Оригинальное описание задачи:
The aim of the kata is to decompose `n!` (factorial n) into its prime factors.
Examples:
n = 12; decomp(12) -> "2^10 * 3^5 * 5^2 * 7 * 11"
since 12! is divisible by 2 ten times, by 3 five times, by 5 two times and by 7 and 11 only once.
n = 22; decomp(22) -> "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"
n = 25; decomp(25) -> 2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23
Prime numbers should be in increasing order. When the exponent of a prime is 1 don't put the exponent.
Notes
- the function is `decomp(n)` and should return the decomposition of `n!` into its prime factors in increasing order of the primes, as a string.
- factorial can be a very big number (`4000! has 12674 digits`, n can go from 300 to 4000).
- In Fortran - as in any other language- the returned string is not permitted to contain any redundant trailing whitespace: you can use `dynamically allocated character strings`.
Пояснение задачи:
Задача состоит в разложении факториала числа n (n) на простые множители и представлении результата в виде строки, где каждый простой множитель сопровождается степенью (количеством раз, которое число входит в разложение), причём множители записаны в порядке возрастания.
Пример:
- Для n=12 факториал равен 12=479\,001\,600, который делится на простые числа следующим образом:
12 = 2^{10} * 3^5 * 5^2 * 7 * 11
Результат разложения:
"2^10 * 3^5 * 5^2 * 7 * 11"
- Для n=22 факториал 22 содержит следующие простые множители:
22 = 2^{19} * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19
Результат разложения: "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"
- Для n=25 факториал 25 включает следующие простые множители:
25 = 2^{22} * 3^{10} * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23
Результат разложения:
"2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23"
Требования:
- Простые множители должны быть отсортированы по возрастанию.
- Если степень простого множителя равна единице, она не указывается (например, 3^1 будет просто записано как 3).
- Необходимо учитывать большие значения n (до 4000), где факториалы имеют тысячи цифр.
- Строка результата не должна содержать лишних пробелов
Наш текущий этап подошел к концу. Мы надеемся, что представленный материал был для вас познавательным и задачи вызвали интерес. Благодарим за уделенное время.
Приглашаем вас к активному диалогу по вопросам алгоритмов и задач. Будем рады вашим комментариям, предложениям и решениям, способствующим поддержанию конструктивной атмосферы. До новых встреч в следующих публикациях!
Вступайте в нашу телеграмм-группу Инфостарт