2015-03-22
935
// 1. Инициализация генератора случайных чисел
void Randomize()
{
srand(time(0));
}
Функция инициализации генератора случайных чисел использует библиотечные функции srand, в которую в качестве параметра передается текущее время time(0). Прототип функции time находится в заголовочном файле <time.h>.
//2. Генератор случайного числа в диапазоне от 0 до range
int Random(int range)
{
return (rand() % range);
}
Функция генератора случайных чисел использует библиотечную функцию rand (прототип в файле stdlib.h). Функция rand вычисляет псевдослучайное число в диапазоне от 0 до 65535. Для задания числа в заданном диапазоне используется остаток от целочисленного деления генерируемого числа на диапазон range.
// 3. Проверка повторения случайного числа
// c - указатель начала массива, n - индекс нового элемента
int Test_Repetition(int *c, int n)
{ int x, j;
x = 0; // Считаем, что значение новое
// Цикл сравнения со всеми предыдущими
for (j=0; j<n; j++)
if (*(c+n)==*(c+j))
{
x = 1; // Элементы совпали
break;
}
return x;
}
Функция проверки повторения случайного числа используется только тогда, когда по условию задачи необходимо генерировать неповторяющиеся случайные числа. Эта функция простым перебором сравнивает новое число (c[n]) со всеми значениями массива.
|
|
|
// 4. Добавить новый элемент
// с - указатель начала массива, n - номер нового элемента
// range1, range2 – левая и правая границы диапазона
void New_Item(int *c, int n, int range1, int range2)
{ int x = 0; // Элементы массива разные
do
{
c[n] = Random(range2 - range1) + range1; // Новое значение
x =Test_Repetition(c,n); // Проверка на повторение
}
while (x==1); // Повторять, когда элементы совпали
}
В этой функции, если проверка на «неповторимость» элемента не требуется, достаточно использовать только строку присваивания в переменную c[n] результата работы функции Random.
// 5. Заполнение одномерного массива
// c - массив, n - количество элементов
void Filling (int *c, int n, int range1, int range2)
{ int i;
c[0]=Random (range2 - range1) + range1; // Элемент с индексом 0.
// Цикл заполнения массива
for (i=1;i<n; i++) // Цикл заполнения элементов значениями
New_Item(c, i, range1, range2);
}
Для реализации заполнения неповторяющимися числами, в функции заполнения массива приходится первое значение (с индексом 0) задавать отдельно, а не в цикле.
// 6. Распечатка одномерного массива
void Print(int *c, int n)
{ int i;
for (i=0; i<n; i++)
printf("%4d",c[i]);
puts(""); // Переход на новую строку
}
// 7. Поиск минимального значения
// с – указатель на начало одномерного массива,
// n - количество элементов массива,
// index – указатель на индекс минимума
int Min(int *c, int n, int *index)
{ int i, min;
min = c[0]; // Начальное значение минимума
(*index) = 0; // Начальное значение индекса минимума
for (i=1; i<n; i++)
if (c[i]<min)
{
min = c[i];
(*index) = i;
}
return min;
}
В функции поиска минимального значения в массиве обратите внимание на использование параметра-переменной index, которая передается указателем.
|
|
|
// 8. Создание дубликата массива в динамической памяти
int * Copy (int *c, int n)
{ int *m, i;
// Резервирование памяти под дубликат массива
m = (int*)malloc(sizeof(int)*n);
// Копирование массива
for (i = 0; i<n; i++) m[i] = c[i];
// Функция возвращает адрес нового массива
return m;
}
Обратите внимание, что количество резервируемой памяти определяется типом данных одного элемента и количеством элементов в массиве ((sizeof(int)*n)). Так как библиотечная функция для резервирования памяти (malloc) возвращает нетипированный указатель, то требуется преобразование к типу. В данном примере – это преобразование к типу указателя на целое число (int *).
// 9. Обмен элементов местами в массиве
void Exchange (int *c, int n, int k)
{ int tmp; //Переменная для временного хранения данных
tmp = c[n];
c[n] = c[k];
c[k] = tmp;
}
// 10.Сортировка методом прямого поиска
void SearchSort (int *c, int n)
{ int i, min, indexMin; int *p;
for (i=0; i<n-1; i++) // Определить массив с индексами от i до n
{ p = (c+i); // Задать адрес начала массива
min = Min (p, n-i, &indexMin); // Найти минимум в массиве
// Обменять местами минимальный элемент с первым
Exchange (p, 0, indexMin); }
}
Основная часть программы для обработки одномерных массивов может содержать заголовочные файлы, предварительное описание функций и главную часть программы. Предварительно описанные функции (в виде заголовков) могут быть представлены после главной функции.
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>
#define N 15
void Randomize();
int Random(int range);
int Test_Repetition(int *c, int n);
void New_Item(int *c, int n, int range1, int range2);
void Filling (int *c, int n, int range1, int range2);
void Print(int *c, int n);
int Min(int *c, int n, int *index);
int * Copy (int *c, int n);
void Exchange (int *c, int n, int k);
void SearchSort (int *c, int n);
// Главная функция
int main()
{
int m[N];
int min, IndexMin;
int *Duplicate;
Rus();
Randomize();
Title();
puts("\nЗаполнение массива");
Filling(m,N,-30,70);
puts("\nРаспечатка массива\n");
Print (m,N);
puts("\nМинимальное значение массива\n");
min = Min(m,N,&IndexMin);
printf("min = %d его индекс = %d \n", min, IndexMin);
puts("\nСоздание дубликата массива\n");
Duplicate = Copy(m,N);
puts("\nРаспечатка дубликата массива\n");
Print (Duplicate,N);
puts("\nСортировка дубликата методом прямого поиска");
SearchSort(Duplicate,N);
puts("\nРаспечатка дубликата массива после сортировки\n");
Print (Duplicate,N);
puts("\nУдаление дубликата");
free(Duplicate);
return 0;
}
Варианты заданий
1. Заполнить два массива, размером 20 и 30 элементов, соответственно, случайными целыми числами в диапазоне от -50 до 50. Из полученных двух массивов выделить в два массива отдельно отрицательные и положительные числа. Произвести сортировку полученных массивов и исходного массива по возрастанию. Для контроля результата сделать распечатку массивов, в том числе исходного.
2. Заполнить два массива размером 20 и 30 элементов случайным образом буквами латинского алфавита. Заполнить третий массив теми буквами, которые входят и в первый и во второй массив, четвертый массив – оставшимися буквами из первого и второго. Произвести сортировку полученных массивов. Для контроля результата также сделать распечатку массивов, в том числе исходного.
3. Из исходного массива символов, заполненного случайным образом символами с кодами в диапазоне от 21 до 254, выделить в отдельные массивы буквы латинского алфавита, как заглавные, так и прописные. Произвести сортировку полученных массивов. Для контроля результата сделать распечатку массивов, в том числе исходного.
4. В исходном массиве символов, заполненном случайным образом символами с кодами в диапазоне от 21 до 254, выделить в отдельные массивы заглавные гласные и заглавные согласные буквы латинского алфавита. Произвести сортировку полученных массивов. Для контроля результата сделать распечатку массивов, в том числе исходного.
|
|
|
5. Два массива размером 200 и 5 элементов, соответственно, заполните в случайном порядке символами, коды которых расположены в диапазоне от 40 до 200. Проверить входит ли меньший массив полностью в больший и, если это так, то в большем массиве все элементы, принадлежащие меньшему массиву, заменить символом "пробел". Выполните сортировку полученных массивов. Для контроля результата сделайте распечатку массивов, в том числе исходного.
6. В исходном массиве (размер 100 элементов), заполненном символами латинского алфавита и цифр, замените все повторные вхождения каждого символа пробелом, а все повторяющиеся символы поместите во второй массив. Выполните сортировку полученных массивов. Для контроля результата сделайте распечатку массивов, в том числе исходного.
7. Заполните случайным образом массив (100 элементов) поочередно буквами латинского алфавита от A до H и символами цифр от 1 до 8. Проверьте, есть ли в данном массиве записи, сходные с записью ходов коня по шахматной доске, и, если есть заполните ими второй массив. Выполните сортировку полученных массивов. Для контроля результата сделайте распечатку массивов, в том числе исходного.
8. В исходном массиве символов, заполненном случайным образом символами с кодами в диапазоне от 21 до 254, выделить в отдельные массивы строчные гласные и строчные согласные буквы латинского алфавита. Произвести сортировку полученных массивов. Для контроля результата сделать распечатку массивов, в том числе исходного.
9. В виде массива символов дан текст (ввод с клавиатуры). Случайным образом заполните второй массив из 26 элементов символами, отличными от букв латинского алфавита и друг от друга, причем каждый символ должен встречаться один раз. Будем считать, что первый элемент второго массива соответствует букве «а», второй букве «b» и т.д. Требуется зашифровать текст из первого массива, заменяя буквы первого массива символами из второго. Произведите сортировку массивов. Для контроля результата сделать распечатку массивов, в том числе исходного.
|
|
|
10. В массив символов вводится текст на русском языке, состоящий из нескольких слов. Учитывая, что строчные буквы русского алфавита в операционной системе MSDOS расположены не подряд, а разбиты на два диапазона (от «а» до «п» и от «р» до «я»), слова, состоящие только из букв одного из диапазонов поместите в один массив, а другие во второй. Проведите сортировку полученных массивов. Для контроля результата сделайте распечатку массивов, в том числе исходного.
11. Введите с клавиатуры текст в массив символов. Определите, какие из слов в массиве состоят из букв с возрастающими кодами, какие с убывающими и какие из смешанных. Разместите эти слова в отдельные массивы. Произведите сортировку полученных массивов. Для контроля результата сделайте распечатку массивов, в том числе исходного.
12. Дан массив содержащий текст. Среди литер текста особую роль играет знак #, появление которого означает отмену стоящей перед ним буквы, несколько знаков # означает отмену соответствующего числа букв. Создать массив заполненный текстом из первого массива с учетом роли этого знака. (например, ХЭ#E##НЕLO#LO = HELLO). Произвести сортировку полученных массивов. Для контроля результата сделать распечатку массивов, в том числе исходного.
13. Из исходного массива символов, заполненного случайным образом символами с кодами в диапазоне от 21 до 254, выделить в отдельные массивы символы цифр и знаков препинания. Провести сортировку полученных массивов. Для контроля результата сделать распечатку массивов, в том числе исходного.
14. Заполнить два массива, размером 40 и 30 элементов, соответственно, случайными целыми числами в диапазоне от -50 до 50. Из полученных двух массивов создать два массива отдельно, один из которых содержит числа от -10 до 10, а другой – от 20 до 50. Произвести сортировку полученных массивов по возрастанию. Для контроля результата сделать распечатку массивов, в том числе исходного.
15. Заполните случайным образом массив (100 элементов) поочередно буквами латинского алфавита от A до H и символами цифр от 1 до 8. Проверьте, есть ли в данном массиве записи, сходные с записью ходов ладьи по шахматной доске, и, если есть, заполните ими второй массив. Выполните сортировку массивов. Для контроля результата сделайте распечатку массивов, в том числе исходного.
16. Заполните случайным образом массив (100 элементов) поочередно буквами латинского алфавита от A до H и символами цифр от 1 до 8. Проверьте, есть ли в данном массиве записи, сходные с записью ходов ферзя по шахматной доске, и, если есть, заполните ими второй массив. Выполните сортировку массивов. Для контроля результата сделайте распечатку массивов, в том числе исходного.
Контрольные вопросы по теме № 5
1. Какого типа могут быть индексы массивов?
2. Что такое размерность массивов?
3. Для чего нужен «барьер» в сортировке методом прямого включения?
4. Каков алгоритм поиска минимума или максимума в одномерном массиве?
5. Как найти индекс элемента в одномерном массиве по его значению?
6. Алгоритм поиска минимума или максимума в двумерном массиве.
7. Назначение функций random и randomize?
8. Сортировка элементов двумерного массива.
9. Как обратиться к элементу массива по указателю?
