Перебор символов в автомобильном номере

@dsfsdfds · Регистрация: 02.10.2020

Студворк — интернет-сервис помощи студентам

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

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

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

Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать.

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

Формат входного файла
Входной файл содержит одну строку, которая представляет собой корректный автомобильный номер.

Формат выходного файла
В первой строке выходного файла выведите число k — количество номеров, которые могут получиться из заданного перестановкой букв и/или цифр. В последующих k строках выведите все такие номера в произвольном порядке.

Заранее благодарен.

Байт · 30.12.2020, 12:18

dsfsdfds, Считать (перебирать) тут ничего не нужно. Чисто комбинаторная задача, имеющая конечное решение. Зависит от того, сколько одинаковых цифр и букв.
все разные 10!/7!*12!/9!9!
2 цифры совпадают , буквы разные 3*12!/9!
цифры разные, 2 буквы совпадают 3* 10!/7!
И так далее...

@dsfsdfds · 30.12.2020, 13:08 **[ТС]**

Сообщение от dsfsdfds

В последующих k строках выведите все такие номера в произвольном порядке.

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

@likehood · 30.12.2020, 13:45

dsfsdfds, для получения перестановок в стандартной библиотеке существует функция std::next_permutation.

Байт · 30.12.2020, 14:39

Сообщение от dsfsdfds

попрошу быть внимательнее

Безусловно. буду стараться следовать вашему совету. В свою очередь, хочу посоветовать вам внимательнее перечитать правила форума и особое внимание обратить на п.4.7

Добавлено через 6 минут
likehood, там не только перестановке. сочетания тоже. Правда, очень простенькие.
Но конечно, вместо перебора следует воспользоваться генерацией.
И прошу прощения. В посте 2 при оценке количества вариантов я был не прав.

@nalbe666 · 30.12.2020, 14:41

dsfsdfds,

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <set>
 
std::set<std::string> set;
 
void foo(std::string& s, const int& d = 0) {
    if (d == 6) {
        std::swap(s[0], s[3]);
        set.insert(s);
        std::swap(s[0], s[3]);
        return;
    }
    for (int i(d); i < (d < 3 ? 3 : 6); ++i) {
        std::swap(s[d], s[i]);
        foo(s, d + 1);
        std::swap(s[d], s[i]);
    }
}
 
 
int main()
{
    std::string s;
    std::cin >> s;
 
    std::swap(s[0], s[3]);
    foo(s);
    std::cout << set.size() << '\n';
    for (auto& it : set) {
        std::cout << it << '\n';
    }
 
    return 0;
}

@likehood · 30.12.2020, 14:58

nalbe666, здорово получилось!

Рекурсия здесь очень даже к месту.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@dsfsdfds 0 / 0 / 0 Регистрация: 02.10.2020 Сообщений: 25

	Перебор символов в автомобильном номере 30.12.2020, 11:33. Показов 6124. Ответов 6 Метки c++, c++ для начинающих, перебор (Все метки) Условие При расследовании дорожно-транспортных происшествий часто возникают проблемы с розыском автомобилей, водители которых покинули место происшествия. Получение свидетельских показаний — непростая работа. Ситуация осложняется тем, что очень часто свидетели могут только приблизительно вспомнить номер автомобиля. При этом с большой вероятностью опрашиваемый может перепутать порядок цифр или букв в номере. По полученному от свидетеля происшествия номеру, подсчитайте, сколько различных номеров может получиться из него перестановкой букв и/или цифр, а также выведите все такие номера. Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать. В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита. Формат входного файла Входной файл содержит одну строку, которая представляет собой корректный автомобильный номер. Формат выходного файла В первой строке выходного файла выведите число k — количество номеров, которые могут получиться из заданного перестановкой букв и/или цифр. В последующих k строках выведите все такие номера в произвольном порядке. Заранее благодарен. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	30.12.2020, 12:18
	dsfsdfds, Считать (перебирать) тут ничего не нужно. Чисто комбинаторная задача, имеющая конечное решение. Зависит от того, сколько одинаковых цифр и букв. все разные 10!/7!12!/9!9! 2 цифры совпадают , буквы разные 312!/9! цифры разные, 2 буквы совпадают 3* 10!/7! И так далее... 0

@likehood 1272 / 1029 / 470 Регистрация: 25.12.2016 Сообщений: 3,333
	30.12.2020, 13:45
	dsfsdfds, для получения перестановок в стандартной библиотеке существует функция `std::next_permutation`. 0

@likehood 1272 / 1029 / 470 Регистрация: 25.12.2016 Сообщений: 3,333
	30.12.2020, 14:58
	nalbe666, здорово получилось! Рекурсия здесь очень даже к месту. 1

Перебор символов в автомобильном номере

Решение