Общее представление о рекурсии

Рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).

Интересный факт: имеется сходство понятий рекурсии и математической индукции. У рекурсии, как и у математической индукции, есть база — аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии — способ сведения задачи к более простым.

Пример

Функцию для определения количества цифр числа можно описать в одно действие:

int cnt_digits(int num){

return ( num /= 10 ) ? 1 + cnt_digits(num) : 1;

}

Аналогично можно вычислить с помощью рекурсии значение НОД – наибольшего общего делителя для двух чисел

Пример

int gcd(int n, int m) {

return !m ? n : gcd(m, n%m);

}

Задача №223.  Подбор пароля

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

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

Единственное натуральное число L≤5 – длина пароля

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

Список паролей по одному в каждой строке в лексикографическом порядке. Т.е. например для L=3 пароли будут:

aaa

aab

…

zzy

zzz

Решение

#include<iostream>

using namespace std;

int L;

void rec(string s){

int lt=s.length()+1;

for(char ch= 'a';ch<='z';ch++)

   if(lt==L) cout<<s+ch<< endl;

   else rec(s+ch);

}

int main(){

cin>>L;

rec("");

}

Задача №224.  Ханойские башни

Легенда гласит, в Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.

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

Игра "Ханойские башни" состоит в следующем. Есть три стержня. На первый из них надета пирамидка из k колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить с использованием рекурсивного алгоритма программу, указывающую требуемые действия.

Решение

В случае, когда требуется переложить ОДИН диск со стержня номер mна стержень номер n, мы просто перекладываем его m ->n. Если требуется переложить со стержня mна стержень nболее одного диска i, то для этого необходимо переместить i-1 диск на третий стержень с номером s (промежуточный), затем переложить оставшийся самый большой диск с mна n, после чего i-1 диск нужно с промежуточного sпереложить на целевой стержень n. Таким образом, данный алгоритм сводит задачу к перемещению i-1 дисков вместо i.

Рекурсивная подпрограмма

void move(int i, int m, int n)  // перекладывает i дисков

                                // со стержня m на n

{

if(i==1) cout << m << "->" << n << endl;

else {

int s = 6 – m - n;    // s–промежуточный диск,

move(i - 1, m, s);    // 6-сумма номеров всех дисков

move(1, m, n);

move(i - 1, s, n);

}

}

Сама основная программа выглядит так

int main(){

int k;

cin >> k;

move(k, 1, 3);

}

Задача №225.  Учебные тревоги (foxford.ru)

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

Решение

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

Обозначим через d₁, d₂, d₃, … d_i – номера дней, когда происходила i-я учебная тревога.

Тогда i+1 –ая учебная тревога может находиться в интервале от d_iдо D

#include <iostream>

#define N 12

#define DAYS 30

int d[N+1] = {-1}, cnt = 0;

void alert(int k){

for(int i = d[k-1]+2; i <= DAYS; i++){

d[k] = i;

if(k == N) cnt++;

else alert(k+1);

} 

}

int main(){

alert(1);

std::cout << cnt;

}

Задача №226.  Монеты

В обороте участвуют монеты достоинством 1 рубль, 2 рубля, 5 рублей и 10 рублей. Сколькими способами можно набрать сумму S рублей?

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

Единственное целое неотрицательное число – сумма S, которую нужно представить с помощью монет данного достоинства.

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

Единственное число – количество способов, которыми можно представить введённую сумму при помощи данных монет.

Пример

Ввод	Вывод
5	4
13	16

Решение

Представим разложение суммы Sв виде:

где K₁₀, K₅, K₂, K₁ – количество монет номиналом 10, 5, 2 и 1 рубль соответственно.

Решение задачи основывается на выборе всех возможных вариантов K₁₀, K₅, K₂ с помощью рекурсии. Тогда K1 для этого набора K₁₀, K₅, K₂ можно будет выбрать единственным образом.

#include <iostream>

using namespace std;

 

int coin[] = {1, 2, 5, 10},

   last = sizeof(coin) / sizeof(int) - 1, s;

 

int r(int sum, int i = last){

if(!i) return 1;

int all = 0;

for(int j = 0; j <= sum/coin[i]; j++)

   all += r(sum - coin[i]*j, i-1);

return all;

}

 

int main() {

cin >> s;

cout << r(s);

}

Задача №227.  Игра с числами (foxford.ru)

На доске написано 16 чисел [92, 84, 64, 72, 77, 61, 89, 88, 91, 69, 75, 65, 68, 75, 52, 98] (именно в таком порядке). Дима играет в игру со следующими правилами:

· перед каждым ходом на доске написано 2^N чисел (N каждый раз разное)

· на каждом ходе Дима выбирает, какую половину он хочет стереть — первые N чисел или последние N чисел

· после этого Дима стирает выбранную половину и получает количество очков, равное максимальному стертому этим ходом числу.

· игра заканчивается, когда на доске остается одно число, и оно не засчитывается Диме в очки

Какое максимальное число очков сможет набрать Дима?

Решение

Рассмотрим решение данной задачи при помощи рекурсии для произвольного набора целых чисел длины 2^N. Воспользуемся вспомогательной функцией maxval, позволяющей найти максимальное значение среди элементов массива от номера l до номера r.

Рекурсивный поиск в функции recследует прерывать, когда отрезок состоит из одного числа. В качестве начального значения искомой величины maxsum возьмём наименьшее целое число типа int.

#include <iostream>

using namespace std;

 

int a[]={92,84,64,72,77,61,89,88,91,69,75,65,68,75,52,98};

int sz = sizeof(a) / sizeof(int) - 1,

maxsum = 0x80000000;             // maxsum = MIN_INT

 

int maxval(int l, int r){            // поиск max наотрезке

int m = a[l];                    // от l до r

for(int i = l+1; i <= r; i++)

   m = max(m, a[i]);

return m;

}

void rec(int l,int r, int sum){

int mid = (l + r) / 2;           //середина отрезка

if(l < r){

   rec(l, mid, sum + maxval(mid + 1, r));

   rec(mid + 1, r, sum + maxval(l, mid));

} else maxsum = max(maxsum, sum);

}

int main(){

rec(0, sz, 0);

cout << maxsum;

}

Задача №228.  Выбор приборов (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Для проведения эксперимента надо выбрать из N имеющихся приборов только три. Для этого выполняют следующую операцию - если в группе приборов больше трех, то их нумеруют и выбирают одну из групп: с четными или нечетными номерами. Операцию повторяют до тех пор, пока в группе не останется три или менее приборов. Если их остается ровно три, то они и берутся для эксперимента.

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

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

В единственной строке записано число N (1 ≤ N ≤ 2147483647).

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

В единственную строку нужно вывести одно число - найденное количество способов выбора приборов.

Примеры

№	Ввод	Вывод
1	3	1
2	6	2

Решение

Первое решение выглядит достаточно очевидным

#include <iostream>

 

int r(int k){

return (k < 3 ? 0 : (k==3 ? 1 : r(k/2) + r(k - k/2)));

}

 

int main() {

int n;

std::cin >> n;

std::cout << r(n);

}

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

#include <iostream>

 

int r(int k){

return k < 3 ? 0 : (k==3 ? 1 :

        (k % 2  ?  r(k/2) + r(k - k/2) : 2 * r(k/2)));

}

 

int main() {

int n;

std::cin >> n;

std::cout << r(n);

}

Задача №229.  Лесенка(acmp.ru)

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

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

Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке.

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

В выходной файл OUTPUT.TXT необходимо вывести число лесенок, которые можно построить из N кубиков.

Примеры

INPUT.TXT	OUTPUT.TXT
3	2
6	4

Решение

#include<fstream>

using namespace std;

unsigned long long l = 0;

void calc(int from , int to){

for(int i = from; i <= to; i++ )

   calc(i+1, to-i);

if(!to) l++;

}

int main(){

ifstream in("input.txt");

ofstream out("output.txt");

int n;

in >> n;

calc(1, n);

out << l;

}

Задача №230.  Ферзи

Вывести все комбинации, когда N ферзей на доске размером N×N не бьют друг друга.

Решение

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

#include <iostream>

#include <cstdlib>

#define N 8

using namespace std;

int queen[N+1];           //координаты ферзя i (i,queen[i])

 

void check(int j){              //проверка вертикали номер j

bool strike;

  for(int i = 1; i <= N; i++){     //перебор всех клеток вертикали

   strike = false;

   for(int p = 1; p < j; p++) //проверка поставленных ферзей

       if(abs(queen[p]-i) == j-p  ||  queen[p] == i)

           strike = true;

   if (!strike){                //если клетка не под ударом

      queen[j] = i;        //ставим ферзя сюда

       if (j < N)          // если не посл. вертикаль,

           check(j+1); // то проверяем следующую

       else{               // иначе выводим комбинацию

           for(int k = 1; k <= N; k++)

               cout << k << ';' << queen[k] << ' ';

           cout<<endl;

         }

   }

 }

}

 

int main() {

check(1);

}

Рассмотрим более усложненную версию этой же задачи.

Задача №231.  Магараджа (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

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

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

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

Входной поток содержит два целых числа: N и K (1 ≤ K ≤ N ≤ 10).

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

Выведите ответ на задачу.

Примеры

№	Ввод	Вывод
1	3 1	9
2	4 2	20
3	5 3	48

Решение

Очевидно, что магараджи, как и ферзи, должны находиться на разных вертикалях. Для того, чтобы исключить повторение одних и тех же комбинаций по несколько раз, будем считать Y_i<Y_i+1, т.е. горизонталь каждого следующего магараджи имеет номер строго больше, чем горизонталь предыдущего.

#include <iostream>

#include <cmath>          //функцияabs

using namespace std;

int my[10], mx[10], n, k, count=0, dx, dy;

void check(int p){   //установить магараджу номер p

bool strike;

for(int y = (p ? my[p-1]+1 : 1); y <= n; y++)

   for(int x = 1; x <= n; x++){

       strike = false;

       for(int i = 0; i<p; i++){// проверка ранее поставленных

           dy = abs(my[i]-y); // модуль разности координат

           dx = abs(mx[i]-x); // с предыдущим магараджей

           if(!dx || !dy || dx==dy || dx*dy==2) //под ударом?

              {strike = true; break;}

       }

       if(!strike && p<k-1){ // если поле не под ударом

           mx[p] = x;      // и не последний магараджа

           my[p] = y;      // то установить магараджу p

           check(p+1);     // и проверять следующего

       } else count++;     // иначе добавить +1 комбинацию

   }

}

 

int main () {

cin >> n >> k;

check(0);

cout << count;

}

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

Задача №232.  Поиск пути в лабиринте

Лабиринт задается с помощью матрицы, в которой 0 обозначает простое поле, а 1 – непроходимый блок.

Найти любой путь от одной заданной клетки до другой, либо указать, что его нет.

Решение

#include <cstdio>

#define N 4

#define M 5

short a[N][M]={1,0,0,0,1,

            0,0,1,0,1,

            1,0,0,0,0,

            0,0,1,0,0}, i1, j1, i2, j2;

bool pass;

void move(int i, int j, int k){ // i,j–коорд., k - шаг

a[i][j] = k;

k++;

if(i == i2 && j == j2){         //достигли цели

for(int row = 0; row < N; row++){ //вывод матрицы с путём

     for(int col = 0; col < M; col++)

           printf("%4d", a[row][col]);

     printf("\n");

}

pass = true;              //путь найден!

return;

}else{                     //иначе идти в соседние клетки

if (i+1<N&& !a[i+1][j])move(i+1,j,k);

if (j+1<M&& !a[i][j+1])move(i,j+1,k);

if (j&& !a[i][j-1])move(i,j-1,k);

if (i&& !a[i-1][j])move(i-1,j,k);

}

a[i][j]=0;                //возвращаемся и затираем путь

k--;

}

int main(){

pass=false;                     //путь ещё не найден

printf ("i1,j1\n");

scanf ("%d%d", &i1,&j1);

printf ("i2,j2\n");

scanf ("%d%d", &i2,&j2);

if(a[i1][j1]||a[i2][j2]){printf("wrong coords");}

else move(i1,j1,2);

if (!pass)printf("no pass");

}

При выполнении программы она будет выдавать путь в матрице в такой форме:

i1,j1

0 3

i2,j2

3 0

1 0 0 2 1

0 0   1 3 1

1 6 5 4 0

8 7 1 0 0

Путь помечается числами от двух и далее.

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

Задача №233.  Скобки – 2 (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

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

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

Единственное четное натуральное число N, не превышающее 14.

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

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

Примеры

№	Ввод	Вывод
1	2	() []
2	4	(()) [[]] [()] ()[] []() ()() ([]) [][]

Решение

Применим рекурсивную функцию поиска скобочного выражения, записывая в стек открытые скобки.

#include <iostream>

#include <stack>

using namespace std;

 

int n;

string s, b = "([";

stack<char> q;

 

void search() {

  if (s.length() == n) {

    cout << s << endl;

    return;

  }

  if (s.length() < n - q.size()) {

    for (int i = 0; b[i]; i++) {

      s.push_back(b[i]);

      q.push(b[i]);

      search();

        q.pop();

      s.erase(s.length() - 1);

    }

  }

  if (!q.empty()) {

    char l = q.top(), r = l == '(' ? ')' : ']';

    s.push_back(r);

    q.pop();

    search();

    q.push(l);

    s.erase(s.length() - 1);

  }

}

 

int main() {

  cin >> n;

search();

}

Задача №234.  Раскопки (acmp.ru)

Источник задачи: Московская олимпиада по информатике 2002/2003 года.

(Время: 1 сек. Память: 16 Мб)

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований учёные пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции - сложение, умножение и вычитание (марсиане никогда не использовали «унарный минус»: вместо «-5» они писали «0-5»). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3+3*5 у них равнялось 30, а не 18. К сожалению, символы арифметических действий стерлись. Например, если была запись «18=7 (5 3) 2», то возможно восстановить эту запись как «18=7+(5-3)*2». Требуется написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.

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

Первая строка входного файла INPUT.TXT состоит из натурального числа, не превосходящего 2³⁰, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 2³⁰. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).

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

В выходной файл OUTPUT.TXT необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий без лишних пробелов). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа «-1». Выходная строка не должна содержать пробелов.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	18= 7  (5  3)  2	18=7+(5-3)*2
2	5=  3  3	-1

Решение

Это достаточно сложная задача. Для её решения применим принцип функциональной декомпозиции – разобьём её на более простые подзадачи. В качестве исходных данных выступают ответ ans для выражения в правой части – строки s. Для обозначения арифметических операций используем массив из 3 элементов типа char, а для их выполнения заведём массив указателей на функции mul(умножение), add(сложение) и sub(вычитание).

#include <fstream>

#include <cstdlib>

#define SIGNS 3                      //количество действий

using namespace std;

int mul(int x, int y) {return x * y;}     //умножение

int add(int x, int y) {return x + y;}     //сложение

int sub(int x, int y) {return x - y;}     //вычитание

int (*f[SIGNS])(int, int)={mul, add, sub}; //массив ук.-лей на функции

char sgn[SIGNS]={'*','+','-'}, c;    //обозначения операций

 

int ans;                             //число в левой части

string s, t;                         //строки для правой части

Далее нам потребуется функция val для вычисления выражений, записанных в «марсианской нотации». Очевидно, что обрабатывать строку, содержащую выражение, нужно с конца, иначе при преобразовании выражения по правилу val(a?b) = val(a) ?val(b), где знак ? обозначает какую-то арифметическую операцию

3 + 2 * 5 будет вычислено как val(3) +val(2*5), что даст ответ 13 (кстати, правильный в нашей собственной нотации), вместо положенного val(3+2)*val(5) = 30. Дополнительную сложность представляет обработка скобок. Воспользуемся представлением для скобочного автомата, описанного в главе «Задачи с символами и строками».

int val(string expr){

int len = expr.size(), i = len-1, j = expr[i]==')';

while(j){                        // выделяем из выражения

    i--;                         // со скобками правильное

    if(expr[i]==')')j++;         // скобочное выражение

    if(expr[i]=='(')j--;         // (ищем его начало)

}

if(!i && expr[i]=='(' )        // если целиком в скобках

   return val(expr.substr(1, len-2));

for(; i; i--)                    // ищем арифметические

   for(j = 0; j<SIGNS; j++){    // знаки и делим выражение

       if(expr[i] == sgn[j]){   // на части expr1 и expr2

           string expr1 = expr.substr(0, i),

                  expr2 = expr.substr(i+1, len-i-1);

           return (*f[j])(val(s1), val(s2));

       }

   }                            //если дошли до этого места

return atoi(expr.c_str());       // то осталось число

}

Написав функцию val и убедившись после нескольких проверок, что она работает правильно, переходим к следующему вопросу – как перебрать все возможные расстановки знаков арифметических операций в выражении? Для этого в исходной строке в местах, где должны будут стоть знаки действий, поставим какой-нибудь произвольный символ, например знак «?». Как и предыдущая функция val наша функция putsign работает с применением рекурсивного алгоритма. Её аргументом является текущая позиция символа в строке. Найдя символ «?», будем в этом месте поочерёдно устанавливать знаки арифметических операций и запускать проверку оставшейся части. Если мы дошли до конца строки, вычислим значение выражения и проверим его на совпадение с ответом.

bool putsign(int pos){

do{                                   // ищем знак ? или

   pos++;                            // конец строки

   if(pos == s.size()){              // если конец строки

       if(val(s) == ans) return true;     //проверяем значение

       return false;

   }

} while (s[pos] != '?');

for(int i = 0; i < SIGNS; i++){       // поочерёдно ставим

   s[pos] = sgn[i];                  // знаки действий

   if (putsign(pos)) return true;    // и проверяем

}                                     // оставшуюся часть

s[pos] = '?';                         // возвращаем знак ?

return false;

}

Ну и наконец, завершающий штрих – создание тела основной программы.

int main(){

ifstream cin("input.txt");

ofstream cout("output.txt");

cin >> ans >> c >> s;

while(cin >> t) s += "?" + t;

if(putsign(0)) cout << ans << '=' << s;

else cout << -1;

}

Быстрая сортировка

Описание алгоритма

#include <cstdlib>

#include <iostream>

using namespace std;

int a[100];

void quickSort(int l, int r){

cout << l<< "-" << r << endl;

int x = a[(l + r)/2];

int i = l;

int j = r;

while(i <= j){

   while(a[i] < x) i++;

   while(a[j] > x) j--;

   if(i <= j){

       swap(a[i], a[j]);

       i++;

       j--;

   }

}

if (i<r) quickSort(i, r);

if (l<j) quickSort(l, j);   

}

int main(){

int n;

cin >> n;

for(int i = 0; i < n; i++)

   cin >> a[i];

quickSort(0, n-1);

for(int i = 0; i < n; i++)

cout<<a[i]<<" ";

return 0;

}

Приведённый код демонстрирует алгоритм быстрой сортировки массива. Однако при решении задач средствами языка C, нет необходимости его воспроизводить. Он уже реализован в заголовочном файле cstdlib с помощью функции qsort[1].

Функция sort

 (Для C++) В С++ имеется возможность применять наравне с qsort еще более простую в использовании функцию sort, с общей сложностью алгоритма сортировки O(N×logN). Она описана в заголовочном файле algorithm для пространства имён std. Например:

#include <iostream>

#include <algorithm>

int main() {

int array[] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 };

int elements = sizeof(array) / sizeof(array[0]);

std::sort(array, array + elements);

for (int i = 0; i < elements; ++i)

std::cout << array[i] << ' ';

return 0;

}

В данном случае используется массив array. Если в программе требуется отсортировать обычный одномерный массив, например array[1000], то достаточно в коде прописать:

sort(array, array + 1000);

Функцию sort можно вызывать с двумя или тремя параметрами. Третьим выступает компаратор, если, например, требуется произвести сортировку в обратном порядке или типа, не являющегося стандартным. Компаратор должен вернуть true, если первый аргумент меньше, чем второй.

#include <iostream>

#include <algorithm>

#define NMAX 4

using namespace std;

int arr[NMAX] = {67, 12, 1, 100};

bool comp(int a, int b){  //компаратор

return a > b;         //по убыванию, а<b – по возрастанию

}

int main(){

sort(arr, arr + NMAX, comp); //сортируем массив по компаратору

for(int i = 0; i < NMAX; i++)

   cout << arr[i] << " ";

return 0;

}

Для векторов и других контейнеров STL (строки и т.д.) в C++ можно использовать sort в формах

sort(v.begin(), v.end());       //в прямом порядке

sort(v.rbegin(), v.rend());     //в обратном порядке

Функция sort не только более удобна, но также стабильнее и быстрее в сравнении c qsort.

Задача №235.  Анаграммы (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Cтрока S1 называется анаграммой строки S2, если она получается из S2 перестановкой символов. Даны строки S1 и S2. Напишите программу, которая проверяет, является ли S1 анаграммой S2.

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

Первая строка входного файла INPUT.TXT содержит строку S1, вторая - S2. Обе строки состоят только из прописных букв латинского алфавита. Строки не пусты и имеют длину не больше 100000 символов.

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

В выходной файл OUTPUT.TXT выведите YES, если S1 является анаграммой S2, и NO - в противном случае.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	ABAA ABBA	NO
2	ABBA BABA	YES

Решение

#include <fstream>              //файловый ввод-вывод

#include <algorithm>            //функция sort

using namespace std;

int main () {

ifstream cin("input.txt");

ofstream cout("input.txt");

string a, b;

cin >> a >> b;

sort(a.begin(), a.end());

sort(b.begin(), b.end());

cout << (a == b ? "YES" : "NO");

}

В случае,когда регистром символов можно пренебречь, можно использовать transform и tolower.

#include <bits/stdc++.h>

using namespace std;

int main(){

string a, b;

cin >> a >> b;

transform(a.begin(), a.end(), a.begin(), ::tolower);

transform(b.begin(), b.end(), b.begin(), ::tolower);

sort(a.begin(), a.end());

sort(b.begin(), b.end());

cout << (a == b ? "Yes" : "No");

}

Задача №236.  Наименьшее и наибольшее числа из тех же цифр

(Время: 1 сек. Память: 16 Мб)

Требуется написать программу, которая найдет наименьшее и наибольшее числа, состоящие из тех же цифр, что и заданное натуральное число N.

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

Одно натуральное число N (N <= 10¹⁰⁰⁰).

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

В одной строке наименьшее, а через пробел – наибольшее числа.

Примеры

№	Ввод	Вывод
1	7051	1057 7510
2	851	158 851

Решение

#include <iostream>

#include <algorithm>

 

using namespace std;

int main() {

stringn;

cin>>n;

sort(n.begin(), n.end()); // сортируем цифры по возрастанию

inti = 0;

while(n[i]=='0') i++;     // заменяем лидирующий 0 первой

swap(n[0], n[i]);         // ненулевойцифрой

cout << n << ' ';

sort(n.rbegin(), n.rend()); // сортируем цифры по убыванию

cout <<n;

}

Жадные алгоритмы

Задача №237.  Банкомат

В банкомате имеются в достаточном количестве купюры номиналом 50, 100, 200, 500, 1000 и 5000 рублей. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в N рублей, или вывести -1, если указанную сумму выдать нельзя.

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

Одно целое неотрицательное число N≤10⁹.

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

Одно число – требуемое количество купюр.

Пример

Ввод	Вывод
5350	4
73210	-1

Решение

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

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

#include<iostream>

int banknote[]={5000, 1000, 500, 200, 100, 50}; //купюры по убыванию

int main() {

int n, k = sizeof(banknote) / sizeof(int),

   x = 0; // x – количество купюр

std::cin >> n;

for(int i = 0; i < k; i++){ //перебирает все купюры

   x += n / banknote[i]; //сколько раз входит купюра в сумму

   n %= banknote[i]; //сумма заменяется остатком

}

if(n) x = -1; //проверка остатка, который не удалось выдать

std::cout << x;

}

Задача №238.  Сумма – 2 (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Задано натуральное число x. Найдите число способов представить его в виде суммы четырех натуральных чисел: x = a + b + c + d, где a <= b <= c <= d.

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

Одно целое число x (1 <= x <= 1500).

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

Одно число –  ответ на задачу.

Примеры

№	Ввод	Вывод
1	3	0
2	5	1

Решение

Первое же решение, которое приходит в голову – перебрать все возможные варианты d, c, b. Величина a вычисляется как x – d – c – b.

#include <iostream>

int x, a, b, c, d, cnt = 0;

int main(){

std::cin >> x;

for(d=x-3; d; d--)

     for(c=d; c; c--)

           for(b=c; b; b--)

                cnt += (x-d-c-b>0 && x-d-c-b<=b);

std::cout << cnt;

}

Это решение не пройдёт по времени. Попробуем оптимизировать перебор. Очевидно, d не может быть больше, чем x/2, c не может превышать x/3 и a должно быть меньше либо равно x/4.

#include <iostream>

int x, a, b, c, d, cnt = 0;

int main(){

std::cin >> x;

for(a = 1; a <= x/4; a++)

   for(b = a; b <= x/3; b++)

       for(c = b; c <= x/2; c++)

           cnt += x-a-b-c >= c;

std::cout << cnt;       

}

Задачу можно решить и более быстрым способом методом динамического программирования. Воспользуемся формулой из «Онлайн-энциклопедии числовых последовательностей» OEIS. [7]

#include <iostream>

intx, a[1501]={1, 1, 2, 3, 5, 6, 9, 11, 15, 18};

intmain(){

std::cin >> x;

for(int n = 9; n < x; n++)

     a[n] = 1 + (a[n-2] + a[n-3] + a[n-4])

     - (a[n-5] + a[n-6] + a[n-7]) + a[n-9];

std::cout << (x < 4 ? 0 : a[x-4]);

}

Задача №239.  Головоломка(acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Петя разгадывает головоломку, которая устроена следующим образом. Дана квадратная таблица размера N×N, в каждой клетке которой записана какая-нибудь латинская буква. Кроме того, дан список ключевых слов. Пете нужно, взяв очередное ключевое слово, найти его в таблице. То есть найти в таблице все буквы этого слова, причем они должны быть расположены так, чтобы клетка, в которой расположена каждая последующая буква слова, была соседней с клеткой, в которой записана предыдущая буква (клетки называются соседними, если они имеют общую сторону — то есть соседствуют по вертикали или по горизонтали). Например, на рисунке показано, как может быть расположено в таблице слово olympiad.

Рис. 42. Пример к задаче "Головоломка"

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

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

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

В первой строке записаны два числа N (1<=N<=10) и M (0<=M<=100). Следующие N строк по N заглавных латинских букв описывают ребус. Следующие M строк содержат слова. Слова состоят только из заглавных латинских букв, каждое слово не длиннее 100 символов. Гарантируется, что в таблице можно найти и вычеркнуть по описанным выше правилам все ключевые слова.

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

Выведите в алфавитном порядке оставшиеся в таблице буквы.

Примеры

№	Ввод	Вывод
1	5 3 POLTE RWYMS OAIPT BDANR LEMES OLYMPIAD PROBLEM TEST	AENRSW
2	3 2 ISQ ABC IQW I IS	ABCQQW

Решение

Заведем массив P на 26 элементов – счетчики английских букв. При вводе таблицы будем увеличивать счетчики, а при вычеркивании слов – уменьшать.

#include <iostream>

using namespace std;

int main() {

int n, m, p[26] = {0,};

char s[100], ch;

cin >> n >> m;

for(int i = 0; i < n; i++)

     for(int j = 0; j < n; j++){

           cin>>ch;

           p[ch-'A']++;    // считаем буквы таблицы

     }

for(; m--;){

     cin >> s;

     for(int i = 0; s[i]; i++)

           p[s[i]-'A']--;  // вычеркиваем буквы слов

}

for(int i = 0; i < 26; i++)

     while(p[i]--)

           cout << char('A' + i);

}

Задача №240.  Жадный фермер

Фермер планирует вывезти свои товары для продажи в город. У него имеется Nразных видов товара. Каждый товар с номером iописывается двумя величинами W_iи P_i–количество товара в кг и цена одного кг этого товара. Машина фермера может перевезти не более Mкг.

Какую наибольшую сумму может получить фермер после продажи товаров в городе?

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

В первой строке два натуральных числа M, N≤10⁹.

В следующих Nстроках пары чисел – W_iи P_i–количество товара в кг и цена одного кг этого товара соответственно.

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

Единственное число – максимальная сумма, которая может быть у фермера после продажи товаров в городе

Пример

Ввод	Вывод
3003 120 1 50 5 200 10	2300

Решение

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

#include <iostream>

#include <utility>   //описание pair

#include <algorithm> //описание sort и reverse

#define SIZE 100

using namespace std;

int main() {

pair<int, int> t[SIZE];

int n, w, p, m, i, s=0;

cin>>m>>n;

for(i = 0; i < n; i++){

   cin >> w >> p;

   t[i] = make_pair(p,w);

}

sort(t,t+n);          //сортировка товаров по возрастанию цены

reverse(t,t+n);  //перестановка в обратном порядке

w = 0;

for(i=0; i<n && w<m; i++) //загружаем товары в машину

   if(w+t[i].second<=m){ //помещается полностью

       s += t[i].second*t[i].first;

       w += t[i].second;

   } else{           //помещается частично

       s += t[i].first * (m - w);

       w = m;

   }

cout<<s;

}

Задача №241.  Печеньки

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

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