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

Определение периодической последовательности - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
N.1.K.O
0 / 0 / 0
Регистрация: 12.02.2010
Сообщений: 3
12.02.2010, 10:51     Определение периодической последовательности #1
Товарищи! Прошу вас о помощи! Есть задача, и я не могу её решить

Массив заполнен только нулями и единицами.Определите, будет ли полученная последовательность периодической и, если да, то найдите длину наименьшего периода.
Тест. 1; 0; 0; 0; 1; 0; 0; 0; 1; 0; 0; 0;

Надеюсь на вашу помощь

Добавлено через 18 минут
Логически то я могу понять как делать, а вот знания языка не хватает

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

Добавлено через 1 час 44 минуты
Народ! Очень надо!!!

Добавлено через 8 часов 29 минут
Ну хотя бы с этими циклами подскажите как это в программе реализовать!!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
12.02.2010, 11:49     Определение периодической последовательности #2
Простой перебор.
Перебираем длину периода. С 1 до n

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int per;
 
for (L=1;L<n;L++)
{
  per = 1;
  for (j = 0;j<L;j++)
  {
    k=0;
    while ((k+L)<n)
    {
      if (a[k]!=a[k+L]) {per = 0; break;}
      k+=L;
    }
    if (!per) break;
  }
 if (per == 1) printf ("Период: %d\n", L);
}
Как-то так. Работоспособность еще не проверял.
N.1.K.O
0 / 0 / 0
Регистрация: 12.02.2010
Сообщений: 3
12.02.2010, 12:10  [ТС]     Определение периодической последовательности #3
Ага, тогда в готовом виде

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
int main()
{
int per;
int L,j,k,n;
for (L=1;L<n;L++)
 
  per = 1;
  for (j = 0;j<L;j++)
  {
    k=0;
    while ((k+L)<n)
    {
      if (a[k]!=a[k+L]) {per = 0; break;}
      k+=L;
    }
    if (!per) break;
  }
 if (per == 1) printf ("Период: %d\n", L);
}
но выдаёт ошибку
if (a[k]!=a[k+L]) {per = 0; break;}
С2065 не объявленный идентификатор
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
12.02.2010, 12:19     Определение периодической последовательности #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
#include <stdio.h>
 
int main(void)
{
int per, L, j, k;
int a[20] = {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1};
int n=20;
 
for (L=1;L<n;L++)
{
  per = 1;
  for (j = 0;j<L;j++)
  {
    k=j;
    while ((k+L)<n)
    {
      printf ("a[%d] = %d, a[%d] = %d\n",k,a[k],k+L, a[k+L]);
      if (a[k]!=a[k+L]) {per = 0; break;}
      k+=L;
    }
    if (!per) break;
  }
 if (per == 1) {printf ("Период: %d\n", L); break;}
}
}
N.1.K.O
0 / 0 / 0
Регистрация: 12.02.2010
Сообщений: 3
12.02.2010, 12:44  [ТС]     Определение периодической последовательности #5
Спасибо огромное, вроде работает, только результат не особо понятный
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
12.02.2010, 13:11     Определение периодической последовательности #6
Сначала выводятся пары сравниваемых элементов. затем выводится период. Если вставить какой-нибудь разделитель перед проверкой if (per == 1) {printf ...}, то вывод будет выглядеть более осмысленно. Также считается, что строка:
Код
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0
Имеет период, равный 14.
Если же у нас достаточно уникальная строка:
Код
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1
то просто ничего не выведется.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2010, 13:59     Определение периодической последовательности
Еще ссылки по теме:

Вычисление значений периодической функции C++
Определение К-го числа последовательности Фиббоначи C++
Определение монотонности последовательности C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.02.2010, 13:59     Определение периодической последовательности #7
Цитата Сообщение от N.1.K.O Посмотреть сообщение
по идее так:
Ищем первую единицу, потом итерация для подсчета элементов пока не попадется единица. Длинну такого первого периода пишем в переменную. Потом уже точно так же проверяем до конца все остальные элементы, и если находим хотя бы один период другой длинны, то сразу же прерываем цикл и пишем что последовательность непериодична. Если не выкинуло с цикла - то в конце выводим длинну самого первого периода, который записали.
Алгоритм неправильный. Например для варианта: 100011100011 Ваш алгоритм выдаст что последовательность непериодична. Хотя на самом деле период 100011. Ошибка здесь:
и если находим хотя бы один период другой длинны, то сразу же прерываем цикл и пишем что последовательность непериодична.
, нужно не прерывать цикл, а увеличивать длину первого периода и проверять снова.
Yandex
Объявления
12.02.2010, 13:59     Определение периодической последовательности
Ответ Создать тему
Опции темы

Текущее время: 23:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru