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

Рассмотрим несколько подходов к хранению строки. Допустим, имеется строка “ad opus” (лат. «за дело»), состоящая и 7 символов, включая пробел.

В языке Pascal такая строка бы в памяти (тип string) хранилась следующим образом:

	строка (тип string) ЯП Pascal
байт	0	1	2	3	4	5	6	7	8	9					254	255
ASCII-код	7	97	100	32	111	112	117	115	мусор
символы		a	d		o	p	u	s

Такие строки называются строками фиксированной длины. Нулевой байт сохраняет используемую длину строки, в то время как в целом она занимает 256 байт памяти. У этой модели есть ряд преимуществ. Мы к ней вернёмся в теме «Длинная арифметика». Но есть и важные недостатки:

1.. Неэффективное использование памяти.

2.. Ограничение на длину строки.

В языке программирования C/C++ применяются нуль-терминированные строки. Они имеет не фиксированную длину, и завершаются символом с кодом 0 (обозначается '\0'– нуль-терминатор). Например,

	строка в C/C++
байт	0	1	2	3	4	5	6	7
ASCII-код	97	100	32	111	112	117	115	0
символы	a	d		o	p	u	s	\0

Такая строка занимает 8 байт[27] памяти

Реализация строк

Фактически, строка (далее string) — это массив типа char. Но есть несколько отличий:

string - это динамический массив символов, т.е. ему не надо задавать начальный размер:

char c[1000];   // создание массива char длиной в 1000

string s;       // создание string-a

В языке С строки описываются как указатель на char. Например,

#include <cstdio>

#include <cstring> //описание strlen

int main(){

char* str = "ABCD";

printf("%s %d", str, strlen(str));

}

Программа выведет на экран:

ABCD 4

В C++ строки реализованы как класс string, где каждый объект-строка имеет собственные методы.

Та же самая программа будет выглядеть так:

#include <iostream>

using namespace std;

int main(){

string str = "ABCD";

cout << str << " " << str.length();

}

ВАЖНО: Строки можно вводитьдо стоп-символа. По умолчанию ими являются пробел и символ конца строки. Это бывает удобно при решении ряда задач обработки текстов. Например, если требуется ввести фамилию, имя и отчество одной строкой:

string name, secondname, surname;

cin >> surname >> name >> secondname;

если ввести

Иванов Иван Иванович

то surname примет значение “Иванов”, name – “Иван”, secondname – “Иванович”. Программисту на Паскале в таком случае придётся вводить всё в одну строку, а затем самостоятельно разделять её на подстроки. В тех случаях, когда требуется считать строку из потока cin вместе с пробелами, можно использовать функцию getline:

getline(cin, s);

Если же строка реализуется через массив символов, её можно считать с пробелами с помощью функции gets.Выведем длину такой строки и саму строку:

char str[1000];

gets (str);

cout << strlen(str) << " " << str << "\n";

Задача №132.  Быки и коровы

Петя и Вася часто играют в различные логические игры. Недавно Петя поведал Васе о новой игре «Быки и коровы» и теперь они играют в эту игру сутками. Суть игры очень проста: Петя загадывает четырехзначное число, состоящее из различных цифр. Вася отгадывает задуманное Петей число, перебирая возможные варианты. Каждый раз Вася предлагает вариант своего числа, а Петя делает Васе подсказку: сообщает количество быков и коров, после чего Вася с учетом подсказки продолжает отгадывание числа до тех пор, пока не отгадает. Быки – это количество цифр в предложенном Васей числе, совпадающих по значению и стоящих в правильной позиции в задуманном Петей числе. Коровы – количество цифр, совпадающих по значению, но находящихся в неверной позиции. Например, если Петя задумал число 5671, а Вася предложил вариант 7251, то число быков равно 1 (только цифра 1 на своем месте), а число коров равно 2 (только цифры 7 и 5 не на своих местах). Петя силен в математике, но даже он может ошибаться. Помогите Пете написать программу, которая бы по загаданному Петей и предложенному Васей числам сообщала количество быков и коров.

Входные данные

В единственной строке записано два четырехзначных натуральных числа A и B через пробел, где А – загаданное Петей число, а В – предложенный Васей вариант.

Выходные данные

Вывести два целых числа через пробел — количество быков и коров.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	5671  7251	1  2
2	1234  1234	4  0
3	2034  6234	2  1

Решение

#include <iostream>

usingnamespace std;

int main() {

string a, b;

cin >> a >> b;

int cow = 0, bull = 0, i, j;

for(i = 0; i < 4; i++)

   for(j = 0; j < 4; j++){

       cow += (a[i]==b[j] && i!=j);

       bull += (a[i]==b[j] && j==i);

   }

cout << bull << ' ' << cow;

}

Задача №133.  Компьютерная игра

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

Вам дана последовательность побежденных врагов, в которой E обозначает обычного врага, а B - босса. Какой уровень вы получили, если изначально вы были на нулевом уровне?

Входные данные

Текстовая строка, состоящая из заглавных латинских букв Eи B.

Выходные данные

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

Пример

Ввод	Вывод
EEBEBBBB	6

Решение

#include <iostream>

using namespace std;

int main() {

string s;

cin >> s;

int len = s.length(), score = 0, level = 0;

for(int i = 0; i < len; i++){

   score += (s[i]=='E'? 1 : 2);

   if(score >= 2){

       score = 0;

       level++;

   }

}

cout << level;

}

Задача №134.  Клавиатура

Для данной буквы латинского алфавита нужно вывести справа стоящую букву на стандартной клавиатуре. При этом клавиатура замкнута, т.е. справа от буквы «p» стоит буква «a», от буквы «l» стоит буква «z», а от буквы «m» — буква «q».

Входные данные

Входной поток содержит один символ — маленькую букву латинского алфавита.

Выходные данные

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

Примеры

№	Ввод	Вывод
1	q	w
2	t	y
3	p	a
4	l	z
5	m	q

Решение

#include <iostream>

using namespace std;

int main() {

string key = "qwertyuiopasdfghjklzxcvbnmq";

char c;

cin >> c;

for(int i = 0, n = key.length() - 1; i < n; i++)

   if (c == key[i]) cout << key[i+1];

}

Строки сравниваются между собой в лексикографическом порядке, т.е по алфавиту. Например

ABB < BBAC, XYZ  > THEY, XYZ < ZZ и т.д. Это можно использовать в задачах, которые кажутся не связанными со строковым типом.

Задача №135.  Составить число из двух

Имеется два натуральных числа A и B. Записать их рядом, так чтобы получилось наибольшее число

Входные данные

Два числа, не превышающих 10⁹, записаны через пробел.

Выходные данные

Одно число, составленное из первых двух, записанных рядом

Пример

Ввод	Вывод
159 23	23159

Решение

#include <iostream>

using namespace std;

int main(){

string a, b;

cin >> a >> b;

cout << max(a,b) << min(a,b);

}

Задача №136.  Двойная бухгалтерия (Симферополь, 2015, II этап)

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

Входные данные

Одно целое неотрицательное число S ≤ 10⁹⁰ – сумма, которую должен был получать бухгалтер

Выходные данные

Одно число R – сумма, которую он в реальности получал.

Примеры

№	Ввод	Вывод
1	56701	76510
2	55000	55000
3	12000	21000

Решение

Решение задачи достаточно просто. Нужно вывести все цифры числа от больших к меньшим.

Очевидно, при ограничении 10⁹⁰ нельзя решать её через чтение стандартных целых из файла.

Первый способ предполагает после ввода символьной строки, отсортировать её по убыванию. Можно воспользоваться функцией быстрой сортировки sort, описанной в главе «Рекурсия» - «Быстрая сортировка».

#include <iostream>

#include <algorithm>

using namespace std;

string s;

int main() {

  cin >> s;

  sort(s.rbegin(), s.rend());

  cout << s;

}

Второй способ, более оптимальный по времени, заключается в идее подсчитать, сколько раз встречается та или иная цифра в числе, а затем вывести в обратном порядке по частоте.

#include <iostream>

using namespace std;

int main() {

int d[10] = {0,}, i;

string s;

cin >> s;

int l = s.length();

for(i = 0; i < l; i++)

   d[s[i]-'0']++;

for(i = 9; i >= 0; i--)

   for(int j = 1; j <= d[i]; j++)

       cout << i;

}

Такой способ упорядочения данных называется сортировка подсчетом. Рассмотрим более сложную версию этой же самой задачи.

Задача №137.  Годовой баланс (acmp.ru)

В конторе «Рога и Копыта» подходит время подведения годового баланса. В бухгалтерию поступили сведения о том, что, согласно документам, суммарный расход составил а рублей, a суммарный приход – b рублей. Поскольку с реальным положением дел эти цифры все равно не имеют ничего общего, бухгалтер решил реализовать следующую свою идею. Как известно, при наборе чисел на компьютере люди часто вводят цифры в неправильном порядке. Поэтому бухгалтер хочет найти такой способ переставить цифры в числах a и b, чтобы в результате разность a-b (и, соответственно, количество денег, которые он положит к себе в карман), была максимальна, а в случае можно будет сослаться на ошибку секретаря. При этом нельзя забывать о знаке чисел и о том, что ноль не может быть первой цифрой числа. Напишите программу, которая поможет бухгалтеру.

Входные данные

Два целых числа a и b (-10⁹< a,b < 10⁹).

Выходные данные

Выведите одно целое число – наибольшую разность чисел, первое из которых может быть получено перестановкой цифр a, а второе – перестановкой цифр b.

Примеры

№	Ввод	Вывод
1	18 10	71
2	1 -23	33

Решение

Используем для обработки введенных значений такую структуру данных, как «пара значений». Первый элемент – модуль числа в строковой форме, а второй булев – знак числа (trueдля отрицательных и false для положительных). Если учесть, что нам требуется найти сумму a+(-b) для первого числа знаком будет 0, а для второго – 1. При вводе отрицательных значений знак каждого числа будет меняться на противоположный.

#include <bits/stdc++.h>        // подключение станд. библиотек

#define VAL a[i].first

#define SGN a[i].second

using namespace std;

int i, j, x = 0;

pair<string, bool> a[2];

int main(){

for(i = 0; i < 2; i++){

   cin >> VAL;

   SGN = i;                // для a[0]-false, для a[1]-true

   if(VAL[0]=='-'){        // проверка отрицательных чисел

       VAL.erase(VAL.begin());

       SGN = !SGN;

   }

   if(SGN)                      // сортировка цифр числа

       sort(VAL.begin(), VAL.end());

   else sort(VAL.rbegin(), VAL.rend());  

   for(j = 0; VAL[j]=='0'; j++); // замена лидирующего нуля

       swap(VAL[j], VAL[0]); // ненулевой цифрой

   x += atoi(VAL.c_str())*(SGN ? -1 : 1);

}

cout << x;

}

Задача №138.  Палиндром

Назовём палиндромом строку, которую можно одинаково прочесть слева направо и справа налево с точностью до пробелов. Например, «казак», «шалаш», «Аргентина манит негра», «А роза упала на лапу Азора». Определите, является ли введённая строка палиндромом.

Входные данные

Строка латиницей, состоящая из символов ASCII

Выходные данные

Одно слово YES, если введённая строка палиндром и NOв противном случае.

Пример

Ввод	Вывод
mama	NO
kazak	YES
Argentina manit negra	YES

Решение

#include <iostream>

using namespace std;

int main(){

string s;

getline(cin, s);

while(s.find(' ') != string::npos)// удаляем все пробелы

   s.erase(s.find(' '), 1);

int len = s.length()-1;

char ch1, ch2;

bool palindrome = true;

for(int i = 0; i <= len/2; i++){

   ch1 = tolower(s[i]);    // преобразуем в нижний регистр

   ch2 = tolower(s[len-i]);     // преобразуем в нижний регистр

   if (ch1 != ch2) {palindrome = false; break;}

}

cout << (palindrome ? "YES" : "NO");

}

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

Задача №139.  Подстроки-палиндромы

Сколькими способами можно выбрать пару чисел L и R (L <= R) так, чтобы подстрока строки S с символа номер L по символ номер R была палиндромом?

Входные данные

Единственная строка S в нижнем регистре, не содержащая пробелов и других стоп-символов

Выходные данные

Одна строка с единственным числом – количеством способов выбрать Lи R

Пример

Ввод	Вывод
mama	6

Решение

#include<iostream>

using namespace std;

int main(){

string s;

cin >> s;

int l, r, cnt = 0, len = s.length();

bool palindrome;

for(l = 0; l < len; l++)

   for(r = l; r < len; r++){

       palindrome = true;

       for(int i = 0; i <= (r-l)/2; i++)

           if(s[l+i] != s[r-i]) {palindrome = false; break;}

       cnt += palindrome;

   }

cout << cnt;

}

Задача №140.  Телеграмма

Имеется текст телеграммы. Известно, что за каждое слово нужно заплатить 3 руб, а за знак препинания (для простоты определим, что их всего 3 – точка, запятая и восклицательный знак) по 1 руб. Определите общую стоимость телеграммы.

Входные данные

Текстовый файл input.txt содержит одну или более строк. Все слова в тексте разделяются пробелами (не обязательно одним) или символами перевода строки. Знаки препинания пишут слитно с предшествующим текстом.

Выходные данные

В текстовый файл output.txt вывести одно число – суммарную стоимость телеграммы

Пример[28]

Ввод	Вывод
Ars longa, vita brevis.	14

Решение

#include <fstream>

#define SPRICE 1                     // стоимость одного знака

#define WPRICE 3                     // стоимость одного слова

using namespace std;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

char sgn[] = {',', '.', '!'}; // однобайтный символьный тип

int price = 0, i, j;

string txt;

while(cin >> txt){          // читаем текст до конца файла

   for (i = 0; txt[i]; i++)     // проверяем все слова до конца

       for(j = 0; j < sizeof(sgn); j++)

           price += SPRICE * (txt[i] == sgn[j]);

   price += WPRICE;

}

cout << price;

}

Задача №141.  Скобки

Проверить корректность расстановки скобок в арифметическом выражении. Выражение задается из файла "input.txt" и может содержать произвольное количество круглых скобок. Программа должна выдать одну строчку: "правильно" или "неправильно".

Решение

Сначала разберемся, что считать правильной расстановкой скобок:

1. количество открытых скобок всегда больше либо равно количеству закрытых;

2. в конце выражения количество закрытых скобок равно количеству открытых.

В этой задаче возможно употребление, так называемого "конечного автомата", который изменяет свое состояние в зависимости от входных данных. Этот автомат должен иметь счетчик скобок, первоначально инициализированный нулем. Тогда:

1. при появлении символа "(" - увеличить счетчик на 1;

2. при появлении символа ")" - уменьшить счетчик на 1;

3. при появлении символа EOF - прекратить работу;

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

Посмотрим на счетчик: он содержит количество открытых, но еще не закрытых скобок. Если счетчик стал меньше нуля, значит, появилась лишняя закрывающая скобка, т.е. выражение неверно (нарушение пункта 1). Если после завершения работы конечного автомата счетчик не равен нулю (т.е. не все скобки закрыты) то выражение неверно (нарушение пункта 2).

#include <iostream>

using namespace std;

int main() {

string s;

cin >> s;

int p = 0;

for(int i = 0; s[i] && p >= 0; i++)

   p += (s[i] == '(' ? 1 : -1);

cout << (p ? "No" : "Yes");

return 0;

}

Задача №142.  Степень строки (acmp.ru)

Пусть задана строка s = s₁s₂...s_n. Назовем ее k-ой (k > 0) степенью s^k строку s^k = s₁s₂ . . .s_ns₁s₂ . . .s_n......s₁s₂...s_n (k раз). Например, третьей степенью строки abc является строка аbсаbсаbс.

Корнем k степени из строки s называется такая строка t (если она существует), что t^k = s.

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

Входные данные

Первая строка содержит строку s, она содержит только маленькие буквы латинского алфавита и имеет ненулевую длину, не превосходящую 1000.

Вторая строка входного файла содержит целое число k ≠ 0, |k| < 100001. Если k > 0, то необходимо найти k-ую степень строки s, если k < 0, то необходимо найти корень степени |k| из s.

Выходные данные

Выведите строку, являющуюся ответом на задачу. Если длина ответа превосходит 1023 символа, выведите только первые 1023 символа. Если искомой строки не существует — выведите NO SOLUTION.

Примеры

№	Ввод	Вывод
1	abc 3	abcabcabc
2	abcdabcd -2	abcd
3	abcd -4	NO SOLUTION

Решение

#include <iostream>

#define NO {cout << "NO SOLUTION"; return 0 ;}

using namespace std;

int main() {

string s;

int n, len, lenmax;

cin >> s >> n;

len = s.length();

if (n>0) {                  //возведение в степень

   lenmax = min(1023, n * len);

   for(int i = 0; i < lenmax; i++) cout << s[i % len];

   return 0;

}

n = -n;                     //нахождение корня

if (len % n) NO;            //длина строки не кратна n

n = len / n;

for (int i = n; i < len; i++) //есть несовпадающие символы

   if (s[i-n] != s[i]) NO;

lenmax = min(1023, n);

for (int i = 0; i < lenmax; i++) cout << s[i];

}