Сколько ячеек содержит диапазон a1 z5

Saved searches

Use saved searches to filter your results more quickly

Cancel Create saved search

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Небольшие учебные проекты

beatsey/minorProjects

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Switch branches/tags
Branches Tags
Could not load branches
Nothing to show
Could not load tags
Nothing to show

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Cancel Create

Local
Codespaces

HTTPS GitHub CLI
Use Git or checkout with SVN using the web URL.
Work fast with our official CLI. Learn more about the CLI.

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

Latest commit message
Commit time

README.md

This repository contains programming tasks gathered from different programming language courses. Tasks are sorted by addition order.

Задача о рюкзаке (backpack.cpp)
Решить задачу о рюкзаке методом динамического программирования. Алгоритм должен быть инкапсулирован.

Формат входных данных

Данные подаются на стандартный поток ввода. Пустые строки игнорируются. Первая строка содержит натуральное число — максимальную массу предметов, которую выдержит рюкзак. Каждая последующая содержит два неотрицательных числа: массу предмета и его стоимость.

Первая строка содержит два числа: суммарную массу предметов и их суммарную стоимость. В последующих строках записаны номера предметов, которые были помещены в рюкзак, в порядке возрастания номера. Результат работы программы выводится в стандартный поток вывода. В любой непонятной ситуации результатом работы любой команды будет «error».

Входные данные	Результат работы
165 23 92 31 57 29 49 44 68 53 60 38 43 63 67 85 84 89 87 82 72	165 309 1 2 3 4 6

Сумасшедший богач (millionaire_dynamic.py, millionaire_fastest.py)

Один сумасшедший богач на старости лет впал в маразм и стал еще более сумасшедшим. Он решил отдать половину своих богатств тому, кто выиграет в математической игре. Правила игры: изначально каждый игрок начинает с нулевой суммой. Он может либо получить у богача 1 миллион сантиков, либо отдать ему 1 миллион сантиков, либо получить от богача ту же сумму, которая есть у него сейчас. Выигрывает тот, кто за минимальное количество действий наберет сумму, равную половине состояния богача. На беду других игроков, нашелся человек, который что-то слышал про жадные алгоритмы и двоичную систему счисления (возможно это вы).

Формат входных данных

В стандартном потоке записано единственное натуральное число — размер половины состояния богача (в миллионах).

Каждая строка выхода содержит ровно одну операцию (inc, dec или dbl) из кратчайшей последовательности действий для победы. Результат работы программы выводится в стандартный поток вывода.

Входные данные	Результат работы
23	inc dbl inc dbl dbl dbl dec

Автокоррекция (word_correction.py)

Реализуйте программу, которая предлагает варианты замены слова, в котором допущена одна ошибка. Эту задачу можно решить достаточно многими способами — на это ограничений нет, но код должен быть хорошего качества и читаемым. Регистр букв для программы коррекции не имеет значения (слова в словаре хранятся в нижнем регистре). Варианты ошибок — как в алгоритме Дамерау-Левенштейна: вставка лишнего символа, удаление символа, замена символа или транспозиция соседних символов.

Формат входных данных

Данные подаются на стандартный поток ввода. Пустые строки игнорируются. Первая строка содержит число N — количество слов в словаре. Последующие N строк содержат слова из словаря, по одному в строке. Остальные строки — слова, которые надо проверять.

Каждая строка выхода содержит предложение для исправления слов, в порядке их появления. Если слово не содержит ошибок, то выводится «%слово% — ok». Если слово содержит одну ошибку, то выводится «%слово% -> %слово_в_словаре%». Если вариантов несколько, то они разделяются запятой с пробелом. Если слово содержит более одной ошибки, то выводится «%слово% -?» Результат работы программы выводится в стандартный поток вывода.

Входные данные	Результат работы
8 some random words for testing your solutions far

Разложение на слагаемые (decompose.cpp, decompose2.cpp)

Дано натуральное число N. Рассмотрим его разбиение на различные натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.

Формат входных данных

Задано единственное число N. (N ≤ 40)

Необходимо вывести все разбиения числа N на различные натуральные слагаемые в обратном лексикографическом порядке.

Входные данные	Результат работы
5	5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1

Максимальный палиндром (maxpalindrome.py)

Палиндром — это строка, которая читается одинаково как справа налево, так и слева направо.

На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.

Формат входных данных

В единственной строке выходных данных выдайте искомый палиндром.

Входные данные	Результат работы
3 AAB	ABA
6 QAZQAZ	AQZZQA
6 ABCDEF	A

Сортировка матрицы (matrixSort.cpp)

Формат входных данных

Данные подаются на стандартный поток ввода. Первая строка содержит число N — размерность массива. Последующие N строк содержат N целых неотрицательных чисел, помещающихся в int32.

Вывод результирующей матрицы построчно через пробел.

Входные данные	Результат работы
3 1 3 2 7 8 9 6 8 9	1 2 6 3 7 8 8 9 9

Быстрая сортировка (quicksort.py)

Реализуйте эффективный алгоритм быстрой сортировки.

Формат входных данных

Ввод осуществляется со стандартного потока ввода. Первая и единственная строка всегда содержит входной массив. Все данные гарантированно валидны, проверять данные на корректность не нужно.

Результат работы — отсортированный массив. Результат работы программы выводится в стандартный поток вывода.

Входные данные	Результат работы
4 3 5 1 2	1 2 3 4 5

Бинарный поиск (binarysearch.py)

Реализуйте рекурсивно алгоритм бинарного поиска. Реализация алгоритма должна быть инкапуслирована, т.е. не зависеть от форматов входных/выходных данных и непосредственно ввода/вывода.

Формат входных данных

Ввод осуществляется со стандартного потока ввода. Первая строка всегда содержит отсортированный массив, в котором должен производится поиск. Остальные строки имеют формат search K, где K — некоторое число. Все данные гарантированно валидны, проверять данные на корректность не нужно.

Результат поиска — индекс числа в массиве. Если число в массиве отсутствует, то результатом будет -1. Результат работы программы выводится в стандартный поток вывода.

Входные данные	Результат работы
10 20 30 40 50 60 70 80 search 30 search 5	2 -1

Перестановки (permutations.py)

Реализуйте алгоритм генерации перестановок с началом в произвольной перестановке. Реализация алгоритма должна быть инкапсулирована и не зависеть от ввода/вывода.

Формат входных данных

На стандартном потоке ввода в первой и единственной строке задаётся перестановка — несколько чисел, разделенных пробелами.

На стандартный поток вывода выводятся построчно все последующие перестановки, включая входную, в лексикографическом порядке.

Входные данные	Результат работы
3 2 1 4	3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2

Самый частый элемент массива (mostcommon.py)

Реализуйте алгоритм поиска наиболее частого элемента массива, который работает за линейное время.

Формат входных данных

Результат поиска — самый частый элемент массива. Если таких чисел несколько, то наименьшее из них. Результат работы программы выводится в стандартный поток вывода.

Входные данные	Результат работы
2 5 1 3 5 4 2 3 5 4 3 4 5 4 5	5

Самый частый элемент массива 2 (mostcommon2.cpp)

Реализуйте алгоритм поиска наиболее частого элемента массива, который работает за линейное время.

Формат входных данных

На вход подается количество чисел n, после которого идет n чисел. Числа и их количество не превышают 1000000.

Результат поиска — самый частый элемент массива. Если таких чисел несколько, то наименьшее из них. Результат работы программы выводится в стандартный поток вывода. После числа с наибольшим количеством упоминаний вывести медианное число (в случае четного количества чисел, вывести минимальное).

Входные данные	Результат работы
2 4 5	4 4
4 8 8 8 8	8 8
8 9 7 8 3 1 9 7 7	7 7
7 4 8 5 7 8 4 9	4 7
3 6 9 1	1 6

Сферы в параллелепипедах (spheresinside.py)

В трёхмерном пространстве описан набор сфер и прямоугольных параллелепипедов. Требуется определить, находятся ли все сферы внутри параллелепипедов или нет.

Формат входных данных

В первой строке через пробел записаны 2 целых числа M и K — количество сфер и параллелепипедов соответственно. Оба числа не превышают 10. Далее идёт M строк по 4 числа в строке через пробел: целочисленные координаты X,Y,Z центров сфер (не превышают по модулю 1000) и целочисленный радиус (от 1 до 100). Далее — K строк, описывающих параллелепипеды, по 24 целых числа — координат вершин (не превышают по модулю 2000) в строке через пробел: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 X4 Y4 Z4 X5 Y5 Z5 X6 Y6 Z6 X7 Y7 Z7 X8 Y8 Z8.

Номера сфер по порядку ввода (нумерация начинается с 1), которые не находятся полностью в параллелепипедах.

Параллелепипеды не могут быть вложены друг в друга, между собой не пересекаются и не соприкасаются.

Входные данные	Результат работы
2 1 1 1 1 1 10 10 10 2 0 0 0 10 0 0 0 10 0 10 10 0 0 0 10 10 0 10 0 10 10 10 10 10	2

Последняя цифра (lastdigit.py)

Для заданного в некоторой системе счисления числа N определить последнюю цифру числа N^k.

Формат входных данных

В строке через пробел записаны число C — основание системы счисления от 2 до 20, целое число N (не более 5 разрядов, в C-й системе счисления) и положительная целая степень k в десятичной системе счисления, не превышающая 100.

Последняя цифра N^k в C-й системе счисления.

Входные данные	Результат работы
2 111 3	1
16 AE 2	4

Минимальное число контейнеров (mincontainers.py)

Мама Малыша готовится к приёму гостей, ей срочно нужно приготовить очень много тефтелей. Готовые тефтели она решила раскладывать по кастрюлям и позвала Малыша помочь принести нужные кастрюли. Помогите Малышу определить минимальное количество кастрюль, которые потребуются.

Формат входных данных

В первой строке через пробел записаны целые числа N и M — минимальный общий объём кастрюль, который понадобится, и количество свободных кастрюль на кухне. Далее M строк, в каждой записано по одному вещественному числу — объём соответствующей кастрюли.

Номера кастрюль, которые надо принести Малышу, записанные по одному в строке, в порядке возрастания. Номера считать по порядку входных данных, начиная с единицы. Если подходит несколько возможных вариантов, то Малышу требуется принести самые большие кастрюли. В случае, если подходящих кастрюль нет, вывести слово NO.

Входные данные	Результат работы
5 4 1 3.5 2 4	2 4
3 5 1 0.8 1.2 2 1.5	4 5

Мороженое и холодильник (refrigerator.java)

Харитон любит мороженое. В своём любимом магазине мороженого Харитон каждому сорту мороженого присвоил рейтинг. Чем больше этот рейтинг, тем вкуснее мороженое с точки зрения Харитона. Каждый день в киоске некоторое мороженое назначаются мороженым дня и продают со скидкой. Харитон любит экономить, поэтому он покупает только мороженое дня или не покупает мороженого вообще. Если рейтинг мороженого дня не меньше, чем рейтинг самого вкусного мороженого, хранящегося в холодильнике Харитона, то он купит две порции этого мороженого. Одну съест сразу, а вторую положит в холодильник. Иначе Харитон не будет ничего покупать и съест самое вкусное мороженое из своего холодильника.

Требуется по заданной информации о мороженых дня за n дней определить, какое максимальное количество порций мороженого одновременно оказывалось в холодильнике Харитона на протяжении этих n дней. А также какое мороженое Харитон покупал чаще всего.

Формат входных данных

В каждой из следующих n строк содержится информация о мороженом дня в соответствующий день: наименование сорта мороженного s_j и через пробел его рейтинг r_j (0<=r_j<=1000000).

Наименование сорта мороженого s_j — непустая строка из строчных латинских букв, цифр и нижнего подчёркивания, начинающаяся с буквы и имеющая длину не более 30 символов.

Гарантируется, что для фиксированного наименования мороженого рейтинг сорта мороженого постоянный.

В первой строке выведите целое число m — максимальное число одновременно лежавших в холодильнике порций мороженого.

Во второй строке вывести целые числа v и k — максимальное количество раз, которое Харитон покупал мороженое одного и того же сорта, и количество сортов мороженого, которые Харитон покупал чаще всего.

Далее выведите k строк, в каждой строке укажите по одному наименованию сорта мороженого, которое Харитон покупал чаще всего. Наимеинования сортов выводите в лексикографическом (алфавитном) порядке.

Входные данные	Результат работы
14 strawberry 3 vanilla 5 blackberry 4 banana 3 strawberry 3 watermelon 2 lemon 6 vanilla 5 blackberry 4 vanilla2 4 strawberry 3 vanilla2 4 vanilla 5 strawberry 3	5 2 3 strawberry vanilla vanilla2

Мороженое и холодильник 2 (refrigerator2.java)

Харитон решил изменить стратегию. Он не станет покупать мороженое в двух случаях:

Если в холодильнике имеется мороженое, которое лежит там уже d дней. В этом случае Харитон съест в этот день именно это мороженое.
Если никакое мороженок не лежит в холодильнике d дней, но рейтинг мороженого дня меньше, чем рейтинг самого вкусного мороженого, которое есть у Харитона в холодильнике. В этом случае Харитон съест в этот день самое вкусное мороженое из своего холодильника. Если в холодильнике несколько порций мороженого с одинаковым рейтингом, то он съест то, которое купил последним.

Если рейтинг мороженого дня не меньше, чем рейтинг самого вкусного мороженого, хранящегося в холодильнике Харитона, и, кроме того, никакое мороженое в холодильнике не лежит уже d дней, Харитон купит две порции мороженого дня. Одну съест, а вторую положит в холодильник.

Требуется по заданной информации о мороженых дня за n дней определить:

Сколько раз Харитон отказывался от покупки мороженого, рейтинг которого был выше, чем хотя бы у одного мороженого, имевшегося в тот момент в холодильнике.
Максимальное количество дней, которое порция мороженого провела в холодильнике Харитона, и количество таких порций.
Количество сортов мороженого, порции которого пробыли в холодильнике максимальное количество дней, и вывести список этих сортов в лексикографическом (алфавитном) порядке.

Формат входных данных

В каждой из следующих n строке содержится информация о мороженом дня в соответствующий день: наименование сорта мороженого s_j и через пробел его рейтинг r_j с точки зрения Харитона (j=1,2. n), (0<=r_j<=1000000)

Гарантируется, что для фиксированного наименования мороженого рейтинг сорта мороженого постоянный.

В первой строке выведите целое число z — количество раз, которое Харитон отказывался от покупки мороженого, рейтинг которого был выше, чем хотя бы у одного мороженого, имевшегося в тот момент в холодильнике.

Во второй строке выведите целые числа p и q — максимальное количество дней, которое порция мороженого провела в холодильнике Харитона, и количество таких порций.

В третьей строке выведите целое число w — количество сортов, порции которых провели в холодильнике Харитона максимальное количество дней.

Далее выведите w строк — названия этих сортов в лексикографическом (алфавитном) порядке.

Входные данные	Результат работы
14 3 strawberry 3 vanilla 5 blackberry 4 banana 3 strawberry 3 watermelon 2 lemon 6 vanilla 5 blackberry 4 vanilla2 4 strawberry 3 vanilla2 4 vanilla 5 strawberry 3	1 3 2 2 blackberry strawberry
8 4 blackberry 4 strawberry 3 vanilla 5 watermelon 2 banana 3 lemon 6 strawberry 3 vanilla 5	0 3 1 1 banana
1 1 blackberry 4	0 0 1 1 blackberry

Контрольная работа (controlwork.java)

Фалалель готовится к контрольной работе.

По просьбе Фалалеля его товарищ подобрал ему n задач, для каждой из которых указал уровень сложности d_j. По мнению товарища, Фалалей в начальный момент времени способен решать задачи с уровнем сложности, не превосходящим величину f. Для краткости будем говорить, что в начальный момент времени Фалалей обладает навыком f.

Фалалей решает задачи в порядке нумерации.

Возможны следующие исходы:

Фалалей решает задачу и уровень сложности больше текущего навыка f. В этом случае Фалалель испытывает положительные эмоции, а его навык выростает до уровня сложности задачи.
Фалалей решает задачу и уровень сложности не больше текущего навыка f. В этом случае Фалалелю становится скучно.
Фалалей не решает задачу. В этом случае Фалалей испытывает отрицательные эмоции. Если при этом сложность задачи не больше навыка Фалалея, то его навык уменьшается на единицу.

Ваша задача — по представленным номерам задач определить:

минимальный и максимальный уровни сложности задачи, которую Фалалей не решил к моменту, когда он завершил работу над задачей с представленным номером;
каких эмоций Фалалей испытал больше к моменту, когда он завершил работу над задачей с заданным номером.

Формат входных данных

Во второй строке содержится n целых чисел d_1, d_2, . d_n (1

В третьей строке содержится последовательность из n символов (без пробелов) A и R. Если на i-й позиции находится символ A, то Фалалей решил соответствующую задачу. Если R, то не решил.

В четвёртой строке содержится m целых чисел p_1, p_2, . p_m — номера задач, для которых нужно ответить на вопрос задачи.

Выведите m строк. Каждая строка должна содержать два целых числа и обозначение эмоции, которую Фалалей испытывал наиболее часто к этому моменту. Числа и обозначение эмоции должны быть разделены пробелами.

Первое и второе числа — это минимальный и максимальный уровень сложности задачи, которую Фалалей не решил к моменту завершения работы над задачей с номером p_i. Если к этому моменту Фалалель решил все предыдущие задачи, выведите -1.

Обозначение эмоции — это последовательность символов «:-)», «:-(» для положительных и отрицательных эмоций, «:-|» для скуки.

Если Фалалей к моменту завершения работы над задачей с номером p_i испытал одинаковое (максимальное) количество различных эмоций, следует выводить обозначение той эмоции, которую он испытал позже.

Входные данные	Результат работы
15 10 8 7 5 7 8 14 6 11 7 11 12 3 11 14 12 14 ARRAAARAAARRAAA 7 3 14 13 9 15 8 5 3 12	5 11 🙁 5 7 🙁 3 11 🙂 3 11 🙂 5 11 🙂 3 11 😐 5 11 😐 5 7 🙂 5 7 🙁 3 11 🙁
3 4 5 7 3 8 AAA 3 2 1 3	-1 -1 🙂 -1 -1 😐 -1 -1 🙂 -1 -1 🙂

Подготовка (preparations.java)

Харитон расспросил однокурсников, уже сдавших экзамен, какие дополнительные вопросы задавал им преподаватель.

Всего Харитон расспросил n однокурсников, и каждый из них перечислил Харитону заданные ему дополнительные вопросы. Для каждого дополнительного вопроса Харитон записывал тему, к которой этот вопрос относится.

Требуется выяснить, по каким темам было задано больше всего дополнительных вопросов.

Формат входных данных

В первой строке выведите целые числа p и q — количество тем, по которым было задано максимальное количество дополнительных вопросов, и количество этих вопросов.

Входные данные	Результат работы
6 3 10 5 14 2 14 12 5 8 13 5 12 3 4 10 13 1 4 0 3 2 2 8	7 2

Регистрация (registration.py)

Предварительно создайте текстовый файл (accounts.txt), в котором структурирована информация вида: login -> password (не менее 5 пар). При этом на каждой строчке содержатся уникальные логины, а пароли могут повторяться. Создайте функцию регистрации нового пользователя, которая будет предлагать пользователю ввести логин и пароль до тех пор, пока не будет введён уникальный логин, и пароль не будет соответствовать требованиям:

Наличие букв в разных регистрах
Наличие цифры
Наличие спецсимвола (@. $,#)

Корректная комбинация должна быть добавлена в текстовый файл accounts.txt.

Содержимое accounts.txt на начало работы:

login1 -> password user -> friendly summer -> qwerty qbq812309 -> gdhjasdgj nagibator228 -> systemCall1238sj newUser -> Hey2201#

Две кучи (two_heaps.cpp)

Формат входных данных

Минимальная неотрицательная разница в весе куч.

Входные данные	Результат работы
5 8 9 6 9 8	4
6 14 2 12 9 9 8	2

Польский калькулятор (calculator_polsk_prefix.cpp)

Для вычисления арифметических выражений на практике удобно использовать польскую запись. В ней операции записывают перед операндами, а не между как мы привыкли. Таким образом
— 2 1 = (2 — 1)
и
— * / 15 — 7 + 1 1 3 + 2 + 1 1 = 15 / (7 — (1 + 1)) * 3 — (2 + (1 + 1))

Вам необходимо написать калькулятор, который вычисляет значение арифметического выражения в префиксной записи. Размеры операндов и результаты операций не превосходят 1000.

Входные данные	Результат работы
+ 1 2	3
— * / 15 — 7 + 1 1 3 + 2 + 1 1	5

Польский калькулятор (обратный) (calculator_polsk_reverse.py)

Задание связано с обратной польской нотацией. Она используется для парсинга арифметических выражений. Ещё её иногда называют постфиксной нотацией. В постфиксной нотации операнды расположены перед знаками операций.

Формат входных данных

В единственной строке дано выражение, записанное в обратной польской нотации. Числа и арифметические операции записаны через пробел. На вход могут подаваться операции: +, -, *, / и числа, по модулю не превосходящие 10000. Операция / является математическим целочисленным делением с округлением вниз. Гарантируется, что значение промежуточных выражений в тестовых данных по модулю не больше 50000.

Выведите единственное число — значение выражения.

Входные данные	Результат работы
3 4 +	7
12 5 /	2
-1 3 /	-1
10 2 4 * —	2
2 1 + 3 *	9
7 2 + 4 * 2 +	38

Торговый автомат (h11_authomata.cpp)

Одна фирма обслуживает автоматы по продаже чая и кофе. Стоимость стакана чая и кофе в автомате равна пяти рублям. Автомат принимает монеты по 5 и 10 рублей, а также купюры в 10, 50 и 100 рублей. Когда покупателю надо выдавать сдачу (т.е. когда пассажир бросил в автомат десятирублёвую монету или 10-, 50- или 100- рублёвую купюру), автомат выдаёт сдачу пятирублёвыми монетами; если же покупатель бросил в автомат пятирублёвую монету, то автомат её сохраняет и может использовать для сдачи следующим покупателям. Ясно, что, чтобы обеспечить возможность выдачи сдачи всем покупателям, может потребоваться изначально загрузить в автомат некоторое количество пятирублёвых монет.

Сейчас автоматы проходят испытания с целью определить минимальное количество монет, которые надо загрузить в автомат перед началом дня.Вам дан протокол одного из таких испытаний: известен порядок, в котором покупатели оплачивали свои покупки различными монетами и купюрами.Определите, какое минимальное количество пятирублёвых монет должно было изначально находиться в автомате, чтобы всем покупателям хватило сдачи.

Формат входных данных

Выведите одно число — минимальное количество пятирублёвых монет, которые надо было загрузить в автомат изначально, чтобы всем покупателям хватило сдачи.

Входные данные	Результат работы
3 10 5 100	19
3 5 5 10	0

Обратное число по модулю (h12_reciprocal.cpp)

Известно, что команда деления целых чисел на современных компьютерах исполняется неприлично долго. Оптимизирующие компиляторы во многих случаях заменяют операцию деления на константу группой операций, в которых имеется умножение на другую константу.

Для этого компилятору, в числе других действий, требуется найти такое число q для заданного делителя p, что q * p = 1 по известному модулю m.

Известно также, что m — простое число, и что для заданных p и m ответ существует.

Формат входных данных

Входные данные	Результат работы
5 7	3
199212331 4010101141	525555399

Последовательность строк (h13_sequence.cpp)

Последовательность строк формируется следующим образом:

Первая строка состоит из цифры 1.

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

Вот несколько первых строк:
1
211
3211112
432111122111123
5432111122111123321111221111234

Заметьте, что десятая строка начнётся с символов 10, одиннадцатая — с символов 11 и так далее.

Ваша задача заключается в том, чтобы по заданному номеру строки и номеру её элемента вывести символ, стоящий в ней на указанном месте.

Формат входных данных

Нумерация строк и символов в строках начинается с единицы.

M символов, не разделённых пробелами, соответствующие позициям Pi.

Входные данные	Результат работы
5 5 2 4 6 8 10	42112

Перестановки (h14_permutation.cpp)

Как известно, из множества из N различных предметов можно сделать N! различных перестановок.

Если предметы можно сравнивать между собой, то перестановки можно перенумеровать в лексикографическом порядке. Например, перестановки множества будут идти в следующем порядке: , , , , , .

Таким образом, все перестановки множества различных элементов можно пронумеровать от 1 до N!.

В нашей задаче мы будем переставлять элементы из множества натуральных чисел от 1 до N.

Формат входных данных

На вход программы подаётся два числа — количество предметов в перестановке 2

Вывести через пробел элементы перестановки, имеющей номер M.

Входные данные	Результат работы
5 120	5 4 3 2 1
10 73238	1 3 9 6 8 4 7 2 10 5

Чуждые элементы (h15_alliens.cpp)

Формат входных данных

Входные данные	Результат работы
10 4 8 1 2 4 2 1 7 62 3	3

Камера хранения (h21_storeroom.cpp)

На железнодорожном вокзале столицы Бурляндии решили установить новую автоматическую камеру хранения. Для этого потребовалось узнать, сколько ячеек одновременно занято хранящимся багажом. Было установлено несколько датчиков использования старой камеры хранения, фиксировавших момент прихода пассажира и занятия им ячейки, а так же момент ухода пассажира и момент освобождения им ячейки. Протокол прихода и ухода пассажиров за одни сутки приведён далее. Ячейка не освобождается мгновенно, поэтому если в какое-то время один пассажир ушёл и в это же время пришёл другой пассажир, требуется две ячейки. Определите максимальное количество одновременно занятых ячеек, наблюдаемое в течении суток.

Камера открыта круглосуточно. Времена прихода и ухода пассажиров находятся в пределах одних суток. В 00:00 камера хранения пуста.

Формат входных данных

N (количество пассажиров, 1 <=N<=1000000).
HA1:MA1 HD1:MD1
.
HAN:MAN HDN:MDN

Входные данные	Результат работы
5 02:18 11:54 03:18 04:16 00:26 20:41 17:19 20:48 08:42 23:45	3
10 17:59 22:58 12:25 16:06 09:05 18:39 08:34 23:23 15:59 22:53 15:55 21:20 18:05 22:08 03:48 22:23 12:50 14:41 05:46 10:41	7

Башня (h22_circus.cpp)

В Бурляндск приехал цирк. Одним из привлекающих внимание горожан номеров всегда было построение как можно более высокой башни из группы циркачей.

В построенной башне один циркач стоит на земле, второй — на его плечах, третий — на плечах второго, и так далее. У циркача под номером i вес равен wi, а сила — fi. Сила — способность удерживать на себе заданный вес. Точно известно, что более тяжёлый циркач является и более сильным. Впрочем, циркачи с одинаковым весом могут иметь различную силу.

Формат входных данных

Каждая их последующих строк содержит по два числа — вес и силу участника команды. Все числа — положительные целые, меньшие 10000.

Максимальная высота башни, которую может построить эта команда.

Входные данные	Результат работы
4 1 9 5 13 13 15 16 20	4

Разрезание блинов (h23_cakes.cpp)

На очень большом столе разложено много абсолютно круглых блинов, некоторые из которых могут частично или полностью налегать друг на друга. Абсолютно прямым ножом проводится луч из первой точки по направлению ко второй. Требуется определить, какие из блинов будут задеты разрезом. Касания НЕ учитываются.

Формат входных данных

В первой строке — координаты двух точек на плоскости, которые определяют луч разреза. Во второй строке — количество блинов 1

Радиус — строго положительное целое число.

Номера разрезанных блинов в порядке возрастания. Нумерация блинов начинается с 1.

Входные данные	Результат работы
0 0 0 1 5 -1 -1 1 -2 -2 1 -3 -3 4 1 2 4 3 1 1	4
0 0 0 1 2 3 0 3 3 0 1

Позитивизм (h24_positivism.cpp)

У Иеремии родители — философы. Он часто слышит их разговоры, но мало что в них понимает. Сам Иеремия учится в информатическом классе физматшколы, и философия его пока не интересует. Недавно он услышал новое для себя слово: позитивизм. Он постеснялся спросить своих родителей, что это слово обозначает, и узнал в Википедии, что-то про эмпирические и философские исследования. Так как слово ему понравилось, он загорелся идеей провести какие-то исследования, а так, как недавно в школе они проходили матрицы, вопрос, что же будет объектом исследования, оказался для него очевидным. Он называет позитивной матрицей такую двумерную матрицу, у которой сумма элементов каждой из строк неотрицательна и сумма элементов каждого из столбцов тоже неотрицательна.

Он поставил перед собой задачу установить, каждую ли из матриц можно сделать позитивной, имея ровно две операции: смену всех знаков на противоположные либо для всех элементов строки, либо для всех элементов столбца. Операции первого вида он записывал, как l y, где y — номер инвертируемой строки, а второго — как c x, где x — номер инвертируемого столбца. И столбцы и строки нумеруются с нуля. Он проделал серию экспериментов и убедился, что если решение существует, то оно может быть не единственным.

Ваша задача состоит в том, чтобы помочь Иеремии, написав программу, которая либо сообщит, что не существует такой последовательности операций, чтобы матрица стала позитивной, либо выдаст любую последовательность операций, приводящую в конечном итоге к позитивной матрице.

Формат входных данных

В первой строке — числа N и M — количество строк и столбцов соответственно. Эти числа не превосходят 100. В каждой из следующих N строк содержатся значения элементов каждой строки. Ни одно из этих чисел по абсолютной величине не превосходит 10e6.

Если матрицу можно сделать позитивной, то решение должно состоять из произвольного числа строк указанного выше вида. Если матрица позитивна с самого начала, программа ничего не должна выводить. Если её позитивной сделать нельзя, нужно вывести одно слово: Impossible.

Входные данные	Результат работы
3 3 1 -10 8 2 1 3 1 7 4	l 0 c 2
2 2 1 2 3 4

Количество подстрок (h25_strings.cpp)

Назовём подстрокой любой набор подряд идущих символов строки. Например, в строке aba можно найти три подстроки длины один: a, b, a, две подстроки длины два: ab и ba, а также одну подстроку длины 3: aba. Две подстроки здесь совпадают, поэтому различных подстрок здесь 5. Нужно для заданной строки, состоящей из строчных букв латинского алфавита, определить, сколько в ней можно найти различных подстрок.

Формат входных данных

Строка, длиной от 5 до 10000 символов.

Количество различных подстрок в данной строке.

Входные данные	Результат работы
abracadabra	54

Генератор Гауссовых слов (gausswordgenerator.py)

Гауссово слово – это слово, в котором все буквы встречаются ровно два раза. При этом вначале идет буква a, первая непарная ей – b, следующая непарная им – с, и так далее. Требуется написать программу, которая выведет все Гауссовы слова из букв от «a» вплоть до введённой латинской буквы.

Формат входных данных

Одна буква латинского алфавита.

Все возможные Гауссовы слова из заданного диапазона букв по одному слову на строчке.

Входные данные	Результат работы
a	aa
c	aabbcc aabcbc aabccb ababcc abbacc abbcac abbcca abacbc abcabc abcbac abcbca abaccb abcacb abccab abccba

Накачка и сброс (pumpndump.py)

Pump’n’dump (накачка и сброс) — это схема относительно честного отъема денег. Она выглядит следуюшим образом. Несколько крупных игроков или много мелких договариваются вместе купить малоизвестную бумагу с низкой ценой и объёмом торгов. Это приводит к мгновенному взлету цены (pump), далее приходят неопытные игроки в надежде успеть заработать на таком росте. В этот момент организаторы схемы начнают все продавать (dump). Весь процесс занимает от нескольких минут до нескольких часов.

Ваша задача найти самый сильный pump’n’dump бумаги на заданном промежутке времени. Для этого для каждого дня определим число pnd, равное отношению максимальной цены бумаги в данный день к максимуму из цен открытия и закрытия в тот же день. Нужно найти день, когда pnd был максимален и его величину.

Формат входных данных

На вход подаётся много-много строк в формате дата цена. Самая первая цена за день — цена открытия. Самая последняя цена за день — цена закрытия. Гарантируется, что цены идут в хронологическом порядке.

Выведите самое большое число pnd

Входные данные	Результат работы
2020-07-19 18:00:00 20 2020-07-19 19:00:00 10 2020-07-19 20:00:00 30 2020-07-19 21:00:00 40	1
2020-07-19 21:00:00 20 2020-07-19 22:00:00 10 2020-07-19 23:00:00 40 2020-07-20 00:00:00 50 2020-07-20 01:00:00 10 2020-07-20 02:00:00 20 2020-07-20 03:00:00 15 2020-07-20 04:00:00 60 2020-07-20 05:00:00 10	1.2
2021-03-01 09:30:00 690 2021-03-01 10:30:00 703 2021-03-01 11:30:00 711 2021-03-01 12:30:00 714 2021-03-01 13:30:00 709 2021-03-01 14:30:00 710 2021-03-01 15:30:00 712 2021-03-02 09:30:00 719 2021-03-02 10:30:00 709 2021-03-02 11:30:00 705 2021-03-02 12:30:00 704 2021-03-02 13:30:00 699 2021-03-02 14:30:00 691 2021-03-02 15:30:00 686 2021-03-03 09:30:00 690 2021-03-03 10:30:00 679 2021-03-03 11:30:00 693 2021-03-03 12:30:00 680 2021-03-03 13:30:00 680 2021-03-03 14:30:00 666 2021-03-03 15:30:00 657	1.0043478260869565

Кубики (cubes.py)

Аня и Боря любят играть в разноцветные кубики, причем у каждого из них свой набор и в каждом наборе все кубики различны по цвету. Однажды дети заинтересовались, сколько существуют цветов таких, что кубики каждого цвета присутствуют в обоих наборах. Для этого они занумеровали все цвета случайными числами. На этом их энтузиазм иссяк, поэтому вам предлагается помочь им в оставшейся части. Номер любого цвета — это целое число в пределах от 0 до 109.

Формат входных данных

В первой строке входного файла записаны числа N и M — количество кубиков у Ани и Бори соответственно. В следующих N строках заданы номера цветов кубиков Ани. В последних M строках номера цветов кубиков Бори.

Выведите сначала количество, а затем отсортированные по возрастанию номера цветов таких, что кубики каждого цвета есть в обоих наборах, затем количество и отсортированные по возрастанию номера остальных цветов у Ани, потом количество и отсортированные по возрастанию номера остальных цветов у Бори.

Входные данные	Результат работы
4 3 0 1 10 9 1 3 0	2 0 1 2 9 10 1 3
2 2 1 2 2 3	1 2 1 1 1 3
0 0	0 0 0

Продажи (sales.py)

Дана база данных о продажах некоторого интернет-магазина. Каждая строка входного файла представляет собой запись вида Покупатель товар количество, где Покупатель — имя покупателя (строка без пробелов), товар — название товара (строка без пробелов), количество — количество приобретенных единиц товара. Создайте список всех покупателей, а для каждого покупателя подсчитайте количество приобретенных им единиц каждого вида товаров.

Формат входных данных

Вводятся сведения о покупках в указанном формате.

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

Входные данные	Результат работы
Ivanov paper 10 Petrov pens 5 Ivanov marker 3 Ivanov paper 7 Petrov envelope 20 Ivanov envelope 5	Ivanov: envelope 5 marker 3 paper 17 Petrov: envelope 20 pens 5
Ivanov aaa 1 Petrov aaa 2 Sidorov aaa 3 Ivanov aaa 6 Petrov aaa 7 Sidorov aaa 8 Ivanov bbb 3 Petrov bbb 7 Sidorov aaa 345 Ivanov ccc 45 Petrov ddd 34 Ziborov eee 234 Ivanov aaa 45	Ivanov: aaa 52 bbb 3 ccc 45 Petrov: aaa 9 bbb 7 ddd 34 Sidorov: aaa 356 Ziborov: eee 234

Слишком серьёзная задача (tooserious.py)

Эконом прослушал курс по финансовым рынкам. Он показался ему слишком практическим. Теперь надо как-то применять знания на практике. Поэтому все скачали себе Пенькоф-Инвестиции и начали торговать. Это не является инвестиционной рекомендацией. Давайте немного помечтаем и представим, что нам стало так везти, что для любой ценной бумаги в любой день мы умудряемся купить её по минимальной цене и в тот же день продать по максимальной. Страшно подумать, как можно было бы приумножить свой капитал всего лишь за несколько дней.

Ваша задача — узнать во сколько раз вырастут ваши вложения при такой удаче. Все заработанные деньги вы реинвестируете. Короткие позиции запрещены. Продавать раньше, чем покупать запрещено. У вас нет премиум-аккаунта.

Формат входных данных

На вход подаётся много-много строк в формате дата цена. Гарантируетcя, что цена изменяется от 0 до 106.

Выведите свою максимальную доходность. В процентах. Сумма, которую вы изначально вкладываете в бумагу — неважна.

Комментарий к примерам

Есть 100 рублей. Мы купили бумаги по 10 и продали по 40. В итоге у нас 400 рублей. Итоговая доходность 100*(40 — 10)/10 = 300%
Есть 100 рублей. Мы купили бумаги по 20 и продали по 40. Ко второму дню у нас есть 200 рублей. Все полученные деньги мы реинвестировали. Купили за 20, продали за 60. В итоге у нас 600 рублей. Итоговая доходность 500%.

Входные данные	Результат работы
2020-07-19 18:00:00 20 2020-07-19 19:00:00 10 2020-07-19 20:00:00 30 2020-07-19 21:00:00 40	300
2020-07-19 21:00:00 20 2020-07-19 22:00:00 40 2020-07-19 23:00:00 10 2020-07-20 00:00:00 20 2020-07-20 01:00:00 60 2020-07-20 02:00:00 30	500

Очень быстрая сортировка (radix_sort.cpp)

Уметь сортировать быстро – полезный навык. Стандартные сортировки в языках Си и C++ достаточно быстры и универсальны. К сожалению, их универсальность имеет недостаток: сложность алоритмов этих сортировки составляет O(N log(N)). Между тем известно, что для некоторых типов данных имеются и сортировки со сложность по времени O(N). Вам и предстоит такую написать.

Файл, который вы должны послать в тестирующую систему, должен иметь реализацию ровно одной функции. Она должна ничего не вводить и ничего не выводить.

void fast_sort(unsigned *begin, unsigned *end) < // Your code for implementation >

Требуется, чтобы ваша функция отсортировала массив, заданный аргументами, по возрастанию. Ваша программа не должна содержать функции main.

Пример программы, которую можно использовать при тестировании:

int main() < unsigned array[8] = ; fast_sort(array, array+8); // Now array = >

Факториальная система счисления (r11_factradix.cpp)

Наряду с уже привычными позиционными системами счисления, к которым мы все уже привыкли, существует множество других, всё также позиционных, но с другими правилами вычисления весов позиций. Мы рассмотрим факториальную систему счисления, в которой вес каждой позиции — факториал от её номера. Для позиций после десятичной точки используются обратные к факториалам веса. Каждая правильная дробь (p < q) представляется в такой системе единственным конечным образом при условии, что в самом правом члене записи коэффициент отличен от нуля. Ваша задача — найти такие числа ai < i, чтобы сумма их произведений на факториалы их индексов i равнялась заданной дроби.

Формат входных данных

В одной строке через пробел выведите коэффициенты разложения, начиная с a2.

Гарантируется, что число выводимых членов будет меньше 1000.

Входные данные	Результат работы
1 4	0 1 2
5 7	1 1 1 0 4 2

Танец точек (r12_dance.cpp)

Формат входных данных

Входные данные	Результат работы
10 5 30 3 14 19 21	2

Офисное здание (r13_complaints.cpp)

Эта задача аналогична задаче h21_storeroom за исключением точности до секунд.

В одной очень большой стране в одном очень большом городе стояло очень-очень большое здание, в котором граждане этой страны подавали жалобы на других граждан. Так как жалобщиков было очень много, оно работало круглосуточно, но каждый из посетителей, пришедших в какое-то время после нуля часов, был обязан покинуть здание до 24 часов. Клерков, принимающих жалобы, было не очень много, из-за чего гражданам приходилось сидеть и ждать в очереди, пока нужный клерк освободится. На эту организацию, принимающую жалобы, в неё же поступила жалоба, что жалобы рассматриваются недостаточно быстро и вам было поручено определить, а сколько же жалобщиков одновременно находится в здании. К счастью для вас, во всех жителей этой страны были встроены чипы, точно определяющие положение в любой момент времени. Вам был дан доступ к данным за сутки. В 00:00:00 здание жалобщиков не ещё не содержало, а в 24:00:00 уже не содержало, так как все жалующиеся покинули здание. Дверей в здании много, поэтому вполне могли случаться такие ситуации, когда в одну и ту же секунду один жалобщик прибывал, а другой — покидал помещение. В таком случае оба считались находящимися в здании. Ваша задача — определить максимальное число жалобщиков, одновременно находящихся в здании.

Формат входных данных

Одно число — максимальное количество жалобщиков, одновременно находящихся в здании.

Входные данные	Результат работы
5 02:03:42 20:44:18 02:01:25 13:54:01 13:04:48 23:39:34 02:08:16 19:30:44 01:02:34 08:00:07	4

Подмножества (r14_subsets.cpp)

Множество задано строкой, то есть каждая буква есть элемент множества. Но это множество — не совсем простое. Элементы в нём могут повторяться. Два подмножества считаются одинаковыми, если все элементы одного множества совпадают с элементами другого. Например, множества, представленные строками abc и cba совпадают. Совпадают также множества abra и raba. Ваша задача по заданной строке, представляющей исходное множество, вывести все различные его подмножества, каждое на отдельной строке вывода. Выводить можно в произвольном порядке. Выход не должен содержать совпадающие подмножества. Пустое множество тоже является подмножеством исходного.

Формат входных данных

Исходное множество в виде строки

Все уникальные подмножества исходного множества по одному на строку. Подмножества не требуется как-либо упорядочивать, будет принят любой верный ответ.

Не забудьте, что пустая строка — тоже верное подмножество. В приведённом примере она следует первой, перед строкой a.

Входные данные	Результат работы
abra	a b ba ar rb aa raab baa abr ara r

Q1aQQ	QQa Qa 1 QQ 1a QQQa QQQ 1QQQ a 1Q 1QQ

Игра в 2048 (game2048.cpp)

Петя решил поиграть в известную игру 2048. Но играть в классическую версию ему уже неинтересно и он разработал улучшенную версию. У игрока имеется набор из нескольких чисел, где каждое число — степень двойки с натуральным показателем, не превыщающим n. Каждый ход игрок может сделать одно из следующих действий:

Сгенерировать число 2^k, это действие занимает ak секунд.

Умножить все имеющиеся числа на 2. При этом, если вы умножаете на 2 число 2^n, оно превращается в число 2. Такое действие занимает x секунд.

Например, если вы собрали набор 2, 32, 128 и n=7, то после выполнения второго действия у вас будет набор 4, 64, 2. Игра заканчивается, когда вы собираете ровно n чисел, и все они различны. Изначально у игрока нет чисел. Все ходы выполняются последовательно, один за одним. Петя решил провести соревнования по новой игре, и вы принимаете в нём участие. Спланируйте свою тактику так, чтобы быстрее всего закончить игру.

Формат входных данных

Выведите одно число — минимальное количество времени, необходимое для прохождения игры.

Входные данные	Результат работы
3 5 1 2 3	6
4 5 1 100 3 4	13

В первом тесте невыгодно использовать второе действие, поэтому просто последовательно сгенерируем все степени двойки. Во втором тесте выгодно сгенерировать за первые два хода (2,8), после этого умножить их на два, получить набор (4,16), и за два хода сгенерировать 2 и 8. Ответ: 1+3+5+1+3=13.

Несколько классов (several_classes.cpp)

Разработать набор классов, объекты которых реализуют типы данных, указанные ниже. С помощью перегрузки операторов (operator) разработать стандартную арифметику объектов, включающую арифметические действия над объектами и стандартными типами (целыми, вещественными, строками – в зависимости от вида объектов), присваивание, ввод и вывод в стандартные потоки (используя операторы «>»), приведение к/от базового типа данных. Организовать операции в виде конвейера значений, с результатом (новым объектом) и сохранением значений входных операндов.

Дата и время, представленные целочисленными переменными: год, месяц, день, час, минута, секунда. Базовый тип: uint64_t формат представления unix time. Реализовать возможность преобразования в/из формата представления filetime (целое 64-х разрядное значение, представляющее число интервалов по 100 наносекунд, прошедших с первого января 1601 года).
Год «от Адама», имеющий внутреннее представление в виде целочисленных переменных: индикт, круг солнцу, круг луне. Диапазоны значений (циклические): индикт 1—15, круг солнцу 1—28, круг луне 1—19. Ежегодно каждая переменная увеличивается на 1. Итоговое значение вычисляется как произведение переменных (диапазона на некоторый множитель; переменные независимы), а хранимое значение является остатком от деления (на диапазон), при этом 0 соответствует максимум. Необходима возможность отображения/задания как в виде одного числа, так и виде трех. Реализовать возможность преобразования в/из формата представления «от рождества Христова» используя соответствие 1652 = 7160 «от Адама».
Разреженная матрица, представленная динамическим массивом структур, содержащих описания ненулевых коэффициентов: индексы местоположения коэффициента в матрице (целые) и значение коэффициента (вещественное).

Формат входных данных

Выведите единственное число – максимальную сумму ответов на запросы, которую может получить Агата.

Входные данные	Результат работы
5 3 1 9 4 3 1 1 4 2 2 3 5	34
1 1 5 1 1	5
2 2 8 4 1 1 2 2 1 1	12

Физрук Арсений (gym_teacher.cpp)

В начале урока физкультуры ученики 13А класса выстроились в ряд. Физрук Арсений любит порядок, но школьники опять встали не по росту. Он решил проучить их и выбрать какой-то хороший отрезок детей, и отправить их играть в волейбол, а остальных оставить выполнять нормативы. Хорошим отрезком детей Арсений называет такой непрерывный отрезок детей в ряду, что их рост строго убывает. Ученики любят волейбол, поэтому хотят понять, есть ли у них шанс оказаться в числе счастливчиков. Для этого каждый школьник хочет выяснить, как много людей может пойти играть с ним в волейбол, то есть найти длину наибольшего хорошего отрезка, содержащего его самого.

Формат входных данных

Выведите n целых чисел через пробел, где i-е число — максимальная длина хорошего отрезка, содержащего школьника номер i.

Входные данные	Результат работы
5 7 4 2 2 10	3 3 3 1 1
5 2 4 6 4 2	1 1 3 3 3

Гурман (gourmet.cpp)

Нитуширг в жизни больше всего любит две вещи — вкусно поесть и отдыхать на море. Поэтому он решил совместить приятное с приятным и поехать на пятизвёздочный морской курорт Фокьнит. Но вот незадача: в Фокьните есть только одна столовая, меню в которой каждый день заранее фиксировано. Поскольку Нитуширг — гурман, он предпочитает разнообразие в еде, поэтому если за время отдыха какое-то меню попадётся более K раз — Нитуширг очень расстроится и весь отпуск пойдёт насмарку. При этом, разумеется, Нитуширг хочет отдохнуть на море как можно дольше. Ваша задача состоит в том, чтобы по известному заранее меню столовой на N дней выбрать как можно более длинный отрезок подряд идущих дней, в которые Нитуширг поедет в Фокьнит так, чтобы никакой набор блюд не повторялся более K раз за всё время поездки.

Формат входных данных

Входные данные	Результат работы
1 1 a	1 1
6 2 abbbaa	4 3

Структура данных — Дек (data_structure_deck.py)

Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за О(1). Помогите Гоше! Напишите эффективную реализацию. При реализации нельзя использовать связный список.

Формат входных данных

В первой строке записано количество команд n — целое число, не превосходящее 5000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 1000. В следующих n строках записана одна из команд:

push_back(value) — добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести ‘error’.
push_front(value) — добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести ‘error’.
pop_back() — вывести последний элемент дека и удалить его. Если дек был пуст, то вывести ‘error’.
pop_front() — вывести первый элемент дека и удалить его. Если дек был пуст, то вывести ‘error’. value — целое число, по модулю не превосходящее 1000.

Выведите результат выполнения кадой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.

Входные данные	Результат работы
4 4 push_front 861 push_front -819 pop_back pop_back	861 -819
7 10 push_front -855 push_front 720 pop_back pop_back push_back 844 pop_back push_back 823	-855 720 844

Сжиматель фоток (BMP_image_resizer/BMP_image_resizer.cpp)

В файле pic.bmp задано изображение в формате True Color 32 бита на пиксел. Написать программу на языке C++, которая загружает это изображение в программу, масштабирует изображение таким образом, чтобы его ширина и высота уменьшились бы втрое и выводит в файл pic2.bmp. В каждой точке создаваемого изображения каждая компонента цвета должна быть выбрана в виде среднего значения из девяти значений из квадрата 3х3 вокруг соответствующей точки на исходном изображении. В граничных точках размер области вокруг соответствующей точки на исходном изображении может быть меньше. Вся отведенная память в программе должна быть очищена. Все открытые файлы должны быть закрыты.

Скобочная последовательность (bracketssequence.py)

Дана скобочная последовательность. Нужно определить, правильная ли она. Будем придерживаться такого определения:

пустая строка — правильная скобочная последовательность;
правильная скобочная последовательность, взятая в скобки одного типа является правильной скобочной последовательностью;
правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью — тоже правильная.

На вход подаётся последовательность из скобок трёх видов: [], (), <>. Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.

Формат входных данных

На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.

Выведите True или False

Входные данные	Результат работы
	True
()	True
(	False

Списочная очередь (listqueue.py)

Любимый вариант очереди Тимофея — очередь, написанная с использованием связного списка. Помогите ему с реализацией. Очередь должна поддерживать выполнение трёх команд:

get() — вывести элемент, находящийся в голове очереди, и удалить его. Если очередь пуста, то вывести «error»;
put(x) — добавить число x в очередь;
size() — вывести текущий размер очереди.

В первой строке записано количество команд n — целое число, не превосходящее 1000. В каждой из следующих n строк записаны команды по одной строке.

Напечатайте результаты выполнения нужных команд, по одному на строке.

Входные данные	Результат работы
10 put -34 put -23 get size get size get get put 80 size	-34 1 -23 0 error error 1
6 put -66 put 98 size size get get	2 2 -66 98
9 get size put 74 get size put 90 size size size	error 0 74 0 1 1 1

Ограниченная очередь (sizedqueue.py)

Нужно написать класс MyQueueSized, который принимает параметр max_size, означающий максимально допустимое количество элементов в очереди. Реализуйте программу, которая будет эмулировать работу такой очереди. Функции, которые надо реализовать, описаны в формате ввода.

Формат входный данных

В первой строке записано одно число — количество команд, оно не превосходит 5000. Во второй строке задан максимально допустимый размер очереди, он не превосходит 5000. Далее идут команды по одной на строке. Команды могут быть следующих видов:

push(x) — добавить число x в очередь;
pop() — удалить число из очереди и вывести на печать;
peek() — напечатать первое число в очереди;
size() — вернуть размер очереди.

При превышении допустимого размера очереди нужно вывести «error». При вызове операций pop() или peek() для пустой очереди нужно вывести «None».

Напечатайте результаты выполнения нужных команд, по одному на строке.

Входные данные	Результат работы
8 2 peek push 5 push 2 peek size size push 1 size	None 5 2 2 error 2
10 1 push 1 size push 3 size push 1 pop push 1 pop push 3 push 3	1 error 1 error 1 1 error

Стек (stack.py)

Нужно реализовать класс StackMax, который поддерживает операцию определения максимума среди всех элементов в стеке. Класс должен поддерживать операции push(x), где x — целое число, pop() и get_max().

Формат входных данных

В первой строке записано одно число n — количество команд, которое не превосходит 10000. В следующих n строках идут команды. Команды могут быть следующих видов:

push(x) — обавить число x в стек;
pop() — удалить число с вершины стека;
get_max() — напечатать максимальное число в стеке

Если стек пуст, при вызове команды get_max() нужно напечатать «None», для команды pop() — «error».

Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте «None». Если происходит удаление из пустого стека — напечатайте «error».

Входные данные	Результат работы
8 get_max push 7 pop push -2 push -1 pop get_max get_max	None -2 -2
7 get_max pop pop pop push 10 get_max push -9	None error error error 10

Транспонирование матрицы (transposeMatrix.py)

Есть матрица размера m x n. Нужно написать функцию, которая её транспонирует. Транспонированная матрица получается из исходной заменой строк на столбцы.

Формат входных данных

В первой строке задано число m — количество строк матрицы. Во второй строке задано n — число столбцов. m,n

В следующих m строках задана матрица. Числа в ней не превосходят по модулю 1000.

Напечатайте транспонированную матрицу в том же формате, который задан во входных данных. Каждая строка матрицы выводится на отдельной строке, элементы разделяются пробелами.

Входные данные	Результат работы
4 3 1 2 3 0 2 6 7 4 1 2 7 0	1 0 7 2 2 2 4 7 3 6 1 0
9 5 -7 -1 0 -4 -9 5 -1 2 2 9 3 1 -8 -1 -7 9 0 8 -8 -1 2 4 5 2 8 -7 10 0 -4 -8 -3 10 -7 10 3 1 6 -7 -5 9 -1 9 9 1 9	-7 5 3 9 2 -7 -3 1 -1 -1 -1 1 0 4 10 10 6 9 0 2 -8 8 5 0 -7 -7 9 -4 2 -1 -8 2 -4 10 -5 1 -9 9 -7 -1 8 -8 3 9 9

Два велосипеда (binarysearch2.py)

Вася решил накопить на два одинаковых велосипеда — себе и сестре. У Васи есть копилка, в которую каждый день он может добавлять деньги. В процессе накопления Вася не вынимает деньги из копилки. У вас есть информация о росте Васиных накоплений — сколько у Васи в копелке было денег в каждый из дней.

Ваша задача — по заданной стоимости велосипеда определить первый день, в который Вася смог бы купить один велосипед, а также первый день, в который он бы мог купить два велосипеда. Решение должно работать за O(log n).

Формат входных данных

Нужно вывести два числа — номера дней по условию задачи. Если необходимой суммы в копилке не нашлось, нужно вернуть -1 вместо номера дня.

Входные данные	Результат работы
6 1 2 4 4 6 8 3	3 5
6 1 2 4 4 4 4 3	3 -1
6 1 2 4 4 4 4 10	-1 -1
4 1 10 10 10 2	2 2

Генератор скобок (bracketsgenerator.py)

Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке — алфавит состоит из ( и ) и открывающаяся скобка идёт раньше закрывающей. Помогите Рите — напишите программу, которая по заданному n выведет все ПСП в нужном порядке.

Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:

(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).

Формат входных данных

На вход функция принимает n — целое число от 0 до 10.

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

Входные данные	Результат работы
3	((())) (()()) (())() ()(()) ()()()
2	(()) ()()
4	(((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()

Комбинации (combinations_mobile.py)

На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв. Примерно так: 2: ‘abc’ 3: ‘def’ 4: ‘ghi’ 5: ‘jkl’ 6: ‘mno’ 7: ‘pqrs’ 8: ‘tuv’ 9: ‘wxyz’

Вам известно в каком порядке были нажаты кнопки телефона, без учёта повторов. Напечатайте все комбинации букв, которые можно набрать такой последовательностью нажатий.

Формат входных данных

На вход подаётся строка, состоящая из цифр 2-9 включительно. Длина строки не превосходит 10 символов.

Выведите все возможные комбинации букв через пробел.

Входные данные	Результат работы
23	ad ae af bd be bf cd ce cf
92	wa wb wc xa xb xc ya yb yc za zb zc
228	aat aau aav abt abu abv act acu acv bat bau bav bbt bbu bbv bct bcu bcv cat cau cav cbt cbu cbv cct ccu ccv

Большое число (bignumber.py)

Вечером ребята решили поиграть в игру «Большое число». Даны числа. Нужно определить, какое самое большое число можно из них составить.

Формат входных значений

В первой строке записано n — количество чисел. Оно не превосходит 100. Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.

Нужно вывести самое большое число, которое можно составить из данных чисел.

Входные данные	Результат работы
3 15 56 2	56215
3 1 783 2	78321
5 2 4 5 2 10	542210
6 9 10 1 1 1 6	9611110
38 82 58 66 34 64 37 40 97 93 52 28 98 90 64 19 22 21 83 56 70 46 17 31 51 55 41 68 18 98 89 88 74 6 6 31 36 35 8	9898979390898888382747068666664645856555251464140373635343131282221191817

Клумбы (segmentsunion.py)

Алла захотела, чтобы у неё под окном были узкие клумбы с тюльпанами. На схеме земельного участка клумбы обозначаются просто горизонтальными отрезками, лежащими на одной прямой. Для ландшафтных работы было нанято n садовников. Каждый из них обрабатывал какой-то отрезок на схеме. Процесс был организован не очень хорошо, иногда один и тот же отрезок или его часть могли быть обработаны сразу несколькими садовниками. Таким образом, отрезки, обрабатываемые двумя разными садовниками, сливаются в один. Непрерывный обработанный отрезок затем станет клумбой. Нужно определить границы будущих клумб.

Формат входных данных

В первой строке записано n — количество отрезков. В следующих n строках через пробел записаны 2 неотрицательных числа.

Вывести границы будущих клумб.

Входные данные	Результат работы
4 7 8 7 8 2 3 6 10	2 3 6 10
4 2 3 5 6 3 4 3 4	2 4 5 6
6 1 3 3 5 4 6 5 6 2 4 7 10	1 6 7 10

Гардероб (wardrobe.py)

Рита решила оставить у себя одежду только трёх цветов: розового, жёлтого и малинового. После того как вещи других расцветок были убраны, Рита захотела отсортировать свой новый гардероб по цветам. Сначала должны идти вещи розового цвета, потом — жёлтого, и в конце — малинового. Помогите Рите справиться с этой задачей.

Формат входных данных

В первой строке задано количество предметов в гардеробе: n — оно не превосходит 1000000. Во второй строке даётся массив, в котором указан цвет для каждого предмета. Розовый цвет обозначен 0, жёлтый — 1, малиновый — 2.

Нужно вывести в строку через пробел цвета предметов в правильном порядке.

Входные данные	Результат работы
7 0 2 1 2 0 0 1	0 0 0 1 1 2 2
5 2 1 2 0 1	0 1 1 2 2
6 2 1 1 2 0 2	0 1 1 2 2 2
0

Подпоследовательность (issubsequence.py)

Даны 2 строки, нужно понять, является ли первая из них подпоследовательностью второй. Когда строки достаточно длинные, очень трудно получить ответ на этот вопрос, просто посмотрев на них. Помогите Гоше написать функцию, которая решает эту задачу.

Формат входных данных

В первой строке записана строка s. Во второй — строка t.

Обе строки состоят из маленьких латинских букв, длины строк не превосходят 150000. Строки могут быть пустыми.

Выведите True, если s является подпоследовательностью t, иначе — False.

Входные данные	Результат работы
abc ahbgdcu	True
abcp ahpc	False
abcd dkajsdlkbca	False
anystring	True

Пузырек (bubblesort.py)

Требуется реализовать алгоритм сортировки пузырьком (по неубыванию):

На каждой итерации проходим по массиву, поочередно сравниваем пары соседних элементов. Если элемент на позиции i больше элемента на позиции i+1, то меняем их местами. После первой итерации самый большой элемент всплывёт в конце массива.
Проходим по массиву, выполняя указанные действия до тех пор, пока на очередной итерации не окажется, что обмены больше не нужны, то есть массив уже отсортирован.
После не более, чем n-1 итераций выполнение алгоритма заканчивается, так как на каждой итерации хотя бы один элемент оказывается на правильной позиции.

Формат входных данных

После каждого прохода по массиву, на котором какие-то элементы меняются местами, выводите его промежуточное состояние. Таким образом, если сортировка завершена за k меняющих массив итераций, то надо вывести k строк по n чисел в каждой — элементы массива после каждой из итераций. Если массив был изначально отсортирован, то просто выведите его.

Входные данные	Результат работы
2 4 51	4 5
5 1 1 1 1 1	1 1 1 1 1
5 4 3 9 2 1	3 4 2 1 9 3 2 1 4 9 2 1 3 4 9 1 2 3 4 9
5 12 8 9 10 11	8 9 10 11 12
10 87 123 23 9 71 2 11 23 -99 0	87 23 9 71 2 11 23 -99 0 123 23 9 71 2 11 23 -99 0 87 123 9 23 2 11 23 -99 0 71 87 123 9 2 11 23 -99 0 23 71 87 123 2 9 11 -99 0 23 23 71 87 123 2 9 -99 0 11 23 23 71 87 123 2 -99 0 9 11 23 23 71 87 123 -99 0 2 9 11 23 23 71 87 123

Двумерные массивы (211012_matrices.pas)

Даны квадратные матрицы A, B, C размерности n. Вычислить матрицу D. E — единичная матрица. Для решения задачи применить процедуры: сложения, вычитания и умножения матриц. Исходные и получаемые матрицы должны отображаться на форме.

Формат входных данных

На первой строке вводится целое положительное число n. На последующих 3n строках вводятся строки матриц A, B, C по n целых чисел в строке, разделённых пробелами.

Вывести результирующую матрицу D = A * A — B * C + E.

Входные данные	Результат работы
3 1 2 3 -2 0 7 -8 -7 -6 8 17 22 -1 1 17 2 0 0 9 6 3 -1 -2 -3 4 2 0	-169 -77 26 -116 -78 -42 36 14 -42

Поиск в сломанном массиве (binarysearch_shifted_array.py)

Произошла ошибка при копировании из одной структуры данных в другую. Массив чисел хранился в кольцевом буфере и был отсортирован по возрастанию, в нём можно было найти элемент за логарифмическое время. Данные были скопированы из кольцевого буфера в обычный массив, в результате они стали циклически сдвинуты. Нужно обеспечить возможность находить элемент за логарифмическое время.

Формат входных данных

В первой строке вводится размер массива n. Во второй — искомое число. На третьей строке идут n целых чисел через пробел. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000.

Вернуть индекс элемента, равного k, если такой есть в массиве (нумерация с нуля). Если элемент не найден, вернуть -1. Изменять массив нельзя.

Входные данные	Результат работы
9 5 19 21 100 101 1 4 5 7 12	6
2 1 5 1	1

Матричные манипуляции (MatrixManipulation.cpp)

Реализовать программу для работы с квадратной матрицей. Программа должна содержать:

Структуру, описывающую матрицу.
Функцию для заполнения квадратной матрицы размерностью nn возрастающей последовательностью от 1 до nn целых чисел по заданной схеме.

На примере n=4:
4 3 2 1
5 10 11 12
6 9 14 13
7 8 15 16

n=5:
5 4 3 2 1
6 13 14 15 16
7 12 19 18 17
8 11 20 23 24
9 10 21 22 25

Функцию для заполнения квадратной матрицы размерностью n*n целых чисел.
Функция вывода матрицы в файл (в виде матрицы).
Функция нахождения обратной матрицы.
Функция умножения матриц.

Мир наш исполнен войны — целая вечность сражений во имя Императора. Он никогда не прекращает и не отступается от бесконечной вражды, а значит — не должны и мы.

Второй год Похода Мучений. В отдалённой системе войска Императора столкнулись с планетой полной ужасающих человекоподобных зверей, представляющих собой серьёзную угрозу. После ожесточённых боёв связь с ударным отрядом чёрных тамплиеров во главе с братом Герхартом была потеряна, в связи с чем было приятно единственно верное решение в таких ситуациях — ЭКСТЕРМИНАТУС, то есть полное уничтожение всего живого на поверхности. Для запуска орбитальной бомбардировки требуются специальные коды запуска. Обычно они приходят на отдельный канал и с ними не возникает никаких проблем, но в этот раз в связи с оплошностью подчинённого несколько передач принимались по одному каналу и результаты перемешались. Ваша задача состоит в том, чтобы извлечь из полученной информации коды запуска орудий.

Формат входных данных

Передача состоит из заглавных и строчных латинских букв, цифр, а также 4 основных арифметических действий ‘+’, ‘-‘, ‘*’, ‘/’. Её длина не превосходит 2000 символов. Известно, что кодом является некоторая команда вида A op B, где A и B — целые неотрицательные числа, а op — одно из арифметических действий, результат которой является корректно вычислимым выражением модуль которого не превосходит 120000. При этом выражение «A op B» является подстрокой исходного сообшения. Гарантируется, что числа A,B и результат операции над ними не переполняют 32-х битные целые знаковые числа.

Необходимо найти все такие команды и вывести их каждую с новой строки в виде A op B = res, где res — результат вычисления. Всё остальное считается мусором из других передач. Заметим, что для выражения A op1 B op2 C нужно вывести: A op1 B = res1
B op2 C = res2

Входные данные	Результат работы
100+200/9	100 + 200 = 300 200 / 9 = 22
rDU+9519+28006-+45350-80003-7034/14870/50385i-25266-39120*8557	9519 + 28006 = 37525 45350 — 80003 = -34653 80003 — 7034 = 72969 7034 / 14870 = 0 14870 / 50385 = 0 25266 — 39120 = -13854

Работа со списком (list_manipulation.c)

Формат входных данных

Во входном файле input.txt записаны две строки, каждая из которых содержит последовательность из не более чем 10000 целых чисел. Обе последовательности заканчиваются числом -1 (и оно не входит в последовательность), остальные числа неотрицательны и не превосходят 10^9.

Указание: при решении данной задачи запрещается использовать массивы. Для хранения последовательности чисел используйте однонаправленный или двунаправленный список.

Требуется в файл output.txt вывести без изменения порядка все члены второй последовательности, кроме тех которые встречаются в первой последовательности.

Входные данные	Результат работы
1 8 4 12 -1 2 4 1 3 5 8 -1	2 3 5
3 5 4 2 0 -1 5 3 2 1 0 4 3 -1	1

Вставка в двоичное дерево поиска (search_tree_insertion.c)

Структура struct tree (int x; struct tree *left, *right, *parent;); описывает двоичное дерево поиска. Напишите функцию void ins (struct tree *t, int x), вставляющую в дерево поиска t, заведомо содержащее ключ x, элемент с ключом, на единицу меньшим следующего по размеру за x ключа в дереве, либо с ключом x+1, если x — максимальный элемент дерева. Гарантируется, что ключ, который нужно вставлять, не содержится в дереве.

Dual linked list (dualLinkedListTemplate.cpp)

Develop a template of a container class, that represents an abstract data type of dual linked list. This class should contain random access iterator and have the following interface:

Name	Description
constructor
destructor
operator=
Iterators:
begin	return iterator to beginning
end	return iterator to end
rbegin	return reverse iterator to reverse beginning
rend	return reverse iterator to reverse end
Capacity:
empty	test whether container is empty
size	return size
Element access:
front	access first element
back	access last element
Modifiers:
assign	assign new content to container
push_front	insert element at beginning
pop_front	delete first element
push_back	add element at the end
pop_back	delete last element
insert	insert element x at index idx
erase	erase element
swap	swap content
resize	change size
clear	clear
Operations:
reverse	reverse the order of elements

It is forbidden to use std::iterator. Demonstrate work of the implemented methods in the main function.

Горнолыжный курорт (hills.cpp)

Сеть пунктов проката горнолыжного оборудования представляет собой корневое дерево, состоящее из n вершин, пронумерованных от 1 до n с корнем в вершине номер 1. В каждой вершине имеется пункт проката. Пункт, расположенный в i-й вершине, закупает оборудование по цене c_i рублей за комплект.

Пусть a_i — суммарное количество комплектов горнолыжного оборудования, которое будет закуплено во всех пунктах проката, находящихся в поддереве вершины номер i. Согласно маркетинговым исследованиям для каждого i эта величина должна находиться в диапазоне: l_i

Необходимо определить, какое количество комплектов нужно закупить к началу сезона каждому из пунктов проката, чтобы для поддерева любой вершины сети общее количество комплектов находилось в указанном маркетологами диапазоне, а суммарная стоимость всех купленных комплектов была как можно меньше. Либо определить, что выполнить все условия маркетологов невозможно.

Напомним, что граф называется деревом, если он связный и не содержит циклов. Между любыми двумя вершинами в дереве существует ровно один простой путь. Корневым деревом называется дерево, в котором есть одна выделенная вершина — корень. Поддеревом вершины v называют множество всех вершин, для которых вершина v лежит на пути от соответствующей вершины до корня. Обратите внимание, что сама вершина v тоже входит в это множество. Родителем вершины v называется такая вершина p_v, что v и pv соединены ребром, и pv лежит на пути от v до корня.

Формат входных данных

Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число t — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано одно целое число n (1

Гарантируется, что сумма n по всем наборам входных данных не превышает 100000.

Для каждого набора данных выведите ответ в следующем формате.

Если невозможно выполнить все условия маркетологов, в единственной строке выведите -1.

Иначе, в первой строке выведите минимальное количество рублей, которое необходимо потратить на закупку горнолыжного оборудования всем пунктам сети суммарно. Во второй строке выведите n целых чисел bi, где bi равно количеству комплектов, которое необходимо закупить пункту проката номер i. Если существует несколько способов выполнить все условия маркетологов, потратив минимальное возможное количество рублей, вы можете вывести любой из них.

Входные данные	Результат работы
2 3 1 1 3 1 2 5 7 1 2 2 4 2 1 5 5 0 1 2 2	8 0 2 3 -1
1 10 1 2 1 1 4 2 1 2 5 229935705 252294888 574618756 226876866 225916692 249797075 133791770 102539705 760471176 956697279 125 237 48 102 13 27 20 42 29 58 11 22 21 41 13 26 7 15 20 40	45429982917 0 0 13 9 9 11 30 26 7 20

Сумма и определитель матрицы (matrixsum.java)

Реализовать консольное приложение, которое имеет примитивный текстовый интерфейс и меню, состоящее как минимум из четырех пунктов:

Ввод исходных данных, как вручную, так и сгенерированных случайным образом
Выполнение алгоритма по заданию
Вывод результата
Завершение работы программы

В работе можно использовать только массивы! Результат не может быть выведен без обработки введённых данных. Вывод результата не может быть осуществлен без выполнения алгоритма. При вводе новых данных результаты выполнения алгоритма «сбрасываются». Варианты заданий, где указан массив слов подразумевают, что разделителями для слов являются пробельные символы и знаки препинания.

Формат входных данных

Две квадратные матрицы одинакового размера, значение которого также вводит пользователь.

Сумма матриц и значение ее определителя.

Количество выходных в году (weekdays_a_year.c)

В некоторой стране действует Григорианский календарь. В добавление к выходным дням субботы и воскресенья выходными объявляются 1, 2, 4, 8, 16, 32, 64, 128 и 256 день в году (1 января считается днем 1). Если такой день уже приходится на выходной, он не переносится, то есть дополнительный выходной “сгорает”.

Формат входных данных

Целое число — год (от 1902 до 2037).

Целое число — количество выходных дней в этом году.

В десятичную систему счисления (anytodecimal.c)

В аргументах командной строки задаются 64-битные беззнаковые числа в 17-ричной системе счисления. На стандартный поток вывода напечатайте эти числа в десятичной системе счисления, упорядоченные по невозрастанию.

Пример запуска программы: ./solution 1 2 3

Результат работы программы:
3
2
1

Бинаризуй (BinarizeMe.cpp)

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

Формат входных данных

На вход подается строка из не более 255 символов, среди которых могут быть и пробельные. Гарантируется, что числа в строке не начинаются с 0.

Строка — результат преобразования.

Входные данные	Результат работы
192873a kjhfd129380	101111000101101001a kjhfd11111100101100100
6a8g923mx	110a1000g1110011011mx

Электронные часы (digitalwatch.cpp)

У вас есть сломанные электронные часы, у которых некоторые пиксели перестали работать или наоборот — работают всегда. Требуется по ним определить и вывести текущее время или вывести ошибку в случае, если этого сделать нельзя.

Формат входных данных

На вход подаются 6 строк по 20 символов. Каждый прямоугольник 6х5 задает цифру циферблата.

Выведите время в формате hh:mm. Если на изображении присутствуют лишние пиксели или неверный формат времени (больше 23:59), выведите ERROR. Если время нельзя определить однозначно, выведите AMBIGUITY.

Входные данные	Результат работы
`..##..####.####..##.` `.#..#. #.#. #..#` `. #. #..###..#..#` `. #. #. #..###` `..#. #.#..#. #` `.####.###. ##..###.`	23:59
`. #.#..#.####..###` `. ##.#..#.#. #.` `..#.#.#..#.###..###.` `. #.####. #.#..#` `. #. #.#..#.#..#` `. #. #..##. ##.`	14:56
`..##..####.#..#..##.` `.#..#. #.#..#.#..#` `.#..#. #..#..#..##.` `.#..#..#. ####.#..#` `.#..#..#. #.#..#` `..##. #. #..##.`	07:48
`. #..##..###. ##.` `. ##.#..#. #.#..#` `..#. #. #.` `. #. #. #` `. #..#. #. #` `. ####.#. ##.`	AMBIGUITY
`. #..##..###. ##.` `. ##.#..#. #.#..#` `..#. #. #. #.` `. #. #. #` `. #..#. #. #` `. ##.`	12:38
`#.` `.` `.` `.` `.` `.`	ERROR
`. #.` `.` `..#. #. #.` `. #.` `. #..` `. #.`	13:47

Стабильная сортировка (stable_quicksort.cpp)

Требуется реализовать стабильную сортировку для следующей задачи. Выведите фамилии и имена абитуриентов, подавших документы на поступление в ВУЗ в порядке убывания их среднего балла по ЕГЭ.

Про каждого ученика известны их фамилии, имена и баллы ЕГЭ по следующим предметам: информатика, математика и русский язык.

Формат входных данных

Необходимо вывести пары фамилия — имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить баллы не нужно. Если несколько учащихся имеют одинаковые средние баллы, то их нужно выводить в порядке, заданном во входных данных.

Входные данные	Результат работы
2 Markov Alexander 100 99 98 Ivanov Ivan 99 98 98	Markov Alexander Ivanov Ivan
3 Markov Alexander 75 90 90 Sergey Petrov 100 50 100 Petrov Petr 99 94 71	Petrov Petr Markov Alexander Sergey Petrov
6 A A 90 90 90 B B 90 90 90 C C 90 90 90 D D 90 90 90 E E 90 90 90 F F 90 90 90	A A B B C C D D E E F F

Гипершашки (hypershashki.cpp)

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гепершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал a баллов, второй — b, третий c, то говорят, что игра закончилась со счетом a : b : c. Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в k раз. После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа x1, x2, . xn. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки. Требуется написать программу, которая по числу k и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

Формат входных данных

Одно целое число — искомое количество различных вариантов счета.

Входные данные	Результат работы
3 1 1 1 1	1
6 6 1 1 1 2 2 21	8
6 3 1 2 3 4 5 6	66
3 1 1 2 3	0
5 2 2 2 3 4 5	18

Карточная игра (cardgame.cpp)

В игре в зожника карточная колода раздается поровну двум игрокам. Далее они вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, которые кладутся под низ его колоды. Тот, кто остается без карт — проигрывает. Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту («шестерка берет туза»). Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).

Напишите программу, которая моделирует игру в зожника и определяет, кто выигрывает. В игре участвует 10 карт, имеющих значения от 0 до 9, большая карта побеждает меньшую, карта со значением 0 побеждает карту 9.

Формат входных данных

Две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карт первого игрока, вторая строка — номера карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.

Программа должна определить, кто выигрывает при данной раздаче, и вывести слово «first» или «second», после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10^6 ходов игра не заканчивается, программа должна вывести слово «botva».

Входные данные	Результат работы
1 3 5 7 9 2 4 6 8 0	second 5
7 8 3 0 4 6 2 9 1 5	botva
9 8 7 1 2 0 3 4 5 6	second 15

Задачи на графы (TasksOnGraphs.ipynb)

22 небольшие задачи на ориентированные и неориентированные графы, написанные на python. В том числе задачи на подсчет числа компонент связности, определение транзитивности, полноты и регулярности графов.

Процессы: текущее время (fork_currentdate.c)

Родитель создает сына, тот — внука, а тот — правнука. Правнук передает в канал текущее время, полученное с помощью системного вызова time, в бинарном виде (тип time_t).

Отец, сын и внук считывают время из канала. Процесс-отец выводит на экран строку «Y. «, где . заменяются на текущий год, сын — «M. «, где ?? заменяются на текущий месяц в году (от 1 до 12), число всегда выводится с двумя знаками, внук — «D. «, где ?? заменяются на номер дня в месяце, всегда выводящееся с двумя знаками.

Внук должен вывести число первым, сын — вторым, а отец — третьим. Записывать в канал разрешается только правнуку.

Пример вывода:
D:11
M:09
Y:2001

Процессы: сумма чисел (fork_printsum.c)

Процесс-родитель создает процесса-сына, а тот в свою очеред процесса-внука. Процесс-родитель и процесс-внук должны быть соединены анонимным каналом в направлении от родителя к внуку. Процесс-родитель считывает 32-битные знаковые целые числа, подаваемые на стандартном потоке ввода в текстовом виде. Последовательность заканчивается признаком конца файла. Процесс-родитель передает считанные числа в канал в бинарном виде. Процесс-внук считывает числа из канала и вычисляет их сумму. После чтения всех чисел процесс-внук выводит на стандартный поток вывода их сумму и завершает работу. Процесс-родитель должен дождаться завершения всех порожденных им процессов и завершиться сам с кодом завершения 0.

Input 1 2 3 4 5 6 7 8 9 10 Output 55

Максимальная куча на бинарном дереве (maxheap.cpp)

Требуется реализовать приоритетную очередь с помощью бинарной пирамиды, поддерживающую три операции: добавить элемент, извлечь максимальный элемент и удалить заданный элемент. При просеивании нельзя совершать лишние перемещения (например, в случае равенства элементов). Если при просеивании вниз, рассматриваемый элемент можно перемещать как влево вниз, так и вправо вниз, то следует выбрать лево.

Формат входных данных

В ответ на запрос типа 1 следует вывести: Если извлекать было нечего (очередь пуста), то -1. Иначе — два числа, первое — индекс конечного положения элемента после его просеивания (если удален последний элемент и просеивать нечего, то вывести 0), второе — значение извлеченного элемента. В ответ на запрос типа 2 следует вывести: Если добавить нельзя (нет места, т.к. в очереди уже N элементов), то -1. Иначе — индекс добавленного элемента. В ответ на запрос типа 3 следует вывести: Если элемента с таким индексом нет и удаление невозможно, то -1. Иначе — значение удаленного элемента. После выполнения всех запросов требуется вывести пирамиду в её конечном состоянии.

Входные данные	Результат работы
4 10 1 2 9 2 4 2 9 2 9 2 7 1 3 4 2 1 3 3	-1 1 2 3 2 -1 2 9 -1 4 9 9 4 1
5 5 2 4 2 5 1 1 1	1 1 1 5 0 4 -1
10 30 1 2 -1 1 1 2 0 1 2 0 2 9 2 -6 1 1 1 1 2 6 2 4 2 -1 2 -5 2 3 1 2 -5 1 1 2 7 1 2 -3 2 6 1 1 2 4 2 0	-1 1 0 -1 -1 1 0 0 1 1 3 2 9 1 0 0 -6 -1 1 2 3 4 5 2 6 5 2 4 3 3 1 2 7 2 1 2 6 2 -1 1 2 4 0 -5 -5 -3

Количество способов из 1 в N (countWays1toN.py)

Имеется калькулятор, который выполняет следующие операции:

умножить число X на 2
умножить число X на 3
прибавить к числу X единицу

Определите, какое наименьшее количество операций требуется, чтобы получить из числа 1 число N.

Формат входных данных

Во входном файле написано натуральное число N, не превосходящее 10^6.

В первой строке выходного файла выведите минимальное количество операций. Во второй строке выведите числа, последовательно получающиеся при выполнении операций. Первое из них должно быть равно 1, а последнее N. Если решений несколько, выведите любое.

Входные данные	Результат работы
1	0 1
5	3 1 3 4 5

Движение по полосам (dorogi.py)

При организации движения по сложным перекресткам, для того, чтобы траектории водителей, выполняющих различные маневры, не пересекались, вводят ограничения на возможные маневры водителей, в зависимости от того, по какой полосе движения водитель подъехал к перекрестку. Для этого используется знак «движение по полосам». Рассмотрим дорогу, подходящую к перекрестку, на котором сходится m дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в m различных направлениях — обратно по дороге, по которой он приехал, а также по одной из оставшихся m — 1 дорог. Пронумеруем возможные направления числами от 1 до m слева направо с точки зрения подъезжающего водителя. Номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 — поворот на самую левую из дорог, и т.д.

Пусть дорога содержит n полос для движения. Пронумеруем полосы от 1 до n слева направо, самая левая полоса получит номер 1, следующая номер 2, и т.д. Знак «движение по полосам» разрешает каждой из полос движение по некоторым из m возможных направлений. При этом должны выполняться следующие условия:

Если с i-й полосы разрешено движение в a-м направлении, а с j-й полосы разрешено в b-м направлении, причём i < j, то a
С каждой полосы разрешено движение хотя бы в одном направлении.
В каждом направлении разрешено движение хотя бы с одной полосы.

Инспекция по безопасности дорожного движения заинтересовалась, а сколько различных знаков «движение по полосам» можно установить перед таким перекрестком. Помогите им найти ответ на этот вопрос.

Формат входных данных

В выходной файл выведите одно число — количество возможных знаков «движение по полосам», которые можно установить перед перекрестком.

Входные данные	Результат работы
4 2	7
5 2	9
4 3	25
50 15	108206580836328381

В первом примере возможны следующие варианты знаков «движение по полосам»:

С левой полосы	С правой полосы
разворот	разворот, налево, прямо, направо
разворот	налево, прямо, направо
разворот, налево	налево, прямо, направо
разворот, налево	прямо, направо
разворот, налево, прямо	прямо, направо
разворот, налево, прямо	направо
разворот, налево, прямо, направо	направо

Каждому по компьютеру (pcforeverybody.py)

В каждом новом учебном году на занятия в компьютерные классы Дворца Творчества Юных пришли учащиеся, которые были разбиты на N групп. В i-й группе оказалось Xi человек. Тут же перед директором встала серьезная проблема: как распределить группы по аудиториям. Во дворце имеется M >= N аудиторий, в j-й аудитории имеется Yj компьютеров. Для занятий необходимо, чтобы у каждого учащегося был компьютер и еще один компьютер был у преподавателя. Переносить компьютеры из одной аудитории в другую запрещается. В одной аудитории одновременно может находиться только одна группа. Напишите программу, которая найдет, какое максимальное количество групп удастся одновременно распределить по аудиториям, чтобы всем учащимся в каждой группе хватило компьютеров, и при этом остался бы ещё хотя бы один для учителя.

Формат входных данных

Выведите на первой строке число P — количество групп, которые удастся распределить по аудиториям. На второй строке выведите распределение групп по аудиториям — N чисел, i-е число должно соответствовать номеру аудитории, в которой должна заниматься i-я группа. (Нумерация как групп, так и аудиторий, начинается с 1). Если i-я группа осталась без аудитории, i-е число должно быть равно 0. Если допустимых распределений несколько, выведите любое из них.

Входные данные	Результат работы
1 1 1 2	1 1
1 1 1 1	0 0
3 4 5 3 4 3 5 3 6	2 0 2 4
3 3 1 2 3 3 4 2	3 3 1 2

Турнир (tournament.py)

В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью — 1, за поражение — 0 очков. Известно, сколько очков в итоге получила каждая команда, однако результаты конкретных матчей были утеряны. Требуется восстановить одну из возможных турнирных таблиц.

Формат входных данных

В первой строке входных данных содержится одно натуральное число K, не превосходящее 100 — количество команд. Во второй строке задаются через пробел K целых неотрицательных чисел, не превосходящих 2(K-1), количество очков, набранных командами, занявшими первое, второе, . K-е места соответственно (то есть каждое следующее число не больше предыдущего).

Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, . последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел — количество очков, набранных в игре данной команды с первой, второй, . командами соответственно. Количество очков — это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды «самой с собой») нужно записать нули. Гарантируется, что входные данные соответствуют реальному турниру, то есть хотя бы одна таблица, соответствующая входным данным, может быть построена. Если таких таблиц несколько, выведите любую из них.

Входные данные	Результат работы
4 6 4 2 0	0 2 2 2 0 0 2 2 0 0 0 2 0 0 0 0
4 3 3 3 3	0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
4 4 3 3 2	0 1 1 2 1 0 1 1 1 1 0 1 0 1 1 0
5 6 5 5 2 2	0 1 1 2 2 1 0 1 1 2 1 1 0 2 1 0 1 0 0 1 0 0 1 1 0

Транспортировка (transfer.cpp)

К очередной Летней компьютерной школе было решено подготовить кружки как для школьников, так и для всех преподавателей.

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до ЛКШ, остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения

Формат входных данных

В первой строке находятся числа n (1≤n≤500) и m — количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ — номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик — 3 тонны.

Выведите одно число — максимальное количество кружек, которое можно привезти за первый рейс, потратив не более 24часов.

Входные данные	Результат работы
3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099	2

Нормализация UNIX пути (unixpath.cpp)

В этой задаче нужно написать функцию, которая приводит к нормализованному виду строку, представляющую собой путь к файлу или директории в UNIX-подобной операционной системе.

Нормализация пути заключается в приведении к абсолютному пути и избавлении от следующих элементов:

/ в конце пути
. — текущая директория
.. — родительская директория
// — равносильно /

Формат входных данных

На вход подается текущая директория current_working_dir (абсолютный путь, т.е. начинающийся с / ) и путь path , который может быть как абсолютным, так и относительным.

Надо вернуть нормализованный абсолютный путь, которому соответсвует path .

Входные данные	Результат работы
NormalizePath(«/», «.»)	/
NormalizePath(«/home/user1», «../user2»)	/home/user2
NormalizePath(«/», «..»)	/
NormalizePath(«/home», «../../tmp»)	/tmp
NormalizePath(«/», «../../a/»)	/a
NormalizePath(«/», «.././/././/./../b/././././././»)	/b

Сапёр (minesweeper.cpp)

Реализуйте класс Minesweeper для игры «Сапёр».

принимающий размеры поля и количество мин — расставляет мины на поле случайным образом
принимающий размеры поля и список клеток — расставляет мины на указанных клетках

NewGame — инициализирует новую игру; имеет два варианта, аналогичных конструкторам
OpenCell — аналог клика левой кнопкой мыши
- если игра выиграна или проиграна, ничего не делает
- если клетка с флажком, ничего не делает
- если клетка без флажка, открывает клетку; алгоритм отрытия клеток описан ниже
- если игра выиграна или проиграна, ничего не делает
- пустую клетку отмечает флажком
- с клетки с флажком снимает флажок
- закрытая клетка — —
- клетка с миной — *
- клетка с флагом — ?
- открытая клетка без мин — число от 1 до 8 (соответствует количеству мин в соседних клетках), вместо 0 рисуется .
Алгоритм открытия клетки
- Если клетка содержит мину
  - открываются все клетки
  - игра заканчивается проигрышем
  - текущая клетка открывается
  - алгоритм открытия клетки применяется ко всем соседям текущей клетки без флажка
  Игра считается выигранной, когда открыты все клетки кроме тех, на которых стоят мины.
  
  Внутреннее представление игры не должно быть завязано на отображение. Преобразуйте внутреннее представление в строки только в методе RenderField .
  
  Наивный алгоритм случайной расстановки мин может быть неэффективен при количестве мин, близком к общему количеству клеток. Поле может быть очень большим. Не используйте рекурсивный вызов функций/методов для открытия клеток.
  
  Тесты для данной задачи находятся в функции main файла minesweeper.cpp .
  
  Информатика и программирование основы информатики 9785769581441
  
  Table of contents :
  Список основных используемых сокращений и обозначений
  Введение
  Глава 1. Информатика — наука и вид практической деятельности
  1.1. Информатика и ее структура
  1.2. Информатика в обществе
  1.3. Информатика в природе
  Глава 2. Основы теории информации
  2.1. Понятие информации
  2.2. Непрерывная и дискретная информация
  2.3. Адекватность информации и ее формы
  2.4. Синтаксическая мера информации
  2.4.1. Вероятностный подход
  2.4.2. Объемный подход
  2.5. Показатели качества информации
  Глава 3. Информационные процессы, системы и технологии
  3.1. Информационные процессы
  3.2. Информационные системы
  3.3. Информационные технологии
  Глава 4. Системы счисления
  4.1. Непозиционная и позиционная системы счисления
  4.2. Двоичная, десятичная и шестнадцатеричная системы счисления. Перевод чисел в десятичную систему счисления
  4.3. Перевод целых чисел из одной системы счисления в другую
  4.4. Перевод дробных чисел из одной системы счисления в другую
  Глава 5. Представление чисел, символов, графических и звуковых данных в ЭВМ
  5.1. Представление целых чисел в ЭВМ
  5.1.1. Форматы представления целых чисел
  5.1.2. Прямой и дополнительный коды представления двоичных чисел
  5.2. Представление вещественных чисел в ЭВМ
  5.3. Представление символов в ЭВМ
  5.4. Представление графических и звуковых данных в ЭВМ
  Глава 6. Логические основы ЭВМ
  6.1. Алгебра высказываний. Понятие, высказывание, умозаключение
  6.2. Логические операции
  6.3. Логические функции
  6.3.1. Способы представления логических функций
  6.3.2. Способы перевода логических функций из одного базиса в другой
  6.3.3. Минимизация логических функций
  6.4. Логические элементы и логические схемы
  Глава 7. Знания. Модели представления знаний
  7.1. Знания и их особенности
  7.2. Модели представления знаний
  7.3. Логические модели
  7.4. Семантические сети
  7.5. Продукционные модели
  7.6. Фреймы
  Глава 8. Архитектура ЭВМ
  8.1. Поколения ЭВМ
  8.2. Структура ЭВМ
  8.3. Микропроцессор
  8.4. Системная шина
  8.5. Оперативное и постоянное запоминающие устройства
  8.6. Внешние запоминающие устройства
  8.6.1. Общие сведения
  8.6.2. Магнитные носители
  8.6.3. Оптические носители
  8.6.4. Флэш-память
  8.7. Видеоподсистема ЭВМ
  8.7.1. Видеокарта
  8.7.2. Основные характеристики мониторов
  8.7.3. Типы мониторов
  8.8. Контроллеры портов ввода-вывода
  8.9. Периферийные устройства
  8.9.1. Клавиатура
  8.9.2. Манипулятор типа «мышь»
  8.9.3. Принтеры
  8.9.4. Сканеры
  8.9.5. Сетевой адаптер
  8.9.6. Модем
  Глава 9. Основы алгоритмизации
  9.1. Понятие алгоритма
  9.2. Алгоритмическая система
  9.3. Алгоритмизация
  9.4. Средства записи алгоритмов
  9.4.1. Словесная запись алгоритмов
  9.4.2. Схемы алгоритмов
  9.4.3. Структурограммы
  9.5. Технология разработки алгоритмов
  9.6. Структуры алгоритмов
  9.6.1. Алгоритмы линейной структуры
  9.6.2. Ветвления
  9.6.3. Циклы
  9.6.4. Итерационные циклы
  9.6.5. Вложенные циклы
  9.6.6. Вспомогательные алгоритмы
  Глава 10. Программное обеспечение ЭВМ
  10.1. Жизненный цикл программного продукта
  10.2. Классификация программного обеспечения
  10.3. Операционные системы
  10.3.1. Понятие «операционная система» и ее виды
  10.3.2. Распределение ресурсов ЭВМ между процессами
  10.3.3. Поддержание файловой системы
  10.3.4. Обеспечение интерфейса пользователя
  10.3.5. Файлы конфигурации операционных систем Windows
  10.3.6. Драйверы устройств
  10.4. Архиваторы
  10.5. Текстовые процессоры
  10.5.1. Классификация программ для работы с текстовыми документами
  10.5.2. Общие сведения об объектах текстового редактора Microsoft Word
  10.5.3. Элементы форматирования текстового редактора Microsoft Word
  10.5.4. Примеры оформления документов
  10.5.5. Элементы документа текстового редактора Microsoft Word
  10.5.6. Автоматизация работы текстового редактора Microsoft Word
  10.6. Табличные процессоры
  10.6.1. Табличные процессоры, их функции и структура
  10.6.2. Общие сведения об объектах Microsoft Excel
  10.6.3. Типы адресации в Microsoft Excel
  10.6.4. Присвоение имен ячейкам и диапазонам в Microsoft Excel
  10.6.5. Формулы Microsoft Excel и их отладка
  10.6.6. Логические функции Microsoft Excel
  10.6.7. Функции теории вероятностей и математической статистики в Microsoft Excel
  10.6.8. Финансовые функции Microsoft Excel
  10.7. Графические редакторы
  10.8. Базы данных
  10.8.1. Базы данных и их классификация
  10.8.2. Реляционная модель данных
  10.8.3. Нормализация отношений
  10.8.4. Типы связей
  Глава 11. Вычислительные сети
  11.1. Понятие, виды и характеристики вычислительных сетей
  11.2. Модель взаимодействия открытых систем
  11.3. Сетевые протоколы
  11.4. Локальные сети
  11.4.1. Топологии локальных вычислительных сетей
  11.4.2. Виды коммутации
  11.4.3. Способы адресации ЭВМ в сети
  11.4.4. Маршрутизация в вычислительных сетях
  11.5. Глобальная сеть Интернет
  11.5.1. Интернет как сообщество сетей
  11.5.2. Протоколы сети Интернет
  11.5.3. Система адресации в сети Интернет
  11.5.4. Службы сети Интернет
  Список литературы
  
  Citation preview
  
  Б а к а л а в р и ат
  
  информатика и программирование Основы информатики Учебник
  
  Рекомендовано Федеральным государственным бюджетным образовательным учреждением высшего профессионального образования «Московский государственный технический университет имени Н. Э. Баумана» в качестве учебника для студентов высших учебных заведений, обучающихся по направлению подготовки «Программная инженерия»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Под редакцией доктора технических наук, профессора Б. Г. Трусова
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Высшее профессиональное образование
  
  Рецензент — профессор Московского государственного технического университета имени Н. Э. Баумана, доктор техн. наук К. А. Майков
  
  Учебник создан в соответствии с Федеральным государственным образовательным стандартом по направлению подготовки 231000 «Программная инженерия» (квалификация «бакалавр»). Представлены разделы информатики, охватывающие основные вопросы теории информации, перевода чисел из одной системы счисления в другую, представления чисел и символов в памяти ЭВМ, представления и вывода знаний, функционирования аппаратного обеспечения, алгоритмизации, принципов работы различных программных продуктов, устройства вычислительных сетей. Для студентов учреждений высшего профессионального образования.
  
  УДК 621.391(075.8) ББК 32.81я73 Оригинал-макет данного издания является собственностью Издательского центра «Академия», и его воспроизведение любым способом без согласия правообладателя запрещается
  
  Парфилова Н. И., Пруцков А. В., Пылькин А. Н., Трусов Б. Г., 2012 Образовательно-издательский центр «Академия», 2012 Оформление. Издательский центр «Академия», 2012
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Информатика и программирование. Основы информатики : И741 учебник для студ. учреждений высш. проф. образования / Н. И. Парфилова, А. В. Пруцков, А. Н. Пылькин, Б. Г. Трусов ; под ред. Б.Г.Трусова. — М. : Издательский центр «Академия», 2012. — 256 c. — (Сер. Бакалавриат). ISBN 978-5-7695-8144-1
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  УДК 621.391(075.8) ББК 32.81я73 И741
  
  БД — база данных. БЗ — база знаний. ВЗУ — внешнее запоминающее устройство. КВЗУ — контроллер внешнего запоминающего устройства. КПВВ — контроллер порта ввода-вывода. МП — микропроцессор. ОЗУ — оперативное запоминающее устройство. ОС — операционная система. ПЗУ — постоянное запоминающее устройство. ПО — программное обеспечение. РГРТУ — Рязанский государственный радиотехнический университет. СУБД — система управления базами данных. ЭВМ — электронно-вычислительная машина. ЯВУ — язык высокого уровня. ARPAnet (Advanced Research Project Agency Network) — сеть управления перспективного планирования оборонных научно-исследовательских работ. CD (Compact Disc) — компакт-диск. CPU (Central Processing Unit) — центральный обрабатывающий модуль, микропроцессор. DNS (Domain Name System) — система доменных имен. DVD (Digital Versatile Disc) — цифровой универсальный диск. FAT (File Allocation Table) — таблица размещения файлов. FTP (File Transfer Protocol) — протокол передачи файлов. HTTP (Hypertext Transfer Protocol) — протокол передачи гипертекста. IMAP (Internet Message Access Protocol) — протокол доступа к интернет-сообщениям. IP (Internet Protocol) — интернет-протокол. NTFS (New Technology File System) — файловая система нового типа.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Список основных используемых сокращений и обозначений
  
  OSI (Open System Interconnection) — взаимодействие открытых систем. SMTP (Simple Mail Transfer Protocol) — протокол пересылки почты. TCP (Transmission Control Protocol) — протокол управления передачей. URL (Uniform Resource Locator) — унифицированный указатель ресурса. USB (Universal Serial Bus) — универсальная последовательная шина. WWW (World Wide Web) — Всемирная сеть.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Информационная революция второй половины ХХ в. — начала XXI в., связанная с изобретением и развитием микропроцессорных систем и созданием современных информационных коммуникаций, компьютерных сетей и систем передачи данных, привела к созданию новой отрасли — информационной индустрии, направленной на производство технических средств и создание новых технологий производства знаний. Возникновение новой индустрии производства знаний привело к глобальным изменениям в обществе — информатизации общества. Информатизация общества заключается в вовлечении всех его членов в общий процесс производства и реализации знаний на базе новых компьютерных и телекоммуникационных технологий. Информатизация общества потребовала от всех его членов определенного уровня информационной культуры, определенных базовых знаний и умения целенаправленно использовать в своей деятельности современные информационные технологии, технические средства и методы. Научным фундаментом процесса информатизации современного общества и развития информационной индустрии является новая научная дисциплина — информатика. Информатика — это базовая учебная дисциплина, охватывающая сведения о технических, программных и алгоритмических средств организации современных информационных систем и формирующая у обучаемого определенный кругозор, объем знаний, уровень алгоритмического мышления, а также практические навыки работы с конкретными программными системами, необходимыми для его дальнейшего обучения по применению информационных систем в определенных областях человеческой деятельности. При написании учебника авторами были поставлены две задачи. Во-первых, дать читателю как можно более полное представление о разделах информатики и задачах, которые решаются в каждом разделе. Во-вторых, изложить материал просто и понятно. Для этого используются примеры, поясняющие теоретический материал. Учебник состоит из 11 глав, каждая из которых посвящена одному из разделов информатики. В гл. 1 рассматривается структура информатики. Информатика изучает процессы обработки, представления и измерения информации. Информатика связана с другими науками, например с математикой, и включает в себя ряд разделов, изучающих теорию информа-
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ции, аппаратное и программное обеспечение ЭВМ, информационные системы и системы искусственного интеллекта. Глава основана на материалах работ [22, 24]. В гл. 2 рассматриваются основные понятия теории информации: информация и данные. Несмотря на то что информация не материальна, можно измерять количество, адекватность и качество информации. Для измерения информации используются вероятностный и объемный подходы. Вероятностный подход основан на понятии «энтропия». Объемный подход заключается в вычислении числа элементарных единиц информации (бит). Для написания главы использовались материалы работ [1, 2, 7, 15, 22, 26]. Гл. 3 посвящена информационным процессам, системам и технологиям. Информационными процессами называются любые операции с информацией: сбор, обработка, передача. Как правило, информационные процессы используются в информационных системах — программно-аппаратных комплексах для обработки информации. Информационные технологии — это процессы переработки исходной информации в вид, который необходим потребителю информации. Для получения информационного продукта применяются информационные процессы и системы. Использовались материалы работ [2, 10, 11, 24]. В гл. 4 рассматриваются системы счисления, использующиеся в ЭВМ. Для перевода числа из одной системы счисления в другую существуют правила перевода целой и дробной частей на основе арифметических операций сложения, умножения, целочисленного деления и получения остатка от деления. Использовалась публикация [24]. Гл. 5 посвящена представлению чисел и символов в памяти ЭВМ. Целые и вещественные числа и символы хранятся в виде последовательностей нулей и единиц. Форматы представления данных оптимизированы для ускорения логических и арифметических операций в ЭВМ. Использовались материалы работ [24, 38]. В гл. 6 рассмотрены логические основы построения ЭВМ. Приведены способы представления логических функций, методы перевода из одного представления в другое, методы минимизации логических функций. При написании главы использовались материалы работ [3, 14, 34]. Гл. 7 посвящена моделям представления знаний: логическим, фреймовым, продукционным моделям и семантическим сетям. В отличие от данных знания активны и способны порождать новые знания. Поэтому задачей модели представления является не только хранение знаний, но и обеспечение вывода новых знаний. Для каждой модели представления знаний приводится пример логического вывода. Данная глава основана на лекциях С. П. Хабарова [41] и других работах [4, 6, 16, 17, 18, 30, 31, 44]. В гл. 8 рассматривается аппаратное обеспечение ЭВМ, его составные части. Историю ЭВМ делят на четыре поколения. Пятое
  
  ФГБОУ ВПО «Тюменский государственный университет» ФГБОУ ВПО «Тюменский государственный университет»
  
  поколение существует лишь в теории и реализовано частично. Основой любой ЭВМ является микропроцессор, который выполняет логические и арифметические операции и связан системной шиной с запоминающими и периферийными устройствами. Для написания главы использовались материалы работ [1, 22, 27, 32, 42]. В гл. 9 рассматриваются основы алгоритмизации. Аппаратное обеспечение ЭВМ работает под управлением различных программ. В основе программ лежит алгоритм — последовательность действий, необходимых для достижения результата. В этой главе рассматриваются способы записи алгоритмов в виде блок-схем, структурограмм и словесно, основные алгоримические структуры, а также правила разработки и описания алгоритмов решения задач. Гл. 10 посвящена программному обеспечению ЭВМ. В главе рассматриваются различные типы программного обеспечения: операционные системы, драйверы устройств, архиваторы, базы данных. Разделы, посвященные текстовым и табличным процессорам, подготовлены на основе лекций по дисциплине «Пакеты прикладных программ». В основе главы лежат материалы работ [1, 5, 7, 9, 10, 11, 20, 22, 29, 32, 43]. Гл. 11 посвящена сетевым технологиям. В главе рассматриваются устройство и принципы функционирования локальных и глобальных сетей, основные протоколы передачи. В настоящее время большое значение в жизни общества имеет глобальная информационная сеть Интернет, ставшая средством для хранения и обмена информацией. Сеть Интернет включает в себя несколько служб: электронную почту, Всемирную сеть и службу передачи файлов, которые нашли широкое применение. Были использованы материалы работ [1, 2, 7, 10, 11, 26].
  
  Информатика — наука и вид практической деятельности
  
  1.1. Информатика и ее структура
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Информатика — это наука и вид практической деятельности, связанные с процессами обработки информации с помощью вычис лительной техники. Термин «информатика» произошел от слияния двух французских слов information (информация) и automatique (автоматика) и до словно определял новую науку об «автоматической обработке инфор мации». В англоязычных странах информатика называется сomputer science (наука о компьютерной технике). Информатика представляет собой единство разнообразных от раслей науки, техники и производства, связанных с переработкой информации с помощью вычислительной техники и телекоммуника ционных средств связи в различных сферах человеческой деятель ности. Основная задача информатики заключается в определении общих закономерностей процессов обработки информации: создания, пере дачи, хранения и использования в различных сферах человеческой деятельности. Прикладные задачи связаны с разработкой методов, необходимых для реализации информационных процессов с исполь зованием технических средств. Информатика включает в себя следующие разделы. I. Теоретическая информатика. Это часть информатики, вклю чающая в себя ряд подразделов, тесно связанных с другой наукой — математикой. В теории информации и кодирования изучается ин формация как таковая, ее свойства, способы измерения количества информации. Областью исследования теории алгоритмов и автоматов являются методы переработки информации с помощью вычислитель ных систем. Теория формальных языков и грамматик рассматривает правила построения простейших языков с небольшим числом син таксических конструкций, называемых языками программирования. Теория принятия решений и исследования операций связана с ис пользованием информации для принятия решений и оценки их опти
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  мальности. Теоретическая информатика использует математические методы для общего изучения процессов обработки информации. II. Вычислительная техника. Это раздел, включающий в себя общие принципы построения вычислительных систем. Примером вычислительной системы является персональный компьютер, или ЭВМ. Этот раздел не связан с вопросами физической разработки, реализации и производства элементов вычислительных систем. Здесь рассматривается архитектура вычислительных систем — соглашение о составе, назначении, функциональных возможностях и принципах взаимодействия элементов внутри вычислительных систем и вычислительной системы с другими устройствами. Примерами принципиальных, ставших классическими решений в этой области являются архитектура фон Неймана компьютеров первых поколений, шинная архитектура ЭВМ, архитектура параллельной или многопроцессорной обработки информации. III. Программирование. Это деятельность, направленная на разработку программного обеспечения вычислительной техники. Программирование делится на разделы, связанные с разработкой соответствующих типов программного обеспечения. Программное обеспечение, непосредственно управляющее составными частями вычислительной техники, называется системным. Системный уровень программного обеспечения составляют операционные системы. Служебное программное обеспечение — это архиваторы, антивирусы, программы управления файлами и папками. Служебное программное обеспечение предназначено для выполнения некоторых вспомогательных функций. Прикладное программное обеспечение — это программы для решения большинства задач пользователя. Прикладное программное обеспечение включает в себя офисные, графические, справочные программы, среды разработки программ и др. IV. Информационные системы. Это раздел информатики, связанный с решением проблем анализа потоков информации в различных сложных системах, их оптимизации, структурировании, принципах хранения и поиска информации по запросу пользователя. Примерами информационных систем являются информационносправочные, информационно-поисковые, глобальные системы или сети хранения и поиска информации. V. Искусственный интеллект. Это область информатики, в которой решаются сложнейшие проблемы, находящиеся на пересечении с психологией, физиологией, языкознанием и другими науками. Исторически сложились три основных направления развития систем искусственного интеллекта. Целью работ первого направления является создание алгоритмического и программного обеспечения вычислительных машин, позволяющего решать интеллектуальные задачи не хуже человека. В рамках второго подхода объектом исследований являются структура и механизмы работы мозга человека, а конечная цель заключается в моделировании функционирования
  
  1.2. Информатика в обществе
  
  1.3. Информатика в природе Информатика в природе характеризуется изучением информационных процессов, протекающих в биологических системах, использованием накопленных знаний при организации и управлении природными системами и созданием на их основе технических систем.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  В нашем информационном обществе огромную роль играют системы распространения, хранения и обработки информации. Подобно мировой системе связи возникает единая информационная среда, которая обеспечивает любому человеку доступ ко всей необходимой для него информации. Широкое внедрение компьютеров во все области человеческой деятельности, наряду с использованием интеллектуальных роботов, коренным образом изменило традиционную среду обитания людей. Растет число людей, профессионально занятых сбором, накоплением, распространением и хранением информации. Информация стала товаром, имеющим большую ценность. Переход к информационному обществу вызывает проблемы социального, правового, технического характера. Например, применение роботов на производстве приведет к полному изменению технологии, которая в наши дни ориентирована на участие в ней человека. Резко меняется подготовка членов нового общества к самостоятельной жизни. Уже ведутся поисковые работы в области создания новых форм обучения, которые заменят существующие традиционные формы. Полностью меняется номенклатура профессий, специальностей и способов организации труда. Все эти проблемы составляют объект исследования психологов, социологов, философов и юристов, которые работают в области информатики. Создаются автоматизированные обучающие системы (АОС), автоматизированные рабочие места (АРМ) для специалистов различного профиля, распределяемые банковские системы и многие другие, чье функционирование опирается на использование всего арсенала информатики.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  человеческого мозга. Третий подход ориентирован на создание смешанных человекомашинных или интерактивных интеллектуальных систем, на симбиоз возможностей человеческого и искусственного интеллектов. В данном разделе информатики решаются задачи машинного перевода, распознавания речи и рукописного текста, экспертные системы, некоторые игровые программы и др.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Здесь информатика основывается на трех самостоятельных науках. Биокибернетика — наука, которая решает проблемы, связанные с анализом информационно-управляющих процессов, протекающих в живых организмах, с диагностикой заболеваний и поиском путей их лечения и созданием соответствующих систем. Бионика — наука об использовании принципов работы живых организмов в искусственных объектах. Биогеоценология — наука, нацеленная на решение проблем, относящихся к системно-информационным моделям поддержания и сохранения равновесия природных систем и поиска таких воздействий на них, которые стабилизируют разрушающие воздействия человеческой цивилизации на биомассу Земли.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Основы теории информации
  
  2.1. Понятие информации
  
  Пример 2.1. Конспект лектора — это данные. Читая лекцию студентам, лектор передает содержание конспекта в виде сообщения. Студенты получают сообщение и таким образом принимают информацию, записывают ее, представляя информацию в виде данных. Здесь лектор является источником информации, а студенты — потребителями информации.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Обычно под информацией понимается совокупность сведений, расширяющая представление об объектах и явлениях окружающей среды, их свойствах, состоянии и взаимосвязях. Обмен информацией непрерывно происходит между людьми, между людьми и окружающим миром. Обмен информацией осуществляется посредством сообщений. Сообщение — это форма представления информации для ее последующей передачи в одном из следующих видов: • числовая форма, представленная цифрами; • текстовая форма, представленная текстами, составленными из символов того или иного языка; • кодовая форма, представленная кодами (например, кодами в двоичной системе счисления, кодами для сжатия или шифрования, кодами азбуки Морзе или азбуки для глухонемых и т. п.); • графическая форма, представляющая изображения объектов; • акустическая форма, представленная звуковыми сигналами; • видеоформа, представляющая телепередачи, видео- и кинофильмы в специальном формате. При работе с информацией всегда имеются источник и потребитель информации. При этом необходимо различать термины «информация» и «данные». Данные — это информация, представленная в некоторой форме (формализованном виде), что обеспечивает ее хранение, обработку и передачу.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Чтобы сообщение было передано от источника к потребителю, необходима некоторая среда — носитель информации. Примерами носителей информации являются воздух для передачи речи, лист бумаги и конверт — для отсылки текста письма. Сообщение передается с помощью сигналов. Сигнал — это физический динамический процесс, так как его параметры изменяются во времени. Когда параметр сигнала принимает конечное число значений и при этом все они могут быть пронумерованы, сигнал называется дискретным. Сообщение и информация, передаваемые с помощью
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  2.2. Непрерывная и дискретная информация
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Информации обладает следующими свойствами: • запоминаемость — способность воспринять информацию и хранить ее продолжительное время; • передаваемость — способность информации к копированию — восприятием ее другой системой без искажения; • воспроизводимость — характеризует неиссякаемость информации, т. е. при копировании информация остается тождественной себе. Свойство воспроизводимости не является базовым и тесно связано с передаваемостью; • преобразуемость — это способность информации менять способ и форму своего существования. Можно выделить три концепции информации, объясняющие ее сущность. П е р в а я концепция предложена американским ученым Клодом Шенноном и отражает количественно-информационный подход. Информация определяется как мера неопределенности события. Количество информации зависит от вероятности ее получения. Чем меньше вероятность получения сообщения, тем больше информации в нем содержится. Эта концепция получила широкое распространение в теории передачи и кодировании данных. В т о р а я концепция рассматривает информацию как свойство (атрибут) материи. Информация создает представление о природе, структуре, упорядоченности и разнообразии материи. В рамках этой концепции информация не может существовать вне материи, а значит, она существовала и будет существовать вечно, ее можно накапливать, хранить и перерабатывать. Т р е т ь я концепция основана на логико-семантическом подходе, при котором информация рассматривается как знание, которое используется для ориентировки, активного действия, управления или самоуправления.
  
  таких сигналов, также называются дискретными. Примером дискретной информации является текстовая информация, так как количество символов (букв) конечно и их можно рассматривать как уровни сигнала передачи сообщения. Если параметр сигнала является непрерывной во времени функций, то сообщение и информация, передаваемая этими сигналами, называются непрерывными. Примером непрерывного сообщения является человеческая речь, передаваемая звуковой волной, с меняющейся частотой, фазой и амплитудой. Параметром сигнала в этом случае является давление, создаваемое этой волной в точке нахождения приемника — человеческого уха. Непрерывное сообщение может быть представлено непрерывной функцией, заданной на некотором отрезке [а, b]. Дискретизация — это процесс преобразования непрерывного сигнала в дискретный сигнал с некоторой частотой. Для этого диапазон значений функции (ось ординат) разбивается на конечное количество отрезков равной ширины. Тогда дискретное значение определяется отрезком, в который попало значение функции, называемым шагом дискретизации. Чем меньше шаг дискретизации, тем ближе полученный дискретный сигнал к исход ному непрерывному сигналу, а следовательно, больше точность дискретизации.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Пример 2.2. На метеостанции каждые полчаса происходит замер температуры (рис. 2.1).
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Рис. 2.1. Дискретизация непрерывного сообщения
  
  Непрерывно меняющаяся температура замеряется в моменты x1, x2,…, xn. В журнал наблюдений записывается округленное значение температуры, являющееся дискретным значением. В данном примере получасовой промежуток является частотой дискретизации, шаг дискретизации равен 1, так как происходит округление до целого числа, а получасовые замеры температуры — процессом дискретизации.
  
  Важным условием практического использования информации является ее адекватность. Адекватность информации — это уровень соответствия образа, созданного на основе полученной информации, реальному объекту или явлению. Адекватность информации выражается в трех формах: • синтаксическая адекватность — это соответствие структуры и формы представления информации без учета ее смысла. Информация в виде данных обычно обладает синтаксической адекватностью; • семантическая (смысловая) адекватность — в отличие от синтаксической адекватности учитывает смысловое содержание информации; • прагматическая (аксиологическая, потребительская) адекватность — это соответствие ожидаемой ценности, полезности использования информации при выработке потребителем решений для достижения своей цели.
  
  2.4. Синтаксическая мера информации 2.4.1. Вероятностный подход Информация нуждается в измерении. На практике количество информации измеряется с точки зрения синтаксической адекватности. Исторически сложились два подхода к измерению информации: вероятностный и объемный. В 1940-х гг. К. Шеннон предложил вероятностный подход, а работы по созданию ЭВМ способствовали развитию объемного подхода. Рассмотрим вероятностный подход к измерению количества информации в соответствии с первой концепцией информации (см. подразд. 2.1).
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Пример 2.3. Заказчик послал подрядчику сообщение: «Вышлите, пожалуйста, объем выполненных работ для отчета в течение недели». Подрядчик прислал ответ через 10 дней: «Объем выполненных работ составил 3 млн руб.». Заказчик ожидал число (не график, не рисунок) и получил его, следовательно, информация синтаксически адекватна. Полученное число является объемом выполненных работ, следовательно, информация семантически адекватна. Подрядчик прислал сообщение с опозданием, и ценность информации в нем потерялась, так как отчет должен был быть составлен ранее, следовательно, информация прагматически неадекватна.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  2.3. Адекватность информации и ее формы
  
  H = H (α) = log 2 N =
  
  При N = 2 количество информации минимально и равно H = 1. Поэтому в качестве единицы информации принимается количество информации, связанное с двумя равновероятными состояниями системы, например: «орел» — «решка», «ложь» — «истина». Такая единица количества информации называется бит. Введем понятие вероятности. Вероятность события A — это отношение числа случаев M, благоприятствующих событию A, к общему количеству случаев N: Р=
  
  Следовательно, вероятность выпадения числа 6 при бросании кости: Р=
  
  Пример 2.5. Найти вероятность выпадения числа, большего 3, при бросании кости. Р е ш е н и е. Всего граней у кости N = 6. Чисел, больших 3, на гранях кости M = 3.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Пример 2.4. Найти вероятность выпадения числа 6 при бросании кости. Р е ш е н и е. Всего граней у кости N = 6. Число 6 присутствует только на одной грани.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Пусть система α может принимать одно из N состояний в каждый момент времени, причем каждое из состояний равновероятно. Например, в качестве системы могут выступать опыты с подбрасыванием монеты (N = 2) или бросанием игральной кости (N = 6). Количество информации системы α вычисляется по формуле, предложенной Р. Хартли:
  
  Если N состояний системы не равновероятны, т. е. система находится в i-м состоянии с вероятностью Pi и при этом все состояния системы образуют полную группу событий, т. е. сумма вероятностей равна 1: N
  
  то используются следующие формулы, предложенные Шенноном. Для определения количества информации: • в одном (i-м) состоянии системы Н = log 2 •
  
  среднего количества информации во всех состояниях системы: N
  
  N 1 = -∑ Pi log 2 Pi . Pi i =1
  
  Из приведенных выражений следует, что количество информации максимально, если состояния системы равновероятны. Пример 2.6. Вычислительная система может находиться в одном из N = 3 состояний: «включено (простой)», «вычисление», «выключено». Оператор получил сообщение о состоянии системы. Какое количество информации получил оператор? Рассмотреть два случая: 1) состояния системы равновероятны; 2) состояния системы не равновероятны; вероятность нахождения системы в состоянии «включено (простой)» P1 = 0,3; состоянии «вычисление» P2 = 0,5; состоянии «выключено» P3 = 0,2. Р е ш е н и е. В первом случае используем формулу Хартли: HХ = log2N = log23 = 1,58 бит. Во втором случае используем формулу Шеннона: N
  
  Н Ш = -∑ Pi log 2 Pi = -(0,3 log 2 0,3 + 0,5 log 2 0,5 + 0, 2 log 2 0, 2) = i =1
  
  = -(- 0,52 — 0,5 — 0, 46) = 1, 48 бит.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Следовательно, вероятность выпадения числа, большего 3, при бросании кости:
  
  Пример 2.7. В условиях задачи из примера 2.6 определить количество информации, которое получил оператор в сообщении о состоянии «выключено», вероятность которого P3 = 0,2. Р е ш е н и е. Используем формулу Шеннона для одного состояния: Н = log 2
  
  1 1 = log 2 = 2,32 бит. Pi 0, 2
  
  Можно сделать вывод: чем событие маловероятнее, тем больше информации может быть получено при его возникновении.
  
  2.4.2. Объемный подход
  
  Пример 2.8. Сообщение в двоичной системе счисления 10010010 имеет объем данных V = 8 бит. Этот объем данных представляется 1 байтом. Для удобства использования введены и более крупные единицы объема данных: 1 024 байт = 1 килобайт (Кбайт); 1 024 Кбайт = 1 мегабайт (Мбайт) = 1 0242 байт = 1 048 576 байт; 1 024 Мбайт = 1 гигабайт (Гбайт) = 1 0243 байт; 1 024 Гбайт = 1 терабайт (Тбайт) = 1 024 4 байт; 1 024 Тбайт = 1 пентабайт (Пбайт) = 1 0245 байт.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Объем данных V в сообщении измеряется количеством символов (разрядов) в этом сообщении. В информатике в основном используется двоичная система счисления, т. е. все числа представляются двумя цифрами: 0 и 1. Поэтому минимальной единицей измерения данных является бит. Таким образом, 1 бит — это либо 0, либо 1. Элемент, принимающий всего два значения, называется двухпозиционным и просто реализуется аппаратно: например, двумя состояниями «включено» — «выключено», «ток есть» — «ток отсутствует». Более подробно о системах счисления будет рассказано в гл. 3. Наряду с битом используется укрупненная единица измерения — байт, равная 8 бит.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Значение количества информации, вычисленное по формуле Хартли, больше значения, вычисленного по формуле Шеннона.
  
  Пример 2.9. В сообщениях используются только первые шесть букв латинского алфавита: A, B, C, D, E, F. Сколько байт необходимо для хранения сообщения «AABBCCD»? Р е ш е н и е. Определим, сколько бит необходимо для хранения одной буквы по формуле Хартли: VБ = log26 = 2,58. Результат округлим в большую сторону, следовательно: VБ = 3 бита.
  
  VС = M ⋅ VБ = 7 ⋅ 3 = 21 бит = 2,625 байт. Результат вновь округлим в большую сторону: VС = 3 байта.
  
  2.5. Показатели качества информации Эффективность использования информации для принятия решений определяется показателями ее качества. Рассмотрим основные показатели качества информации, и чем они определяются. Репрезентативность (объективность) определяется правильностью отбора и формирования информации в целях адекватного отражения свойств объекта. Содержательность зависит от семантической емкости, равной отношению количества семантической информации в сообщении к объему сообщения. Достаточность (полнота) — это минимальный, но достаточный для принятия правильного решения набор показателей. Как непол-
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Тремя битами можно представить 8 комбинаций: 000, 001, 010, 011, 100, 101, 110, 111. Для кодирования шести букв используются первые шесть комбинаций, а две последние комбинации не используются. Для сообщения, состоящего из M = 7 букв, необходимо
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Общий объем информации в книгах, цифровых и аналоговых носителях за всю историю человечества составляет по оценкам 1018 байт. Зато следующие 1018 байт будут созданы в течение пяти — семи лет. Отличие объема данных от количества информации заключается в следующем: объем данных выражается только целыми значениями, а количество информации — вещественными. Формулу Хартли можно использовать для определения объема данных. При этом результат округляется в большую сторону, так как минимальной ячейкой памяти в ЭВМ является байт. Поэтому, заняв только часть байта (его несколько бит), оставшаяся часть байта не используется.
  
  ФГБОУ ВПО «Тюменский государственный университет» ФГБОУ ВПО «Тюменский государственный университет»
  
  ная, т. е. недостаточная для принятия правильного решения, так и избыточная информация снижает эффективность принимаемых пользователем решений. Однако избыточная информация позволяет восстановить частично утраченную информацию. Например, в слове «дост*пнос*ь» потеряно 18 % букв, однако можно понять по оставшимся буквам, что это слово «доступность». Русский язык, как и другие естественные языки, обладает большой избыточностью. Доступность определяется степенью легкости восприятия и получения информации пользователем. Актуальность определяется степенью соответствия информации моменту ее использования. Своевременность определяется поступлением информации не позже заранее назначенного момента времени, зависящего от времени решения поставленной задачи. Точность — это степень близости получаемой информации к реальному состоянию объекта, процесса, явления и т. п. Достоверность — это вероятность того, что отображаемое информацией значение параметра отличается от истинного значения этого параметра в пределах необходимой точности. Устойчивость — это свойство информации реагировать на изменение исходных данных, сохраняя при этом необходимую точность. Устойчивость и репрезентативность обусловлены правильностью выбора метода отбора и формирования информации. Ценность определяется эффективностью принятых на основе полученной информации решений.
  
  Информационные процессы, системы и технологии
  
  3.1. Информационные процессы
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Операции над информацией называются информационными процессами. Люди обмениваются устными сообщениями, записками, посланиями. Они передают друг другу просьбы, приказы, отчеты о проделанной работе, описи имущества, публикуют рекламные объявления и научные статьи, хранят старые письма и документы или долго размышляют над полученными известиями. Все это примеры информационных процессов. Все информационные процессы можно отнести к одному из следующих классов. Сбор данных — это деятельность по накоплению данных с целью обеспечения достаточной полноты. В сочетании с методами анализа данных они порождают информацию, способную помочь в принятии решений. Например, на основе цены товара и его аналогов, их потребительских качеств мы принимаем решение: покупать или не покупать этот товар. Передача данных — это процесс обмена данными. Предполагается, что существует источник информации, канал связи и потребитель информации. Между ними устанавливаются соглашения о порядке обмена данными. Такие соглашения называются протоколами передачи данных. Например, в обычной беседе между двумя людьми негласно принимается соглашение: не перебивать друг друга во время разговора. Хранение данных — это поддержание данных в форме, постоянно готовой к выдаче их потребителю. Одни и те же данные могут потребоваться потребителю многократно, поэтому существуют способы их хранения на носителях, например на бумаге или запоминающих устройствах, и методы их выдачи по запросу потребителя. Обработка данных — это процесс преобразования информации из исходной формы до получения определенного результата. Сбор, накопление, хранение информации зачастую не являются конечной целью информационного процесса. Нередко первичные данные ис-
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  3.2. Информационные системы
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Информационные процессы могут осуществляться в рамках информационных систем. Информационные системы — это организованные человеком системы сбора, хранения, обработки и выдачи информации, необходимой для принятия эффективных решений. Задачей информационных систем является удовлетворение потребностей потребителя в информации. Потребитель должен своевременно получать информацию в требуемой форме после ее систематизации и необходимой обработки. Информационная система включает в себя следующие составные части: • информация, хранящаяся в информационной системе; • технические средства хранения и обработки данных; • методы и процедуры сбора и обработки информации. Для обеспечения функционирования информационной системы требуется квалифицированный персонал. Информационные системы характеризуются не только структурой, но и выполняемыми функциями. Функции информационных систем можно подразделить на два вида: • функции физической обработки; • функции содержательной обработки. Функции ф и з и ч е с к о й обработки заключаются в фиксации, сборе, кодировании и записи данных на внешних запоминающих устройствах (ВЗУ). Для обеспечения функций этого вида необходимо проведение следующих мероприятий: • исследование способов представления и хранения информации, создание специальных языков для формального описания информации различной природы, разработка специальных приемов сжатия и кодирования информации; • создание сетей хранения, обработки и передачи информации, в состав которых входят информационные банки данных, терминалы, обрабатывающие центры и средства связи. Функции содержательной обработки сводятся к поиску информации, документальному оформлению и размножению результатов поиска и обработки, передаче выходной информации потребителям. Примерами таких функций являются анализ и прогнозирование потоков разнообразной информации, перемещающихся в обществе, аннотирование объемных документов и реферирование их.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  пользуются для решения какой-либо проблемы. Данные преобразуются шаг за шагом в соответствии с алгоритмом обработки до получения выходных данных, которые после анализа пользователем предоставляют необходимую информацию.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Обеспечение функций этого вида требует осуществления следующих действий: • построение различных процедур и технических средств для их реализации, с помощью которых можно автоматизировать процесс извлечения информации из документов, не предназначенных для вычислительных машин, а ориентированных на восприятие их человеком; • создание информационно-поисковых систем, способных воспринимать запросы к информационным хранилищам, сформулированные на естественном языке, а также специальных языках запросов для систем такого типа. По типу выполняемых задач информационные системы можно разбить на три класса: • учетные системы, предназначенные для контроля и выдачи справочной информации; • аналитические системы, предназначенные для прогнозирования, диагностики, поддержки принятия решений; • решающие системы, предназначенные для управления и планирования. Классы информационных систем взаимосвязаны между собой. Каждый предыдущий класс является исходной базой для последующего, а каждый последующий предполагает возможность решения задач предыдущего класса. Например, аналитические системы помимо собственных задач выполняют справочные функции, а решающие системы решают задачи прогноза и контроля. Приведенная классификация позволяет разделить информационные системы на следующие уровни: • системы, не производящие качественного изменения информации; • системы, анализирующие информацию; • системы, вырабатывающие решения. Другим критерием, который может быть положен в основу классификации информационных систем, является тип обработки информации, осуществляемой в информационной системе. По этому признаку информационные системы можно разделить на три группы: • расчетные; • аналитико-статистические; • информационно-поисковые. Автоматизированные р а с ч е т н ы е информационные системы характеризуются небольшими объемами входной и выходной информации и значительным количеством вычислительных операций. Автоматизированные а н а л и т и к о — с т а т и с т и ч е с к и е информационные системы предназначены для сбора и обработки статистической информации. Они характеризуются большим объемом входной и выходной информации, а также большим количеством арифметических и логических операций.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Автоматизированные и н ф о р м а ц и о н н о — п о и с к о в ы е системы используются для ввода, хранения и постоянного обновления информации о некоторых объектах, например документах, людях, транспортных средствах. Эти объекты непрерывно находятся в динамике, что требует постоянного обновления информации о них. В процессе развития автоматизированных информационнопоисковых систем сформировались три вида информационного обслуживания: 1) документальное; 2) фактографическое; 3) концептографическое. Каждому из этих видов соответствует своя информационная система, представляющая собой подсистему общей информационной системы общества. Система д о к у м е н т а л ь н о г о обслуживания в течение долгого времени обеспечивала информационное обслуживание общества в целом и различных его институтов, в том числе науки и техники. Документальное обслуживание заключается в предоставлении потребителям первичных документов. Потребители самостоятельно извлекают необходимые сведения, удовлетворяя свои информационные потребности. Документальное обслуживание потребителя осуществляется в два этапа. На первом этапе потребителю предоставляется перечень релевантных (соответствующих) его запросу первичных документов, т. е. документов, содержание которых имеет смысловое соответствие информационному запросу или другому тексту. Этот этап называется библиографическим, и он аналогичен поиску книги в библиотечном каталоге. На втором этапе после отбора потребителем из этого перечня некоторых пертинентных документов ему предоставляют эти документы. Пертинентность — это соответствие содержания документа информационной потребности конкретного специалиста. Этот этап называется библиотечным обслуживанием. Он аналогичен получению книг, выбранных ранее из библиотечного каталога. Таким образом, документальное обслуживание удовлетворяет потребность в информации опосредованно, через первичные документы. Ф а к т о г р а ф и ч е с к о е обслуживание в отличие от документального удовлетворяет информационные потребности членов общества непосредственно, т. е. представляя им необходимые сведения: отдельные данные и факты. Запрашиваемые потребителем сведения извлекаются из первичных документов после определенной обработки: поиска, анализа и сравнения. Под термином «фактографическая информация» следует понимать сведения не только фактического характера, но и теоретического, предположительного, оценочного характера, т. е. факты, концепции
  
  Информация является таким же важнейшим ресурсом современного общества, как уголь, нефть, металлы, а значит, процесс ее переработки, как и процессы переработки материальных ресурсов, можно назвать технологией. Информационная технология — это процесс, использующий совокупность средств и методов сбора, обработки и передачи данных о состоянии объекта, процесса или явления для получения новой информации об их состоянии. Таким образом, информационная технология — это процесс переработки первичной информации в информационный продукт.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  3.3. Информационные технологии
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  и все то, что может быть объектом извлечения из текста, описания на определенном информационном языке, хранения и поиска в той или иной информационной системе. Если в случае документального и фактографического обслуживания потребителю информации предоставляются документы или сведения, извлеченные из информационного потока в «натуральном» виде, то при к о н ц е п т о г р а ф и ч е с к о м обслуживании все эти документы и сведения подвергаются интерпретации, оценке, обобщению со стороны информационной системы. В результате такой интерпретации формулируется так называемая ситуативная информация, содержащая в себе оценку рассматриваемых сведений, тенденции и перспективы развития отдельных научных и технических направлении, рекомендации. По этой причине под концептографическим обслуживанием можно также понимать формулирование и доведение до потребителей ситуативной информации, в явном виде не содержащейся в анализируемых источниках и полученной в результате информационно-логического и концептографического анализа некоторой совокупности документов. Другими словами, в случае концептографического обслуживания потребителю предоставляются не только сведения о документе или сами сведения из документа, но и некоторая дополнительная информация, привнесенная информационной системой в процессе их интерпретации. Для каждого из видов информационного обслуживания существует свой собственный специфичный ряд вторичных документов, на основе которого производится обслуживание. Поэтому каждый вид обслуживания сводится к созданию ряда вторичных документов и предоставления их потребителю. Разработка информационных систем на основе высокопроизводительных технических устройств и современных средств создания программного обеспечения значительно повысила эффективность их работы и сделала информационные системы неотъемлемой частью жизни общества.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Целью информационной технологии является производство информации для ее анализа человеком и принятия на его основе решения о выполнении соответствующих действий. К техническим средствам производства информации относится его аппаратное, программное и математическое обеспечение. С их помощью производится переработка первичной информации в информацию нового качества. Программное обеспечение является инструментарием информационных технологий, которое позволяет достичь поставленную пользователем цель. В качестве инструментария можно использовать следующие виды программных продуктов: • текстовые процессоры и графические редакторы; • настольные издательские системы; • электронные таблицы; • системы управления базами данных (СУБД); • информационные системы функционального назначения (финансовые, бухгалтерские, для маркетинга и пр.). Информационная технология тесно связана с информационными системами, которые являются для нее основной средой. Информационная технология является процессом, состоящим из четко регламентированных правил выполнения операций, действий, этапов разной степени сложности над данными, хранящимися в компьютерах. Основная цель информационной технологии — в результате целенаправленных действий по переработке первичной информации получить необходимую для пользователя информацию. Информационная система является средой, составляющими элементами которой являются компьютеры, компьютерные сети, программные продукты, базы данных (БД), обслуживающий персонал, различного рода технические и программные средства связи и т. д. Основная цель информационной системы — организация хранения и передачи информации. Информационная система и обслуживающий ее персонал представляют собой человекокомпьютерную систему обработки информации. Реализация функций информационной системы невозможна без знания ориентированной на нее информационной технологии. Информационная технология может существовать и вне сферы информационной системы. Таким образом, информационная технология является более емким понятием, отражающим современное представление о процессах преобразования информации в информационном обществе. Умелое сочетание двух информационных технологий (управленческой и компьютерной) является залогом успешной работы информационной системы. Рассмотрим некоторые виды информационных технологий. Информационная технология о б р а б о т к и д а н н ы х предназначена для решения хорошо структурированных задач, для которых
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  определены все необходимые входные данные и известны алгоритмы и другие стандартные процедуры их обработки. Эта технология применяется для автоматизации некоторых рутинных постоянно повторяющихся несложных операций управленческого труда. Поэтому внедрение информационных технологий и систем позволяет существенно повысить производительность труда персонала, освободить его от рутинных операций и, возможно, привести к необходимости сокращения численности работников. Информационная технология обработки данных решает следующие задачи: • обработка данных об операциях, производимых фирмой; • создание периодических контрольных отчетов о состоянии дел в фирме; • получение ответов на всевозможные текущие запросы и оформление их в виде бумажных документов или отчетов. Целью информационной технологии у п р а в л е н и я является удовлетворение информационных потребностей всех без исключения сотрудников фирмы, имеющих дело с принятием решений. Эта технология ориентирована на работу в среде информационной системы управления и используется при худшей структурированности решаемых задач, если их сравнивать с задачами, решаемыми с помощью информационной технологии обработки данных. Информационная технология управления идеально подходят для удовлетворения сходных информационных потребностей работников различных функциональных подсистем (подразделений). Поставляемая ими информация содержит сведения о прошлом, настоящем и вероятном будущем фирмы. Эта информация имеет вид регулярных или специальных управленческих отчетов. Для принятия решений информация должна быть представлена в агрегированном виде так, чтобы просматривались тенденции изменения данных, причины возникших отклонений и возможные решения. На этом этапе решаются следующие задачи обработки данных: • оценка планируемого состояния объекта управления; • оценка отклонений от планируемого состояния; • выявление причин отклонений; • анализ возможных решений и действий. Главной особенностью информационной технологии п о д д е р ж к и п р и н я т и я р е ш е н и й является качественно новый метод организации взаимодействия человека и компьютера. Выработка решения, что является основной целью этой технологии, происходит в результате итерационного процесса, в котором участвуют: • система поддержки принятия решений в роли вычислительного звена и объекта управления; • человек как управляющее звено, задающее входные данные и оценивающее полученный результат вычислений на компьютере.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Окончание итерационного процесса происходит по воле человека. В этом случае можно говорить о способности информационной системы совместно с пользователем создавать новую информацию для принятия решений. Дополнительно к этой особенности информационной технологии поддержки принятия решений можно указать еще ряд ее отличительных характеристик: • ориентация на решение плохо структурированных (формализованных) задач; • сочетание традиционных методов доступа и обработки компьютерных данных с возможностями математических моделей и методами решения задач на их основе: • направленность на непрофессионального пользователя компьютера; • высокая адаптивность, обеспечивающая возможность приспосабливаться к особенностям имеющегося технического и программного обеспечения, а также требованиям пользователя.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  4.1. Непозиционная и позиционная системы счисления
  
  Пример 4.1. Записать число 1974 в системе римских цифр. Р е ш е н и е. Выпишем тысячи, сотни, десятки и единицы: 1 000 — M; 900 — CM; 70 — LXX; 4 — IV. Тогда число 1974 будет записано как MCMLXXIV. Здесь цифра M сохраняет свой количественный эквивалент 1 000 в обоих вхождениях.
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Система счисления — это соглашение о представлении чисел посредством конечной совокупности символов (цифр) A = , называемой алфавитом. Каждой цифре ставится в соответствие определенный количественный эквивалент. Системы счисления разделяют на позиционные и непозиционные. Рассмотрим эти системы счисления. Непозиционная система счисления — это система, в которой цифры не меняют своего количественного эквивалента в зависимости от местоположения (позиции) в записи числа. К непозиционным системам счисления относится система римских цифр, основанная на употреблении латинских букв для десятичных разрядов I = 1, X = 10, С = 100, М = 1 000 и их половин V = 5, L = 50, D = 500. Рассмотрим запись единиц. Числа 1 и 5 представляются соответственно цифрами I и V. Чтобы представить числа 2 или 3 необходимо записать соответствующее число единиц: II или III. Для представления чисел 4 или 9 к цифре V (пять) или X (десять) слева дописывается единица I: IV или IX. Для представления чисел 6, 7, 8 к цифре V справа подписываются соответствующее число единиц: VI, VII, VIII. Аналогично записываются десятки, сотни и тысячи. Число в системе римских чисел записывается по схеме «тысячи — сотни — десятки — единицы».
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Значение числа, представленного конечной дробью, в n-ичной системе счисления: amam–1 … a1a0,a–1a–2 … a–k, где «,» — разделитель целой и дробной частей; ai (i = −k, m); или с явным указанием основания системы счисления (a ma m–1 … a 1a 0, a–1a–2 … a-k)n, определяется по формуле am nm + am-1nm-1 +…+ a1n1 + a0 n0 + +a-1n-1 + a-2 n-2 +…+ a- k n- k =
  
  В информатике и вычислительной технике широко используются следующие системы счисления: • двоичная n = 2; используемый алфавит: A = ; например, 01110002;
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  4.2. Двоичная, десятичная и шестнадцатеричная системы счисления. Перевод чисел в десятичную систему счисления
  
  ФГБОУ ВПО «Тюменский государственный университет»
  
  Непозиционные системы счисления обладают следующими недостатками: • сложность представления больших чисел (больше 10 000); • сложность выполнения арифметических операций над числами, записанными с помощью этих систем счисления. Из-за перечисленных недостатков числа принято записывать с помощью позиционных систем счисления. Позиционная система счисления — это система, в которой количественный эквивалент цифры зависит от ее положения в числе. Примером позиционной системы счисления является используемая нами десятичная система счисления. Основание позиционной системы счисления — это количество символов в ее алфавите. Например, в десятичной системе счисления десять цифр, поэтому она имеет основание n = 10. Позиционная система счисления с основанием n называется n-ичной. Далее рассматриваются только позиционные системы счисления, поэтому слово «позиционная» опускается.
  
  Т а б л и ц а 4.1. Соответствие между цифрами двоичной, десятичной и шестнадцатеричной систем счисления Двоичная система счисления
  
  Шестнадцатеричная система счисления
  
  МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ХАРЬКОВСКАЯ НАЦИОНАЛЬНАЯ АКАДЕМИЯ ГОРОДСКОГО ХО ЗЯЙСТВА ОСНОВНЫЕ ПРИНЦИПЫ ГЕОИНФОРМАЦИОННЫХ СИСТЕМ Учебное пособие
  
  Синергетика является одной из важнейших составляющих постнеклассического этапа развития науки, ее развитие формирует новые смыслы категорий и концепций эволюционизма, информационного подхода. В данной статье дана характеристика новых работ по методологическим и философским проблемам синергетики (включая современные подходы к емкому понятию «информация»), отражена суть критицизма приложений концепций синергетики в исторических исследованиях в дискуссиях последних лет.
  
  Download Free PDF View PDF
  
  The article discusses the methodology for the study and reconstruction of archaeological and historical monuments, based on non-destructive methods of geophysics and geoinformatics. The proposed methodology provides means for collecting and analyzing diverse factual material and implies integrated approach when creating archaeological geoinformation reconstructions. The practical application is demonstrated on the examples of two monuments: Hotov hillfort of Scythian time and Inkerman galleries, the historical and archaeological site of WWII. The reconstruction of spatial structure of Hotov hillfort with disperse buildings along the defensive system and the lack of buildings in its central part is presented. These results confirm previous research data about configuration and area of the hillfort and are important for understanding the spatial organization of Ukrainian Forest-Steppe hillforts at the Scythian period. Diverse experimental data, summarized and analyzed by means of GIS, led to important conclusions about the state of rock massif, cavity space volume, the degree of preservation of tunnels and galleries of Inkerman and the way of their utilization during the World War II. В статье предложена методика изучения и ре- конструкции памятников археологии и истории, базирующаяся на неразрушающих методах геофи- зики и геоинформатики. Процесс исследования, от этапа натурных измерений и накопления данных до археолого-геоинформационных реконструкций, продемонстрирован на примере двух памятников: Хотовского городища скифского времени и истори- ко-археологического объекта Великой отечествен- ной войны Инкерманские штольни.
  
  Download Free PDF View PDF
  
  The proposed teaching and methodological guide «Methods and technologies of space monitoring of waste disposal sites in the interests of ensuring the ecological safety of the territories», developed in the framework of joint activities of the Russian State University of Oil and Gas. I. Gubkin, Research Institute «AEROKOSMOS» of the Ministry of Education and Science of the Russian Academy of Sciences, Moscow Institute of Open Education of the Department of Education of the City of Moscow (Department of Innovative and Space Technologies in Integrated Training), is devoted to one of the most urgent problems of our time — the problem of pollution of the terrestrial land, water areas and atmosphere human activity. In today’s world, there are many so-called. global problems of mankind [1], which include: 1. The problem of «Rich-Poor»; 2. Global warming; 3. Terrorism; 4. Social degradation and crime; 5. Non-admission of thermonuclear war; 6. Pollution of the environment; 7. Depletion of natural resources. But in the world community «shrinks the ring», becoming ever more relevant with the years, another global problem that can be attributed to a separate group. This is the problem of production and consumption waste, it can be conditionally divided into several components of diverse components: 1. Formation of «garbage morality» in society. 2. Restoration of the environment, degraded due to landfills. 3. Rapid growth of littering areas. 4. Complexity and high cost of waste processing. 5. Currently, for many types of waste, processing technologies have not been developed. 6. Control of issues of design, operation and reclamation of landfills. 7. Soil degradation (salinization, bogging, desertification), pollution of the atmosphere and water resources due to the influence of waste. 8. Negative impact of waste on flora and fauna. 9. Growth of chronic incidence of residents in the vicinity of polygons of solid domestic and industrial waste. The set of theoretical and practical measures on the problem of waste disposal facilities (dumps) includes the following components: 1. Theory of dumps — classification and classification of dumps, causes, sources of occurrence, consequences, mathematical models, dynamics, calculations of polygons, terminology, structure, composition, surface components, etc .; 2. Harbology — waste recycling technologies, waste classifications and classifiers, waste patterns, causes, sources of occurrence, consequences, etc .; 3. Investigation of chemical processes in landfills (waste degradation) — biochemical, photodegradation, water and space degradation of waste; 4. Ecological monitoring of dumps — theoretical information, research history, future research in the field of ground, air and space monitoring of the dumps; 5. Activities to reduce the environment’s littering — see below; 6. Waste management activities — development and implementation of business plans for waste management; 7. Activities to change attitudes of people to the problem of dumps. These problems are of an international nature.
  
  Download Free PDF View PDF
  
  Семакин Информатика 11кл.
  
  ф о р м а т и И. Семакин, Е. Хеннер 2-е издание Д о п у щ е н о Министерством образования Российской Федерации в качестве учебника по информатике для учащихся 11 классов общеобразовательных учреждений Средняя школа № 25 г. Дачькегсрск класс Москва БИНОМ. Показать больше
  
  ф о р м а т и И. Семакин, Е. Хеннер 2-е издание Д о п у щ е н о Министерством образования Российской Федерации в качестве учебника по информатике для учащихся 11 классов общеобразовательных учреждений Средняя школа № 25 г. Дачькегсрск класс Москва БИНОМ. Лаборатория знаний 2 0 0 5 Спрятать
  - Похожие публикации
  - Поделиться
  - Код вставки
  - Добавить в избранное
  - Комментарии
  Похожие публикации:

Сколько ячеек содержит диапазон a1 z5

Saved searches

Use saved searches to filter your results more quickly

beatsey/minorProjects

Name already in use

Sign In Required

Launching GitHub Desktop

Launching GitHub Desktop

Launching Xcode

Launching Visual Studio Code

Latest commit

Git stats

Files

README.md

Информатика и программирование основы информатики 9785769581441

Citation preview

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ХАРЬКОВСКАЯ НАЦИОНАЛЬНАЯ АКАДЕМИЯ ГОРОДСКОГО ХО ЗЯЙСТВА ОСНОВНЫЕ ПРИНЦИПЫ ГЕОИНФОРМАЦИОННЫХ СИСТЕМ Учебное пособие

Семакин Информатика 11кл.

Добавить комментарий Отменить ответ