Главная · Поиск книг · Поступления книг · Top 40 · Форумы · Ссылки · Читатели

Настройка текста
Перенос строк


    Прохождения игр    
Roman legionnaire vs Knight Artorias
Ghost-Skeleton in DSR
Expedition SCP-432-4
Expedition SCP-432-3 DATA EXPUNGED

Другие игры...


liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня
Rambler's Top100
Образование - Различные авторы Весь текст 991.22 Kb

Программирование в теоремах и задачах

Следующая страница
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 85
             ПРОГРАММИРОВАНИЕ: ТЕОРЕМЫ И ЗАДАЧИ


            НЕСКОЛЬКО ЗАМЕЧАНИЙ ВМЕСТО ПРЕДИСЛОВИЯ

Книга   написана  по  материалам  занятий  программированием  со
школьниками математических классов школы N 57.

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

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

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

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

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

Характер  глав различен: в одних предлагается набор мало связан-
ных друг с другом задач с решениями, в других по существу  изла-
гается один-единственный алгоритм. Темы глав во многом пересека-
ются, и мы предпочли кое-какие повторения формальным ссылкам.

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

В качестве языка для записи программ был выбран паскаль  Паскаль
достачно прост и естествен, имеет неплохие реализации (например,
Turbo Pascal 3.0 и 5.0 фирмы Borland) и позволяет записать реше-
ния  всех  рассматриваемых  задач. Возможно, Модула-2 или Оберон
были бы более изящным выбором, но пока что они труднее доступны.

Неудачный опыт писания "популярных" учебников по  программирова-
нию учит: никакого сюсюканья! писать надо так, чтобы потом самим
было не стыдно прочесть.

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

Это не только и не столько учебник для школьника, сколько  спра-
вочник и задачник для преподавателя, готовящегося к занятию.

Об "авторских правах": право формулировать задачу и объяснять её
решение является неотчуждаемым естественным правом всякого,  кто
на это способен. В соответствии с этим текст (в ASCII и TeX-вер-
сиях)  является  свободно  распространяемыми. С ним можно делать
всё, что угодно, и если Вы внесли в него ошибки, не указав,  что
они  принадлежат  Вам, или использовали текст в коммерческих це-
лях, не поделившись прибылью - Бог Вам судья.

Благодарности. Я рад случаю поблагодарить всех, с кем имел честь
сотрудничать, преподавая программирование, особенно тех, кто был
"по другую сторону баррикады".
        Н Е   П О К У П А Й Т Е   Э Т У   К Н И Г У !

                (Предупреждение автора)

     В этой книге ничего не  говорится  об  особенностях  BIOSа,
DOSа, OSа, GEMа и Windows, представляющих основную сложность при
настоящем программировании.

     В ней нет ни слова об объектно-ориентированном программиро-
вании, открывшем новую эпоху в построении дружественных и эффек-
тивных программных систем.

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

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

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

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

     Логическое  программирование,  постепенно вытесняющее уста-
ревший операторный стиль программирования, не затронуто.

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

     Проблемы отладки и сопровождения программ,  занимающие,  по
общему  мнению профессионалов, 90% в программировании, игнориру-
ются.

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

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

     Короче  говоря, покупать эту книгу глупо - особенно теперь,
когда выходит столько переводных руководств, написанных в  циви-
лизованных странах настоящими профессионалами.
     Глава 1. Переменные, выражения, присваивания.

     1.1. Задачи без массивов

     1.1.1. Даны две целые переменные a, b.  Составить  фрагмент
программы, после исполнения которого значения переменных поменя-
лись бы местами (новое значение a равно старому значению b и на-
оборот).

     Решение. Введем дополнительную целую переменную t.
        t := a;
        a := b;
        b := t;
Попытка обойтись без дополнительной переменной, написав
        a := b;
        b := a;
не приводит к цели (безвозвратно утрачивается начальное значение
переменной a).

     1.1.2.  Решить  предыдущую  задачу,  не  используя дополни-
тельных переменных (и предполагая, что значениями целых перемен-
ных могут быть произвольные целые числа).

     Решение. (Начальные значения a и b обозначим a0, b0.)
        a := a + b; {a = a0 + b0, b = b0}
        b := a - b; {a = a0 + b0, b = a0}
        a := a - b; {a = b0, b = a0}

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

     Решение. Введем целую переменную k, которая меняется от  0
до  n,  причем  поддерживается такое свойство: b = (a в степени
k).

        k := 0; b := 1;
        {b = a в степени k}
        while k <> n do begin
        | k := k + 1;
        | b := b * a;
        end;

Другое решение той же задачи:

        k := n; b := 1;
        {a в степени n = b * (a в степени k)}
        while k <> 0 do begin
        | k := k - 1;
        | b := b * a;
        end;

     1.1.4. Решить предыдущую задачу, если требуется, чтобы чис-
ло действий (выполняемых операторов присваивания)  было  порядка
log n (то есть не превосходило бы C*log n для некоторой констан-
ты C; log n - это степень, в которую нужно возвести 2, чтобы по-
лучить n).

     Решение. Внесем некоторые изменения во второе из предложен-
ных решений предыдущей задачи:

        k := n; b := 1; c:=a;
        {a в степени n = b * (c в степени k)}
        while k <> 0 do begin
        | if k mod 2 = 0 then begin
        | | k:= k div 2;
        | | c:= c*c;
        | end else begin
        | | k := k - 1;
        | | b := b * c;
        | end;
        end;

Каждый второй раз (не реже)  будет  выполняться  первый  вариант
оператора  выбора  (если  k  нечетно, то после вычитания единицы
становится четным), так что за два цикла величина k  уменьшается
по крайней мере вдвое.

     1.1.5.  Даны натуральные числа а, b. Вычислить произведение
а*b, используя в программе лишь операции +, -, =, <>.

     Решение.
        var a, b, c, k : integer;
        k := 0; c := 0;
        {инвариант: c = a * k}
        while k <> b do begin
        | k := k + 1;
        | c := c + a;
        end;
        {c = a * k и k = b, следовательно, c = a * b}

     1.1.6.  Даны  натуральные  числа  а и b. Вычислить их сумму
а+b. Использовать операторы присваивания лишь вида

        <переменная1> := <переменная2>,
        <переменная> := <число>,
        <переменная1> := <переменная2> + 1.

     Решение.
          ...
         {инвариант: c = a + k}
          ...

     1.1.7. Дано натуральное (целое неотрицательное) число  а  и
целое положительное число d. Вычислить частное q и остаток r при
делении а на d, не используя операций div и mod.

     Решение. Согласно определению, a = q * d + r, 0 <= r < d.

        {a >= 0; d > 0}
        r := a; q := 0;
        {инвариант: a = q * d + r, 0 <= r}
        while not (r < d) do begin
        | {r >= d}
        | r := r - d; {r >= 0}
        | q := q + 1;
        end;

     1.1.8.  Дано  натуральное  n,  вычислить n!
        (0!=1, n! = n * (n-1)!).

     1.1.9.   Последовательность  Фибоначчи  определяется  так:
a(0)= 1, a(1) = 1, a(k) = a(k-1) + a(k-2) при k >= 2.  Дано  n,
вычислить a(n).

     1.1.10.  Та же задача, если требуется, чтобы число операций
было пропорционально log n. (Переменные должны быть  целочислен-
ными.)

     Указание.  Пара соседних чисел Фибоначчи получается из пре-
дыдущей умножением на матрицу
            |1 1|
            |1 0|
так что задача сводится к возведению матрицы в  степень  n.  Это
можно сделать за C*log n действий тем же способом, что и для чи-
сел.

     1.1.11. Дано натуральное n, вычислить 1/0!+1/1!+...+1/n!.

     1.1.12.  То  же, если требуется, чтобы количество операций
(выполненных команд присваивания) было бы не более C*n для  не-
которой константы С.
     Решение.  Инвариант:  sum  =  1/1! +...+ 1/k!, last = 1/k!
(важно не вычислять заново каждый раз k!).

     1.1.13.  Даны  два  натуральных числа a и b, не равные нулю
одновременно. Вычислить НОД (a,b) - наибольший общий делитель  а
и b.

     Решение (1 вариант).

        if a > b then begin
        | k := a;
        end else begin
        | k := b;
        end;
        {k = max (a,b)}
        {инвариант: никакое  число, большее k, не является об-
          щим делителем}
        while not (((a mod k)=0) and ((b mod k)=0)) do begin
        | k := k - 1;
        end;
        {k - общий делитель, большие - нет}

       (2  вариант - алгоритм Евклида). Будем считать , что НОД
(0,0) = 0. Тогда НОД (a,b) = НОД (a-b,b)  =  НОД  (a,b-a);  НОД
(a,0) = НОД (0,a) = a для всех a,b>=0.

         m := a; n := b;
        {инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
        while not ((m=0) or (n=0)) do begin
        | if m >= n then begin
        | | m := m - n;
        | end else begin
        | | n := n - m;
        | end;
        end;
        if m = 0 then begin
        | k := n;
        end else begin
        | k := m;
        end;

     1.1.14. Написать модифицированный вариант алгоритма Евкли-
да,  использующий соотношения НОД (a, b) = НОД (a mod b, b) при
a >= b, НОД (a, b) = НОД (a, b mod a) при b >= a.

     1.1.15. Даны натуральные а и b, не равные 0  одновременно.
Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y.

     Решение.  Добавим в алгоритм Евклида переменные p, q, r, s
Следующая страница
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 85
Ваша оценка:
Комментарий:
  Подпись:
(Чтобы комментарии всегда подписывались Вашим именем, можете зарегистрироваться в Клубе читателей)
  Сайт:
 
Комментарии (1)

Реклама