Беседка - русскоязычный форум в Израиле: Задачка для программистов - Беседка - русскоязычный форум в Израиле

Перейти к содержимому

  • 2 Страниц +
  • 1
  • 2
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

Задачка для программистов (на любом языке)

#1 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 12 Сентябрь 2006 - 22:36

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

#2 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 13 Сентябрь 2006 - 07:51

:) Меня попросили решить подобное лет 7-8 назад..

Решений на самом деле много.. Некоторые - зависят от языка..
0

#3 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 13 Сентябрь 2006 - 14:10

Согласись, что приятная задача. :) Еще знаешь что-нибудь интересное такого типа?
0

#4 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 13 Сентябрь 2006 - 14:20

Я знаю другого типа :)

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

Есть и другие задачки такого типа :) В основном о системах реального времени..
Хотя.. есть и на алгоритмику... Сейчас вот участвую в конкурсе Гуглевом - там оригинальные задачки есть.
0

#5 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 13 Сентябрь 2006 - 15:16

Что за Гугель?
Почему не знаю ? :)
Ссылочку, please.
0

#6 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 13 Сентябрь 2006 - 15:22

Google™ Code Jam 2006

Но уже, увы :) Жди следующего раза.
Потому что раунд квалификации уже прошел. На прошлой неделе. Отобрали 1000 из тысяч 15-16. Следующий раунд завтра. Останутся 500...
0

#7 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 13 Сентябрь 2006 - 15:38

Большой Грызь, я не понял, а без регистрации сами задачки почитать где-нибудь можно?
И порешать ( порешить? ). :)
0

#8 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 13 Сентябрь 2006 - 15:41

:) Можно меня попросить :) Я приведу условия того, чего уже было.
0

#9 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 13 Сентябрь 2006 - 15:48

Прошу :)
0

#10 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 13 Сентябрь 2006 - 15:55

А как же с битами в обратном порядке? :)
Уже решил?

Просто в алгоритмических задачках тяжело проверять решение.. Ибо не единственное есть :)

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

На примерах.
В строке ABC три максимальных палиндрома: A, B и C. Каждая из этих частей строки АВС не может быть расширена до бОльшего палиндрома.
В строке АААА всего один максимальный палиндром: вся строка.
В строке АВАВ есть два максимальных палиндрома: АВА и ВАВ. Каждый из этих двух палиндромов не может быть расширен.

Задача.. Написать функцию, которая получает строку и возвращает кол-во максимальных палиндромов в оной.
Строк может быть длиной до 1000 символов.. Функция должна работать не более 2 секунд.
0

#11 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 14 Сентябрь 2006 - 03:33

Ну, "на пальцах" я понял как с палиндромами делать, а запрограммировать сложнее. :rudolph:
Биты в обратном порядке - догадываюсь, что какой-то хитрый прикол, которого я не знаю. Но я придумал совсем не хитрое и быстрое решение. Вопрос - достаточно ли быстрое? Как это определить?
0

#12 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 14 Сентябрь 2006 - 12:42

Напиши в личку насчет битов :rudolph:
0

#13 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 15 Сентябрь 2006 - 08:57

С битами решил :)
Лови еще одну :loool:

В некотором месте в памяти хранится текущее значение времени, состоящее из 4 байт и равное кол-ву секунд, проистекших с 1 января 1970-ого года.

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

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

Запрещать прерывания нельзя. Требуется надёжно прочитать точное текущее значение времени. Как это сделать?
0

#14 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 15 Сентябрь 2006 - 19:20

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

#15 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 15 Сентябрь 2006 - 19:27

Просмотр сообщенияБольшой Грызь (13.9.2006, 12:22) писал:

Google™ Code Jam 2006

Но уже, увы :) Жди следующего раза.
Потому что раунд квалификации уже прошел. На прошлой неделе. Отобрали 1000 из тысяч 15-16. Следующий раунд завтра. Останутся 500...


Ну как прошел раунд ? :loool:
0

#16 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 16 Сентябрь 2006 - 16:47

Просмотр сообщенияwith_hello (15.9.2006, 19:20) писал:

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

Ну, вообще-то измениться могут все байты вообще :coolio:)
А прошлое значение можно восстановить, как для старших, так и для младшего разряда :yes:
Если правильно подойти..
0

#17 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 16 Сентябрь 2006 - 16:48

Просмотр сообщенияwith_hello (15.9.2006, 19:27) писал:

Ну как прошел раунд ? :coolio:

541-е.. увы :yes: в пролёте.
Обидно с одной задачей.. Решение показали потом - в одну строку.
0

#18 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 17 Сентябрь 2006 - 03:41

Просмотр сообщенияБольшой Грызь (16.9.2006, 13:48) писал:

541-е.. увы :coolio: в пролёте.
Обидно с одной задачей.. Решение показали потом - в одну строку.


Ничего, еще наверстаешь.
0

#19 Пользователь офлайн   with_hello 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 198
  • Регистрация: 26 Февраль 06

Отправлено 17 Сентябрь 2006 - 03:43

Просмотр сообщенияБольшой Грызь (16.9.2006, 13:47) писал:

Ну, вообще-то измениться могут все байты вообще :coolio:)
А прошлое значение можно восстановить, как для старших, так и для младшего разряда :prop:
Если правильно подойти..


Я в личку подробно написал.
:blink:
0

#20 Пользователь офлайн   Большой Грызь 

  • Активный участник
  • PipPipPip
  • Группа: Участник
  • Сообщений: 298
  • Регистрация: 25 Июль 05
  • Город:Оттава, Канада
  • Интересы:Программирование, астрономия, фотография

Отправлено 17 Сентябрь 2006 - 06:22

Просмотр сообщенияwith_hello (17.9.2006, 3:41) писал:

Ничего, еще наверстаешь.

уже только в следующий раз :coolio:
0

  • 2 Страниц +
  • 1
  • 2
  • Вы не можете создать новую тему
  • Вы не можете ответить в тему

1 человек читают эту тему
0 пользователей, 1 гостей, 0 скрытых пользователей


Внешний вид