Вставка элемента b в упорядоченный массив X, не нарушив его упорядоченности

⇐ ПредыдущаяСтр 2 из 2

Пусть массив Х(N) упорядочен по возрастанию, необходимо в него вставить элемент b, не нарушив упорядоченности массива.

int main()

{

float x[20], b;

int i, j, n;

cout< < " n=";

cin> > n;

cout< < " Massiv x\n";

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

cin> > x[i];

cout< < " b=";

cin> > b;

if (b> =x[n-1])

x[n]=b;

else

{

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

if (x[i]> b)

{j=i; break; }

for(i=n; i> j; i--)

x[i]=x[i-1];

x[j]=b;

}

n++;

cout< < " Massiv x\n";

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

cout< < " x(" < < i< < " )=" < <

x[i]< < " \t";

cout< < endl;

return 0;

}

Найдем максимальный элемент главной диагонали двумерного целочисленного массива размерностью nxn, заданного случайными числами на промежутке [-100; 100).

/*Описание функции поиска максимального элемента главной диагонали*/

int maxi(int str, int slb, int m[max_x][max_y]){

int i, j, e_max=m[0][0];

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

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

if((i==j)& & (m[i][j]> e_max))

e_max=m[i][j];

return e_max;

}

Пример 5. Найдите сумму элементов столбца двумерного массива, номер которого задается с клавиатуры.

/*Описание функции суммирования элементов заданного номера столбца матрицы*/

int summa(int str, int slb, int nom, int m[max_x][max_y]){

int i, j, sum=0;

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

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

if(j==nom-1) sum+=m[i][j];

return sum;

}

Пример 6. Дан двумерный вещественный массив размерностью nxn, заданный случайными числами на промежутке [-100; 100). Замените все элементы выше главной диагонали на 1.1 и ниже ее на 0.0.

//Описание функции замены

void zamena (int str, int slb, double m[max_x][max_y]) {

int i, j;

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

for (j=0; j< slb; j++) {

if (i> j) m[i][j]=0.0;

if (i< j) m[i][j]=1.1;

}

Сортировка в двумерном целочисленном массиве элементов k-той строки по невозрастанию.

void sort_dn(int k, int slb, int m[max][max]) {

int i, j, buf;

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

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

if (m[k][j]> m[k][j-1]){

//фиксированная строка с номером k

buf= m[k][j];

m[k][j]= m[k][j-1];

m[k][j-1]=buf;

}

Для поиска максимальных (минимальных) элементов с целью их дальнейшего упорядочивания удобно выделять отдельно одномерный массив, в котором хранить не значения элементов, а номера столбцов или строк, в которых они располагаются. Например, чтобы найти минимальные элементы в каждом столбце массива n x m отдельно, удобно выделить одномерный массив min[m], в котором число элементов равно числу столбцов. Значениями элементов такого массива будут номера строк, в которых располагаются минимальные элементы каждого столбца. Если же минимальных элементов в столбце несколько, то будет найден первый (или последний) минимальный, что не скажется на значении.

Пример 2. Поиск номеров минимальных элементов в каждом столбце двумерного массива.

void minimum(int str, int slb, int m[max][max], int min[max_y]){

int i, j;

for (j=0; j< slb; j++){//фиксируем номер столбца

min[j]=0;

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

//пробег по столбцу, меняется номер строки

if (m[i][j]< m[min[j]][j]) min[j]=i;

}

В данном примере min[max_y] – это массив, значениями которого будут номера строк, в которых располагается первый минимальный элемент столбца. Так для min[j] начальное значение инициализируется как 0, то есть предполагается, что минимальный элемент расположен в строке с номером 0. Обращение m[min[j]][j] понимается так: элемент массива m, расположенный в строке с номером min[j] и столбце с номером j. Но в строке min[j] для столбца j как раз и находится минимальный элемент.

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

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

void obmen(int strslb, int m[max][max]) {

int i, buf, t;

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

//номера строки и столбца элемента главной диагонали равны

buf= m[i][i];

//t-номер столбца соответствующего элемента побочной диагонали

t= abs(strslb-i-1);

m[i][i]= m[i][t];

m[i][t]=buf;

}

Пример 4. Дана квадратная матрица размера n x n, заполненная с клавиатуры целыми числами так, что в каждой строке и каждом столбце ровно по одному нулевому элементу. Переставьте строки матрицы так, чтобы нулевые элементы были расположены вдоль главной диагонали. Выведите массив на экран в виде таблицы дважды – до и после перестановки. Оформите генерацию, вывод массива и перестановку строк с помощью функций.

#include " stdafx.h"

#include < iostream>

using namespace std;

#define max 10

void gen (int k, int x[max][max]);

void out (int k, int x[max][max]);

void change (int k, int x[max][max]);

int _tmain(int argc, _TCHAR* argv[]) {

int a[max][max];

int n;

do {

printf(" \nВведите количество элементов массива n (n< =%d): ",

max);

scanf (" %d", & n);

}

while (n> max);

gen(n, a);

out(n, a);

change(n, a);

out(n, a);

system(" pause" );

return 0;

}

void gen (int k, int x[max][max]){

int i, j;

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

printf(" \nВведите значения элементов %d-й строки

массива: \n", i);

for (j=0; j< k; j++){

printf(" x[%d][%d]= ", i, j);

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

}

void out (int k, int x[max][max]){

int i, j;

printf(" \nВывод значений %d элементов массива в строку: \n", k);

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

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

printf(" \t%d", x[i][j]);

printf(" \n" );

}

void change (int k, int x[max][max]){

int i, j, buf;

int zero[max]; //массив номеров столбцов нулевых элементов

for (i=0; i< k; i++) //инициализация массива

zero[i] = -1;

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

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

/*генерация массива номерами столбцов, в которых

расположены нулевые элементы*/

if (x[i][j]==0) {

zero[i]=j;

j=k;

}

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

for (j=0; j< k; j++){

/*обмен значениями элементов текущей строки с

соответствующей, чтобы нулевой элемент занял место на

главной диагонали*/

buf=x[i][j];

x[i][j]=x[zero[i]][j];

x[zero[i]][j]=buf;

/*после перестановки строк изменяется номер столбца

нулевого элемента*/

zero[zero[i]]=zero[i];

}

В данном примере zero[max] – это массив, значениями которого будут номера столбцов, в которых располагается нулевой каждой строки (по условию задачи, такой элемент в каждом столбце и каждой строке единственный). Обращение x[zero[i]][j] понимается так: элемент массива x, расположенный в строке с номером zero[i] и столбце с номером j. Но для строки с номером i нулевой элемент располагается в столбце с номером zero[i]. Для каждого элемента главной диагонали индексы строки и столбца равны, поэтому нулевой элемент из столбца zero[i] должен быть перемещен в строку с аналогичным номером (вместе со всеми элементами этой же строки). Обращение zero[zero[i]] означает, что после перестановки строк с номерами i и zero[i] нулевой элемент строки zero[i] будет находиться в столбце с номером zero[zero[i]].

Примеры

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

Пример 1

/*обращение массива*/ #include < stdio.h> main() { int p, i=0; Static a[10]={10, 11, 12, 13, 14, 15, 16, 17, 18, 19}; while(i< 10/2) { p=a[i]; a[i]=a[9-i]; a[9-i]=p; i++; } i=0; while(i< 10) printf(" %d", a[i++]); }

Пример2. Найти среднее арифметическое элементов заданного массива.

#include< stdio.h>
#define TEN 10 //так объявляются константы. Менять значения TEN после этого объявления мы не имеем права
//Здесь же константе TEN мы присвоили значение 10

Void main()

{
float a[TEN], s=0; //мы объявили массив типа float из TEN(десяти) элементов и переменную s

Int i; //переменная цикла

printf(" Введите массив: " );

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

scanf(" %d", m[i]); /*последовательный ввод массива*/

for(i=0; i< TEN; i++)
s = s+a[i]; /*нахождение суммы элементов*/

s=s/TEN; //нахождение среднего арифметического делением суммы на TEN, то есть на 10
printf(" s = %8.2f", s);
}

Приведем несколько примеров, в которых ведется обработка двумерных массивов. Но прежде одну полезную возможносить языка Си. Речь идет о препроцессорном утверждении #dеfine, позволяющем присваивать символические имена константам.

В общем случае это утверждение записывают так:

#define строка1 строка2(точка с запятой не ставится).

Прежде чем исходный текст программы будет передан компилятору, он обрабатывается препроцессором, котоый всюду в исходном текстезаменит вхождение " строка1" на " строка2". Например, строка #difine max 80, записанная в начале программы, обеспечит всюду замену указанного имени maxна соответствующую константу. Замена имени связана не только числами, но и текстами.

А теперь вернемся к примерам. В следующей программе (пример 3) строится единичная матрица a[m][m], размер которой определяется с помощью конструкции #difine m 5.Сам алгоритм вычисления элементов матрицы основан на возведении (i/j)*(j/i)равно единице тогда и только тогда. когда iравно j.В остальных случаях оно равно нулю.

Пример 3

#define M 5 #include < stdio.h> main() { int a[M][M]; int j, i=0; while(i< M) { j=1; while(j< M) { a[i][j]=(i/j)*(j/i); printf(" %d", a[i][j]); j++; } i++; printf(" \n" ); } }

⇐ Предыдущая 12