Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

VPS в России, Европе и США

Бесплатная поддержка и администрирование

Оплата российскими и международными картами

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Книги: [Классика] [Базы данных] [Internet/WWW] [Сети] [Программирование] [UNIX] [Windows] [Безопасность] [Графика] [Software Engineering] [ERP-системы] [Hardware]
     

Секреты поваров компьютерной кухни или ПК: решение проблем

Касперски К.

Издано: 2003, BHV
Твердый переплет, 560 стр..

Аннотация
Статьи из книги

[Заказать книгу в магазине "Мистраль"]

Динамические библиотеки для гурманов

(статья была опубликована в журнале "Программист")

Динамическая библиотека - не статичный набор экспортируемых функций. Это живой организм, доверху напичканный хитростями и секретами поистине с неограниченными возможностями. Продолжая тему предыдущей статьи, здесь мы поговорим о механизмах автоматической инициализации/деинициализации, рассмотрим функцию DllMain (некоторое подобие функции main - стартовой функции языка Си) и откроем один элегантный способ разделения данных между несколькими процессами.

Все примеры превосходно работают во всех версиях Windows и "благословлены" самой Microsoft - пользуйтесь ими без тени опаски. Рекомендуемый автором компилятор - Microsoft Visual C++, совместимость с остальными не гарантируется (хотя и предполагается).

Не прощайтесь по-английски!

Предположим, вашей DLL требуются функции инициализации и деинициализации. О деиницилизации следует сказать особо - поскольку, при отключении DLL выделенная ею память сама собой не освобождается, а открытые файлы - не закрываются, "расчистку мусора" приходится выполнять самой DLL самостоятельно.

Делать это "вручную", вызывая перед отключением DLL специальную функцию, - утомительно, да и небезопасно (программист может забыть это сделать, порождая трудноуловимую ошибку утечки ресурсов). Лучше бы инициализация/деинициализация DLL происходила автоматически при каждом ее подключении/отключении. И такая возможность действительно есть!

Если DLL хочет получать уведомления о важнейших системных событиях она должна иметь особую функцию (не экспортировать ее! просто иметь, - обо всем остальном позаботится компилятор) - BOOL WINAPI DllMain( HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpvReserved), в чем-то похожую на функцию main языка Си. Но сходство это обманчиво. Функция main вызывается один лишь раз при загрузке программы, а DllMain получает управление неоднократно и больше напоминает цикл выборки сообщений, но обо всем по порядку.

Через DllMain система уведомляет динамическую библиотеку о следующих событиях:

  1. проецирование DLL на адресное пространство процесса (подключение);
  2. отключение DLL от адресного пространства процесса (освобождение);
  3. создание подключившим DLL процессом нового потока;
  4. завершение потока, созданного подключившим DLL процессом

Каждому событию соответствует "свое" значение аргумента fdwReason, передаваемого функции DllMain при его возникновении. Поэтому, ее код выглядит приблизительно так (неправда ли, внешне очень похоже на цикл выборки сообщений?):


BOOL APIENTRY DllMain(HINSTANCE hinstDLL,
      DWORD fdwReason, LPVOID lpvReserved)
{
  switch (fdwReason)
  {
    case DLL_PROCESS_ATTACH:  // Подключение DLL
      // Выполняем все необходимые
      // действия по инициализации

      // если инициализация прошла
      // успешно возвращаем TRUE
      // в противном случае – FALSE
      return 1; 

    case: DLL_PROCESS_DETACH: // Отключение DLL
      // Выполняем все действия
      // по деинициализации
      break;

    case DLL_THREAD_ATTACH: // Создание нового потока
      // Переходим на многопоточную версию,
      // если необходимо
      break;

    case DLL_THREAD_DETACH: // Завершение потока
      // Освобождаем переменные, связанные с потоком
      break;
  }
    return TRUE;  // Возвращаем что-нибудь (все равно
        // код возврата игнорируется)
}

Листинг 19 Пример реализации функции DllMain

DLL_PROCESS_ATTACH – с этим значением DllMain вызывается всякий раз когда какой-то процесс загружает DLL явной или неявной компоновкой. Некоторые популярные писатели, в том числе и такой бесспорный авторитет как Джеффри Рихтер в своей монографии "Windows для профессионалов", утверждает, что для каждого процесса DLL_PROCESS_ATTACH вызывается лишь однажды. Выходит, если процесс освободит библиотеку вызовом FreeLibrary, а потом загрузит ее вновь, функция DllMain вызвана не будет? Возникает вопрос - а как же тогда инициализировать DLL при ее повторных подключениях? К счастью, никаких хитрых трюков изобретать не надо - DLL_PROCESS_ATTACH вызывается всегда - сколько бы раз библиотека ни проецировалась на процесс.

Замечание: другое дело - попытка повторной загрузки уже загруженных (и еще не выгруженных!) библиотек. В этом случае LoadLibrary просто возвращает описать экземпляра указанной DLL, естественно не вызывая функцию DllMain. Именно это и хочет сказать Рихтер, но, во всяком случае в русском переводе, высказывает свою мысль очень нечетко и двусмысленно.

Если инициализация прошла успешно, функция DllMain должна возвратить TRUE, в противном случае - FALSE, при этом вызов LoadLibrary, пытающийся загрузить DLL, возвратит ошибку, а процесс, подключающий DLL неявной компоновкой, будет аварийно завершен.

DLL_PROCESS_DETACH – с этим значением DllMain вызывается при отключении DLL - освобождении ее FreeLibrary, завершении загрузившего ее процесса и неудачной инициализации. О последнем следует сказать особо - Джеффри Рихтер в "Windows для профессионалов" замечает "сначала проверьте: не собираетесь ли Вы очищать то, что инициализировать не удалось" и далее приводит фрагмент кода где (по его мнению) сидит жучок:

case DLL_PROCESS_ATTACH:

pvData = HeapAlloc(GetProcessHeap(), 0, 1000);

if (pvData == NULL) return FALSE;

case DLL_PROCESS_DETACH:

HeapFree(GetProcessHeap(),0, pvData);

break;

Листинг 20 Попытка освобождения невыделенного блока памяти по мнению Рихтера приводит к исключению, на самом же деле нет.

Если выделение памяти не происходит, управление передается ветке DLL_PROCESS_DEACH, пытающийся освободить то, что не было выделено. Во избежание проблем Рихтер рекомендует переписать последний фрагмент кода так: if(pvData !=NULL) HeapFree(GetProcessHeap(),0, pvData).

На самом деле - это ни к чему. HeapFreee не настолько глупа, чтобы вызвать исключение при попытке освобождения нулевого указателя. То же самое можно сказать и о других функциях. Автору так и не удалось придумать пример в котором "освобождение того, что инициализировать не удалось" приводило бы к фатальной ошибке.

Единственный случай, когда выгрузка DLL происходит без обращения к DLL -завершение загрузившего ее процесса вызовом TerminateProcess. Для разработчика динамических библиотек это означает, что их деинициализация выполняется не всегда, поэтому недопустимо "оставлять на потом" такие важнейшие операции как, например, сброс дисковых буферов или удаление временных файлов. В то же время, независимо от способа завершения процесса, гарантируется освобождение объектов ядра, пользовательского интерфейса и всей выделенной памяти - за это отвечает сама операционная система и за утечку ресурсов (включая глобальные объекты синхронизации - мутанты, семафоры и т.д.) можно не волноваться.

DLL_THREAD_ATTACH - уведомляет DLL о создании загрузившим ее процессом нового потока. Зачем DLL знать о каких-то там потоках? А вот зачем - далеко не каждая динамическая библиотека может работать в многопоточной среде - это не так-то просто, как кажется поначалу. Возьмем к примеру тривиальную функцию вывода текста на экран и подумаем, что произойдет, если в процессе вывода строки функцию вызовет другой поток. Правильно, образуется полная каша! Чтобы этого избежать необходимо прибегнуть к критическим секциям или другим средствам синхронизации. Однако использование их в однопоточной среде - бессмысленная трата ресурсов. Гораздо лучше, отслеживая создание новых потоков, обращаться к критическим секциям только если они действительно нужны.

К сожалению, механизм уведомлений очень плохо продуман и здесь не обходится без проблем. Во-первых, создание процессом нового потока еще не означает, что в нем используются функции загруженных DLL - так зачем же впустую переходить на мнопоточность? Во-вторых, уведомления поступают только от потоков, созданных после загрузки DLL, а обо всех, существующих на момент ее загрузки, динамическая библиотека ничего не знает!

Это отнюдь не означает, что уведомление DLL_THREAD_ATTACH бесполезно, - просто на его использование наложено множество ограничений и оговорок. Ради справедливости стоит отметить - неявная компоновка снимает большую часть проблем, поскольку, динамические библиотеки подключаются раньше остальных потоков и исправно получают уведомления об их создании.

DLL_THREAD_DETACH - уведомляет DLL о завершении потока, созданного процессом. Если динамическая библиотека создает для каждого потока свои "персональные" ресурсы (как правило - локальные переменные и буфера), то это уведомление позволяет их своевременно освобождать.

Аргумент hinstDLL во всех случаях содержит описатель экземпляра DLL, требующийся для вызова многих функций пользовательского интерфейса (например, LoadIcon). Чаще всего, получив значение описателя при инициализации, его сохраняют в глобальной переменной для последующего использования. Хотя, это и неединственное решение - чтобы не засорять программу глобальными переменными многие предпочитают получать описать "на лету", вызовая GetModuleHandle.

Аргумент lpvReserved указывает на способ подключения DLL - если он равен нулю, динамическая библиотека загружена с явной компоновкой и, соответственно, наоборот. Чаще всего DLL совершенно ни к чему знать способ своей загрузки, т.к. с ее точки зрения и явная и неявная компоновка совершенно идентичны.

Позвольте продемонстрировать все вышесказанное на одном простом примере - скелете настоящей DLL, которая ничего не делает, а только отслеживает происходящие события.


// Test.c
// Тестовая DLL
#include <stdio.h>
#include <windows.h>  // Не забудьте подключить этот
        // хидер, т.к. в нем содержится описание
        // типов APIENTRY, HINSTANCE и др.

// Объявляем функцию DllMain
BOOL APIENTRY DllMain(HINSTANCE hinstDLL,
      DWORD fdwReason, LPVOID lpvReserved)
{

switch (fdwReason)      // Дерево разбора уведомлений
{
  case DLL_PROCESS_ATTACH: // Подключение DLL
    printf("Подключение DLL\n");
    // Получение описателя экземпляра DLL
    printf("HINSTANCE = %x\n",hinstDLL);

    if (lpvReserved)  // Определение способа загрузки
      printf("DLL загружена с неявной компоновкой \n");
    else
      printf("DLL загружена с явной компоновкой \n");
    return 1; // успешная инициализация

  case DLL_PROCESS_DETACH: // Отключение DLL
    // Здесь – освобождаем память, закрываем
    // файлы и т.д.
    printf("Отключение DLL\n");
    break;

  case DLL_THREAD_ATTACH: // Уведомление о новом потоке 
    // Здесь – если надо переходим на
    // многопоточный режим работы с
    // использованием средств синхронизации
    // таких как критическая секция, мутанты,
    // семафоры и т.д.
    printf("Создание процессом нового потока\n");
    break;

  case DLL_THREAD_DETACH:
      //Уведомление о завершении потока
    // Здесь – если надо освобождаем все ресурсы, 
    // вязанные с завершившимся потоком. Какой именно
    // поток завершился можно узнать просмотром списка
    // потоков средствами TOOLHELP32
    printf("Завершение потока\n");
    break;

  }
return TRUE;    // Код возврата игнорируется
}

Листинг 21 Демонстрация обработки событий, получаемых динамической библиотекой

В Microsoft Visual C++ этот пример компилируется так: "cl test.c /LD". Теперь необходимо создать два загрузчика только что полученной DLL - для явной и неявной компоновки соответственно.


// Load1.c
// Загрузчик тестовой DLL с явной компоновкой
#include <stdio.h>
#include <windows.h>
#include <process.h>    // Необходим для _beginthread

int Thread(void *x)
{
  // Пустой поток
  // Он необходим лишь для того, чтобы
  // продемонстрировать получение динамической
  // библиотекой уведомлений о создании и
  // завершении потоков
  return 0;
}

main()
{
  // Загружаем DLL
  HINSTANCE h; h=LoadLibrary("Test.dll");
  if (!h){ printf("Ошибка загрузки DLL"); return;}

  _beginthread(Thread,0,0);  // Создаем новый поток.
  Sleep(100);        // Поспим чуток
  FreeLibrary(h);      // Выгружаем библиотеку
}

Листинг 22 Пример простейшего загрузчика динамической библиотеки

Этот пример компилируется так: "cl Load1.c LIBCMT.LIB", где LIBCMT.LIB - многопоточная библиотека, содержащая в себе код функции "_beginthread". При линковке возникнет следующее "ругательство" "LINK: warning LNK4098: defaultlib "LIBC" conflicts with use of other libs; use /NODEFAULTLIB:library" (Внимание - библиотека по умолчанию LIBC конфликтует с другими библиотеками; используйте ключ /NODEFAULTLIB:library для решения проблемы). На это можно не обращать внимания, т.к. поток, созданный нами, пустой и заведомо не использует функций Си-библиотек.

Запустим полученный файл на выполнение и убедимся, что DLL исправно принимает уведомления обо всех системных событиях:

  Подключение DLL
  HINSTANCE = 10000000
  DLL загружена с явной компоновкой
  Создание процессом нового потока
  Завершение потока
  Отключение DLL

Теперь попробуем загрузить ту же самую DLL с неявной компоновкой. Это не так-то просто, как может показаться на первый взгляд. Ни система, ни компилятор не могут неявно загрузить динамическую библиотеку, не импортируя из нее ни одной функции!

Замечание: hint для ваших защит - поскольку многие хакеры не очень-то осведомлены о тонкостях работы DllMain, имеет смысл поместить в нее некоторый защитный код - пусть взломщики попробуют разобраться как он получает управление!

Что же делать? Не иначе придется экспортировать из DLL хотя бы одну функцию, хотя бы и функцию-пустышку. Назовем ее Demo. Тогда код загрузчика будет выглядеть так (с экспортом функции Demo читатель, надеюсь, справится и самостоятельно):


// Load1.c
// Загрузчик тестовой DLL с явной компоновкой
#include <stdio.h>

__declspec(dllimport) char* Demo();

main() {Demo();}  // Уф как-то не привычно видеть 
      // всю программу в одной строке :-)

Листинг 23 Для явной компоновки DLL, она должна экспортировать по меньшей мере одну функцию, пускай даже функцию-пустышку

Поскольку никаких потоков мы не создавали, результат работы будет выглядеть так:

  Подключение DLL
  HINSTANCE = 10000000
  DLL загружена с неявной компоновкой
  Отключение DLL

Окей, мы видим, что функция DllMain исправно работает, исправно собирая все уведомления. Причем, область ее применения не ограничивается одной лишь инициализацией/де инициализацией.

Позвольте два приема в заключении:

Отслеживание завершения дочерних потоков: пусть ваша программа многократно создает и уничтожает потоки, некоторые из которых создают свои дочерние потоки и так далее без конца. Перед выходом из приложения разумно убедиться, что все порожденные потоки завершили свою работу и не будут прерваны в самый неподходящий момент. Сказать-то легко, а вот попробуй это сделать Да без проблем! Отслеживаем с помощью DllMain создание и завершение потоков, соответственно каждый раз увеличивая или уменьшая некоторую переменную счетчик. Если она равна нулю - вторичных потоков больше нет и приложение можно смело завершать.

Запрет создания потоков: любая DLL может запретить загрузившему ее процессу создавать потоки. Весь фокус в том, что DllMain с уведомлением о создании нового потока вызывает ни кто иной, как сам стартовый код этого потока. Если задержать управление, то поток "повиснет", впрочем, не мешая работать всем остальным. Для чего это может быть нужно? Ну, например, для защиты. Автору попадались несколько динамических библиотек от сторонних разработчиков демонстрационные версии которых имели ограничение - работа только в однопоточной среде. Каким образом блокируется создание новых потоков вы теперь знаете - ну а что делать дальше - думайте сами :-) Не для хакеров: если вы не очень-то уверенно чувствуете себя с отладчиком - самое простое решение - загружать такую DLL после создания всех необходимых вам потоков.

Совместное использование данных несколькими DLL

Предоставление каждому процессу собственного адресного пространства порождает проблему разделения одних данных между несколькими процессами. Как только ни выкручиваются программисты - создают файлы, проецируемые в память, обычные дисковые файлы, прибегают к широковещательной рассылке сообщений и т. д.

Очень эффективный, но малоизвестный трюк заключается в установке такой-то секции DLL атрибута "shared", после чего эта секция будет совместно использоваться всеми загрузившими ее процессами.

Инициализированные перемененные автоматически помещаются компилятором в секцию ".data", а неинициализированные - в секцию ".bss". По умолчанию им обоим присваиваются атрибуты Read и Write, разрешающие и чтение, и запись, но не исполнение или совместное использование! Исправить положение можно с помощью линкера, запустив его следующим образом: "link Имя obj-файла /SECTION:имя секции,атрибуты". Вот, собственно и все премудрости. Не правда ли, это много проще возни с проецируемыми файлами, не говоря уже о других способах?

Замечание: hint - манипулируя атрибутами можно, например, разрешить модификацию секции кода (называется ".text"), что полезно для создания самомодифицирующихся приложений. Правда, вместе с преднамеренной модификацией кода станет возможна и непреднамеренная, поэтому, прибегать к этому способу без лишней нужды не рекомендуется. А если уж и перебегать - то только в окончательно отлаженном приложении, которому не вздумается неожиданно начать себя затирать. В качестве альтернативы можно разрешить выполнение кода в секции данных, присвоив ему атрибут "Executable".

Тогда - переходим от слов к делу! Для начала создадим DLL, экспортирующую некоторую переменную, например, так: "_declspec(dllexport) char buff[666] = "Hello, Sailor\n";" и откомпилируем ее: "cl share.c", "link share.obj /DLL /SECTION:.data,RWS", не обращая внимания на ругательство линкера: "LINK: warning LNK4092: shared section ".data" contains relocations; image may not run correctly" (Внимание: совместно используемая секция ".data" содержит перемещаемые элементы, спроецированный образ может работать не корректно – все будет работать на "ура", т. к. DLL в обоих случаях загружается по одним и тем же линейным адресам).

Теперь создадим два приложения - пусть одно из них что-то пишет в переменную buff, а другое - читает это оттуда. Итак


// Test_w.c
// Приложение-писатель
#include <string.h>
#include <windows.h>
// Подключаем buff неявной компоновкой.
// Можно и явной, но это будет длиннее
__declspec(dllimport) char buff[666];   

main()
{
  strcpy(&buff[0],"Hello, World!\n");  // Пишем
  Sleep(6000);        // Пауза 6 сек
}

// Test_r.c
// Приложение-читатель. Совсем простое :-)
#include <stdio.h>
__declspec(dllimport) char buff[666];
main(){printf("%s\n",&buff[0]);}

Листинг 24 Демонстрация использования совместно используемой памяти через shard-секцию в DLL

Откомпилируем обе программы: "cl test_w.c share.lib" и "cl test_r.c share.lib", а затем запустим приложение-писатель и следом за ним, пока последнее не успело завершиться, приложение-читатель. На экране появится победная надпись: "Hello, World!".

Это работает! И все бы было хорошо, да вот возникает одна проблема - целиком "зашаривать" весь сегмент данных неудобно, да и небезопасно - вдруг некорректно работающая программа, "дорвавшись" до адресного пространства нашей DLL "вырубит весь лес под чистую"! Гораздо удобнее представлять совместный доступ только к некоторым, специально на то предназначенным переменным. Но и такая возможность есть!

Не хочется трогать секцию ".data" - пожалуйста - создадим свою собственную! Достаточно лишь включить в исходный текст программы директиву "#pragma data_seg("Имя секции")", например, так:


// mysection.c
// buff_data помещается в секцию .data по умолчанию
_declspec(dllexport)
   char buff_data[666]="Hello, DATA!\n";

// Создаем новую секцию – .kpnc
// Точка перед именем не обязательна – просто так
// принято
#pragma data_seg(".kpnc")

// Теперь переменная buff_kpnc принудительно
// помещается в секцию .kpnc
_declspec(dllexport)
   char buff_kpnc[666]="Hello, KPNC!\n";

// Указываем компилятору вновь помещать переменные
// в секцию по умолчанию, т.е. .data
#pragma data_seg()

// buff_data2 помещается в секцию .data вслед
// за buff_data
_declspec(dllexport)
   char buff_data2[666]="Hello, DATA2\n";

Листинг 25 Демонстрация создания собственной секции в DLL

Откомпилируем этот пример "cl mysection.c", "link mysection.obj /DLL /SECTION:.kpnc,RSW" и - подать сюда микроскоп - с помощью dumpbin убедимся, что новая секция успешно создана и содержит в себе одну-единственную переменную buff_kpnc, а все остальные находятся в секции ".data". Это можно сделать так: "dumpbin mysection.dll /ALL" (ее ответ занимает очень много места и здесь не приводится).

Теперь модифицируем приложение-читатель и приложение-писатель так, чтобы они работали с переменной buff_kpnc. Ничего экстравагантного от нас не потребуется, достаточно заменить "buff" на "buff_kpnc" вот и все! Работа с импортируемыми элементами не зависит от того, какая секция их экспортирует!

Но довольно о достоинствах, поговорим о недостатках. Секции с атрибутами совместного использования доступны всем процессам, загрузившим эту DLL, и нет никакой возможности защитить ваши данные от посягательств со стороны злоумышленников и некорректно работающих приложений. Проецируемые в память файлы выгодно отличаются тем, что поддерживают атрибуты секретности и позволяют ограничивать совместный доступ только кругом привилегированных лиц. Впрочем, справедливости ради стоит сказать, что атрибуты секретности поддерживает исключительно Windows NT/2000, а Windows 9x их игнорирует, да и под NT совместный доступ чаще всего представляется всем без разбора. Так что отсутствие защиты не такой уж и серьезный недостаток.

Другое, скорее комичное, чем досадное ограничение - неудержимое стремление популярных компиляторов (в том числе и Microsoft Visual C++) запихать все неинициализированные переменные в секцию ".bss". Рассмотрим это на следующем примере:


  #pragma data_seg(".kpnc")
  _declspec(dllexport) int test;
  #pragma data_seg()

Листинг 26 Все неинициализированные переменные принудительно размешаются компилятором в секции .bss

Вы думаете, переменная "test" окажется в секции ".kpnc"? Как бы не так! Компилятор, невзирая на все предписания, поместит ее в секцию ".bss"! Что ж, долго искать выход из этой ситуации не потребуется - присвойте "test" некоторое значение и дело с концом!

И последний недостаток (или это фича?) Как вы думаете, что произойдет если запустить приложение-читатель спустя некоторое время после завершения работы приложения-писателя? Ведь мгновенная выгрузка DLL из памяти не гарантируется, - сколько она будет там оставаться - кто ж знает! Что из этого следует? Из этого много, что следует. Вот, скажем, в результате какой-то ошибки в совместно используемой памяти окажется мусор, отчего работающие с ней приложения зависнут. Казалось бы, выйди из них и запусти опять - ан, нет! Повторные загрузки той же самой DLL не возымеют действия - система исправно спроецирует ее на адресное пространство процесса, но не станет перечитывать с диска. Единственный документированный выход - перезагрузка компьютера. Не нужно быть провидцем, чтобы представить чувства пользователей такого приложения.

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

Об одном нестандартном подходе к решению задач

Все школьные приемы решения задач, так или иначе, сводятся к тому, что сначала каллиграфическим почерком ученик выписывает "Дано", потом "Найти", затем "Решение". Последнее обычно сопровождается ожесточенным покусываем авторучки в поисках оптимального разбиения задачи на более мелкие, не представляющие по отдельности никакой трудности. То есть, говоря математическим языком, - решения с помощью декомпозиции.

Такой подход оптимален для школьных задач потому, что большинство из них составлялось композиционным образом, - то есть, автором учебника бралась за отправную точку некая идея (формула, теорема), а поверх насыпался добрый слой "щебенки", который учащийся и должен был разобрать, проделывая обратный путь.

В жизни же подобной искусственности нет, и наиболее трудным моментом в решении задачи является (ну кто бы мог об этом подумать в школе!) определение того, что нам дано, и что требуется найти.

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

Например, как быстро в уме вычислить, сколько нечетных дней каждого месяца существует в году? Но только не делите 365 на два, потому что это очевидно неверное решение, ведь нумерация дней в году идет не последовательно от одного до 365, а разбита на списки, в каждом из которых может находиться 28, 29, 30 или 31 день. То есть, в одном случае за 30 днем месяца, наступает 1 число следующего, а в другом два нечетных числа "слипаются" и после 31 числа идет 1 день.

Хм, очевидно, что нечетных дней будет ощутимо больше. Но насколько больше? Давайте посчитаем! Так, "длинные" месяцы - Январь, Март, Май, Июль, Август, Октябрь, Декабрь. Итого, выходит нечетных чисел должно быть на семь больше.

Составим простое уравнение x + x  -7 == 365, отсюда 2х == 372, x = 186. Гм, но нет ли более короткого решения (мы все же пытаемся это считать в уме!). Ну конечно же есть! Необходимо только чуть-чуть (на время) изменить условия задачи. Давайте попробуем найти количество четных дней. В самом деле, оно (за исключением февраля) всегда постоянно и в каждом месяце равно пятнадцати. А в феврале, стало быть, четырнадцати. Умножим пятнадцать на десять и добавим еще двадцать девять, - получается 179. Не правда ли просто? А теперь несложно догадаться, что оставшиеся дни в году и будут искомыми нечетными!

Но в чем преимущество такого решения? Вспомним, что в условии не было оговорено, какой нас интересует год - простой или високосный. А, в самом деле, есть ли разница? В первом варианте решения - да, ибо в случае високосных годов наша формула принимает вид: x + x  -8 == 366. Но посмотрите, что происходи со вторым вариантом решения: x == 366 - 179! Или, если это записать в другом виде, x == Число_дней_в_году  - Константа_179.

Вряд ли можно усомниться, что последнее решение элегантнее. А первое и вовсе не верно. Почему? А разве нам кто-то оговаривал, какой именно требуется год? Следовательно, его продолжительность равна Y, а вовсе не 365 дней. Тогда тогда первым уравнением задача не решается.

Кстати, говорят, что программист отличается от простого смертного тем, что пытается проверить задачу на всех, в том числе и бессмысленных, исходных данных. В нашем же случае, приходится явно оговаривать, что Y может принимать только два значения - либо 365, либо 366. Любое другое приведет к бессмысленному результату.

Выходит, что задача решена не в общем, а в частом виде? А каково количество нечетных дней на N-ый день произвольного месяца? То есть, сколько их будет, скажем от первого января 1990 года до 27 октября 2001?

Решая задачу де композиционным способом, пришлось бы для начала найти способ вычисления прошедших дней между двумя произвольными датами, но может быть, существует иной способ решения? Попробуйте отыскать его. Уверяю, что это доставит Вам истинное удовольствие

Аннотация
Статьи из книги

[Заказать книгу в магазине "Мистраль"]

Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

Новости мира IT:

Архив новостей

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...