Решение задач на последовательности При решении таких задач бывает необходимо: каким-либо образом сортировать последовательности

Скачать 57.87 Kb.

Дата	13.06.2013
Размер	57.87 Kb.
Тип	Решение

3. Решение задач на последовательности
При решении таких задач бывает необходимо:

каким-либо образом сортировать последовательности
найти максимальные, минимальный значения
выбрать элементы согласно какому-либо условию
производить арифметические операции над определенными элементами последовательности и т.д.

Прежде всего рассмотрим общую структуру программы при решении задач на обработку последовательности чисел (массивов) на примере заполнения одномерного, двумерного массивов из входных файлов и вывод их в выходной файл.
3.1. Заполнить последовательность (одномерный массив) из 5 элементов из входного файла и вывести в выходной файл.

Пример входных и выходных данных:

input.txt	output.txt
8 12 -1 5 -23	8 12 -1 5 -23

program z3_1;

var f1,f2: text;

a: array [1..5] of integer; {описание массива из 5 элементов}

i: integer;

begin

assign (f1, 'input.txt'); reset (f1);

for i:=1 to 5 do read (f1,a[i]); {заполняем массив из входных данных}

close (f1);

{здесь будет размещаться решение задачи}

assign (f2, 'output.txt'); rewrite (f2);

for i:=1 to 5 do write (f2,a[i],' '); {выводим результирующий массив в выходной файл, пробел нужен для разделения элементов друг от друга}

close (f2);

end.

3.2. Заполнить таблицу (двумерный массив) из 3 строк и 4 столбцов (12 элементов) из входного файла и вывести в выходной файл.

Пример входных и выходных данных:

input.txt	output.txt
8 12 -1 5 3 -8 4 3 9 2 11 -7	8 12 -1 5 3 -8 4 3 9 2 11 -7

program z3_2;

var f1,f2: text;

a: array [1..3,1..4] of integer; {описание массива из 3 строк и 4 столбцов}

i,j: integer;

begin

assign (f1, 'input.txt'); reset (f1);

for i:=1 to 3 do for j:=1 to 4 do read (f1,a[i,j]);

close (f1);

{здесь будет размещаться решение задачи}

assign (f2, 'output.

txt'); rewrite (f2);

for i:=1 to 3 do

begin

for j:=1 to 4 do write (f2,a[i,j]:4); {для каждого элемента выделяем 4 позиции, чтобы была ровная таблица}

writeln (f2); {переводим вывод на следую строку, чтобы было в виде таблицы}

end;

close (f2);

end.
Рассмотрим типовые алгоритмы, которые могут быть использованы при решении задач на последовательности.
3.3. Задан ряд из 10 целых чисел. Найти наибольший элемент ряда. Пример входных и выходных данных:

input.txt	output.txt
-12 1 5 3 -8 14 -3 9 -28 5	14

Алгоритм решения:

Вспомогательной переменной max присваивается первый элемент последовательности
max сравнивается последовательно со всеми элементами последовательности, если max меньше очередного элемента, то max присваивается значение этого элемента (т.е. max всегда принимает наибольшее значение)

Обозначения:

a[i] – элемент ряда (массива)

i – индекс элемента ряда (массива)

max – вспомогательная переменная
Задание: Составьте алгоритм в виде блок-схемы.
Решение:

program z3_3;

var f1,f2: text; a: array [1..10] of integer; i,max: integer;

begin

assign (f1, 'input.txt'); reset (f1);

for i:=1 to 10 do read (f1,a[i]);

close (f1);
max:=a[1];

for i:=2 to 10 do if maxassign (f2, 'output.txt'); rewrite (f2);

write (f2, max);

close (f2);

end.
3.4. (Улусная олимпиада 2003 г.) Необходимо сортировать заданный ряд из 10 целых чисел по возрастанию. Пример входных и выходных данных:

input.txt	output.txt
30 12 -1 5 3 -8 4 3 9 -28	-28 -8 -1 3 3 4 5 9 12 30

Решение выполняется на основе так называемого метода «пузырька»:

Начиная с первого элемента сравниваем его с последующим, если предыдущий элемент больше последующего меняем их местами, в противном случае переходим к следующей паре:

8 12 1 5 23 2 4 16 5 9 8<12, переходим к следующей паре

8 12 1 5 23 2 4 16 5 9 12>1, меняем местами

8 1 12 5 23 2 4 16 5 9

8 1 12 5 23 2 4 16 5 9 12>5, меняем местами

8 1 5 12 23 2 4 16 5 9

... и т.д.

После того как рассмотрим последнюю пару, возвращаемся на начало и все повторяется. И так до тех пор пока все не отсортируется (т.е. больший элемент как пузырек стремится в конец ряда).

Сколько всего проходов (максимально) нужно произвести для полной сортировки?

Рассмотрим наихудший случай, когда наименьший элемент стоит в конце ряда, а наибольший в самом начале ряда. Тогда для того, чтобы они оказались в нужных местах необходимо проделать 9 циклов (т.е. в общем случае для ряда из N элементов N-1 раз).
Обозначения:

a[i] – элемент массива

i – индексы элемента массива

k – количество проходов

x – вспомогательная переменная для обмена значений пары элементов
Задание: Составьте блок-схему алгоритма.
Решение:

program z3_4;

var f1,f2: text; a: array [1..10] of integer; i,k,x: integer;

begin

assign (f1, 'input.txt'); reset (f1);

for i:=1 to 10 do read (f1,a[i]);

close (f1);

for k:=1 to 9 do {количество проходов}

begin

for i:=1 to 9 do if a[i]>a[i+1] then {цикл до 9, т.к. при 10 a[i+1] выходит за предел}

begin {далее идет обмен значений с использованием }

x:=a[i]; {дополнительного переменного, если a[i]>a[i+1] }

a[i]:=a[i+1];

a[i+1]:=x;

end;

end;

assign (f2, 'output.txt'); rewrite (f2);

for i:=1 to 10 do write (f2,a[i], ' ');

close (f2);

end.
Также есть задачи, в которых надо использовать формулы для вычисления i-того элемента последовательности. Рассмотрим на примере.
3.5. (Улусная олимпиада 2005 г.) Вычислить значение арифметического выражения

Без входного файла, выходные данные: числовое значение выражения.

output.txt

1.0404405653E+01

Идея решения: Вычисление надо начинать от внутреннего радикала. В данной задаче начальное значение

. Каждое следующее значение радикала будет вычисляться через предыдущее значение радикала по формуле

, число а изменяется от начального значения 5 до конечного значения 98 с шагом 3.
Задание: Составьте блок-схему алгоритма.
program z3_5;

var r,a: real; {вещественные числа}

f2: text;

begin

r:=sqrt(2);

a:=5;

while a<=98 do

begin

r:=sqrt(a+r);

a:=a+3;

end;

assign(f2, 'output.txt'); rewrite(f2);

write(f2,r);

close(f2);

end.

Задачи для самостоятельного решения
3.6. Задан ряд из 10 целых чисел. Найти наименьший элемент ряда. Пример входных и выходных данных:

input.txt	output.txt
-12 1 5 3 -8 14 -3 9 -28 5	-28

3.7. Необходимо сортировать заданный ряд из 10 целых чисел по убыванию. Пример входных и выходных данных:

input.txt	output.txt
30 12 -1 5 3 -8 4 3 9 -28	30 12 9 5 4 3 3 -1 -8 -28

3.8. Задана последовательность из 10 целых чисел. Найти все подпоследовательности подряд идущих чисел (т.е. чисел, увеличивающихся на 1). Пример входных и выходных данных:

input.txt	output.txt
5 4 3 4 13 7 8 9 1 2	3 4 7 8 9 1 2

3.9. (Улусная олимпиада 2005 г.) Дан двумерный массив А(5;5). Найти сумму S наибольших значений элементов ее строк. Входные данные: двумерный массив 5 строк и 5 столбцов; выходные данные: сумма S. Пример входных и выходных данных:

input.txt	output.txt
5 4 13 4 1 7 8 9 11 2 5 15 6 5 2 45 6 8 2 6	84

3.10. (Улусная олимпиада 2008 г.) Найти самый часто встречающийся элемент одномерного массива из 10 элементов. ( 6 баллов)

input.txt	output.txt
2 2 1 1 4 5 6 4 3 2	2

3.11. (Улусная олимпиада 2004 г.) Числами Фибоначчи называется последовательность 1, 1, 2, 3, 5 … (т.е. каждое последующее число равно сумме двух предыдущих чисел). Вычислить сумму всех чисел Фибоначчи, которые не превосходят заданного натурального числа N. Входные данные: N, выходные данные: список чисел Фибоначчи до N, сумма этих чисел.

input.txt	output.txt
10	1 1 2 3 5 8 20

3.12. (Улусная олимпиада 2001 г.) Заданы натуральное число n и вещественное число а. Для последовательности сумм:

, …,

найти первый ее член, который превышает число а.

Похожие:

	Решение задач со строковыми переменными При решении таких задач бывает необходимо: найти определенные символы (цепочки символов) поиск, подсчет Для решения задач со строковыми переменными необходимо уметь «вырезать» часть строковой переменной (слов), подсчитывать длину строковых...		Обобщённый метод интервалов при решении неравенств При решении многих задач, в том числе и задач Единого Государственного экзамена (егэ) часто возникает необходимость либо непосредственно...
	Решение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление) Алгоритм решения таких задач заключается в переборе возможных значений с проверкой условия делимости		Решение геометрических задач по планиметрии При решении большинства задач не обойтись без привлечения разнообразных фактов теории доказательств тех или иных утверждений. Но...
	Решение краевых задач с помощью s сплайна Мы рассмотрим, каким образом могут быть применены сплайны 3-й степени класса при решении уравнения Пуассона на круге и в других областях....		Дипломная работа Система моделирования муравьиных алгоритмов в грид: задача поиска последовательности мутаций между геномами Допущена к защите Интерес к муравьиным алгоритмам (Ant Colony Optimization Algorithm или aco) сильно возрос в последнее время [1]. Использование aco...
	Числовые последовательности Кратко ее обозначают символом называется общим членом последовательности. Т. к члены последовательности действительные числа, то...		Пояснительная записка Курс рассчитан на 17 часов Для успешного решения геометрических задач необходимо свободно владеть всем теоретическим материалом. Но и при хорошем знании теории...
	Решение задачи: «Найдите катеты прямоугольного треугольника, если известно, что один из катетов на 4 см меньше другого, а гипотенуза равна 20 см» Цель: Показать применение квадратных уравнений при решении задач, в измерительных работах на местности; выработать у учащихся навыки...		Решение задач по теме «Кинематика» Цель урока: Научить учащихся применять теоретические знания при решении задач с последующей проверкой в виртуальной лаборатории

Разместите кнопку на своём сайте:
ru.convdocs.org