Занятие 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 – в самостоятельной). 
Подсказка: загляните в "Словарик. Продолжение". 

Занятие 2. Много нового.

На прошлом занятии мы научились писать простейшие программы, которые умеют выполнять действия, идущие одно за другим, никуда не сворачивая. Такие программы похожи на работника, который о своей работе говорит так: «Могу копать, могу не копать!» - не интересно…

Сегодня мы рассмотрим две программы. Одна будет проверять пароль, и не пускать нас дальше до тех пор, пока мы не введем его правильно.

А вторая программа будет угадывать любой, самый сложный пароль. 

Сразу скажу честно: да, с помощью второй программы вы могли бы взломать чужие Вконтакте, почту, сайт Пентагона и даже банкомат… если бы смогли запустить эту программу в нужном месте. А вот как прицепить эту программку к почтовому серверу я вам рассказывать не буду. И вообще: взлом уголовно наказуем. А мы – приличные люди, не нарушающие законов.

Итак, первая задача: написать программу, которая будет запрашивать пароль. Если пароль введен верно – написать «Добро пожаловать», если не верно – вернуться к вводу пароля.

Начинаем мы с определения количества и типов переменных. Нам надо две переменных, которые будут содержать более, чем один символ, буквы и цифры. Значит, это будут переменные типа String.

Почему две? В первую мы запомним правильный пароль, а во вторую будем записывать то, что вводит пользователь.

Что мы будем делать в ходе программы? Мы будем проверять, равны ли между собой наши переменные. Если равны – выводить сообщение «Добро пожаловать», если нет – отправлять пользователя на ввод пароля еще раз.

Для того, чтобы вернуться по тексту программы назад, нам нужны метки в программе. Для этого мы в «шапке» не забудем записать раздел Label, сразу в словарике посмотрите, что это за слово такое.

Поехали! Вы же помните, то, что написано красным курсивом в текст программы писать не надо?

Program password; - мы назвали программу английским словом «пароль». Почему                                          нет?

Label 1; - мы сможем вернуть программу «назад во времени».

Var

Pas1, pas2: String; - готовим две переменные. Pas1 – правильный пароль, pas2 – то,       что введет  пользователь.

Begin

Writeln (‘Vvedi ishodnyj parol’); - надо же нам с чем-то сравнивать…

Readln (pas1); - запомним исходный пароль

1:  Writeln (‘Vvedi parol’); - теперь мы спросим второй вариант пароля.

Readln (pas2); - запомним пароль, который ввел пользователь.

If (pas1 = pas2) then – Если pas1 = pas2 тогда – это то, что написано в этой                                                 строке.

Writeln (‘Dobro pojalovat’) – если условие строкой выше выполнилось – написать             «Добро пожаловать»

Else goto 1; - Иначе отправиться к метке 1. Кстати, где она? Какая строка                                    начинается с «1:»?

Readln; - приостановим программу, посмотрим на результат.

End. – закончим программу.

Набрали программу? 

Заработало? Если да – браво. 

Если нет, спорим, вы поставили «точку с запятой» после строки Writeln (‘Dobro pojalovat’) … 

Дело в том, что перед оператором Else НИКОГДА не ставят «точку с запятой». Почему? «Точка с запятой» означает логическое окончание фразы. Например: программа называется так-то; - фраза окончена. Напечатать на экране вот то и вот это – фраза окончена. А что же там с Else?

Если( If) условие выполнилось тогда (then) сделайте это иначе (Else) сделайте что-то другое ; - фраза логически заканчивается только здесь. Вот почему ПЕРЕД Else «точку с запятой» не ставят.

А теперь давайте сделаем нашу программу лучше. Вот, например, мы вводим пароль с клавиатуры, и даже не прячем его. Трудно не угадать такой пароль, правда? 

Изменим программу так, чтоб:

• Пароль загадывался в отдельном файле;
• Сообщение о результате угадывания пароля выводилось в отдельный файл.

Для этих улучшений надо проделать дополнительную работу:

• Создаем на диске D: папку Pr1
• Создаем в этой папке два пустых файла в редакторе «Блокнот», называем их  «Input.txt» и  «output.txt»
• Морально готовимся к тому, что мы сохраним нашу программу в эту папку.

Открываем TP 7.0 и вводим программу.

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

Program password2;

Label 1;

Var

pas1, pas2: string;

f,g: text;           - мы вводим две новых переменных для работы с файлом. У них новый                            тип - text

Begin

assign (f, 'input.txt');     - связываем в сознании компа переменную f и файл input.txt

reset  (f);                       - открываем текстовый файл для чтения

read (f, pas1);               - считываем пароль из файла input.txt и запоминаем его в                                                 переменную pas1

close (f);                        - закрываем текстовый файл f

1: writeln ('vvedi parol');

readln(pas2);

assign (g, 'output.txt');       - связываем в сознании компа переменную g и файл output.txt

rewrite(g);                          - открываем текстовый файл для записи

If (pas1=pas2) then

writeln (g, 'Ugadal!')

else

goto 1;

close (g); - закрываем текстовый файл

readln;

end.

Что мы имеем в результате?

Наша папка PR1 на диске D: выглядит так:

В файл input.txt  вы можете вписать любой пароль, и программа будет бродить по кругу пока вы не введете его правильно. После этого в файле output.txt появится надпись Ugadal!

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

Если на них нажать, мы перейдем на один уровень вверх – в папку Паскаля. Поднимемся еще на один уровень и так до тех пор, пока не увидим название нашей папки PR1 на диске D:

Итак, первая задача решена.

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

Сколько переменных какого типа нам будут нужны?

Как взрослые программисты, мы будем записывать пароль в один файл, а результат угадывания выводить в другой файл. Значит, нам нужны переменные типа text, и их будет две – одна для файла ввода, другая для файла вывода.

Мы договорились, что наш пароль будет не длиннее 20 символов, значит, нам нужны 20 переменных типа char  для загадывания пароля и 20 переменных типа char  для разгадывания пароля. Всего 40.  Но мы не будем их вводить по одной, мы сделаем два массива. Подробности – в "Словарике".

А еще нам нужны будут переменные для счета: i,n  типа integer.

И одна переменная, которую мы будем использовать для подбора символов, типа char.

Теперь о идее решения.

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

Потом мы будем делать следующее: брать переменную а[ номер будем менять постепенно] и сравнивать её со всеми возможными символами подряд. 

Кстати, хочу отметить, что есть определенный порядок расположения символов. Сначала идут все цифры от 0 до 9. Потом все большие латинские буквы от «A» до «Z», а потом все маленькие латинские буквы от «a» до «z». 

Как только мы будем находить совпадающий с а[ номер которого мы сейчас рассматриваем] символ, мы будем присваивать переменной b[ того же самого номера, что и а] этот символ.

А когда мы их всех переберем – выведем в файл вывода.

Поехали!

program Vzlom;

Var

f,g:text;                                            -наши переменные для текстовых файлов

a,b:array[1..20] of char;                 - это мы задали 20 переменных а и 20 переменных b

p:char;                                            - переменная для перебора символов

i,n:integer;                                      - переменные для счета

begin

i:=1;                                               - номер первой а равен 1

n:=0;                                              - мы пока не знаем, сколько символов в пароле

assign (f,'input.txt');                       - готовим файл ввода

reset(f);                                          - открываем его для чтения

while not eof (f) do begin            – пока файл не кончится, делать…

        read (f, a[i]);                           - читать символ и запоминать в а [ i ]

       i:=i+1;                                      - поменять номер а на следующий

       n:=n+1;                                   - посчитать очередной символ

    end;                                       - уф! Мы прочитали весь наш файл ввода. Все символы                  из него мы запомнили в последовательность переменных                  a[1], a[2],…, a[n]. А получившееся в конце число n – это                           количество символов в пароле.

close (f);                               - файл ввода можно закрывать.

For i:=1 to n do                   – для всех номеров от 1 до n делать…

For p:='0' to 'z' do                – меняя все возможные символы от '0' до 'z'

if a[i]=p then b[i]:=p;            - если а [ i ]= этому символу, запомнить его в b[ i ], если нет – ничего не делать.

assign(g,'output.txt');               - готовим файл для вывода данных

rewrite(g);

For i:=1 to n do                   – печатаем в него все найденные символы

write(g, b[i]);

close (g);                                - закрываем файл вывода

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

Сохраните свою программу в ту же папку PR1.

Введите какой-нибудь набор больших и маленьких букв и цифр в файл Input.txt и сохраните его.

Запустите программу. Откройте файл вывода. Получилось? Классно!

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

1. Почему при использовании внешних файлов нужно сохранять программу в папку с этими файлами?
2. Что означает строчка a:array[1..10] of Real; ?
3. Какими строками в программе подготовить считывание информации из внешнего файла?
4. Какие ДВЕ команды общие при работе с внешними файлами ввода и вывода?
5. Напишите программу, которая будет считывать символы из файла ввода информации, и записывать их В ОБРАТНОМ ПОРЯДКЕ в файл вывода информации. Например: в файле ввода «1 2 3 4 5», тогда в файле вывода «5 4 3 2 1»

Подсказка:

Пусть у нас в файле ввода n символов, причем n=5. После того, как мы заполним массив а, мы должны заполнить массив b, взяв элементы массива а в обратном порядке. Массив b мы потом будем выводить.

Если мы зададим такой цикл:

For i:=1 to n do

For j:=n downto 1 do

b[ i ]:=a[ j ];

Что мы получим в итоге в массиве b?