Информатика, 10 класс К. Ю. Поляков, Е. А. Еремин
 Скачать 0.95 Mb.
|
|
A[c]; при этом левая граница L перемещается в c. Поиск заканчивается при выполнении условия L = R-1, когда в рабочей зоне остался один элемент. Если при этом A[L]=X, тов результате найден элемент, равный X, иначе такого элемента нет. int X, L, R, c; L = 0 ; R = N; while ( L < R-1 ) { c = (L+R) / 2 ; if ( X < A[c] ) R = c; else L = c; } if ( A[L] == X ) printf ( "A[%d]=%d" , L, X ); else printf ( Не нашли ); Двоичный поиск работает значительно быстрее, чем линейный. В нашем примере (для массива из 8 элементов) удается решить задачу за 3 шага вместо 8 при линейном поиске. При увеличении размера массива эта разница становится впечатляющей. В таблице сравнивается количество шагов для двух методов при разных значениях N: Однако при этом нельзя сказать, что двоичный поиск лучше линейного. Нужно помнить, что данные необходимо предварительно отсортировать, а это может занять значительно больше времени, чем сам поиск. Поэтому такой подход эффективен, если данные меняются (и сортируются) редко, а поиск выполняется часто. Такая ситуация характерна, например, для баз данных. 1. Почему этот алгоритм поиска называется двоичным 2. Приведите примеры использования двоичного поискав обычной жизни. 3. Как можно примерно подсчитать количество шагов при двоичном поиске 4. Сравните достоинства и недостатки линейного и двоичного поиска. 1. Напишите программу, которая сортирует массив по убыванию и ищет в нем все значения, равные введенному числу. 2. Напишите программу, которая считает среднее число шагов при двоичном поиске для массива из 32 элементов в диапазоне 0..100. Для поиска используйте 1000 случайных чисел в этом же диапазоне 66. Символьные строки Что такое символьная строка Если в середине XX века первые компьютеры использовались, главным образом, для выполнения сложных математических расчётов, сейчас их основная работа – обработка текстовой символьной) информации. Символьная строка – это последовательность символов, расположенных в памяти рядом (в соседних ячейках. Для работы с символами во многих языках программирования есть перемен линейный поиск двоичный поиск 2 2 2 16 16 5 1024 1024 11 1048576 1048576 21 Задачи и задания ? Контрольные вопросы Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 48 22.10.2015 ные специального типа символы и символьные массивы. Казалось бы, массив символов – это и есть символьная строка, однако здесь есть некоторые особенности. Дело в том, что массив – это группа символов, каждый из которых независим от других. Это значит, что вводить символьный массив нужно посимвольно, в цикле. Более того, размер массива задается при объявлении, и не очень ясно, как использовать массивы для работы со строками переменной длины. Таким образом, нужно • работать с целой символьной строкой как с единым объектом • использовать строки переменной длины. В языках C и C++ работа с символьными строками происходит по-разному. Сначала мы рассмотрим язык C (заметим, что все эти возможности работают ив. В языке C строка объявляется как массив символов, то есть массив элементов типа char (от англ. character – символ char s[ 10 ]; Чем же отличается строка от массива Только тем, что внутри этого массива есть символ с кодом 0, который обозначается как '\0'. Этот невидимый символ (для него нет никакого изображения) обозначает окончание символьной строки. Ненужно путать его с символом '0' (цифрой 0), который имеет код 48. Таким образом, в символьный массив из 10 символов можно записать строку длиной 9 символов ещё один символ нужно оставить на признак окончания строки. Рассмотрим такой массив Символ '\0' в элементе массива s[7] говорит о том, что здесь заканчивается символьная строка, состоящая в данном случае из 7 символов. Для вывода строки на экран можно использовать функцию printf с форматом %s (от англ. string – строка printf ( "%s" , s ); Для массива, показанного выше, будет выведено Привет Символы с индексами 8 и 9 хранятся в памяти, ноне выводятся на экран, потому что при выводе в элементе s[7] встретился символ с кодом 0, означающий конец строки. Для вывода одной строки удобно использовать функцию puts: puts ( s ); Она выводит строку на экран с переходом на новую строку, то есть автоматически добавляет символ. Строку можно записать в массив при объявлении char s[ 10 ] = Привет Можно даже не указывать размер массива – в этом случае транслятор вычислит его автоматически Привет Размер этого массива будет равен 8 (7 символов строки + символ с кодом 0), записать в него строку длиннее 8 символов нельзя (в этом случае будет выход заграницы массива, который приведет к изменению ячеек памяти, не принадлежащих этому массиву. Вводить строку с клавиатуры тоже можно по формату %s: scanf ( "%s" , s ); Обратите внимание, что знак & перед именем строки не ставится (в отличие от ввода целых переменных, потому что имя строки в языке C воспринимается как адресе первого символа (символа с индексом 0). Если вводить таким образом строку, содержащую пробелы, вы увидите, что вводится только первое слово (символы до первого пробела, так работает функция scanf. Часто бывает нужно ввести строку с пробелами целиком, для этого удобно использовать функцию gets: gets ( s ); 0 1 2 3 4 5 6 7 8 9 s Привет Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 49 Длина строки (количество символов от начала строки до завершающего символа с кодом 0) определяется с помощью стандартной функции strlen (от англ. string length – длина строки. Вот так в целочисленную переменную n записывается длина строки s: n = strlen ( s ); Чтобы использовать эту функцию (и другие функции для работы с символьными строками, нужно подключить заголовочный файл string.h: #include s[ 4 ] = 'а Приведём полную программу, которая вводит строку с клавиатуры, заменяет в ней все буквы на буквы б и выводит полученную строку на экран. #include #include main() { char s[ 80 ]; int i; printf ( Введите строку" ); gets ( s ); for ( i = 0 ; i < strlen(s); i++ ) if ( s[i] == а ) s[i] = б puts ( s ); } Теперь покажем, как сделать тоже самое, используя возможности языка C++. Для работы с символьными строками в C++ введён специальный тип данных, который называется string: main() { string s; ... } Начальное значение строки можно задать прямо при объявлении string s = Привет Новое значение строки записывается с помощью оператора присваивания s = Привет Для того, чтобы ввести из входного потока строку с пробелами, применяется функция getline: getline ( cin, s ); а вывод выполняется стандартным образом cout << s; Для определения длины строки s используется запись s.size(). Это так называемая точечная нотация (подробнее мы познакомимся с ней в курсе 11 класса. Такая запись означает, что метод size применяется к объекту s типа string. В данном случае size – это функция (метод, связанная с типом данных string. Таким образом, программа которая заменяет в строке все буквы 'а' на буквы 'б' на языке C++ выглядит так #include using namespace std; main() { string s; int i; cout << Введите строку " ; getline ( cin, s ); Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 50 22.10.2015 for ( i = 0 ; i < s.size(); i++ ) if ( s[i] == а ) s[i] = б cout << s; } Операции со строками (язык C) Для выполнения стандартных операций со строками (копирования, сцепления удаления и строк, вставки символов применяют функции стандартной библиотеки языка C, которые подключаются с помощью заголовочного файла string.h. Для того, чтобы объединить две строки в одну, используется функция strcat (от англ. string concatenation – сцеплениестрок). Она дописывает вторую строку вконец первой char s[ 80 ]= Привет, Вася strcat ( s, ", " ); strcat ( s, s1 ); В результате в массиве s будет построена строка Привет, Вася. Первый вызов функции strcat добавит вконец строки s запятую и пробела второй – допишет ещё строку Вася, которая записана в массиве Функция strcpy (от англ. string copy – копировать строку) копирует строку из одного места в другое. Например, после выполнения фрагмента программы char s[ 80 ], Привет strcpy ( s1, Вася" ); strcpy ( s, s1 ); в обоих массивах будет записана строка Вася первый вызов функции strcpy запишет строку Вася в массива второй вызов – скопирует строку изв. Обратите внимание, что при вызове этой функции сначала указывают куда скопировать, а потом – что скопировать. Функция strcpy (как и другие функции для работы со строками) не проверяет, есть ли в массиве место для копирования строки. Если в приведённом примере размер массива s будет меньше, чем 5 символов, произойдет выход заграницы массива. Это опасная ошибка, в результате которой стираются данные за пределами массива. Функции strcpy на самом деле нужно передать два адреса в памяти – адрес строки- приёмника и адрес строки-источника данных. Как мы уже говорили, указав имя строки, мы сообщаем функции адрес начала этой строки, но это необязательно. В следующем примере адрес приёмника (куда будут скопированы данные) – это адрес символа s[7]: char s[ 80 ] = "Прошёл поезд strcpy ( &s[ 7 ] , пароход В результате в массиве s будет построена строка «Прошёл пароход. Вместо «&s[7]» можно использовать равносильную запись « s+7». Адрес источника данных (второй параметр) также необязательно совпадает с началом строки. Например char s[ 80 ] = "Прошёл поезд, s1[] = Привет, Вася strcpy ( s+ 7 , s1+ 8 ); В массиве s будет построена строка «Прошёл Вася. Функцию strcpy можно использовать для удаления символов из строки. Вот так удаляются 4 символа с s[2] по s[5]: char s[] = "0123456789" ; strcpy ( s+ 2 , s+ 6 ); Хвост строки, начиная с символа s[6], переносится ближе к началу, на место символа s[2]. В массиве s остаётся строка «016789». В библиотеке языка C есть еще одна функция для копирования строк, которая называется strncpy (в середине названия есть дополнительная буква n). Она отличается от strcpy тем, что • копирует не всю строку, а указанное количество символов (третий параметр функции, целое число • не добавляет вконец строки завершающий символ с кодом 0. Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 51 С помощью этой функции можно заменить часть строки char s[] = "Мухтар, ко мне, s1[] = Цезарь живет у нас дома strncpy ( s, s1, 6 ); В начало массива s будет скопировано 6 первых символов из массива s1, получится Цезарь, ко мне. Можно также использовать адреса символов в середине массивов char s[] = Вчера Мурзик вернулся, s1[]= Кота зовут Васька strncpy ( s+ 6 , s1+ 11 , 6 ); В массиве s получается строка Вчера Васька вернулся. В помощью функции strncpy несложно получить подстроку (часть строки) в другом массиве. Например, так можно скопировать в массив s1 четыре символа из строки s с номерами от 2 до 5: char s[] = "0123456789" , s1[ 20 ]; strncpy ( s1, s+ 2 , 4 ); s1[ 4 ] = '\0' ; Поскольку функция strncpy не добавляет вконец строки завершающий символ с кодом 0, его приходится ставить вручную. В массиве s1 будет записана строка «2345». К сожалению, в языке C непросто выполнить операцию вставки фрагмента в строку. Для этого нужно использовать вспомогательный массив (буфер. В этом фрагменте после имени Иван в строку s вставляется отчество Васильевич, так что получается строка Иван Васильевич меняет профессию char s[ 80 ] = Иван меняет профессию, s1[ 30 ]; strcpy ( s1, s+ 4 ); // s1 = " меняет профессию ( s+ 4 , " Васильевич" ); // s = "Иван Васильевич" strcat ( s, s1 ); // s = "Иван Васильевич меняет профессию" При первом вызове функции strcpy в буфер s1 копируется хвост строки. Затем к начальной части добавляется фрагмент-вставка, и потом вконец строки дописывается хвост из буфера. Операции со строками (язык C++) В языке C++ операции со строками выполняются значительно проще благодаря введённому типу string. Оператор '+' используется для объединения (сцепления) строк, эта операция иногда называется конкатенация. Например s1 = Привет s2 = Вася s = s1 + ", " + s2 + "!" ; Здесь и далее считаем, что в программе объявлены строки s, s1 и s2. В результате выполнения приведённой программы в строку s будет записано значение Привет, Вася. Для того, чтобы выделить часть строки (подстроку, англ. substring), применяется метод substr, который тоже вызывается с помощью точечной нотации. Этот метод принимает два параметра номер начального символа и количество символов Следующий фрагмент копирует в строку s1 пять символов строки s (с го пой В строку s1 будет записано значение «34567». Если второй параметр при вызове substr не указан, метод возвращает все символы до конца строки. Например, s = "0123456789" ; s1 = s.substr ( 3 ); вернёт « 3456789». Для удаления части строки нужно вызвать метод erase, указав номер начального символа и число удаляемых символов s = "0123456789" ; Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 52 22.10.2015 s.erase ( 3 , 6 ); В строке s остаётся значение «0129» (удаляются 6 символов, начиная с го. Обратите внимание, то процедура erase изменяет строку. При вставке символов методу insert передают вставляемый фрагмент и номер символа, с которого начинается вставка s = "0123456789" ; s.insert ( 3 , "ABC" ); Переменная s получит значение «012ABC3456789». Поиск в строках В библиотеке языка Сесть отдельные функции для поиска одного символа и подстроки в строке. Им нужно передать строку, в которой надо искать, и образец для поиска. Эти функции возвращают адрес в памяти, который можно записать в специальную пере- менную-указатель. Указатели в языке C объявляются с помощью знака *. Например, так объявляют указатель на символ, то есть переменную, в которой можно хранить адрес любого символа в памяти (вспомните, где мы раньше уже фактически использовали указатели char *p; В такую переменную можно записать результат функции strchr (от англ. string – строка и charac- ter – символ, которая ищет один символ в строке char s[] = Здесь был Вася char *p; p = strchr ( s, с ); Обратите внимание, что символ заключается в апострофы, а не в двойные кавычки. Если символ найден, его номер вычисляется как разность указателя p и адреса начала строки s. Если такого символа в строке нет, в переменную p будет записано специальное значение NULL (нулевой указатель Номер первого символа 'c': %d\n" , p-s ); else printf ( Символ не найден ); Если указанных символов несколько, функция strchr найдет первое вхождение символа в строку. Если нужно искать символ с конца строки, применяют функцию strrchr (добавляется буква r в середине, от англ. reverse – обратный. Поиск подстроки в строке выполняет функция strstr, которая работает аналогично char s[] = Здесь был Вася char *p; p = strstr ( s, Вася" ); if ( p != NULL ) printf ( Слово 'Вася' начинается с s[%d]\n" , p-s ); else printf ( Слово не найдено" ); В языке C++ для поиска символа и подстроки используется метод find. Эта функция возвращает номер найденного символа (номер первого символа подстроки) или –1, если найти нужный фрагмент не удалось. string s = Здесь был Вася int n; n = s.find ( с ); if ( n >= 0 ) cout << Номер первого символа 'c': " << n << endl; else cout << Символ не найден n = s.find ( Вася" ); if ( n >= 0 ) cout << Слово 'Вася' начинается с s[" << n << "]\n" ; else cout << Слово не найдено Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 53 Для поиска с конца строки используют метод rfind: n = s.rfind ( с ); if ( n >= 0 ) cout << Номер последнего символа 'c': " << n << endl; else cout << Символ не найден Пример обработки строк Предположим, что с клавиатуры вводится строка, содержащая имя, отчество и фамилию человека, например Василий Алибабаевич Хрюндиков Каждые два слова разделены одним пробелом, вначале строки пробелов нет. В результате обработки должна получиться новая строка, содержащая фамилию и инициалы Хрюндиков В.А. Возможный алгоритм решения этой задачи может быть на псевдокоде записан так ввести строку s найти в строке s первый пробел имя = всё, что слева от первого пробела удалить из строки s имя с пробелом найти в строке s первый пробел отчество = всё, что слева от первого пробела удалить из строки s отчество с пробелом // осталась фамилия = s + ' ' + имя + '.' + отчество + '.' Мы последовательно выделяем из строки три элемента имя, отчество и фамилию, используя тот факт, что они разделены одиночными пробелами. После того, как имя сохранено в отдельной переменной, в строке s остались только отчество и фамилия. После изъятия отчества остается только фамилия. Теперь нужно собрать строку-результат из частей сцепить фамилию и первые буквы имении отчества, поставив пробелы и точки между ними. Для выполнения всех операций будем использовать стандартные функции, описанные выше. Приведем полные программы на языке C: #include #include main() { char s[ 80 ], name[] = " ." , name2[] = " ." ; char *p; printf ( Введите имя, отчество и фамилию " ); gets ( s ); name[ 0 ] = s[ 0 ]; // первая буква имени p = strchr ( s, ' ' ); // найти пробел strcpy ( s, p+ 1 ); // стереть имя name2[ 0 ] = s[ 0 ]; // первая буква отчества p = strchr ( s, ' ' ); // найти пробел strcpy ( s, p+ 1 ); // осталась фамилия strcat ( s, " " ); // добавить пробел strcat ( s, name ); // прицепить имя strcat ( s, name2 ); // прицепить отчество puts ( s ); } и на С #include using namespace std; main() { string s, name, name2; int n; Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 54 22.10.2015 cout << Введите имя, отчество и фамилию " ; getline ( cin, s ); n = s.find( ' ' ); name = s.substr( 0 , 1 ) + '.' ; // первая буква имени s = s.substr ( n+ 1 ); n = s.find( ' ' ); name2 = s.substr( 0 , 1 ) + '.' ; // первая буква отчества s = s.substr ( n+ 1 ); // осталась фамилия s = s + ' ' + name + name2; cout << s; } Используя описания стандартных функций, самостоятельно разберитесь, как работают эти программы. Преобразования число ↔строка В практических задачах часто нужно преобразовать число, записанное в виде цепочки символов, в числовое значение, и наоборот. Для преобразования символьной строки в число в библиотеке языка Сесть функции atoi преобразование строки в целое число) и atof (преобразование строки в вещественное число. Для их использования нужно подключить заголовочный файл stdlib.h: #include s, в целое число char s[] = "123" ; int N; N = atoi ( s ); // N = 123 Если строку не удается преобразовать в целое число (например, если строка содержит нецифро- вой символ, работа функции останавливается на первом ошибочном символе. Например, при преобразовании строки х будет получено число 12. Аналогичная функция atof преобразует строку в вещественное число char s[] = "123.456" ; float X; X = atof ( s ); // X = Обратное преобразование (из числа в символьную строку) проще всего сделать с помощью функции sprintf, которая очень похожа на известную нам функцию printf, ноне выводит результат на экрана записывает его в символьную строку char s[ 80 ]; int N = 123 ; float X = 123.456 ; sprintf ( s, "%d" , N ); // s = "123" sprintf ( s, "%e" , X ); // s = "1.234560E+002" sprintf ( s, "%10.3f" , X ); // s = " Первый аргумент функции sprintf – это символьная строка, в которую нужно записать результат. При использовании формата %e вещественные числа представлены в научном формате ( "1.234560E+002" означает 2 10 23456 , 1 ⋅ ). В последней строке примера используется форматный вывод запись « %10.3f» означает вывести вещественное число с фиксированной точкой в 10 позициях с 3-мя знаками в дробной части. В языке C++ для преобразования строки (типа string) в число можно использовать те же функции atoi и atof: string s = "123" ; int N; double X; N = atoi ( s.c_str() ); // N = 123 X = atof ( s.c_str() ); // X = Поскольку исходная строка – это объект типа string, его сначала нужно преобразовать к типу данных, который принимают функции atoi и atof, то есть к символьной строке с нулевым за Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 55 22.10.2015 вершающим символом на конце. Это делает метод c_str, введённый для объектов типа string. В стандарте C++11 вместо atoi и atof можно использовать функции stoi и stof, которые не требуют такого преобразования и работают с объектами типа string. Для обратного преобразования (из числа в строку) в C++ используется та же идея, что ив перенаправить результат вывода не на экрана в символьную строку. Для этого в C++ нужно использовать строковые потоки вывода, которые подключаются с помощью заголовочного файла sstream: #include main { ostringstream ss; ... } Здесь ss – это объект типа ostringstream, выходной поток, направленный в строку. Итак, сначала выводим число в такой потока затем из этого потока преобразуем в строку (типа string) с помощью метода str: string s; int N = 123 ; double X = 123.456 ; ss << N; s = ss.str(); // s = "123" ss.str( "" ); // очистка потока // ширина поля // число знаков в дробной части << scientific << X; // вывести в научном формате = ss.str(); // s = "1.234560E+002" ss.str( "" ); // очистка потока // ширина поля // число знаков в дробной части << fixed << X; // вывести с фиксированной точкой = ss.str(); // s = " Строки в процедурах и функциях Строки можно передавать в процедуры и функции как аргументы. Построим процедуру, которая заменяет в строке s все вхождения слова-образца wOld на слово-замену wNew (здесь wOld и wNew – это имена переменных, а выражение слово wOld» означает слово, записанное в переменную. Сначала разработаем алгоритм решения задачи. В первую очередь в голову приходит такой псевдокод пока слово wOld есть в строке s { удалить слово wOld из строки вставить на это место слово wNew } Однако такой алгоритм работает неверно, если слово wOld входит в состав wNew, например, нужно заменить '12' на 'A12B' (покажите самостоятельно, что это приведет к зацикливанию. Чтобы избежать подобных проблем, попробуем накапливать результат в другой символьной строке res, удаляя из строки s уже обработанную часть. Предположим, что на некотором шаге в оставшейся части строки s обнаружено слово wOld риса Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 56 Теперь нужно выполнить следующие действия 1) ту часть строки s, которая стоит слева от образца, прицепить вконец строки res (рис. б 2) прицепить вконец строки res слово-замену wNew (рис. в 3) удалить из строки s начальную часть, включая найденное слово-образец (рис. г. Далее все эти операции (начиная с поиска слова wOld в строке s) повторяются до тех пор, пока строка s не станет пустой. Если очередное слово найти не удалось, вся оставшаяся строка s приписывается вконец строки-результата, и цикл заканчивается. Вначале работы алгоритмы в строку res записывается пустая строка, не содержащая ни одного символа. В таблице приведен протокол работы алгоритма замены для строки « 12.12.12», в которой нужно заменить слово «12» на «A12B»: рабочая строка s результат res "12.12.12" "" ".12.12" "A12B" ".12" "A12B.A12B" "" "A12B.A12B.A12B" Теперь можно написать процедуру на языке C. Она принимает три символьные строки, размер которых мы не указываем void replaceAll ( char s[], char wOld[], char wNew[] ) { int lenOld, lenNew; char *p, *pS, *pRes; char res[ 200 ]; lenOld = strlen(wOld); lenNew = strlen(wNew); res[ 0 ] = '\0' ; pS = s; pRes = res; while ( strlen(pS) > 0 ) { p = strstr ( pS, wOld ); if ( p == NULL ) { strcat ( res, s ); break ; } if ( p > pS ) { strncpy ( pRes, pS, p-pS ); pRes += p-pS; pS = p; } strcpy ( pRes, wNew ); pRes += lenNew; pS += lenOld; } strcpy ( s, res ); } wNew wOld res s s s s s res res res а) б) в) г) Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 57 Дадим некоторые пояснения. Ответ формируется в отдельной символьной строке res (это локальная переменная, ив конце процедуры копируется в строку s. В самом начале в первый по счёту символ массива res записывается символ с кодом 0 (строка res – пустая. Переменные lenOld и lenNew – это длины слова-образца и слова-замены соответственно. В процедуре используется также три указателя • p – указывает на очередное найденное слово-образец; • pS – указывает на рабочую точку внутри строки s, сначала устанавливается на начало этой строки • pRes – указывает на рабочую точку внутри строки-результата res; сначала устанавливается на начало этой строки. Указатель pS будет сдвигаться вдоль строки s, обозначая начало зоны поиска. Цикл заканчивается тогда, когда в рабочей части строки s не осталось ни одного символа, то есть вызов функции strlen(pS) вернёт 0: while ( strlen(pS) > 0 ) { ... } Кроме того, предусмотрен ещё один выход из цикла – если слово образец не найдено в оставшейся части строки, остаётся просто прицепить этот хвост к строке-результату выйти из цикла с помощью оператора break: p = strstr ( pS, wOld ); if ( p == NULL ) { strcat ( res, s ); break ; } Если поиск завершился удачно, проверяем, есть ли какие-то символы слева от образца. Если они есть, копируем их в строку-результат: if ( p > pS ) { strncpy ( pRes, pS, p-pS ); pRes += p-pS; pS = p; } Здесь p-pS – это количество символов в строке s слева от найденного образца до рабочей точки. Теперь остаётся прицепить строку-замену wNew к результату и передвинуть оба указателя strcpy ( pRes, wNew ); pRes += lenNew; pS += lenOld; После этого начинается новый шаг цикла. Приведем пример использования процедуры main() { char s[ 80 ] = "12.12.12" ; replaceAll ( s, "12" , "A12B" ); puts ( s ); } В результате должна быть выведена строка «A12B.A12B.A12B». Аналогичная процедура на языке С+ выглядит значительно проще благодаря более развитым средствам работы со строками void replaceAll ( string &s, string wOld, string wNew ) { string res = "" ; int p, len = wOld.size(); while ( s.size() > 0 ) Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 58 22.10.2015 { p = s.find ( wOld ); if ( p < 0 ) { res = res + s; break ; } if ( p > 0 ) res = res + s.substr ( 0 , p ); res = res + wNew; if ( p + len > s.size() ) s = "" ; else s.erase ( 0 , p + len ); } s = res; } Поскольку строка s изменяется, она передаётся по ссылке ив заголовке процедуры переде именем ставится знак &. Переменная len хранит длину строки-образца, в остальном алгоритм не изменяется. Построенную выше процедуру на языке C++ можно легко превратить в функцию. Для этого нужно • в заголовке функции указать, что она возвращает строку (использовать ключевое слово string вместо void); • убрать в заголовке процедуры символ & перед именем исходной строки (она не должна изменяться вернуть результат с помощью оператора return. Ниже показаны все изменённые части подпрограммы string replaceAll ( string s, string wOld, string wNew ) { ... return res; } Вызывать функцию можно таким образом main() { string s = "12.12.12" ; s = replaceAll ( s, "12" , "A12B" ); cout << s; cin.get(); } К сожалению, преобразовать процедуру на языке C в функцию не получится, потому что функции в этом языке не могут возвращать массив в качестве результата. Рекурсивный перебор В алфавите языка племени «тумба-юмба» четыре буквы Ы, Ш, Ч и О. Нужно вывести на экран все слова, состоящие из L букв, которые можно построить из букв этого алфавита. Это типичная задача на перебор вариантов, которую удобно свести к задаче меньшего размера. Будем определять буквы слова последовательно, одну за другой. Первая буква может быть любой из четырёх букв алфавита. Предположим, что сначала первой мы поставили букву Ы. Тогда для того, чтобы получить все варианты с первой буквой Ы, нужно перебрать всевозможные комбинации букв на оставшихся L-1 позициях Далее поочередно ставим на первое место все остальные буквы, повторяя процедуру Ы ? ? ? перебор символов Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 59 перебор L символов Ы перебор последних L-1 символов Ш перебор последних L-1 символов Ч перебор последних L-1 символов О перебор последних L-1 символов Здесь через w обозначена символьная строка, в которой хранится рабочее слово. Таким образом, задача для слов длины L свелась км задачам для слов длины L-1. Как вызнаете, такой прием называется рекурсией, а процедура – рекурсивной. Когда рекурсия должна закончиться Тогда, когда все символы расставлены, то есть количество установленных символов N равно L. При этом нужно вывести получившееся слово на экран и выйти из процедуры. Подсчитаем количество всех возможных слов длины L. Очевидно, что слов длины 1 всего 4. Добавляя ещё одну букву, получаем 4 ⋅4=16 комбинаций, для трех букв – 4⋅4⋅4=64 слова и т.д. Таким образом, слов из L букв может быть Сначала напишем программу на языке C. В основной программе построим слово (символьную строку) word нужной длины (что в ней будет записано, не имеет значения. Процедуре Tum- baWords передается алфавит в виде символьной строки, слово word и число уже установленных символов вначале "ЫШЧО" , word, 0 ); getchar(); } В процедуре используется описанный выше рекурсивный алгоритм void TumbaWords( char A[], char w[], int N ) { int i; if ( N == strlen(w) ) { puts ( w ); return ; } for ( i = 1 ; i < strlen(A); i ++ ) { w[N] = A[i]; TumbaWords ( A, w, N+1 ); } } Если условие вначале процедуры ложно (не все символы расставлены, в цикле перебираем все символы алфавита и поочередно ставим их на первое свободное место, а затем вызываем рекурсивно эту же процедуру, увеличивая третий аргумент на 1. Приведем аналогичную программу на C++: void TumbaWords( string A, string &w, int N ) { int i; if ( N == w.size() ) { cout << w << endl; return ; } for ( i = 1; i < A.size(); i ++ ) { w[N] = A[i]; TumbaWords ( A, w, N+1 ); } Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 60 22.10.2015 } main() { string word = "..." ; TumbaWords ( "ЫШЧО" , word, 0 ); cin.get(); } Обратите внимание, что параметр w (строка-результат) – это изменяемый параметр. Сравнение и сортировка строк Строки, как и числа, можно сравнивать. Для строк, состоящих из одних букв (русских или латинских, результат сравнения очевиден меньше будет та строка, которая идет раньше в алфавитном порядке. Например, слово паровоз будет меньше, чем слово пароход они отличаются в пятой букве ив х. Более короткое слово, которое совпадает с началом более длинного, тоже будет стоять раньше в алфавитном списке, поэтому пар < парк. Но откуда компьютер знает, что такое алфавитный порядок И как сравнивать слова, в которых есть и строчные и заглавные буквы, а также цифры и другие символы. Что больше, ПАР, Парили пар Оказывается, при сравнении строк используются коды символов. Тогда получается, что ПАР < Пар < пар. Возьмем пару ПАР и Пар. Первый символ в обоих словах одинакова второй отличается – в первом слове буква заглавная, а во втором – такая же, но строчная. В таблице символов заглавные буквы стоят раньше строчных, и поэтому имеют меньшие коды. Поэтому А < а, Паи ПАР < Пар < пар. А как же с другими символами (цифрами, латинскими буквами Цифры стоят в кодовой таблице по порядку, причём раньше, чем латинские буквы латинские буквы – раньше, чем русские заглавные буквы (русские и латинские) – раньше, чем соответствующие строчные. Поэтому «5STEAM» < «STEAM» < «Steam» < «steam» < ПАР < Пар < пар. Сравнение строк используется, например, при сортировке. Рассмотрим такую задачу ввести с клавиатуры 10 фамилий и вывести их на экран в алфавитном порядке. Для хранения данных удобно выделить массив строк. Поскольку в языке C строка хранится в массиве, то массив строк – это массив, составленный из массивов const int N = 10 ; char S[N][ 80 ]; Здесь S – это массив из N строк, в каждой строке может храниться до 79 символов (+ один символ с кодом 0, завершающий строку. Для сравнения строк в языке С используется функция strcmp (от англ. string comparison – сравнение строк. Она принимает два параметра (сравниваемые строки) и возвращает разность строк • 0, если они равны • положительное число, если первая строка больше второй (стоит после второй в алфавитном списке • отрицательное число, если первая строка меньше второй. Для обращения к строке с номером i используют, как обычно, форму S[i]. Вводи вывод массива строк выполняется в цикле с помощью функций gets и puts: main() { const int N = 10 ; char s1[ 80 ], S[N][ 80 ]; int i, j; printf ( Введите строки \n" ); 12 Значение, которое возвращает функция strcmp – это разность кодов первых различных символов двух строк или 0, если все символы совпали. Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 61 22.10.2015 for ( i = 0 ; i < N; i ++ ) gets ( S[i] ); for ( i = 0 ; i < N- 1 ; i ++ ) for ( j = N- 2 ; j >= i; j -- ) if ( strcmp(S[j],S[j+1]) > 0 ) { strcpy (s1, S[j]); strcpy (S[j], S[j+1]); strcpy (S[j+1], s1); } printf ( После сортировки \n" ); for ( i = 0 ; i < N; i ++ ) puts ( S[i] ); } Сортировка выполняется методом пузырька, а для перестановки двух строк из массива используется вспомогательная строка s1. В языке C++, где есть тип данных string, ситуация упрощается, и программа выглядит более понятной main() { const int N = 10 ; string s1, S[N]; int i, j; cout << Введите строки \n" ; for ( i = 0 ; i < N; i ++ ) getline ( cin, S[i] ); for ( i = 0 ; i < N- 1 ; i ++ ) for ( j = N- 2 ; j >= i; j -- ) if ( S[j] > S[j+1] ) { s1 = S[j]; S[j] = S[j+1]; S[j+1] = s1; } cout << После сортировки \n" ; for ( i = 0 ; i < N; i++ ) cout << S[i] << endl; } 1. Что такое символьная строка 2. Как хранятся строки в языках C и С 3. Как обращаться к элементу строки с заданным номером 4. Как вычисляется длина строки 5. Что обозначает оператор '+' применительно к строкам в C++? 6. Перечислите основные операции со строками и соответствующие им стандартные функции. 7. Как определить, что при поиске в строке образец не найден 8. Чем отличаются средства языков C и C++ для работы со строками Какой вариант вам больше нравится 9. Как преобразовать число из символьного видав числовой и обратно 10. Почему строку не всегда можно преобразовать в число 11. Объясните выражение рекурсивный перебор. 12. Сравните рекурсивные и нерекурсивные методы решения переборных задач. ? Контрольные вопросы Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 62 22.10.2015 1. Напишите программу, которая во введенной символьной строке заменяет все буквы а на буквы б и наоборот, как заглавные, таки строчные. При вводе строки « абсАБС» должен получиться результат « басБАС». 2. Ввести символьную строку и проверить, является ли она палиндромом (палиндром читается одинаково в обоих направлениях, например, казак. 3. Ввести адрес файла и разобрать его на части, разделенные знаком '/'. Каждую часть вывести в отдельной строке. 4. Ввести строку, в которой записана сумма натуральных чисел, например, « 1+25+3». Вычислите это выражение. 5. Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести фамилию и инициалы. Например, при вводе строки Иванов Петр Семёнович» должно получиться ПС. Иванов. 6. Разберитесь, как работает еще одна функция замены на языке С string replaceAll ( string s, string wOld, string wNew ) { int p, len = wOld.size(); p = s.find ( wOld ); while ( p >= 0 ) { s.erase( p, len ); s.insert ( p, len ); p = s.find ( wOld ); } return s; } Приведите пример входных данных, при которых эта функция работает неправильно. 7. Напишите рекурсивную версию процедуры replaceAll. Сравните две версии. Какую из них вы рекомендуете выбрать и почему 8. Напишите функцию, которая изменяет в имени файла расширение на заданное (например, на « .bak»). Функция принимает два параметра имя файла и нужно расширение. Учтите, что в исходном имени расширение может быть пустым. 9. Напишите функцию, которая определяет, сколько раз входит в символьную строку заданное слово. 10. С клавиатуры вводится число N, обозначающее количество футболистов команды Бублика затем – N строк, в каждой из которых – информация об одном футболисте таком формате Фамилия Имя год рождения голы Все данные разделяются одним пробелом. Нужно подсчитать, сколько футболистов, родившихся в период с 1998 по 2000 год, не забили мячей вообще. 11. В условиях предыдущей задачи определите фамилию и имя футболиста, забившего наибольшее число голов, и количество забитых им голов. 12. В условиях предыдущей задачи выведите в алфавитном порядке фамилии и имена всех футболистов, которые забили хотя бы один гол. В списке не более 100 футболистов. 13. Измените программу рекурсивного перебора так, чтобы длину слова можно было ввести с клавиатуры. 14. Выведите на экран все слова из L букв, в которых буква Ы встречается более 1 раза, и подсчитайте их количество. 15. Выведите на экран все слова из L букв, в которых есть одинаковые буквы, стоящие рядом например, «ЫШШО»), и подсчитайте их количество. 16. В языке племени «тумба-юмба» запрещено ставить две гласные буквы подряд. Выведите все слова длины L, удовлетворяющие этому условию, и найдите их количество. Задачи и задания Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 63 22.10.2015 17. Напишите программу перебора слов заданной длины, не использующую рекурсию. Попробуйте составить функцию, которая на основе некоторой комбинации вычисляет следующую за ней. 18. Перестановки. К вам пришли L гостей. Напишите программу, которая выводит все перестановки – способы посадить их за столом. Гостей можно обозначить латинскими буквами. |