IPB

Здравствуйте, гость ( Вход | Регистрация )

4 страниц V   1 2 3 > »   
Ответить в эту темуОткрыть новую тему
> Как научиться программировать?, Кто хочет стать настоящим программистом?
Gall
сообщение 12.10.2005, 23:54
Сообщение #1





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



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

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

Часть первая. Императивный подход.

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


Часть вторая. Процедурный подход.

Описывать такие мелкие движения неудобно. Сгруппируем их в более крупные действия - процедуры.
Исходный код
ПРОЦЕДУРА взять карандаш:
 передвинуть руку ...
 ...
КОНЕЦПРОЦЕДУРЫ

Описываем какое-нибудь действие в виде таких процедур.
Исходный код
ПРОЦЕДУРА Вскипятитьчайник
 взять чайник
 ЕСЛИ чайник пуст ТО
   налить воду в чайник
 КОНЕЦЕСЛИ
 поставить чайник на плиту
 зажечь газ
КОНЕЦПРОЦЕДУРЫ


Часть третья. Декларативный подход.

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

ПРАВИЛА:

 дано: чайник с водой на плите
 надо: кипящий чайник
 как: зажечь газ

 дано: чайник с водой
 надо: чайник с водой на плите
 как: поставить чайник на плиту

 дано: чайник пуст
 надо: чайник с водой
 как: налить воду в чайник

ПРОГРАММА:

 дано: чайник пуст
 надо: кипящий чайник


Потренируйтесь в подобных задачах. Когда задачи перестанут вызывать вопросы, переходите к следующему уроку.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 13.10.2005, 00:10
Сообщение #2





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Урок 1. Машинный язык.

Переходим к программированию настоящих компьютеров. Нам потребуется какой-нибудь несложный компьютер, лучше 60-х годов. Поскольку таких у нас нет, возьмем машину под названием MIX, придуманную Дональдом Кнутом. Эмулятор этой машины можно найти в интернете (http://dmoz.org/Computers/Programming/Lang...embly/MIX-MMIX/). Советую вот этот:http://www.menees.com/MIXBuilder.htm

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

Берем книгу [1] и читаем первую главу. Математику, изложенную в самом начале, Вы, возможно, уже знаете. Если знаете - можете не читать. Внимательно читаем описание компьютера MIX. Пробуем писать для него простенькие программки - например, сумму двух чисел:
Исходный код
LDA 2000
ADD 2001
STA 2002


Выполняем простенькие упражнения из книги.

Литература.
[1] Дональд Кнут. Искусство программирования. Т. 1: Основные алгоритмы. Гл. 1: Основные понятия.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 3.11.2005, 17:02
Сообщение #3





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Урок 2. Начинаем изучать Паскаль.

Нам надо понять основы структурного программирования. В качестве языка для обучения выберем классический Паскаль, причем не будем отвлекаться на дополнительные возможности, которые есть в Delphi и Borland Pascal.

Ищем хорошую книжку. Лучше Вирта, но ее трудно найти. Ищем компилятор. Например, FreePascal (www.freepascal.org). Можно обойтись и Delphi (в режиме консольного приложения) или Borland Pascal 7.

Часть первая. Основная структура программы.

Программа на Pascal состоит из объявлений и тела. Программа начинается со слова program и названия программы, затем следуют объявления (переменные, константы, функции). Затем идет блок тела, открывающийся словом begin и заканчивающийся end и точкой.

Исходный код

program Hello;  (* заголовок *)

               (* объявления, у нас их нет *)

begin

 writeln ('Hello World'); (* тело *)

end.


Часть вторая. Переменные. Объявления переменных. Оператор var. Типы переменных. Простая математика.

Исходный код

program Sum;

 var
   x, y: integer;

begin

 x := 2 + 2;
 writeln (x);

 y := x * 2;
 writeln (y);

 x := x + 1;
 writeln (x);

end.


Здесь же уместно научиться пользоваться оператором readln.

Часть третья. Условия if - then - else.

Часть четвертая. Повторения одной и той же операции. Циклы. Цикл for.

Часть пятая. Условные повторения. Циклы с пре- и постусловием (while, repeat - until).

Добавлено в [mergetime]1131018828[/mergetime]:
Урок 3. Процедурное программирование на Pascal.

Часть первая. Операторы procedure и function. Формальные параметры и возвращаемое значение. Передача параметров по ссылке (var в параметрах).

Часть вторая. Глобальные и локальные переменные, области видимости. Вызов функции из функции. Рекурсия.

Часть третья. Разбиение программы на несколько файлов. Модули. Операторы unit и uses. Интерфейс и реализация.

Добавлено в [mergetime]1131019353[/mergetime]:
Урок 4. Расширенные возможности Pascal.

Часть первая. Сложные типы данных. Операторы array, set, record, file.

Часть вторая. Строки. Тип string.

Часть третья. Вспомогательные операторы организации потока программы. Оператор case.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 4.11.2005, 01:15
Сообщение #4





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Урок 5. Выделение памяти и указатели.

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

Часть первая. Тип данных Pointer. Операторы @ и ^.

В Паскале имеется оператор @, который позволяет определить адрес переменной в памяти. Чтобы не спутать адрес с обычным числом, для него используют особый тип данных - Pointer.
Исходный код

 var
   p: pointer;
   x: integer;
(* ... *)
 p := @x;


Обратная операция (получени е содержимого ячейки по ее адресу) делается с помощью оператора ^. Например:
Исходный код

p := @x;
y := p^;


Часть вторая. Типизированные указатели.

Предыдущий пример не будет работать, поскольку тип p^ неизвестен. Для решения этой проблемы придуманы типизированные указатели. Вместо слова pointer используется ^название_типа.
Исходный код

var
 p: ^integer;
 x, y: integer;
(*...*)
p := @x;
y := p^;


Часть третья. Выделение памяти. Операторы new и dispose.
Исходный код

p := new (integer);
p^ = 1;
writeln (p^);
dispose (p);


Добавлено в [mergetime]1131048935[/mergetime]:
Урок 6. Основные структуры данных.

Часть 1. Массив (вектор).
Часть 2. Связный список. Двусвязный список.
Часть 3. Дерево. Различные деревья.
Часть 4. Хеш-таблицы.
Часть 5. Применение различных структур данных для эффективного хранения информации.

Литература.
[2] Никлаус Вирт. Алгоритмы и структуры данных.
[3] Ахо, Хопкрофт, Ульман. Структуры данных и алгоритмы.
А также первый том Кнута [1].
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 2.4.2006, 20:26
Сообщение #5





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Продолжение напишу по требованию, когда кто-нибудь пройдет первые 6 уроков.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Лесной
сообщение 4.4.2006, 18:58
Сообщение #6





Группа: Пользователи
Регистрация: 30.12.2004
Из: Лес 58a
Пользователь №: 3 476



Гал, у тебя есть эта литература в электронном виде?
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 5.4.2006, 11:52
Сообщение #7





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Цитата(Лесной @ 4.4.2006, 18:58)
Гал, у тебя есть эта литература в электронном виде?
*


Большую ее часть выложили здесь:
Полезные публикации
В бумажном виде все эти книги сейчакс купить не проблема.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Vigo
сообщение 16.5.2006, 01:21
Сообщение #8





Группа: Пользователи
Регистрация: 20.10.2005
Из: Yekb
Пользователь №: 5 924



Gall,
А этот тип pointer в паскале... это тоже что и void * ? в cях?
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 16.5.2006, 01:29
Сообщение #9





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Цитата(Vigo @ 16.5.2006, 01:21)
Gall,
А этот тип pointer в паскале... это тоже что и void * ? в cях?
*


В точности. Абсолютно то же самое.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
winnie the cat
сообщение 16.5.2006, 16:39
Сообщение #10





Гости





почему-то обижены неимперативные языки программирования. а они, между тем, предлагают интересные и полезные концепции организации программ, например, ленивые вычисления или обратные выводы. программист не достигнет Дао, пока не осознает, что такое lambda-исчисление, логическое программирование и прочие интерестности вроде refal'а. ключевые слова названы, дерзайте : )
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 17.5.2006, 01:11
Сообщение #11





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Цитата(winnie the cat @ 16.5.2006, 16:39)
почему-то обижены неимперативные языки программирования. а они, между тем, предлагают интересные и полезные концепции организации программ, например, ленивые вычисления или обратные выводы. программист не достигнет Дао, пока не осознает, что такое lambda-исчисление, логическое программирование и прочие интерестности вроде refal'а. ключевые слова названы, дерзайте : )
*


Не обижены, просто не дошел smile.gif Собирался и про refal, и про lisp, и про prolog, и про haskell написать.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 18.5.2006, 13:00
Сообщение #12





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



К этому моменту следующие три задачи уже не должны вызывать особых трудностей.

Задача 1. Ханойские башни.

Имеется три стержня. На одном стержне нанизана пирамидка из дисков (внизу самый большой, сверху самый маленький). Требуется перенести эту пирамидку на другой стержень. Каждый раз можно перекладывать только один диск, причем можно класть маленькитй диск на большой, а большой на маленький нельзя.
1. Доказать, что для любого числа дисков перекладывание возможно.
2. Определить, за какое время можно переложить N дисков.
3. Написать программу, перекладывающую диски. Если не лень - можно рисовать палки и диски на экране. Если лень - достаточно печатать строки "переложить диск оттуда-то туда-то".
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Uzer
сообщение 18.5.2006, 14:10
Сообщение #13





Группа: Пользователи
Регистрация: 7.11.2004
Пользователь №: 3 101



Цитата(Gall @ 18.5.2006, 13:00)
1. Доказать, что для любого числа дисков перекладывание возможно.
индукция по N? huh.gif
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 18.5.2006, 21:12
Сообщение #14





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Цитата(Uzer @ 18.5.2006, 14:10)
индукция по N?  huh.gif
*


Верно.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Uzer
сообщение 18.5.2006, 21:14
Сообщение #15





Группа: Пользователи
Регистрация: 7.11.2004
Пользователь №: 3 101



Цитата(Gall @ 18.5.2006, 21:12)
Верно.
Не могу вывести формулу fingal.gif
рекурсивное соотношение находится лехко из алгоритма, а как из него получить формулу N-ого члена unsure.gif
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 18.5.2006, 21:19
Сообщение #16





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Задача 2. Кольцо в списке.

Имеется односвязный список (см. Вирта). Есть подозрение, что этот список закольцован (т.е. в нем последний элемент указывает не в "нуль", а на какой-то элемент из середины [не обязательно первый]). Требуется определить, есть кольцо в списке или нет. На то, чтобы как-то помечать или запоминать элементы, которые нам уже встречались, у нас нет памяти - в списке могут быть гигабайты данных. Как быть?

Задача 3. Квадратный корень.
Процессор обычно знает только 4 действия арифметики. Задача: извлечь квадратный корень из числа, пользуясь только 4 действиями арифметики.

Литература: та же, при трудностях - Кнута все три тома, могу еще подсказать.

Добавлено в [mergetime]1147969165[/mergetime]:
Цитата(Uzer @ 18.5.2006, 21:14)
Не могу вывести формулу fingal.gif
рекурсивное соотношение находится лехко из алгоритма, а как из него получить формулу N-ого члена unsure.gif
*


А зачем? Это не нужно для решения.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
dJony
сообщение 21.5.2006, 12:09
Сообщение #17





Группа: Пользователи
Регистрация: 8.5.2006
Из: 3аречный-city
Пользователь №: 11 701



Цитата(Gall @ 18.5.2006, 22:19)
Задача 2. Кольцо в списке.

Имеется односвязный список (см. Вирта). Есть подозрение, что этот список закольцован (т.е. в нем последний элемент указывает не в "нуль", а на какой-то элемент из середины [не обязательно первый]). Требуется определить, есть кольцо в списке или нет. На то, чтобы как-то помечать или запоминать элементы, которые нам уже встречались, у нас нет памяти - в списке могут быть гигабайты данных. Как быть?



как вариант его можно развернуть.. biggrin.gif
т.е. если есть следующий элемент списка, то текущий будет указывать на предыдущий (тогда первый будет ук. на NULL) и переходим к следующему..
т.о. запомнив адрес 1го элемента если мы вновь доходим до него, то это означает наличие цикла в списке, иначе мы дойдем до NULL

остается узнать, как выделить цикл, или даже оборвать его.. rolleyes.gif
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 21.5.2006, 18:06
Сообщение #18





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Цитата(dJony @ 21.5.2006, 12:09)
как вариант его можно развернуть..  biggrin.gif
т.е. если есть следующий элемент списка, то текущий будет указывать на предыдущий (тогда первый будет ук. на NULL) и переходим к следующему..
т.о. запомнив адрес 1го элемента если мы вновь доходим до него, то это означает наличие цикла в списке, иначе мы дойдем до NULL

остается узнать, как выделить цикл, или даже оборвать его..  rolleyes.gif
*


Не получится так. Решение гораздо проще и изящнее...

Если не терпится узнать ответ, то воспользуйся поиском по форуму. Я уже давал эту задачу, и ее решили.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Dreamer
сообщение 21.5.2006, 21:38
Сообщение #19





Группа: Пользователи
Регистрация: 6.10.2004
Пользователь №: 2 843



Цитата(Gall @ 18.5.2006, 22:19)
Имеется односвязный список (см. Вирта). Есть подозрение, что этот список закольцован (т.е. в нем последний элемент указывает не в "нуль", а на какой-то элемент из середины [не обязательно первый]). Требуется определить, есть кольцо в списке или нет. На то, чтобы как-то помечать или запоминать элементы, которые нам уже встречались, у нас нет памяти - в списке могут быть гигабайты данных. Как быть?

решение: 2 бегунка по списку, один быстрее другого, если цикл есть, то рано или поздно более быстрый нагонит медленного, в ином случае он встретит NULL. Задачка интересная, пришлось немного помучать мозг smile.gif

Сообщение отредактировал Dreamer - 21.5.2006, 21:41
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
DreamHacker
сообщение 22.5.2006, 07:57
Сообщение #20


способен придумать оригинальный статус-)


Группа: Пользователи
Регистрация: 19.9.2004
Пользователь №: 2 706



Цитата(Gall @ 18.5.2006, 22:19)
Задача 3. Квадратный корень.
Процессор обычно знает только 4 действия арифметики.


Уточни какие... булевой алгебры или имеено арифметики. unsure.gif

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

Сачала из числа последовательно вычитать 1... потом 2ойку... потом 3ойку... - вычитать до тех пор, пока сумма не уйдет в 0 или -,если сумма равна 0, то необходимо умножить то число которое мы вычитали на счетчик вычитаемых чисел - если не равно первоначальному числу - идем дальше, останавливаемся в тот момент, когда вычитаемое превысит значение счетчика
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
dJony
сообщение 22.5.2006, 08:27
Сообщение #21





Группа: Пользователи
Регистрация: 8.5.2006
Из: 3аречный-city
Пользователь №: 11 701



откуда из этого алгоритма возьмутся вещественные числа, непонимаю mellow.gif

Сообщение отредактировал dJony - 22.5.2006, 08:27
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 22.5.2006, 12:24
Сообщение #22





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Цитата(DreamHacker @ 22.5.2006, 07:57)
Уточни какие... булевой алгебры или имеено арифметики. unsure.gif
*


Арифметики. Веществеенной.

Переформулирую. Вычислить квадратный корень на обыкновенном бухгалтерском калькуляторе, у которого нет кнопки "корень", а есть только "+", "-", "*", "/".
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
HUG
сообщение 22.5.2006, 21:10
Сообщение #23





Группа: Пользователи
Регистрация: 31.8.2003
Пользователь №: 188



Цитата(Gall @ 22.5.2006, 12:24)
Арифметики. Веществеенной.

Переформулирую. Вычислить квадратный корень на обыкновенном бухгалтерском калькуляторе, у которого нет кнопки "корень", а есть только "+", "-", "*", "/".
*



по-моему стандартаня задача
дают на подготовительных в вуз
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Gall
сообщение 22.5.2006, 21:16
Сообщение #24





Группа: Пользователи
Регистрация: 18.7.2004
Из: Мосгорка
Пользователь №: 2 341



Цитата(HUG @ 22.5.2006, 21:10)
по-моему стандартаня задача
дают на подготовительных в вуз
*


Тем не менее ее почти никто не умеет решать!!!
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Uzer
сообщение 22.5.2006, 21:27
Сообщение #25





Группа: Пользователи
Регистрация: 7.11.2004
Пользователь №: 3 101



Цитата(Gall @ 22.5.2006, 21:16)
Тем не менее ее почти никто не умеет решать!!!
там вроде какой-то рекурсивный алгоритм есть
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения

4 страниц V   1 2 3 > » 
Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия Сейчас: 17.1.2018, 20:14
Блог КАБiNET