Запишите на языке паскаль массива в котором 111 элементов

Методика быстрого обучения программированию на основе изучения классов задач (11-15) Текст научной статьи по специальности «Математика»

АЛГОРИТМ / ALGORITHM / ПРОГРАММА / PROGRAM / ЯЗЫК ПРОГРАММИРОВАНИЯ ПАСКАЛЬ / PROGRAMMING LANGUAGE PASCAL / МАССИВ / ARRAY / ПРОЦЕДУРЫ И ФУНКЦИИ / PROCEDURES AND FUNCTIONS / РЕКУРСИЯ / RECURSION / МНОЖЕСТВО / SET / ЗАПИСЬ / RECORD

Аннотация научной статьи по математике, автор научной работы — Аляев Юрий Александрович

Предлагается методика быстрого обучения программированию на основе изучения классов задач, разработанная и применяющаяся на практике в процессе обучения программированию студентов вузов

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Аляев Юрий Александрович

Методика быстрого обучения программированию на основе изучения классов задач (16-17)
Методика быстрого обучения программированию на основе изучения классов задач (6-7)
Методика быстрого обучения программированию на основе изучения классов задач (18-19)
Методика быстрого обучения программированию на основе изучения классов задач (8-10)
Методика быстрого обучения программированию на основе изучения классов задач
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Methods of the quick education to programming on base of the study of the classes of the problems (11-15)

Is offered methods of the quick education to programming on base of the study of the classes of the problems, designed and using in practice in process of the education to programming student high school

Текст научной работы на тему «Методика быстрого обучения программированию на основе изучения классов задач (11-15)»

1. Дорошенко Е.Г., Пак Н.И., Рукосуева Н.В., Хегай Л.Б. О технологии разработки ментальных учебников // Вестник Томского государственного педагогического университета (Tomsk State Pedagogical University Bulletin). 2013. Вып. 12 (140). С. 145-151.

2. Новак Д., Канас А. Теория построения и практика применения карт понятий. URL: http://cmap.ihmc.us/Publications/ResearchPapers/TheoryCmaps/TheoryUnderl

3. Шенк Ф.Б. Ментальные карты: конструирование географического пространства в Европе / пер. с нем. А. Жоровой // Политическая наука. Политический дискурс: История и современные исследования. 2001. Вып. 4. С. 4-17.

4. Шаталов В.Ф. Эксперимент продолжается. М.: Педагогика, 1989. 334 с.

5. Калитина В.В. Электронная энциклопедия как средство повышения уровня запоминания учебного материала // Вестник КГПУ. 2013. № 1 (23). С. 111-114.

6. Мюллер Х. Составление ментальных карт: метод генерации и структурирования идей / пер. с нем. В.В. Мартыновой, М.М. Демина. М.: Омега-Л, 2007. 126 с.

7. Пак Н.И. Гипермозг как основа становления ментальной дидактики. Интернет — свободный, безопасный, образовательный // Межрегион. науч.-практ. конф. (18-19 октября, 2013 г., г. Омск): сб. матер. / под общ. ред. М.П. Лапчика. Омск: Полиграфический центр КАН, 2013. 278 с.

8. Пак Н.И. Информационное моделирование: учебное пособие. // КГПУ им. В.П. Астафьева. Красноярск, 2010. 152 с.

9. Колесник В. Ментальные карты. URL: http://kolesnik.ru/2005/mindmapping

10. Петрова И.А., Ракова Е.П. Использование структурированных графических схем в изучении информатики // Успехи современного естествознания. 2013. № 10. С. 35-36.

11. Найссер У. Познание и реальность. М.: Прогресс, 1981. 252 с.

12. Бруннер Е.Ю. Применение технологии mind map в учебном процессе // Развитие международного сотрудничества в области образования в контексте Болонского процесса: материалы международной науч.-практ. конф. г. Ялта (5-6 марта 2008 г.). Ялта: РИО КГУ, 2008. Вып. 19. Ч. 1. С. 50-53.

13. Бабич А.В. Эффективная обработка информации (Mind mapping). URL: http://www.intuit.ru/studies/courses/647/503/lecture/11414?page=8

Use in educational process mental map

Damir Rashitovich Khakimov, Master SibGTU, Siberian State Technological University,

In this paper, the technique used in the training process of mental maps, the technology development which is based on the information model of thinking. Using this technique significantly affects the intensification of training and intensifying training activities due to higher than traditional teaching methods, the degree of visualization of the material presented.

Keywords: mental map, image, information model of thinking, structuring the learning process

МЕТОДИКА БЫСТРОГО ОБУЧЕНИЯ ПРОГРАММИРОВАНИЮ НА ОСНОВЕ ИЗУЧЕНИЯ КЛАССОВ ЗАДАЧ (11-15)

Юрий Александрович Аляев, доц., доц. кафедры программного обеспечения вычислительной техники и автоматизированных систем,

e-mail: alyr1@yandex.ru, Пермский военный институт внутренних войск МВД России,

Предлагается методика быстрого обучения программированию на основе изучения классов задач, разработанная и применяющаяся на практике в процессе обучения программированию студентов вузов.

Ключевые слова: алгоритм, программа, язык программирования Паскаль, массив, процедуры и функции, рекурсия, множество, запись

Разделы курса «Информатика» — алгоритмизация и программирование — остаются наиболее важными для формирования алгоритмического мышления. Поскольку в школах данные разделы преподаются в недостаточном объеме, в вузе возникает необходимость начинать обучение с нуля и достичь хорошего уровня программирования при ограниченном количестве часов преподавания.

Этого удается добиться за счет применения рациональных методов обучения, прежде всего, последовательно проводя идеи обучения на основе выделения элементарных операций деятельности по построению алгоритмов и программ; выявления структуры алгоритма и форм ее записи на алгоритмическом языке; одинаковой формы алгоритма для решения задач с одинаковой структурой исходных данных [1-2]. Благодаря этим идеям, задачи по программированию удается разбить на ряд классов и типизировать методы решения задач каждого класса.

Предлагаемая методика быстрого обучения программированию на основе изучения классов задач, появилась и применяется на протяжении многих лет в процессе обучения программированию студентов пермских вузов благодаря В.П. Гладкову [2]. В статье рассматриваются методики решения по пяти (11-15) из девятнадцати выделенных классов задач (1-10 классы задач рассмотрены в [3-6]).

11. Данные типа string

Задача 1. Подсчитать, сколько раз в заданной строке встречается указанная буква. Решение 1. Пусть исходная строка хранится в переменной s, а искомая буква в переменной а. Для решения задачи будем просматривать строку s посимвольно и каждый символ сравнивать с заданной буквой. k:=0; for i:=1 to length(s) do

if copy(s,i,1)=a then k:=k+1;. Решение 2. Будем искать положение указанной буквы в строке до тех пор, пока ее удастся найти. Затем отбрасываем ту часть строки, где была найдена указанная буква, и повторяем поиск.

s:=copy(s,j+1 ,length(s)-j); j:=pos(a,s); end.

Задача 2. Проверить, входят ли в строку s две буквы а.

Решение. Для двух букв а, стоящих подряд: if pos(‘aa’,s)>0 then write(‘входят’) else write(‘HE входят’). Здесь требуется проверить наличие двух букв а, стоящих в любом месте строки. Эта задача является поисковой. Если строка закончится и две буквы а не будут найдены, то ответ на вопрос задачи отрицательный. Если при поиске будут найдены две буквы а, то ответ на вопрос задачи положительный. Для подсчета найденных букв а использовать счетчик. k:=0; f:=false; i:=1; while (i<=length(s)) and not f do if copy(s,i,1)='a' then begin k:=k+1;

if k=2 then f:=true;

then write(‘в строке есть две буквы а’) else write^ строке нет двух букв а’);. Другое решение этой задачи можно получить, основываясь на втором решении задачи 10.1.1.

then begin s:=copy(s,j+1,length(s)-j); j:=pos(‘a’,s); if j>0

then write(‘в строке есть две буквы а’) else write^ строке нет двух букв а’);

else write^ строке нет двух букв а’);.

Задача 3. В строке s заменить символы а на символы я.

Решение 1. Просматриваем строку посимвольно, удаляем найденный символ а, вставляем на его место я. for i:=1 to length(s) do if copy(s,i,1)=’a’ then begin delete(s,i,1) insert(V,s,i);

Решение 2. Просматриваем исходную строку посимвольно и переписываем в выходную строку символы, отличные от а. Вместо символа а переписываем символ я. s1:=»; < выходная строка >for i:=1 to length(s) do if copy(s,i,1)=’a’ then s1:=s1+V else s1:=s1+copy(s,i,1);. Решение 3. Оно основывается на решении 2 задачи 10.1.1. j:=pos(‘a’,s); while j<>0 do

Задача 4. Будем считать словом любую последовательность букв и цифр. Строка состоит из слов, разделенных одним или несколькими пробелами. Удалить лишние пробелы, оставив между словами по одному пробелу.

Решение. Лишними пробелами называются второй, третий и т.д., следующие за первым пробелом. Следовательно, чтобы найти лишний пробел, нужно искать два пробела, стоящие рядом, и удалять второй пробел в каждой найденной паре. j:=pos(‘ ‘,s); while j<>0 do begin delete(s,j,1);

Задача 5. Строка символов — это любая последовательность символов, заключенная в апострофы. Задана строка символов, состоящая из слов и строк,

разделенных одним или несколькими пробелами. Удалить из строки все незначащие пробелы. Незначащими пробелами называются пробелы, не стоящие в апострофах.

Решение. Запишем формально определение незначащего пробела. Текущий пробел незначащий, если предыдущий символ является пробелом и этот пробел не стоит в апострофах. Введем логическую переменную p, которая принимает значение false, если предыдущий символ не является пробелом, и значение true, если предыдущий символ — пробел. Введем логическую переменную q, которая принимает значение false, если пробел находится не в апострофах, и значение true, если пробел в апострофах. Тогда формальное определение незначащего пробела запишется так: (copy(s,i,1)=’ ‘) and p and not q.

Составляем программу: p:=false; q:=false; s1:=»;

for i:=1 to length(s) do begin if not((copy(s,i,1)=’ ‘) and p and not q) then s1:=s1+copy(s,i,1); if copy(s,i,1)=’ ‘ then p:=true else p:=false; if copy(s,i,1)=»» then q:=not q; end;.

Задача 6. Подсчитать количество гласных букв русского алфавита в строке. Решение. Гласная буква — это такая буква, которая принадлежит множеству гласных букв. Для решения задачи просматриваем строку посимвольно и проверяем каждый символ на принадлежность гласным буквам: k:=0; for i:=1 to length(s) do if pos(copy(s,i,1),’аоуэыяёюеи’)>0 then k:=k+1;.

Задача 7. Задано предложение, состоящее из слов, разделенных одним или несколькими пробелами. Определить самое длинное слово предложения.

Решение. Для того чтобы выделить окончание слова, нужно анализировать два символа: первый символ должен быть отличен от пробела, а второй должен быть пробелом. Для одинаковой обработки всех символов добавим к концу предложения дополнительный символ — пробел. Как только обнаружится конец слова, вычислим его длину и проверим на максимум:

то запоминаем его>

else if copy(s,i,1)<>‘ ‘ then ss:=ss+copy(s,i,1);

Задача 8. Задано предложение, состоящее из слов, разделенных одним или несколькими пробелами. Расположить слова предложения в алфавитном порядке.

Решение. Перепишем слова предложения по одному в элементы одномерного массива. Отсортируем массив по возрастанию и перепишем слова из массива в строку. const nn=100; type mas=array[1..nn]of string; var a:mas; i,j , k:integer; s,

write(‘Введите строку ‘); readln(s);

if a[i]>a[j] then begin

for i:=1 to k do s:=s+a[i]+’ ‘; write(s); end.

12. Процедуры и функции

Задача 1. Написать программы для вычисления числа сочетаний из n по m, оформив вычисления факториала процедурой без параметров, процедурой с параметрами, функцией. Сравнить решения.

Решение 1. Воспользуемся известной формулой: n!

procedure fact1; var i:longint; begin p:=1;

for i:=1 to q do p:=p*i;

begin write(‘Введите n и m ‘); readln(n,m);

write(‘Число сочетаний из ‘,n,’ по ‘,m,’ равно ‘,c); end.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

procedure fact2(q:longint;var p:longint); var i:longint; begin p:=1;

for i:=1 to q do p:=p*i;

begin write(‘Введите n и m ‘); readln(n,m); fact2(n,fn); fact2(m,fm); fact2(n-m,fnm); c:=fn div (fm*fnm);

write(‘Число сочетаний из ‘,n,’ по ‘,m,’ равно ‘,c); end.

c:longint; function fact3 (q: longint): longint; var i:longint; begin p:=1;

for i:=1 to q do p:=p*i; fact3:=p;

begin write(‘Введите n и m ‘); readln(n,m);

write(‘Число сочетаний из ‘,n,’ по ‘,m,’ равно ‘, fact3(n) div (fact3(m)*fact3(n-m))); end.

Задача 2. Даны два числа a и b. Разработать алгоритм и написать программу для определения наибольшего общего делителя (НОД) трех величин: a+b, I a-b I , a-b. Расчет НОД двух чисел оформить в виде пользовательской процедуры.

Математическая модель данной задачи имеет вид:

Расчет: x=a+b; y=| a-b I ; z=a-b.

Для расчета наибольшего общего делителя используем следующее выражение: нод^у^^нодснод^у)^). Для расчета НОД двух чисел используем алгоритм Евклида.

Фрагмент алгоритма для расчета наибольшего общего делителя k двух чисел n и m имеет вид:

Цикл-ПОКА (m*n); Если m>n То;

n:=n-m; Конец-Если; Конец-Цикла; k:=m;

В Паскаль-программе пользовательская процедура размещается в разделе описания процедур и функций.

procedure evklid(m,n:integer; var k:integer);

while m<>n do if m>n then m:=m-n else n:=n-m; k:=m; end;

writeln(‘a=’,a,’ b=’,b); evklid(a+b,abs(a-b),c); evklid(c,a*b,c); writeln(‘нод=’,c);

В данной программе обращение к пользовательской процедуре осуществляется дважды: первый раз — для расчета НОД суммы и модуля разности чисел a и b, второй раз — для расчета НОД числа, полученного от первого обращения к процедуре и произведения чисел a и b.

Пользовательская процедура имеет три формальных параметра: параметры-значения — m и n, а также параметр-переменную — k. Формальному параметру k соответствует фактический параметр с, с помощью которого выводится на печать искомый результат.

Задача 3. Решить задачу 11.2.2, используя для нахождения НОД пользовательскую функцию. Программа на языке Паскаль для решения этой задачи имеет следующий вид:

function evklid(m,n:integer) : integer; begin

while m<>n do if m>n then m:=m-n

evklid:=m; end; begin read(a,b);

writeln(‘a=’,a,’ b=’,b); c:=evklid(evklid(a+b,abs(a-b)),a*b); writeln(‘нод=’,c);

Для вызова пользовательской функции применяется оператор присваивания, в котором в качестве операнда используется обращение к функции, содержащее имя функции и список фактических параметров. В соответствии с правилами приоритета первым выполняется обращение evklid(a+b,abs(a-b)). Для возвращения результата решения пользовательская функция должна содержать оператор присваивания, у которого в левой части должно стоять имя функции, а в правой — возвращаемый в основную программу результат.

Задача 1. Известно рекурсивное определение факториала:

fi, если n = 0 или n = 1, n =\

Здесь n — неотрицательно. Записать эту функцию на языке Паскаль. Решение. В первой строке определения явно указано, как вычислить факториал, если аргумент равен нулю или единице. В любом другом случае для вычисления n! необходимо вычислить предыдущее значение (п-1)! и умножить его на n. Уменьшающееся значение гарантирует, что, в конце концов, возникнет необходимость найти 1! или 0!, которые вычисляются непосредственно. program task5;

function fact(i: integer) :integer; begin if (i=1) or (i=0) then fact:=1 else fact:=fact(i-1)*i;

begin write(‘Введите нужное значение n ‘); readln(n);

writeln(‘Факториал ‘,n,’ равен ‘,fact(n)); end.

Вспомним, что на время выполнения вспомогательного алгоритма основной алгоритм приостанавливается. При вызове новой копии рекурсивного алгоритма вновь выделяется место для всех переменных, объявляемых в нем, причем переменные других копий будут недоступны. При удалении копии рекурсивного алгоритма из памяти удаляются и все его переменные. Активизируется предыдущая копия рекурсивного алгоритма, становятся доступными ее переменные. Пусть необходимо вычислить 4!. Основной алгоритм: вводится n=4, вызов fact(4). Основной алгоритм

приостанавливается, вызывается и работает fact(4): 4<>1 и 4<>0, поэтому fact:=fact(3)*4. Работа функции приостанавливается, вызывается и работает fact(3): 3<>1 и 3<>0, поэтому fact:=fact(2)*3. В данный момент в памяти компьютера две копии функции fact. Вызывается и работает fact(2): 2<>1 и 2<>0, поэтому fact:=fact(1)*2. В памяти компьютера уже три копии функции fact и вызывается четвертая. Вызывается и работает fact(1): 1=1, поэтому fact(1)=1. Работа этой функции завершена, продолжает работу fact(2). fact(2):=fact(1)*2=1*2=2. Работа этой функции также завершена, и продолжает работу функция fact(3). fact(3):=fact(2)*3=2*3=6. Завершается работа и этой функции, и продолжает работу функция fact(4). fact(4):=fact(3)*4=6*4=24. Сейчас управление передается в основную программу и печатается ответ: «Факториал 4 равен 24».

14. Тип данных множество

Задача 1. Задать множество целых чисел от заданного числа до числа в три раза большего, чем заданное.

Решение. Используем описание множеств на языке Паскаль и операторы для работы с множествами.

Если количество элементов n в множестве известно заранее, то задача решается

type setnum=set of byte; const mn:setnum=[n..3*n];

. Если начальное значение задается пользователем, то задача решается так: type setnum=set of byte; var mn:setnum; n,i:byte;

begin write(‘задайте первый элемент множества ‘);

else write(‘заданное количество элементов не поместится в множестве ‘); end.

Задача 2. Вывести элементы множества, содержащего прописные и строчные буквы латинского алфавита, на экран.

Решение. В цикле проверим вхождение всех элементов базового типа и выводим те, которые входят в множество. var zn:set of ‘A’..’z’; i:char;

begin for i:=’A’ to ‘Z’ do

if i in zn then write(i,’ ‘); for i:=’a’ to ‘z’ do

if i in zn then write(i,’ ‘);

Задача 3. Написать программу, которая в заданном слове, состоящем из строчных букв, определяет составляющие его буквы, глухие и звонкие согласные, затем все согласные и все гласные буквы. Решение.

type setchar = set of char;

ALF:string=’абвгдеёжзийклмнопрстуфхцчшщъыьэюя’; var s:string;

for i:=1 to length(ALF) do if ALF[i] in mn then write(ALF[i],’ ‘); writeln; end;

begin write(‘Введите русское слово ‘); readln(s);

gla:=buk-(sog+[V,V]); print(‘слово состоит из букв; ‘,buk); print(‘гласные буквы: ‘,gla); print(‘согласные буквы: ‘,sog); print(‘глухие согласные: ‘,mgl); print(‘звонкие согласные; ‘,mzv); end.

Задача 4. Заданы два слова. Определить буквы, которые не являются общими для обоих слов.

Решение. Образуем множества, содержащие буквы первого и второго слова. Затем найдем разности первого и второго, второго и первого множеств. Их объединение даст ответ.

type setchar=set of char;

begin for i:=1 to length(ALF) do

if ALF[i] in mn then write(ALF[i],’ ‘); writeln; end;

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

begin write(‘Введите два русских слова, разделив их нажатием клавиши Enter ‘); readln(s 1);readln(s2); ms1:=[]; ms2:=[]; for i:=1 to length(sl) do ms1:=ms1+[s1[i]]; < множество букв второго слова>for i:=1 to length(s2) do ms2:=ms2+[s2[i]]; g1:=ms1-ms2; g2:=ms2-ms1; print(g1+g2); end.

Задача 5. Написать программу для нахождения простых чисел с помощью «решета Эратосфена». Решение.

1. Поместим все числа между 2 и n (n<=255) в решето.

2. Выберем из решета наименьшее из чисел.

3. Поместим это число среди простых.

4. Переберем и вынем из решета все числа, кратные данному.

5. Если решето не пустое, то повторим шаги 2 — 5. const n=255; var interval,

begin interval:=[2..n]; prost:=[]; next:=2;

repeat while not (next in interval) do next:=succ(next); prost: =pro st+[next]; c:=2*next-1; j:=next; while j

begin interval:=interval-[j]; j:=j=c; end; until interval=[]; end.

Задача 6. Натуральные числа вводятся с клавиатуры до тех пор, пока не будет введено число нуль (признак окончания ввода). Написать программу для определения цифры, которая встречается во всех введенных числах.

Решение. Для каждого введенного числа образуем множество его цифр и найдем его пересечение с множествами цифр других чисел. Для первого числа не существует множества цифр предыдущих чисел, поэтому в ответе следует записать все множество цифр первого числа. Эта ситуация контролируется в программе с помощью переменной — признака р.

if p=1 then begin s:=s1;p:=0; end else s:=s*s1; read(a);

for a:=0 to 9 do if a in s then write(a,’ ‘);

15. Тип данных запись

Задача 1. Создайте массив автовладельцев. Для каждого автовладельца известен номер, марка автомобиля, фамилия и адрес. Нужно подсчитать количество владельцев автомобиля определенной марки и вывести все сведения о них.

Решение. Сведения об автовладельцах представим массивом записей. Исходные данные вводятся с клавиатуры. Работа с массивом записей аналогична работе с одномерным массивом.

writeln(‘Введите ‘,n,’ автовладельцев’); for i:=1 to n do begin v[i].nomer:=i;

writeln(‘автовладелец номер ‘,v[i].nomer); write(‘Фамилия? ‘);readln(v[i].fio); write(‘марка ? ‘);readln(v[i].marka); write(‘адрес? ‘);readln(v[i].adres);

write(‘Какая марка вас интересует? ‘);

for i:=1 to n do if v[i].marka=s

then begin with v[i] do writeln(nomer,’ ‘,marka,’ ‘,fio,’ ‘,adres); k:=k+1;

write(‘Количество владельцев марки ‘,s,’=’,k);

Таким образом, представлены методики решения по пяти из девятнадцати выделенных классов задач:

11. Данные типа string.

12. Процедуры и функции.

14. Тип данных множество.

15. Тип данных запись.

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

17. Организация работы с модулями.

1. Аляев Ю.А. Алгоритмизация и языки программирования Pascal, C++, Visual Basic / Ю.А. Аляев, О.А. Козлов. М.: Финансы и статистика, 2002, 2004, 2007. 320 с.

2. Аляев Ю.А. Практикум по алгоритмизации и программированию на языке Паскаль / Ю.А. Аляев, В.П. Гладков, О.А. Козлов. М.: Финансы и статистика, 2004, 2007. 528 с.

3. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (1-3) // Образовательные ресурсы и технологии. 2015’1(9). С. 3-14. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_1_3-14.pdf

4. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (4-5) // Образовательные ресурсы и технологии. 2015’2(10). С. 3-16. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_2_3 — 16.pdf

5. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (6-7) // Образовательные ресурсы и технологии. 2015’3(11). С. 3-20. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_003_020.pdf

6. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (8-10) // Образовательные ресурсы и технологии. 2015’4(12). С. 26-43. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_4_026-043.pdf

Methods of the quick education to programming on base of the study of the classes of the problems (11-15)

Yuri Alexandrovich Alyaev, assistant professor, assistant professor of the pulpit of software of the computing machinery and automated systems, Perm military institute of internal troops of the MIA of Russia,

Is offered methods of the quick education to programming on base of the study of the classes of the problems, designed and using in practice in process of the education to programming student high school.

The Keywords: algorithm, program, programming language Pascal, array, procedures and functions, recursion, set, record

Почему массивы начинаются с нуля

Самое очевидное объяснение: индекс — это смещение относительно начала массива. Так элементы массива легче адресовать в памяти.

Проверим это на C.

#include int main() < int data[3] = ; int i = 0; printf("Array address: %p\n", data); do < printf("Array[%u] = %p\n", i, (void *)(&data[i])); i++; >while(i

Array address: 0x7ffd7c514a6c
Array[0] = 0x7ffd7c514a6c
Array[1] = 0x7ffd7c514a70
Array[2] = 0x7ffd7c514a74

Как первый (нулевой) элемент, так и сам массив находятся по одному и тому же адресу, поскольку 0-й элемент удалён на 0 элементов от начала. Эта связь между указателями и массивами в C настолько тесная, что их даже можно рассматривать вместе.

Однако это ответ на вопрос «зачем», а не «почему». Нумеровать массивы с нуля стали не сразу. Удивительно, но развитие такого простого вопроса не умещается в предложении или абзаце.

Потому что так удобнее

К началу 1960-х годов сформировалось три подхода к организации структуры, которую сегодня мы называем статическим массивом:

Исчисление с 0. Нижняя граница массива начинается с нуля.

Непривычно для обывателя, если это не житель Германии, свыкшийся с нумерацией этажей в зданиях. Последний элемент массива из, скажем, 8 элементов имеет номер 7.

Не всё так однозначно. Единообразия даже у самых первых языков программирования не существовало:

1. Нумерация с нуля: LISP 1.5, APL (допускает выбор при запуске программы).
2. Нумерация с единицы: APL, Бейсик, ранний Фортран.
3. Произвольные границы: Алгол-60, затем Фортран, CPL, SIMULA, CLU, PL/1, Кобол, Паскаль, Алгол-68, JOVIAL.

Конечно, это не самый сильный аргумент. Часто языки снабжались синтаксическим сахаром для нумерации с 1. К примеру, в Алголе массив V[0:3] начинается с 0, а массив V[3] — с 1.

Создатель языка APL Кеннет Айверсон в книге «A Programming Language» объясняет, почему далее по тексту он будет пользоваться нумерацией элементов массива с нуля. При этом язык допускает отсчёт как с единицы, так и с нуля. Айверсон приводит уже описанный выше аргумент о сдвигах в позиционной нумерации.

Тем не менее и в эпоху до C звучали предложения выбирать нумерацию с 0. Логично предположить, что это была историческая неизбежность, до которой оставалось несколько лет.

Потому что парусные регаты мешали вычислениям

В 1967 году Мартин Ричардс впервые реализует компилятор своего детища — BCPL (Basic Combined Programming Language). Этот язык программирования был призван исправить проблемы созданного в начале шестидесятых языка CPL путём отказа от технологий, затрудняющих компиляцию.

Первый компилятор BCPL был написан для операционной системы CTSS машины IBM 7094 Массачусетского технологического института. На тот момент компьютеры — это уже не целые комнаты и электронные лампы, но всё ещё огромные шкафы с транзисторами и консоли управления без экранов. Ресурсов серии 7090 хватило, чтобы запустить американца в космос. Но мощность измерялась в тысячах машинных слов, микросекундах тактов и килофлопсах, а цена — в миллионах долларов.

В пятидесятых и шестидесятых IBM выдавала институту щедрые скидки на свои научные компьютеры или даже предоставляла их бесплатно. В 1963 году в МТИ поставили IBM 7094. На компьютер уговор был такой: 8 часов в сутки получают специалисты института, 8 часов — другие колледжи и университеты Новой Англии, а третью смену отдавали самой IBM для личных нужд.

На этом особенности не кончались. Несколько раз в год IBM обсчитывала регаты: президент IBM соревновался в заплыве на больших яхтах в проливе Лонг-Айленд, и каждое из судов получало очки гандикапа по специальной сложной формуле. Когда в вычислительный центр приходило задание, операторам полагалось всё бросить и запустить вычисления этих очков.

Машинный зал с установленным компьютером IBM 7094 в Колумбийском университете США. Фотоархив

Вообще, и без этого был шанс не получить результат вычислений. Изначально 7094 работал в режиме пакетной обработки. Вспомогательная система на IBM 1401 загружала пакет задач с перфокарт на ленту, а затем запускала задачи одну за другой и записывала результаты для последующей печати. Для каждой задачи приводилась оценка времени. Если задача выходила за пределы отпущенного, её принудительно прерывали.

В итоге компиляция в BCPL была оптимизирована по максимуму. То есть и указатели на элементы массива должны максимально близко походить на машинный код, без необходимости вычитать единицу при указании на элемент массива. Хотя во время выполнения программы не играет роли схема организации массивов, нумерация с нуля могла появиться для оптимизации времени компиляции.

Впрочем, конкретно эта версия — лишь гипотеза Майка Хойе. Ей нет никаких подтверждений от собствено Ричардса или хотя бы упоминаний в литературе. Мартин Ричардс в переписке с Хойе лишь приводит общие соображения о том, что он хотел достичь близости к машинному коду, поэтому указатель p и p + 0 — это одна и та же переменная. Ни на какие яхты Ричардс не жалуется.

К тому же на момент появления первого компилятора BCPL уже была готова операционка Compatible Time-Sharing System. В ней на одной машине с разделением времени компьютер выполняет одну задачу за один раз, но с оптимизацией ввода и вывода, чтобы паузы одного пользователя заполнялись работой других. Это уже не былая пакетная обработка задач.

Точно известно, что в дальнейшем BCPL значительно повлиял на все современные языки программирования.

В 1969 году Кен Томпсон урезал функциональность BCPL до языка B. В дальнейшем, для развития операционной системы Unix, Деннис Ритчи улучшил B добавлением функций PDP-11, в результате чего и получился C. Полвека спустя список языков, на которые оказал влияние C, занимает в «Википедии» целую страницу.

В языке BCPL v!5 и 5!v совпадают, поскольку являются указателем на !(v+5) или !(5+v) . Аналогично в C v[5] эквивалентно 5[v] .

Потому что так предложил Дейкстра

В 1982 году Эдсгер Дейкстра опубликовал статью «Почему нумерация должна начинаться с нуля». В ней он низверг как нумерацию с единицы, так и произвольные границы индексов. Очевидно, что Дейкстра — не человек, который легко поддаётся влиянию C, но также он раскритиковал Алгол-60, своё собственное детище, и Паскаль.

Известно, что Дейкстра ближе к концу жизни всё больше писал от руки, а не набирал тексты на машинке. Архив рукописей Эдсгера Вибе Дейкстры

Если необходимо записать интервал натуральных чисел 2, 3, …, 12 без опухоли из точек, возможны четыре варианта:

Затем автор замечает, что для нижней границы предпочтителен знак «⩽», поскольку наименьшее натуральное число существует. В противном случае, если последовательность начинается с наименьшего натурального числа, нижняя граница не будет натуральным числом.

Затем статья делает вывод, что из соображений простоты для последовательности из N членов предпочтительнее диапазон 0 ⩽ i < N , а не 1 ⩽ i < N+1 .

Куда менее известный документ — это полушуточная техническая заметка от 1 апреля 1980 года IEN 137 под названием «О священных войнах и призыв к миру» [On Holy Wars and a Plea for Peace].

В заметке Дэнни Коэн приводит интересный аргумент: в системе счисления с основанием b при отсчёте с нуля первые b ^ N неотрицательных чисел представляются ровно N цифрами. Например, если речь про двоичную запись, то 2 ^ 3 = 8 , и восьмой элемент массива будет иметь номер 111₂, а не 1000₂. Понятно, что с такими преобразованиями легко бы мог справиться компилятор.

Потому что так более элегантно

Это объяснение может раздражать субъективностью. Соображения о красоте у каждого свои и совпадать не обязаны. Но авторы языков программирования — тоже люди со своими предпочтениями.

В конце восьмидесятых Гвидо ван Россум при создании Python как учёл свой предыдущий опыт с языком ABC, так и задумал привлечь аудиторию хакеров от мира Unix и C.

С 1983 года Гвидо работал в Центре математики и информатики в Амстердаме над реализацией языка ABC. Проект ставил целью создать язык программирования, пригодный для обычных людей, но не настолько ужасно реализованный, как Бейсик. Нумерация массивов в ABC начиналась с единицы. Такой же схемы придерживались другие знакомые Россуму языки — Алгол, Фортран и Паскаль.

Однако в вышедшем в 1991 году Python нумерация начинается с нуля, а не единицы. Получилось так в результате долгих размышлений.

Одна из причин — слайсы. Чаще всего при создании слайса используются операции «получить первые n элементов» и «начиная с i, получить следующие n элементов». При этом первый случай эквивалентен i == первый индекс . Гвидо посчитал, что лучше, если обе операции возможны без лишней головной боли в виде коррекции +1 и −1.

Если первый элемент имеет номер 1, то возможно указывать первый элемент и число элементов, которые нужно получить. Россум уже был знаком с подобным по ABC и вполне мог бы положиться на этот опыт.

Тем не менее автора Python очаровал синтаксис слайсов полуоткрытого интервала, если нумерация начинается с нуля: a[:n] (или a[0:n] ) и a[i:i+n] . К примеру, строку a легко разбить на три части a[:i] , a[i:j] и a[j:] .

Заметим, что в воспоминаниях Гвидо не приводит ни призывы гениев информатики, ни практики других языков, ни принципы, заложенные мастодонтами компьютерных вычислений шестидесятых. Зато слово «элегантность» в пяти абзацах его объяснения встречается 3 раза.

Почему же массивы начинаются с нуля?

Так исторически сложилось.

Запишите на языке паскаль массива в котором 111 элементов

Дан массив, состоящий из целых чисел. Нумерация элементов начинается с 0. Напишите программу, которая выведет элементы массива, номера которых четны (0, 2, 4. ).

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

Необходимо вывести все элементы массива с чётными номерами.

Входные данные

6 4 5 3 4 2 3

Выходные данные

4 3 2

ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Дан массив, состоящий из целых чисел. Напишите программу, которая выводит те элементы массива, которые являются чётными числами.

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

Необходимо вывести все четные элементы массива (то есть те элементы, которые являются четными числами).

Входные данные

5 1 2 3 4 5

Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

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

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 10000\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

Необходимо единственное число — количество положительных элементов в массиве.

Входные данные

5 1 2 3 -1 -4

Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

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

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 10000\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

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

Входные данные

5 1 2 3 4 5

Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Дан массив, состоящий из целых чисел. Напишите программу, которая определяет, есть ли в массиве пара соседних элементов с одинаковыми знаками.

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 10000\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел не равных 0.

Выходные данные

Необходимо вывести слово YES, если существует пара соседних элементов с одинаковыми знаками. В противном случае следует вывести слово NO.

Входные данные

5 1 -3 4 -2 1

Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

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

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

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

Входные данные

5 1 2 3 4 5

Выходные данные
Входные данные

5 1 5 1 5 1

Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Напишите программу, которая переставляет элементы массива в обратном порядке без использования дополнительного массива. Программа должна считать массив, поменять порядок его элементов, затем вывести результат (просто вывести элементы массива в обратном порядке – недостаточно!)

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 35\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

Необходимо вывести массив, полученный после перестановки элементов.

Входные данные

6 4 5 3 4 2 3

Выходные данные

3 2 4 3 5 4

ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Напишите программу, которая переставляет соседние элементы массива (1-й элемент поменять с 2-м, 3-й с 4-м и т.д. Если элементов нечетное число, то последний элемент остается на своем месте).

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 35\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

Необходимо вывести массив, полученный после перестановки элементов.

Входные данные

6 4 5 3 4 2 3

Выходные данные

5 4 4 3 3 2

ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Напишите программу, которая циклически сдвигает элементы массива вправо (например, если элементы нумеруются, начиная с нуля, то 0-й элемент становится 1-м, 1-й становится 2-м, . последний становится 0-м, то есть массив превращается в массив ).

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 35\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

Необходимо вывести массив, полученный после сдвига элементов.

Входные данные

6 4 5 3 4 2 3

Выходные данные

3 4 5 3 4 2

ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Вводится массив, состоящий из целых чисел. Найти наибольшее среди них.

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 35\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.

Выходные данные

Необходимо вывести значение наибольшего элемента в массиве.

Входные данные

3 1 2 3

Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

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

Входные данные

Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел, находящихся в пределах от \(-2^\) до \(2^-1\)

Выходные данные

Необходимо вывести единственное число — количество различных чисел в массиве.

Входные данные

5 1 1 1 1 1

Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

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

Входные данные

Задан единственный символ C.

Выходные данные

Необходимо вывести получившийся символ.

Входные данные
Выходные данные
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Входные данные

В единственной строке входных данных записано натуральное число n (1≤n ≤ 45).

Выходные данные

Вывести одно число F_n

Входные данные
Выходные данные
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Переведите натуральное число из двоичной системы в десятичную (в двоичном числе не более 10 цифр).

Входные данные

Вводится натуральное число, записанное в двоичной системе.

Выходные данные

Выведите число, записанное в десятичной системе.

Входные данные

1001

Выходные данные
Входные данные
Выходные данные
Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2008, Задача B ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

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

Грабители обнаружили, что можно по одному вытаскивать гранитные блоки, находящиеся с краю (как слева, так и справа). Они хотят вытащить из-под лавочки как можно больше блоков так, чтобы она при этом не упала (передвигать оставшиеся блоки нельзя). Определите, какие блоки они должны оставить.

Входные данные

В первой строке входных данных содержатся два числа: L — длина лавочки и K — количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.

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

Выходные данные

Требуется перечислить ножки, которые грабителям нужно оставить. Для каждой ножки нужно выдать ее положение, как оно задано во входных данных. Ножки следует перечислять слева направо, в том порядке, в котором они встречаются во входных данных.

Пример

Входные данные	Выходные данные
5 2 0 2	2
13 4 1 4 8 11	4 8
14 6 1 6 8 11 12 13	6 8

Второй пример соответствует лавочке на рисунке.

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2006, Задача B ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

Входные данные

Сначала вводится число \(N\) — количество элементов исходной последовательности (1 ≤ \(N\) ≤ 100). Далее идут \(N\) чисел — элементы этой последовательности, натуральные числа от 1 до 9.

Выходные данные

Выведите сначала число \(M\) — минимальное количество элементов, которое надо дописать к последовательности, а потом \(M\) чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.

Входные данные

9 1 2 3 4 5 4 3 2 1

Выходные данные
Входные данные

5 1 2 1 2 2

Выходные данные

3 1 2 1

Входные данные

5 1 2 3 4 5

Выходные данные

4 4 3 2 1

Источники: [ Командные олимпиады, ВКОШП, 2002, Задача G ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes

Требуется сгенерировать перестановку, которая при применении к массиву 1..N возвращает его в исходное состояние за наибольшее количество применений.

Ваня и Петя играют в следующую игру. Ваня пишет на бумаге какую-либо перестановку чисел от 1 до \(N\) (то есть выписывает все числа от 1 до \(N\) в некотором порядке) и расставляет на столе в ряд \(N\) предметов. После этого Петя переставляет предметы в соответствии с Ваниной перестановкой. А именно, Петя выполняет следующие действия: если i-ое число в Ваниной перестановке равно \(a_i\), то Петя ставит предмет, который стоит на i-ом месте, на место с номером \(a_i\).

Обозначим предметы числами от 1 до \(N\). Тогда начальное расположение предметов можно обозначить последовательностью чисел (1, 2, . \(N\)). К примеру, если \(N\) = 5, то начальное расположение предметов есть (1, 2, 3, 4, 5). Пусть Ваня написал перестановку . Это значит, что после перемещения предметов они окажутся расставлены в следующем порядке: (5, 1, 4, 3, 2).

Однако, переставив предметы, Петя не останавливается на достигнутом и вновь переставляет их в соответствии с Ваниной перестановкой. Снова, если i-ое число в Ваниной перестановке равно \(a_i\), то Петя ставит предмет, который стоит на i-ом месте на место с номером \(a_i\). Так, если в приведенном выше примере повторно применить перестановку, предметы окажутся расположены в следующем порядке: (2, 5, 3, 4, 1).

Таким образом, Петя переставляет предметы в соответствии с Ваниной перестановкой, пока их расположение не окажется таким же, как исходное. В нашем примере Пете потребуется сделать еще 4 действия, порядок предметов после каждого из них будет следующим: (1, 2, 4, 3, 5), (5, 1, 3, 4, 2), (2, 5, 4, 3, 1), (1, 2, 3, 4, 5). Всего Пете потребовалось применить перестановку 6 раз.

Добрый Ваня хочет, чтобы Пете пришлось выполнить как можно больше действий. Помогите ему выбрать соответствующую перестановку.

Входные данные

Вводится единственное целое число \(N\) — количество предметов (1

ограничение по памяти на тест
64 megabytes

Есть куб состоящий из единичных кубиков. Заданы наборы кубиков, проткнутые спицей вдоль одной из осей. Требуется подсчитать количество оставшихся кубиков.

Петя склеил из \(N^3\) единичных кубиков большой куб размером \(N\) × \(N\) × \(N\). Устав от этой сложной работы, он отправился спать, а утром, проснувшись, с ужасом обнаружил, что его младший брат Ваня \(K\) раз проткнул куб спицей.

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

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

Входные данные

В первой строке вводятся числа \(N\) и \(K\) (1

Программирование на языке Паскаль Часть II Тема 1. Массивы

• 

2 слайд Массивы
Массив – это группа однотипных элементов, имеющих общее имя, но различные индексы.
Особенности:
все элементы имеют один тип
весь массив имеет одно имя
все элементы расположены в памяти рядом
Примеры:
список учеников в классе
квартиры в доме
школы в городе
данные о температуре воздуха за год

3 слайд Массивы
A
массив
3
15
НОМЕР
элемента массива
(ИНДЕКС)
A[1]
A[2]
A[3]
A[4]
A[5]
ЗНАЧЕНИЕ элемента массива
A[2]
НОМЕР (ИНДЕКС)
элемента массива: 2
ЗНАЧЕНИЕ
элемента массива: 10

4 слайд Объявление массивов
Зачем объявлять?
определить имя массива
определить тип массива
определить число элементов
выделить место в памяти
Массив целых чисел:

Размер через константу:
имя
начальный индекс
конечный индекс
тип
элементов

var A: array[1.. ] of integer;
const N=5;
N
var A : array[ 1 .. 5 ] of integer ;

5 слайд Объявление массивов
Массивы других типов:
Другой диапазон индексов:
Индексы других типов:
var X, Y: array [1..10] of real;
C: array [1..20] of char;
var Q: array [0..9] of real;
C: array [-5..13] of char;
var A: array [‘A’..’Z’] of real;
B: array [False..True] of integer;
.
A[‘C’] := 3.14259*A[‘B’];
B[False] := B[False] + 1;

6 слайд Что неправильно?
var a: array[10..1] of integer;
.
A[5] := 4.5;
[1..10]
var a: array [‘z’..’a’] of integer;
.
A[‘B’] := 15;
A[‘b’]
[‘a’..’z’]
var a: array [0..9] of integer;
.
A[10] := ‘X’;

7 слайд Массивы
Объявление:
Ввод с клавиатуры:
Поэлементные операции:
Вывод на экран:
const N = 5;
var a: array[1..N] of integer;
i: integer;
for i:=1 to N do begin
write(‘a[‘, i, ‘]=’);
read ( a[i] );
end;
a[1] =
a[2] =
a[3] =
a[4] =
a[5] =
5
12
34
56
13
Почему
write?
?
for i:=1 to N do a[i]:=a[i]*2;
writeln(‘Массив A:’);
for i:=1 to N do
write(a[i]:4);
Массив A:
10 24 68 112 26

8 слайд Задания
«4»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех элементов массива.
Пример:
Введите пять чисел:
4 15 3 10 14
среднее арифметическое 9.200
«5»: Ввести c клавиатуры массив из 5 элементов, найти минимальный из них.
Пример:
Введите пять чисел:
4 15 3 10 14
минимальный элемент 3

9 слайд Программирование
на языке Паскаль
Часть II
Тема 2. Максимальный
элемент массива

12 слайд Программа
program qq;
const N = 5;
var a: array [1..N] of integer;
i, iMax: integer;
begin
writeln(‘Исходный массив:’);
for i:=1 to N do begin
a[i] := random(100) + 50;
write(a[i]:4);
end;
iMax := 1; < считаем, что первый – максимальный >
for i:=2 to N do < проверяем все остальные >
if a[i] > a[iMax] then < новый максимальный >
iMax := i; < запомнить i >
writeln;
writeln(‘Максимальный элемент a[‘, iMax, ‘]=’, a[iMax]);
end;
случайные числа в интервале [50,150)
поиск максимального

13 слайд Задания
«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и найти в нем максимальный и минимальный элементы и их номера.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
максимальный a[4]=10
минимальный a[8]=-10
«5»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и найти в нем два максимальных элемента и их номера.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
максимальные a[4]=10, a[7]=8

14 слайд Программирование
на языке Паскаль
Часть II
Тема 3. Обработка массивов

15 слайд Инверсия массива
Задача: переставить элементы массива в обратном порядке.
Алгоритм:
поменять местами A[1] и A[N], A[2] и A[N-1], …
Псевдокод:
for i:=1 to N do
< поменять местами A[i] и A[N+1-i] >
сумма индексов N+1
Что неверно?
?
N div 2
do

16 слайд Как переставить элементы?
2
3
1
Задача: поменять местами содержимое двух чашек.
Задача: поменять местами содержимое двух ячеек памяти.
4
6
?
4
6
4
x
y
c
c := x;
x := y;
y := c;
x := y;
y := x;
3
2
1
Можно ли обойтись без c?
?

18 слайд Задания
«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить инверсию отдельно для 1-ой и 2-ой половин массива.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
Результат:
-4 10 3 -5 4 0 1 -10 8 -6
«5»: Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить инверсию для каждой трети массива.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0 5 7
Результат:
10 3 -5 4 -10 8 -6 -4 7 5 0 1

19 слайд Циклический сдвиг
Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится на место последнего.
Алгоритм:
A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N];
Цикл:
for i:=1 to N-1 do
A[i]:=A[i+1];
Что неверно?
?
почему не N?

21 слайд Задания
«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить циклический сдвиг ВПРАВО.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
Результат:
0 4 -5 3 10 -4 -6 8 -10 1
«5»: Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить циклический сдвиг ВПРАВО на 4 элемента.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0 5 7
Результат:
-4 -6 8 -10 1 0 5 7 4 -5 3 10

22 слайд Программирование
на языке Паскаль
Часть II
Тема 4. Сортировка массивов

23 слайд Сортировка
Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …).
Задача: переставить элементы массива в порядке возрастания.
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод вставки
сложные, но эффективные
«быстрая сортировка» (Quick Sort)
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка
сложность O(N2)
сложность O(N·logN)
время
N
O(N2)
O(N·logN)

24 слайд Метод пузырька
Идея – пузырек воздуха в стакане воды поднимается со дна вверх.
Для массивов – самый маленький («легкий») элемент перемещается вверх («всплывает»).
начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место
1-ый проход
2-ый проход
3-ий проход
Для сортировки массива из N элементов нужен
N-1 проход (достаточно поставить на свои места N-1 элементов).

25 слайд Программа
1-ый проход:
сравниваются пары
A[N-1] и A[N], A[N-2] и A[N-1]
…
A[1] и A[2]
A[j] и A[j+1]
2-ой проход
A[1] уже на своем месте!
!
for j:=N-1 downto 2 do
if A[j] > A[j+1] then begin
c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
end;
2
for j:=N-1 downto 1 do
if A[j] > A[j+1] then begin
c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
end;
1
i-ый проход
for j:=N-1 downto i do
.
i

26 слайд Программа
program qq;
const N = 10;
var A: array[1..N] of integer;
i, j, c: integer;
begin
< заполнить массив >
< вывести исходный массив >
for i:=1 to N-1 do begin
for j:=N-1 downto i do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
end;
end;
< вывести полученный массив >
end;
Почему цикл по i до N-1?
?
i
элементы выше A[i] уже поставлены

27 слайд Метод пузырька с флажком
Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны.
Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход.
repeat
flag := False; < сбросить флаг >
for j:=N-1 downto 1 do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
flag := True; < поднять флаг >
end;
until not flag; < выход при flag=True >
flag := False;
flag := True;
not flag;
var flag: boolean;
Как улучшить?
?

28 слайд Метод пузырька с флажком
i := 0;
repeat
i := i + 1;
flag := False; < сбросить флаг >
for j:=N-1 downto 1 do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
flag := True; < поднять флаг >
end;
until not flag; < выход при flag=True >
i := 0;
i
i := i + 1;

29 слайд Метод вставки
Идея:
найти минимальный элемент и поставить на первое место (поменять местами с A[1])
из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2]), и т.д.

30 слайд Метод вставки
for i := 1 to N-1 do begin
nMin = i ;
for j:= i+1 to N do
if A[j] < A[nMin] then nMin:=j;
if nMin <> i then begin
c:=A[i];
A[i]:=A[nMin];
A[nMin]:=c;
end;
end;
N-1
N
нужно N-1 проходов
поиск минимального от A[i] до A[N]
если нужно, переставляем
Можно ли убрать if?
?
i+1
i

31 слайд Задания
«4»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
30 11 41 32 13 14 25 76 97 58
«5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
13 14 25 30 76 97 58 41 32 11

32 слайд Программирование
на языке Паскаль
Часть II
Тема 5. Поиск в массиве

33 слайд Поиск в массиве
Задача – найти в массиве элемент, равный X, или установить, что его нет.
Решение: для произвольного массива: линейный поиск (перебор)
недостаток: низкая скорость
Как ускорить? – заранее подготовить массив для поиска
как именно подготовить?
как использовать «подготовленный массив»?

34 слайд Линейный поиск
nX := 0;
for i:=1 to N do
if A[i] = X then begin
nX := i;
break;
end;
nX := 0; < пока не нашли . >
for i:=1 to N do < цикл по всем элементам >
if A[i] = X then < если нашли, то . >
nX := i; < . запомнили номер>
if nX < 1 then writeln('Не нашли. ')
else writeln(‘A[‘, nX, ‘]=’, X);
nX – номер нужного
элемента в массиве
Что плохо?
?
Улучшение: после того, как нашли X, выходим из цикла.
nX := 0; i := 1;
while i if A[i] = X then begin
nX := i; i := N;
end;
i := i + 1;
end;
break;
i := N;

35 слайд Двоичный поиск
X = 7
X < 8
8
4
X > 4
6
X > 6
Выбрать средний элемент A[c] и сравнить с X.
Если X = A[c], нашли (выход).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.

37 слайд Сравнение методов поиска

38 слайд Задания
«4»: Написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск.

«5»: Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.

39 слайд Программирование
на языке Паскаль
Часть II
Тема 6. Символьные строки

40 слайд Чем плох массив символов?
var B: array[1..N] of char;
Это массив символов:
каждый символ – отдельный объект;
массив имеет длину N, которая задана при объявлении
Что нужно:
обрабатывать последовательность символов как единое целое
строка должна иметь переменную длину

41 слайд Символьные строки
длина строки
рабочая часть
s[1]
s[2]
s[3]
s[4]
var s: string;
var s: string[20];
Длина строки:
n := length ( s );
var i: integer;
В Delphi это ограничение снято!
!

42 слайд Символьные строки
Задача: ввести строку с клавиатуры и заменить все буквы «а» на буквы «б».
program qq;
var s: string;
i: integer;
begin
writeln(‘Введите строку’);
readln(s);
for i:=1 to Length(s) do
if s[i] = ‘а’ then s[i] := ‘б’;
writeln(s);
end.
readln(s);
writeln(s);
Length(s)
ввод строки
длина строки
вывод строки

43 слайд Задания
«4»: Ввести символьную строку и заменить все буквы «а» на буквы «б» и наоборот, как заглавные, так и строчные.
Пример:
Введите строку:
ааббссААББСС
Результат:
ббаассББААСС
«5»: Ввести символьную строку и проверить, является ли она палиндромом (палиндром читается одинаково в обоих направлениях).
Пример: Пример:
Введите строку: Введите строку:
АБВГДЕ КАЗАК
Результат: Результат:
Не палиндром. Палиндром.

44 слайд Операции со строками
Объединение: добавить одну строку в конец другой.
Запись нового значения:
var s, s1, s2: string;
s := ‘Вася’;
s1 := ‘Привет’;
s2 := ‘Вася’;
s := s1 + ‘, ‘ + s2 + ‘!’;
‘Привет, Вася!’
Подстрока: выделить часть строки в другую строку.
s := ‘123456789’;

s1 := Copy ( s, 3, 6 );
s2 := Copy ( s1, 2, 3 );
‘345678’
‘456’
с 3-его символа
6 штук

45 слайд Удаление и вставка
Удаление части строки:
Вставка в строку:
s := ‘123456789’;
Delete ( s, 3, 6 );
с 3-его символа
6 штук
строка
меняется!
‘123456789’
‘129’
s := ‘123456789’;
Insert ( ‘ABC’, s, 3 );
Insert ( ‘Q’, s, 5 );
куда вставляем
что вставляем
начиная с 3-его символа
’12ABC3456789′
’12ABQC3456789′

46 слайд Поиск в строке
Поиск в строке:
s := ‘Здесь был Вася.’;
n := Pos ( ‘е’, s );
if n > 0 then
writeln(‘Буква е – это s[‘, n, ‘]’)
else writeln(‘Не нашли’);
n := Pos ( ‘Вася’, s );
s1 := Copy ( s, n, 4 );
var n: integer;
s[3]
3
n = 11
Особенности:
функция возвращает номер символа, с которого начинается образец в строке
если слова нет, возвращается 0
поиск с начала (находится первое слово)

47 слайд Примеры
s := ‘Вася Петя Митя’;
n := Pos ( ‘Петя’, s );
Delete ( s, n, 4 );
Insert ( ‘Лена’, s, n );
‘Вася Лена Митя’
s := ‘Вася Петя Митя’;
n := length ( s );
s1 := Copy ( s, 1, 4 );
s2 := Copy ( s, 11, 4 );
s3 := Copy ( s, 6, 4 );
s := s3 + s1 + s2;
n := length ( s );
‘Вася Митя’
14
‘Вася’
‘Митя’
‘Петя’
‘ПетяВасяМитя’
12
6

48 слайд Пример решения задачи
Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы».
Пример:
Введите имя, фамилию и отчество:
Василий Алибабаевич Хрюндиков
Результат:
Хрюндиков В.А.
Алгоритм:
найти первый пробел и выделить имя
удалить имя с пробелом из основной строки
найти первый пробел и выделить отчество
удалить отчество с пробелом из основной строки
«сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы…

49 слайд Программа
program qq;
var s, name, otch: string;
n: integer;
begin
writeln(‘Введите имя, отчество и фамилию’);
readln(s);
n := Pos(‘ ‘, s);
name := Copy(s, 1, n-1); < вырезать имя >
Delete(s, 1, n);
n := Pos(‘ ‘, s);
otch := Copy(s, 1, n-1); < вырезать отчество >
Delete(s, 1, n); < осталась фамилия >
s := s + ‘ ‘ + name[1] + ‘.’ + otch[1] + ‘.’;
writeln(s);
end.

50 слайд Задания
«4»: Ввести имя файла (возможно, без расширения) и изменить его расширение на «.exe».
Пример:
Введите имя файла: Введите имя файла:
qqq qqq.com
Результат: Результат:
qqq.exe qqq.exe
«5»: Ввести путь к файлу и «разобрать» его, выводя каждую вложенную папку с новой строки
Пример:
Введите путь к файлу:
C:\Мои документы\10-Б\Вася\qq.exe
Результат:
C:
Мои документы
10-Б
Вася
qq.exe

51 слайд Программирование
на языке Паскаль
Часть II
Тема 7. Рекурсивный перебор

52 слайд Рекурсивный перебор
Задача: Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Вывести на экран все слова из К букв, которые можно составить в этом языке, и подсчитать их количество. Число K вводится с клавиатуры.
1
K
в каждой ячейке может быть любая из 4-х букв
4 варианта
4 варианта
4 варианта
4 варианта
Количество вариантов:

53 слайд Рекурсивный перебор
1
K
Рекурсия: Решения задачи для слов из К букв сводится к 4-м задачам для слов из K-1 букв.
1
K
1
K
1
K
перебрать все варианты
перебрать все варианты
перебрать все варианты
перебрать все варианты

54 слайд Процедура
procedure Rec(p: integer);
begin
if p > K then begin
writeln(s);
count := count+1;
end
else begin
s[p]:=’Ы’; Rec ( p+1 );
s[p]:=’Ц’; Rec ( p+1 );
s[p]:=’Щ’; Rec ( p+1 );
s[p]:=’О’; Rec ( p+1 );
end;
end;
1
K
p
Глобальные переменные:
var s: string;
count, K: integer;
s
p+1
рекурсивные вызовы
А если букв много?
?
окончание рекурсии

55 слайд Процедура
procedure Rec(p: integer);
const letters = ‘ЫЦЩО’;
var i: integer;
begin
if p > k then begin
writeln(s);
count := count+1;
end
else begin
for i:=1 to length(letters) do begin
s[p] := letters[i];
Rec(p+1);
end;
end;
end;
const letters = ‘ЫЦЩО’;
for i:=1 to length(letters) do begin
s[p] := letters[i];
Rec(p+1);
end;
все буквы
цикл по всем буквам
локальная переменная

56 слайд Программа
program qq;
var s: string;
K, i, count: integer;
begin
writeln(‘Введите длину слов:’);
read ( K );
s := »;
for i:=1 to K do s := s + ‘ ‘;
count := 0;
Rec ( 1 );
writeln(‘Всего ‘, count, ‘ слов’);
end.
procedure Rec(p: integer);
.
end;
процедура
s := »;
for i:=1 to K do s := s + ‘ ‘;
строка из K пробелов
глобальные переменные

57 слайд Задания
Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Число K вводится с клавиатуры.
«4»: Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество.
«5»: Вывести на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, ЫЩЩО), и подсчитать их количество.

58 слайд Программирование
на языке Паскаль
Часть II
Тема 8. Матрицы

59 слайд Матрицы
Задача: запомнить положение фигур на шахматной доске.
1
2
3
4
5
6
c6
A[6,3]

60 слайд Матрицы
Матрица – это прямоугольная таблица чисел.
Матрица – это массив, в котором каждый элемент имеет два индекса (номер строки и номер столбца).
A
строка 2
столбец 3
ячейка A[3,4]

61 слайд Матрицы
Объявление:
const N = 3;
M = 4;
var A: array[1..N,1..M] of integer;
B: array[-3..0,-8..M] of integer;
Q: array[‘a’..’d’,False..True] of real;
Ввод с клавиатуры:
for i:=1 to N do
for j:=1 to M do begin
write(‘A[‘,i,’,’,j,’]=’);
read ( A[i,j] );
end;
Если переставить циклы?
?
A[1,1]=
25
A[1,2]=
14
A[1,3]=
14
.
A[3,4]=
54
i
j
for j:=1 to M do
for i:=1 to N do begin

62 слайд Матрицы
Заполнение случайными числами
for i:=1 to N do
for j:=1 to M do
A[i,j] := random(25) — 10;
Какой интервал?
?
цикл по строкам
цикл по столбцам
Вывод на экран
for i:=1 to N do begin
for j:=1 to M do
write ( A[i,j]:5 );
writeln;
end;
в той же строке
перейти на новую строку
вывод строки
Если переставить циклы?
?

63 слайд Обработка всех элементов матрицы
Задача: заполнить матрицу из 3 строк и 4 столбцов случайными числами и вывести ее на экран. Найти сумму элементов матрицы.
program qq;
const N = 3; M = 4;
var A: array[1..N,1..M] of integer;
i, j, S: integer;
begin
. < заполнение матрицы и вывод на экран>
S := 0;
for i:=1 to N do
for j:=1 to M do
S := S + A[i,j];
writeln(‘Сумма элементов матрицы ‘, S);
end;

64 слайд Задания
Заполнить матрицу из 8 строк и 5 столбцов случайными числами в интервале [-10,10] и вывести ее на экран.
«4»: Найти минимальный и максимальный элементы в матрице их номера. Формат вывода:
Минимальный элемент A[3,4]=-6
Максимальный элемент A[2,2]=10
«5»: Вывести на экран строку, сумма элементов которой максимальна. Формат вывода:
Строка 2: 3 5 8 9 8

65 слайд Операции с матрицами
Задача 1. Вывести на экран главную диагональ квадратной матрицы из N строк и N столбцов.
A[1,N]
A[2,2]
A[3,3]
A[N,N]
for i:=1 to N do
write ( A[i,i]:5 );
Задача 2. Вывести на экран вторую диагональ.
A[N,1]
A[N-1,2]
A[2,N-1]
for i:=1 to N do
write ( A[i, ]:5 );
N+1-i
сумма номеров строки и столбца N+1
A[1,1]

66 слайд Операции с матрицами
Задача 3. Найти сумму элементов, стоящих на главной диагонали и ниже ее.
Одиночный цикл или вложенный?
?
строка 1: A[1,1]
строка 2: A[2,1]+A[2,2]
.
строка N: A[N,1]+A[N,2]+. +A[N,N]
S := 0;
for i:= 1 to N do
for j:= 1 to i do
S := S + A[i,j];
цикл по всем строкам
складываем нужные элементы строки i

67 слайд Операции с матрицами
Задача 4. Перестановка строк или столбцов. В матрице из N строк и M столбцов переставить 2-ую и 4-ую строки.
2
4
j
A[2,j]
A[4,j]
for j:=1 to M do begin
c := A[2,j];
A[2,j] := A[4,j];
A[4,j] := c;
end;
Задача 5. К третьему столбцу добавить шестой.
for i:=1 to N do
A[i,3] := A[i,3] + A[i,6];

68 слайд Задания
Заполнить матрицу из 7 строк и 7 столбцов случайными числами в интервале [-10,10] и вывести ее на экран. Обнулить элементы, отмеченные зеленым фоном, и вывести полученную матрицу на экран.
«4»: «5»:

69 слайд Программирование
на языке Паскаль
Часть II
Тема 9. Файлы

70 слайд Файлы
Файл – это область на диске, имеющая имя.
Файлы
только текст без оформления,
не содержат управляющих символов (с кодами < 32)
ACSII (1 байт на символ)
UNICODE (2 байта на символ)
*.txt, *.log,
*.htm, *.html
могут содержать любые символы кодовой таблицы
*.doc, *.exe,
*.bmp, *.jpg,
*.wav, *.mp3,
*.avi, *.mpg
Текстовые
Двоичные
Папки
(каталоги)

71 слайд Принцип сэндвича
I этап. открыть файл :
связать переменную f с файлом
открыть файл (сделать его
активным, приготовить к работе)
assign(f, ‘qq.dat’);
reset(f);
rewrite(f);
II этап: работа с файлом
Переменная типа «текстовый файл»:
var f: text;
III этап: закрыть файл
close(f);
read ( f, n ); < ввести значение n >
write ( f, n ); < записать значение n >
writeln ( f, n );

72 слайд Работа с файлами
Особенности:
имя файла упоминается только в команде assign, обращение к файлу идет через файловую переменную
файл, который открывается на чтение, должен существовать
если файл, который открывается на запись, существует, старое содержимое уничтожается
данные записываются в файл в текстовом виде
при завершении программы все файлы закрываются автоматически
после закрытия файла переменную f можно использовать еще раз для работы с другим файлом

73 слайд Последовательный доступ
при открытии файла курсор устанавливается в начало
чтение выполняется с той позиции, где стоит курсор
после чтения курсор сдвигается на первый непрочитанный символ
12 5 45 67 56●
конец файла
(end of file, EOF)
12 5 45 67 56●
assign ( f, ‘qq.dat’ );
reset ( f );
read ( f, x );

74 слайд чтение до конца строки
как вернуться назад?
Последовательный доступ
close ( f );
reset ( f ); < начать с начала >
readln ( f, x );
12 5 45¤ 36 67¤ 56●
конец строки
(end of line, EOL)

75 слайд Пример
Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно. Записать в файл output.txt их сумму.
Алгоритм:
Открыть файл input.txt для чтения.
S := 0;
Если чисел не осталось, перейти к шагу 7.
Прочитать очередное число в переменную x.
S := S + x;
Перейти к шагу 3.
Закрыть файл input.txt.
Открыть файл output.txt для записи.
Записать в файл значение S.
Закрыть файл output.txt.
Можно ли обойтись без массива?
?
цикл с условием
«пока есть данные»

76 слайд Программа
program qq;
var s, x: integer;
f: text;
begin
assign(f, ‘input.txt’);
reset(f);
s := 0;
while not eof(f) do begin
readln(f, x);
s := s + x;
end;
close(f);
assign(f, ‘output.txt’);
rewrite(f);
writeln(f, ‘Сумма чисел ‘, s);
close(f);
end.
f: text;
eof(f)
логическая функция, возвращает True, если достигнут конец файла
запись результата в файл output.txt

77 слайд Задания
В файле input.txt записаны числа, сколько их – неизвестно.
«4»: Найти среднее арифметическое всех чисел и записать его в файл output.txt.
«5»: Найти минимальное и максимальное числа и записать их в файл output.txt.

78 слайд Обработка массивов
Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно, но не более 100. Переставить их в порядке возрастания и записать в файл output.txt.
Проблемы:
для сортировки надо удерживать в памяти все числа сразу (массив);
сколько чисел – неизвестно.
Решение:
выделяем в памяти массив из 100 элементов;
записываем прочитанные числа в массив и считаем их в переменной N;
сортируем первые N элементов массива;
записываем их в файл.
Можно ли обойтись без массива?
?

79 слайд Чтение данных в массив
var A: array[1..100] of integer;
f: text;
function ReadArray: integer;
var i: integer;
begin
assign(f, ‘input.txt’);
reset(f);
i := 0;
while (not eof(f)) and (i < 100) do begin
i := i + 1;
readln(f, A[i]);
end;
close(f);
ReadArray := i;
end;
Глобальные переменные:
Функция: ввод массива, возвращает число элементов
ReadArray := i;
цикл заканчивается, если достигнут конец файла или прочитали 100 чисел

80 слайд Программа
program qq;
var A: array[1..100] of integer;
f: text;
N: integer;
Begin
N := ReadArray;
. < сортировка первых N элементов >
assign(f, ‘output.dat’);
rewrite(f);
for i:=1 to N do
writeln(f, A[i]);
close(f);
end.
function ReadArray: integer;
.
end;
вывод отсортированного массива в файл

81 слайд Задания
В файле input.txt записаны числа (в столбик), известно, что их не более 100.
«4»: Отсортировать массив по убыванию последней цифры и записать его в файл output.txt.
«5»: Отсортировать массив по возрастанию суммы цифр и записать его в файл output.txt.

82 слайд Обработка текстовых данных
Задача: в файле input.txt записаны строки, в которых есть слово-паразит «короче». Очистить текст от мусора и записать в файл output.txt.
Файл input.txt :
Мама, короче, мыла, короче, раму.
Декан, короче, пропил, короче, бутан.
А роза, короче, упала на лапу, короче, Азора.
Каждый, короче, охотник желает, короче, знать, где .
Результат — файл output.txt :
Мама мыла раму.
Декан пропил бутан.
А роза упала на лапу Азора.
Каждый охотник желает знать, где сидит фазан.

83 слайд Обработка текстовых данных
Алгоритм:
Прочитать строку из файла (readln).
Удалить все сочетания «, короче,» (Pos, Delete).
Перейти к шагу 1.
Обработка строки s:
Особенность:
надо одновременно держать открытыми два файла (один в режиме чтения, второй – в режиме записи).

пока не кончились данные
repeat
i := Pos(‘, короче,’, s);
if i <> 0 then Delete(s, i, 9);
until i = 0;
искать «, короче,»
удалить 9 символов

84 слайд Работа с файлами
program qq;
var s: string;
i: integer;
fIn, fOut: text;
begin
assign(fIn, ‘instr.txt’);
reset(fIn);
assign(fOut, ‘outstr.txt’);
rewrite(fOut);
. < обработать файл >
close(fIn);
close(fOut);
end.
fIn, fOut: text;
файловые переменные
открыть файл для чтения
открыть файл
для записи

85 слайд Полный цикл обработки файла
while not eof(fIn) do begin
readln(fIn, s);
writeln(fOut, s);
end;
repeat
i := Pos(‘, короче,’, s);
if i <> 0 then
Delete(s, i, 9);
until i = 0;
пока не достигнут конец файла
обработка строки
запись «очищенной» строки

86 слайд Задания
В файле input.txt записаны строки, сколько их – неизвестно.
«4»: Заменить все слова «короче» на «в общем» и записать результат в файл output.txt.
«5»: Вывести в файл output.txt только те строки, в которых больше 5 слов (слова разделены одним пробелом).

Рабочие листы
к вашим урокам