(A) Напишите функцию int min (int a, int b, int c, int d), находящее наименьшее из четырех данных чисел. Функция main дожна считывать четыре числа с клавиатуры, вызывать функцию min, выводить результат ее работы на экран. 
(B) Напишите функцию double power (double a, int n), вычисляющую значение an . Функция main должна считывать числа a и n, вызывать функцию power, выводить результат ее работы на экран. 
© Напишите функцию bool Xor (bool x, bool y), реализующую функцию "Исключающее ИЛИ" двух логических переменных x и y. Функция Xor должна возвращать true, если ровно один из ее аргументов x или y, но не оба одновременно равны true. Функция main в программе должна запрашивать значения переменных x и y, (два числа, равных 0 или 1), вызывать функцию Xor(x,y) и выводить результат на экран. 
(D) Напишите "функцию голосования" bool Election(bool x, bool y, bool z), которая возвращает то значение (true или false), которое среди значений ее аргументов x, y, z встречается чаще. Функция main должна запрашивать три числа, равных 0 или 1, вызывать функцию Election и выводить результат на экран. 
(E) Напишите функцию bool IsPrime (int n), возвращающую true, если натуральное число n>1 простое, и false, если составное. 
Функция main должна запрашивать число с клавиатуры, вызывать функцию IsPime, выводить строку prime, если число простое или composite, если число составное. 

Указание: число является составным, если оно имеет натуральный делитель, отличный от 1 до n. Программа должна проверить делимость числа n на все числа от 2 до n-1 и вернуть false при нахождении нетривиального делителя. Для того, чтобы проверить, что число n делится на число d нацело, необходимо сравнить остаток от деления n на d с нулем. 

Рекурсия
                      Эпиграф:
                        void ShortStory()
                        {
                            cout<<"У попа была собака, он ее любил."<<endl;
                            cout<<"Она съела кусок мяса, он ее убил,"<<endl;
                            cout<<"В землю закопал и надпись написал:"<<endl;
                            ShortStory();
                        }

Как мы видели выше, функция может вызывать другую функцию. Но функция также может вызывать и саму себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что 0!=1, 1!=1. А как вычислить величину n! для большого n? Если бы мы могли вычислить величину (n-1)!, то тогда мы легко вычислим n!, поскольку n!=n(n-1)!. Но как вычислить (n-1)! ? Если бы мы вычислили (n-2)!, то мы сможем вычисли и (n-1)!=(n-1)(n-2)!. А как вычислить (n-2)! ? Если бы... В конце концов, мы дойдем до величины 0!, которая равна 1. Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на C++: 

     int factorial (int n)
     {
         if (n==0)
             return 1;
         else
             return n*factorial(n-1);
     }

Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция называется рекурсивной. 

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

Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку if (n==0), то factorial(0) вызовет factorial(-1), тот вызовет factorial(-2) и т.д. 
Рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет вызывать factorial(n), то также получиться бесконечная цепочка. 
Поэтому при разработке рекурсивной функции необходимо прежде всего оформлять условия завершения рекурсии и думать, почему рекурсия когда-либо завершит работу. 

Упражнения
(B) Напишите рекурсивную функцию возведения в степень, пользующуюся следующим свойством: an=a*an-1. 
(F) Напишите функцию возведения в степень, которая работала бы как для положительных, так и для отрицательных значений n: a-n=1/an. 
(G) Напишите функцию быстрого возведения в степень, которая пользовалась бы следующими свойствами: an=(an/2)2 при четном n, an=a*an-1 при нечетном n. Подумайте, сколько умножений выполнит эта функция для вычисления an? 
(H) Последовательность Фибоначчи определена следующим образом: φ0=1, φ1=1, φn=φn-1+φn-2 
при n>1. Начало ряда Фибоначчи выглядит следующим образом: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Напишите функцию int phi(int n), которая по данному натуральному n возвращает φn. Функция n должна считывать значение n и выводить значение n-го числа Фибоначчи. 

(I) Для биномиальных коэффициентов (числа сочетаний из n по k) хорошо известна рекуррентная формула: Cnk=Cn-1k-1+Cn-1k. Вычислите значение Cnk пользуясь этой формулой и учитывая, что Cn0=Cnn=1. 
(J) Головоломка "Ханойские башни" состоит из трех колышков, пронумерованных числами 1, 2, 3. На колышек 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного колышка на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку с колышка 1 на колышек 2 за минимальное число перекладываний. 
Напишите программу, которая решает головоломку – для данного числа дисков n печатает последовательность перекладываний в формате "Disk 1 move from 1 to 2" (диск 1 переложить c колышка 1 на колышек 2), печатая по одной инструкции в строке. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров. 

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


Указание: подумайте, как переложить пирамидку из одного диска? Из двух дисков? Из трех дисков? Из четырех дисков? Напишите функцию void move (int n, int x, int y), которая перекладывает пирамидку высоты n с колышка номер x на колышек номер y.