Отправляет email-рассылки с помощью сервиса Sendsay

Дистанционное обучение

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 406 RSS
←   Октябрь 2008   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://дистанционный-репетитор.рф
Открыта: 04-12-2005

Автор
Андрей Темнов

Статистика

406 подписчиков
0 за неделю
←   Все выпуски   →

Уроки и методика преподавания информатики для учителей www.thl.narod.ru


Задача №2. Строки Фибоначчи
Последовательность строк Фибоначчи определяется следующим образом: S[1]=?b?, S[2]=?a?, S[k] = S[k-1] + S[k-2] для k>2. Например, S[3]=?ab?, S[4]=?aba?, S[5]=?abaab? и т. д.
Даны натуральные числа N, М, L. Требуется вывести подстроку строки s[N], начинающуюся с позиции M и имеющую длину L.
Входной файл INPUT.TXT содержит одну строку, в которой находятся три разделённых пробелом натуральных числа N, M и L, где
1<=N<=40; 1<=M<=length(S[N]), 1<=L<=1000.
Выходной файл OUTPUT.TXT содержит подстроку строки S[N], начинающуюся с позиции M и имеющую длину L (длина выведенной подстроки может оказаться меньше, если длина оставшейся части строки S[N] , начинающейся с позиции M, меньше L).
Пример:
input.txt
5
3
10
output.txt
aab

Решение.

Этой задача решается аналогично предыдущей с той разницей, что мы должны хранить все длины строк или вычислять по мере надобности.
Теория.
Сложность алгоритмов.
После того, как программист ознакомится с задачей, которую он должен решить, он должен выбрать алгоритм, с помощью которого он и будет ее решать. Обычно задача имеет несколько различных решений, эффективных и не очень, иногда крайне нерациональных.
Рассмотрим простейшую задачу: найти сумму всех натуральных чисел от 1 до N, где
1<=N<=3 000 000 000. В первую секунду раздумий приходит простейшее решение: for i:=1 to N do sum:=sum+i. Разумеется, оно неэффективно: на третью секунду размышлений приходит другой вариант: sum=(1+N)/2*N, принципиально улучшить который невозможно. Отсюда возникает вопрос: насколько эффективен должен быть алгоритм и когда его улучшение можно прекратить. Все задачи, решаемые программистами, можно разделить на три класса: учебные, олимпиадные и реальные. Учебные задачи обычно просты и требуют от решающего лишь
знания определенного материала. Творческий подход здесь почти отсутствует. В отличие от учебных задач, олимпиадные могут требовать для своего решения знания практически чего угодно и каких угодно разделов науки (обычно математики, реже – физики); кроме того, часто нужно время, а иногда и немалое, чтобы пообобрать подходящий алгоритм решения. Но у этих задач, по сравнению с реальными, есть одно несомненное преимущество: обычно они предусматривают решению, удовлетворяющее условиям. То есть в этих задачах есть
ограничения на входные данные. Еще более непредсказуемы задачи, возникающие на практике, названные мной реальными. Часто они бывают довольно просты, но иногда попадаются и такие, для решения которых придется основательно пораскинуть мозгами. Если подобные задачи сразу не решаются, то у программиста обычно возникает одна из двух мыслей: «Я слишком туп для решения этой задачи», «А можно ли вообще найти эффективной решение этой задачи». Что касается второй мысли, то, действительно, существуют классы задач, удовлетворительного
решения которых до сих пор пока не и, вероятно, никогда не будет. В качестве примеров можно привести задачи дешифровки данных, закодированных с помощью некоторых современных алгоритмов. Но это еще не самое страшное: существуют задачи, решить которые невозможно вообще! В качестве примера можно привести десятую проблему Гильберта: существует ли алгоритм, который позволяет для произвольного многочлена p(x[1],x[2],…,x[n]) выдает, имеет ли решение в целых числах уравнение p=0. Также, например, невозможно построить
алгоритм, который для произвольной программы и произвольных входных данных определял бы, корректно ли работает данная программа.
Зачастую время выполнения программы определяется не столько сами исходные данные, сколько их «размер». Под размером здесь и далее мы понимаем как физический размер данных (например, длина последовательности), так и размер рассматриваемых объектов (например, строки в задачах предыдущего выпуска). Обычно говорят, что время выполнения программы имеет порядок T(n) от входных данных размера n. Например, некая программа имеет время выполнения T(n) = cn^2, где c – константа. Единица измерения точно не определена, но
мы будем понимать T(n) как количество инструкций, выполняемых на идеализированном компьютере. Можно также рассматривать T(n) как время выполнение программы в случае наихудшего набора входных данных, кроме того, иногда T(n) рассматривают как среднее время выполнения программы.
Для описания скорости роста функции T(n) используется O-символика. Например,
когда говорят, что время выполнения T(n) некоторой программы имеет порядок O(n^2), то подразумевают, что существуют положительные константы c и n0 такие, что для всех n>=n0 выполняется неравенство T(n)<=cn^2. Так как обычно вся программа разбивается на фрагменты, то время ее выполнения можно сосчитать как сумму или произведение отдельных ее частей. Пусть T1(n) и T2(n) – время выполнения двух программных фрагментов P1 и P2. T1(n) имеет степень роста O(f(n)), а T2(n) – O(g(n)). Тогда T1(n)+T2(n), т. е. время последовательного
выполнения фрагментов P1 и P2, имеет степень роста O(max(f(n),g(n))). Аналогично вычисляется степень роста произведения T1(n)*T2 (n): она равна O(f(n)*f(n)).
Проиллюстрируем сказанное на примере пузырьковой сортировки.
const n=100;
var A: array[1..n] of integer;
i, j, temp: integer;
begin
for i:=1 to n do A[i]:=random(1000);
for i:=1 to n-1 do
for j:=n downto i+1 do
if A[j-1]>A[j] then begin
{ перестановка местами A[j-1] и A[j] }
temp:=a[j-1];
a[j-1]:=a[j];
a[j]:=temp;
end;
for i:=1 to n do write(A[i],’ ’)
end.

Здесь P1 – ввод данных, P2 – сортировка, P3 – вывод данных. Степень роста P1
и P2 равна O(n), так как выполняется ровно n операций. Время выполнения внутреннего
цикла в сортировки зависит от i: он выполняется от 1 до n-2 раз, поэтому для
него порядок времени выполнения можно считать n/2, то есть O(n); для внешнего
цикла его также можно считать O(n), но тогда порядок времени выполнения всего
цикла равен O(n*n)=O(n^2). Порядок времени выполнения всей программы будет равен
O(max(n,n^2,n)) = O(n^2).
Стоит также отметить то, что иногда вместо того, чтобы говорить «порядок времени
выполнения» говорят просто «время выполнения», подразумевая, что время работы
программы зависит от n так же, как и выражение, находящееся под символом O.
Если время выполнения участка кода не зависит от n, то его сложность считают
равной О(1).

в следуюжем выпуске мы рассмотрим решение задачи:
Задача 3.
Максимальная подматрица.
Дана матрица N*N из целых двузначных чисел. Требуется найти подматрицу с тем
условием, чтобы сумма чисел этой подматрицы была максимальной.
Входной файл (input.txt):

В первой строке содержится количество строк исходной матрицы.
В последующих N строках записана сама матрица.

Выходной файл:
Сумма найденной подматрицы.

Пример:
input.txt

-----начало файла-----
5
3 0 –7 14 20
–5 17 99 –99 0
11 –1 5 0 10
-9 10 34 78 –53
3 -27 15 –2 -10
-----конец файла-----

output.txt

-----начало файла-----
159
-----конец файла-----

Комментарий: 17+99+(-1)+5+10+34 = 159

Удач в решении задач. До следующего выпуска.
В избранное