Разминка: сформировать последовательность без трех подстрок подряд.

Предлагаю для разминки мозгов попробовать написать программу ( алгоритм ) для создания строки, заданной длины, в которой нет трех одинаковых подстрок подряд (длина подстроки может быть любой)

Язык не обязательно С

 

UPD: строка состоит исключительно из 0 и 1.
Примеры:
01011010 - валидная строка, нет трех одинаковых подстрок, идущих подряд
1101010100 - невалидная строка, есть повторения.

 

Нельзя что бы три подряд одинаковых группы по 2 бита шли?

 

длина подстроки может быть любой
от 1 до length/3, где length длина строки

 

Конкретно алгоритм не скажу, поскольку эта задача достаточно далека от моих интересов, соотв., вникать в детали не особенно и хочется. Тем неменее, есть книга Смит Б. Методы и алгоритмы вычислений на строках, где среди прочего автор разбирает, что-то подобное. Если не ошибаюсь ( на данный момент, буки нет под рукой ), он назавет это "внутренними паттернами".

 

Ation

Если длина строки больше двух, то задача не решаема в такой постановке.

 

в таком случае на алфавите {0, 1} вадиндые строки имеют размер меньше 5 символов, и их похоже всего две... поскольку например строка "10101" невалидна, поскольку имеет три подстроки "1" длины в один символ... для адекватности решения задачи нужны длины подстрок хотя бы от двух символов...

 

Еще раз условия. Читайте, плиз, внимательнее.
Длина строки от одного до предела беззнакового инта.
Строка состоит из символов 0 и 1.
Длина подстроки может быть любой.
Не должно быть трех одинаковых подстрок идущих строго подряд
1011 - нормально
0111 - невалидная.
То, что задача имеет решение - это 100 %. (Даже минимум два принципиально разных)

 

в лоб и без проверки

Код (Text):

1. int is_3_chnks(unsigned N, int n){
2.   unsigned mask;
3.   int i;
4.  
5.   for(i = 1; i <= n/3; i++){
6.     mask = 1 | (1 << i) | (1 << 2*i);
7.    
8.     if( ( N >> (n - i*3)) % mask != 0 )
9.       return true;
10.   }
11.  
12.   return false;
13. }
14.  
15.  
16. unsigned get_not_3_chnks_chain(){
17.   unsigned N;
18.   int n;
19.  
20.   N = rnd_0_1() | (rnd_0_1() << 1);
21.  
22.   for(n = 2; n < maxlen(N); n++){
23.     N |= (rnd_0_1() << n);
24.  
25.     if(is_3_chnks(N, n)){
26.       N = xor(N, 1 << n);
27.  
28.       if(is_3_chnks(N, n+1))
29.         N &= (1 << n) - 1;
30.         break;
31.     }
32.   }
33.  
34.   return N;
35. }

 

Ключевое слово - строка заданной длины
В любом случае этот пример не работает.

 

сразу оговорюсь написал на скорую руку не отлаживал баги вполне могут быть но впринципе работает

Код (Text):

1. #include <c++>
2.  
3. int i(char *bsr, size_t len){
4.     char *p = bsr + len - 1;
5.     while (*p != '0' && p != bsr)
6.         *p-- = '0';
7.     if (p == bsr && *p == '1')
8.         return 0;
9.     *p-- = '1';
10.     return 1;
11. }
12.  
13. char* c(size_t s){
14.     if ((__int64)s + 1 > SIZE_MAX) __asm int 3;
15.     char *p = (char*)malloc(s+1);
16.     if (p) memset(p, '0', s), p[s] = '\0';
17.     return p;
18. }
19.  
20. int v(char *str, size_t len){
21.     if (len < 3) __asm int 3;
22.     char tmp[1024];
23.     size_t i = 1, ggf = 0, eq = 0;
24.     char *p, *q;
25.     for (;ggf <= len - 3;ggf++, i = 1){
26.         for (;i < len - ggf;){
27.             p = str + ggf;
28.             memmove(tmp, p, i);
29.             tmp[i] = '\0';
30.             q = p + i;
31.             bool fl = false;
32.             while (*q){
33.                 if (!strncmp(q, tmp, i)){
34.                     if (++eq == (!fl?2:3))
35.                         return 0;
36.                 } else {
37.                     eq = 0, fl = true;
38.                 }
39.                 if (str + len - 1 - q > (ptrdiff_t)i)
40.                     q += i;
41.                 else
42.                     q++;
43.             }
44.             i++;
45.             eq = 0;
46.         }
47.     }
48.     return 1;
49. }
50.  
51. int main(){
52.     size_t len = 3;
53.     char* buff = c(len);
54.     for (;;){
55.         if (v(buff, len)) puts(buff);
56.         if (!i(buff, len))
57.             break;
58.     }
59. }

 

Как я понимаю, строка формируется как поиск первого двоичного числа, которое соответствует требованиям.
Алгоритм работает, но не самый оптимальный.
Попробуй посмотреть, что получится для длины скажем в 100, или 1025
Возможно его можно улучшить начальной инициализацией. К примеру разбивать на меньшие строки (скажем по 10), и искомую строку заполнять этим строками (полученными на разных итерациях).

PS: свой алгоритм и реализацию выложу завтра, когда все кто хотел успеют подумать и высказаться.

И большая просьба для любителей адресной арифметики, оставляйте минимальные комментарии =)
И желательно хоть краткое описание алгоритма, это упростит жизнь и сэкономит время всем читающим

 

Ation

пример был писан из головы сразу в форму. после проверки и исправления нескольких очевидных опечаток

Код (Text):

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <time.h>
4.  
5. #define maxlen_N sizeof(unsigned)*8
6.  
7. #define true 1
8. #define false 0
9.  
10.  
11. unsigned rnd_0_1(){
12.   return (unsigned)rand() & 1;
13. }
14.  
15. unsigned xor(unsigned a, unsigned b){
16.   return (a & ~b) | (b & ~a);
17. }
18.  
19. void print_bits(unsigned N, int len){
20.   for(; len > 0;){
21.     len--;
22.     printf("%d", (N >> len) & 1);
23.   }
24.   printf("\n");
25. }
26.  
27.  
28. //----------------------------------------------------------------------
29. int is_3_chnks(unsigned N, int n){
30.   unsigned mask;
31.   int i;
32.  
33.   for(i = 1; i <= n/3; i++){
34.     mask = 1 | (1 << i) | (1 << 2*i);
35.    
36.     if( ( N >> (n - i*3)) % mask == 0 )
37.       return true;
38.   }
39.  
40.   return false;
41. }
42.  
43.  
44. unsigned get_not_3_chnks_chain(){
45.   unsigned N;
46.   int n;
47.  
48.   N = rnd_0_1() | (rnd_0_1() << 1);
49.  
50.   for(n = 2; n < maxlen_N; n++){
51.     N |= (rnd_0_1() << n);
52.  
53.     if(is_3_chnks(N, n+1)){
54.       N = xor(N, 1 << n);
55.  
56.       if(is_3_chnks(N, n+1)){
57.         N &= (1 << n) - 1;
58.         break;
59.       }
60.     }
61.   }
62.  
63.   return N;
64. }
65. //----------------------------------------------------------------------
66.  
67.  
68. main(){
69.   int i;
70.  
71.   srand( (unsigned)time( NULL ) );
72.  
73.   for(i = 0; i < 20; i++){
74.     print_bits(get_not_3_chnks_chain(), maxlen_N);
75.   }
76. }

тип контейнер для строки своей зададите сами

если надо строку не короче заданной

то добавим пару строк и для обеспечения этого
чуть позже только

 

Если строка слишком длиная, то отрежьте сколько нужно.

Код (Text):

1.   char s[19684]="0";
2.   for(l=1;l<19683;l*=3)
3.     for(int i=0;i<l;i++){
4.       s[i+l]=s[i];
5.       s[i+l+l]=s[l-1-i]^1;
6.     }
7.   printf("%s\n",s);

 

Black_mirror

у меня не работает. создает повторяющийся рисунок

 

qqwe
А в каком именно месте не работает? Вот код для проверки:

Код (Text):

1. for(int i=1;i<=l/3;i++){
2.   for(int j=0;j<=l-3*i;j++){
3.     if(!strncmp(s+j,s+j+i,i)&&!strncmp(s+j,s+j+i+i,i)){
4.       printf("%s\%s\n%s\n",s+j,s+j+i,s+j+j);
5.       getchar();
6.     }

 

Black_mirror

код в мэйне без объявлений и инициализаций

Код (Text):

1.   for(l = 1; l < 19683; l *= 3){
2.     for(i = 0; i < l; i++){
3.       s[i + l] = s[i];
4.       s[i + l + l] = s[l - 1 - i] ^ 1;
5.     }
6.     printf("%s\n", s);
7.  
8.     printf("-----------------------------------------------\n");
9.  
10.     for(i = 1; i <= l/3; i++){
11.       for(j = 0; j <= l-3*i; j++){
12.         if(!strncmp(s+j, s+j+i, i) && !strncmp(s+j, s+j+i+i, i)){
13.           printf("%s\n%s\n%s\n---\n", s+j, s+j+i, s+j+j);
14.  //         getchar();
15.         }
16.       }
17.     }
18.  
19.   }

рисунок что выдается

Код (Text):

1. 001
2. -----------------------------------------------
3. 001001011
4. -----------------------------------------------
5. 001001011001001011001011011
6. -----------------------------------------------
7. 001001011001001011001011011001001011001001011001011011
8. 001001011001011011001011011
9. -----------------------------------------------
10. 001001011001001011001011011001001011001001011001011011
11. 001001011001011011001011011001001011001001011001011011
12. 001001011001001011001011011001001011001011011001011011
13. 001001011001001011001011011001001011001011011001011011
14. 001001011001011011001011011
15. -----------------------------------------------
16. 001001011001001011001011011001001011001001011001011011
17. 001001011001011011001011011001001011001001011001011011
18. 001001011001001011001011011001001011001011011001011011
19. 001001011001001011001011011001001011001011011001011011
20. 001001011001011011001011011001001011001001011001011011
21. 001001011001001011001011011001001011001011011001011011
22. 001001011001001011001011011001001011001001011001011011
23. 001001011001011011001011011001001011001001011001011011
24. 001001011001011011001011011001001011001011011001011011
25. 001001011001001011001011011001001011001001011001011011
26. 001001011001011011001011011001001011001001011001011011
27. 001001011001011011001011011001001011001011011001011011
28. 001001011001001011001011011001001011001011011001011011
29. 001001011001011011001011011
30. -----------------------------------------------
31.  
32. // дальнейшие итерации поскипаны

 

qqwe
Ну да, это и есть искомая последовательность, в ней нигде нет трёх одинаковых подряд идущих подстрок

 

Спасибо всем за ответы.
Мое решение, как оказалось, открыто фиг знает когда
http://ru.wikipedia.org/wiki/Последовательность_Морса-Туэ
Вот оно

Код (Text):

1. char*
2. generate_str(unsigned int length) {
3.     char *result;
4.  
5.     char *positive_substring;
6.     char *negative_substring;
7.  
8.     int substring;
9.     unsigned int offset;
10.     unsigned int to_copy;
11.  
12.     unsigned int current_length = length / 2 + (length & 1);
13.     unsigned int max_substrnig_length = 1;
14.  
15.     if (length == 0) return NULL;
16.  
17.     while (current_length >= max_substrnig_length) max_substrnig_length <<= 1;
18.  
19.     max_substrnig_length >>= 1;
20.  
21.     result = NULL;
22.  
23.     positive_substring = (char*)malloc(max_substrnig_length);
24.     if (positive_substring != NULL) {
25.         negative_substring = (char*)malloc(max_substrnig_length);
26.         if (negative_substring != NULL) {
27.             result = (char*)malloc(length + 1);
28.  
29.             if (result != NULL) {
30.                 // set termination 0 symbol
31.                 result[length] = 0;
32.  
33.                 // form substring
34.                 positive_substring[0] = '1';
35.                 negative_substring[0] = '0';
36.  
37.                 for (current_length = 1; current_length < max_substrnig_length; current_length <<= 1) {
38.                     memcpy(positive_substring + current_length, negative_substring, current_length);
39.                     memcpy(negative_substring + current_length, positive_substring, current_length);
40.                 }
41.  
42.                 for (current_length = 1, substring = 0, offset = 0; offset != length; ) {
43.                     to_copy = length - offset;
44.  
45.                     if (to_copy > current_length) {
46.                         to_copy = current_length;
47.                     }
48.  
49.                     if (substring) {
50.                         memcpy(result + offset, positive_substring, to_copy);
51.  
52.                         substring = 0;
53.                         current_length <<= 1;
54.                     } else {
55.                         memcpy(result + offset, negative_substring, to_copy);
56.                         substring = 1;
57.                     }
58.  
59.                     offset += to_copy;
60.                 }
61.             } else {
62.                 result = NULL;
63.             }
64.             free(negative_substring);
65.         } else {
66.             result = NULL;
67.         }
68.         free(positive_substring);
69.     } else {
70.         result = NULL;
71.     }
72.     return result;
73. }

Вот обсуждение на RSDN, где мне про это рассказали =)

Второй вариант основан на регулярных выражениях. Формируется строка из одинаковых символов, потом ищутся одинаковые подстроки и третья инвертируется.

 

Ation
по объему кода хуже уже моего. не говоря про блэк мирроровское. а маллоки и по скорости ударят