Обратная польская запись

 

Алгоритм:

Пока строка содержит символы для чтения, читаем очередной символ. Далее рассматриваются варианты:
1) Если символ не является символом функции или скобкой, добавляем его к выходной строке.
2)

  1. Если встретили символ функции, помещаем его в стек.
  2. Если встретили символ функции и при этом стек не пустой, выталкиваем в выходную строку все символы функции, пока не встретим символ, имеющий больший приоритет или открывающую скобку.
  3. Если символ является закрывающей скобкой:
    Выталкиваем элементы из стека в выходную строку, пока верхним элементом стека не станет открывающая скобка. Если после этого на вершине стека находится символ функции, выталкиваем его в выходную строку.
  4. Если символ является открывающей скобкой, помещаем его в стек.

Код на Ideone.

e-olymp 4050. Забавная игра

Ссылка на задачу.

Засчитанное решение.

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

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

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

Входные данные

Первая строка содержит два целых числа: n и k, разделённые пробелом. Здесь n — количество аэропортов (n1000), а k — номер аэропорта, являющегося начальной точкой игры (1kn). Следующая n−1 строка содержит пары целых чисел, разделённых пробелами. Это номера аэропортов, соединённых рейсом. Все рейсы двусторонние и упомянуты только один раз. Каждый аэропорт соединён рейсами не более, чем с 20 другими.

Выходные данные

Если игрок, начинающий игру, выигрывает, программа должна написать «First player wins flying to airport L«, где L— номер аэропорта, в который игрок должен вылететь из текущего. Если таких аэропортов несколько, программа должна выбрать вариант с меньшим номером аэропорта. Если начинающий игрок проигрывает, программа должна написать «First player loses«.

Определяем массив аэропортов, булев массив пройденных аэропортов уровень вложенности функции dfs(), переменную запоминающую вторую вершину, булевы переменные для определения победителя, отсортированных вершин. В функции мы отмечаем первую вершину как пройденную переходим на следующий уровень. Сортируем все возможные варианты перехода, выбираем наименьший подходящий нам. Далее определяем переменную, которая считает вершины, в которые можно пойти из данной. В цикле проходим все вершины, пока проходим считаем количество детей.
Если оно равно нулю то это тупик.
И мы посмотрим кто бы выиграл если бы бандиты дошли до этого аэропорта.Если level нечетный, то мы ищем правильный ход первого, иначе второго террориста. Если уровень равен 1, то мы уже выходим. Выводим ответ. Иначе, если level не равен 1, то мы еще не дошли до конца и возвращаем выше, кто выигрывает в данном узле.
При этом каждый бандит ищет ветку где бы он победил.
Определяем количество детей. Если мы не в тупике, то но увеличивается на 1. Далее, если ходит второй террорист, то он выбирает ветку, в котором выиграет он. Если мы попали в тупик, выводим кто выиграл в зависимости от четности пройденного пути.
В main() считываем количество аэропортов и номер первого , записываем в вектора смежные аэропорты для каждого и запоминаем первую вершину. Запускаем dfs().

А 1041

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

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

Определяем переменные: количество слонов, длинна и ширина шахматного поля, массив клеток поля. Далее определяем булевы переменные для добавления и удаления диагоналей, расположения слонов, выхода из рекурсии. Функция «giagonal» осуществляет все операции с диагоналями. Добавляет/удаляет диагонали(параллельные главной или побочной). Она принимает булевы переменные для определения того, добавляем мы главную диагональ или побочную, собираемся мы добавлять диагональ или удалять. А также координаты начала диагоналей, координаты расположения слона.  Если клетку бьет какой-либо слон, прибавляем к ее значению 1. При этом число свободных клеток уменьшается. Если же мы удаляем диагональ, то просто уменьшаем количество бьющих данную клетку слонов (это указывается в самой клетке). Если удаленный слон был единственным, кто ее бил, увеличиваем число свободных клеток. Функция «space». Она используется как для удаления, так и для добавления диагоналей. В ней мы запоминаем последнее расположение слонов на доске и далее ищем начало прохода диагоналей. Для этого сначала мы определяем в какой части доски находится поставленный слон и исходя из этого, если оказалось, что координата по горизонтали больше координаты по вертикали, то следовательно начало первой диагонали будет в первой строке, в противном случае ее начало будет в первом столбце. Вторые координаты зависят от разности j-i. При поиске начала второй диагонали используем сумму i+j, если эта сумма меньше 8 (то есть слон находится ближе к верхнему левому углу доски, чем к правому нижнему) тогда диагональ начинается в первом столбце. Функция «find_permutation» (рекурсивно расставляет слонов). С каждой новым поставленным слоном увеличиваем переменную level, для определения в последствии момента установки последнего слона. Просматриваем клетки, если какая-то из них не под боем-ставим туда слона и запускаем функцию «space» для него. Так расставляем их, пока число слонов не достигнет 8. Если после какой-либо расстановки мы нашли правильный ответ, то используя булеву переменную isEnd выходим из рекурсии. Если после установки восьмого слона оказалось, что все поля были заполнены, то мы выводим: «Ответ найден» и печатаем доску (если булева переменная is_set — true, то есть этот элемент слон, тогда выводим 1, остальные клетки — 0). Далее выходим из всех циклов, определив переменную isEnd = true. Удаляем слонов и битые ими поля. Конец программы.

ideone.com

e-olymp 4. Две окружности

Две окружности

Ссылка на засчитанное решение.

Определить количество точек пересечения двух окружностей.
Входные данные

6 чисел x1, y1, r1, x2, y2, r2, где x1, y1, x2, y2 — координаты центров окружностей, а r1, r2 – их радиусы. Все числа — действительные, не превышают по модулю 1000000000, заданы не более чем с 3-мя знаками после запятой.

Выходные данные

Количество точек пересечения. Если точек пересечения бесконечно много, то вывести -1.

Считываем данные, далее если координаты центров и длины радиусов совпадают печатаем: «-1». Затем рассматриваем варианты, когда окружности имеют одну, две общих точки либо не имеют ни одной.

Код на Java:

Код Ideone

Засчитанное решение на e-olimp

e-olymp 974. Флойд-1

974. Флойд-1

Ссылка на засчитанное решение.

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

Входные данные

В первой строке записано количество вершин графа n (1n100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

Выходные данные

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

Код программы:

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

e-olymp 625. Расстояние между вершинами

Задача с сайта e-olimp № 625.

Ссылка на засчитанное решение.

РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ

Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.

Входные данные

Первая строка входного файла содержит натуральные числа N, M, S и F (N5000, M100000, 1S, FN, SF) — количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.

Следующие M строк содержат по три натуральных числа bi, ei и wi — номера концов i-ого ребра и его вес соответственно (1bi, eiN, 0wi100000).

Выходные данные

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

Код программы:

После считывания входных данных создаем три массива. Массив вершин входящих в кратчайший путь, а также два массива для преобразования считанной матрицы в матрицу смежности  вершин графа. Далее с помощью алгоритма Дейкстра находим кратчайшее расстояние до каждой вершины и одновременно записываем в  массив [latex]h\left [ n \right ][/latex] вершины, через которые проходит кратчайший путь. Затем выводим расстояние до вершины [latex]f[/latex] если путь к ней существует, иначе печатаем: «-1». Далее выводим кратчайший маршрут между вершинами [latex]s[/latex] и [latex]f[/latex].

А710

Дана матрица A размера [latex]m*n[/latex]. Получить транспонированную матрицу A*(ее размер [latex]n*m[/latex]).

n m А А*
5 4
 5 6
4  3

Код программы:

Считываем матрицу [latex]n*m[/latex], а затем создаем транспонированную матрицу, в которой строки исходной матрицы являются столбцами и наоборот. Выводим A*.

Код программы.

АА5

В заданной строке удалить все пробелы. Если пробелов не было, выдать сообщение об этом, иначе напечатать количество удаленных пробелов.

Ввод Вывод
Однажды во дворе стояла ясная погода. Однаждыводворестоялаяснаяпогода.
5
Единство предмета речи — это тема высказывания. Единствопредметаречи—этотемавысказывания.
6
Слово. Слово.
Пробелов не было.

Код программы:

Вводим строку из стандартного потока ввода. Используем getline. Вводим счетчик пробелов.
Проходя по элементам строки, если встречаем пробел, то увеличиваем счетчик на 1 и удаляем элемент. Потом возвращаемся обратно и в случае обнаражения пробела, удаляем его.  Печатаем строку. Если пробелов в строке не было выводим: «Пробелов не было.» Иначе выводим число пробелов, которые были удалены.

Ссылка на ideone.com.

Код на Java:

 

 

Ю12.2

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

Текст
There are many big and small libraries everywhere in our country.
They have millions of books in different languages.
Every school has a library.
Pupils come to the library to take books on different subjects.
Результат

Код программы:

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

Алгоритм:

Описываем и считываем строки. Затем описываем количество пробелов в строке и длину самой длинной строки (относительно которой и будет производится выравнивание по правому краю).

При проходе строк создаем счётчик для подсчета пробелов. Создаем строку и вводим в нее форматированный вариант представления строки на которую указывает указатель i, потом убираем ведущий пробел. Увеличиваем счетчик каждый раз когда встречаем пробел.  Убираем ведущий пробел.

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

Затем второй проход строк.

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

Смещаем  указатель проходящий все символы в строке. Теперь оставшиеся пробелы вставляем в начало чтобы выровнять строку по правому краю.

Для проверки работы программы можно воспользоваться объектом.

 

Какой треугольник?

Задача: 905. Какой треугольник? с сайта http://www.e-olimp.com.ua Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон. Существование треугольника и корректность исходных данных гарантируется. Технические условия Входные данные В единственной строке задано 3 целых числа — длины сторон треугольника. Длины сторон не превышают 100. Выходные данные В единственной строке вывести 1, если треугольник равносторонний, 2 если равнобедренный и 3 если разносторонний.

Первая сторона Вторая сторона Третья сторона Результат
2 2 2 1
3 4 3 2
4 7 14 3

Код программы:

Задача решена методом моделирования. Вычисления проведены согласно условию, представленному в задаче. По условию задачи необходимо проверить каким является треугольник: равносторонним, равнобедренным или разносторонним. Для этого создаем массив из трех элементов(сторон треугольника), считываем его. Далее, если все элементы массива равны, то треугольник равносторонний, иначе, если две стороны равны, то он равнобедренный, если ни то, ни то не выполняется, то он разносторонний. Для проверки работы программы можно воспользоваться объектом. Ссылка на e-olimp: http://www.e-olymp.com/ru/submissions/2319469 Второй вариант:

http://www.e-olymp.com/ru/submissions/2319474

Код на Java:

Второй вариант:

e-olymp 6277. Покупка воды

Задача №6277 с сайта e-olimp.com.

Стоимость бутылки воды, учитывая стоимость пустой бутылки, составляет 1 грн 20коп., а стоимость пустой бутылки 20 коп.
Сколько бутылок воды можно выпить на [latex]n[/latex] грн, учитывая, что пустые бутылки можно сдавать, и на полученные деньги приобретать новые бутылки воды.

Входные данные
Натуральное число [latex]n[/latex] (1 [latex]n[/latex] 1000).

Выходные данные
Количество бутылок воды, которое можно выпить на [latex]n[/latex] грн.

[latex]n[/latex] Результат
2 1
10 9
0.7 0

Код программы:

Задача решена методом моделирования. Вычисления проведены согласно условию, представленному в задаче. По условию задачи необходимо узнать сколько можно выпить бутылок имея [latex]n[/latex] грн. Для этого описываем и считываем количество денег [latex]n[/latex], а также создаем счетчик, определяющий сколько бутылок воды в итоге можно купить. Затем создаем цикл, в котором пока мы имеем достаточно средств покупаем воду за 1.2 грн и сразу же сдаем бутылку за 0.2 грн, в результате количество денег уменьшается на 1, а счетчик увеличивается на 1. Когда количество денег станет меньше 1.2 грн выходим из цикла и печатаем количество купленных бутылок.
Для проверки работы программы можно воспользоваться объектом.

Имеется альтернативный линейный вариант решения:

http://ideone.com/ClAaK4
Решение принято

Код на Javа:

А412б

Задача. Даны две целочисленные квадратные матрицы порядка 6.
Найти последовательность из нулей и единиц [latex]b_{1}[/latex], \ldots, [latex]b_{6}[/latex] такую, что [latex]b_{i} = 1[/latex], когда
б) все элементы i-х строк первой и второй матриц
отрицательны;

[latex]M_1[/latex] [latex]M_2[/latex]  [latex]b_1, \dots, b_6[/latex]
-2 -3 -4 -5 -6 -7
1  2  3  3  3  3
1  1  1  1  1  1
1  1  1  1  1  1
1  1  1  1  1  1
1  1  1  1  1  1
-1 -2 -3 -6 -7 -2
1  2  2  2  2  2
4  4  4  4  4  4
1  1  1  1  1  1
1  1  1  1  1  1
1  1  1  1  1  1
1 0 0 0 0 0
-7 -31 -4 -9 -8 -7
5  3  2  9  5  3
-4 -1 -1 -2 -8 -5
1  2  1  3  1  1
1  7  1  1  4  1
1  23  1  8  1  1
-1 -2 -3 -6 -7 -2
1  2  2  2  2  2
-4 -9 -4 -12 -7 -4
3  1  1  5  1  1
6  13  11  1  19 1
24  1  5  7  1  9
1 0 1 0 0 0
4 -37 12 -5 8 -7
-16 -8 -9 -3 -2 -3
-4 -1 -1 -2 -8 -5
-3 -2 -1 -2 -1 -7
3  7  1  1  4  1
1  23  1  8  8  1
-1 -2 -3 -6 -7 -2
-1 -2 -2 -2 -2 -2
-8 7 -4 15 -6 -4
-3 -7 -1 -5 -22 -1
6 13 11 12 19 1
24  1  5  7  1  11
0 1 0 1 0 0

Код программы:

По условию задачи необходимо вывести последовательность [latex]b_{1}, \ldots, b_{6}[/latex] из «1» и «0», при том «1» выводится если в соответствующих строках двух вводимых с клавиатуры матриц все элементы отрицательные. Для этого опишем две матрицы порядка 6 на 6 и два счетчика. Затем создадим циклы для ввода элементов матриц. Потом присваиваем элементам последовательности [latex]b_{1}, \ldots, b_{6}[/latex]  1.  Затем в цикле при условии, что элементы матрицы не отрицательные присваиваем [latex]B[i][/latex]  0  и выходим  из цикла. Если в строке двух матриц не встретилось ни одного числа большего либо равного 0, то  [latex]b_{i}[/latex] осталось равным 1. И выводим массив [latex]b[i][/latex].
Для проверки работы программы можно воспользоваться объектом.

 

Код на Java:

Ю4.29

Текущий минимум. Каждый из элементов [latex] t_{i}[/latex] массива [latex]T(m)[/latex] заменить минимальным среди первых [latex]i[/latex] элементов этого массива.

[latex]m[/latex] [latex]t_{1}, t_{2},\ldots,t_{i}[/latex]  Результат:
6 9
7
8
5
14
1
9
7
7
5
5
1
5 3
-2
5
-3
8
3
-2
-2
-3
-3
4 12
0
4
-7
12
0
0
-7

Код программы:

По условию задачи необходимо выводить текущий минимум введенных элементов массива.
Для этого опишем количество элементов, которое вводится с клавиатуры (так как это целое число, оно имеет тип «int»). Затем описав массив, считываем первый элемент массива и присваиваем переменной минимум его значение. После необходимо создать цикл для ввода остальных элементов массива. При условии, что текущий элемент меньше предыдущего, переприсваиваем минимум. Все элементы массива заменяем минимальным. Остается только вывести все текущие минимумы.
Для проверки работы программы можно воспользоваться объектом.

 

Код на Java:

 

Ю3.43

Текущая стоимость оборудования. Фирма ежегодно на протяжении [latex]n[/latex] лет закупала оборудование стоимостью соответственно [latex]s_{1},s_{2}\ldots,s_{n}[/latex] руб. в год (эти числа вводятся и обрабатываются последовательно).Ежегодно в результате износа и морального старения(амортизации) все имеющееся оборудование уценяется на [latex]p[/latex]%. какова общая стоимость накопленного оборудования за n лет?

   [latex]p[/latex]    [latex]n[/latex] [latex]s_{1}, s_{2},\ldots,s_{n}[/latex] Результат:
10 6 5
8
10
58
18
43
5.000000
12.500000
21.250000
77.125000
87.412500
121.67125
28 4 12
7
14
33
12.000000
15.640800
25.260800
51.187776
15 4 24.5
31.78
0
11.51
24.500000
52.60500
44.714250
49.517113

Код программы:

По условию задачи нужно вычислять общую стоимость оборудования, которое ежегодно уценяется на определенный процент. Вначале вводим переменные: [latex]n[/latex] с типом данных «int», так как это количество лет и переменные [latex]p[/latex] и [latex]s[/latex] с типом «double». Потом считываем процент уценки и количество лет. Далее создаем цикл в котором считываем стоимость оборудования, с каждым годом  уценяем ее по формуле: [latex]S=S*(100-p)/100[/latex] и суммируем со стоимостью только что закупленного оборудования.
Для проверки работы программы можно воспользоваться объектом.

А165з

Даны действительные числа [latex]a_{1}, a_{2}, \cdots [/latex].
Известно, что [latex]a_{1}>0[/latex] и что среди [latex]a_{2}, a_{3},[/latex]… есть хотя бы одно отрицательное число. Пусть [latex]a_{1},[/latex]…,[latex]a_{n}[/latex] – члены данной последовательности, предшествующие первому отрицательному члену ([latex]n[/latex] заранее неизвестно). Получить з)
[latex](-1)^n \cdot a_{n}[/latex].

Последовательность [latex](-1)^n \cdot a_{n}[/latex] Результат:
2  5  6  3  8  7  -3 7 Тест пройден
4.67  9  14  8  3.5  -4 -3.5 Тест пройден
0  7  12  -5  3.3  -4  2 12 Тест пройден
-7  4  3.8  9.62  8 0 Тест пройден

Код программы:

Continue reading

Ю2.20

Как успеть подешевле? Можно ехать на такси со скоростью [latex]v_{1}[/latex] км/ч и оплатой [latex]p_{1}[/latex] pуб/км либо идти пешком со скоростью [latex]v_{2}[/latex] км/ч бесплатно. Как с наименьшими затратами преодолеть путь [latex]s[/latex] за время [latex]t[/latex], если это возможно? Каковы эти затраты?

v1 v2 s t p1 Результат:
30 5 18 2 4 0
50.44 4 75.7 3 5.5 174.975969
62 5 800 5 7 No time
8 17 60 3 8 0

Код программы:

По условию задачи нужно выяснить, как с наименьшими затратами преодолеть путь [latex]s[/latex] за время [latex]t[/latex], если это возможно. Вводим переменные с типом данных “double”, так как переменные входят в множество действительных чисел. Необходимо рассмотреть несколько случаев.
Первый случай, когда можно успеть добраться пешком, то есть [latex]s/v_{2}<t[/latex], следовательно оплата равна [latex]0[/latex].
Второй случай, когда скорость пешком больше или равна скорости такси. Если при этом пешком успеть нельзя, тогда выводим «No time», если пешком успеем, то оплата равна 0.

Третий случай, когда можно часть пути проехать на такси, а остаток пройти пешком так, чтобы затраты были минимальными. Для этого надо формулу: [latex]s=v_{1} \cdot t_{1}+v_{2} \cdot t_{2}[/latex] преобразовать в вид: [latex]s=t_{1} \cdot v_{1}+t \cdot v_{2}-t_{1} \cdot v2[/latex] и выразить [latex]t_{1}[/latex], введя переменную [latex]T[/latex](минимальное время езды на такси).
[latex]T = (s-t \cdot v_{2}) / (v_{1}-v_{2})[/latex].
В результате получаем формулу:
[latex]p=(T \cdot v_{1}) \cdot p_{1}[/latex] и считаем [latex]p[/latex].
И наконец четвертый случай,  если невозможно успеть вовремя ни на такси, ни пешком.
Для проверки работы программы можно воспользоваться объектом.

 

Код программы на Java:

Ссылка на Java код.

Ю3.3

Точки внутри эллипса. Для заданных [latex]a[/latex] и [latex]b[/latex] найти все точки с целочисленными координатами, находящиеся внутри эллипса [latex]\frac{x^2}{a^2}+\frac{y^2}{b^2}\leq 1[/latex]. Полезно, используя процедуру GoToXY в Паскале,  вывести найденные координаты точек в форме эллипса.

a b Результат:
1 1 (-1,0);(0,-1);(0,0);
(0,1);(1,0)
2 1 (-2,0);(-1,0);(0,-1);(0,0)
(0,1);(1,0);(2,0)
3 2 (-3,0);(-2,-1);(-2,0);(-2,1);
(-1,-1);(-1,0)(-1,1);(0,-2);
(0,-1);(0,0);(0,1);(0,2);
(1,-1);(1,0);(1,1);
(2,-1);(2,0);(2,1);(3,0)

Код программы:

По условию задачи нужно для заданных [latex]a[/latex] и [latex]b[/latex] найти все точки с целочисленными координатами, находящиеся внутри эллипса.

Вводим переменные [latex]a[/latex] и [latex]b[/latex] с типом данных «float», а [latex]x[/latex] и [latex]y[/latex] с типом «int», так как нам нужны точки с целочисленными координатами.

Пусть [latex](x,y)\in Z^2[/latex] ,[latex] a>0[/latex], [latex] b>0[/latex] и [latex]\frac{x^2}{a^2}+\frac{y^2}{b^2}\leq 1[/latex] .

Тогда [latex]\frac{x^2}{a^2}+y\leq 1\rightarrow[/latex] [latex]0\leq \frac{y^2}{b^2}[/latex][latex]\leq 1-\frac{x^2}{a^2}\rightarrow[/latex][latex]0\leq 1-\frac{x^2}{a^2}\Leftrightarrow[/latex][latex]\frac{x^2}{a^2}\leq 1\Leftrightarrow [/latex][latex]x^2\leq a^2 \Leftrightarrow[/latex] [latex]-a\leq x\leq a\Leftrightarrow[/latex]
[latex][-a]\leq x\leq [a][/latex].
Аналогичным образом получаем, что обязано выполняться двойное неравенство [latex][-b]\leq x\leq [b].[/latex]

С геометрической точки зрения, полученные результат означает, что все точки эллипса, имеющие целочисленные координаты, лежат внутри прямоугольника [latex]\left \{ \right.(x,y)\in R^2|[-a]\leq x\leq [a]; [-b]\leq x\leq [b]\left. \right \}[/latex] .
Перебрав все целочисленные точки этого прямоугольника и отобрав те из них, которые удовлетворяют неравенству эллипса, решим задачу.

Для проверки работы программы можно воспользоваться объектом.

 

Код программы на Java:

Ю1.20

Приближение [latex]\sin(x)[/latex]. Функция [latex]y=\sin(x)[/latex] на отрезке [latex][0;\frac{\pi}{2}][/latex] хорошо аппроксимируется разложением: [latex]y=x-\frac{x^3}{6} + \frac{x^5}{120}[/latex]. Для заданного значения аргумента [latex]x[/latex] вычислить [latex]y[/latex] по этой формуле и сравнить с точным значением, вычисленным с помощью стандартной функции [latex]\sin[/latex].

x Ответ: Комментарий:
0 0 Тест пройден
0.5 0.000002 Тест пройден
1 0.000196 Тест пройден
1,57 0,004509 Тест пройден

Код программы:

По условию задачи необходимо для заданного значения аргумента [latex]x[/latex] вычислить [latex]y[/latex] по этой формуле и сравнить с точным значением, вычисленным с помощью стандартной функции [latex]\sin[/latex]. Вводим переменную [latex]x[/latex] c типом данных «float»,
так как нам потребуются не только целые числа на отрезке [latex][0;\frac{\pi}{2}][/latex].

После введения числа  выводим модуль разности значения [latex]\sin(x)[/latex] и значения функции по формуле:

[latex]f=x-\frac{x^3}{6}+\frac{x^5}{120}[/latex].
Погрешность при аппроксимации функции возрастает с увеличением [latex]x[/latex]. На отрезке [latex]x \in [0;0.4][/latex] погрешности практически нет, начиная с [latex]x=0.5[/latex] погрешность возрастает и в точке [latex](\frac{\pi}{2})[/latex], [latex]b[/latex](погрешность) составляет 0.004509. При [latex]x>\frac{\pi}{2}[/latex] она становится значительной, поэтому формула [latex]f=x-\frac{x^3}{6}+\frac{x^5}{120}[/latex] подходит лишь для аппроксимации на отрезке [latex][0;\frac{\pi}{2}][/latex].
Для выполнения программы и проверки тестов можно воспользоваться следующим объектом.

 

Код программы на Java:

А53

Задача: Даны действительные числа [latex]a,b,c,d,e,f,g,h.[/latex] Известно, что точки [latex](e,f)[/latex] и [latex](g,h)[/latex] различны. Известно также, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] не лежат на прямой [latex]l[/latex], проходящей через точки [latex](e,f)[/latex] и [latex](g,h)[/latex]. Прямая [latex]l[/latex] разбивает координатную плоскость на две полуплоскости. Выяснить, верно ли, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] принадлежат одной и той же полуплоскости.

a b c d e f g h Комментарий:
1 1 1 1 1 1 1 1 (a,b) и (c,d) принадлежит
разным полуплоскостям
2 3 7 5 6 3 5 2 (a,b) и (c,d) принадлежат
одной полуплоскости
3 1545 3455 4 42 656,1 3445 1,56 (a,b) и (c,d) принадлежат
разным полуплоскостям

Код программы:

По условию задачи нужно выяснить, верно ли, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] принадлежат одной и той же полуплоскости. Вводим переменные с типом данных «float», так как координаты входят в множество действительных чисел.   Определяем  взаимное расположение точек с помощью  уравнения прямой:  [latex]f=(x-e)(h-f)-(y-f)(g-e)[/latex] .

Если точки лежат в одной полуплоскости, то [latex](a-e)*(h-f)-(b-f)*(g-e)[/latex] и
[latex](c-e)*(h-f)-(d-f)*(g-e)[/latex] – должны быть числами одного знака, если же их знаки противоположны, то точки лежат в разных полуплоскостях.

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом.

 

Код программы на Java: