Новые книги

Книга построена в форме иллюстрированных ответов на всевозможные вопросы, которые обычно возникают у начинающего пользователя нетбука. Рассмотрены настройка нетбука, основы работы в Windows 7, установка и использование популярных прикладных программ (антивирусов, архиваторов, переводчиков, гаджетов, бесплатных приложений Google и др.). Особое внимание уделено созданию сети и подключению к Интернету (по ADSL, GPRS, 3G/4G, Wi-MAX и выделенной линии). Продемонстрированы основы работы с браузерами Internet Explorer 8 и Opera, использование электронной почты, обмен сообщениями в ICQ и QIP, организация телефонных разговоров с помощью Skype. Описано подключение мобильного телефона и цифрового фотоаппарата. Показано, как слушать интернет-радио и музыку, смотреть фильмы и многое другое.
Не так давно от столь популярного в наше время прилагательного «креативный»1 образовалось новое существительное. Если вы — один из нас, миллионов людей, зарабатывающих на жизнь своим умом, вас можно смело назвать представителем «креативного класса», или попросту — креативщиком. Каждый день вы решаете проблемы, предлагаете нововведения, разрабатываете системы, создаете дизайнерские решения, пишете, занимаетесь стратегическим планированием и работаете головой. Именно благодаря вам рождаются новые концепции и формируются целые рабочие системы, закладывающие основу будущего экономического роста, — создается принципиально новый продукт, которого не было и в помине, пока на сцену не вышли вы.

Может быть, вы вовсе и не собирались становиться творческой личностью. Более того, возможно, вы даже содрогаетесь всякий раз, когда вас называют «креативным». И это вполне понятно, ведь ярлык «креативщик» обычно вызывает в воображении этакого рекламного гуру из Сохо2, мельтешащего туда-сюда в своих фирменных джинсах за 500 долларов. Скорее всего, вам приятнее называть себя стратегом или менеджером, что звучит более определенно, более реально. Называйте себя как пожелаете, но если вы отвечаете за решение проблем, разработку стратегий или напряженно трудитесь над генерированием новых идей, я буду называть вас креативщиком, даже если выходит, что вы стали им случайно.

2.3.1. Последовательныйпоиск


2.3.1. Последовательный поиск

Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента.

Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В, а Si - количество сравнений, необходимое для его поиска, то

                                                 n
       Max{А} = max{ Si, i=1,n }  ;    Avg{А} =    Pi Si .
                                                i=1

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

Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.

Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:

       /*    последовательный поиск без стоппера    */
       #include 
       main()
       {
       int k[100],v,i;
       for (i=0;i<100;i++) scanf("%d",&k[i]); scanf("%d",&v); i="0;" while(k[i]!="v" && i<100) i++; if (k[i]="=v)" printf("%d %d",v,i); else printf("%d не найден",v); } 

С использованием стоппера программу можно записать в виде:

       /*  последовательный поиск со стоппером    */
       #include 
       main()
       {
       int k[101],v,i;
       for (i=0;i<100;i++) scanf("%d",&k[i]); /* ввод данных */ scanf("%d",&v); k[100]="v;" /* стоппер */ i="0;" while(k[i]!="v)" i++; if (i<100) printf ("%d %d",v,i); else printf ("%d не найден",v); } 

2.3.2. Бинарный поиск

Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка.

Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов .

Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V - элементы списка и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется. Составим программу для ввода данных и осуществления бинарного поиска ключа V в списке К1,К2,...,К100.

     /*    Бинарный поиск      */
     #include 
     main()
     {
     int k[100],v,i,j,m;
     for (i=0;i<100;i++) scanf("%d",&k[i]); scanf("%d",&v); i="0;" j="100;" m="50;" while (k[m]!="v)" { if (k[m] < v) i+="m;" else j="m-i;" m="(i+j)/2;" } printf("%d %d",v,m); } 

2.3.3. М-блочный поиск

Этот способ удобен при индексном хранении списка. Предполагается, что исходный упорядоченный список B длины N разбит на M подсписков B1,B2,...,Bm длины N1,N2,...,Nm, таким образом, что B=B1,B2,..,Bm.

Для нахождения ключа V, нужно сначала определить первый из списков Bi, i=1,M, последний элемент которого больше V, а потом применить последовательный поиск к списку Bi.

Хранение списков Bi может быть связным или последовательным. Если длины всех подсписков приблизительно равны и M= N, то Max М-блочного поиска равен 2 N. При одинаковой частоте использования элементов Avg М-блочного поиска равен N.

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

Если вместо ключа V имеется упорядоченный список ключей, то последовательный или М-блочный поиск может оказаться более удобным, чем бинарный, поскольку не требуется повторной инициализации для каждого нового ключа из списка V.

2.3.4. Методы вычисления адреса

Методы вычисления адреса. Пусть в каждом из М элементов массива Т содержится элемент списка (например целое положительное число). Если имеется некоторая функция H(V), вычисляющая однозначно по элементу V его адрес - целое положительное число из интервала [0,M-1],то V можно хранить в массиве T с номером H(V) т.е. V=T(H(V)). При таком хранении поиск любого элемента происходит за постоянное время не зависящее от M.

Массив T называется массивом хеширования, а функция H - функцией хеширования.

При конкретном применении хеширования обычно имеется определенная область возможных значений элементов списка V и некоторая информация о них. На основе этого выбирается размер массива хеширования M и строится функция хеширования. Критерием для выбора M и H является возможность их эффективного использования.

Пусть нужно хранить линейный список из элементов K1,K2,..,Kn, таких, что при Ki=Kj, mod(Ki,26)= mod(Kj,26). Для хранения списка выберем массив хеширования T(26) с пространством адресов 0-25 и функцию хеширования H(V)= mod(V,26). Массив T заполняется элементами T(H(Ki))=Ki и T(j)=0 если j (H(K1), H(K2),..,H(Kn)).

Поиск элемента V в массиве T с присваиванием Z его индекса если V содержится в T, или -1, если V не содержится в T, осуществляется следующим образом

        int t[26],v,z,i;
        i=(int)fmod((double)v,26.0);
        if(t[i]==v) z=i;
        else z=-1;

Добавление нового элемента V в список с возвращением в Z индекса элемента, где он будет храниться, реализуется фрагментом

        z=(int)fmod((doule)v,26.0);
        t[z]=v;

а исключение элемента V из списка присваиванием

        t[(int)fmod((double)v,26)]=0;

Теперь рассмотрим более сложный случай, когда условие Ki=Kj H(Ki)=H(Kj) не выполняется. Пусть V - множество возможных элементов списка (целые положительные числа), в котором максимальное число элементов равно 6. Возьмем M=8 и в качестве функции хеширования выберем функцию H(V)=Mod(V,8).

Предположим, что B=, причем H(K1)=5, H(K2)=3, H(K3)=6, H(K4)=3, H(K5)=1, т.е. H(K2)=H(K4) хотя K2=K4. Такая ситуация называется коллизией, и в этом случае при заполнении массива хеширования требуется метод для ее разрешения. Обычно выбирается первая свободная ячейка за собственным адресом. Для нашего случая массив T[8] может иметь вид

         T=<0,K5,0,K2,K4,K1,K3,0> .

При наличии коллизий усложняются все алгоритмы работы с массивом хеширования. Рассмотрим работу с массивом T[100], т.е. с пространством адресов от 0 до 99. Пусть количество элементов N не более 99, тогда в T всегда будет хотя бы один свободный элемент равный нулю. Для объявления массива используем оператор

            int static t[100];

Добавление в массив T нового элемента Z с занесением его адреса в I и числа элементов в N выполняется так:

        i=h(z);
        while (t[i]!=0 && t[i]!=z)
        if (i==99) i=0;
        else i++;
        if (t[i]!=z)  t[i]=z,  n++;

Поиск в массиве T элемента Z с присвоением I индекса Z, если Z имеется в T, или I=-1, если такого элемента нет, реализуется следующим образом:

        i=h(z);
        while (t[i]!=0 && t[i]!=z)
        if (i==99) i=0;
        else i++;
        if (t[i]==0) i=-1;

При наличии коллизий исключение элемента из списка путем пометки его как пустого, т.е. t[i]=0, может привести к ошибке. Например, если из списка B исключить элемент K2, то получим массив хеширования в виде T=<0,K5,0,0,K4,K1,K3,0>, в котором невозможно найти элемент K4, поскольку H(K4)=3, а T(3)=0. В таких случаях при исключении элемента из списка можно записывать в массив хеширования некоторое значение непринадлежащее области значений элементов списка и не равное нулю. При работе с таким массивом это значение будет указывать на то, что нужно просматривать со средние ячейки.

Достоинство методов вычисления адреса состоит в том, что они самые быстрые, а недостаток в том, что порядок элементов в массиве T не совпадает с их порядком в списке, кроме того довольно сложно осуществить динамическое расширение массива T.

2.3.5. Выбор в линейных списках

Задача выбора. Задан линейный список целых, различных по значению чисел B=, требуется найти элемент, имеющий i-тое наибольшее значение в порядке убывания элементов. При i=1 задача эквивалентна поиску максимального элемента, при i=2 поиску элемента с вторым наибольшим значением.

Поставленная задача может быть получена из задачи поиска j-того минимального значения заменой i=n-j+1 и поиском i-того максимального значения. Особый интерес представляет задача выбора при i=a/n, 0<a<1, в частности, задача выбора медианы при a=1/2.

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

Количество действий можно уменьшить применяя сортировку выбором только частично до i-того элемента. Это можно сделать, напри мер при помощи функции findi

       /*  выбор путем частичной сортировки  */
       int findi(int *s, int n, int i)
       {
          int c,j,k;
          for (k=0; k<=i; k++) for (j="k+1;" j<="n;" j++) if (s[k] < s[j]) { c="s[k];" s[k]="s[j];" s[j]="c;" } return s[i]; } 

Эта функция ищет элемент с индексом i, частично сортируя массив s, и выполняет при этом (n*i) сравнений. Отсюда следует, что функция findi приемлима для решения задачи при малом значении i, и малоэффективна при нахождении медианы.

Для решения задачи выбора i-того наибольшего значения в списке B модифицируем алгоритм быстрой сортировки. Список B разбиваем элементом K1 на подсписки B' и B", такие, что если Ki -B', то Ki>K1, и если Ki - B", то Ki<K1, и список B реорганизуется в список B',K1,B". Если K1 элемент располагается в списке на j-том месте и j=i, то искомый элемент найден. При j>i наибольшее значение ищется в списке B'; при j<i будем искать (i-j) значение в подсписке B".

Алгоритм выбора на базе быстрой сортировки в общем эффективен, но для улучшения алгоритма необходимо, чтобы разбиение списка на подсписки осуществлялось почти пополам. Следующий алгоритм эффективно решает задачу выбора i-того наибольшего элемента в списке B, деля его на подсписки примерно равной величины.

1. Если N<21, то выбрать i-тый наибольший элемент списка B обычной сортировкой.

2. Если N>21 разделим список на P=N/7 подсписков по 7 элементов в каждом, кроме последнего в котором mod(N,7) элементов.

3. Определим список W из медиан полученных подсписков (четвертых наибольших значений) и найдем в W его медиану M (рекурсивно при помощи данного алгоритма) т.е. (P/2+1)-й наибольший элемент.

4. С помощью элемента M разобьем список B на два подсписка B' с j элементами большими или равными M, и B" c N-j элементами меньшими M. При j>i повторим процедуру поиска сначала, но только в подсписке B'. При j=i искомый элемент найден, равен M и поиск прекращается. При j < i будем искать (i-j)-тый наибольший элемент в списке B".

     /*   алгоритм выбора делением списка почти пополам   */
     int search (int *b, int n, int i)
     {
      int findi(int  *, int, int);
      int t, m, j, p, s, *w;
      if (n<21) return findi(b, n, i); /* шаг 1 */ p="(int)(n/7);" w="calloc(p+1,sizeof(int));" /* шаги 2 и 3 */ for (t="0;" t < p; t++) w[t]="findi(b+7*t," 7, 3); if (n%7!="0)" { w[p]="findi(b+7*p,n%7,(n%7)/2);" p++; } m="search(w," p, p/2); free (w); for (j="0," t="0;" t < n; t++) /* шаг 4 */ if (b[t]>=m) j++;
        if (j>i)
        {
          for (p=0, t=0; p < n; t++)
          if (b[t]>=m)
          { b[p]=b[t]; p++; }
          m=search(b, j, i);             /*   поиск в B"    */
        }
        if (j < i)
        {
          for (p=0, t=0; t < n; t++)
            if (b[t] < m)     b[p++]=b[t];
            m=search(b, n-j, i-j);       /*   поиск в B"    */
        }
      return m;
     }

Рекурсивная функция search реализует алгоритм выбора i-того наибольшего значения. Для ее вызова можно использовать следующую программу

     #include 
     #include 
     main()
     {
       int search (int *b, int n, int i);
       int *b;
       int l, i, k, t;
       scanf("%d%d",&l,&i);
       printf
       ("\nВыбор %d максимального элемента из %d штук",i,l);
       b=(int *)(calloc(100,sizeof(int)));
       for (k=0; k<100; k++) b[k]="k;" /* заполнение массива */ for (k="1;" k < l/4; k++) { t="b[k];" /* перемешивание */ b[k]="b[l-k];" /* массива */ b[l-k]="t;" } k="search(b,l,i);" /* выбор элемента */ printf ("\n выбран элемент равный %d\n\n",k); return 0; } 

Используя метод математической индукции, можно доказать, что для функции search требуется выполнить в самом неблагоприятном случае 28*N сравнений.

Действительно, если N<21, то выполнение функции findi потребует сравнений порядка N*(N-1)/2, т.е. меньше чем 28*N. Предположим, что для любого T<N количество сравнений при выполнении функции search не более 28*T и подсчитаем, сколько сравнений потребуется функции search при произвольном значении N. Для поиска медианы в каждом из подсписков функцией findi требуется не более 7*(7-1)/2=21 сравнений, а для формирования массива W в целом не более 21*(N/7)=3*N сравнений. По предположению индукции для поиска медианы в массиве W длины N/7 требуется 28*(N/7)=4*N сравнений. После удаления из B части элементов с помощью медианы в B' (или в B") останется не более N*5/7 элементов, и для удаления ненужных элементов необходимо количество сравнений порядка N. Для поиска в оставшейся части массива (в B' или B") по предположению индукции требуется не более 28*(N*5/7)=20*N сравнений. Таким образом, всего потребуется 3*N+4*N+N+20*N=28*N сравнений, т.е. выдвинутое предположение доказано.