Программирование. Ветвления и циклы

Тема «Программирование. Ветвления и циклы»

Цель: развитие навыков решения практико-ориентированных задач, по возможности позволяющие расширение и/или оптимизацию.

1. Найти все “пифагоровы” тройки натуральных чисел, наибольшее из которых не превосходит N (Тройка натуральных чисел называется пифагоровой, если сумма квадратов двух из них равна квадрату третьего).
2. Вычислить квадратный корень из заданного числа х с точностью Е по итерационному методу Ньютона по формуле:

3. Два параллельных зеркала А и В обращены друг  к другу. При падении луча на зеркало А он  ослабляется на Т[%], а при его падении на зеркало В -на Р[%]. Определить, после скольких  отражений луч, попеременно отражаясь то от  зеркала А, то от зеркала В, ослабеет более чем  в 50 раз. Первоначально он попадает на зеркало А.
4. В водохранилище каждые сутки поступает Т [м3] воды, а расходуется R [ м3] на орошение полей  и испарение, к тому же ежесуточно теряется  А (1-EXP(-V)) [м3] воды на просачивание  в почву, где А – коэффициент , V – объем воды в водохранилище. Определить, за сколько дней объем воды в водохранилище  уменьшится на Р [%] заданного первоначального объема  V0. Принять А = 100.
5. На железнодорожном пути находится N разрозненных вагонов. К ним движется вагон с кинетической энергией W, он сцепляется с ближайшим вагоном, затем вместе с ним движется дальше, сцепляясь с очередным вагоном, и т.д. При каждой сцепке расходуется 20% имеющейся кинетической энергии, еще Р[ Дж ] затрачивается на то, чтобы стронуть с места неподвижный вагон и, если энергия не истрачена полностью, движение продолжается. Определить, сколько вагонов окажутся сцепленными.
6. Найти число в последовательности Фибоначчи  большее заданного числа М и его порядковый  номер. Члены ряда Фибоначчи вычисляются по формуле:   F(1) = F(2) = 1 F(k) = F(k-1) + F(k-2), k > 2
7. Вычислить сумму ряда. Суммирование осуществлять, пока разность между преды­дущим и текущим членами остается больше 0.04. Кроме суммы, вывести на экран значение последнего слагаемого и его номер.
8. Написать программу, которая “задумывает” число в диапа­зоне от 1 до 10 и предлагает пользователю угадать число за 5 по­пыток. Ниже представлен рекомендуемый вид экрана во время работы программы (данные, введенные пользователем, выделе­ны полужирным шрифтом).

Игра “Угадай число”.

Компьютер “задумал” число от 1 до 10.

Угадайте его за 5 попыток.

Введите число и нажмите <Enter>

•> 5 Нет.

•> 3

Вы выиграли! Поздравляю!

9. В числовую переменную ввести не превышающее 32000 натуральное число, опреде­лить, является ли оно “совершенным”, и выдать на экран соответствующее сообще­ние. Предусмотреть проверку правильности ввода информации. “Совершенным” называется натуральное число, равное сумме всех своих делителей, исключая само число. Например: 28 = 1+2+4+7+14.
10. Продав квартиру, вы получили $ 100 000 и положили их банк. Банк начисляет 1% в первый месяц, а каждый следующий — тоже 1%, но уже с получившейся суммы. Сколько   денег   будет   в   банке   на   вашем   счету   через   год? 
11. Кролики и Рекуррентные соотношения

Последовательность представляет собой упорядоченную совокупность элементов (обычно цифр), в которой допускается наличие дубликатов. Последовательности могут быть конечным или бесконечным. Два примера конечная последовательность: ( π, – 2-√, 0 , π)(π,-2,0,π),  и бесконечная последовательность нечетных чисел: ( 1 , 3 , 5 , 7 , 9 , … )(1,3,5,7,9,…)/ Мы используем обозначения а_n для представления n-ый члена последовательности.

Рекуррентное соотношение– соотношения вида “следующий через предыдущих”, то есть отношение, когда значение f(n) описывается через f(m), где n > m. f – функция целого аргумента, обычно натурального или целого неотрицательного. В случае кроликов фибоначиевых из введения, любой месяц будет содержать кроликов , которые были живы в предыдущем месяце, плюс любое новое потомство. Ключевое наблюдение состоит в том, что число потомков в любом месяце равно числу кроликов, которые были живы за два месяца до начала. В результате, если F_N представляет число пар кроликов в живых после того, как прошел NN-ый месяц, то мы получим последовательность Фибоначчи, имеющие условия F_N которые определяются рекуррентным соотношением F_N= F_{N – 1}+ F_{N – 2}  (с F1= F2=1 инициировать последовательность). 

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

Формат входных данных: Положительные целые числа N ≤ 40, а также K ≤ 5.

Формат выходных данных: Общее количество пар кроликов , которые будут присутствовать через N месяцев, если мы начинаем с 1 парой и в каждом поколении, каждая пара воспроизводства возраста кроликов производит помет К пары кроликов (а не только 1 пара).

Пример:

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

Расширение задачи:

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

Формат входных данных: Положительные целые числа N≤100 а также М ≤ 20.

Формат выходных данных: Общее количество пар кроликов, которые будут оставаться после того , как N-ый месяц, если все кролики живут M месяцев.

Пример:

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

12. Лифт

Чтобы поднять на -й этаж M-этажного дома новый холодильник, Витя вызвал бригаду грузчиков. Оплата работы грузчиков рассчитывается так: за подъем холодильника на один этаж требуется заплатить A рублей, за спуск на один этаж – B рублей. За подъем и спуск на лифте плата не взимается. Несмотря на то, что в доме есть лифт, Вите, возможно, все же придется заплатить грузчикам, поскольку лифт останавливается только на каждом K-м этаже, начиная с первого (то есть на этажах с номерами 1, K+1, 2K+1, 3K+1, …). Нужно вычислить, какой минимальной суммы денег достаточно, чтобы грузчики доставили холодильник с первого этажа на N-й.

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

Первая строка содержит целые числа A и B – стоимость подъема и спуска на один этаж (1 ≤ A,B ≤ 1000);

Вторая строка содержит целое число M – количество этажей в доме (1 ≤ M ≤ 1000000);

Третья строка содержит целое число N – номер этажа, на который нужно доставить груз (1 ≤ N ≤ M);

Четвертая строка содержит целое число K – период остановки лифта (1 ≤ K < M).

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

Одно число – минимальная стоимость подъема холодильника.

Примеры

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

13. Спички

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

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

Первая строка – N (1 ≤ N < 10⁸) – число квадратов.

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

Одно число – минимальное число спичек.

Примеры

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

14. Покупка

Покупатель имеет купюры достоинством A(1), …,A(n), а продавец – B(1), .. ,B(m). Необходимо найти максимальную стоимость товара Р, которую покупатель не может купить, потому что нет возможности точно рассчитаться за этот товар с продавцом, хотя денег на покупку этого товара достаточно.

15. Ханойские башни

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

Hеобходимо перенести диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, так, чтобы диски на стержне C располагались в том же порядке, в каком они располагаются на диске A перед перемещением.

При перемещении никогда нельзя класть больший диск на меньший.