Пример 1. Пусть задано натуральное число m. Необходимо найти минимальное число n такое, что факториал n! > m.
По определению, n!=1*2*3*…n.Таким образом, решение поставленной задачи сводится к последовательному увеличению значения n, вычисления n! и сравнения его с заданным числом m. Как только величина n! станет больше m, вычисления нужно прекратить и вывести результат. Последовательное увеличение n организуем с помощью цикла while, а для вычисления факториала числа воспользуемся следующими соотношениями:
В этой последовательности первый член равен 1, а каждый последующий равен предыдущему, умноженному на k. Такое соотношение называется рекуррентным, что означает «возвращающийся».
Из школьного курса математики нам известны такого рода соотношения для членов арифметической и геометрической прогрессий, где d – разность, q – знаменатель. Рекуррентные соотношения играют важную роль в программировании, т.к. в сочетании с операторами циклов создают мощный вычислительный инструментарий.
Запишем алгоритм нашей задачи:
1. «подготовка» цикла: ввод m; k=1; p=1;
2.«управление» циклом: если p<m, то выполнять пункт 3 (тело цикла),
иначе выполнять пункт 4 (вывод результата);
3.«тело» цикла: к=к+1; p=p*k; возврат к пункту 2;
4.вывод результата n=k.
Оформим его в виде подпрограммы-функции:
#include <iostream.h>
#include <conio.h>
int Min_N(int m)
{
int k=1,p=1;
while (p<m)
{ k++; p*=k;}
return k;
}
void main (void)
{
int m;
cout<<"Введите число m=?"<<endl; cin>>m;
cout<<" Минимальное значение n="<<Min_N(m)<<endl;
getch();
}
Провести отладку и тестирование программы. Вычислить значение n для случаев, когда m=MAXINT и MAXLONG.
Пример 2.Напишем логическую функцию, которая будет возвращать значение true, если натуральное число n простое, и false – в противном случае.
Напомним, что натуральное число называется простым, если оно делится без остатка только на единицу и само себя. Очевидно также, что число n – составное, если оно делится хотя бы на одно из чисел 2,3,…,n-1.
Таким образом, при n>2 необходимо проверить делимость n на каждое из чисел k=2,3, … n-1. На самом деле, как показано в теории чисел, можно сократить сверху диапазон поиска до целой части корня квадратного из n: .
Составим программу на языке C++:
bool Simple(int n)
{
bool b=true; int k=2,max;
max=sqrt(n)+1;
while (b&&(k<max))
{
if ((n%k)==0) b=false;
k++;
}
return b;
}
Поэкспериментируйте с программой. Простые числа 2,3,5,7,11,13,…расположены в натуральном ряду весьма загадочным образом. Двигаясь по этой последовательности чисел необходимо вычислить простое число по его номеру.
Пример 3. Используя алгоритм Евклида, составим программу определения наибольшего общего делителя числа a на b: НОД(a,b).
Один из вариантов этого алгоритма состоит в том, что необходимо последовательно находить остатки от деления :
// Greatest Common Divisor -наибольший общий делитель
int r1,r2,r3;
if (a>b){ r1=a; r2=b;}
else { r1=b; r2=a;}
while(r2 !=0)
{
r3=r1%r2;
r1=r2; r2=r3;
}
return r1;
}
Введите, отладьте и протестируйте программу.
Пример 4. Напишем программу, в которой для заданного натурального числа n, ищется число q, записанное цифрами в обратном порядке. К примеру, если n=1965, то q=5691.
Запишем натуральное число n в виде n=akak-1...a0 , где ai - цифры, составляющие его в десятичной системе счисления:
akak-1...a0 = a0100 + a1101 + ... + ak10k
Тогда натуральное число q, записанное цифрами в обратном порядке
a0a1...ak = ak100 + ak-1101 + ... + a010k .
Значение a0 можно найти как остаток от деления числа n на 10. Разделив n на 10, и найдя снова остаток, получим цифру а1, ... В противоположность этому, число q формируется путем умножения на 10 , полученных остатков от деления числа n. Это последовательное умножение на 10 можно осуществить в виде:
нужно прекратить и вывести результат. Последовательное увеличение n организуем с помощью цикла while, а для вычисления факториала числа воспользуемся следующими соотношениями:
и геометрической 
прогрессий, где d – разность, q – знаменатель. Рекуррентные соотношения играют важную роль в программировании, т.к. в сочетании с операторами циклов создают мощный вычислительный инструментарий.
.
; r1 = a mod b;
; r2= b mod r1;
на 
; r3 = r1 mod r2;
не станет равным нулю. Итак,
тогда
. Начальное значение искомой величины 
.