Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 2 ] |
|
Автор | Сообщение | ||
---|---|---|---|
zero2hack |
|
||
Задача: построить МТ, высчитывающая сумму всех ПРОСТЫХ чисел, которые <=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) и т.д., пока исходное число не затрется символом # : **|||||||||||||||||#########_********** замечания, пожалуйста! к чему преподаватель может придраться ? =) |
|||
Вернуться к началу | |||
zero2hack |
|
||
PS мне вот не нравится пункт 4.
zero2hack писал(а): с помощью состояний легко..эмм..запомнить, что у нас сейчас обрабатывается цифра 3 а если это число, хотя бы, 999 , то сколько же это состояний необходимо... ? |
|||
Вернуться к началу | |||
[ Сообщений: 2 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Задачи на сочетание с моим решением
в форуме Теория вероятностей |
5 |
532 |
06 сен 2014, 15:30 |
|
Машина Тьюринга и машина Поста | 0 |
362 |
30 май 2016, 22:19 |
|
Машина Тьюринга | 1 |
481 |
14 апр 2014, 09:49 |
|
Машина Тьюринга | 0 |
267 |
01 окт 2015, 21:12 |
|
Машина Тьюринга | 3 |
366 |
26 май 2017, 09:08 |
|
Машина Тьюринга | 11 |
704 |
19 дек 2015, 02:02 |
|
Машина Тьюринга | 0 |
367 |
22 апр 2015, 22:05 |
|
Машина Тьюринга | 0 |
249 |
01 мар 2018, 15:43 |
|
Машина Тьюринга
в форуме Информатика и Компьютерные науки |
0 |
548 |
02 июн 2014, 18:51 |
|
Машина Тьюринга | 0 |
308 |
02 дек 2020, 18:26 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |