MLoops22

Условие

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

1491625364964811001211441
6919622525628932436140044
1484529576625676729784841
9009611024108911561225129

Тестирование

№	Входные данные	Выходные данные
1	1 1	1
2	7 1	1491625
3	10 2	1491625364 9648110012
4	1 3	1 4 9
5	1 6	1 4 9 1 6 2
6	5 5	14916 25364 96481 10012 11441
7	25 4	1491625364964811001211441 6919622525628932436140044 1484529576625676729784841 9009611024108911561225129

Код

#include <iostream>
#include <cmath>
using namespace std;

// Возвращает длину числа
int GetLength(int a) {
	return (a==0?1:log10(a)+1);
}

// Возвращает левую часть числа до заданной цифры включительно
int LeftPart(int a, int n) {
	return a/pow(10, GetLength(a) - n);
}

// Возвращает правую часть числа после заданной цифры
int RightPart(int a, int n) {
	int p = pow(10, GetLength(a) - n);
	return a%p;
}

int main() {
	int n, m, i = 0, toPrint; // Столбцы, строки, счетчик очередного числа для возведения в квадрат, текущее значение для печати
	bool haveRest = false;	// Есть ли часть числа, "отрезанная" после переноса строки
	cin >> n >> m;
	int columnsLeft = n;	// Присваиваем переменной для оставшихся свободных столбцов значения общего количества столбцов
	while(m > 0) {
		if(columnsLeft == 0) {	// Если не осталось свободных столбцов
			m--;
			if(m > 0)
				cout << endl;
			columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
			haveRest = false;	// "Отрезанной" части числа нет
		} else {	// Если есть свободные столбцы
			i = (haveRest?i:++i);
			toPrint = (haveRest?toPrint:i*i);	// Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа
			if(GetLength(toPrint) <= columnsLeft) {	// Если хватает свободных столбцов для печати числа в toPrint
				cout << toPrint;
				columnsLeft -= GetLength(toPrint);	// Обновляем количество свободных столбцов
				haveRest = false;	// "Отрезанной" части числа нет
			} else {	// Если свободных столбцов не хватает для печати числа в toPrint целиком
				cout << LeftPart(toPrint, columnsLeft);	// Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы
				toPrint = RightPart(toPrint, columnsLeft);	// Присваиваем toPrint значение его ненапечатанной части
				m--;
				if(m > 0)
					cout << endl;
				columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
				haveRest = true;	// "Отрезанная" часть числа есть
			}
		}
	}
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

// Возвращает длину числа

int GetLength(int a) {

return (a==0?1:log10(a)+1);

}

// Возвращает левую часть числа до заданной цифры включительно

int LeftPart(int a, int n) {

return a/pow(10, GetLength(a) - n);

}

// Возвращает правую часть числа после заданной цифры

int RightPart(int a, int n) {

int p = pow(10, GetLength(a) - n);

return a%p;

}

int main() {

int n, m, i = 0, toPrint; // Столбцы, строки, счетчик очередного числа для возведения в квадрат, текущее значение для печати

bool haveRest = false; // Есть ли часть числа, "отрезанная" после переноса строки

cin >> n >> m;

int columnsLeft = n; // Присваиваем переменной для оставшихся свободных столбцов значения общего количества столбцов

while(m > 0) {

if(columnsLeft == 0) { // Если не осталось свободных столбцов

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = false; // "Отрезанной" части числа нет

} else { // Если есть свободные столбцы

i = (haveRest?i:++i);

toPrint = (haveRest?toPrint:i*i); // Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

if(GetLength(toPrint) <= columnsLeft) { // Если хватает свободных столбцов для печати числа в toPrint

cout << toPrint;

columnsLeft -= GetLength(toPrint); // Обновляем количество свободных столбцов

haveRest = false; // "Отрезанной" части числа нет

} else { // Если свободных столбцов не хватает для печати числа в toPrint целиком

cout << LeftPart(toPrint, columnsLeft); // Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы

toPrint = RightPart(toPrint, columnsLeft); // Присваиваем toPrint значение его ненапечатанной части

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = true; // "Отрезанная" часть числа есть

}

return 0;

}

Решение

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

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

Опираясь на вышеперечисленное, опишем алгоритм работы цикла построения таблицы более подробно:

В первую очередь проверяется условие продолжения цикла. Цикл будет выполняться до тех пор, пока количество полностью напечатанных строк (то есть строк, длина которых равна заданному количеству столбцов) будет меньше требуемого количества строк в готовой таблице.
Определяется количество свободных столбцов в текущей строке. Если оно равно нулю, выполняется перевод на новую строку, количество полностью напечатанных строк увеличивается на [latex]1[/latex] и итерация цикла завершается.
Определяется последовательность цифр, печатаемая в текущей итерации цикла. Если с прошлой итерации в результате переноса строки осталась «отрезанная» часть числа, то в этой итерации будет выводиться она; иначе же будет выводиться квадрат очередного натурального числа.
Проверяется, сможет ли число, сформированное на предыдущем шаге, полностью уместиться в текущей строке. Если его длина меньше или равна количеству свободных столбцов, то оно выводится в поток и итерация цикла завершается; в противном случае выводится та его часть, которая может уместиться в строке, ненапечатанная часть сохраняется и будет выведена в следующей итерации (если выполнится условие продолжения цикла), количество полностью напечатанных строк увеличивается на [latex]1[/latex] и итерация цикла также завершается.

Чтобы реализовать такой алгоритм, нам, помимо указанных в условии целочисленных переменных n и m для обозначения требуемого количества столбцов и строк в таблице, также понадобятся следующие переменные и функции:

int i для хранения очередного натурального числа, квадрат которого нужно вычислить;
int toPrint для хранения числа, которое нужно будет выводить в очередной итерации цикла;
int columnsLeft для хранения числа свободных столбцов в текущей строке;
bool haveRest для обозначения наличия или отсутствия «отрезанной» в результате переноса строки части числа;
функция int GetLength(int a), возвращающая длину числа a;
функция int LeftPart(int a, int n), возвращающая левую часть числа a до n-той цифры включительно;
функция int RightPart(int a, int n), возвращающая правую часть числа a после n-той цифры.

До начала выполнения цикла присвоим переменной haveRest значение false («отрезанные» части чисел могут появится не раньше второй итерации), а переменной columnsLeft — считанное значение количества столбцов в таблице n.

Составим код цикла, следуя описанному выше алгоритму построения таблицы. Условием продолжения цикла будет наличие не напечатанных до конца строк m (в дальнейшем будем декрементировать m всякий раз при переносе строки):

while(m > 0)

1	while(m > 0)

Теперь выполняем проверку на наличие свободных столбцов в текущей строке. Если окажется, что в строке свободных столбцов не осталось, выполняем перенос на новую строку, после чего восстанавливаем число оставшихся столбцов (задаем переменной columnsLeft значение количества столбцов в таблице n) и указываем, что «отрезанная» часть отсутствует:

if(columnsLeft == 0) {	// Если не осталось свободных столбцов
	m--;
	if(m > 0)
		cout << endl;
	columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
	haveRest = false;	// "Отрезанной" части числа нет
}

if(columnsLeft == 0) { // Если не осталось свободных столбцов

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = false; // "Отрезанной" части числа нет

}

Если же свободные столбцы есть, определяем число, которое будет печататься в этой итерации. В случае, если «отрезанная» часть отсутствует, переменной toPrint присваиваем значение квадрата очередного натурального числа, иначе оставляем ее без изменений ( toPrint получает значение ненапечатанной части числа в конце цикла, если таковая имеется):

i = (haveRest?i:++i);
toPrint = (haveRest?toPrint:i*i);	// Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

1 2	i = (haveRest?i:++i); toPrint = (haveRest?toPrint:i*i); // Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

Наконец, оценим, может ли число, хранящееся в toPrint, уместиться в текущей строке. Если может, то выводим его, обновляем число свободных столбцов в строке и указываем, что «отрезанной» части числа нет:

if(GetLength(toPrint) <= columnsLeft) {	// Если хватает свободных столбцов для печати числа в toPrint
	cout << toPrint;
	columnsLeft -= GetLength(toPrint);	// Обновляем количество свободных столбцов
	haveRest = false;	// "Отрезанной" части числа нет
}

if(GetLength(toPrint) <= columnsLeft) { // Если хватает свободных столбцов для печати числа в toPrint

cout << toPrint;

columnsLeft -= GetLength(toPrint); // Обновляем количество свободных столбцов

haveRest = false; // "Отрезанной" части числа нет

}

В противном случае печатаем ту часть числа, которая помещается в строке, после чего присваиваем переменной toPrint значение ненапечатанной части, выполняем перенос строки, восстанавливаем количество свободных столбцов и указываем, что имеется «отрезанная» часть числа. Таким образом, в следующей итерации (если выполнится условие продолжения цикла) выводиться будет не очередной квадрат, а правая часть числа, которая не уместилась в предыдущей строке.

else {	// Если свободных столбцов не хватает для печати числа в toPrint целиком
	cout << LeftPart(toPrint, columnsLeft);	// Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы
	toPrint = RightPart(toPrint, columnsLeft);	// Присваиваем toPrint значение его ненапечатанной части
	m--;
	if(m > 0)
		cout << endl;
	columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
	haveRest = true;	// "Отрезанная" часть числа есть
}

else { // Если свободных столбцов не хватает для печати числа в toPrint целиком

cout << LeftPart(toPrint, columnsLeft); // Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы

toPrint = RightPart(toPrint, columnsLeft); // Присваиваем toPrint значение его ненапечатанной части

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = true; // "Отрезанная" часть числа есть

}

Ссылки

Код программы на Ideone.com;

Последовательность в OEIS;

Список задач на циклы.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

MLoops22

Условие

Тестирование

Код

Решение

Ссылки

Related Images:

Понравилось это:

Похожее

One thought on “MLoops22”

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

Условие

Тестирование

Код

Решение

Ссылки

Related Images:

Share this:

Понравилось это:

Похожее

One thought on “MLoops22”

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