Занятие 9. Палиндром, или почему Аргентина манит негра?

Сегодня мы рассмотрим еще одну стандартную олимпиадную (уровня районной олимпиады) задачу: проверить, является ли НЕЧТО палиндромом.

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

Во-вторых: почему НЕЧТО. Потому, что в зависимости от того, исследуем мы на палиндромность число, слово или фразу - задача может быть решена по-разному. Давайте рассмотрим все варианты решений.

Итак, вариант 1.

Проверить, является ли число палиндромом.

Идея решения: вводим число a - то, которое будем проверять. Потом, используя цикл While - "пока" с помощью двух меняющихся в ходе выполнения цикла переменных b и c делаем следующую операцию: "откусываем" последнюю цифру от  a и запоминаем её как временное значение c. На следующем витке цикла мы умножаем полученное ранее  c на 10, и прибавляем следующую цифру... И так, пока не получим конечное число c,  которое по сути является числом a, записанным задом наперед.

Затем мы сравниваем a и c, и, если числа равны, выводим сообщение о том, что число - палиндром, или о том, что не палиндром, в противном случае.

Перед вами результат работы программы, реализовавшей эту идею решения:

Введите целое положительное число a=123456

c=6 b=12345

c=65 b=1234

c=654 b=123

c=6543 b=12

c=65432 b=1

c=654321 b=0

654321

Не палиндром

Понятен ли вам принцип? Возникает вопрос, как "откусить" цифру. Тут нам помогут функции div и  mod, о которых вы можете прочесть в Словарике. Коротко:

19:5=3 (остаток 4)

19 div 5 = 3

19 mod 5=4

Попробуйте решить задачу сами. Если не получится - смотрите в Решения к уроку 9.

Рассмотрим 2 вариант этой задачи. 

Проверить, является ли введенное слово палиндромом.

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

Итак:

 Program pal_2;

Var

s: string;  - заводим переменную, в которой запомним наше слово.

i,f: byte; - две технических переменных: счетчик и "переключатель" "ДА" - "НЕТ"

begin 

   write('String: ');  - запросили слово

   readln(s);            - запомнили слово

   f := 0;                   - обнулили переключатель 

for i := 1 to length(s) div 2 do  - ДЛЯ (for) i от 1 до ДЛИНЫ СЛОВА (length(s)) деленного на 2                                                       без остатка (div) ДЕЛАТЬ (do)

if s[i] <> s[length(s)-i+1] then - ЕСЛИ (if) дальше будет изменение в зависимости от номера                                                          шага: 
                                                     на первом шаге ПЕРВАЯ БУКВА (s[i], i=1) не равна                                                                          ПОСЛЕДНЕЙ БУКВЕ (s[длина слова - i, i=1, +1) 
                                                     на втором шаге ВТОРАЯ БУКВА (s[i], i=2) не равна                                                                          ПРЕДПОСЛЕДНЕЙ БУКВЕ (s[длина слова - i, i=2, +1)
                                                     и так до середины слова... 

   begin                                        - делать такой набор действий

        writeln('No palindrome');   - написать "Не палиндром"

        f := 1;                                   - присвоить f значение 1

        break                                   - прервать выполнение программы (ну смысл нам проверять                                                               слово до конца, если уже вторая пара букв, скажем, не                                                                    совпала?)

    end;                                            - конец блока действий, если " все плохо"

 if f = 0 then write('Palindrome');  - если к концу проверки не совпавших пар не нашлось, f                                                                         осталось равным 0, написать сообщение, что слово -                                                                       палиндром.

end.                                                   - конец программы.

Чем интересно это решение?

• Во-первых, мы повторили оператор div, который использовали для сокращения количества шагов в цикле. Слово проверяется за количество шагов, равное половине длины слова. Это позволяет корректно проверять слова, состоящие из нечетного количества букв. Например, слово "КАБАК" будет проверено так: сравним первую и последнюю буквы - это "К", все хорошо. Затем сравним вторую и предпоследнюю. Обе - "А". У буквы "Б" нет пары, но ее наличие не мешает слову быть палиндромом. Эту букву мы вообще не проверяем, потому, что...
• Во-вторых мы познакомились с оператором  length(s) , который считает ДЛИНУ любой переменной типа String, типа, который соответствует значению "много букв". Так вот, мы теперь можем узнать, сколько - много.
• В-третьих посмотрите, почему цикл задан только до середины слова. На примере "КАБАК" - length(s) = 5. length(s) div 2 = 2. Именно по этой причине мы не трогали букву "Б", о чем было сказано в разделе "Во-первых".
• В-четвертых, эта программа будет проверять ЛЮБЫЕ введенные символы. Т.е. ей будет все равно, введете вы реально существующее слово, случайный набор букв, число или смесь букв разных языков и цифр. Если введенная вами строка будет читаться одинаково с обоих концов - вам сообщат, что это - палиндром. 

А теперь - вариант 3.

Проверить, является ли палиндромом фраза.

Первый вариант решения не подходит, так как фраза не может быть типа integer. Второй вариант решения тоже не подходит, так как в фразе, в отличие от слова, есть пробелы между словами. И они крайне редко совпадают по своему положению при чтении с разных концов. Например, фразу "Кабак казак кабак" вариант 2 посчитает палиндромом. А вот фразу "Аргентина манит негра", с которой мы начинали - нет, так как на 6 шаге проверки встретятся буква "Т" из слова "Аргентина" и пробел перед словом "негра"... 

Но мы справимся и с этой задачей.

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

Давайте будем считать, что в наших фразах для проверки будет не более 50 символов вместе с пробелами. 

Опираясь на этот факт мы заведем себе три массива типа CHAR:

• Массив a, в который мы запишем всю введенную нам фразу, в том числе и пробелы, по одному символу в каждой a[ i ].
• Массив b, в котором мы будем сохранять только те символы, которые окажутся НЕ пробелами.
• Массив c, в который мы запишем массив b в обратном порядке.

Если бы мы точно знали, сколько символов в нашей фразе, мы могли бы сразу сократить программу на четверть, но...

Мы введем переменные типа INTEGER:

• i , j - счетчики переменных. Уже при вводе массива a и массива b мы получим разное количество элементов. Ведь с пробелами наша фраза - пример "Аргентина манит негра" займет 21 элемент массива a (столько символов, включая пробелы, в этой фразе), и только 19 элементов массива b - откинем два пробела.
• k - у меня в программе это счетчик итогового количества элементов в массиве b. Если я нахожу "не пробел" в массиве a, я записываю этот символ в массив b и увеличиваю k на 1. Тогда к концу цикла я буду знать, сколько у меня букв без пробелов в фразе.
• d - эту переменную я использую при проверке совпадений массивов b и c. Если находится несовпадение - d увеличивается на 1. В итоге я смогу даже сказать, сколько конкретно несовпадений в фразе, если они есть. В этой программе я не делала сброса при первом же несовпадении, но вы можете это сделать.
• f, g - традиционные переменные типа TEXT для организации работы с файлами ввода и вывода.

С переменными разобрались. Теперь - ход работы:

Открываем файл input.txt и ДО КОНЦА ФАЙЛА (мы же помним про оператор eof?) записываем ВСЕ символы в массив a, а если символ оказывается НЕ ПРОБЕЛОМ, то и в массив b. 

В процессе мы считаем количество элементов, не являющихся пробелами.

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

Затем мы сравниваем элементы массивов b и c. Если пара не совпадает, переменной d присваивается значение d+1.  

Если к концу сравнения d =0, выводим сообщение, что фраза - палиндром. В противном случае - что нет.

Занятие 8. Решаем задачи с матрицей.

Рисование фигурок в матрице - это замечательно. Кстати, один из способов создания компьютерных шрифтов - это прорисовка каждого символа внутри матрицы определенного размера путем расстановки "0" и "1" в определенных позициях. Но не только для этого нам нужны матрицы.

Рассмотрим несколько задач с решениями:

Задача 1. 

Создать двумерный массив из 8 строк по 5 столбцов в каждой из случайных целых чисел из отрезка [10;99]. Вывести массив на экран.

Учимся читать условие задачи и сразу делать выводы.

1. Двумерный массив из 8 строк и 5 столбцов, целые числа. Значит, в разделе переменных необходима запись:

a: array [1..8,1..5] of integer;

2. Числа случайные. Т.е. не мы их вводим с клавиатуры или из файла, а компьютер их сам себе придумывает. Для этой ситуации есть специальная команда:

random; - возвращает случайным образом "0" или "1"

random(n); - возвращает выбранное случайным образом число из промежутка от "0" до "n-1", например  random(100); означает, что будут выбираться случайным образом числа от 0 до 99 включительно.

random(a,b);  - выбирает случайным образом числа из числового промежутка [a, b].

Поскольку нам задан числовой промежуток  [10;99] , то нам нужен будет третий вариант оператора random. 

3. О внешних файлах никто не говорит, значит выводим все, как и сказано в условии, на экран.

Теперь задача:

Program lesson8_1;

Var

a:array[1..8,1..5] of integer;

i,j:integer;

begin

For i:=1 to 8 do begin

For j:=1 to 5 do begin

a[i,j]:=random(10,99);

write (a[i,j]:3);

end;

writeln;

end;

end.

Если у вас есть вопросы по тексту задачи - спросите в комментариях к уроку, я отвечу. Если вопросов нет - ответьте мне, зачем нужен оператор writeln; между двумя операторами end; ?

Мы уже говорили, что научиться программировать можно только самостоятельно написав определенное количество программ. Вперед!

Самостоятельная работа:

1. Создать двумерный массив из 5 строк по 8 столбцов в каждой из случайных целых чисел из отрезка [-99;99]. Вывести массив на экран. После на отдельной строке вывести на экран значение максимального элемента этого массива (его индекс не имеет значения).
2. Cоздать двумерный массив из 7 строк по 4 столбца в каждой из случайных целых чисел из отрезка [-5;5]. Вывести массив на экран. Определить и вывести на экран индекс строки с наибольшим по модулю произведением элементов. Если таких строк несколько, то вывести индекс первой встретившейся из них.
3. Создать двумерный массив из 6 строк по 7 столбцов в каждой из случайных целых чисел из отрезка [0;9]. Вывести массив на экран. Преобразовать массив таким образом, чтобы на первом месте в каждой строке стоял её наибольший элемент. При этом изменять состав массива нельзя, а можно только переставлять элементы в рамках одной строки. Порядок остальных элементов строки не важен (т.е. можно соврешить только одну перестановку, а можно отсортировать по убыванию каждую строку). Вывести преобразованный массив на экран.
4. Для проверки остаточных знаний учеников после летних каникул, учитель младших классов решил начинать каждый урок с того, чтобы задавать каждому ученику пример из таблицы умножения, но в классе 15 человек, а примеры среди них не должны повторяться. В помощь учителю напишите программу, которая будет выводить на экран 15 случайных примеров из таблицы умножения (от 2*2 до 9*9, потому что задания по умножению на 1 и на 10 — слишком просты). При этом среди 15 примеров не должно быть повторяющихся (примеры 2*3 и 3*2 и им подобные пары считать повторяющимися).

Занятие 7. Матрица.

Я сейчас вас удивлю. Матрица - это не боевик. Матрица - это такой математический термин, перешедший в программирование. И вообще, очень полезная и удобная вещь. Если с ней уметь обращаться, конечно.

Немного истории. 

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

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

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

По сути матрица - это НАБОР МАССИВОВ. с массивами мы с вами уже сталкивались, когда задавали строку элементов вида a[1], a[2], a[3],... Теперь мы будем говорить не только о номере элемента в строке, но и о номере строки, в которой этот элемент стоит. Например, элемент, стоящий в 3 строке на 5 месте мы обозначим a[3,5]. Номер строки - на первом месте, номер столбца (положение в строке) на втором. Номера строк в общем виде обозначают обычно буквой i, номера столбцов буквой  j. Тогда элемент стоящий в i -ой строке на j -ом месте обозначим  a[i,j]. Правило обозначения элементов лучше поможет понять такая таблица:

Рассмотрим простую задачу: 

Заполните таблицу 5 на 5 значениями "0" и "1" так, чтоб "1" стояли по всем крайним строкам и столбцам, а в центре были символы "0".

Другими словами. я хочу примерно такую картинку:

Program matr;

Var

a:array[1..5,1..5] of integer; - готовим ячейки памяти для нашей матрицы. По условию - 5*5.

i,j:integer;

begin

For i:=1 to 5 do begin - начинаем считать строки

For j:=1 to 5 do begin- начинаем считать столбцы

If ((i=1) or (j=1) or(i=5) or(j=5)) then - если номер элемента совпадает с номером крайней                                                                           строки или столбца...

a[i,j]:=1 - присвоить этому элементу значение 1

else

a[i,j]:=0; - иначе - присвоить значение 0

write (a[i,j]:2); - печатать элементы в строчку с интервалом 2 между ними

end; - закончили работу в строке, пройдя по всем столбцам

Writeln; - перешли на новую строку

end; - и начали работать со следующей строкой, если следующая строка есть.

end.

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

Уже знакомая вам матрица с обозначением номеров элементов. Красной линией выделена ГЛАВНАЯ диагональ, зеленой линией выделена ПОБОЧНАЯ диагональ матрицы.

Каким свойством обладают номера элементов, попавших на главную диагональ? Это элементы a[1,1], a[2,2], a[3,3]. Если бы матрица была большего размера, то на главной диагонали лежали бы и другие элементы у которых... правильно, коэффициент i=j. 

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

Только не надо мне рассказывать, что i и j изменяются на 1 в разные стороны - один коэффициент увеличивается, другой уменьшается. Как вы это объясните компьютеру? 

  

Надо искать математическую закономерность. Итак: давайте сложим i и j каждого из элементов, попавших на побочную диагональ. Какое число получилось? 4? А матрица у нас какого размера? 3*3. Поскольку у нас матрица квадратная - число строк равно числу столбцов, можем говорить "Квадратная матрица размера 3", или просто "матрица размера 3", подразумевая, что в этом случае она - квадратная.

Как связаны числа 4 и 3? Правильно, 4= 3+1. Теперь смотрим на первый элемент матрицы, попавший на эту диагональ. Какие коэффициенты у этого элемента? О! Так это же наши 3 и 1! Которые 3+1=4!

А если у нас матрица будет размером 7? В верхнем правом углу будет стоять элемент первой строки последнего, седьмого столбца. Тогда формула для побочной строки будет 7+1=8.

А если матрица будет размером 9? 9+1=10.

А если размера n?

Для любой матрицы размера n верны следующие утверждения:

1. Если i=j, то элемент a[i,j] принадлежит ГЛАВНОЙ диагонали.
2. Если i+j=n+1, то элемент a[i,j] принадлежит ПОБОЧНОЙ диагонали.

Ну а теперь, вооруженные знаниями про диагонали матрицы, напишите сами задачу, в результате которой мы увидим на экране матрицу, где на диагоналях стоят "1" а все остальные элементы - "0". Задайте матрице размер 10.

И, кроме этого, САМОСТОЯТЕЛЬНАЯ РАБОТА:

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

1. "Крестик"  
   
2. "Окошко" 
   

Занятие 6. Еще одна практическая работа.

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

1. Сначала попробуйте решить задачу самостоятельно.

2. Если не получится - подсмотрите в решения. Разберите чужой код. Ответьте для себя на вопрос, что делает каждая из строк в программе. 

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

4. Если задача написана на ввод данных с клавиатуры - переделайте на ввод данных из файла. Если программа написана для ввода информации из файла - перепишите на ввод с клавиатуры.

А теперь - задачи!

1.  Найдите наибольшее значение отношения трехзначного числа к сумме его цифр.

2.  Дана строка, состоящая из символов, каждый из которых является знаком «+» или цифрой, начинающаяся и заканчивающаяся цифрой. Если в строке встречается сочетание «++», то выдать сообщение об ошибке, в противном случае вычислить получившуюся сумму.

3. Каждый элемент квадратной матрицы размеренности NxN равен нулю, либо единице. Найдите количество «островов», образованных единицами. Под «островом» понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному «острову», если из одной из них можно перейти к другой «наступая» на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.

Материалы с сайта Подготовка к олимпиадам по информатике

Занятие 5. Без практики - никуда...

Наше занятие номер 5 будет очень коротким с моей стороны, но длинным с вашей.

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

Задача 1.

Вы, наверное, замечали, что люди бывают толстыми, худыми и обыкновенными. Известно, что вес

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

школьника с ростом 160 см будет ровно 60 кг. Ваша задача – определить тип школьника по его весу и

росту.

Формат входных данных

Во входном файле input.txt в двух строках находятся два числа H и W: H – рост школьника, W – вес

школьника. Числа H, W не превосходят 1000 .

Формат выходных данных

Выведите в выходной файл output.txt слово «OPTIMUM » (без кавычек), если вес школьника

оптимален; «FAT »,если школьнику стоит похудеть; «THIN », если школьнику стоит есть больше мучного и сладкого.

Пример

Пример входного файла input.txt	Пример выходного файла output.txt
170  105	1.      FAT

Задача 2.

Дана блок-схема алгоритма.

Какое значение приобретет переменная S после завершения выполнения алгоритма, если на вход подали N = 289?

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

Задача 3.

Ваня наблюдает за лягушкой. Изначально она сидит в точке 0 числовой прямой. Каждую секунду

она прыгает на 1 вправо, пока не достигнет точки K .Затем она начинает каждую секунду прыгать на 1

влево, пока не вернется в точку 0,затем – опять вправо и т.д. Требуется определить, где окажется лягушка через T секунд.

Формат входных данных

Во входном файле input.txt в двух строках находятся два числа K и T, разделенные пробелом. Оба

числа натуральные и не превосходят 1 000 000 000.

Формат выходных данных

Вывести в выходной файл output.txt одно число – координату лягушки в момент времени T.

Пример

Пример входного файла input.txt	Пример выходного файла output.txt
5 8	2

Примечание

Программа не должна выводить никаких дополнительных сообщений, а также не может содержать

операторов, вызывающих задержку выполнения программы (например, readln в конце программы)

Занятие 4. Поговорим о сортировке.

Занятие 4.

Одна из стандартных задач программирования - сортировка элементов массива. Массив - это набор переменных, содержащих элементы одного типа. С массивами вы встречаетесь каждый день не только в программировании, но и в обычной жизни.

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

Нельзя запихнуть в один массив тетрадь по информатике и бутерброд, который мама дала с собой в школу. Они разных типов. :-)

А теперь с переменными. Вот, допустим, у вас есть 20 участников олимпиады по информатике. Надо отсортировать их так, чтоб тот, у кого больше баллов, получил первое место, а тот, у кого меньше всех баллов - последнее. 

Да, я знаю, что проще сделать это, например, в Excel. Но, во-первых, мы учимся программировать. А во-вторых - не поверите, но Excel - это программа, которую тоже кто-то когда-то написал!

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

Существует много разных методов сортировки, вы можете почитать о них, например, здесь, но мы будем использовать метод "Пузырька".

Если взять бутылку с шампунем и потрясти ее как следует, то получатся пузырьки. А если бутылку перевернуть, то пузырьки наперегонки полетят вверх. И чем больше будет пузырек, тем быстрее он доберется наверх. Таковы законы физики.

В нашем случае - с числами - будет примерно так же.

Отсортируем такой массив чисел: 

81  5  32  47  16  - это наш исходный массив. Теперь, сравнивая два соседних элемента, мы будем менять их местами, если ЛЕВЫЙ окажется больше ПРАВОГО.

1. Сравним 81 и 5. Больше 81. Меняем местами. После первого сравнения получим ряд:   5 81 32 47 16
2. Сравним 81 и 32. Больше 81. Меняем местами. 
3. И так до конца ряда. Когда ряд будет пройден до конца, 81 как самое большое число окажется в конце.

5  32  47  16  81

Когда мы пройдем ряд от начала до конца второй раз, массив примет вид:

5  32  16  47  81

После третьего прохода:

5  16  32  47  81

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

Есть еще одна проблема, о которой важно знать. Как правильно менять местами два элемента в массиве? Рассмотрим два варианта.

Обмен элементов с введением дополнительной переменной.

Надо поменять местами элементы a и b. Дополнительная переменная - c.

c:=a;

a:=b;

b:=c;

Сразу возникает вопрос - а зачем нам с? Смотрите: пусть a=2, b=3. 

Неправильно		Правильно
a=2, b=3		a=2, b=3
a:=b	b=3, a=3.	c:=a	a=2, b=3, c=2
b:=a	b=3, a=3.	a:=b	a=3, b=3, c=2
Мы потеряли число 2.		b:=c	a=3, b=2, c=2

Обмен элементов без введения дополнительной переменной.

a:=a+b;
b:=a-b;
a:=a-b;

В принципе, можно любым способом, но мне кажется, что первый - надежнее.

А теперь возвращаемся к задаче.

В файле ввода данных содержится неизвестное количество целых чисел, не менее одного, не более 20. В файл вывода данных вывести все эти числа, отсортировав их в порядке возрастания.

Логика решения:

1. Нам нужны две переменные типа text для работы с файлами ввода и вывода данных.
2. Нам нужен массив для 20 целых чисел (не больше - по условию, но и не меньше - мы не знаем, сколько их будет). Значит, a: array [1.. 20] of integer;
3. Нам будут нужны переменные типа  integer:
• i - это будет номер элемента в массиве
• j - это будет число проходов по массиву
• k - это будет ячейка для временного хранения значения элемента при обмене
• n - это будет количество элементов в массиве, когда посчитаем.
4. Ход решения: 
• Считываем все элементы из файла ввода
• Сортируем их методом пузырька
• Выводим в файл вывода

Текст программы:

program Sortirovka;

var

a: array[1..20] of integer;

i,j,k,n:integer;

f,g:text;

begin

i:=1;

n:=0;

assign(f,'input.txt');

reset(f);

while not eof (f) do begin

        read (f, a[i]);

       i:=i+1;

       n:=n+1;

    end;

close (f);

For i:=1 to n do

For j:=1 to n-1 do

if a[j]>a[j+1] then begin

k:=a[j];

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

a[j+1]:=k;

end;

assign (g,'output.txt');

rewrite (g);

for i:=1 to n do begin

write (g, a[i]:3);

end;

close (g);

end.

Самостоятельная работа:

1. Изменить программу так, чтоб она сортировала элементы по убыванию (от большего к меньшему).
2. Изменить программу так, чтоб она сортировала не числа, а буквы по алфавиту.
3. Изменить программу так, чтобы она сортировала не буквы (один символ) а слова, например, вводят список фамилий и производится сортировка по алфавиту.
4. В файле ввода данных список вида: фамилия - балл за олимпиаду. Например:

Иванов 60
Петров 65
Сидоров 55

Составить программу, которая выведет в файл вывода данных список фамилий, отсортированный по результатам олимпиады:

Петров 65
Иванов 60
Сидоров 55

Занятие 3. Одна задача. Но какая!

Занятие 3.

Вы не поверите – основные вещи, необходимые вам для написания программ вы уже знаете. Остались мелочи – научиться правильно использовать те знания, которые у нас есть. Помните Тыкву из «Приключений Чиполино»? У него было мало кирпичей, но свой домик он построил. Вот и мы с вами будем использовать то, что есть на данный момент.

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

Задача.

Найти значение квадратного корня из числа с точностью до 4 знака после запятой, не используя функцию квадратного корня.

Сначала мы определяемся с тем, что в принципе мы будем делать для решения. Задачи такого плана – на подбор числа – можно решать методом «ПОЛОВИННОГО ДЕЛЕНИЯ». Но это тоже просто, не пугайтесь. Итак, знакомьтесь - метод «ПОЛОВИННОГО ДЕЛЕНИЯ».

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

Переменная b – это всегда серединка числового отрезка, а переменные n и a меняют свое положение в зависимости от того, в правую или левую часть отрезка попадает загаданное число.

Теперь вернемся к нашей задаче.

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

2.       Логично предположить, что значение квадратного корня из числа находится где-то между числом 0 и числом z.

3.       Z мы запомним как образец, и пока трогать не будем. Зато заведем еще переменную a, которая на первом шаге совпадет с z, а вообще в программе будет выполнять роль значения ПРАВОГО конца отрезка.

4.       Получим первое приблизительное число, которое могло бы быть ответом. Для этого разделим исходное число на 2. Пусть это будет переменная b.

5.       Найдем с=b*b

6.       Сравним с и z.

7.       Если с оказалось больше z, мы берем в качестве нового значения  b  выражение b:=(0+b)/2. Зачем прибавлять 0? Да мы просто складываем два старых конца отрезка и делим на 2. Почему мы берем левую часть отрезка? Если с оказалось больше z, значит, нужное нам число МЕНЬШЕ нашего. Поэтому – левая часть.

8.       Если с оказалось меньше z, мы в качестве нового значения  b берем выражение b:=(а+b)/2. Т.е. нужное нам число, БОЛЬШЕ нашего, и мы должны взять правую часть отрезка.

9.       Еще одна проблема: нам указана точность – 4 знака после запятой. Зачем? Все наши переменные будут типа Real, т.е. будут выводится на экран с точностью до 10 знаков после запятой, а нам надо только 4. Поэтому, когда мы будем сравнивать c и z, использовать знак «=» не имеет смысла. Наша программа сможет, конечно, найти значение квадратного корня из числа 8 как 2,8284271247461900976033774484194, но нас просят только 2,8284…

10.   Давайте рассмотрим такую конструкцию:

If (abs (z-c) <0.00001) then

begin

Writeln ('Koren iz ',z,' =',b);

goto 1;

end

Что мы написали? Если разность исходного числа и того, которое мы получили, умножая подобранное число само на себя, меньше 0,00001, т.е. числа отличаются начиная с ПЯТОГО знака после запятой, вывести подобранное число на экран. И идти к метке 1, к концу программы. А если нет – подбирай дальше.

Тут нам встретились непонятные буквы abs( )  - это функция модуля. Понимаете, если с больше z, то  z-c будет отрицательным, т.е. , поскольку ЛЮБОЕ отрицательное число меньше ЛЮБОГО положительного, программа будет выходить после первого шага, выдавая неверный результат. Попробуете после ввода и проверки программы убрать abs из этой строки. И найти квадратный корень из 9. Знаете, сколько будет? 4,5! По мнению программы, конечно. Так, по жизни, вообще-то 3… Про функцию abs( ) почитайте в продолжении словарика. 

И еще один важный момент. В тетради по математике вы отделяете целую часть от дробной в числе запятой. Например, так: «4,321». А в Паскале надо писать так: «4.321». Иначе не поймет…

А теперь – программа!

Program podbor_kornja;

label 1,2;

var

z,c,b,a,n:real;

begin

Writeln('Vvedi chislo');

Readln(z);

n:=0;

a:=z;

2: b:=(n+a)/2;

c:=b*b;

         If (abs(z-c)<0.00001) then

                   begin

                      Writeln ('Koren iz ',z,' =',b);

                   goto 1;

                  end

         Else

            begin

               If (z-c>0) then

                         begin

                             n:=b;

                         goto 2;

                     end

           else

                     begin

                 a:=b;

                 goto 2;

                end;

       end;

1: end.

Самостоятельная работа:

1.       Переписать это программу так, чтоб она брала данные из файла input.txt  и выдавала ответ в файл output.txt

2.       По этому же принципу написать программу, которая находит значение кубического корня из числа, т.е. такое число, которое при умножении само на себя три раза дает исходное с точностью до 6 знака.

3.       Подумать, как организовать вывод ответа с нужной точностью. (Чтоб не 10 знаков после запятой, а только 4 – в решенной задаче или 6 – в самостоятельной). 
Подсказка: загляните в "Словарик. Продолжение".