ummasha

В конце ноября была олимпиада по информатике. Вот пара заданий, с которыми я не справилась:
1) какое из чисел является логическим продолжением ряда
2,3,7,25,121?
(варианты ответов: 252, 721, 158, 1021, 3175)
2) дан фрагмент программы на Паскале:

read(n,m);
sum:=0;
for i:=1 to n do
for j:=1 to m do
for x:=i to n do
for v:=j to m do
sum:=sum+1;
writeln(sum);

Этот фрагмент можно записать одним присваиванием:
sum:=f(n,m)
Какой вид имеет функция f(n,m)?

ЗЫ: где-то на форуме я видела тему с олимпиадными задачами, но найти ее не могу.

Vladimir_S

Так, ну с первой задачей ясно - ответ 721. Значения чисел определяются, как k!+1, где k = 1, 2, 3, 4, 5; k = 6 дает 721.

Со второй - будем думать.

Vladimir_S

Ага, ну вот и вторая. Ответ:
f(n,m) = n*(n+1)*m*(m+1)/4

Рассуждаем так:
Если бы было

for i:=1 to n do
for j:=1 to m do
sum:=sum+1;

то ответ, очевидно, был бы m*n.

Если бы было

for i:=1 to n do
for x:=i to n do
sum:=sum+1;

то ответ был бы суммой n членов арифметической прогрессии с а(1) = 1, а(n) = n и разностью 1, то есть (1+n)*n/2.

Теперь замечаем, что циклы можно переставить местами, чтобы упорядочить:

for i:=1 to n do
for x:=i to n do
for j:=1 to m do
for v:=j to m do
sum:=sum+1;

поскольку суммирования по парам индексов (i,x) и (j,v) взаимно независимы, то есть результат, как и в первом упрощении, есть произведение результатов по каждой паре. Отсюда и получается произведение двух сумм арифметических прогрессий.

P.S. На всякий случай - проверено.

Darkcosinus

Задачи какие-то математические, а не "информатические"

Хотите информатическую?
Поменять местами значение 2 переменных, не используя дополнительную переменную или указатели

ummasha

Спасибо за ответы!
Vladimir_S, спасибо огромное!
Darkcosinus, над задачей подумаю завтра.

Vladimir_S

Элементарно, Ватсон :

Read(x, y)
y:=x+y;
x:=y-2*x;
x:=(x+y)/2;
y:=y-x;

Всё! Ох, сейчас мне опять будет выдано за неоптимизацию!

ummasha

Ой! Нам что-то такое на курсах рассказывали, только в общем виде, без Паскаля.
И что значит "неоптимизация"?

Darkcosinus

x=250, y=251... Получите integer out of range, распишитесь

А вдруг число нечётное? type mismatch

Darkcosinus

Использование неоптимального алгоритма. Ну к примеру если есть задача поиска простых чисел в диапазоне от 1 до N, и решается она перебором всех чисел от 1 до N - это алгоритм верный, но не оптимальный, т.к. можно сделать перебор только нечётных чисел, т.к. чётные простыми по определению не являются (ну, кроме 2).

Или сортировка массива методом пузырька - метод правильный, но не оптимальный. В оптимальном сам чёрт ногу сломит

В общем это всё относится к другой теме, где мы разговаривали про задачу как раз на оптимальный алгоритм

ummasha

А можно ссылку на эту тему?