Пара задач с олимпиады

[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 и разностью 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]

y:=x+y;

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

x:=(x+y)/2;

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

 

[Darkcosinus]

И что значит "неоптимизация"?

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

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

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

 

[ummasha]

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

 

[Vladimir_S]

y:=x+y;

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

Ну, Darkcosinus, теперь Вы меня по-настоящему достали!
Где в Вашей формулировке, скажите на милость, указано, что переменные имеют формат BYTE? Приведенное решение годится для форматов INTEGER, LongInt, REAL, EXTENDED и даже, если определить такой тип, то COMPLEX, т. е. переменные могут быть хоть комплексные!

x:=(x+y)/2;

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

Если бы Вы соблаговолили проследить всю цепочку, то поняли бы, что в данной строке величина (x+y) есть В ТОЧНОСТИ УДВОЕННОЕ ЗНАЧЕНИЕ ИСХОДНОЙ ВЕЛИЧИНЫ y! Т.е. возражение АБСОЛЮТНО вздорное!

P.S. Боже, упаси нас от таких начальников и заказчиков-самодуров!

 

[Vladimir_S]

Ладно, черт с Вами - если уж так надо извернуться, чтобы остаться в пределах типа BYTE... Можем и так.

IF x>y THEN
BEGIN
y:=x-y;
x:=x-y;
y:=x+y;
END ELSE
BEGIN
x:=y-x;
y:=y-x;
x:=x+y;
END;

 

[Darkcosinus]

Приведенное решение годится для форматов INTEGER, LongInt, REAL, EXTENDED и даже, если определить такой тип, то COMPLEX

А они ограничений не имеют? Я просто показал примером, что сложение там не пройдёт. Тип тут не важен.

С делением на 2 - был неправ, ошибся в расчётах.

Последнее решение нежизнеспособно - неправильно работает при x=y и опять же out of range в случае, если одно из значений отрицательное.

 

[Vladimir_S]

А они ограничений не имеют? Я просто показал примером, что сложение там не пройдёт. Тип тут не важен.

С делением на 2 - был неправ, ошибся в расчётах.

Последнее решение нежизнеспособно - неправильно работает при x=y и опять же out of range в случае, если одно из значений отрицательное.

При x=y работает - "стоя, лёжа и с колена"! Что-то у Вас, похоже, с арифметикой, сударь, не лады.
Что до знаков - ну можно выстроить цепочку типа
if (x>0) and (y<0) then ... else if ну и т.д. Скучища!

 

[ummasha]

У меня для вас отличная новость! Мне аж до конца учебного года дали книжку с самостоятельными и контрольными по программированию! Если возникнут затруднения - я сразу к вам.

 

[Vladimir_S]

У меня для вас отличная новость! Мне аж до конца учебного года дали книжку с самостоятельными и контрольными по программированию! Если возникнут затруднения - я сразу к вам.

Ну что же - чем можем, как говорится. Всегда пожалуйста.

 

[ummasha]

Задача: найти сумму цифр натурального числа:

Program k1_w1_a;
Var m,n,s,p:longint;
k:integer;
Begin
Write('n=');read;
m:=n;k:=0;s:=0;
while m<>0 do begin
p:=m mod 10;
s:=s+p;
Writeln('p=',p,'s=',s);
k:=k+1; m:=m div 10;end;
writeln('сумма цифр S=',s); readln;
end.

Все нормально, но зачем выводить это:

n=46
p=6s=6
p=4s=10
сумма цифр S=10

Это - промежуточные значения? Нельзя ли обойтись без них? Просто эта задача решена в книге, а потом дано еще несколько подобных для самостоятельной работы.

 

[Vladimir_S]

Это - промежуточные значения? Нельзя ли обойтись без них?

Можно, конечно. Так - для наглядности и для контроля хода выполнения программы. Обучение всё-таки.

 

[AlexZir]

Просто удалите Writeln('p=',p,'s=',s); из программы. Для чего оно нужно - написано выше.

 

[ummasha]

Спасибо! Так и сделаю.