Нужна помощь по дискретной математике в решении задач Опции

[computersha]

<адрес удален> Помогите пожалуйста срочно решить задачи по дискретке!!
тема: "Программа машин Поста" (там шесть видов команд стандартных - i U j, i стоп и т.д.)
1) Подсчитать количество различных программ длины 2.
2) Написать программу бессмертного глобального вируса, уничтожающего ленту, на которой галочки и пустые места стоят как угодно далеко и справа и слева.
3) Написать программу глобального бессмертного вируса, который уничтожает любую ленту.
4) Написать программу удвоения массива, изображающего число.
Пожалуйста, это невероятно важно!! (сколько сможете) мыло <сколько можно говорить: публикация адресов запрещена! Lapp>

Извините, что влезла в вашу тему "Дискретная математика, нужна помощь", я никогда раньше не была на форумах.

[Lapp]

computersha, судя по не очень активной (мягко выражаясь) реакции публики, народ не очень знаком с этим материалом. Я бы на твоем месте привел чуть более подробные сведения..

И прочитай, наконец, Правила Форума.. (ссылка вверху).
Еще: рекомендую сменить название темы. На более конкретное. Например: "Дискретка. Программа машин Поста". И никогда не пиши слово "помощь" и родственные ему в заголовке..

[Lapp]

там шесть видов команд стандартных - i U j, i стоп и т.д.)

Считаю, что эти команды такие:

n L j - сместиться влево
n R j - сместиться вправо
n 0 j - стереть метку
n 1 j - поставить метку
n ? j1, j0 - условный переход
n Stop

n - это номер (адрес) строки.
j - адрес перехода. Если j не указано, то переход на следующую строку.

1) Подсчитать количество различных программ длины 2.

Вопрос: что считать различными программами? Если различными по коду, то тогда примерно такое рассуждение:

6*6 различных наборов команд
из них 5+5=10 содержат 1 Stop
и одна содержит два стопа
Все команды, кроме Stop, могут иметь адрес перехода 1 или 2. То есть их число увеличивается в два раза, за вычетом 11.
Команда ? имеет два адреса. То есть 5+5=10 команд нужно еще удвоить.
А программа, состоящая из двух ? еще раз удваивается.. значит, еще плюс 2.
Таким образом, всего:

6*6 + (6*6-10-1) + 10 + 2 = 6*6*2 + 1 = 73.
Ищите у меня ошибки в комбинаторике и арифметике .

2) Написать программу бессмертного глобального вируса, уничтожающего ленту, на которой галочки и пустые места стоят как угодно далеко и справа и слева.
3) Написать программу глобального бессмертного вируса, который уничтожает любую ленту.

Я что-то не улавливаю разницы в этих двух вопросах.. Вот, написал прогу, которая просто стирает все метки с ленты.

Код

1  R
2  ?  3, 1
3  0
4  L
5  ?  6, 4
6  0  1

Она действительно бессмертная, если лента бесконечная в обе стороны .

4) Написать программу удвоения массива, изображающего число.

Как я понял, нужно умножить число на два. Вот программа.
Предполагаем, что перед началом каретка стоит на самой левой единице. Также преполагаем, что слева от числа есть достаточно свободного места.

Код

1  ?  3, 2  
2  Stop
3  0
4  L
5  ?  4, 6
6  1
7  R
8  ?  7, 9
9  1
10 R

Спасибо за задачку! развлекся немного, узнал про машину Поста..

[-computersha-]

Большущее спасибо, Lapp!!! Даже не надеялась, что кто-то ответит!

[-computersha-]

Сорри, смайлик, показывающий язык случайно нажала!:)
P.S.: В принципе, все задания более менее понятны за исключением первого, где ты говоришь о комбинаторике, т.к. на лекциях о таком нам не говорили пока еще. И мне поэтому не ясно по какой формуле это вычисляется. И сам ход рассуждений тоже.
P.P.S.: Я в этом просто не очень разбираюсь.

[Lapp]

В последнем коде (умножение на два) обнаружил ошибку на свежую голову.. Сорри!
В последней строке нужен переход обратно на первую:

Код

1  ?  3, 2  
2  Stop
3  0
4  L
5  ?  4, 6
6  1
7  R
8  ?  7, 9
9  1
10 R  1

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

Хорошо, давай попробуем разобраться без лекций . Заодно проверим мои рассуждения..

Шесть команд - это шесть различных объектов, которые мы располагаем упорядоченно. Замечаешь сходство с цифрами? Каждая команда одна, но экземпляров ее в программе может быть несколько - как и одна цифра в число может входить несколько раз, верно? Продолжим аналогию с цифрами. Программа из двух команд - это как двузначное число. Сколько существует двузначных чисел? Сто (00, 01, ..., 09, 10, 11, ... 99 - предшествующий ноль тоже цифра!!), то есть 10*10, или 10^2. А если цифр было бы не 10, а 6? Да, тогда 6^2, то есть 36. Это объяснение первого шага.

И тут я вижу, что я ошибся.. (и куда только смотрят модераторы! ) Первая часть объяснения все равно годится, так что продолжаю объяснять дальше - и уже правильный вариант (не пытайся его связать со старым рещением).

Итак, если бы различных команд было действительно 6, возможных программ было бы 36. Но мы должны учитывать не только команды, но и их параметры (адреса перехода). У четырех команд по одному адресу, который может принимать значения 1 и 2 (номера строк в двустрочной программе). Значит, каждая из таких команд имеет 2 варианта, то есть всего различных объектов из них получается 6*2=12 (то есть как бы 12 цифр).

Идем дальше. Одна команда (?, условный переход) имеет аж два параметра, каждый из которых может быть 1 или 2 - всего 4 комбинации. То есть у этой команды 4 варианта. Значит, к нашим уже имеющимся 12 "цифрам" прибавляется еще 4 "цифры". Всего получается 16 различных объектов.

Осталась только одна команда: Stop. Она параметров не имеет, так что это как бы всего одна "цифра". Это делает нашу "систему счисления" 17-ричной .

А теперь мы готовы ответить на заданный вопрос. Но только сначала перефразируем его в ключе того, о чем мы говорили и чего добились . Теперь он звучит так:
Сколько существует различных двузначных (включая с предшествующим нулем, то есть однозначные тоже) чисел в семнадцатиричной системе счисления?
Надеюсь, ты ответишь сама .

[Lapp]

А откуда я взял 12? Пора к доктору..
Сначала рассматриваем четыре команды, а не шесть, как я почему-то решил..
Короче, так:

4 команды с одним адресом - всего 8 различных вариантов;
1 команда с двумя адресами - всего 4 различных варианта;
1 команда без адреса - один вариант.

Всего получается: 8 + 4 + 1 = 13.
Количество различных прграмм есть 13^2 = 169. И это мое последнее слово..

Computersha, ты не заходишь или заходишь гостем и не пишешь?

[Atos]

А вариант с отсутствием метки для перехода считать? (Если строго считать программы различными по записи кода, то, видимо, да)

Если j не указано, то переход на следующую строку.

Таким образом, имеем 4 команды с одним адресом - всего 12 различных вариантов;
А всего 12+4+1 =17
*посмотрев чуть выше* А, так вот значит откуда Lapp взял сначала 12

Сообщение отредактировано: Atos - 16.11.2007 10:34