это быстро и бесплатно
Оформите заказ сейчас и получите скидку 100 руб.!
ID (номер) заказа
2600608
Ознакомительный фрагмент работы:
Комплексная лабораторная работа
Вариант №5
Задание 1. Доказательство примитивной рекурсивности функции и её вычисление.
Написать рекурсивную и не рекурсивную программу вычисления значения функции f, полученной оператором примитивной рекурсии R над функциями g и h. Доказать, что функция примитивно-рекурсивна.
g(x, y) = y+xh (x, y, z, t) = t(x+y)
По определению оператора примитивной рекурсии:
f(x,y,0)=y+xf(x,y,z+1)=f(x,y,z)(x+y)
Доказательство ПРФ: Функция f является ПРФ, т.к. построена из примитивно-рекурсивных функций с помощью оператора примитивной рекурсии. Функция сложения и произведения являются примитивно-рекурсивными.
Напишем рекурсивную и не рекурсивную функцию:
#include "pch.h"
#include <iostream>
#include <cstdio>
int f_rec(int x, int y, int z)
{
if (z == 0) return y + x;
return f_rec(x, y, z-1)*(x + y);
}
int f_norec(int x, int y, int z)
{
int f = x + y;
for (int i = 0; i < z; i++)
{
f = f * (x + y);
}
return f;
}
int main()
{
printf( "Rec: %x \n" , f_rec(1,2,3));
printf( "Norec: %x \n" , f_norec(1, 2, 3 ));
}
Результат выполнения:
Задание 2. Построить машину Тьюринга
На ленте записана цепочка, состоящая из 0 и 1. Если она начинается с 0, то стереть цепочку и вывести f, иначе все символы заменить на символ *.
Вход МТ: 011101
Выход МТ: f
Решение:
Состояния:
Q1 – ветвление по первому символу
Q2 – стираем все символы, в конце пишем f и выходим
Q3 – меняем 0 и 1 на *
Q4 – возвращаемся в начало цепочки символов и выходим
Использован эмулятор: http://kpolyakov.spb.ru/prog/turing.htm
Задание 3. Построить алгоритм Маркова, вычисляющий функцию. Значения аргументов задаются в унарном коде через разделитель.
Y(X,Y)=2*X/3+1
Результат выполнения: 11111
Проверка: x=6, y=2 Y(6,2)=2*6/3+1=12/3+1=4+1=5
Использован эмулятор: http://kpolyakov.spb.ru/prog/nma.htmЗадание 4. Оценка сложности алгоритма, построение эффективных алгоритмов
Написать рекурсивную и не рекурсивную программу для задачи по варианту. Оценить класс сложности алгоритмов.
Написать программу, которая проверяет, есть ли число X в упорядоченном массиве из N чисел.
Пример:
Массив [1, 5, 6, 15, 20, 56, 60, 71, 100]
Число X = 15
Функция поиска возвращает True.
Код программы:
#include "pch.h"
#include <iostream>
#include <cstdio>
// функция с алгоритмом двоичного поиска
bool Rec_poisk(int arr[], int left, int right, int key)
{
intmidd = (left + right) / 2;
if (key == arr[midd]) // если искомое равно элементу в массиве
{
return true; // возвращаем true
}
if (midd == right || midd == left) // если границы сомкнулись
{
return false;
}
if (key < arr[midd]) // если искомое меньше значения в ячейке
{
returnRec_poisk(arr, left, midd, key); // смещаем правую границу поиска, вызываем рекурсивную функцию поиска
}
else if (key > arr[midd]) // если искомое больше значения в ячейке
{
returnRec_poisk(arr, midd, right, key); // смещаем левую границу поиска, вызываем рекурсивн...
Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников 
Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.
Цены ниже, чем в агентствах и у конкурентов
Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит
Бесплатные доработки и консультации
Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки
Гарантируем возврат
Если работа вас не устроит – мы вернем 100% суммы заказа
Техподдержка 7 дней в неделю
Наши менеджеры всегда на связи и оперативно решат любую проблему
Строгий отбор экспертов
К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»
Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован 
Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн 
Требуется разобрать ст. 135 Налогового кодекса по составу напогового...
Решение задач, Налоговое право
Срок сдачи к 5 дек.
Школьный кабинет химии и его роль в химико-образовательном процессе
Курсовая, Методика преподавания химии
Срок сдачи к 26 дек.
Реферат по теме «общественное мнение как объект манипулятивного воздействий. интерпретация общественного мнения по п. бурдьё»
Реферат, Социология
Срок сдачи к 9 дек.
Выполнить курсовую работу. Образовательные стандарты и программы. Е-01220
Курсовая, Английский язык
Срок сдачи к 10 дек.
Изложение темы: экзистенциализм. основные идеи с. кьеркегора.
Реферат, Философия
Срок сдачи к 12 дек.
«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами
Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:
Принимаем к оплате
© 2011—2025 Всё сдал!
Заполните форму и узнайте цену на индивидуальную работу!
Мы ВКонтакте 
Трейлер о сайте