II.Экспериментальный раздел работы

Пример 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).

Один из вариантов этого алгоритма состоит в том, что необходимо последовательно находить остатки от деления:

 

a на b: ; r1 = a mod b;

b на ; r2= b mod r1;

на ; r3 = r1 mod r2;

..........................

до тех пор, пока не станет равным нулю. Итак,

 

НОД(a,b) = НОД(b,r1) = НОД(r1,r2) =... = НОД(rn,0) = rn.

Например,

 

НОД(18,12) = НОД(12,6) = НОД(6,0) = 6.

Напишем подпрограмму-функцию:

int GCD(int a,int 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 можно осуществить в виде:

 

a0a1...ak = ak + 10(ak-1 + 10(ak-2 +... + 10(a1 + 10a0)...)

 

Пусть тогда

Теперь нетрудно составить систему рекуррентных соотношений:

которую нужно «прокрутить» в цикле до тех пор пока . Начальное значение искомой величины .

Запишем алгоритм вычислений:

1) «подготовка» цикла: ввод n; k=0; p=n; q=0;

2) «управление» циклом: если p>0, то выполнять пункт 3 (тело цикла),

иначе выполнять пункт 4 (вывод результата);

3) «тело» цикла: a=p mod 10; к=к+1; p=p div 10; q=q*10 +a; возврат к пункту 2;

4) вывод результата q.

Оформим его в виде подпрограммы-функции:

int Inv_N(int n)

{

int a,p=n,q=0,k=0;

while(p>0)

{

a=p%10;k++;

p/=10; q=q*10+a;

}

return q;

}

Отладить, протестировать и провести эксперимент с программой.

Напишите программу перевода чисел из двоичной системы счисления в десятичную; из системы счисления m в систему счисления n.