Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Машина Тьюринга.поиск простого числа (с моим решением)
СообщениеДобавлено: 13 июн 2014, 16:29 
Не в сети
Начинающий
Зарегистрирован:
04 июн 2014, 05:24
Сообщений: 4
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здрасте =)

Задача: построить МТ, высчитывающая сумму всех ПРОСТЫХ чисел, которые <=X.

мне не нужно строить всю таблицу состояний и проч. Нужно объяснить преподу алгоритм, чтобы он сказал "работает".
и число представляется палочками, т.е. 2 - ||, 6 - |||||| и т.д.

Как вижу я:
допустим, X = 8, тогда на ленте будет так:
****||||||||****** , где * - это пустая ячейка

1) установим в начале числа символ #
*****#||||||||*************

2) 1 - непростое число, значит его можно опустим. 2 - простое, тогда сразу слева от числа напишем два.
и цифру, которую уже "обработали" закроем символом #
****||###||||||***********

3) 3 - тоже простое. но, с него уже начнем выполнение алгоритма по поиску простого числа.
установим в конце исходного числа служебный символ, например, "_"
****||###||||||_**********

4) с помощью состояний легко..эмм..запомнить, что у нас сейчас обрабатывается цифра 3, тогда перепишем три в правую часть
****||####|||||_|||*******

5) простое число, это то, у которого есть всего два делителя: один и само число.
тогда нам нужно делить обрабатываемое число на n, где n = 2,3,4,5.. пока не закончится число, т.е. на ленте не останется "палочек" от обрабатываемого числа.
после обрабатываемого числа установим ещё один служебный символ
****||####|||||_|||-******

как я делю: например, на 2. затираем первые две палочки числа символом, идем вправо, ставим |, возвращаемся к числу, затираем ещё 2 палочки и ставим в конец ещё одну | и т.д. и точно так же для остальных чисел.

т.е.
****||####|||||_**|-******
****||####|||||_**|-|*****
****||####|||||_***-|*****
по идее, каретка сейчас должна стоять на "|", но она передвинулась на служебный символ, а значит число закончилось, а значит на 2 данное число не делится (потому что остался остаток), что значит - у данного числа цифра "два" не делитель. делим на три:
****||####|||||_***-|*****
после того как каретка вернется, она попадет на служебный символ => значит число закончилось.

теперь тут два случая: это либо делитель обрабатываемого числа - само число; либо это 3й делитель, а значит число не простое. проверяется это кол-вом палочек в конце.
в нашем случае в конце одна палочка, значит число простое. стираем правую часть до служебного символа после исходного числа и записываем в левую часть ленты три палочки:
**|||||####|||||_**********

6) и т.д., пока исходное число не затрется символом # :
**|||||||||||||||||#########_**********

замечания, пожалуйста! к чему преподаватель может придраться ? =)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Машина Тьюринга.поиск простого числа (с моим решением)
СообщениеДобавлено: 13 июн 2014, 16:30 
Не в сети
Начинающий
Зарегистрирован:
04 июн 2014, 05:24
Сообщений: 4
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
PS мне вот не нравится пункт 4.
zero2hack писал(а):
с помощью состояний легко..эмм..запомнить, что у нас сейчас обрабатывается цифра 3

а если это число, хотя бы, 999 , то сколько же это состояний необходимо... ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задачи на сочетание с моим решением

в форуме Теория вероятностей

DeusEx

5

351

06 сен 2014, 15:30

Машина Тьюринга и машина Поста

в форуме Дискретная математика, Теория множеств и Логика

Mr_Whoopee

0

130

30 май 2016, 22:19

Машина Тьюринга

в форуме Информатика и Компьютерные науки

Anyaaaa

0

357

02 июн 2014, 18:51

Машина Тьюринга

в форуме Дискретная математика, Теория множеств и Логика

Danila16

2

376

01 июн 2011, 00:10

Машина Тьюринга

в форуме Дискретная математика, Теория множеств и Логика

Aecttann

0

202

22 апр 2015, 22:05

Машина Тьюринга

в форуме Дискретная математика, Теория множеств и Логика

KPI

0

269

05 май 2013, 21:39

Машина Тьюринга

в форуме Дискретная математика, Теория множеств и Логика

nadya2190

0

82

01 мар 2018, 15:43

Машина Тьюринга

в форуме Дискретная математика, Теория множеств и Логика

Sviter

11

387

19 дек 2015, 02:02

Машина Тьюринга

в форуме Дискретная математика, Теория множеств и Логика

Stasya7

0

137

01 окт 2015, 21:12

Машина тьюринга

в форуме Дискретная математика, Теория множеств и Логика

datgen

1

328

11 дек 2012, 23:00


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved