Цепочка

Тема в разделе "C/C++/C#", создана пользователем Nasferatu, 8 апр 2011.

  1. Nasferatu

    Nasferatu Гость

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


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

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Что-то я не совсем понимаю.. Последовательности где хранятся и откуда берутся?
     
  3. Nasferatu

    Nasferatu Гость

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Ок. Генератором случайных чисел.

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

    Nasferatu Гость

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Какого размера?
     
  7. Nasferatu

    Nasferatu Гость

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    N - это длина последовательности. Т.е., нужно искать различные последовательности длиной N в массиве размера N ?
     
  9. Nasferatu

    Nasferatu Гость

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Есть идеи? Наброски?
     
  11. Nasferatu

    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 .
     
  12. Nasferatu

    Nasferatu Гость

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Во-первых, это не твои соображения, это ты скопировал, видимо из условий...
    Во-вторых, у меня складывается такое чувство, что ты хочешь чтобы все сделали за тебя только для того чтобы ты сдал экзамен\зачет.
    В-третьих, с нуля думать о решении данной проблемы за кого-то у меня нет никакого желания.
     
  14. Nasferatu

    Nasferatu Гость

    Я тут кое что написал...Посмотрите,может исправите что.Работает но неправельно
    Код (C++):
    //#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;
    }
     

Поделиться этой страницей