Задачи для самостоятельного решения. 1.5.2.1. Дан текст, состоящий из слов

1.5.2.1. Дан текст, состоящий из слов. Найти и напечатать наибольшую цепочку слов, в которой каждое следующее начинается на ту же букву, на которую кончается предыдущее слово.

Исходные данные:

Если блин нет то напечатать -1

Результат:

блин нет то

1.5.2.2. Дан текст, состоящий из слов. Найти и напечатать слово с наибольшим числом буквы А (прописных и строчных).

Исходные данные:

В тексте найти и напечатать самое длинное слово

Результат:

напечатать

1.5.2.3. Дан текст, состоящий из слов. Найти и напечатать слово с наибольшим числом различных букв и это количество.

Исходные данные:

В тексте найти и напечатать самое длинное слово

Результат:

напечатать 7

1.5.2.4. Дан текст, состоящий из слов. Напечатать все слова буквами наоборот.

Исходные данные:

Пример простого текста

Результат:

ремирП огтсорп атскет

1.5.2.5. Дан текст, состоящий из слов. Напечатать все слова в порядке от последнего к первому.

Исходные данные:

Пример простого текста

Результат:

текста простого пример

1.5.2.6. Дана символьная строка, содержащая некоторую формулу с тремя типами скобок – круглыми, квадратными и фигурными. Написать программу, которая напечатает «ОК», если скобки расставлены правильно, и «НЕТ» в противном случае.

Исходные данные:

([]{[]})

Результат:

OK

1.5.2.7. В тексте найти и напечатать все различные слова по одному в строке. Разделители между словами – только пробелы.

Исходные данные:

Пример простого текста, не содержащего в себе другого текста

Результат:

Пример

простого

текста,

не

содержащего

в

себе

другого

1.5.2.8. Дан текст, состоящий из слов. Напечатать слова в несколько строк шириной W, вставляя лишние пробелы между словами. Начало слова – первый символ в строке, конец слова – последний. Перед текстом в отдельной строке задаётся ширина W.

Исходные данные:

Результат:

1.5.2.9. В тексте встречаются числа. Напечатать самое большое.

Исходные данные:

Пример текста с 3 или 15 числами

Результат:

1.5.2.10. Даны два слова (текста) одинаковой длины. Если они состоят из одинакового набора символов, то напечатать «ДА», иначе – напечатать «НЕТ».

Исходные данные:

ABBA

BАВA

Результат:

ДА

1.5.2.11. Дано слово. Если из него можно получить палиндром, переставляя некоторые буквы, то напечатать один из них. Если нельзя, напечатать слово «НЕТ».

Исходные данные:

ABRACADABRA

Результат:

НЕТ

1.5.2.12. Даны два слова (текста). Найти и напечатать номер позиции, начиная с которой первое слово входит как часть во второе. Если нет, то напечатать -1. Нумерация с 0.

Исходные данные:

ABRACADABRA

BRA

Результат:

1.5.2.13. Даны два слова (текста). Найти и напечатать сколько раз первое слово входит как часть во второе.

Исходные данные:

ABRACADABRA

BRA

Результат:

1.5.2.14. Дан словарь правильных слов и текст. Напечатать все слова из текста, которые содержат более одной ошибки типа - неправильная буква, пропущена буква, лишняя буква. В первой строке задаётся количество слов в словаре n (n <= 1000). Далее следуют n строк, содержащих слова из словаря по одному в строке. Длина каждого слова не превосходит 20. Слова состоят только из строчных латинских букв. В последней строке задаётся текст длиной до 100000 символов из строчных латинских букв и знаков препинания.

Исходные данные:

the

word

this

is

world

thit is hte uorlt

Результат:

hte

uorlt

1.5.2.16. Дан словарь из нескольких слов и некоторый набор букв. Напечатать все слова из этого словаря, которые можно составить из заданного набора букв. В первой строке задаётся количество слов в словаре n (n <= 1000). Далее следуют n строк, содержащих слова из словаря по одному в строке. Длина каждого слова не превосходит 20. Слова состоят только из строчных латинских букв. В последней строке задаётся набор строчных латинских букв длиной до 26 символов.

Исходные данные:

the

word

this

is

world

ihostwr

Результат:

this

word

is

1.5.2.17. Дан текст из слов, разделенных пробелами. Удалить слово с указанным номером.

Исходные данные:

We are the world

Результат:

We are world

1.5.2.18. Дан текст из слов, разделенных пробелами, и ещё одно слово. Вставить новое слово после слова с указанным номером без использования дополнительных массивов.

Исходные данные:

We are world

the

Результат:

We are the world

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

Исходные данные:

We are the world

1 3

Результат:

the are We world

1.5.2.20. Анаграмма. Пусть задано некоторое слово, состоящее из букв английского алфавита длинной не более 80 символов (например, “WORD”). Рассмотрим набор возможных перестановок, состоящих из букв данного слова (например, “RDOW”, “WODR” и т.д.). Требуется выбрать из этого множества слово, следующее по алфавиту за исходным. В единственной строке записано слово, не последнее по алфавиту среди возможных его перестановок. Вывести следующее слово по алфавиту.

Исходные данные:

WORD

Результат:

WDRO

1.5.2.21. Степень строки. Пусть задана строка 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.

Исходные данные:

abcdabcd
-2

Результат:

abcd

Продвинутые задачки.

1.5.3.1. Дана символьная строка, состоящая из прописных латинских букв. Напечатать «ДА», если она является палиндромом, если игнорировать пробелы и не учитывать регистр букв.

Исходные данные:

Вона Бирганов а вона Грибанов

Результат:

ДА

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

Исходные данные:

())(

Результат:

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

Исходные данные:

HTEOLFEOLEH

Результат:

HELOLEH

1.5.3.4. Выкинуть из текста программы (много строк) примечания. На вход подаётся последовательность строк, некоторой синтаксически правильной программы на языке Си++.

Исходные данные:

int main () /* главная функция */

{

return 0; // it’s result

}

Результат:

int main ()

{

return 0;

}

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

Исходные данные:

Пример простого и короткого текста

2 4

Результат:

Пример короткого и простого текста

1.5.3.6. Абракадабра. Последовательность из латинских букв строится следующим образом. Вначале она пуста. На каждом последующем шаге последовательность удваивается, после чего к ней слева дописывается очередная буква латинского алфавита (a, b, c, …). Ниже приведены первые шаги построения по-следовательности:

Шаг 1. a

Шаг 2. baa

Шаг 3. cbaabaa

Шаг 4. dcbaabaacbaabaa

…………………………

Написать программу, которая по заданному числу N находит символ, который стоит на N-ом месте в последовательности, получившейся после 26-го шага. В единственной строке записано число N (1 <= N < 2²⁶). Вывести символ, стоящий в N-й позиции получившейся последовательности.

Исходные данные:

Результат:

w

1.5.3.7. Охрана. На секретной военной базе работает N охранников. Сутки поделены на 10000 равных промежутков времени, и известно когда каждый из охранников приходит на дежурство и уходит с него. Например, если охранник приходит в 5, а уходит в 8, то значит, что он был в 6, 7 и 8-ой промежуток. В связи с уменьшением финансирования часть охранников решено было сократить. Укажите: верно ли то, что для данного набора охранников, объект охраняется в любой момент времени хотя бы одним охранником и удаление любого из них приводит к появлению промежутка времени, когда объект не охраняется. В первой строке записано натуральное число K (1 ≤ K ≤ 100) – количество тестов в файле. Каждый тест начинается с числа N (1 ≤ N ≤ 10000), за которым следует N пар неотрицательных целых чисел A и B - время прихода на дежурство и ухода (0 ≤ A < B ≤ 10000) соответствующего охранника. Все числа во входном файле разделены пробелами и/или переводами строки. Вывести K строк, где в M-ой строке находится слово Accepted, если M-ый набор охранников удовлетворяет описанным выше условиям. В противном случае выведите Wrong Answer.

Исходные данные:

2
3 0 3000 2500 7000 2700 10000
2 0 3000 2700 10000

Результат:

Wrong Answer
Accepted

1.5.3.8. Строки. Циклическим сдвигом строки s называется строка s_ks_k+1s_k+2…s_|s|s₁s₂…s_k-1 для некоторого k, здесь |s| - длина строки s. Подстрокой строки s называется строка s_is_i+1…s_j-1s_j для некоторых i и j. Вам даны две строки a и b. Выведите количество подстрок строки a, являющихся циклическими сдвигами строки b. Первая строка содержит строку a (1 ≤ |a| ≤ 1000). Во второй строке записана строка b (1 ≤ |b| ≤ min(100,|a|)). Обе строки состоят только из символов латинского алфавита и цифр.

Исходные данные:

aAaa8aaAa
aAa

Результат:

Тема 1.6. Матрицы

Цель.

Изучение алгоритмов обработки многомерных массивов или их фрагментов.

Основные понятия.

Описание и выделение памяти для автоматических и динамических матриц

Работа с элементами

Ключевые слова.

Матрица, многомерный массив, строка, столбец, определитель

ПРИМЕР.

Дана квадратная матрица целых чисел порядка n. Транспонировать её относительно главной диагонали и напечатать. Другие массивы не использовать. Значения элементов не превосходят 10⁵.

Алгоритм.

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

Решение.

// C++

# include <iostream>

# include <iomanip>

# include <cstdlib>

using namespace std;

const int N = 100; // заранее заведём большую матрицу

int a [N][N];

int main ()

{

setlocale (LC_ALL, "RUS");

cout << "Транспонирование матрицы" << endl;

cout << "Введите размер матрицы, потом саму матрицу" << endl;

int n;

cin >> n;

for ( int i=0; i < n; i++ )

for ( int j=0; j < n; j++ )

cin >> a [i][j];

for ( int i=1; i < n; i++ )

for ( int j=0; j < i; j++ )

swap (a [i][j], a [j][i]);

for ( int i=0; i < n; i++ )

{

for ( int j=0; j < n; j++ )

cout << setw (5) << a [i][j] << " ";

cout << endl;

}

system ("PAUSE");

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine ("Транспонирование матрицы");

Console.WriteLine ("Введите размер матрицы, потом саму матрицу");

int n = int.Parse (Console.ReadLine ());

int [,] a = new int [n, n];

for ( int i=0; i < n; i++ )

{

string ss = Console.ReadLine ();

string [] s = ss.Split (' ');

for ( int j=0; j < n; j++ )

a [i, j] = int.Parse (s [j]);

}

for ( int i=1; i < n; i++ )

for ( int j=0; j < i; j++ )

{

int temp = a [i, j];

a [i, j] = a [j, i];

a [j, i] = temp;

}

for ( int i=0; i < n; i++ )

{

for ( int j=0; j < n; j++ )

Console.Write (a [i, j] + " ");

Console.WriteLine ();

}

Console.ReadKey ();

}

}