![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Ссылки и многомерные массивыСодержание книги
Поиск на нашем сайте
Для решения одних и тех же задач можно использовать многомерные массивы и массивы указателей. Для простоты сравнения возьмем двумерный массив и одномерный массив указателей. Пусть имеем следующие определения: short a[10][10]; short *b[10]; и пусть оба массива используются аналогичным образом, т.е. a[5][5] и b[5][5] допустимые обращения к одному и тому же целому значению. Тогда под массив a будет выделена память размером в 100 целых значений (200 байтов), а под массив b – размером в 10 указателей типа short. Если каждая ссылка массива b указывает на массив из 10 целых, то потребная память для решения составит: 100 целых + 10 указателей на short. Кроме того, необходимо будет динамически выделять память под массив. Однако, не требуется вычислять адрес элемента двумерного массива, а можно обратиться прямо по ссылке. Второе преимущество: каждый элемент массива ссылок может указывать на на массив, количество элементов которого может быть произвольным, т.е. с его помощью можно реализовать так называемые непрямоугольные массивы, содержащие разное число элементов в младших измерениях. Обычно это используют при работе с массивами строк (string). См. пример "Инициализация массива ссылок". Пример. Вывод сообщений в окна. #include <conio.h> #define Screen BLACK void message(short nom, // Номер сообщения short reg){ // Режим: 1-вывод сообщения, 0-очистить окно static struct mes{ // Описание сообщения short beg_x, // Начальная позиция окна по x beg_y, // Начальная позиция окна по y end_x, // Конечная позиция окна по x end_y, // Конечная позиция окна по y regim; // Режим вывода текста: 'r' – с разрядкой, 'p' - плотный char *text; // Текст сообщения } def[ ]={ // Инициализация списка сообщений 28, 2, 54, 4, 'r', "ВВОД ДАННЫХ", 19, 12, 61, 14, 'p', "Имя файла входных данных", . . . 19, 12, 61, 14, 'r', "ВВОД ДАННЫХ ЗАКОНЧЕН" }; struct mes *p; // Указатель на элемент списка p = &def[nom-1]; if (reg){ // Вывод сообщения в окно init_window(p->beg_x, p->beg_y, p->end_x, p->end_y, BLACK, LIGHTGRAY, 1); out_text(2, 2, 200, p->regim, p->text); } else { /* Очистка окна */ clear_window(p->beg_x, p->beg_y, p->end_x, p->end_y, Screen); } } /* End message */ Рекурсивные процедуры В языках C и Basic любая процедура может быть рекурсивной, т.е. в ее теле может быть обращение к самой себе. Такие процедуры применяются для реализации класса рекурсивных алгоритмов, наиболее простым и известным из которых является вычисление функции факториала.
Пример. Вычислить n!=n*(n-1)!. short factorial(short n){ short fact; if (n == 0){ // Условие завершение рекурсии return 1; } else { fact = n * factorial(n – 1); } return fact; } Рекурсия реализуется с помощью рассмотренной выше структуры данных – стека. При этом не предусматриваются никакие механизмы защиты памяти, вследствие чего при неправильном программировании терминальной ветви рекурсивного алгоритма (см. пример выше) автоматически выделяемая память под каждый рекурсивный вызов (программный стек) будет переполняться и вызывать прерывание программы во время выполнения (run time error) с сообщением stack overflow (переполнение стека). Рекурсивные процедуры работают не быстрее нерекурсивных, но зато они более компактны и понятны. Ниже разбирается пример реализации более сложного рекурсивного алгоритма. Для сравнения приводятся 2 нерекурсивных решения той же задачи. Пример. "Ханойская башня". Это последовательность дисков различного диаметра, положенных друг на друга так, чтобы диск меньшего диаметра располагался сверху. Требуется: переместить башню с одной площадки на другую с соблюдением следующих условий: - за 1 раз переносится 1 диск; - нельзя ставить диск большего диаметра на диск меньшего диаметра; - можно использовать только одну резервную площадку.
Рисунок ниже иллюстрирует процесс решения для n=2 и n=3. n=2 n=3 Площ. 1 Площ. 2 Площ. 3 Площ. 1 Площ. 2 Площ. 3 В соответствии с рисунком рекурсивное решение для n=3 записывается так:
hanoi(1, 2, 3) = 1à 2 hanoi(3, 2, 2) Для произвольного n и произвольных номеров площадок от 1 до 3 получим:
hanoi(a, b, n) = a à b hanoi(6-a-b, b, n-1) Здесь: - a - № начальной площадки, - b - № конечной площадки, - n – число дисков в башне. В общем случае для решения задачи требуется 2n -1 операций переноса дис- ков. Решение представляется в выводе на экран последовательности номеров начальной и конечной площадок. Для n=4 решение имеет вид: 1 à 3 1 à 2 3 à 2 1 à 3 2 à 1 2 à 3 1 à 3 1 à 2 3 à 2 3 à 1 2 à 1 3 à 2 1 à 3 1 à 2 3 à 2 Рекурсивное решение void hanoi( short a, // № начальной площадки short b, // № конечной площадки short n){ // Число дисков if (n == 1){ // Конец рекурсии printf(" %2d %2d\n", a, b);
return; } hanoi(a, 6-a-b, n-1); printf(" %2d %2d\n", a, b); hanoi(6-a-b, b, n-1); } // End hanoi При каждом рекурсивном вызове процедуры hanoi транслятор помещает значения аргументов a, b, n в так называемый стек вызова, т.е. программисту не надо вручную записывать операции помещения в стек и извлечения из стека. В нерекурсивном решении возможны 2 варианта реализации стека: в виде массива и в виде списка.
|
||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-08; просмотров: 485; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.221.158.39 (0.01 с.) |