14. C-sharp 8 22-10-2013

Created Saturday 23 November 2013

** Алгоритмы и структуры данных
** Nicolas Virt
** При рекурсивном алгоритме метод вызывает себя, что может
приводить к переполнению стека, поэтому всегда, когда
возможно, следует реализовывать циклические алгоритмы
вместо рекурсивных, или, как минимум, контролировать
внутренний вызов метода, чтобы ограничивать глубину
вызовов.
** Любой рекурсивный алгоритм можно реализовать циклом.
** Бинарный поиск в отсортированном массиве
*** Любой алгоритм поиска ищет значение и возвращает индекс
*** После каждой итерации поиска массив уменьшается в 2 раза
*** Чем больше массив, тем эффективнее бинарный поиск
*** Необходимо знать, как отсортирован массив (возрастание или убывание)
*** 1) Вычисляется индекс центра массива и сравнивается значение с искомым числом
*** 2) Если значение середины меньше/больше, то 1-я/2-я половина массива отбрасывается
*** 3) Выполняется та же операция (рекурсия)
*** 4) Если в какой-то момент поиск середины даёт один и тот же результат,
то искомого элемента в массиве нет
*** Индексация при работе с базами данных - это создание отсортированного
массива для бинарного поиска
*** Если есть несколько одинаковых значений, то можно делать дополнительную проверку
соседних элементов (массив упорядоченный!)
** Линейная структура - когда у каждого элемента один индекс (одномерный массив)
** Домашнее задание:
+ :
Таблица крестики-нолики. В массиве хранятся данные символьного типа char.
Написать программу для игры в крестики-нолики, используя двухмерный массив.
Играют 2 игрока: х и о. При запуске программы на экране видна доска.
Под доской программа запрашивает Ваш ход. Игрок вводит: х,1,2 -
Это значит, что х будет поставлен в 1-ю строку и во второй столбец (считаем
от нуля). Программа записывает доску и отображает её по новой. И опять
программа просит ввод. Вводится: 0,2,2. Необходимо всё время проверять
столбцы, строки и диагонали - если кто-то выиграл - game over (или когда
не осталось свободных мест). Имеет смысл инициализировать массив пробелами -
с одной стороны, это символ, а с другой его не видно. Можно напечатать
таблицу с пустыми ячейками. Программа проверяет правильность очерёдности
ввода - нельзя два раза подряд пойти х или о. Программа проверяет правильность
указания индексов (от out of range). Программа проверяет окончание игры.
+ :
Версия банковской задачи с использованием 3-х мерного массива.
Есть 4 банка: M, A, D, L. В каждом банке есть 3 периода:
1, 7, 30. 0-10, 10-25, 25-50, 50-100, 100+ - вклады. В массиве хранится
годовой процент на краткосрочный вклад в указанном банке на
определённый срок в определённой сумме.
double[,,] = new double[BANKS,RANGES,PERIODS];
Решить задачу "банковский калькулятор", где проценты хранятся в виде 3-х-мерного
массива. С клавиатуры вводится: "Введи банк", "введи срок", "введи сумму". Программа
вычисляет сумму заработка за указанный срок в указанном банке.
+ :
Спроектировать структуры данных исходя из заданного:
на заводе есть два цеха, в каждом цеху по три конвейера, на каждом конвейере работает
по 5 человек. О каждом работнике известно: адрес, по которому он проживает -
город, улица, номер дома; дата приёма на работу; его социальное положение -
женат, одиночка, разведён, вдовец); пол - м. ж.; оклад; информация о премиях,
которые он получал в течение года каждый месяц - премия состоит из 2х значений -
сумма и описание, за что получил.
3х мерный массив таких структур (инумы не забыть внутри и т.д.)
Программа должна: а) заполнить данными информацию о рабочих; б) выполнять
следующие операции: всем работникам 1го цеха, проживающим в Хайфе, увеличить
зарплату на 10%; всем работникам, отработавшим более 3х лет женского пола
выплатить премию в марте 200шк с пометкой "Международный женский день";
всем неженатым работникам мужского пола выплатить премию за все зимние
месяцы в размере 5% от их зарплаты с пометкой "За мужество"; всем работникам
завода выплатить премию за декабрь в размере минимальной премии за 1-е полугодие,
а если он не получал, то в размере 1% от зарплаты.



Backlinks: