Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex] m > 0[/latex] (количество строк).
|
1 2 3 4 5 |
0 10 1110 3110 132110 1113122110 311311222110 13211321322110 1113 122113121113222110 3113112221131 1123113322110 132113213221133112 132123223110 1113122113121113222 |
Входные данные
Количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]) в таблице.
Выходные данные
Построенная для данной последовательности таблица с соответствующим количеством столбцов и строк.
Тесты
| [latex]n[/latex] | [latex]m[/latex] | Результат работы программы | ||
| 1 | 1 | 0 | ||
| 2 | 2 |
|
||
| 1 | 6 |
|
||
| 4 | 4 |
|
||
| 5 | 5 |
|
||
| 32 | 5 |
|
||
| 50 | 10 |
|
||
| 10 | 10 |
|
Алгоритм
Для начала определим алгоритм построения предоставленной последовательности. Перед нами так называемая Look-and-Say sequence, начинающаяся с 0. Чтобы получить последующий член последовательности, нам потребуется обратиться к предыдущему и выполнить следующее:
- Посчитать количество одинаковых подряд идущих цифр и записать его.
- Записать саму эту цифру.
Разберем на примере:
- Первый член последовательности — [latex]0[/latex] («Основание» последовательности);
- Второй член последовательности — [latex]10[/latex] («Вижу» один ноль);
- Третий член последовательности — [latex]1110[/latex] («Вижу» одну единицу и один ноль);
- Четвертый член последовательности — [latex]3110[/latex] («Вижу» три единицы и один ноль).
- …
Реализуем данное построение на практике. Создадим два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (изначально start [latex] = 0[/latex]) и счетчик количества совпадающих элементов (изначально quantity [latex] = 0[/latex]). Запустим цикл от первого до последнего элемента массива previousTerm и выполним ряд действий, а именно:
- Пока последующие элементы совпадают с текущим сравниваемым, инкрементируем счетчик.
- Как только находиться элемент не совпадающий с текущим сравниваемым, выполняем вывод количества вхождений и само число, также записываем данные значения в вектор currentTerm. Переходим к следующей цифре для сравнения и присваиваем счетчику значение [latex]1[/latex].
- Отдельно выполняем предыдущий пункт для последней последовательности цифр или одной цифры, так как нет возможности сравнения с последующими.
- Как только один член последовательности полностью построен, обнуляем значения индекса сравниваемой цифры и счетчика. Также очищаем вектотр previousTerm и передаем ему значения вектора currentTerm, очищаем вектор currentTerm.
Теперь наша задача состоит в том, чтобы выполнить правильный вывод таблицы. Основную работу по построению таблицы будет выполнять метод ToPrint, принимающий как параметры заданное количество столбцов, строк, номер текущего столбца, текущей строки и цифру которую нужно вывести на печать (или пробел).
Рассмотрим детали его работы:
- При запуске метода сразу же увеличиваем текущий номер столбца, в который записывается символ, на [latex]1[/latex].
- Далее проверяем не превышает ли номер текущего столбца возможный. Если это так, то выполняем перевод курсора на новую строку, присваиваем текущему столбцу значение [latex]1[/latex] и инкрементируем значение номера текущей строки.
- Если количество строк превышает заданное, заканчиваем работу программы.
- В противном же случае выполняем печать символа, если это не пробел в начале строки (если это все же пробел в начале строки, то ничего не печатаем и уменьшаем значение текущего столбца для печати). Для упрощения вывода пробел передается в метод по его коду в таблице ASCII — [latex]32[/latex]. Мы имеем полное право использовать число [latex]32[/latex] без угрозы ошибки, так как передавать мы будем только цифры [latex]0, 1, 2, 3[/latex].
Таким образом общий алгоритм работы программы можем сформулировать так:
- Считываем заданное количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]).
- Для последующей работы объявляем переменные хранящие значения номера текущего столбца и строки (currentNumberColumn и currentNumberRow соответственно), два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (start) и счетчик количества совпадающих элементов (quantity) .
- Отправляем в вектор previousTerm значение «основания» последовательности — [latex]0[/latex].
- Выводим первый член последовательности и пробел после него (если потребуется).
- Далее запускаем бесконечный цикл, так как окончание работы программы предусмотрено в методе ToPrint.
- И выполняем последовательное построение членов последовательности (описано выше) и тут же вывод, пока количество строк не превышает заданное.
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <vector> using namespace std; void ToPrint(int n, int m, int *currentNumberColumn, int *currentNumberRow, int symbolToPrint) { (*currentNumberColumn)++; // Инкрементируем значение номера столбца, так как есть символ на печать if (*currentNumberColumn > n) { cout << endl; // Переходим на новую строку (*currentNumberRow)++; *currentNumberColumn = 1; } // Если следует выполнить переход на следующую строку, выполняем этот переход по всем индексам if (*currentNumberRow > m) exit(0); // Заканчиваем работу программы, как только количество строк превышает заданное else if (symbolToPrint == 32 && *currentNumberColumn == 1) // В таблице ASCII 32 - пробел (*currentNumberColumn)--; // Возвращаем предыдущее значение номера столбца, так как ничего не было напечатано else if (symbolToPrint == 32) cout << char(symbolToPrint); // Выводим пробел, если это не начало строки else cout << symbolToPrint; } int main() { int n, m; // Количество столбцов и строк соответственно cin >> n >> m; int start = 0; // Индекс элемента текущей цифры с которой ведется сравнение int quantity = 0; // Количество идущих подряд одинаковых элементов в данном члене int currentNumberRow = 1; // Номер текущей строки, в которой будет записан символ int currentNumberColumn = 0; // Номер текущего столбца, в который будет записан символ vector <short> currentTerm; // Вектор, хранящий значение текущего члена последовательности vector <short> previousTerm; // Вектор, хранящий значение предыдущего члена последовательности previousTerm.push_back(0); // Записываем в вектор предыдущего члена значение первого члена последовательности ToPrint(n, m, ¤tNumberColumn, ¤tNumberRow, 0); // Выводим первый член последовательности ToPrint(n, m, ¤tNumberColumn, ¤tNumberRow, 32); // Выводим пробел после него (если он не понадобится его уберет метод ToPrint) while (true) { for (int i = 0; i < previousTerm.size(); i++) { if (previousTerm[i] == previousTerm[start]) quantity++; // Считаем количество идущих подряд одинаковых цифр else { currentTerm.push_back(quantity); // Записываем в вектор количество текущих цифр currentTerm.push_back(previousTerm[start]); // Записываем саму цифру ToPrint(n, m, ¤tNumberColumn, ¤tNumberRow, quantity); ToPrint(n, m, ¤tNumberColumn, ¤tNumberRow, previousTerm[start]); // Печатаем полученные данные start += quantity; // Переходим к следующей цифре для сравнения quantity = 1; // Присваиваем количеству одинаковых идущих подряд цифр 1, так как мы перешли к следующей цифре } // Если значение текущей цифры не совпадает с предыдущим, выполняем вывод и заполнение вектора следующего члена if (i == (previousTerm.size() - 1)) { currentTerm.push_back(quantity); currentTerm.push_back(previousTerm[start]); ToPrint(n, m, ¤tNumberColumn, ¤tNumberRow, quantity); ToPrint(n, m, ¤tNumberColumn, ¤tNumberRow, previousTerm[start]); } // Отдельный вывод для последнего элемента данного члена } // Цикл для прохода по всем цифрам предыдущего члена последовательности start = 0; quantity = 0; // Обнуляем все параметры для подсчета, так как дальше будем работать со следующим членом последовательности ToPrint(n, m, ¤tNumberColumn, ¤tNumberRow, 32); // Печатаем пробел после текущего члена последовательности previousTerm.clear(); previousTerm = currentTerm; // Записываем в вектор предыдущего члена текущий построенный член последовательности currentTerm.clear(); } // Бесконечный цикл, так как условие окончание работы программы задано в методе печати } |
Ссылки
- Код программы
- Дополнительная информация о «Look-and-Say» sequence:
Источник 1; Источник 2; Источник 3; Источник 4;
Хорошо, зачтено.
Надеюсь распознать последовательность было не слишком легко?
Добавьте, пожалуйста ссылку на OEIS A001155.
Спасибо, ссылку добавила.