IPB
ЛогинПароль:

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Нужна помощь по дискретной математике в решении задач
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 2
Пол: Женский
Реальное имя: Алина

Репутация: -  0  +


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

Извините, что влезла в вашу тему "Дискретная математика, нужна помощь", я никогда раньше не была на форумах. 10.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(computersha @ 11.11.2007 18:26) *

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

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

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

Цитата(computersha @ 11.11.2007 18:26) *

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

Цитата(computersha @ 11.11.2007 18:26) *
2) Написать программу бессмертного глобального вируса, уничтожающего ленту, на которой галочки и пустые места стоят как угодно далеко и справа и слева.
3) Написать программу глобального бессмертного вируса, который уничтожает любую ленту.
Я что-то не улавливаю разницы в этих двух вопросах.. Вот, написал прогу, которая просто стирает все метки с ленты.
Код
1  R
2  ?  3, 1
3  0
4  L
5  ?  6, 4
6  0  1

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

Цитата(computersha @ 11.11.2007 18:26) *

4) Написать программу удвоения массива, изображающего число.
Как я понял, нужно умножить число на два. Вот программа.
Предполагаем, что перед началом каретка стоит на самой левой единице. Также преполагаем, что слева от числа есть достаточно свободного места.
Код
1  ?  3, 2  
2  Stop
3  0
4  L
5  ?  4, 6
6  1
7  R
8  ?  7, 9
9  1
10 R

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Большущее спасибо, Lapp!!! Даже не надеялась, что кто-то ответит! good.gif blum.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


В последнем коде (умножение на два) обнаружил ошибку на свежую голову.. Сорри!
В последней строке нужен переход обратно на первую:
Код
1  ?  3, 2  
2  Stop
3  0
4  L
5  ?  4, 6
6  1
7  R
8  ?  7, 9
9  1
10 R  1

Цитата(-computersha- @ 14.11.2007 15:19) *

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

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

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

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

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


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

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

Сообщение отредактировано: Atos -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:08
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name