А. Для заданного натурального числа определить количество единичных бит в его представлении.

Арифметические операторы.

Основные арифметические операторы: сложения, вычитания, умножения, деления. В языке С++ применяются для представления арифметических действий. В С++ нет оператора возведения в степень.

+ (сложение): +x, x+y
- (вычитание): -x, x-y
* (умножение): x*y
/ (деление): x/y
% ( остаток от деления): x%y

Существуют префиксные и постфиксные операторы.
Префиксные (до) указывают C++ сначала увеличить (или уменьшить) значение переменной, а затем использовать это значение.
Постфиксные (после) указывают C++ сначала использовать значение переменной, а затем увеличить (или уменьшить) его.

1.2. Побитовые операторы.
К побитовым, или поразрядным операторам относятся:
операторы поразрядного И (побитовое умножение) &;
операторы поразрядного ИЛИ (побитовое сложение) |;
операторы поразрядного исключающего ИЛИ ^;
унарный оператор поразрядного отрицания ~.
оператор сдвига влево <<;
оператор сдвига вправо >>;

Операнды поразрядных операций могут быть любого целого типа.

Оператор & часто используется для маскирования некоторого множества битов.

Оператор | используется для включения битов

Используя оператор ^ можно обменять значения двух переменных, не используя третью: x=x^y, y=x^y, x=x^y

Оператор << (сдвиг влево) выполняет побитовый сдвиг влево левого операнда на количество разрядов, соответствующее значению правого операнда. Сдвиг на 1 бит эквивалентный умножению на 2. Результатом является целое число.

Оператор >> (сдвиг вправо): выполняет побитовый сдвиг вправо левого операнда на количество разрядов, соответствующее значению правого операнда. Если число без знака, то левые биты = 0. Сдвиг на 1 бит эквиалентный делению на 2. Результатом является целое число.

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

Логические операторы

В качестве операндов выступают логические значения, результат – тоже логическое значение
! (отрицание)

|| (логическое “или”)
&& (логическое “и”)

1.4. Операторы сравнения (отношения).
Любое значение, не равное нулю, - истина. Если тождественно равное нулю – ложь.Операторы сравнения и логические операторы не изменяют значения своих операндов, а только вычисляют значение: 0 (false), 1 (true).

Сравнивать можно операнды любого типа, но

либо они должны быть оба одного и того же встроенного типа (сравнение на равенство и неравенство работает для двух величин любого типа),
либо между ними должна быть определена соответствующая операция сравнения.

Результат – логическое значение true или false.

1.5. Приоритет операторов определяется круглыми скобками. В противном случае предполагается, что операторы имеют следующие относительные приоритеты.

! -(изменение знака) + + + - -(унарные)
* / %
+ -
<< >>
< <= > >= = = !=
&
^
|

&&
||
? : (условный оператор)

Выражения

Программа оперирует с данными. Числа можно складывать, вычитать, умножать, делить. Из разных величин можно составлять выражения, результат вычисления которых – новая величина.

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

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

1.7. Преобразование типов

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

Для явного преобразования типа выражения используется оператор:
(<тип>) <выражение>
где в скобках – один из простых типов данных.
(int) (1.5 / 0.3); // тип int
(float) (1.5 / 0.3); // тип float

В выражении приоритет преобразования типов данных приравнивается к приоритету унарных операторов.

Инструкция break

Прекращает работу блока switch и циклов.

Инструкция continue.

Инструкция continue вынуждает ближайший содержащий ее цикл (for, whileили do-while) начать следующий шаг итерации. Операторы, стоящие в цикле после continue, не выполняются.

Инструкция goto.

Инструкция goto позволяет реализовать передачу программного управления из одной точки программы в другую, отмеченную мет­кой перехода. Метка перехода состоит из идентификатора и за­вершающего двоеточия, как и метки switch-оператора.

Конструкция имеет синтаксис: gotoметка;

Выход из программы exit()

С помощью функции ехit() можно прервать выполнение программы в любом месте. Такой вы­ход из программы исполь­зуется при возникновении серьезной ошибки, которая делает дальней­шее выполнение программы бессмысленным или невоз­можным.

2.5. Инструкция if …else.

В некоторых ситуациях необходимо указать не только оператор (блок операторов), выполняемый в случае получения результата trueпри вычислении условия, но и оператор (блок операторов), выполняемый при получении результата false.

Синтаксис инструкции выбора в этом случае будет следующим:
if (условие) оператор;
else оператор;

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

В качестве оператора может выступать отдельный оператор или блок операторов. Отдельный оператор всегда должен заканчиваться точкой с запятой (ограничителем операторов). Если используется блок операторов, то он должен быть заключен в фигурные скобки.

Вложение else if

С помощью ключевых слов if и else можно составлять так называемые else-if-конструкции, которые могут осуществить проверку сразу нескольких выражений, не используя сложные условия .
if (условие) оператор;
else if (условие) оператор;
else if (условие) оператор;
… else оператор;

Условия проверяются в той последовательности, в которой они перечислены в программном коде.

Если результатом одного из условий является true (1),то выполняется следующий за условием оператор и проверка оставшихся elseif-условий не осуществляется.

Если ни одно из проверенных условий не дало в результате значения true,то выполняются операторы, относящиеся к последнему else.

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

Инструкция switch

С помощью оператора switch программа может передать управление в одну из нескольких точек программы в зависимости от значения выражения.

switch (выражение) {

case константа_1: оператор; break;

case константа_2: оператор; break;

case константа_3: оператор; break;

…

case константа_m: оператор; break;

default: оператор;

}

Выражение должно иметь целочисленный тип. Значение выражения сопоставляется со всеми находящимися внутри switch-оператора case- константами.

Оператор, указанный после case-метки, выполняется, если значение switch-выражения равно соответствующей константе. Если ни с одной из case-констант совпадения нет, то управление передается на конструкцию с default-меткой, при условии ее наличия, в противном случае ни одна из подынструкций switch не выполняется.

Так как case-константы являются метками, то после найденного совпадения операторы будут выполняться последова­тельно до тех пор, пока не закончится switch-оператор. Поэтому после каждого блока операторов, относящегося к конкретной case-метке, необходимо указать ключевое слово (оператор) break(если это необходимо). Оператор breakсразу же передает программное управление за пределы switch-оператора, завершая его.

Оператор цикл for

Цикл for является циклом с предпроверкой условия выхода. Конструкция for-цикла имеет синтаксис: for (выражение1; выражение2; выражение3) оператор;

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

Выражение2 формулирует условие выполнения цикла (т.е. если выражение2 истинно, то операторы тела цикла выполняются, в противном случае происходит выход из цикла). Если выражение2 опущено, то считается, что его значение всегда истинно. В последнем случае операторы тела цикла будут повторяться до тех пор, пока один из них не приведет к выходу из цикла.

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

Раздел оператор может состоять из одного оператора или из блока операторов. Отдельные операторы должны всегда заканчиваться точкой с запятой. Если в качестве тела цикла выступает блок операторов, то он должен быть заключен в фигурные скобки.

3.2. Бесконечный цикл for(;;) представляет собой особый вид цикла for. Он получается, если все три элемента определения цикла for опустить и оставить только точки с запятой, разделяющие элементы.

Программно выход из такого цикла может быть осуществлен только с помощью оператора break , так как условие выхода из цикла не указано.

Цикл do-while

В языке С++ существует конструкция цикла do или do-while. Самое важное его отличие от цикла while состоит в том, что операторы тела цикла do выполняются хотя бы один раз. Оценка выражения, содержащего условие выхода из цикла, происходит всегда после выполнения тела цикла. Конструкция цикла имеет синтаксис:

do оператор

while (выражение);

Цикл while

Цикл while является циклом с предпроверкой условия выхода. Конструкция while-цикла имеет синтаксис:
while (выражение)

оператор; //тело цикла

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

В качестве оператора может выступать отдельный оператор или блок операторов. Отдельный оператор всегда должен за­канчиваться точкой с запятой (ограничителем операторов). Если тело цикла представляет собой блок операторов, то он должен быть заключен в фигурные скобки.

Выражение цикла while вычисляется прежде, чем выполняются операторы тела цикла.

Условием выхода из цикла является равенство нулю (false) выражения цикла.

Если при первом же вычислении выражения цикла while получено значение false (0), то операторы тела цикла не выполняются ни разу.

Алгоритм Евклида

Дана пара (a, b).
Шаг 1. Поделить a на b с остатком r
Шаг 2. Если r = 0, то НОД (a, b) = b
Шаг 3. Если r <>0, то перейти к шагу 1 с парой (b, r)

do

if (a>b)

a%=b;

else

b%=a;

while ((a !=0) && (b!=0));

Алгоритмы обмена чисел

Имеется две переменные a и b. Поменять их значения местами.
int a,b, tmp;
{1}
tmp = a; a = b; b = tmp;
{2}
a = a + b; b = a - b; a = a - b;
{3}
a = a ^ b; b = a ^ b; a = a ^ b;

C. Перевод из 10-й с/с в 2..9

int a,r;
{ // ввод n
a = 0; r = 1;
while (n >= 1)
{
a = a + (n % p) * r; r = r * 10;
n = n / p;
}

либо

int main()

{

char M1[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

int M[32]; //Массив под остатки

int a,i,n;

scanf("%d %d", &a, &n);

i=0;

while (a!=0)

{

M[i]=a%n;

a/=n;

i++;

}

for(i--;i>=0;i--)

printf("%c", M1[M[i]]);

printf("\n");

}

D. Дихотомический поиск

int BinSearch(int *M, int left, int right, int x)

{

int mid;

while (left<=right)

{

mid=(left+right)/2;

if (M[mid]==x)

return(mid);

else

{

if (M[mid]>x)

right=mid-1; else

left=mid+1;

}

}

return(-1);

}

F. Совершенные числа

Натуральное число Р называется совершенным, если оно равно сумме всех своих делителей кроме Р. Доказано, что если р и 2р-1 - простые числа, то число Р=(2р-1)*2^(p-1) является совершенным

void Number_Sover (){

int n,k,p,i,flag,ch;

printf("Enter N ");

scanf("%d",&n);

p=2;i=1;

while (i<=n) {//простое или нет

int j=2;

flag=1; //да

while ((j<=p/2) && (flag))

if ( !(p%j)) flag=0;//нет

else ++j;

if ((flag)||(p==2) ||(p==3)){

int step=1; int m=p-1; int x=2;

while (m != 0){

if (m % 2 == 1) step=step*x;

x=x*x;

m=m / 2;

}

ch=step*(step*2-1);

printf("%d \n",ch);

i++;

}

p++;

}}

E. Числа Мерсенна

Числами Мерсенна называют числа вида 2^n-1

void Number_Mersenne(int m)

{

printf("CM\n");

int r=0;

for (int i=1;i<=m;i++)

{

r=(2<<i-1)-1;

printf("%d\n",r);

}

}

F. Числа Армстронга

n-значное число называется числом Армстронга, если оно равно
сумме n-ых степеней своих цифр.

#include <stdio.h>

#include <math.h>

int main()

{

long a,b,k,c,chislo,z;

long double m,t,k1;

m=0; k=0;

printf("Input two borders a b (a<b): ");

scanf("%d %d", &a, &b);

for (int i=a; i<b+1; ++i){ //перебор всех чисел

m=0; k=0; z=i; chislo=i;

while (z) //определение количества знаков

{k++;

z/=10;}

k1=k;

for (int p=1; p<k+1; ++p) //подсчет суммы степеней цифр

{

c=chislo%10;

chislo=(chislo-c)/10;

t=pow(c,k1);

m+=t;

}

if (m==i)

printf("chislo Armstronga: %d\n", i);

}}

G. Числа Фибоначчи
Число называется числом Фибоначчи, если оно является одним из членов последовательности:
fn = fn-1 + fn-2,
где f0 = 1 и f1 = 1.

Можно также определить n-й член ряда Фибоначчи, непосредственно подсчитав выражение:

H. Числа Смита

Число называется числом Смита, если сумма цифр числа равна сумме цифр разложения этого числа на простые множители.

Функция main()

main – это имя главной функции программы. С функции main всегда начинается выполнение. У функции есть имя (main), после имени в круглых скобках перечисляются аргументы или параметры функции (в данном случае у функции main аргументов нет). У функции может быть результат или возвращаемое значение.

Параметры функции

Все параметры в функции C передаются по значению, т. е. при вызове функции в стек заносится копия значения фактического параметра, и операторы в теле функции работают с этой копией. Поэтому значения фактических параметров, которые переданы в функцию, не изменяются. Передача параметров по значению предусматривает следующие действия:

1. При компиляции функции выделяются участки памяти для формальных параметров.
2.Формальные параметры - это внутренние объекты функции. Для параметров типа float формируются объекты типа double. Для параметров типа char, short int создаются объекты типа int.
3.Если параметром является массив, то формируется указатель на начало этого массива и он служит представлением массива-параметра в теле функции.

4. Вычисляются значения выражений, использованных в качестве фактических параметров при вызове функции.
5. Значения выражений-фактических параметров заносятся в участки памяти, выделенные для формальных параметров функции.
6. В теле функции выполняется обработка с использованием значений внутренних объектов-параметров, и результат передается в точку вызова функции как возвращаемое ею значение.
7. Никакого влияния на фактические параметры функция не оказывает.

Для того чтобы обеспечить изменение передаваемых в функцию фактических параметров, необходимо явно передать адрес изменяемого параметра. Этого можно достичь двумя способами: 1) в качестве формального параметра описать указатель на тип, с которым будем работать; 2) использовать ссылки.

ФУНКЦИИ ОБЩЕГО НАЗНАЧЕНИЯ

В заголовке <stdlib.h> объявляется набор функций, служащих для преобразования данных, генерации случайных чисел, получения и установки переменных среды, управления выполнением программ и выполнения команд.
Abs - модуль целого числа
bsearch - двоичный поиск
qsort - сортировка массива

Для получения псевдо-случайных чисел используют функции int rand(void);

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

void srand(unsigned int );

Эту функцию можно применить для полyчения другой последовательности, использyя некотоpyю величинy.

Алгоритм зависит от статической переменной "random seed"; выдаваемые значения циклически повторяются через число вызовов rand, равное значению этой переменной.

Ввод-вывод массивов

Ввод элементов одномерного массива организовать цикл.
for (int i=0; i<n; i++)
{
printf ("введите элемент массива");
scanf("%d",&A[i]);
}

Вывод элементов одномерного массива.

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

printf("%d \n",A[i]);

// то же можно и через cout

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

printf("%d ",A[i]);

Вывод в 2 столбца:
for ( i=0;i<n-1;i+=2)
{
printf("%-5d%-5d\n",A[i],A[i+1]);
printf("%d\t%d\n",A[i],A[i+1]);
}

Ввод элементов двумерного массива
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
scanf("%d",&Ma[i][j]);

// Вывод матрицы построчно, каждое число в 5 позициях
for (int i=0;i<n;i++)
{ for (int j=0;j<m;j++)
printf("%5d",Ma[i][j]);
printf(“\n"); }
}

Передача массивов функциям

Для передачи массивов-параметров функций формальный параметр массив можно объявить тремя способами:

-указатель, тип которого будет совпадать с типом элементов массива;
int function (int *a, int n) {……}-массив с фиксированной длиной;
int function ( int a[20]) {……}-безразмерный массив.
int function ( int a[], int n) {……}

Когда двумерный массив используется как параметр функции, необходимо передать указатель на первый элемент. Функция, получающая двумерный массив должна как минимум определять размерность первого измерения. Формальный параметр двумерный массив можно объявить следующими способами:
· двумерный массив с фиксированной длиной;
int function ( int ma[100][100]){……} Для использования этой функции двумерный массив должен быть описан с максимальной размерностью int Ma[100][100], но можно обрабатывать размерности n*m.

· двумерный с фиксированной размерностью первого измерения, т.е. второй размерностью; int func ( int ma[][100]) {…}Для использования этой функции двумерный массив должен быть описан со второй размерностью =100

· указатель, которому при вызове буде соответствовать адрес первого элемента двумерного массива;
int func ( int *ma) {……} В этом случае массив должен быть точно такой же размерности, как при вызове.

· указатель на двумерный массив, тип которого будет совпадать с типом элементов массива. int func ( int **ma) {……}- двумерный массив должен быть описан как указатель на указатель, для int **ma необх.ВыделитьПамятьНекоторойРазмерности n*m,но можно<= n*m

Переменные-указатели

Указатель – это переменная, которая содержит адрес памяти. Этот адрес как правило является адресом некоторой другой переменной.

Тип данных переменных, на который указывает указатель называется базовым типом данных. Стандартный вид объявления указателя:

Тип * имя

int *ip, *iq; // указатели на целые объекты
flоat *fp; // указатель на символьный объект
char *cp; // указатель на символьный объект
char *const ср; // константный указатель на char
char const* pc; //указатель на константу типа char
int x;

Указатели и массивы

Имя массива - это константный указатель

Адрес массива можно присвоить обычному указателю
int *pa=a;

pa - адрес a[0],
*(pa+1) есть содержимое a[1]
a+i - адрес a[i],
*(pa+i) - содержимое a[i].

Элемент массива можно изображать как в виде указателя со смещением, так и в виде имени массива с индексом.

Между именем массива и указателем, выступающим в роли имени массива, существует одно различие.

Указатель - это переменная, поэтому можно написать pa=a или pa++.

Имя массива не является переменной, и записи вроде a=pa или a++ не допускаются.

Массивы-параметры

Для передачи массивов-параметров функций формальный параметр массив можно объявить тремя способами:

-указатель, тип которого будет совпадать с типом элементов массива;
int function (int *a, int n) {……}-массив с фиксированной длиной;
int function ( int a[20]) {……}-безразмерный массив.
int function ( int a[], int n) {……}

Когда двумерный массив используется как параметр функции, необходимо передать указатель на первый элемент. Функция, получающая двумерный массив должна как минимум определять размерность первого измерения. Формальный параметр двумерный массив можно объявить следующими способами:
· двумерный массив с фиксированной длиной;
int function ( int ma[100][100]){……} Для использования этой функции двумерный массив должен быть описан с максимальной размерностью int Ma[100][100], но можно обрабатывать размерности n*m.

· двумерный с фиксированной размерностью первого измерения, т.е. второй размерностью; int func ( int ma[][100]) {…}Для использования этой функции двумерный массив должен быть описан со второй размерностью =100

· указатель, которому при вызове буде соответствовать адрес первого элемента двумерного массива;
int func ( int *ma) {……} В этом случае массив должен быть точно такой же размерности, как при вызове.

· указатель на двумерный массив, тип которого будет совпадать с типом элементов массива. int func ( int **ma) {……}- двумерный массив должен быть описан как указатель на указатель, для int **ma необх.ВыделитьПамятьНекоторойРазмерности n*m,но можно<= n*m размерности <= n*m.

Указатели на функции.

Имя функции является адресом этой функции в памяти.

Язык программирования Си позволяет определять указатели на функции. Например, следующая инструкция
int (*fp)(int x, int y);

Пример
int add(int x, int y)
{ return x + y;}
int sub(int x, int y)
{ return x - y;}

void main()
{
int (*p)(int, int);
p = add;
/* вызываем функцию через указатель */
printf("1 + 2 = %d\n", (*p)(1, 2));
p = sub;
/* можно вызвать функцию и так */
printf("1 - 2 = %d\n", p(1, 2));
return 0;

}

12.9. Указатель на void
Существует указатель на объект любого типа: void* имя; Действия с указателем:
· переменной типа void* можно присвоить указатель на объект любого типа;

· void* нельзя разыменовывать.

· void* можно явно преобразовать в указатель на другой тип.

· один void* можно присвоить другому void*;
· пару void* можно сравнивать на равенство и неравенство;
· нельзя изменять void* (размер объекта неизвестен)

Основными применениями void* являются:
-передача указателей функциям, которым не позволено делать предположения о типе объектов
-возврат объектов «неуточненного типа» из функций.

Чтобы воспользоваться таким объектом, необходимо явно преобразовать тип указателя.

12.9. Алгоритмы преобразование и перестановки .

void swaptmp(int *px, int *py) /* перестановка *px и *py */
{
// Обмен чисел
int temp;
temp = *px;
*px = *py;
*py = temp;
}

void swap(int *px, int *py)
/* перестановка *px и *py */
{
// Обмен чисел
*px ^= *py;
*py ^= *px;
*px ^= *py;
}

int* Revers(int *a, int n)
// Переворачивание элементов массива
{
int k;
for (int i=0;i<n/2;i++)
{
k=a[i];
a[i]=a[n-i-1];
a[n-i-1]=k;
}
return a;}

int* ReversP(int *a,int n)
{
int k;
for (int i=0;i<n/2;i++)
{
k=*(a+i);
*(a+i)=*(a+n-i-1);
*(a+n-i-1)=k;
}
return a;
}

int* ReversL(int *a,int n)
{
for (int i=0;i<n/2;i++)
{
*(a+i)^=*(a+n-i-1);
*(a+n-i-1)^=*(a+i);
*(a+i)^=*(a+n-i-1);
}
return a;
}

Сортировка пузырьком

Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий" элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности.

void sort( int *array, int size )

{

register int i, j;

int temp;

for( i = size - 1; i > 0; i-- )

{

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

{

if( array[j] > array[j+1] )

{

temp = array[j];

array[j] = array[j+1];

array[j+1] = temp;

}

}

}

return; }

Сортировка Вставками

Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].

На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива.

Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.

В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.

void sort( int *array, int size )

{

register int i, j;

int temp;

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

{

temp = array[i];

for ( j = i - 1; j >= 0; j--)

{

if( array[j] < temp )

break;

array[j+1] = array[j];

}

array[j+1] = temp; }}

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

На этот раз при просмотре мaccива мы будем искать наименьший элемент, сравнивая его с первым. Если такой элемент

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

в первую позицию в таблице. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать

подобным образом, пока не рассортируем весь массив.

void sort( int *array, int size )

{

register int i, j, k; int temp;

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

{

temp = array[i];

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

{

if( temp > array[j] )

{

temp = array[j];

k = j;

}

}

temp = array[i];

array[i] = array[k];

array[k] = temp; }

return; }

Линейный поиск

Линейный, последовательный поиск — нахождения заданного

элемента в некотором массиве. Поиск значения осуществляется простым сравнением очередного значения и искомого, если значения совпадают, то поиск считается завершённым. Если у массива длина = N, найти решение можно за N шагов. Сложность алгоритма - O(n). В связи с малой эффективностью линейный поиск используют только

если N не большое.

1. Определяем начало интервала поиска и выбираем элемент для поиска.

2. Cравниваем образец с выбранным элементом.

Если элемент совпадает с образцом, то определяем его индекс и переходим к шагу 4.

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

4. Если индекс определен, то элемент найден, иначе - искомого элемента в массиве нет.

int LineSearch (int *a, int n, int x)

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

if (a[i] == x)

return i;

return -1; // элемент не найден

Сортировка Шелла

Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.

Рассмотрим следующий алгоритм сортировки массива a[0].. a[15].

1. Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1],a[9]), ... , (a[7], a[15]).

2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).

В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п.

3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).

4. В конце сортируем вставками все элементы

void Shella( int *a,int n)

{

int h, i, t;

int k; // пpизнак пеpестановки

h=n / 2; // начальное значение интеpвала

while (h>0)

{ // цикл с yменьшением интеpвала до 1

// пyзыpьковая соpтиpовка с интеpвалом h

k=1;

while (k)

{

// цикл, пока есть пеpестановки

k=0;

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

{ //сpавнение эл-тов на интеpвале h }

if (a[i]>a[i+h])

{

t=a[i]; a[i]=a[i+h]; a[i+h]=t;

k=1; // пpизнак пеpестановки

}

}

}

h=h / 2; //{ yменьшение интеpвала } } }

Бинарный поиск.

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

1. Определяем середину интервала поиска.

2. Сравниваем образец с элементом, расположенным посередине. Если образец оказался больше, то областью дальнейшего поиска становится правая половина; в противном случае - левая половина интервала, но в любом случае индексный интервал уменьшается вдвое. (Если осуществить еще одну проверку, то можно установить и совпадение, после чего дальнейшие шаги не обязательны.)

3. Если остался интервал единичной длины, то переходим к заключительному шагу 4, в противном случае - к шагу 1.

4. Либо единственный элемент интервала совпадает с образцом, либо - искомого элемента в массиве нет.

int BinarySearch(int a[],i, j, int x)

{

int , middle;

while (i <= j)

{

middle = (i + j)/2;

if (x == a[middle])

return middle;

else

if (x > a[middle])

i = middle + 1;

else
j = middle - 1;

}

return -1;

}

Сортировка Слияниями

#include <stdio.h>

#include <stdlib.h>

void merge(int a[], int lb, int split, int ub)

{

int pos1=lb;

int pos2=split+1;

int pos3=0;

int *temp =(int*)malloc((ub-lb+1)*sizeof(int));

while (pos1<=split && pos2<=ub)

{

if (a[pos1]<a[pos2])

temp[pos3++]=a[pos1++];

else

temp[pos3++]=a[pos2++];

}

while (pos2<=ub)

temp[pos3++]=a[pos2++];

while (pos1<=split)

temp[pos3++]=a[pos1++];

for (pos3=0; pos3<ub-lb+1; pos3++)

a[lb+pos3]=temp[pos3];

free(temp);

}

void mergsort(int a[], int lb, int ub)

{

int split;

if (lb<ub)

{

split = (lb + ub)/2;

mergsort(a, lb, split);

mergsort(a, split+1, ub);

merge(a, lb, split, ub);

}

}

void main()

{

int c[5];

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

scanf("%d", &c[i]);

mergsort(c, 0, 4);

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

printf("%d ", c[i]);

}

Указатели и строки

Смысл заключается в том, что сама строка никогда не копируется. Оператор создает второй указатель, ссылающийся на ту же самую строку.

Сравнение строк

int strcmp(const char *str1, const char *str2);

int strncmp (const char *str1, const char *str2, size_t n);

лексикографически сравнивает не более чем n первых символов из строк str1 и str2. Функция возвращает –1, 0 или 1, если первые n символов из строки str1 соответственно меньше, равны или больше первых n символов из строки str2.

char* strstr(const char *str1, const char *str2);

находит первое вхождение строки str2 (без конечного нулевого байта) в строку str1. В случае успеха функция возвращает указатель на найденную подстроку, а в случае неудачи – NULL. Если указатель str1 указывает на строку нулевой длины, то функция возвращает указатель str1.

Копирование строк

char *strcpy(char *strDst, const char *strSrc);

копирует строку strSrc в строку strDst. Строка strSrc копируется полностью, включая завершающий нулевой байт. Функция возвращает указатель на strDst. Если строки перекрываются, то результат непредсказуем.

char *strncpy(char *strDst, const char *strSrc, size_t n);

копирует n символов из строки strSrc в строку strDst. Если строка strSrc содержит меньше чем n символов, то последний нулевой байт копируется столько раз, сколько нужно для расширения строки strSrc до n символов. Функция возвращает указатель на строку str1

char* strcat(char *strDst, const char *strSrc);

присоединяет строку strSrc к строке strDst, причем завершающий нулевой байт строки strDst стирается. Функция возвращает указатель на строку strDst.

char* strncat(char *strDst, const char *strSrc, size_t n);

присоединяет n символов из строки strSrc к строке strDst, причем завершающий нулевой байт строки strDst стирается. Если длина строки strSrc меньше n, то присоединяются только символы, входящие в строку strSrc. После соединения строк к строке strDst всегда добавляется нулевой байт. Функция возвращает указатель на строку strDst

Поиск символа в строке.

char* strchr(const char *str, int c);

ищет первое вхождение символа, заданного параметром c, в строку str. В случае успеха функция возвращает указатель на первый найденный символ, а в случае неудачи – NULL.

char* strrchr(const char *str, int c);

ищет последнее вхождение символа, заданного параметром c, в строку str. В случае успеха функция возвращает указатель на последний найденный символ, а в случае неудачи – NULL.

size_t strspn(const char *str1, const char *str2);

возвращает индекс первого символа из строки str1, который не входит в строку str2.

Функция

size_t strcspn(const char *str1, const char *str2);

возвращает индекс первого символа из строки str1, который входит в строку str2.

char* strpbrk(const char *str1, const char *str2);

находит в строке str1 первый символ, который равен одному из символов в строке str2. В случае успеха функция возвращает указатель на этот символ, а в случае неудачи – NULL.

Разбор на лексемы

char* strtok(char *str1, const char *str2);

возвращает указатель на следующую лексему (слово) в строке str1, в которой разделителями лексем являются символы из строки str2. В случае если лексемы закончились, то функция возвращает NULL. При первом вызове функции strtok параметр str1 должен указывать на строку, которая разбирается на лексемы, а при последующих вызовах этот параметр должен быть установлен в NULL. После нахождения лексемы функция strtok записывает после этой лексемы на место разделителя нулевой байт.

Память

void *memchr(const void *str, int c, size_t n);

Ищет первое вхождение с в n байтах str.

int memcmp(conct void *str1, const void *str2, size_t n); Сравнивает первые n байт str1 и str2.

void *memcpy(void *str1, const void *str2,size_t n); Копирует n байт из str2 в str1

void *memmove(void *str1, const void *str2,size_t n); Копирует n байт из str2 в str1, перекрыв. Строк

void *memset(void *str1, int c,size_t n);

Копирует c в n байт в str1.

Функции преобразования строк и числовых данных.

в заголовочном файле stdlib.h, который нужно включить в программу.

строки в число типа int

int atoi(const char *str);

которая в случае успешного завершения возвращает целое число, в которое преобразована строка str, а в случае – неудачи 0. Например,

строки в число типа long

long int atol(const char *str);

которая в случае успешного завершения возвращает целое число, в которое преобразована строка str, а в случае – неудачи 0. Например,

строки в число типа double

double atof(const char *str);

которая в случае успешного завершения возвращает плавающее число типа double, в которое преобразована строка str, а в случае – неудачи 0.

Функции преобразования строк и числовых данных.

long int strtol(const char *str, char **endptr, int base);

преобразует строку str в число типа long int, которое и возвращает. Если аргумент base равен 0, то преобразование зависит от первых двух символов строки str:

если первый символ – цифра от 1 до 9, то предполагается, что ч<