Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Татаринов Артур
0 / 0 / 0
Регистрация: 24.05.2013
Сообщений: 4
#1

Жемчужное ожерелье - C++

05.06.2014, 07:06. Просмотров 557. Ответов 5
Метки нет (Все метки)

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

Формат входных данных
Содержит единственное целое число N (N≤8).

Формат выходных данных
Первая строка количество полученных ожерелий. В следующих строках описание ожерелий.

Пример
input.txt output.txt
3 4

Примечание. В данном примере можно получить следующие ожерелья:
ЧЧЧ
ЧЧБ
ЧББ
БББ

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <conio.h>
using namespace std;
typedef __int64 vec[100];
vec p,a,b; int sifra, kol=0,kount=0, c,kop=0;
 
void print(__int64 k)
{   
    for(int i=1; i<=k; i++)
        a[i]=p[i];
    for(int i=1; i<=k; i++)
    {
        for(int l=1; l<=k; l++)
        {
            if(a[i]!=b[i] && a[i+1]!=b[i+1] && a[i+2]!=b[i+2] && a[i+3]!=b[i+3]) kount++;
            else break;
            c=a[k];
            for(int h=k; h>=1; h--)
                a[h]=a[h-1]; 
            a[1]=c;
        }
    }
    if(kount==4) 
        for(int j=1; j<=k; j++)
        {
            b[kol]=a[kol]; 
            kol++;
        }
        kount=0;
}
 
void razm(__int64 n, __int64 k)
{
    __int64 i,j, flag;
    for(i=1;i<=k; i++) p[i]=0;
    print(k);
    do
    {
        flag=0;
        for(i=k; i>=1; i--)
            if(p[i]<n-1)
            {
                p[i]++;
                for(j=i+1; j<=k; j++)
                p[j]=0;
                print(k);
                flag=1;
                break;
            }
    }while(flag);
}
 
void main()
{
    int k,l=0;
    double kolvar;
    /*freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);*/
    cin>>k;
    memset(b,3,20);
    razm(2,k);
    for(int i=0; i<=2^k; i++)
    {
        for(int j=0; j<=2^k; j++)
        {
 
            if(kop==4) {kop=0;cout<<endl;}
            cout<<b[i]<<' ';
            kop++;
        }
 
        cout<<endl;
    }
    getch();
}
Перестановки все правильно делает. Я не могу реализовать замкнутый круг и отсеивать одинаковые значения. Помогите пожалуйста.
Вот пытался сделать в ф-ии print. Что то не получается.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2014, 07:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Жемчужное ожерелье (C++):

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две соседние бусины не были покрашены в один цвет....

Имеется ожерелье которое состоит из k бусинок, жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд - Turbo Pascal
Имеется ожерелье которое состоит из k бусинок(k&lt;=20), жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд.Максимум...

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две соседние бусины не были покрашены в один цвет....

Имеется ожерелье которое состоит из k бусинок, жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд - Turbo Pascal
Имеется ожерелье которое состоит из k бусинок(k&lt;=20), жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд.Максимум...

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две соседние бусины не были покрашены в один цвет....

Имеется ожерелье которое состоит из k бусинок, жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд - Turbo Pascal
Имеется ожерелье которое состоит из k бусинок(k&lt;=20), жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд.Максимум...

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две соседние бусины не были покрашены в один цвет....

Имеется ожерелье которое состоит из k бусинок, жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд - Turbo Pascal
Имеется ожерелье которое состоит из k бусинок(k&lt;=20), жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд.Максимум...

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две соседние бусины не были покрашены в один цвет....

Имеется ожерелье которое состоит из k бусинок, жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд - Turbo Pascal
Имеется ожерелье которое состоит из k бусинок(k&lt;=20), жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд.Максимум...

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две соседние бусины не были покрашены в один цвет....

Имеется ожерелье которое состоит из k бусинок, жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд - Turbo Pascal
Имеется ожерелье которое состоит из k бусинок(k&lt;=20), жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд.Максимум...

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две соседние бусины не были покрашены в один цвет....

Имеется ожерелье которое состоит из k бусинок, жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд - Turbo Pascal
Имеется ожерелье которое состоит из k бусинок(k&lt;=20), жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд.Максимум...

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две со

Ожерелье - Комбинаторика
Найдите количество способов раскрасить ожерелье из 11 бусин в 3 цвета так, чтобы никакие две соседние бусины не были покрашены в один цвет....

Имеется ожерелье которое состоит из k бусинок, жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд - Turbo Pascal
Имеется ожерелье которое состоит из k бусинок(k&lt;=20), жёлтого и красного цветов.Найти максимальное кол-во бусинок идущих подряд.Максимум...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
05.06.2014, 07:12 #2
гораздо проще будет написать функцию сочетания
С(m, n) = (n!) / (m! * (n - m)!)

m всегда будет равно 2.

поэтому, Вам только необходимо написать функцию факториала - это элементарно. В инете куча примеров на любой вкус и цвет.
0
Татаринов Артур
0 / 0 / 0
Регистрация: 24.05.2013
Сообщений: 4
05.06.2014, 07:15  [ТС] #3
Это понятно. Спасибо. Мне нужно вывести эти неодинаковые значения.
0
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
05.06.2014, 09:26 #4
генерация сочетаний в лексикографическом порядке
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.06.2014, 01:51 #5
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/////////////////////////////////////////////////////////////////////////////////////////
//Круглое ожерелье состоит из N жемчужин. Каждая жемчужина либо черного (Ч), либо белого (Б) цвета. 
//Получите количество всевозможных вариантов ожерелий, которые можно составить из N жемчужин.
//Ожерелья являются замкнутыми. Это означает, например, что два ожерелья, состоящие из четырех жемчужин: 
//Б-Б-Б-Ч и Б-Ч-Б-Б являются одинаковыми.
//
//Формат входных данных
//Содержит единственное целое число N (N≤8).
//
//Формат выходных данных
//Первая строка количество полученных ожерелий. В следующих строках описание ожерелий.
//
//Пример
//input.txt output.txt
//3 4
//
//Примечание. В данном примере можно получить следующие ожерелья:
//ЧЧЧ
//ЧЧБ
//ЧББ
//БББ
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
int     const   MAX_LEN     =   8;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                 T_str;
typedef std::bitset< MAX_LEN    >   T_necklace;
typedef std::vector< T_str      >   T_neckl_strings;
/////////////////////////////////////////////////////////////////////////////////////////
bool    necklace_with_len_is_min
    (
        T_necklace  const   &   necklace,
        int                     n
    )
{
    T_str   str     =   necklace.to_string().substr( MAX_LEN - n );
    str             =   str + str;
 
    for( int i = 0; i < n; ++i )
    {
        if  (
                    T_necklace( str, i, n )     .to_string()
                <   necklace                    .to_string()
            )
        {
            return  false;
        }
    }//for
 
    return  true;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_black_and_white_necklaces_with_len( int  n )
{
    T_neckl_strings     neckl_strings;
 
    for( int  i = 0; i < pow(2.0, n); ++i )
    {
        T_necklace  necklace(i);
 
        if  (
                necklace_with_len_is_min
                    (
                        necklace,
                        n
                    )
            )
        {
            neckl_strings.push_back
                (
                    necklace.to_string().substr( MAX_LEN - n )
                );
        }//if
    }//for
 
    std::cout   <<  std::endl
                <<  neckl_strings.size()
                <<  std::endl
                <<  std::endl;
 
    std::copy
        (
            neckl_strings.begin             (),
            neckl_strings.end               (),
            std::ostream_iterator<T_str>    (std::cout, "\n")
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_prompt_and_input_value_from_interval
    (
        T_str   const   &   prompt,
        int             &   val,
        int                 L,
        int                 R
    )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  val;
    }
    while   (
                    val < L
                ||  val > R
            );
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::ostringstream  sout;
 
        sout    <<  "Введите N (1.."
                <<  MAX_LEN
                <<  "): ";
 
        int     n   =   0;
 
        print_prompt_and_input_value_from_interval
            (
                sout.str(),
                n,
                1,
                MAX_LEN
            );
 
        print_black_and_white_necklaces_with_len( n );
 
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}
1
Татаринов Артур
0 / 0 / 0
Регистрация: 24.05.2013
Сообщений: 4
10.06.2014, 19:33  [ТС] #6
Спасибо за предоставленную информацию) Узнал много нового

Добавлено через 35 секунд
Спасибо) Досконально изучил код и понял)
0
Yandex
Объявления
10.06.2014, 19:33
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru