MLoops24

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex] m > 0[/latex] (количество строк).

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

Количество столбцов ([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. Чтобы получить последующий член последовательности, нам потребуется обратиться к предыдущему и выполнить следующее:

  1. Посчитать количество одинаковых подряд идущих цифр и записать его.
  2. Записать саму эту цифру.

Разберем на примере:

  • Первый член последовательности — [latex]0[/latex] («Основание» последовательности);
  • Второй член последовательности — [latex]10[/latex] («Вижу» один ноль);
  • Третий член последовательности — [latex]1110[/latex] («Вижу» одну единицу и один ноль);
  • Четвертый член последовательности — [latex]3110[/latex] («Вижу» три единицы и один ноль).

Реализуем данное построение на практике. Создадим два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (изначально start [latex] = 0[/latex]) и счетчик количества совпадающих элементов (изначально quantity [latex] = 0[/latex]). Запустим цикл от первого до последнего элемента массива previousTerm и выполним ряд действий, а именно:

  1. Пока последующие элементы совпадают с текущим сравниваемым, инкрементируем счетчик.
  2. Как только находиться элемент не совпадающий с текущим сравниваемым, выполняем вывод количества вхождений и само число, также записываем данные значения в вектор currentTerm. Переходим к следующей цифре для сравнения и присваиваем счетчику значение [latex]1[/latex].
  3. Отдельно выполняем предыдущий пункт для последней последовательности цифр или одной цифры, так как нет возможности сравнения с последующими.
  4. Как только один член последовательности полностью построен, обнуляем значения индекса сравниваемой цифры и счетчика. Также очищаем вектотр previousTerm и передаем ему значения вектора currentTerm, очищаем вектор currentTerm.

Теперь наша задача состоит в том, чтобы выполнить правильный вывод таблицы. Основную работу по построению таблицы будет выполнять метод ToPrint, принимающий как параметры заданное количество столбцов, строк, номер текущего столбца, текущей строки и цифру которую нужно вывести на печать (или пробел).
Рассмотрим детали его работы:

  1. При запуске метода сразу же увеличиваем текущий номер столбца, в который записывается символ, на [latex]1[/latex].
  2. Далее проверяем не превышает ли номер текущего столбца возможный. Если это так, то выполняем перевод курсора на новую строку, присваиваем текущему столбцу значение [latex]1[/latex] и инкрементируем значение номера текущей строки.
  3. Если количество строк превышает заданное, заканчиваем работу программы.
  4. В противном же случае выполняем печать символа, если это не пробел в начале строки (если это все же пробел в начале строки, то ничего не печатаем и уменьшаем значение текущего столбца для печати).  Для упрощения вывода пробел передается в метод по его коду в таблице ASCII — [latex]32[/latex]. Мы имеем полное право использовать число [latex]32[/latex] без угрозы ошибки, так как передавать мы будем  только цифры [latex]0, 1, 2, 3[/latex].

Таким образом общий алгоритм работы программы можем сформулировать так:

  1. Считываем заданное количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]).
  2. Для последующей работы объявляем переменные хранящие значения номера текущего столбца и строки (currentNumberColumn и currentNumberRow соответственно), два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (start) и счетчик количества совпадающих элементов (quantity) .
  3. Отправляем в вектор previousTerm значение «основания» последовательности — [latex]0[/latex].
  4. Выводим первый член последовательности и пробел после него (если потребуется).
  5. Далее запускаем бесконечный цикл, так как окончание работы программы предусмотрено в методе ToPrint.
  6. И выполняем последовательное построение членов последовательности (описано выше) и тут же вывод, пока количество строк не превышает заданное.

Код программы:

 

Ссылки

2 thoughts on “MLoops24

Добавить комментарий