ГЛАВА 4. Делители целого числа

 

Для нахождения всех делителей некоторого натурального числа N, исключая 1 и само число, следует перебрать все натуральные значения от 2 до [ N /2], так как в интервале от [ N /2]+1 до N множителей нет [26]. Здесь [x] – целая часть числа x.

 

Листинг 4.1. Определить все делителели некоторого натурального числа N, за исключением 1 и самого числа.

 

//L4_1.cpp

#include <iostream>

using namespace std;

int main()

{

setlocale(LC_CTYPE,"russian");

int n,d;

do // Цикл гарантирует

{ // введение натурального

cout<<"Введите n "; // числа.

cin>>n;

}while (n<=0);

for(d=2;d<=n/2;d++) // Нахождение делителей

{

if(n%d==0)

cout<<d<<" ";

}

cout<<endl;

return 0;

}

 

Результат работы программы листинга 4.1 приведен на рис. 4.1:

 

 

Рис. 4.1. Результат работы программы листинга 4­.1

 

Следует отметить, что можно искать делители среди натуральных чисел, не превышающих квадратный корень из исходного числа, а остальные делители получаются в результате деления этого числа на найденные делители, то есть цикл «Нахождение делителей» будет иметь следующий заголовок:

for(d=2; d*d<=n; d++).

 

В этом случае результат работы программы представлен на рис. 4.2.

 

 

Рис. 4.2. Результат работы программы листинга 4­.2

 

Листинг 4.2. Найти наибольший общий делитель (НОД) двух неотрицательных целых чисел m и n, используя алгоритм Евклида [4, 26]. Алгоритм Евклида основывается на том, что для двух чисел m и n, причем m ³ n, НОД(m, n) = НОД(n, r), где r – остаток от деления m на n. Если n = 0, то НОД(m,0)= m.

 

//L4_2.cpp

#include <iostream>

using namespace std;

int main()

{

setlocale(LC_CTYPE,"russian");

int n,m,r;

do // Цикл гарантирует

{ // введение натуральных

// чисел.

cout<<"Введите натуральные числа m и n ";

cin>>m>>n;

}while (m <= 0 || n <= 0);

if (m < n)

{

r=m;

m=n;

n=r;

}

while (n > 0)

{

r=m % n;

m=n;

n=r;

}

cout<<"Наибольший общий делитель "<<m<<endl;

return 0;

}

 

На рис. 4.3 представлен результат выполнения программы листинга 4.2.

 

 

Рис. 4.3. Результат работы программы листинга 4­.2

 

Листинг 4.3. Найти простые числа, не превышающие заданного натурального числа N [26].

Первые простые числа – это 2 и 3. Если введенное число совпадает с ними, то их следует напечатать. В остальных случаях следует проверить, имеет ли текущее число делители меньше кадратного корня из числа. Четные числа проверять нет необходимости, так как они всегда имеют делитель 2.

 

//L4_3.cpp

#include <iostream>

using namespace std;

int main()

{

setlocale(LC_CTYPE,"russian");

int N,d,k;

do // Цикл гарантирует

{ // введение натурального

// числа.

cout<<"Введите натуральное число n ";

cin>>N;

}while (N<=0);

if(N>=2)

cout<<2<<" ";

if(N>=3)

cout<<3<<" ";

k=5;

while (k<=N)

{

for(d=2; d*d<k && k%d!=0; d++)

;

if(d*d>k) // Число простое

cout<<k<<" ";

 

k+=2;

}

cout<<endl;

return 0;

}

 

Результат работы программы листинга 4.3 приведен на рис. 4.4:

 

 

Рис. 4.4. Результат работы программы листинга 4­.3

 

 

Упражнения

1. Для натурального числа N найти сумму всех делителей, включая 1 и само число.

2. Для натурального числа N найти число четных делителей.

3. Для натурального числа N найти число всех делителей, исключая 1 и само число.

4. Для натурального числа N найти сумму всех нечетных делителей, включая 1 и само число (если оно нечетное).

5. Для натурального числа N найти сумму всех четных делителей, включая и само число (если оно четное).

6. Найти все натуральные числа из интервала от 1 до 200, у которых сумма делителей равна N.

7. Найти все натуральные числа из интервала от 1 до 200, у которых число делителей равно N.

8. Найти все натуральные числа из интервала от N 1 до N 2, у которых сумма делителей больше K.

9. Найти все натуральные числа из интервала от N 1 до N 2, у которых сумма делителей меньше или равна K.

10. Найти натуральное число в диапазоне от 1 до10 000 с максимальной суммой делителей.

11. Найти натуральное число в диапазоне от 1 до 10 000 с минимальной суммой делителей.

12. Найти натуральное число в диапазоне от 1 до 10 000 с максимальным числом делителей.

13. Найти количество делителей натурального числа N, больших K.

14. Даны целые числа p и q. Получить все делители числа q, взаимно простые с p. Числа называются взаимно простыми, если у них нет ощих делителей, кроме 1. Например, 15 и 8.

15. Получить все простые делители числа N.

16. Среди всех четырехзначных чисел найти все простые числа, у которых сумма двух старших цифр равна сумме двух младших цифр.

17. Найти наибольший обший делитель трех чисел НОД(N, M, K), используя соотношение НОД(N, M, K) = НОД(НОД(N, M), K).

18. Даны натуральные числа M и N. Получить все кратные им числа, меньшие M×N.

19. Для натуральных чисел N и M найти наименьшее общее кратное, используя соотношение НОК(N, M)= N×M / НОД(N, M).

20. Найти наибольший обший делитель n чисел НОД(N ₁, N ₂,…, N_k), используя соотношение:

НОД(N ₁, N ₂,…, N_k) = НОД(НОД(N ₁, N ₂,…), N_k) =

НОД(НОД(НОД(N ₁, N ₂,…, N_{k -2}), N_{k -1}), N_k) и так далее.

21. Найти все совершенные натуральные числа не превосходящие N. Совершенным называется число, равное сумме своих делителей, включая 1 и исключая само число. Например, 28=1+2+4+7+14.

22. Найти все совершенные натуральные числа из интервала от N 1 до N 2.

23. Найти все простые множители числа N, причем каждый из них должен быть выведен столько раз, сколько он встречается в исходном числе. Например, N = 28 = 2×2×7.

24. Найти все простые множители числа N, причем каждый из них должен быть выведен один раз. Например, N = 28 Þ2 7.

25. Найти все пары дружественных натуральных чисел из интервала от N 1 до N 2. Два числа называются дружественными, если каждое из них равно сумме делителей другого (само число в качестве делителя не рассматривается).

 

ГЛАВА 5. Сортировка данных

 

Сортировку данных можно осуществлять различными алгоритмами. Среди них наиболее часто применяются следующие методы [10]: сортировка вставкой, метод пузырька, сортировка выбором и быстрая сортировка. Рассмотрим эти методы подробнее.

Сортировка вставкой

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

Листинг 5.1. Программа демонстрирует метод сортировки вставкой массива из 10 целых элементов.

 

//L5_1.cpp

#include <iostream>

using namespace std;

int main()

{

setlocale(LC_CTYPE,"russian");

int A[10], n=10, i, j, key;

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

{

cout<<"Введите А("<<i+1<<")=";

cin>>A[i];

}

cout<<"Исходный массив\n";

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

cout<<A[i]<<" ";

cout<<endl;

for(i = 1; i<n; i++)

{

key = A[i];

j = i - 1;

while (j >= 0 && A[j] > key)

{

A[j + 1] = A[j];

j = j - 1;

A[j + 1] = key;

}

}

cout<<"Полученный массив\n";

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

cout<<A[i]<<" ";

cout<<endl;

return 0;

}

Результат работы программы листинга 5.1 приведен на рис. 5.1:

 

 

Рис. 5.1. Результат работы программы листинга 5­.1

Метод пузырька

 

Алгоритм сортировки методом пузырька состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны. Это означает, что массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название данного алгоритма).

Листинг 5.2. Задан список студентов с указанием фамилии и номера группы. Упорядочить этот список по возрастанию номера группы, а внутри группы построить его в алфавитном порядке.

 

//L5_2.cpp

#include <string.h>

#include <iostream>

using namespace std;

int main()

{

setlocale(LC_CTYPE,"russian");

int n, i,*grup, f, k=0, gtmp;

char **name, *ntmp, fam[30];

do

{

cout<<"Введите число студентов ";

cin>>n;

}while(n<=0);

name=new char*[n]; // Выделение памяти для указателей,

// связанных с фамилией студентов.

grup=new int[n]; // Выделение памяти под номера групп.

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

{

cout<<"Введите фамилию "<<i+1<<"-го студента и его группу ";

cin>>fam>>grup[i];

name[i]=strdup(fam); // Заполняется фамилия i-го студента

}

do

{

f=0;

for(i=0; i<n-1-k; i++)

// Сравнение по группам, а если они равны, сравнение фамилий:

if(grup[i]>grup[i+1] || (grup[i]==grup[i+1] && strcmp(name[i],name[i+1])>0))

{

ntmp=name[i];

name[i]=name[i+1];

name[i+1]=ntmp;

gtmp=grup[i];

grup[i]=grup[i+1];

grup[i+1]=gtmp;

f=1;

}

}while (f);

cout<<"Полученный список\n";

setlocale(LC_CTYPE,".866"); // Установка страницы для правильного

// вывода символов кириллицы.

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

{

cout.width(6); // Выделение поля для вывода группы

cout<<grup[i]<<" ";

cout<<name[i]<<'\n';

}

return 0;

}

 

На рис. 5.2 представлен результат выполнения программы листинга 5.2.

 

 

Рис. 5.2. Результат работы программы листинга 5­.2

Сортировка выбором

 

Алгоритм сортировки выбором состоит из трех шагов:

1. Находится номер минимального значения в текущем списке.

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

3. Сортируется «хвост» списка, исключив из рассмотрения уже отсортированные элементы.

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

Листинг 5.3. Задан список студентов с указанием фамилии и номера группы (рис. 5.3). Упорядочить этот список по возрастанию номера группы, а внутри группы построить его в алфавитном порядке.

//L5_3.cpp

#include <string.h>

#include <iostream>

using namespace std;

 

int main()

{

setlocale(LC_CTYPE,"russian");

int n, i, j, *grup, jmax, gm;

char **name, fam[30], *fm;

fstream ff("input.txt");

ff>>n;

name=new char*[n ]; // Выделение памяти для указателей, связанных

//с фамилией студентов.

grup=new int[n]; // Выделение памяти под номера групп

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

{

ff>>fam>>grup[i];

name[i]=strdup(fam); // Заполняется фамилия i-го студента

}

ff.close();

for(i=0;i<n-1;i++)

{

fm=name[i];

gm=grup[i];

jmax=i;

for(j=i+1;j<n;j++)

if(grup[j]<gm ||(grup[j]==gm && strcmp(name[j],fm)<0))

{

fm=name[j];

gm=grup[j];

jmax=j;

}

name[jmax]=name[i];

name[i]=fm;

grup[jmax]=grup[i];

grup[i]=gm;

}

cout<<"Полученный список\n";

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

{

cout.width(6); // Выделение поля для вывода группы

cout<<grup[i]<<" ";

cout<<name[i]<<'\n';

}

ff.open("input.txt", ios::app);

ff<<"\nПолученный список\n";

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

{

ff.width(6);

ff<<grup[i]<<" ";

ff<<name[i]<<'\n';

}

ff.close();

cin.get();

return 0;

}

Содержимое файла “input.txt”

 

Рис. 5.3. Информация, находящаяся в файле «input.txt»

 

Результат работы программы листинга 5.3 приведен на рис. 5.4:

 

 

Рис. 5.4. Результат работы программы листинга 5­.3

 

 

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

 

Быстрая сортировка, хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов сортировки. Метод основан на принципе «разделяй-и-властвуй».

Общая схема быстрой сортировки такова: из массива выбирается некоторый опорный элемент a[i], запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] – вправо (рис. 5.5). Теперь массив состоит из двух подмножеств, причем левое подмножество меньше, либо равно правого:

 

 

Рис. 5.5. Разделение массива на два подмассива

 

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

Рассмотрим алгоритм быстрой сортировки подробнее.

 

1. На входе задаем массив a[0]... a[N] и опорный элемент p, по которому будет производиться разделение.

2. Введем два указателя: i и j (рис. 5.6). В начале алгоритма они указывают, соответственно, на левый и правый концы последовательности.

3. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p.

4. Аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] <= p.

5. Если i <= j, меняем a[i] и a[j] местами и продолжаем двигать i, j по тем же правилам.

6. Повторяем шаг 3, пока i <= j.

 

Рассмотрим работу процедуры быстрой сортировки для массива a[0]...a[6] и опорного элемента p = a[3] (рис. 5.6).

 

 

Рис. 5.6. Иллюстрация алгоритма быстрой сортировки

 

 

Теперь массив разделен на две части: все элементы левой меньше либо равны p, все элементы правой – больше, либо равны p. Разделение завершено.

Листинг 5.4. Задать исходный массив х[N]. Количество элементов массива N и значения элементов массива ввести с клавиатуры. Применяя алгоритм быстрой сортировки, отсортировать исходный массив в порядке возрастания его элементов. Вывести на экран дисплея исходный и отсортированный массивы.

 

//L5_4.cpp

#include <iostream>

using namespace std;

void qs(int* s_arr, int first, int last); // Прототип функции qs()

int main()

{

setlocale(LC_CTYPE,"russian");

int i, n, *x;

do

{

cout<<"Введите число элементов массива ";

cin>>n;

}while (n<=1);

x=new int[n];

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

{

cout<<"Введите x("<<i+1<<")=";

cin>>x[i];

}

cout<<"Исходный массив\n";

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

cout<<x[i]<<" ";

cout<<endl;

qs(x,0,n-1);

cout<<"Полученный массив\n";

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

cout<<x[i]<<" ";

cout<<endl;

return 0;

}

 

void qs(int* s_arr, int first, int last)

{

int i = first, j = last, x = s_arr[(first + last) / 2];

 

do {

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

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

 

if(i <= j) {

if (i < j) swap(s_arr[i], s_arr[j]);

i++;

j--;

}

} while (i <= j);

 

if (i < last)

qs(s_arr, i, last);

if (first < j)

qs(s_arr, first, j);

}

 

На рис. 5.7 приведен результат выполнения программы листинга 5.4.

 

 

Рис. 5.7. Результат работы программы листинга 5.4

 

 

Упражнения

1. Упорядочить массив из n числовых элементов методом пузырька по возрастанию.

2. Упорядочить массив из n числовых элементов методом пузырька по убыванию.

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

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

5. Используя алгоритм сортировки выбором, упорядочить массив из n числовых элементов по убыванию.

6. Используя алгоритм сортировки выбором, упорядочить массив из n числовых элементов по возрастанию.

7. Упорядочить четные элементы массива из n числовых элементов методом пузырька по возрастанию.

8. Упорядочить нечетные элементы массива из n числовых элементов методом пузырька по убыванию.

9. Упорядочить массив из n символов методом пузырька в алфавитном порядке.

10. Упорядочить массив из n символов методом быстрой сортировки в алфавитном порядке.

11. Упорядочить массив из n символов методом сортировки вставкой в алфавитном порядке.

12. Упорядочить массив из n числовых элементов методом пузырька по возрастанию числа их делителей.

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

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

15. Задан список студентов с указанием их среднего балла за текущую сессию. Упорядочить список студентов по убыванию балла, а в случае равенства баллов, упорядочить список студентов в алфавитном порядке.

16. Задан список студентов с указанием числа их прогулов за текущий семестр. Упорядочить список студентов по убыванию числа прогулов, а в случае равенства прогулов, упорядочить его в алфавитном порядке.

17. Задан список сотрудников с указанием отдела, в котором они работают. Упорядочить список сотрудников по убыванию номера отдела, а в случае равенства номеров отделов, упорядочить его в алфавитном порядке.

18. Упорядочить массив из n элементов следующим образом: положительные элементы по возрастанию, а отрицательные – по убыванию.

19. Заданы два упорядоченных массива из n и m элементов. Построить массив размерностью n+m с той же упорядоченностью.

20. Заданы два упорядоченных массива из n и m элементов. Построить массив размерностью n+m с противоположной упорядоченностью.

21. Упорядочить массив из n элементов следующим образом: сначала положительные элементы по убыванию, а затем отрицательные элементы по возрастанию.

22. Задан список финалистов лыжного соревнования с указанием фамилии и результата в минутах. Упорядочить список по возрастанию результатов, а в случае равенства результатов, указать фамилии спортсменов в алфавитном порядке.

23. В налоговой инспекции составлен список налогоплательщиков с указанием фамилии и суммы уплаченного налога. Упорядочить список налогоплательщиков по убыванию заплаченной суммы, а в случае равенства сумм указать фамилии налогоплательщиков в алфавитном порядке.

24. В налоговой инспекции составлен список налогоплательщиков с указанием фамилии и суммы задолженности по налогам. Упорядочить список налогоплательщиков по возрастанию суммы, а в случае равенства сумм указать фамилии налогоплательщиков в алфавитном порядке.

25. Задан список сотрудников некоторой фирмы с указанием фамилии и суммы, заработанной за месяц. Упорядочить список сотрудников по убыванию заработанной суммы, а в случае равенства сумм упорядочить фамилии сотрудников в алфавитном порядке.