Компьютерные программы.

[Gall]

и какой уровень соответствует решившему задачу ? {}

Зачет за первый семестр сдан. Еще 9 семестров осталось.

[KRAB-XIMIK]

Задачку на вычисление количества перекладываний колец я видел в учебнике по геометрии за 9 класс. Оно равно 2^N-1. Попробуйте это доказать, используя математическую индукцию. У меня не получается :(

[prikol1]

... но очень слабо изобретает алгоритмы...

 

Всем зеленым новичкам я всегда даю в качестве такой задачи "Ханойские башни". Формулировка общеизвестна. Вопросы ставлю так:

1. Доказать, что задача имеет решение для любого N дисков.

2. Найти наименьшее время решения (число ходов) для N дисков.

3. Доказать, что это число действительно наименьшее.

4. Реализовать решение на любом языке программирования и запустить его.

Подглядывать в готовое решение запрещается.

 

Ради спортивного интереса попробую.

1.Для двух дисков решение есть. Пусть их N+1. Нижний - самый большой, алгоритма для N не нарушает. Перекладываем N штук на ненужный стержень, последний на нужный и остальные на нужный с помощью алгоритма для N.

2,3. Пока верхние не уберём на единственный стержень, нижний сдвинуть не можем. Как убрали, сдвигаем его один раз, меньше некуда. Итого минимальное f(N+1)=f(N)*2+1=1+2*(1+2*f(N-1))=1+2+4...+2^(n-1).

f(1)=1

f(N+1)=(1+2+4...+2^(n-2)+1)*2+1=1+2+...+2^(N-1)=2^(N)-1

формулу минимального числа ходов получили и доказали.

4. Реализация удобнее всего по рекурсии.

 

Что такое парсер, я не очень понял. Что-то типа получения компилятором внутреннего представления программы по её коду? А если в ней ошибки, то в один проход может и не получится, хотя я не пробовал.

[Gall]

Ради спортивного интереса попробую.

Правильно. Только обычно доказательство начинают не с двух дисков, а с одного. "Очевидно, что переложить 1 мы можем..." Ну и дальше по индукции.

 

Что такое парсер, я не очень понял. Что-то типа получения компилятором внутреннего представления программы по её коду? А если в ней ошибки, то в один проход может и не получится, хотя я не пробовал.

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

 

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

 

Классическая задачка на парсеры и компиляторы - такая. Дано арифметическое выражение (четыре действия и скобки). Представить его в виде набора команд для машины с обратной польской нотацией. (Польская нотация - это когда пишутся сначала аргументы, потом операция. Например, 2+2 пишется 2,2,+, а (3+4)*(5+6) пишется 3,4,+,5,6,+,*, то есть числа кладутся на стек, а операция берет со стека аргументы и ответ тоже кладет на стек. Кто работал с советскими калькуляторами Б3-34 или МК-61, хорошо знает это). С этой задачи обычно начинается изучение теории построения компиляторов.

 

Вот здесь есть много хороших задачек для желающих порешать:

 

http://acm.timus.ru/

 

От самых простых и до жутко сложных.

[Kotto]

А я бы предложил попробовать освоить лисп если будет скучно или пролог ) Распознавание символов на лиспе довольно веселая задачка )

---

 

эх, вспоминается с чего все начиналось еще в универе, прога Statistica Neural Network, потом зазказ откуда то на программу распознавания лиц... так я и нашел свою работу :-D

Изменено 18 Февраля, 2012 в 16:55 пользователем Kotto

[gecsagen]

Прога указанная http://kriptomir.forum2x2.ru/t45-topic тут работать будет?

[Gall]

Прога указанная http://kriptomir.forum2x2.ru/t45-topic тут работать будет?

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

[gecsagen]

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

 

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

[Gall]

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

[gecsagen]

Я хотел спросить что за файл такой файл "CS" и чем его можно открыть?