Цепочка

[Nasferatu]

Как написать данную программу?Помогите пожалуйста.


Посчитать количество различных, закольцованных последовательностей длиной N, где a = 0/1 (0 или 1). Две последовательности считаются различными, если из одной нельзя получить вторую путем циклических сдвигов.
Ввод:
В первой строке вводится число N (1 <= N <= 30).

Вывод:
В первой строке выведите целое число – количество различных, закольцованных последовательностей из 0 или 1 длиной N.

 

[lazybiz]

Что-то я не совсем понимаю.. Последовательности где хранятся и откуда берутся?

 

[Nasferatu]

Самому создать.Вроде нужно посчитать сколько их получится

 

[lazybiz]

Самому создать.

Ок. Генератором случайных чисел.

Давай еще раз попробуем:

Последовательности где хранятся?

 

[Nasferatu]

В динамическом массиве

 

[lazybiz]

В динамическом массиве

Какого размера?

 

[Nasferatu]

Массив размерностью N

 

[lazybiz]

N - это длина последовательности. Т.е., нужно искать различные последовательности длиной N в массиве размера N ?

 

[Nasferatu]

В общем да.Нужно найти количество различных последовательностей в масcиве N

 

[lazybiz]

Есть идеи? Наброски?

 

[Nasferatu]

Есть идейка,только не знаю как осуществить её с помощью кода



Можно назвать последовательность из 0 и 1, хорошей. Обозначим число хороших последовательностей длины k через Fk .
Попытаемся теперь выразить количество хороших последовательностей длины k через количества хороших последовательностей меньшей длины. Для этого рассмотрим, как можно построить хорошую последовательность длины k. Если последним символом этой последовательности выбрать 0, то в качестве предыдущих k-1 символов можно взять произвольную хорошую последовательность длины k-1. А таких последовательностей Fk-1 . Если же последним символом выбрать 1, то на (k-1)-ом месте 1 стоять не может и, значит, там стоит 0. Тогда в качестве первых k-2 символов можно взять любую хорошую последовательность длины k-2, а их количество Fk-2 . Таким образом, находим, что Fk = Fk-1 + Fk-2.
Получив эту рекуррентную формулу, нам остается задать первые два значения рассматриваемой последовательности (F0 = 1, F1 = 2), а затем в цикле последовательно вычислить числа F2 , F3 , ..., FN .

 

[Nasferatu]

Помогите пожалуйста...(

 

[lazybiz]

Во-первых, это не твои соображения, это ты скопировал, видимо из условий...
Во-вторых, у меня складывается такое чувство, что ты хочешь чтобы все сделали за тебя только для того чтобы ты сдал экзамен\зачет.
В-третьих, с нуля думать о решении данной проблемы за кого-то у меня нет никакого желания.

5. Ну а те, кто не хочет что-то делать самостоятельно должны понимать, что работа людей стоит денег. Даже самая мелкая. А потому если вы готовы платить за решение своей проблемы, то так же указывайте это в своей теме. Что-то в духе: Нужно решить такую-то задачу. Оплата.

 

[Nasferatu]

Я тут кое что написал...Посмотрите,может исправите что.Работает но неправельно

//#include <conio>
#include <iostream>
using namespace std;


int main()
{
int N, s=2;
cin>>N;

for(int i=1; i<N; ++i)
{
if(i==1 || i==N-1)
{
++s;
continue;
}
if(i==2)
{
s+=N-i;
continue;
}
s+=N-i;
for(int j=i-1; j>1; --j)
{
if(j!=2)
{
if(j*2>=i)
s+=N-i-1+N-i-2;
//else
//s+=N-i-2;
}
else
{
if(j*2>=i)
s+=N-i-2+N-i-3;
// else
//s+=N-i-3;
}
}
}
cout<<s;

//_getch();
return 0;
}