This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| package com.javarush.task.task05.task0532; |
| import java.io.*; |
| /* |
| Задача по алгоритмам |
| */ |
| public class Solution |
| public static void main(String[] args) throws Exception |
| BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); |
| int n = Integer.parseInt(reader.readLine()); |
| if(n |
| int maximum = Integer.parseInt(reader.readLine()); |
| for (int i = n; i > 1; i—) |
| maximum = Math.max(Integer.parseInt(reader.readLine()), maximum); |
| System.out.println(maximum); |
| > |
| > |
Пишем программу: нахождения НОД и НОК двух чисел | Алгоритм Евклида
ricciotto-in-nebbia commented Nov 7, 2018
Задача по алгоритмам
Написать программу, которая:
- считывает с консоли число N, которое должно быть больше 0
- потом считывает N чисел с консоли
- выводит на экран максимальное из введенных N чисел.
Требования:
1. Программа должна считывать числа с клавиатуры.
2. Программа должна выводить число на экран.
3. В классе должен быть метод public static void main.
4. Нельзя добавлять новые методы в класс Solution.
5. Программа должна выводить на экран максимальное из введенных N чисел.
IgorBrykin commented Mar 26, 2020
Это реально «Пушка».
Спасибо!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Footer
You can’t perform that action at this time.
Источник: gist.github.com
3. Решение простых алгоритмических задач
При написании программ в качестве входного и выходного потоков использовать стандартные потоки ввода и вывода.
При решении задач аккуратно форматируйте код согласно правилам. Давайте переменным и функциям значимые имена. Прежде чем сдавать программу преподавателю, проверьте, что она правильно работает на более чем 10 различных входных данных.
В каждой задаче ответьте на вопрос о том, как растет время работы программы и используемая программой память с ростом параметра размера входных данных (например, параметра n).
3.1. «Max». Написать программу, которая выводит максимальное число из n заданных чисел. В первой строчке входа дано число n, а в следующей строчке указано n целых чисел.
Линейные программы. Решение задач. Ч.1.
3.2. «Числа Фибоначчи I». Написать программу, которая по данному n находит n-е число Фибоначчи Fn. Числа Фибоначчи определяются соотношениями
Подсказка: организуйте цикл, в котором по последним двум вычисленным числам будет вычисляться следующее. Необходимо ли хранить в памяти все вычисленные числа Фибоначчи?
3.3. «Числа Фибоначчи II». Решить предыдущую задачу, используя идею рекурсии. Оценить число элементарных операций, которое необходимо сделать в рекурсивном и нерекурсивном алгоритмах вычисления числа Fn.
3.4. «Биномиальные коэффициенты». Написать программу, которая для данного натурального числа n находит коэффициенты в разложении
Оценить, как растет время работы вашей программы с ростом n.
3.5. «Простые числа». Написать программу, которая определяет, является ли введенное число n простым.
3.6. Написать программу, вычисляющую площадь односвязной прямоугольной фигуры, заданной перечислением пар целочисленных координат её вершин в произвольном порядке.
3.7. «Задача Иосифа». N человек, имеющие номера от 1 до N и расположившиеся по кругу друг за другом, считаются считалкой, состоящей из M слов. Расчет начинается с номера 1. Человек, на котором считалочка заканчивается – выбывает. А расчет (этой же считалочкой) продолжается с участника, следующего за выбывшим. Написать программу, которая для заданных N и M сообщает (в порядке выбывания) номера трех игроков, выбывших последними.
3.8. «Уравнение». Написать программу, которая в указанном интервале находит нетривиальный корень уравнения tg x = x с погрешностью 10 –10 . Сколько итераций необходимо сделать, чтобы достичь указанной точности методами деления пополам, Ньютона, простых итераций?
4. Жадные алгоритмы
4.1. «Атлеты». Написать программу, которая находит «башню» из атлетов максимальной высоты. Атлеты характеризуются двумя параметрами – массой и силой. Сила равна максимальной массе, которую атлет может держать на плечах. Известно, что если атлет тяжелее, то он точно сильнее. Подсказка: упорядочьте атлетов по силе и стройте башню сверху.
Вверх естественно поместить самого слабого. Входом является число атлетов n и n пар (масса, сила).
4.2. «Отрезки». Написать программу, которая для множества заданных отрезков находит минимальное подмножество отрезков, объединение которых покрывает отрезок S = [0, 10000]. Число отрезков и координаты их концов заданы на входе. Все координаты целочисленные. Подсказка: покрывайте отрезок S пошагово, двигаясь слева направо. На каждом шаге будет непокрытая часть [x, 10000].
Из оставшихся отрезков выбирайте тот, который урежет непокрытую часть до [y, 10000], где y максимальное. Решите эту задачу за время O(n log n), где n – количество данных отрезков.
4.3. «Коммивояжер». Написать программу, которая, используя один из возможных жадных алгоритмов, находит на плоскости ломаную линию, идущую из A в B по всем заданным точкам A1, A2, A3, …, An>, как можно меньшей длины. Есть ли такие входные данные, когда написанная программа находит не самый короткий путь? Если есть, приведите пример.
Источник: studfile.net
Собеседование по алгоритмам: задача Иосифа Флавия
В 67 году н.э. во время иудейско-римской войны Иосиф Флавий и сорок мятежников оказались в ловушке в пещере. Предпочтя самоубийство плену, они решили встать в круг и убивать каждого третьего из оставшихся в живых. Иосиф Флавий хотел остаться в живых и понял, где он должен стоять в кругу, чтобы остаться в живых в череде казней. Так он выжил, чтобы рассказать эту легенду.
На следующем собеседовании по алгоритмам вам может попасться алгоритмическая задача, основанная на этой легенде. По кругу стоят мятежников, пронумерованных от до . Начиная с нулевого, они убивают по кругу каждого -го оставшегося в живых. Обозначим через номер мятежника, оставшегося последним. Напишите программу, которая по данным и находит . Пример ниже показывает, что .
Ниже мы рассмотрим несколько алгоритмов для решения этой задачи. Читать вам будет гораздо интереснее, если вы перед прочтением придумаете алгоритм для этой задачи самостоятельно: во-первых, полезно потренироваться решать задачи с собеседований; во-вторых, решение гораздо лучше запоминается, если придумать его самостоятельно; в-третьих, удовольствие и уверенность, полученные от самостоятельного решения, мало с чем сравнятся =) Ниже мы приводим наглядную визуализацию и подробные описания алгоритмов.
Наивный алгоритм
Наивный способ решения задачи — промоделировать: завести массив размера , в котором отмечать, кто из мятежников всё ещё жив, и, проходя массив слева направо, отмечать каждого -го (из всё ещё живых) как убитого. Код на Python:
def josephus(n, k): alive = [True] * n num_survivors, current_position, index = n, 0, 0 while num_survivors: if alive[current_position]: index += 1 if index == k: num_survivors = num_survivors — 1 if not num_survivors: return current_position else: alive[current_position] = False index = 0 current_position = (current_position + 1) % n
Время работы работы этого алгоритма — : после каждого прохода по массиву количество живых мятежников уменьшается примерно в раз, поэтому понадобится примерно проходов. Ниже мы построим более простой и быстрый алгоритм.
Быстрый алгоритм
После того, как первый мятежник убит, остаётся та же самая задача: по-прежнему убивают каждого -го, но всего мятежников теперь , у них другие номера и убийства начинаются уже не с нулевого, а с мятежника с номером .
Новые и старые номера мятежников связаны такой формулой:
Это приводит к такому рекуррентному соотношению:
В свою очередь, это рекуррентное соотношение легко переделывается в рекурсивный алгоритм со временем работы . Код на Python:
def josephus(n, k): return 0 if n == 0 else (josephus(n — 1, k) + k) % n
Ещё более быстрый алгоритм
Оказывается, что для частного случая, когда , можно построить ещё более быстрый алгоритм! Опять же, мы настоятельно рекомендуем вам попробовать придумать его самостоятельно. Решение можно найти в видео выше или в нашей интерактивной книге «Алгоритмические задачи с собеседований» (см. раздел 5.11, он доступен бесплатно; до 19 января действует промокод HABR, дающий скидку 40%).
Источник: habr.com