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