Глава_03

Назад | Начало урока | Вперед
Содержание

Глава 3

Поиск в строках find(), find_first_of()
Решето Эратосфена find(), find_first_of()

Поиск в строках

Функции группы find класса string предназначены для поиска символа или группы символов в заданной строке. Ниже перечислены функции группы find и область их применения.

find()
Ищет в строке символ или группу символов. Возвращает начальную позицию первого найденного экземпляра или npos при отсутствии совпадений.

find_first_of()
Ищет в строке и возвращает позицию первого символа, совпадающего с любым символом из заданной группы. При отсутствии совпадений возвращает npos.

find_last_of()
Ищет в строке и возвращает позицию последнего символа, совпадающего с любым символом из заданной группы. При отсутствии совпадений возвращает npos.

find_first_not_of()
Ищет в строке и возвращает позицию первого элемента, не совпадающего ни с одним из символов заданной группы. При отсутствии совпадений возвращает npos.

find_last_not_of()
Ищет в строке и возвращает позицию последнего элемента, не совпадающего ни с одним из символов заданной группы. При отсутствии совпадений возвращает npos.

rfind()
Просматривает строку от конца к началу в поисках заданного символа или группы символов и возвращает начальную позицию совпадения. При отсутствии совпадений возвращает npos.

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

Следующая программа использует решето Эрастофена для поиска простых чисел, меньших 50. Этот алгоритм начинается с числа 2, помечает все числа, кратные 2, как непростые и повторяет процесс для следующего кандидата в простые числа. Конструктор SieveTest инициализирует массив sieveChars, для чего он задает исходный размер символьного массива и записывает значение 'P' в каждый из его элементов.

Вверх


//: C03:Sieve.h

#ifndef SIEVE_H

#define SIEVE_H

#include <cmath>

#include <cstddef>

#include <string>

#include "../TestSuite/Test.h"

using std::size_t;

using std::sqrt;

using std::string;

class SieveTest : public TestSuite::Test {

  string sieveChars;

public:

  // Создание строки длиной 50 и заполнение ее символов

  // значениями 'P' (сокращение от Prime, то есть "простое число")

  SieveTest() : sieveChars(50, 'P') {}

  void run() {
    findPrimes();

    testPrimes();
  
}


  bool 
isPrime

(int p) {
    if (p == 0 || p == 1) return false;

    int root = int(sqrt(double(p)));

    for (int i = 2; i <= root; ++i)

      if (p % i == 0) return false;

    return true;

  
}


  void 
findPrimes

() {
    // По определению числа 0 и 1 не являются простыми.

    // Заменяем эти элементы символами "N".

    sieveChars.replace(0, 2, "NN");
    // Перебор массива:

    size_t sieveSize = sieveChars.size();

    int root = int(sqrt(double(sieveSize)));

    for (int i = 2; i <= root; ++i)

      // Поиск всех кратных чисел:

      for (size_t factor = 2; factor * i < sieveSize;++factor)

        sieveChars[factor * i] = 'N';


  
}


  void 
testPrimes

() {
    size_t i = sieveChars.find('P');

    while (i != string::npos) {
      test_(isPrime(i++));

      i = sieveChars.find('P', i);

    }


    i = sieveChars.find_first_not_of('P');

    while (i != string::npos) {
      test_(!isPrime(i++));

      i = sieveChars.find_first_not_of('P', i);

    }

  }

};

#endif // SIEVE_H ///:~


//: C03:Sieve.cpp

//{L} ../TestSuite/Test

#include "../TestSuite/Test.h"

#include "Sieve.h"

int main() {

  SieveTest t;

  t.run();

  return t.report();

} ///:~

Результат:

Анализ:

Функция find() перебирает содержимое string в прямом направлении; с ее помощью можно найти все вхождения символа или группы символов.
Функция find_first_not_of() ищет символы или подстроки, не соответствующие заданному критерию.

Вверх

Решето Эратосфена

Программа выводит ряд простых чисел в интервале от 0 до 50.
За основу взята программа Sieve.cpp на тему "Поиск в строках"
глава 3 из книги "Thinking in C++" -Автор Брюс Эккель.

Интересная программа, я бы даже сказал забавная!
Оригинальное решение и оригинальная демонстрация
применения find() и find_first_not_of().
И применения алгоритма "просеивания" простых чисел - "Решето Эратосфена".


//: C03:Sieve.h

#ifndef SIEVE_H

#define SIEVE_H

#include <cmath>

#include <string>

#include <iostream>

using namespace std;


class SieveTest {

  string sieveChars;

public:

  // Создание строки длиной 50 и заполнение ее символов

  // значениями 'P' (сокращение от Prime, то есть "простое число")

  SieveTest() : sieveChars(50, 'P') {}
  void 

run()

 {

    findPrimes();

    testPrimes();
  }

  bool 

isPrime

(int p) {

    if (p == 0 || p == 1) return false;

    int root = int(sqrt(double(p)));

    for (int i = 2; i <= root; ++i)

      if (p % i == 0) 

return false;


    return true;

  }


 void 
findPrimes

() {

    // По определению числа 0 и 1 не являются простыми.

    // Заменяем эти элементы символами "N".

    sieveChars.replace(0, 2, "NN");

	cout << sieveChars  << endl;

	

	// Перебор массива:

    size_t sieveSize = sieveChars.size();

    int root = int(sqrt(double(sieveSize)));

	for (int i = 2; i <= root; ++i){

      // Поиск всех кратных чисел:

      // В позицию строки, соответствующую кратному числу

      // вставим символ 'N'

      for (size_t factor = 2; factor * i < sieveSize; ++factor){
        sieveChars[factor * i] = 'N';
	  }

	}

	cout << sieveChars  << endl;
  }

  void 

testPrimes

()
 {

    size_t i = sieveChars.find('P');

    while (i != string::npos) {
      i = sieveChars.find('P', i);

    	cout << i <<  endl;

		i++;

		i++;

		if(i >= 48) break; 
    }

		cout <<  " OK !" << endl;

    i = sieveChars.find_first_not_of('P');

    while (i != string::npos) {

      i = sieveChars.find_first_not_of('P', i);

    	cout << i <<  endl;

		i++;

		i++;

		if(i >= 48) break; 
	}

  }

};

#endif // SIEVE_H ///:~


//: C03:Sieve.cpp

#include "Sieve.h"

int main() {

  SieveTest t;

  t.run();

   char StopCharacter;

       cout << endl << "Press a key and \"Enter\" : ";

       cin >> StopCharacter;  

  return 0;


} ///:~

Результат:

NNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
NNPPNPNPNNNPNPNNNPNPNNNPNNNNNPNPNNNNNPNNNPNPNNNPNN
2
5
7
11
13
17
19
23
29
31
37
41
43
47
OK !

Анализ:

В следующей строке все символы 'P' находятся на позициях,
на которых находятся в последовательности натуральных чисел простые числа.

NNPPNPNPNNNPNPNNNPNPNNNPNNNNNPNPNNNNNPNNNPNPNNNPNN

Теперь ничего не стоит вывести и сами числа.

А решето Эратосфена действует замечательно! Оно пометило все простые числа символом 'P'.
Точнее говоря пометило все непростые числа символом 'N'.
И сделала это функция findPrimes().

Для начала в программе создадим строку в 50 символов и заполним ее символами 'P'.
Для этого в программе сначала сделано объявление строки, а затем ее инициализация символами 'P'. Причем инициализация строки сделана в конструкторе класса SieveTest:

class SieveTest {


  string sieveChars;

public:

  // Создание строки длиной 50 и заполнение ее символов

  // значениями 'P' (сокращение от Prime, то есть "простое число")

  SieveTest() : sieveChars(50, 'P') {}

...

Надо сказать, что объявление а затем инициализация строки символами в конструкторе класса - весьма любопытна.
Благодаря такой инициализации можно обращаться со строкой как как с массивом символов. Что далее мы и увидим.

void findPrimes () {


    // По определению числа 0 и 1 не являются простыми.

    // Заменяем эти элементы символами "N".

    sieveChars.replace(0, 2, "NN");

	cout << sieveChars  << endl;

	

	// Перебор массива:

    size_t sieveSize = sieveChars.size();

    int root = int(sqrt(double(sieveSize)));

	for (int i = 2; i <= root; ++i){

      // Поиск всех кратных чисел:

      // В позицию строки, соответствующую кратному числу

      // вставим символ 'N'

      for (size_t factor = 2; factor * i < sieveSize; ++factor){
        sieveChars[factor * i] = 'N';
	  }

	}

	cout << sieveChars  << endl;

Эта функция в двойном цикле определила все значения позиций, которые соответствуют непростым числам. Во все эти позиции функция поместила символ 'N'. В остальных позициях строки остался символ 'P'. То есть символ 'P' остался только в тех позициях, значение которых соответствует простым числам в интервале от 0 до 50.

Вот что сделала эта функция! Это и есть работа алгоритма, называемого Решето Эратосфена.

Эта функция преобразовала строку, состоящую из одних только символов 'P',
в строку в которой все символы 'P' находятся на позициях, на которых находятся в
последовательности натуральных чисел простые числа.

Меня удивила следующая инструкция:

sieveChars[factor * i] = 'N';

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

Просто я упустил из виду, что в конструкторе класса SieveTest создается и инициализируется
массив символов на 50 элементов:

SieveTest() : sieveChars(50, 'P') {}

Далее этот массив символов будет использоваться.

Итак строка сформирована. В ней в позиции простых чисел находятся символы 'P'

В следующей функции testPrimes () при помощи find() будем находить позиции, в которых находятся символы 'P'. Значения этих позиций будут совпадать со значениями простых чисел. Таким образом мы имеем возможность вывести простые числа в интервале от 0 до 50 !

void testPrimes () {


    size_t i = sieveChars.find('P');

    while (i != string::npos) {
      i = sieveChars.find('P', i);

    	cout << i <<  endl;

		i++;

		i++;

		if(i >= 48) break; 
    }

		cout <<  " OK !" << endl;

};

Функция выводит следующую последовательность простых чисел:
2
5
7
11
13
17
19
23
29
31
37
41
43
47
OK !

Интересная программа! Оригинальное решение и оригинальная демонстрация
применения find(). И применения алгоритма "Решето Эратосфена".

Для того, чтобы вывести все непростые числа в том же интервале,
достаточно в функции testPrimes() добавить тот же код, который уже был написан, но в нем заменить find() на find_first_not_of():

void testPrimes () {


    size_t i = sieveChars.find('P');

    while (i != string::npos) {
      i = sieveChars.find('P', i);

    	cout << i <<  endl;

		i++;

		i++;

		if(i >= 48) break; 
    }

		cout <<  " OK !" << endl;

    i = sieveChars.find_first_not_of('P');

    while (i != string::npos) {

      i = sieveChars.find_first_not_of('P', i);

    	cout << i <<  endl;

		i++;

		i++;

		if(i >= 48) break; 
	}

}

};

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

while (i != string::npos)

Поэтому в конце каждого цикла мне пришлось добавить инструкцию:

if(i >= 48) break;

Результат:

NNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
NNPPNPNPNNNPNPNNNPNPNNNPNNNNNPNPNNNNNPNNNPNPNNNPNN
2
5
7
11
13
17
19
23
29
31
37
41
43
47
OK !
0
4
6
8
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46

Назад | Начало урока | Вверх | Вперед
Содержание