2. Переборы. Вложенные циклы. Сложность циклических алгоритмов.
1. Перебор. Вложенные циклы.
Очень часто при реализации алгоритмов используются вложенные циклы – когда один цикл запускается внутри другого (например, чтобы перебрать элементы двумерного массива):
int[,] mass = new int[10, 10];
for (int i = 0; i < mass.GetLength(0); i++)
{
for (int j = 0; j < mass.GetLength(1); j++)
{
команды;
}
}Иногда порядок вложения может достигать трех, четырех, пяти и даже более циклов.
2. Сложность циклических алгоритмов.
Чтобы оценить сложность алгоритмов с вложенными циклами, необходимо найти самый большой порядок вложения (остальными можно пренебречь) и записать сложность О(Nz), где Z – максимальный порядок вложения, а N – количество итераций (повторов) цикла.
for ( int i = 0; i < n; i++ )
{
for ( int j = 0; j < n; j++)
{
for ( int k = 0; k < n; k++)
{
команды1;
}
}
}
for ( int i = 0; i < n; i++)
{
for ( int j = 0; j < n; j++)
{
команды2;
}
}Блок «команды1» вложен в три цикла for от 1 до n, а блок «команды 2» - в два цикла for (тоже от 1 до n).
Получим общую сложность алгоритма O(n3) + O(n2).
Но при достаточно больших n вторым слагаемым можно пренебречь.
Тогда сложность данного алгоритма будет равна O(n3).
Время работы циклических алгоритмов можно примерно оценить при любом N, учитывая, что за 1 секунду средненький компьютер выполняет примерно 1000000 операций в секунду.
Пример:
Давайте попробуем заставить компьютер «задуматься». Не будем использовать операторы, которые позволяют вычислить время работы программы (о них поговорим позже), просто оценим время визуально.
Console.Write(("Введите число:"));
int n = Convert.ToInt32(Console.ReadLine());
int k = 0;
for (int i = 0; i<n; i++)
{
for (int j = 0; j < n; j++)
{
k++;
}
}
Console.WriteLine("Расчет закончен!");При вводе 10000 на моем компьютере (выше среднего) отрабатывает практически без пауз, 30000 – уже заметно, 50000 – 5-6 секунд. А дальше – грустно…
Получается, что если в игре зарегистрировано более 50000 игроков, использовать вложенные циклы «в чистом виде» просто нельзя!
Задачи и примеры их решения
1. Перебор подряд идущих чисел (задача про банкоматы)
Условие: Вас попросили написать программу для «однорукого бандита» (автомата для игры на деньги). Но писать алгоритм вероятности генерации победных комбинаций вам не доверили, зная вашу порядочность и честность. Ваша программа должна «подсказывать» автомату, какими купюрами (банкнотами разного номинала) можно выдать выигрыш игроку. На вход подается число S. Необходимо вывести все возможные варианты выдачи суммы ровно S рублей, если в банкомат закладывают купюры по 100, 50, 20, 10 и 5 рублей (мелочь от рубля и ниже в данном казино даже не учитывается).
Console.Write(("Введите сумму:"));
int s = Convert.ToInt32(Console.ReadLine());
int k = 0;
for (int k1 = 0; k1 <= s / 100; k1++)
{
for (int k2 = 0; k2 <= s / 50; k2++)
{
for (int k3 = 0; k3 <= s / 20; k3++)
{
for (int k4 = 0; k4 <= s / 10; k4++)
{
for (int k5 = 0; k5 <= s / 5; k5++)
{
if (k1 * 100 + k2 * 50 + k3 * 20 + k4 * 10 + k5 * 5 == s)
{
k++;
Console.WriteLine("Вариант №" + k + ": " + k1 + "- по 100 руб. " + k2 +
"- по 50 руб. " + k3 + "- по 20 руб. " + k4 + "- по 10 руб. " +
k5 + "- по 5 руб. ");
}
}
}
}
}
}2. Удаление всех знаков препинания из предложения
Условие: В игре, конечно, есть игровой чат, за которым надо постоянно следить, пресекая попытки использования игроками ненормативной лексики. Все время следить за сообщениями достаточно утомительно. Попробуем написать программу, которая будет блокировать сообщения с «плохими» словами. Но сначала полезно немного преобразовать исходную строку чата, вводимую игроком - удалить из нее все знаки препинания и все буквы сделать строчными (маленькими). После этого будет проще искать «неправильные» слова.
string punctuationSymbols = ".,:;!?/*";
Console.WriteLine("Сообщение в чате:");
string userMessage = Console.ReadLine();
string tempString = "";
for (int i = 0; i < userMessage.Length; i++)
{
if (userMessage[i] != '"') //В этой строке знак кавычки в одинарных апострофах
{
bool isPunctuationSymbol = false;
for (int j = 0; j < punctuationSymbols.Length; j++)
{
if (userMessage[i] == punctuationSymbols[j])
{
isPunctuationSymbol = true;
break;
}
}
if (isPunctuationSymbol)
{
tempString += " ";
}
else
{
tempString += userMessage[i];
}
}
}
tempString = tempString.ToLower();
Console.WriteLine("Полученная строка:" + tempString);3. Контроль за «ненормативной» лексикой
Условие: Итак, знаки препинания удалены, все буквы – прописные. Теперь нам надо блокировать некоторые сообщения. Заведем словарь «плохих» слов. И если хоть одно из этих слов найдено в сообщении, сообщение должно блокироваться.
string[] words = {"дурак", "гад", "болван", "идиот", "редиска"};
tempString += " ";
bool hasForbiddenWord = false;
string word = "";
for (int i = 0; i < tempString.Length; i++)
{
if (tempString[i] == ' ')
{
for (int j = 0; j < words.Length; j++)
{
if (word == words[j])
{
hasForbiddenWord = true;
}
}
word = "";
}
else
{
word += tempString[i];
}
if (hasForbiddenWord)
{
break;
}
}
if (hasForbiddenWord)
{
Console.WriteLine("Сообщение заблокировано!");
}
else
{
Console.WriteLine("Ваше сообщение будет отправлено!");
}
Как можно набирать «нехорошие» слова так, чтобы наш алгоритм их «не заметил»?
Итоги занятия
Сегодня мы поговорили про переборные алгоритмы со вложенными циклами, научились определять их сложность и примерное время работы, разобрали примеры, оценили возможность оптимизации алгоритмов.
А на следующем занятии мы попробуем сделать то, чего сделать нельзя: заставим массив изменять свой размер (то есть растягиваться и сжиматься) и поймем, что это не всегда приводит к желаемому результату.