Версия для печати темы

Автор: computersha 11.11.2007 22:26

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

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

Автор: Lapp 12.11.2007 18:49

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

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

Автор: Lapp 14.11.2007 13:37

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

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

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

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

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.
Ищите у меня ошибки в комбинаторике и арифметике .

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

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

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

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

Автор: -computersha- 14.11.2007 19:13

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

Автор: -computersha- 14.11.2007 19:19

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

Автор: Lapp 15.11.2007 12:25

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

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

Шесть команд - это шесть различных объектов, которые мы располагаем упорядоченно. Замечаешь сходство с цифрами? Каждая команда одна, но экземпляров ее в программе может быть несколько - как и одна цифра в число может входить несколько раз, верно? Продолжим аналогию с цифрами. Программа из двух команд - это как двузначное число. Сколько существует двузначных чисел? Сто (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 16.11.2007 9:51

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

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

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

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

Автор: Atos 16.11.2007 14:33

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

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