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

Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
Doomsday
18 / 0 / 0
Регистрация: 20.11.2012
Сообщений: 40
01.04.2013, 21:39     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #1
Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ).

Проблема такая: у меня все выводимые последовательности состоят из двух элементов, но ведь могут быть последовательности состоящие из трех, четырех и тд элементов, в которых нет двух одинаковых элементов подряд, а вот как это реализовать я не знаю.

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
#include "stdafx.h"
#include <stdlib.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include <math.h>
 
using namespace std;
 
int main() {
    int n, m=0, element1=0, element2=1; // Объявляем переменные 
    //element1 - первый сравниваемый элемент, element2 - второй сравниваемый элемент 
    //m -  количество последовательностей, в которых нет куска вида XX 
    //n - число элементов последовательности из нулей, единиц и двоек
    cout << "Enter n: ";
    cin >> n;
    int* arr = new int[n];// Задаем массив из n элементов
    srand (time(0)); // Инициализируем генератор псевдослучайных чисел
    int num;
    for (int i=0; i<n; i++) {
        num=rand() %3;// Генерируем случайные числа от 0 до 2
        arr[i]=num;
    }
    for (int i=0;i<n;i++) {cout << arr[i] << " " ;}
    cout << endl;// Выводим массив на экран
    do {
        if (arr[element1]>arr[element2] || arr[element1]<arr[element2]) {
            m=m++;
            cout << arr[element1];
            cout << " ";
            cout << arr[element2] << endl;// Сравниваем последовательно элементы: первый и второй, второй и третий и тд. 
            // Если они не равны, то выводим их на экран
        }
        element1=element1++;
        element2=element2++;
    }
    while (element2<n);// Выполняем цикл, пока второй элемент не станет равным числу n. 
    //После этого последний элемент не с чем будет сравнивать
    cout << "the number of sequences: ";
    cout << m << endl;// Выводим количество последовательностей, в которых нет куска вида XX
    delete []arr;//Стираем наш массив после использования, чтобы освободить память
    system("pause");
}
ну к примеру: имеем массив из 6 элементов: 0 1 2 1 1 0
моя программа выведет
0 1
1 2
2 1
1 0
а по идее должна вывести
0 1 2 1
1 0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2013, 21:39     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX )
Посмотрите здесь:

найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
C++ Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц
Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц C++
C++ Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX )
C++ Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Doomsday
18 / 0 / 0
Регистрация: 20.11.2012
Сообщений: 40
03.04.2013, 12:00  [ТС]     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #2
тема актуальна, помогите кто может
IrineK
Заблокирован
03.04.2013, 12:28     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #3
Насколько я поняла условие задачи, n - это длина подпоследовательности, которая выводится (а не количество всех элементов в целом).
Так, если n = 2, то для 0 1 2 1 1 0 ваш вывод
0 1
1 2
2 1
1 0
правильный.
Если n = 3
0 1 2
1 2 1
Если n = 4
0 1 2 1
При n = 5 и 6 - подпоследовательности без повторения не найдём.
Doomsday
18 / 0 / 0
Регистрация: 20.11.2012
Сообщений: 40
03.04.2013, 12:55  [ТС]     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #4
Цитата Сообщение от IrineK Посмотреть сообщение
Насколько я поняла условие задачи, n - это длина подпоследовательности, которая выводится (а не количество всех элементов в целом).
Так, если n = 2, то для 0 1 2 1 1 0 ваш вывод
0 1
1 2
2 1
1 0
правильный.
Если n = 3
0 1 2
1 2 1
Если n = 4
0 1 2 1
При n = 5 и 6 - подпоследовательности без повторения не найдём.
хм, получается я не совсем правильно понял условие задачи... то есть надо задать длину последовательности, которая будет выводиться и общее количество элементов, из которого эти последовательности будут браться.
Вопрос с тем как поправить код, чтобы все работало правильно остается
GuGo1991
267 / 261 / 93
Регистрация: 02.08.2012
Сообщений: 609
03.04.2013, 13:07     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #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
#include <iostream>
using namespace std;
 
int main(){
    int n;
    cout << "Enter n: ";
    cin >> n;
    int* arr = new int[n];
    srand (time(0));
    int num;
    for (int i=0; i<n; i++) {
        num=rand() %3;
        arr[i]=num;
    }
    for (int i=0;i<n;i++) {
        cout << arr[i] << " " ;
        if (arr[i] == arr[i + 1]){
           cout << endl;
        }
        }
    cout << endl;
        
    system("pause");
    return 0;
}
Я правильно понял?
Doomsday
18 / 0 / 0
Регистрация: 20.11.2012
Сообщений: 40
03.04.2013, 13:35  [ТС]     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #6
Цитата Сообщение от GuGo1991 Посмотреть сообщение
Я правильно понял?
помоему нет...
вот, как я думаю, оно должно выглядеть: 1. Вводим с клавиатуры длину массива, который состоит из 0,1,2.
2. Вводим с клавиатуры длину последовательностей.
3. Программа из этого массива выбирает последовательности указанной длины, проверяя при этом нет ли в них двух одинаковых элементов рядом.

например: 1.задаем длину массива - 8 элементов - допустим он сгенерирует такой массив - 0 2 1 1 2 0 1 2
2.задаем длину последовательности: 3
3. должно вывестись 0 2 1
1 2 0
2 0 1
0 1 2
Последовательность 2 1 1 вывестись не может, т.к. подряд идут две единицы
GuGo1991
267 / 261 / 93
Регистрация: 02.08.2012
Сообщений: 609
03.04.2013, 15:16     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #7
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
#include <iostream>
using namespace std;
 
int main(){
    int n, k, _n = 0, v = 0;
    cout << "Enter n: ";
    cin >> n;
    cout << "Enter k: ";
    cin >> k;
    int* arr = new int[n];
    srand (time(0));
    int num;
    for (int i=0; i<n; i++) {
        num=rand() %3;
        arr[i]=num;
    }
    for (int i=0;i<n;i++) {
        cout << arr[i] << " " ;
        }
        
    cout << endl;
    
    while (_n != (n - k + 1)){
        for (int l=v;l<k+v;l++){
            cout << arr[l];
            }
            v++;
            _n++;
            cout << endl;
        }
        
    cout << endl;
        
    system("pause");
    return 0;
}
Пока вот так... Осталось сравнить всех соседей
Постараюсь добить...
Doomsday
18 / 0 / 0
Регистрация: 20.11.2012
Сообщений: 40
04.04.2013, 11:15  [ТС]     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #8
Цитата Сообщение от GuGo1991 Посмотреть сообщение
Постараюсь добить...
Буду очень благодарен, а то горит курсач))
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
04.04.2013, 14:22     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #9
Если я правильно понял, решение в обобщенном виде. Выбираемая система счисления, выбираемая длина.
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
#include <iostream>
#include <cmath>
 
bool hasTwoDigitsInRow(int number, int radix) {
  int prevDigit = number % radix;
  number /= radix;
  while (number > 0) {
    if (number % radix == prevDigit) {
      return true;
    }
    prevDigit = number % radix;
    number /= radix;
  }
  return false;
};
 
void swap(char &a, char &b) {
  char c = a;
  a = b;
  b = c;
}
 
char *toRadix(int number, int radix, char *buffer) {
  static const char DIGITS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  char *result = buffer;
 
  while (number > 0) {
    *buffer++ = DIGITS[number % radix];
    number /= radix;
  }
  *buffer = '\0';
  for (char *i = result, *j = buffer - 1; i < j; ++i, --j) {
    swap(*i, *j);
  }
  return result;
}
 
int main(int argc, char **argv) {
  char buffer[1024];
 
  int radix = 3; // система счисления. 3 == 0, 1, 2
  int numberOfDigits = 3; // количество цифр
  // минимум и максимум можно по-хитрее считать,
  // чтобы не было лишних итераций, но мне лень
  int maxNumber = pow(radix, numberOfDigits);
  int minNumber = pow(radix, numberOfDigits - 1);
  
  for (int i = minNumber; i < maxNumber; ++i) {
    if (!hasTwoDigitsInRow(i, radix)) {
      std::cout << toRadix(i, radix, buffer) << std::endl;
    }
  }
  
  
  std::cin.get();
  return 0;
}
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
04.04.2013, 15:27     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
 
int main()
{
    std::vector<size_t> v = {0,1,2,1,1,0,2,1,2,2,2,0,1,0,2,1,0,0,2,1};
    
    for (auto begin = v.begin(), end = begin; end != v.end(); begin = end)
    {
        end = std::adjacent_find(end, v.end());
        if (end != v.end())
            std::copy(begin, ++end, std::ostream_iterator<size_t>(std::cout," "));
        else
            std::copy(begin, end, std::ostream_iterator<size_t>(std::cout," "));
        std::cout<<"\n";
    }
    return 0;
}
http://liveworkspace.org/code/3sVrGt
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 16:47     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX )
Еще ссылки по теме:

Получить все n-элементные последовательности из нулей и единиц содержащие ровно m единиц (m<=n) C++
Вывести все простые числа, в которых нет двух подряд идущих одинаковых цифр C++
Среди всех n-битных двоичных чисел указать количество тех, в двоичной записи которых нет k единиц подряд C++

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

Или воспользуйтесь поиском по форуму:
GuGo1991
267 / 261 / 93
Регистрация: 02.08.2012
Сообщений: 609
04.04.2013, 16:47     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) #11
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
#include <iostream>
using namespace std;
 
int main(){
    int n, k, _n = 0, v = 0, _k = 0, l = 0, _l = 0, masIndex = 0;
    cout << "Enter n: ";
    cin >> n;
    cout << "Enter k: ";
    cin >> k;
    int* arr = new int[n];
    srand (time(0));
    int num;
    for (int i=0; i<n; i++) {
        num=rand() %3;
        arr[i]=num;
    }
    for (int i=0;i<n;i++) {
        cout << arr[i] << " " ;
        }
        
    cout << endl;
 
    int* mas = new int[k-1];
    int index = n - k + 1;
    while (_n != (index)){
        for (l=v;l<k+v;l++){
            mas[masIndex] = arr[l];
            masIndex++; 
            }
        for (int j=0;j<masIndex;){
            if (mas[j] != mas[j+1])
                j++;
                else{ 
                    masIndex = 0;
                    break;
                    }
                }
        if (masIndex > 0){
            for (int z=0;z<masIndex;z++){
                cout << mas[z];
                }
            cout << endl;
            }
        masIndex = 0;
        
        v++;
        _n++;
        }
    cout << endl;
    
    system("pause");
    return 0;
}
Всё, вроде работает )
Yandex
Объявления
04.04.2013, 16:47     Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX )
Ответ Создать тему
Опции темы

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