Задача 76217

Темы:    [ Знакомство с циклами ] [ Задачи с целыми числами ]

Сложность: 2 Классы:

Условие

Та же задача, но разрешается использовать из арифметических операций лишь сложение и вычитание, причём общее число действий должно быть порядка n.

Решение

Введём переменную k_square (square — квадрат), связанную с k соотношением k_square = k²:

        k := 0; k_square := 0;
        writeln (k_square);
        while not (k = n) do begin
        | k := k + 1;
        | {k_square = (k-1) * (k-1) = k*k - 2*k + 1}
        | k_square := k_square + k + k - 1;
        | writeln (k_square);
        end;

Замечание. Можно обойтись без вычитания с помощью такой хитрости:

        while not (k = n) do begin
        | k_square := k_square + k;
        | {k_square = k*k + k}
        | k := k + 1;
        | {k_square = (k-1)*(k-1)+(k-1)=k*k-k}
        | k_square := k_square + k;
        end;

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	1
Название	Задачи без массивов
задача
Номер	1.1.21