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



Скачать 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


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

  1. Вспомогательной переменной max присваивается первый элемент последовательности

  2. 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 и вещественное число а. Для последовательности сумм:

, , , …,

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

Похожие:

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


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org