1. В алфавите племени Мумба-Юмба есть только две буквы: "М" и "Ю".
2. Слова в племени Мумба-Юмба состоят строго из 11 букв.
3. Два слова в племени Мумба-Юмба считаются одинаковыми, если у них совпадает (находятся на одном месте и равны по значению) семь и/или более букв

Из какого максимального количества попарно различных слов может состоять словарный запас человека из племени Мумба-Юмба? Вывести список этих слов.

Здравствуйте, Mystic, Вы писали:

M>1. В алфавите племени Мумба-Юмба есть только две буквы: "М" и "Ю".
M>2. Слова в племени Мумба-Юмба состоят строго из 11 букв.
M>3. Два слова в племени Мумба-Юмба считаются одинаковыми, если у них совпадает (находятся на одном месте и равны по значению) семь и/или более букв

M>Из какого максимального количества попарно различных слов может состоять словарный запас человека из племени Мумба-Юмба? Вывести список этих слов.

Одно ! — МММММММММММ
Последовательно заменяя любую букву на Ю, мы каждый раз делаем тождественное преобразование.

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Mystic, Вы писали:

M>>1. В алфавите племени Мумба-Юмба есть только две буквы: "М" и "Ю".
M>>2. Слова в племени Мумба-Юмба состоят строго из 11 букв.
M>>3. Два слова в племени Мумба-Юмба считаются одинаковыми, если у них совпадает (находятся на одном месте и равны по значению) семь и/или более букв

M>>Из какого максимального количества попарно различных слов может состоять словарный запас человека из племени Мумба-Юмба? Вывести список этих слов.

P>Одно ! — МММММММММММ
P>Последовательно заменяя любую букву на Ю, мы каждый раз делаем тождественное преобразование.

Кто сказал, что отношение совпадения транзитивно? Вот множество:
{МММММММММММ, ЮЮЮЮЮЮЮЮЮЮЮ} — два попарно различных слова.

Здравствуйте, Mystic, Вы писали:

M>Из какого максимального количества попарно различных слов может состоять словарный запас человека из племени Мумба-Юмба? Вывести список этих слов.

где-то так:

MMMMMMMMMMM
MMMMMMЮЮЮЮЮ
MMMЮЮЮMMMЮЮ
MMMЮЮЮЮЮЮMM
MЮЮMMЮMMЮMЮ
MЮЮMMЮЮЮMЮM
MЮЮЮЮMMMЮЮM
MЮЮЮЮMЮЮMMЮ
ЮMЮMЮMMЮMЮM
ЮMЮMЮMЮMЮMЮ
ЮMЮЮMЮMЮMMЮ
ЮMЮЮMЮЮMЮЮM
ЮЮMMЮЮMЮЮЮЮ
ЮЮMMЮЮЮMMMM
ЮЮMЮMMMЮЮMM
ЮЮMЮMMЮMMЮЮ

размер словаря = 16

проверка:

#define num_letters      11
#define required_letters 7

a[1<<num_letters],n,i,k,l,t,s;

int main(void)
{
 for(i=n=0; i< (1<<num_letters); i++)
 {
  for(k=0;k<n;k++)
  {
   t=~(a[k]^i);
   for(l=s=0;l<num_letters;l++)
   {
    s+=t&1;
    t=t>>1;
   }
   if(s>=required_letters) break;
  }
  if(k==n)
  {
   a[n++]=i;
   for(l=num_letters-1;l>=0;l--)printf("%s%s",((i>>l)&1)?"Ю":"M",(l)?"":"\n");
  }
 }
 printf("размер словаря = %d\n",n);
 return 0;
}

правильно ?

Здравствуйте, Mystic, Вы писали:

<>

Задача о создании кода, исправляющего 11-7 ошибок в 11-битной посылке

Поскольку дискретную математику забыл, то используем брутфорс

  00000000000
  00000011111
  00011100011
  00011111100
  01100100101
  01100111010
  01111000110
  01111011001
  10101001010
  10101010101
  10110101001
  10110110110
  11001101111
  11001110000
  11010001100
  11010010011

где 0 в каждой позиции означает либо М, либо Ю, а 1 — наоборот.
То есть мы имеем 2^11 диалектов мумбы-юмбы, в каждом из которых — 16 слов.

Этот набор получен прямым перебором, с одной попытки.
Существуют и другие диалекты:
— если мы исключим любое слово, то можно будет добавить другие слова
— перестановки столбцов (в том числе — циклический сдвиг)

Для длины 12 и порога идентичности 7 — также получаем 16 слов в диалекте.
Для длины 13 и 14 — 8 слов.
Для длины 15 и 16 — 4 слова.
Для 17 и более — 2 слова: 000000_0...0, 000000_1...1

Здравствуйте, plague, Вы писали:

P>Здравствуйте, Mystic, Вы писали:

M>>Из какого максимального количества попарно различных слов может состоять словарный запас человека из племени Мумба-Юмба? Вывести список этих слов.

P>где-то так:
P>

P>MMMMMMMMMMM
P>MMMMMMЮЮЮЮЮ
P>MMMЮЮЮMMMЮЮ
P>MMMЮЮЮЮЮЮMM
P>MЮЮMMЮMMЮMЮ
P>MЮЮMMЮЮЮMЮM
P>MЮЮЮЮMMMЮЮM
P>MЮЮЮЮMЮЮMMЮ
P>ЮMЮMЮMMЮMЮM
P>ЮMЮMЮMЮMЮMЮ
P>ЮMЮЮMЮMЮMMЮ
P>ЮMЮЮMЮЮMЮЮM
P>ЮЮMMЮЮMЮЮЮЮ
P>ЮЮMMЮЮЮMMMM
P>ЮЮMЮMMMЮЮMM
P>ЮЮMЮMMЮMMЮЮ
P>

P>размер словаря = 16

P>проверка:

P>

P>#define num_letters      11
P>#define required_letters 7

P>a[1<<num_letters],n,i,k,l,t,s;

P>int main(void)
P>{
P> for(i=n=0; i< (1<<num_letters); i++)
P> {
P>  for(k=0;k<n;k++)
P>  {
P>   t=~(a[k]^i);
P>   for(l=s=0;l<num_letters;l++)
P>   {
P>    s+=t&1;
P>    t=t>>1;
P>   }
P>   if(s>=required_letters) break;
P>  }
P>  if(k==n)
P>  {
P>   a[n++]=i;
P>   for(l=num_letters-1;l>=0;l--)printf("%s%s",((i>>l)&1)?"Ю":"M",(l)?"":"\n");
P>  }
P> }
P> printf("размер словаря = %d\n",n);
P> return 0;
P>}
P>

P>правильно ?

Если перед началом перебора включить в массив найденных слов "ЮЮЮЮЮЮЮЮЮЮЮ", то вы найдете только 12 слов. Где гарантия, что при выбранном порядке перебора слов вы получите максимальный результат?

Здравствуйте, Mystic, Вы писали:


M>Если перед началом перебора включить в массив найденных слов "ЮЮЮЮЮЮЮЮЮЮЮ", то вы найдете только 12 слов. Где гарантия, что при выбранном порядке перебора слов вы получите максимальный результат?

если порядок не определен, тогда нельзя и определить содежание словарного запаса вышеуказанного племени...
т.е. он есть но вариантов "диалектов" (как сказал товарисч Кодт) может быть 2^11...

поэтому предположим что их словарь начинается с MMMMMMMMMMM (IMHO более вероятно чем ЮЮЮЮЮЮЮЮЮЮЮ)
и каждое последующее слово находится по правилам двоичной арифметики... тогда
нужно заучить всего 16 вышеописанных слов...

Здравствуйте, Кодт:

 1. MMMMMMMMMMM
 2. MMMUUUUUUUU
 3. MMUMMMMUUUU
 4. MMUMUUUMMMU
 5. MUMMMUUMUUM
 6. MUMUMMUUMMU
 7. MUUMUMUUMUM
 8. MUUUMUMMMUU
 9. MUUUUMMMUMM
10. UMMMUMUUUMM
11. UMMUMUMMUMU
12. UMUMUUMMUUM
13. UMUUMMUMMUM
14. UMUUUMMUMMU
15. UUMMUMMMMUU
16. UUMUMMMUUUM
17. UUMUUUUMMMM

17 > 16

Здравствуйте, plague, Вы писали:

P>Здравствуйте, Mystic, Вы писали:

P>нужно заучить всего 16 вышеописанных слов...

Вон у меня 17 получилось...

Здравствуйте, Mystic, Вы писали:

M>17 > 16

Именно этого я и боялся!
Просто меня заломало писать алгоритм перебора с откатами, а после того, как для бОльших слов стали получаться степени двойки, расслабился

Сейчас откаты прикручу, посмотрим, что выйдет.

Здравствуйте, Mystic, Вы писали:

M>1. В алфавите племени Мумба-Юмба есть только две буквы: "М" и "Ю".
M>2. Слова в племени Мумба-Юмба состоят строго из 11 букв.
M>3. Два слова в племени Мумба-Юмба считаются одинаковыми, если у них совпадает (находятся на одном месте и равны по значению) семь и/или более букв

M>Из какого максимального количества попарно различных слов может состоять словарный запас человека из племени Мумба-Юмба? Вывести список этих слов.


M — длина слова
N — кол-во совпадающих символов, достаточных для совпадения слов
M >= N

Максимальное количество попарно различных слов: 2^M / 2^(M — N) = 2^N.

При M = 11, N = 7 получим 2^7.

Интересный результат. Выходит, что объем словарного запаса не зависит от длинны слова .
Утешусь тем, что от нее зависит число различных словарей .

Здравствуйте, J.Quintana, Вы писали:

JQ>Здравствуйте, Mystic, Вы писали:

M>>1. В алфавите племени Мумба-Юмба есть только две буквы: "М" и "Ю".
M>>2. Слова в племени Мумба-Юмба состоят строго из 11 букв.
M>>3. Два слова в племени Мумба-Юмба считаются одинаковыми, если у них совпадает (находятся на одном месте и равны по значению) семь и/или более букв

M>>Из какого максимального количества попарно различных слов может состоять словарный запас человека из племени Мумба-Юмба? Вывести список этих слов.

JQ>
JQ>M — длина слова
JQ>N — кол-во совпадающих символов, достаточных для совпадения слов
JQ>M >= N

JQ>Максимальное количество попарно различных слов: 2^M / 2^(M — N) = 2^N.

JQ>При M = 11, N = 7 получим 2^7.

JQ>Интересный результат. Выходит, что объем словарного запаса не зависит от длинны слова .
JQ>Утешусь тем, что от нее зависит число различных словарей .

Мне трудно уследить за логикой . Не подскажите ли вы хотя-бы какой нибудь путь, дающий список из 2^7 = 64 попарно различных слов?

Здравствуйте, Mystic, Вы писали:


M>Мне трудно уследить за логикой . Не подскажите ли вы хотя-бы какой нибудь путь, дающий список из 2^7 = 64 попарно различных слов?

Кажется, я ошибся. Заметив, что первые 99 чисел меньше 100, решил, что вообще все числа меньше 100
Я проверил все варианты для M<4, а уже при M=4 все ломается.