Пара задач с олимпиады
В конце ноября была олимпиада по информатике. Вот пара заданий, с которыми я не справилась:
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)? ЗЫ: где-то на форуме я видела тему с олимпиадными задачами, но найти ее не могу. |
Так, ну с первой задачей ясно - ответ 721. Значения чисел определяются, как k!+1, где k = 1, 2, 3, 4, 5; k = 6 дает 721.
Со второй - будем думать. |
Ага, ну вот и вторая. Ответ:
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. На всякий случай - проверено. |
Задачи какие-то математические, а не "информатические" :)
Хотите информатическую? Поменять местами значение 2 переменных, не используя дополнительную переменную или указатели :) |
Спасибо за ответы! :)
Vladimir_S, спасибо огромное! Darkcosinus, над задачей подумаю завтра. |
Элементарно, Ватсон :) :
Read(x, y) y:=x+y; x:=y-2*x; x:=(x+y)/2; y:=y-x; Всё! Ох, сейчас мне опять будет выдано за неоптимизацию! |
Ой! Нам что-то такое на курсах рассказывали, только в общем виде, без Паскаля.
И что значит "неоптимизация"? |
Цитата:
Цитата:
|
Цитата:
Или сортировка массива методом пузырька - метод правильный, но не оптимальный. В оптимальном сам чёрт ногу сломит :) В общем это всё относится к другой теме, где мы разговаривали про задачу как раз на оптимальный алгоритм :) |
А можно ссылку на эту тему?
|
Часовой пояс GMT +4, время: 01:48. |
Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.