Задачи перестановок в массивах

Задачи замены в массивах

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

Пример 3. Дан одномерный целочисленный массив, заданный случайными числами на промежутке [-50; 50). Заменить в массиве все отрицательные элементы им противоположными.

Для решения задачи выполним просмотр массива с начала. Каждый элемент сравним с нулем, при этом отрицательные значения элементов заменим им противоположными (if (x[i]<0) x[i]=-x[i]). В данной задаче целесообразно выполнить вывод массива дважды: до и после замены.

//Замена отрицательных значений элементов противоположными

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <time.h>

//подключение модуля для генератора случайных чисел

#define max 100

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

//прототип функции генерации массива

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

//прототип функции вывода массива

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

//прототип функции замены

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

int mas[max];

int n;

do {

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

scanf ("%d",&n);

}

while (n>max);

gen(n,-50,50,mas);

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

out(n,mas);

zamena (n,mas);

printf("\nВывод массива после замены отрицательных

элементов на протипоположные:\n");

out(n,mas);

system("pause");

return 0;

}

//Описание функции генерации массива

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

int i;

srand(time(NULL)*1000);

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

x[i]=rand()%(b-a)+a;

}

}

//Описание функции вывода массива в строку

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

int i;

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

printf("%-6d",x[i]);

}

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

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

int i;

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

if (x[i]<0) x[i]=-x[i];

}

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

Пример 4. Дан одномерный целочисленный массив, заданный случайными числами на промежутке [-10; 10). Выполните циклический сдвиг элементов с нулевой позиции вправо на одну позицию. То есть должна быть реализована схема перестановок: x [0] ® x [1], x [1] ® x [2], …, x [ k -1] ® x [0].

Одним из алгоритмов такого циклического сдвига является следующая последовательность действий. Поместим в буфер последний элемент массива (buf=x[k-1]). Выполним смещение остальных элементов вправо на одну позицию (x[i]=x[i-1]). При этом важен порядок смещения: на освободившееся место последнего элемента перемещается предпоследний, на место предпоследнего – предшествующий ему и т.д. В результате таких перемещений освобождается место нулевого элемента, на которое перемещается элемент из буфера. В данной задаче целесообразно выполнить вывод массива дважды: до и после циклического сдвига.

/*Циклический сдвиг элементов в массиве с нулевой позиции на одну позицию вправо*/

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <time.h>

//подключение модуля для генератора случайных чисел

#define max 100

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

//прототип функции генерации массива

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

//прототип функции вывода массива

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

//прототип функции циклического сдвига элементов массива

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

int mas[max];

int n;

do {

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

scanf ("%d",&n);

}

while (n>max);

gen(n,-10,10,mas);

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

out(n,mas);

sdvig (n,mas);

printf("\nВывод массива после циклического сдвига

элементов: \n");

out(n,mas);

system("pause");

return 0;

}

//Описание функции генерации массива

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

int i;

srand(time(NULL)*1000);

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

x[i]=rand()%(b-a)+a;

}

}

//Описание функции вывода массива в строку

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

int i;

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

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

}

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

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

int i,buf;

buf=x[k-1];

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

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

x[0]=buf;

}

Дата добавления: 2014-01-04