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

@erenije · Регистрация: 30.10.2017

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

Ожерелье. Круглое ожерелье состоит из N жемчужин. Каждая жемчужина либо черного (Ч), либо белого (Б) цвета. Получите количество всевозможных вариантов ожерелий, которые можно составить из N жемчужин.
Ожерелья являются замкнутыми. Это означает, например, что два ожерелья, состоящие из четырех жемчужин: Б-Б-Б-Ч и Б-Ч-Б-Б являются одинаковыми.
Формат входных данных
Содержит единственное целое число N (N≤8).
Формат выходных данных
В первой строке напечатать количество полученных ожерелий.

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
#include <iostream>
using namespace std;
typedef int vec[20];
vec p; int n;
void print()
{
 for (int i=1;i<=n;i++) cout<<p[i]<<" ";
 cout<<endl;
}
void swap(int &a, int &b){
 int r;
 r=a; a=b; b=r;
}
void main() {
    int i, j, k;
  cin>>n;
 for (i=1;i<=n;i++) p[i]=i;
  print();
  do {
     for (i=n-1; i>=1, p[i] > p[i + 1]; i--);
        if (i==0) break;
        for (j=n; p[j]<p[i]; j--);
        swap(p[i], p[j]);
        for (k = 1; k<=(n - i) / 2; k++ )
        swap(p[i + k], p[n + 1 - k]);
        print();
  } while (true);
}

Перестановки все правильно делает. Я не могу реализовать замкнутый круг и отсеивать одинаковые значения. Помогите пожалуйста.

@RomanSedyshev · 08.10.2018, 13:22

Может представить ожерелье в виде набора битов и обрабатывать битовую последовательность?
Для исключения повторяющихся ожерелий сдвигаешь биты оператором << и в начало добавляешь то, что вытесняется. Нужно сделать полный круг сдвигов, и если какое-то из значений совпало с тем, что уже есть, то этот вариант отбрасывается. Иначе выводишь его.

@Martein · 08.10.2018, 13:45

Мне видится решение в создании дополнительного массива в качестве "чёрного списка" комбинаций. При создании очередной комбинации в "чёрный список" заносятся все её "вращённые" варианты, с предварительной проверкой наличия уже имеющихся в списке таких же комбинаций для избавления от дубликатов (но это увеличивает количество операций). То есть для Ч-Б-Б-Б внести в "чёрный список" Б-Ч-Б-Б, Б-Б-Ч-Б, Б-Б-Б-Ч. При создании очередной комбинации проверить наличие для неё в "чёрном списке" совпадения, при отсутствии которого комбинация считается удачной.

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	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 Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии 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. . .

@RomanSedyshev 51 / 39 / 15 Регистрация: 20.09.2018 Сообщений: 163
	08.10.2018, 13:22
	Может представить ожерелье в виде набора битов и обрабатывать битовую последовательность? Для исключения повторяющихся ожерелий сдвигаешь биты оператором << и в начало добавляешь то, что вытесняется. Нужно сделать полный круг сдвигов, и если какое-то из значений совпало с тем, что уже есть, то этот вариант отбрасывается. Иначе выводишь его. 0

@Martein 704 / 109 / 21 Регистрация: 22.06.2014 Сообщений: 241
	08.10.2018, 13:45
	Мне видится решение в создании дополнительного массива в качестве "чёрного списка" комбинаций. При создании очередной комбинации в "чёрный список" заносятся все её "вращённые" варианты, с предварительной проверкой наличия уже имеющихся в списке таких же комбинаций для избавления от дубликатов (но это увеличивает количество операций). То есть для Ч-Б-Б-Б внести в "чёрный список" Б-Ч-Б-Б, Б-Б-Ч-Б, Б-Б-Б-Ч. При создании очередной комбинации проверить наличие для неё в "чёрном списке" совпадения, при отсутствии которого комбинация считается удачной. 0