Тестовые задания при приёме на работу

← →
АндрейК (2014-02-05 15:35) [0]

Здравствуйте я студент третьего курса соответствующей специальности.
Думаю из пользователей этого форума есть люди которые работают в серьезных фирмах и сталкиваются с кандидатами, которые пытаются устроиться на работу. Наверняка им дают тестовое задание и отправляют на 1-2 дня домой для решения поставленной задачи.

Поделитесь, если можно, подобного рода заданиями для самотестирования.

Можете и сюда написать задания, а я буду выкладывать в нужный срок решение.

← →
MonoLife © (2014-02-05 15:43) [1]

>дают тестовое задание и отправляют на 1-2 дня домой
такое разве бывает?

← →
sniknik © (2014-02-05 15:48) [2]

> такое разве бывает?
у другого входа фирмы объявление - "курсовые не дорого" :)... почему бы и нет?

← →
Jeer © (2014-02-05 16:18) [3]

Для начала, в художественно-приближенном виде, изложить в рукописном варианте на 2..3-х листах А4, свою историю по крайнему году жизни и работы.

← →
а в гугл заглянуть? (2014-02-05 16:24) [4]

в фирмах скорее всего будут давать задачи по своей (узкой) специфике
если нужны нетрудные абстрактные задачи, связанные с математикой - вот:
http://projecteuler.net/problems
кроме того, есть книги по конкретным языкам/технологиям с упражнениями (заданиями) в каждой главе
есть смысл выбрать интересную лично тебе тему посложнее и реализовать её, чтобы был пример своей работы, способный заменить тестовое задание на собеседованиях (выложить на github и т.п. и ссылаться в резюме)

← →
Дмитрий СС (2014-02-05 16:42) [5]

Вводится натуральное n.
Необходимо найти такие целые ненулевые A, B и C, чтобы выполнялось равенство:
A^n + B^n = C^n

← →
Kerk © (2014-02-05 16:43) [6]

> MonoLife © (05.02.14 15:43) [1]
>
> >дают тестовое задание и отправляют на 1-2 дня домой
>
> такое разве бывает?

Бывает конечно. Причем по разным причинам.

Не у всех есть ресурсы на проведение собеседований с каждым желающим, а даже простое тестовое задание отсечет 90% не умеющих программировать и 5% тех, кому вакансия не особо и интересна на самом деле.

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

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

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

← →
Слава Пестов1 (2014-02-05 16:58) [7]

> Дмитрий СС (05.02.14 16:42) [5]
>
> Вводится натуральное n.
> Необходимо найти такие целые ненулевые A, B и C, чтобы выполнялось
> равенство:
> A^n + B^n = C^n

В каком диапазоне?
А что брать и в лоб перебирать?

← →
Sergey Masloff (2014-02-05 17:03) [8]

sniknik © (05.02.14 15:48) [2]
>> такое разве бывает?
>у другого входа фирмы объявление - "курсовые не дорого" :)... почему бы и >нет?
Да кому такие курсовые нужны...

У меня есть действительно три набора заданий (sql, с# и delphi) которые направляю ДО очной встречи всем соискателям которых направляют кадры. Они совсем простые думаю их решение максимум на час-полтора всех вместе.
Да реально некоторые люди сразу отказываются отвечать и наверное часть тех кто мог бы подойти уходят. Но по крайней мере я отсеял те 90% которые ходят на собеседования зная чуть меньше чем нихрена и которые отнимали ТУЧУ времени.

Тут конечно не могу опубликовать и так уже часть собеседников приходит с явносписаными вариантами

← →
Kerk © (2014-02-05 17:04) [9]

> если нужны нетрудные абстрактные задачи, связанные с математикой - вот:
> http://projecteuler.net/problems

Мне кажется, оно слишком оторвано от реальной жизни, чтоб это рассматривать как тестовое задание. Если говорить о тренировке, я бы посоветовал попробовать написать хотя бы простенький векторный графический редактор. Работа уровня студенческого курсовика, а всякие полезные в реальной работе навыки придется использовать во весь рост.

← →
Empleado © (2014-02-05 17:05) [10]

> соответствующей специальности

?

← →
ухты (2014-02-05 17:10) [11]

интересно, а есть еще проффесии где дают тестовые задания, да еще и домой? да еще и так массово

← →
АндрейК (2014-02-05 17:12) [12]

> У меня есть действительно три набора заданий (sql, с# и
> delphi)

>
> Тут конечно не могу опубликовать и так уже часть собеседников
> приходит с явносписаными вариантами

Сергей, а если по почте?

← →
Kerk © (2014-02-05 17:19) [13]

> ухты (05.02.14 17:10) [11]
>
> интересно, а есть еще проффесии где дают тестовые задания,
> да еще и домой? да еще и так массово

В некоторых профессиях так вообще портфолио требуют. Массово :)

← →
а в гугл заглянуть? (2014-02-05 17:20) [14]

(не самые простые задания):
- вычисление заданного строкой арифметического выражения (скобки, функции - по желанию)
- векторный графический редактор (прямые, ломаные, многоугольники и т.п., выбор цвета, перемещение объектов и отдельных точек, выше всех/ниже всех; эллипсы, сектора, текст - по желанию)
(архитектура редактора - с классами, инкапсуляцией, наследованием)
- добавить редактору сохранение в файл и чтение из него, объединение, пересечение, вычитание многоугольников
- почтовый клиент (pop3 и smtp; навороты - по желанию)
- парсер сайта с новостями или объявлениями о покупке/продаже, с фильтрацией "особо интересного" и отправкой его через е-мэйл/смс

← →
ухты (2014-02-05 17:21) [15]

так и тут его требуют

← →
ухты (2014-02-05 17:22) [16]

> ухты (05.02.14 17:21) [15]
это к Kerk © (05.02.14 17:19) [13]

← →
Kerk © (2014-02-05 17:23) [17]

> ухты (05.02.14 17:21) [15]
>
> так и тут его требуют

Портфолио? Не сталкивался, у меня его нет.

← →
ухты (2014-02-05 17:25) [18]

> Kerk © (05.02.14 17:23) [17]
а трудовая не портфолио ли? по мне так оно и есть, а на собеседовании еще и рассказывать просят что и как было

← →
АндрейК (2014-02-05 17:25) [19]

> а в гугл заглянуть? (05.02.14 17:20) [14]

Это задание на пол года.

← →
а в гугл заглянуть? (2014-02-05 17:31) [20]

надо же, Керк опередил с редактором
добавлю: программе с простым интерфейсом (своей или чужой) приделать web-интерфейс (свой элементарный локальный web-сервер)

← →
а в гугл заглянуть? (2014-02-05 17:37) [21]

АндрейК> Это задание на пол года.
какое из?
нормальному программисту на любое хватит недели (и дня, чтобы уже хоть что-то заработало)
если для вас это полгода... то и спешить вам тогда особо не куда - учитесь пока себе (главное - программируйте каждый день)

← →
Sergey Masloff (2014-02-05 17:45) [22]

а в гугл заглянуть? (05.02.14 17:37) [21]
>нормальному программисту на любое хватит недели (и дня, чтобы уже хоть >что-то заработало)
Мне кажется для тестовой задачи это крутовать (любая из). Только мое личное мнение

← →
а в гугл заглянуть? (2014-02-05 17:49) [23]

> Sergey Masloff (05.02.14 17:45) [22]
> Мне кажется для тестовой задачи это крутовать (любая из). Только мое личное мнение

> а в гугл заглянуть? (05.02.14 16:24) [4]
> есть смысл выбрать интересную лично тебе тему посложнее и реализовать её, чтобы был пример своей работы, способный заменить тестовое задание на собеседованиях (выложить на github и т.п. и ссылаться в резюме)

← →
Rouse_ © (2014-02-05 17:52) [24]

> Поделитесь, если можно, подобного рода заданиями для самотестирования.

Ну напиши мне на rouse79@yandex.ru
Вышлю свой вариант таких задач, но только с условием их неразглашения (только для твоей собственной самоподготовки).

← →
Sergey Masloff (2014-02-05 17:53) [25]

а в гугл заглянуть? (05.02.14 17:49) [23]
> есть смысл выбрать интересную лично тебе тему посложнее и реализовать её,

А ну как вариант - хорошо

← →
Rouse_ © (2014-02-05 17:53) [26]

> Kerk © (05.02.14 17:23) [17]
> Портфолио? Не сталкивался, у меня его нет.

Здрассе приплыли... а это что?
http://roman.yankovsky.me/

← →
DVM © (2014-02-05 17:55) [27]

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

← →
Dimka Maslov © (2014-02-05 18:03) [28]

> В каком диапазоне?
> А что брать и в лоб перебирать?

Вы нам не годитесь. До свидания.

← →
Jeer © (2014-02-05 18:11) [29]

Я, как-то, в бытность преподом в Бауманском, давал студентам задачку:
12 способов запуска исполняемого файла *.exe в среде Windows [XP]

До сих пор, когда встречают - помнят:)

← →
АндрейК (2014-02-05 18:12) [30]

> Rouse_ © (05.02.14 17:52) [24]

Александр, я вам отправил пустое письмо. Жду ответа.

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

Зачем оно мне нужно. Конкурентов плодить))

← →
Rouse_ © (2014-02-05 18:16) [31]

> Jeer © (05.02.14 18:11) [29]
> Я, как-то, в бытность преподом в Бауманском, давал студентам
> задачку:
> 12 способов запуска исполняемого файла *.exe в среде Windows
> [XP]
>
> До сих пор, когда встречают - помнят:)

Их больше сотни, это если на вскидку...
Правда если использовать только честные способы, ну в районе 70/75-ти...

← →
Rouse_ © (2014-02-05 18:16) [32]

> АндрейК (05.02.14 18:12) [30]

Отправил.

← →
Дмитрий СС (2014-02-05 18:34) [33]

> Их больше сотни, это если на вскидку...
> Правда если использовать только честные способы, ну в районе
> 70/75-ти...

А что называть разными способами?

← →
Rouse_ © (2014-02-05 18:38) [34]

> А что называть разными способами?

Это то, что должен контролировать любой уважающий себя антивирус (если в самом простом виде) :)

← →
Дмитрий СС (2014-02-05 18:41) [35]

Тогда это хороший повод поспорить. Я считаю, что 70 это многовато :)

← →
АндрейК (2014-02-05 18:55) [36]

> Rouse_ © (05.02.14 18:38) [34]
Хорошее у вас задание.
Требует хорошей теор. базы и некоторого опыта программирования

С на наскока решил, ну может до 5 заданий

← →
Rouse_ © (2014-02-05 19:07) [37]

> Дмитрий СС (05.02.14 18:41) [35]
> Тогда это хороший повод поспорить. Я считаю, что 70 это
> многовато :)

Это уже не ко мне, а к разработчикам ОС :)

> АндрейК (05.02.14 18:55) [36]
> С на наскока решил, ну может до 5 заданий

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

← →
а в гугл заглянуть? (2014-02-05 19:07) [38]

delphi? возможно, заинтересуетесь тестами
http://www.delphikingdom.com/quintana/quintana.asp
http://www.specialist.ru/test/430
еще на odesk.com есть тест, да поищите сами

← →
Rouse_ © (2014-02-05 19:14) [39]

> АндрейК (05.02.14 18:55) [36]

Вот тебе еще до кучи:
http://alexander-bagel.blogspot.ru/2013/12/1.html
как решишь, читай правильный ответ тут:
http://alexander-bagel.blogspot.ru/2013/12/1_19.html

← →
АндрейК (2014-02-05 19:24) [40]

Удалено модератором

← →
Rouse_ © (2014-02-05 19:28) [41]

> АндрейК (05.02.14 19:24) [40]

Это давай уже по почте...
Твой пост удалю - во избежание.

← →
Дмитрий СС (2014-02-05 20:58) [42]

> http://www.delphikingdom.com/quintana/quintana.asp

http://www.delphikingdom.com/quintana/quintana.asp?ItemID=12
Не согласен с ответом на вопрос 1.

Задача поставлена как поставлена. А в поставленной задачи код является верным.

← →
vuk © (2014-02-05 21:04) [43]

to Дмитрий СС (05.02.14 20:58) [42]:

> Задача поставлена как поставлена. А в поставленной задачи
> код является верным.

Чтобы этот код являлся верным, необходимо выполнение некоторых предусловий, вополнения которых никто не обещал. А так, если оно даже скомпилится, то это, один хрен, потенциальный баг.

← →
Германн © (2014-02-05 21:17) [44]

> А так, если оно даже скомпилится

Хуже всего то, что он гарантировано скомпилится если специально не удалить то, что по умолчанию подставлено в шаблон модуля формы.

← →
vuk © (2014-02-05 21:31) [45]

to Германн © (05.02.14 21:17) [44]:

> если специально не удалить то, что по умолчанию подставлено
> в шаблон модуля формы.

Это да. Borland в свое время знатную свинью подложил вообще сделав эти переменные и дав возможность писать косой код. И мало того, Delphi, во всяком случае до XE включительно, умудрялась пихать их даже туда, где в них смысла нет ну вот совсем. Может, конечно, сейчас уже изменилось что, не знаю.

← →
ухты (2014-02-05 21:35) [46]

а на Вопрос №3 какой ответ правильный? :)

← →
Ega23 © (2014-02-05 22:02) [47]

> а на Вопрос №3 какой ответ правильный? :)

AV

← →
Jeer © (2014-02-05 22:16) [48]

>Их больше сотни, это если на вскидку...

Ага, не те студенты пошли уж:)

← →
Inovet © (2014-02-05 23:20) [49]

1. Загузить в память и передать управление, ну выделить там предварительно всё необходимое.
2. Открыть/распечатать файл, и пошагово на в голове/на бумажке выполнять.
Ещё какие способы?

← →
Jeer © (2014-02-05 23:24) [50]

>Inovet © (05.02.14 23:20) [49]

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

← →
Jeer © (2014-02-06 21:49) [51]

Прекрасный тест для большинства местных профи - реализовать подобное на Delphi :)

Анимация ветрового поля по Земле:
http://earth.nullschool.net

P.S.
Ну, а сам ресурс - очень познавательное "чтиво".
Особенно меня порадовали "ревущие сороковые" - бывал там в экспедициях на НИС.
Помню, что это такое.

← →
Jeer © (2014-02-06 22:01) [52]

P.P.S.
Просто вошел в нирвану, когда увидел пояс штиля на 30-й параллели с.ш.
До сих пор считал, что это не так глобально, хотя там мы какое-то время лежали в дрейфе на Крузенштерне.

← →
megavoid © (2014-02-08 12:18) [53]

А что, [5] A^n + B^n = C^n частенько соискатели доказывают? :)

← →
GEN++ © (2014-02-08 17:43) [54]

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

Реальная задача при поступлении на работу

← →
clickmaker © (2014-02-10 09:43) [55]

> 12 способов запуска исполняемого файла *.exe в среде Windows
> [XP]

а я знаю 13-й )
begin
ShellExecute(nil, nil, ParamStr(1), nil, nil, SW_SHOWNORMAL);
end;

← →
Юрий Зотов © (2014-02-10 15:10) [56]

> clickmaker © (10.02.14 09:43) [55]

ParamStr(0) гораздо лучше.

← →
Demo (2014-02-10 15:38) [57]

А задаете ли вы вопросы, типа: Почему люк круглый, можно ли утверждать что крокодил летает, если утверждать что все животные летают и тп? Я сталкивался с такими вопросами и был очень удивлен.

← →
Inovet © (2014-02-10 15:48) [58]

> [57] Demo (10.02.14 15:38)

Почему люк круглый? Много скормили железа.
можно ли утверждать что крокодил летает? Можно

← →
Ega23 © (2014-02-10 17:05) [59]

> Почему люк круглый,

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

> можно ли утверждать что крокодил летает, если утверждать
> что все животные летают

Можно.

← →
Inovet © (2014-02-10 17:56) [60]

> Почему люк круглый

Почему бутылка виски квадратная, а бутылка водки круглая?

← →
ухты (2014-02-10 20:29) [61]

ща ега все растлумачит, это его профиль,он тут мастер :)

← →
petr (2014-02-10 21:24) [62]

> Ega23 © (10.02.14 17:05) [59]
>
>
> > Почему люк круглый,
>
>
> Чтобы внутрь не проваливался.
>

а в европе люки часто квадратные, и не проваливаются. а колодцы почему круглые (на которые бабы с коромыслами ходят)?

← →
MsGuns © (2014-02-10 23:55) [63]

Все это фигня, тесты, резюмы, портфолии там всякие.
Главное, чтоб человек был хороший :)

← →
clickmaker © (2014-02-11 09:06) [64]

> колодцы почему круглые (на которые бабы с коромыслами ходят)
> ?

чтобы баба внутрь не провалилась?

← →
GEN++ © (2014-02-11 10:01) [65]

>Почему бутылка виски квадратная, а бутылка водки круглая?
КШ: "бабушка, бабушка а почему у тебя виски в квадратной бутылке?"
Б-ка: "а потому внученька, что квадратных пузырьков в ящик больше влазит
чем круглых"
КШ: "бабушка, бабушка а почему у тебя водка в круглой бутылке?"
Б-ка: "а потому внученька, что круглый пузырек держать удобнее и боя
в ящике меньше при перевозке"
Представитель ВПК из-за кровати: "И коктель Молотова дальше бросить можно"

← →
Inovet © (2014-02-11 10:41) [66]

> [65] GEN++ © (11.02.14 10:01)
> Представитель ВПК

Это Волк что ли там спрятался?

← →
Ega23 © (2014-02-11 10:45) [67]

> а в европе люки часто квадратные, и не проваливаются.

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

← →
Inovet © (2014-02-11 10:53) [68]

> [67] Ega23 © (11.02.14 10:45)
> люк при открытии сантехниками

У них бабы-с-вёдрами курглые, а мужики-сантехники квадратные.

← →
Inovet © (2014-02-11 10:55) [69]

И вообще, давно уже известно (в определённых кругах): квадратное  чтобы катить, круглое  чтобы носить.

← →
clickmaker © (2014-02-11 11:07) [70]

> круглый люк не провалится ни при каком раскладе, как его
> не крути

а в военное время?

← →
Ega23 © (2014-02-11 11:13) [71]

> а в военное время?

А в военное время все канализационные люки становятся танковыми. На изумленье супостату.

← →
GEN++ © (2014-02-11 11:16) [72]

>[66] Inovert "Это Волк что ли там спрятался?"

Спасибо, действительно за кроватью сидел волк
а представитель ВПК в чине подполковника подавал голос из
подпола (конечно, подпол из подпола)

← →
Inovet © (2014-02-11 12:35) [73]

> [72] GEN++ © (11.02.14 11:16)

Какая бабушка молодая у КШ. Ну это всё объясняет: волк пришёл в гости с виски, а подпол с водкой.

← →
Ega23 © (2014-02-11 12:47) [74]

Бабушка не молодая, но закалённая и своя в доску.

← →
Дмитрий Белькевич (2014-02-11 15:32) [75]

>А в военное время все канализационные люки становятся танковыми. На изумленье супостату.

Противотанковыми?

← →
Ega23 © (2014-02-11 15:34) [76]

> Противотанковыми?

Противотанковыми становятся дороги.

← →
clickmaker © (2014-02-11 16:13) [77]

> Противотанковыми становятся дороги

да им даже становиться не надо...

← →
Ega23 © (2014-02-11 16:42) [78]

> да им даже становиться не надо...

Rename - тоже action

← →
GEN++ © (2014-02-11 17:09) [79]

А что задачу из [54] решить слабо?????

← →
Ega23 © (2014-02-11 17:15) [80]

> А что задачу из [54] решить слабо?????

А я вообще условие не понял. Какие-то поносные матрицы, кубы навального, групповуха 3х3...

← →
Rouse_ © (2014-02-11 17:46) [81]

> GEN++ © (11.02.14 17:09) [79]
> А что задачу из [54] решить слабо?????

Я тож условие не понял :) Слова понятные, но в кучу чей-то не собираются :)

← →
картман © (2014-02-11 19:28) [82]

Почему в зеркале меняются местами право и лево, а не верх и низ?

← →
Rouse_ © (2014-02-11 20:14) [83]

> картман © (11.02.14 19:28) [82]
> Почему в зеркале меняются местами право и лево, а не верх
> и низ?

Смотря для какого реципиента, для обладающего диоптрическим зрением это верно, но это скорее исключение из правил :)

← →
clickmaker © (2014-02-11 20:15) [84]

> [82] картман © (11.02.14 19:28)

потому что ты обычно стоишь перед ним, а не лежишь

← →
Inovet © (2014-02-11 20:34) [85]

> [84] clickmaker © (11.02.14 20:15)

Либо  потому что зеркало обычно приделано к стене, а не к полу или потолку. Но тогда поменяются ещё и верх с низом. Для компенсации эффекта требуется 2 разных бутылки. См. предыдущую задачу.

← →
petr (2014-02-11 21:20) [86]

> Почему бутылка виски квадратная, а бутылка водки круглая?

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

подозреваю, что с люками какая-то такая же история.

← →
Rouse_ © (2014-02-11 21:48) [87]

> Inovet © (10.02.14 17:56) [60]
> Почему бутылка виски квадратная, а бутылка водки круглая?

Потому что это плохая водка и виски :)
Самая вкусная водка выпускается как раз в квадратных бутылках, а виски (как это ни странно) в круглых :)

← →
petr (2014-02-11 21:52) [88]

> Rouse_ © (11.02.14 21:48) [87]
>
>

вкусную можно и более дорогую тару разлить.
> а виски (как это ни странно) в круглых :)

ничего странного, традиция, коньяк в квадратных тоже редкость, вино тем более :) хотя с вином и технология может быть заточена на круглость, может его там переворачивают раз полгода или еще что

← →
vuk © (2014-02-11 21:53) [89]

to Rouse_ © (11.02.14 20:14) [83]:

> Смотря для какого реципиента, для обладающего диоптрическим
> зрением это верно, но это скорее исключение из правил :)

Подойди к зеркалу и закрой один глаз. :)

← →
Inovet © (2014-02-11 22:02) [90]

> [89] vuk © (11.02.14 21:53)
> закрой один глаз

Это будет монокулярное.

← →
vuk © (2014-02-11 22:04) [91]

to Inovet © (11.02.14 22:02) [90]:

> Это будет монокулярное.

Таки да, будет. Что-нибудь поменялось от того, что закрыли один глаз? Глаза ни при чем. :)

← →
Плохиш © (2014-02-11 22:11) [92]

Открою секрет - ни форма бутылки, ни вкус, ни стоимость никак между собой не связаны.

← →
Jeer © (2014-02-11 22:35) [93]

Мало кто знает, что чел и без зеркала видит перевернутое изображение:)

← →
Inovet © (2014-02-11 22:50) [94]

> [91] vuk © (11.02.14 22:04)
> > Это будет монокулярное.
>
> Таки да, будет

Ну. А у Розыча было про
> [83] Rouse_ © (11.02.14 20:14)
> для обладающего диоптрическим зрением это верно

← →
Inovet © (2014-02-11 22:53) [95]

> [93] Jeer © (11.02.14 22:35)
> Мало кто знает, что чел и без зеркала видит перевернутое изображение:)

Нейроны перевернут. Не зеркальное же.

← →
Inovet © (2014-02-11 22:56) [96]

Нужны две квадратных зеркальных бутылки виски или одна кгруглая зеркальная водки. Бывают такие?

← →
vuk © (2014-02-11 23:03) [97]

to Inovet © (11.02.14 22:50) [94]:

> Ну. А у Розыча было про

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

Но суть-то в том, что в зеркале ничего местами не меняется. :)

← →
GEN++ © (2014-02-11 23:21) [98]

>[81]Я тож условие не понял :) Слова понятные, но в кучу чей-то не собираются :)

В принципе - понятно, думать лень - это нормально.

Но все таки повторю условие другими словами.

Есть куб составленный из группы 4 х 4 х 4=64 шт кубиков единичного размера ребра
(метр, сантиметр, километр - не важно) . Из этого куба вытаскиваем
несколько кубиков и для полученной фигуры строим 3 проекции 4 х 4
виды: фронтальный, справа, сверху
Надо написать код который по этим 3-м проекциям восстановит (построит)
все возможные кубы имеющие эти проекции. Код должен делать восстановление куба для любой заданной комбинаций из 3-х проекций
(для каких то комбинаций проекций будет 1 решение для каких то вариантов
их будет несколько или вообще не будет решения)
ВВод исходных проекций может быть в виде задания 3-х матриц 4х4
например:
фронтальная вид сверху вид справа
1 0 1 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1
1 1 1 1 1 0 0 1 1 1 1 1

1 - есть кубик 0- нет кубика
вывод решения может быть в виде вывода 4-х матриц 4 х4
по каждому слою куба или графикой
время решения ограничено 1-м часом работы компа
время написания кода естественно существенно больше

← →
Стенка © (2014-02-11 23:31) [99]

> картман © (11.02.14 19:28) [82]
> Почему в зеркале меняются местами право и лево, а не верх и низ?

В зеркале левое слева остается, правое - справа.

> GEN++ © (11.02.14 23:21) [98]
> время решения ограничено 1-м часом работы компа

Очевидно, за это время совершенно невозможно перебрать все варианты.

← →
картман © (2014-02-11 23:36) [100]

> GEN++ © (11.02.14 23:21) [98]

а 0 тута - сквозная дырка?

← →
Inovet © (2014-02-11 23:40) [101]

> [100] картман © (11.02.14 23:36)
> а 0 тута  сквозная дырка?

0000  пропилы
0  проелы.

← →
Styx (2014-02-11 23:53) [102]

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

← →
Inovet © (2014-02-12 00:16) [103]

А я не понял какого чёрта на видах элементы несовпадают, которые одни и те же. Надо к этим матрицам изометрический чёртёж приложить, и вообще на нём их нарисовать, для понимания.

← →
GEN++ © (2014-02-12 10:13) [104]

>[102] .. либо задача про кубик решается в три строчки... если известна относительная ориентация проекций.

Ориентация естественно известна но решение в три строки????????

Недели 2 - это хорошо

>[103] .... на видах элементы несовпадают, которые одни и те же...
матирцы проекций я привел только в качестве примера их вида
они не являются конкретными проекциями реальной фигуры

← →
clickmaker © (2014-02-12 10:15) [105]

> решение в три строки????????
>
> Недели 2 - это хорошо

день, чтобы решить, остальные 13 - уложить решение в 3 строки

← →
GEN++ © (2014-02-12 10:21) [106]

>[105] ..день, чтобы решить...

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

← →
Ega23 © (2014-02-12 10:31) [107]

Уточнение: я правильно понимаю, что трёх проекций недостаточно для нахождения единственного решения, их (решений) может быть много? И за час работы требуется найти все, так?

← →
GEN++ © (2014-02-12 10:41) [108]

>[107]
Именно так! Есть варианты где число решений превышает 100
На это достаточно скоростной код тратит 3-4 минуты
Видимо целесообразно 1 проекцию или 1 слой кубика кодировать как биты
16-ти разрядного word

← →
Ega23 © (2014-02-12 10:44) [109]

> Видимо целесообразно 1 проекцию или 1 слой кубика кодировать
> как биты 16-ти разрядного word

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

← →
Inovet © (2014-02-12 13:59) [110]

> [104] GEN++ © (12.02.14 10:13)
> они не являются конкретными проекциями реальной фигуры

Не, ну нормально да? А бесцельная амортизация нейронов как.

← →
GEN++ © (2014-02-12 15:24) [111]

> [110] А бесцельная амортизация нейронов как.
Накладные расходы, издержки на среду обитания

← →
Rouse_ © (2014-02-12 19:39) [112]

> GEN++ ©

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

← →
Rouse_ © (2014-02-12 19:45) [113]

Да и время работы алгоритма при таком подходе явно не час...

← →
Kerk © (2014-02-12 19:56) [114]

> Rouse_ © (12.02.14 19:39) [112]

Вот тебе входные проекции :)

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Как твой метод догадается, что куб внутри пустой? :)

← →
Rouse_ © (2014-02-12 20:05) [115]

Исходя из этого:

> Надо написать код который по этим 3-м проекциям восстановит
> (построит)
> все возможные кубы имеющие эти проекции

и по твоим проекциям - куб полон.
Или я пропустил еще какое-то условие задачи?

← →
Kerk © (2014-02-12 20:08) [116]

> и по твоим проекциям - куб полон.

С чего бы? Это ведь проекции, а не рентген.

← →
Inovet © (2014-02-12 20:26) [117]

А тоже не понял про переборы. Известные в проекциях, неизвестные уходят на варианты кубов. По ним что ли перебор для их построения?

← →
Rouse_ © (2014-02-12 20:41) [118]

> Kerk © (12.02.14 20:08) [116]
> С чего бы? Это ведь проекции, а не рентген.

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

← →
Kerk © (2014-02-12 20:43) [119]

> Rouse_ © (12.02.14 20:41) [118]

>> все возможные кубы имеющие эти проекции

Трудно понять как-то иначе :)

← →
Kerk © (2014-02-12 20:45) [120]

> если проекция это только отображение первого слоя

Да елки, проекция - это не отображение первого слоя! Ты на в школе на черчении спал чтоль? :)

← →
Rouse_ © (2014-02-12 20:49) [121]

> Kerk © (12.02.14 20:45) [120]
> Да елки, проекция - это не отображение первого слоя! Ты
> на в школе на черчении спал чтоль? :)

Не спал, поэтому и не понимаю в чем затруднения в моей реализации алгоритма? :)

← →
Rouse_ © (2014-02-12 20:53) [122]

Мне кажется лучше сделать так:
GEN++ даст входные матрицы проекций и тот результат, который должен получится.
Отсюда и будем плясать (бо сам уж заинтересовался - чеж там хитрого такого) :)
Ну а после этого и можно рассмотреть варианты решений.

← →
Dennis I. Komarov © (2014-02-12 21:00) [123]

> Rouse_ © (12.02.14 19:39) [112]
>
> > GEN++ ©
>
> Задача ясна, первое что на вскидку вижу, кубический массив
> заполненный единицами и три прохода по векторам (X, Y, Z)
> со скидыванием в ноль по входным матрицам. В итоге остаются
> инициализированные единицами только те ячейки куба, которые
> соответствуют трем входным матрицам.
> Судя по всему неопределенностей здесь нет и время на реализацию
> минут пятнадцать.
> Я где-то ошибся?

Ну да,
шаг 1 - на полный куб накладываем 0-проекции (пропилы и проелы)
шаг 2 - по каждой стороне проекции вычисляем количество "1" (недоелы)
шаг 3 - в том месте где sum(недоелы) >=3 возможны варианты (т.е. невидимый кубик)
шаг 4 - вычисление значение невидимого кубика из расчета всех проекций
шаг 5 - количество неопределенных кубиков ˆ2 есть количество вариантов

← →
Dennis I. Komarov © (2014-02-12 21:03) [124]

шаг 3 - ..... >=2

← →
Kerk © (2014-02-12 21:04) [125]

> Rouse_ © (12.02.14 20:49) [121]
>
> > Kerk © (12.02.14 20:45) [120]
> > Да елки, проекция - это не отображение первого слоя! Ты
> > на в школе на черчении спал чтоль? :)
>
> Не спал, поэтому и не понимаю в чем затруднения в моей реализации
> алгоритма? :)

Положи тапок на лист бумаги, обведи его карандашом. Убери тапок. Что останется на бумаге? Рентген, верхний слой тапка или все же одна из его проекций? :)

← →
Kerk © (2014-02-12 21:05) [126]

> Dennis I. Komarov © (12.02.14 21:00) [123]

Да, места, где точно, нули определить легко. Дальше перебор. Вся задача сводится к сокращению этого перебора. Копчиком чувствую, что нужно посмотреть в сторону алгоритмов решения судоку :)

← →
Kerk © (2014-02-12 21:08) [127]

Если с тапком не получится, обведи банку с огурцами. Проверь видно ли на проекции, что в банке есть огурцы :)

← →
Dennis I. Komarov © (2014-02-12 21:15) [128]

> Да, места, где точно, нули определить легко. Дальше перебор.
> Вся задача сводится к сокращению этого перебора. Копчиком
> чувствую, что нужно посмотреть в сторону алгоритмов решения
> судоку :)

3. по сумме не нулевых элементов вычисляют где он не один, т.е. возможны различные варианты.
4. эти варианты накладываем на 0-проекции и на S-проекции - там где совпало с 0 или с 1 (на S) элемент однозначно определен, else может принимать оба значения (не противоречит исходным данным)

Все довольно однозначно, никаких переборов

← →
Dennis I. Komarov © (2014-02-12 21:26) [129]

> Копчиком чувствую, что нужно посмотреть в сторону алгоритмов
> решения судоку

Я делал, там сложнее.

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

Тут есть однозначные проекции и куча вариантов ответов, а не единственный правильный.

← →
Rouse_ © (2014-02-12 21:27) [130]

Сходил принял конячку - осмыслил решение :)

Допустим дано три проекции вида:

0000 0110 0110 0000

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

Отсюда строим алгоритм:
1. изначально бьем тунель из нулей по каждой оси
2. (тут два решения - умное и правильное)
2.1: умное - ищем группы кубов и убирая каждый из них - сверяемся с проекциями (оно нам надо?)
2.2: (правильное) Имея на руках только отсеченные кубы, бежим по ним всем и исключаем со сверкой с матрицами. Те кто не прошли сверку - в результат вывода не попадают.

Итого: время на реализацию 30 минут, время работы алгоритма менее секунды.

← →
Dennis I. Komarov © (2014-02-12 21:34) [131]

> Сходил принял конячку - осмыслил решение :)

Тебя допинг-контроль спалил :)

← →
Rouse_ © (2014-02-12 21:40) [132]

> Dennis I. Komarov © (12.02.14 21:34) [131]
> Тебя допинг-контроль спалил :)

Не - жена ща с полями Галуа разбирается, ей точно не до меня :)

← →
Dennis I. Komarov © (2014-02-12 21:51) [133]

> шаг 5 - количество неопределенных кубиков ˆ2 есть количество
> вариантов

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

> Допустим дано три проекции вида:
>
> 0000
> 0110
> 0110
> 0000

По нему 8 элементов однозначно не определены, но так как в любой проекции на них "1" в условиях не должно быть два "0" подряд

Проекции  это OR всех слоёв по оси. Я правильно понимаю?

> Проекции — это OR всех слоёв по оси. Я правильно понимаю?

true

> С какого перепугу?

Потому как все три проекции одинаковы (как я понял), и согласно им все крайние грани пусты. Остается внутри куб 2х2 из 8-ми элементов. Где я не прав?

> Остается внутри куб 2х2 из 8-ми элементов

2х2х2 разумеется...

Ну как минимум в том, что 2 х 2 = 8 :)

> Dennis I. Komarov © (12.02.14 22:09) [141]
>
> > Остается внутри куб 2х2 из 8-ми элементов
>
> 2х2х2 разумеется...

Ой плин - эт я затупил - сори, конечно 8 :)))

так, ну решение далее такое (совсем без перебора не придумал):

5 - цикл по всем неопределенным вариантам, на каждом формируем S-проекции (обозначим S2). Далее сравниваем если в S2-проекции элемент "0", а в исходной "1", тогда данный вариант противоречит условию

P.S.
Кстати, достаточно вычислить и проверить проекции S2 только этого элемента.

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

> GEN++ © (12.02.14 10:41) [108]
> Есть варианты где число решений превышает 100
> На это достаточно скоростной код тратит 3-4 минуты

Че-то много)
Можешь хоть один такой вариант привести?

← →
Styx (2014-02-13 00:20) [150]

> Ориентация естественно известна но решение в три строки?
> ???????

Тогда cube[i,j,k]=p1[i,j]*p2[j,k]*p3[i,k] обязательно будет решением.
Но если нужно найти все возможные решения и/или проверить проекции на совместимость - тогда, конечно, не три строки.

> Юрий Зотов © (13.02.14 00:01) [148]
> два профессиональных программиста не понимают механизмов передачи параметров

потамушта задурили людям головы всякой хренью вместо преподавания основ

> [149] Sha © (13.02.14 00:16)
> Можешь хоть один такой вариант привести?

Керк приводил

> [114] Kerk © (12.02.14 19:56)

4*4*4*4=256 вариантов только с 1 единицей в каждом слое отнимем из всего 2^(4*4*4*4). Так что ли? Что-то много получилось.

> Inovet © (13.02.14 00:26) [152]
> Керк приводил

мне кажется, что на расчет приведенного им варианта
потребуется гораздо меньше 3-4х минут

> [153] Sha © (13.02.14 00:33)
> мне кажется, что на расчет приведенного им варианта
> потребуется гораздо меньше 3-4х минут

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

> Inovet © (13.02.14 00:43) [154]
> Ну первое, получается, в реальности вообще невозможно сделать.

Почему невозможно?
Например, представить кубик 4х4х4 как 4 слоя размером 4х4.
Хотя мне больше нравится как int64 )

Может кто-нить накодит "input-output" в GUI?

Стандартизируем условие:
AX, AY, AZ: array[0..N-1, 0..N-1] of Byte; // Проекции куба

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

> Так это самое сложное в этой задаче)

скорее самое нудное и долгое, а время нема...

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

Я думал... ИМХО так проще для понимания алгоритма. Этот кубик можно упаковать в 8 байт, а проекцию в два, но не удобно для восприятия.
И сильно привяжется к N=4

> а проекцию в два,

пардонтес, в пол байта

проще договориться вводить данные из Memo (сейчас это модно),
а привязка к N=4 для учебной задачи даже хорошо,
можно посмотреть, как структура данных влияет на скорость

> проще договориться вводить данные из Memo (сейчас это модно),

ввод - ерунда, вот вывод множества...

> а привязка к N=4 для учебной задачи даже хорошо,
> можно посмотреть, как структура данных влияет на скорость

ну если задачу рассматривать как обучение битовым операциям... так об этом речи вроде не было...
мне лень :)

> Dennis I. Komarov © (13.02.14 14:55) [163]
> ввод - ерунда, вот вывод множества...

можно выводить количество и последний найденный,
хотя даже для [130] у меня не получается вручную подсчитать
количество решений

> ну если задачу рассматривать как обучение битовым операциям...

а че лень-то, там все решение в 10 строчек уложится ))

> можно выводить количество и последний найденный,
> хотя даже для [130] у меня не получается вручную подсчитать
>
> количество решений
>

там 256 потенциальных решений, из них нужно исключить те, которые противоречат исходным проекциям. Кроме как перебирать варианты, я пока ничего не придумал.
Если я не ошибаюсь, то там будет 2 * 2^6 = 128 решений, но это вычислено логически, а не математически.

> а че лень-то, там все решение в 10 строчек уложится ))

Если писать нормально, тогда не верю. У меня уже >50 и это без перебора.

> Как твой метод догадается, что куб внутри пустой? :)

надо вводить доп. обозначения - штрихпунктир...

> Dennis I. Komarov © (13.02.14 16:29) [165]
> Если писать нормально, тогда не верю.
> У меня уже >50 и это без перебора.

вечером напишу

>[156] Куда складывать решения?
В исходном варианте задания было так
"Наити решение (я)" где кол-во оствшихся в фигуреи кубиков будет минимально"
Но чтобы найти минимальное решение надо проверить все

>[159] Так это самое сложное в этой задаче)
И потом очень важно выбрать представление данных, упрощающее алгоритм.

В точку

Эту задачу давали при приеме на работу в одной Зеленоградской фирме
Условие было такое вот задание, срок 2 недели - решаете берем на работу
иначе - ну тут понятно.

> Но чтобы найти минимальное решение надо проверить все

А вот и нет...

> GEN++ © (13.02.14 16:51) [168]
> Эту задачу давали при приеме на работу в одной Зеленоградской
> фирме
> Условие было такое вот задание, срок 2 недели - решаете
> берем на работу
> иначе - ну тут понятно.

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

> У нас с этим как-то проще, мы по другим критериям отбор
> ведем :)

Количество и качество коньяка? :)))

> Dennis I. Komarov © (13.02.14 18:06) [171]
> Количество и качество коньяка? :)))

Это уже на психологическую совместимость с коллективом (тоже важный момент, кстати) :)

вот те самые 10 строчек, поехал домой дописывать остальное)

count:=0; sol:=-1; repeat; sol:=(sol+1) or cube; for d:=0 to dim do begin; temp:=-1; for p:=0 to bnd do temp:=mask[d,p] and sol shr (p*plane[d]) and temp; if temp<>proj[d] then goto next; end; inc(count); next: until sol=-1;

> вот те самые 10 строчек, поехал домой дописывать остальное)

У мни дома IDE нету... даже окон не осталось

а xCode пока не освоил...

А коменты к коду можно? Так без Розыча не разобрать, коньяк у него...

> Dennis I. Komarov © (13.02.14 19:57) [174]
> А коменты к коду можно?

Это быстрый вариант тупого перебора. Просто подсчитывает количество решений в count. В переменной sol сидит очередной 64-битный кандидат. Единственное достоинство этого варианта перебора в том, что благодаря инвертированному представлению данных (1 означает осутствие кубика), он позволяет при помощи (... or cube) проскакивать биты, где заведомо не может стоять кубик. Но тем не менее он делает много лишнего (а в свете [168] - очень много лишнего), например, он начинает перебор с 0, хотя очевидно, что минимальное необходимое число кубиков превышает максимальную площадь проекций. По идее тут нужна комбинация двоичного поиска для выбора числа кубиков и перебора сочетаний для этого числа кубиков.
Другое: цикл по d - цикл по количеству измерений (проекций), temp - проекция кандидата на решение, цикл по p - цикл по слоям текущего измерения, mask[d,p] - маски слоев (индикаторы принадлежности бита слою p измерения d), plane[d] - расстояние между соседними слоями по измерению d, proj[d] - проекция по измерению d.

> А коменты к коду можно? Так без Розыча не разобрать, коньяк
> у него...

Коньяк да, у меня, а воть декларация переменных у Сани, я сам пока что не вкуриваю в чего он тут наваял :)

тама все 64-битное, окромя переменных цикла и plane[]

> Sha © (13.02.14 20:37) [177]
> тама все 64-битное, окромя переменных цикла и plane[]

Пусть так, но алгоритм не читабелен и идеи выцепить не могу (увы...)

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

> Rouse_ © (13.02.14 20:53) [178]
> Пусть так, но алгоритм не читабелен

Есть такое дело. Ща ввод допишу уже, наверно, будет чуть яснее.

Ну идею я понял, но трэйсить в голове это...
Однако сей подход противоречит решению задачи, просто перебрать все варианты. Некие инъекции логики в этот подход будет довольно сложно реализовать :) А прочесть еще сложнее :)

> Dennis I. Komarov © (13.02.14 21:23) [180]
> Некие инъекции логики в этот подход

Этот подход любые инъекции только замедлят.
Годный подход описан в [175].

//Объемный куб состоит из 4х4х4 кубиков единичного размера. Некоторые из них прозрачные. //По 3-м заданным проекциям (фронтальная, сверху, справа) определить количество возможных фигур. //Ввод данных - в виде 3-х послойных матриц 4х4, вывод - в виде 4-х матриц. //Время вычислений - не более 1 часа. Найти решение с минимальным количеством кубиков. unit Cube4x4Form; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; const dim= 2; //номер последней проекции или размерность пространства - 1 )) bnd= 3; //номер последней строки (столбца, слоя) в проекции type TForm1 = class(TForm) memInput: TMemo; memDebug: TMemo; memOutput: TMemo; btnInput: TButton; btnSolution: TButton; procedure btnInputClick(Sender: TObject); procedure btnSolutionClick(Sender: TObject); end; var Form1: TForm1; implementation {$R *.dfm} // вид спереди, вид сверху, вид справа, // ближний слой ближний слой дальний слой // 0 1 2 3 0 16 32 48 0 16 32 48 // 4 5 6 7 1 17 33 49 4 20 36 52 // 8 9 10 11 2 18 34 50 8 24 40 56 // 12 13 14 15 3 19 35 51 12 28 44 60 //коэффициенты = расстояния между var // (спереди, сверху, справа) col: array[0..dim] of integer= (1, 16, 16); row: array[0..dim] of integer= (4, 1, 4); plane: array[0..dim] of integer= (16, 4, 1); zerocount: array[0..255] of byte; var //маски для выбора кубиков нужного слоя в нужном измерении mask: array[0..dim, 0..bnd] of int64; //проекции (спереди, сверху, справа), //после ввода инвертируем: единичный биты соответствуют сквозным дыркам proj: array[0..dim] of int64; //максимально заполненный куб, //после ввода инвертируем: единичный бит означает запрет размещения кубика на данном месте cube: int64; dataOK: boolean= false; const CRLF= #13#10; function GetData(const txt: AnsiString): boolean; var SL: TStringList; s: array[0..dim] of AnsiString; t: AnsiString; //u, v: AnsiString; ch: AnsiChar; d, c, r, p, i: integer; temp, extent: int64; begin; Result:=false; SL:=TStringList.Create; try SL.Text:=txt; for i:=SL.Count-1 downto 0 do begin; t:=Trim(SL[i]); if t="" then SL.Delete(i) else begin; if Length(t)<>1+bnd then exit; for c:=0 to bnd do if not (t[1+c] in ["0","1"]) then exit; SL[i]:=t; end; end; if SL.Count<>(dim+1)*(bnd+1) then exit; for d:=0 to dim do begin; SetLength(s[d],(bnd+1)*(bnd+1)*(bnd+1)); for r:=0 to bnd do begin; for c:=0 to bnd do begin; ch:=SL[d*(1+bnd)+r][1+c]; i:=r*row[d]+c*col[d]; for p:=0 to bnd do begin; s[d][1+i+p*plane[d]]:=ch; end; end; end; end; cube:=-1; extent:=0; for d:=0 to dim do begin; proj[d]:=0; for r:=0 to bnd do begin; for c:=0 to bnd do begin; i:=r*row[d]+c*col[d]; ch:=s[d][1+i]; //plane[0] temp:=1; temp:=temp shl i; if ch="1" then proj[d]:=proj[d] or temp; mask[d,0]:=mask[d,0] or temp; end; end; temp:=0; for p:=0 to bnd do begin; i:=p*plane[d]; temp:=temp or proj[d] shl i; if p<>0 then mask[d,p]:=mask[d,0] shl i; end; cube:=cube and temp; extent:=extent or temp; end; for d:=0 to dim do begin; temp:=-1; for p:=0 to bnd do begin; temp:=mask[d,p] and extent shr (p*plane[d]) and temp; end; if temp<>proj[d] then exit; //ошибка в исходных данных (проекции не согласованы) end; { t:=""; for d:=0 to dim do t:=t+s[d]+CRLF; Form1.memDebug.Text:=t; SetLength(t,(bnd+1)*(bnd+1)*(bnd+1)); SetLength(u,(bnd+1)*(bnd+1)*(bnd+1)); SetLength(v,(bnd+1)*(bnd+1)*(bnd+1)); temp:=cube; for i:=0 to (bnd+1)*(bnd+1)*(bnd+1)-1 do begin; t[1+i]:=AnsiChar(ord("0")+(temp and 1)); u[1+i]:=AnsiChar(ord("0")+i div 10); v[1+i]:=AnsiChar(ord("0")+i mod 10); temp:=temp shr 1; end; Form1.memDebug.Lines.Add(""); Form1.memDebug.Lines.Add(t); Form1.memDebug.Lines.Add(u); Form1.memDebug.Lines.Add(v); } cube:=not cube; for d:=0 to dim do proj[d]:=mask[d,0] and not proj[d]; for i:=0 to 255 do begin; d:=i; r:=0; for c:=0 to 7 do begin; if d and 1=0 then inc(r); d:=d shr 1; end; zerocount[i]:=r; end; Result:=true; finally SL.Free; end; end;

function GetSolutionText(const Solution: int64): AnsiString; var s: AnsiString; r, p, i, len: integer; temp: int64; begin; len:=(bnd+1)*(bnd+1)*(bnd+1); SetLength(s,len); temp:=not Solution; for i:=0 to len-1 do begin; s[1+i]:=AnsiChar(temp and 1 + ord("0")); temp:=temp shr 1; end; Result:=""; i:=1; for p:=0 to bnd do begin; Result:=Result + CRLF; for r:=0 to bnd do begin; Result:=Result+copy(s,i,bnd+1)+CRLF; i:=i+(bnd+1); end; end; end; function GetSolutionSize(const Solution: int64): integer; var i: integer; begin; Result:=0; i:=SizeOf(Solution)*8; repeat; i:=i-8; Result:=Result + zerocount[Solution shr i and 255]; until i=0; end; //Это быстрый вариант тупого перебора. Просто подсчитывает количество решений в Count. //В переменной sol сидит очередной кандидат. Единственное достоинство этого варианта перебора в том, //что благодаря инвертированному представлению данных (1 означает отсутствие кубика), //он позволяет при помощи (... or cube) проскакивать биты, где заведомо не может стоять кубик. //Он делает много лишнего, например, начинает перебор с 0, хотя очевидно, что необходимое //число кубиков не менее максимальной площади проекций. Вероятно, тут лучше подойдет //перебор сочетаний для возможных чисел кубиков. //Другое: цикл по d - цикл по количеству измерений (проекций), temp - проекция кандидата на решение, //цикл по p - цикл по слоям текущего измерения, mask[d,p] - маски слоев (индикаторы принадлежности //бита слою p измерения d), plane[d] - расстояние между соседними слоями по измерению d, //proj[d] - проекция по измерению d. procedure FindSolution(var Solution, Total, Count: int64; var Size: integer); var sol, temp: int64; d, p, i: integer; label next; begin; Total:=0; Size:=MaxInt; sol:=-1; repeat; sol:=(sol+1) or cube; for d:=0 to dim do begin; temp:=-1; for p:=0 to bnd do temp:=mask[d,p] and sol shr (p*plane[d]) and temp; if temp<>proj[d] then goto next; end; inc(Total); i:=GetSolutionSize(sol); if Size>=i then begin; if Size>i then begin; Size:=i; Solution:=sol; Count:=0; end; inc(Count); end; next: until sol=-1; end; procedure TForm1.btnInputClick(Sender: TObject); const InputMessages: array[boolean] of AnsiString= ("Oшибка во входных данных", "Данные введены успешно"); begin; memOutput.Text:=""; dataOK:=GetData(memInput.Text); memOutput.Lines.Add(InputMessages[dataOK]); end; procedure TForm1.btnSolutionClick(Sender: TObject); var Solution, Total, Count: int64; Size: integer; begin; if dataOK then begin; FindSolution(Solution, Total, Count, Size); memOutput.Lines.Add(Format("Всего найдено %d решений", [Total])); if Count>0 then begin; memOutput.Lines.Add(Format("Из них %d решений из %d кубиков", [Count, Size])); memOutput.Lines.Add("Одно из них приведено ниже"); memOutput.Lines.Add("(вид спереди, ближний слой - первый)"); memOutput.Lines.Add(GetSolutionText(Solution)); end; end; end; end.

Вход 0000 0110 0110 0000 0000 0110 0110 0000 0000 0110 0110 0000 Выход Данные введены успешно Всего найдено 35 решений Из них 2 решений из 4 кубиков Одно из них приведено ниже (вид спереди, ближний слой - первый) 0000 0000 0000 0000 0000 0010 0100 0000 0000 0100 0010 0000 0000 0000 0000 0000

>[168] Вообще суровые у вас критерии отбора :)
Хотя фиг знает, я же специфики не знаю - вероятно именно такой подход в чем-то оправдан (в данном случае).
У нас с этим как-то проще, мы по другим критериям отбор ведем :)

К счастью это не у нас. Начало, как Вы могли заметить интригующее
но вот концовка в совковом стиле:
2 с лишним года назад у меня сын заканчивал вуз и подыскивал себе
работу на будущее, имея средний опыт написания кода и для PC
и для микроконтроллеров. Так вот повозившись с этой задачей и написав
для решения код с ГУЕМ (я в задаче принимал участие в качестве скептика
из мозгового штурм) представил его в фирму. Директор направил его к
сотрудникам для оценки. Оценили работу так (эту задачу давали у них, как выяснилось, многим):
такой быстрый и находящий такое кол-во решений код еще не писал никто. После ознакомления с выводами сотрудников директор заявил (почти дословно)
"Ну ты это, проработай у нас пока так (т.е. бесплатно) а если мы увидим что ты прибыль приносишь то будем может быть и и зарплату (причем без указания размера) давать"

Так что "У нас с этим как-то проще, мы по другим критериям отбор ведем "
это обнадеживает.

Найдена опечатка в
procedure TForm1.btnSolutionClick(Sender: TObject); напечатано if Count>0 then begin; должно быть if Total>0 then begin;

> Выход
>
> Данные введены успешно
> Всего найдено 35 решений
> Из них 2 решений из 4 кубиков
> Одно из них приведено ниже
> (вид спереди, ближний слой - первый)

А время?

Но для внутреннего кубика 3х3х3 ищет уже около 3 сек.

И еще, если кто будет играть с приведенным кодом,
советую выкинуть из процедуры ввода проверку противоречивости проекций:

for d:=0 to dim do begin; temp:=-1; for p:=0 to bnd do begin; temp:=mask[d,p] and extent shr (p*plane[d]) and temp; end; if temp<>proj[d] then exit; //ошибка в исходных данных (проекции не согласованы) end;

Похоже, что-то я перемудрил там, а и без нее все прекрасно работает и отсекается.

← →
демотиватор (2014-02-17 15:13) [190]

А стоят ли такие выпендрежи и мозгодробилки, ну вот вы прошли отбор и вас взяли неизвестно куда в супер-пупер НИИ на з/п. в 20 тыс. рублей ... остановитесь и одумайтесь оно вам нужно жизнь то одна стоит ли ее в богом забытых конторах проводить за непонятные фуфелки?

Тестовые задания при приёме на работу Найти похожие ветки