|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.10.2011, 19:41 | #1 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
профессионалам (задачи при приеме на работу)
прошу знающих кодеров решить две задачи, которые были предложены мне на собеседовании.
после ваших решений выложу то, что написал я. скажу заранее, на работу не взяли специально не даю свои решения сразу, хочу увидеть ваши правильные мысли. 1. в некой стране принимается денежная реформа. максимальная купюра будет расцениваться в от 1 до 100000 единиц. известно, что каждая более мелкая купюра должна быть делителем каждой более крупной. например 1 7 14 42. написать функцию, на вход которой подается номинал максимальной купюры (n), а функция возвращает максимальное количество различных купюр. будет принято то сочетание, в котором максимальное количество различных купюр. 2. задана строка длиной не более 50 символов. написать функцию, которая возвращает минимальное количество символов, которое необходимо дописать в конец строки чтобы строка стала симметричной. на задания давался час |
20.10.2011, 20:16 | #2 |
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
Я не профессионал, и мне лень писать код, поэтому я могу предложить лишь алгоритм:
1. В массив выписываем делители за O(n), делаем такую линейную по памяти динамику за O(n^2): a[k] - длина макс. посл-ти, заканч. на k-том элементе, a[0] = 1, a[k] = i from [1 .. k-1] max{a[i] + 1}, при a[k] кратном a[i]. Ответ - максимальное число в массиве динамики. 2. Перебор по кол-ву добавляемых символов 1..длины строки, проверка на возможность - поиск нового центра строки и проверка на полиндромность внутренней части. Задания не трудные, за час вполне. Это куда собеседование?
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
20.10.2011, 21:38 | #3 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
еще?
мои решения координально другие. ку да, напишу позже |
21.10.2011, 01:41 | #4 |
Форумчанин
Регистрация: 29.09.2010
Сообщений: 636
|
ну 2 вот так решил
Код:
а, да, про 50 символов не учитывал ограничение, ну и для простоты со string работал, хотя с С-массивом не сложнее было бы. про 1 попож подумаю)) Последний раз редактировалось onewho; 21.10.2011 в 01:46. |
22.10.2011, 17:41 | #5 |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
Первая задача. Тут решение фактически задано уже в условии:
1) Факторизовать введенное число, сохраняя делители в массиве. Например, для числа 42 результатом будет {1, 2, 3, 7}. Количество элементов в полученном массиве и будет ответом, собсна. 2) Для получения номиналов всех купюр нужно взять единицу, и в произвольном порядке домножать ее на все остальные элементы массива. Но в задаче это не требуется, впринципе, потому хватит и первого пункта. Ну а для второй решение уже написали в предыдущем комментарии. |
22.10.2011, 19:39 | #6 | ||
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
Цитата:
Цитата:
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
||
22.10.2011, 20:13 | #7 |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
|
22.10.2011, 20:20 | #8 |
Форумчанин
Регистрация: 29.09.2010
Сообщений: 636
|
чует моё сердце в 1 задаче рекурсия нужна
|
22.10.2011, 20:21 | #9 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
не, ребят, 1 2 3 7 не канают же. например 7 на 3 не делится.
|
22.10.2011, 20:37 | #10 | |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
И еще раз. Цитата:
Взяли единицу, домножаем ее на делители, взятые в произвольном порядке. Например так: 1*2=2 2*3=6 6*7=42 Итоговые номиналы - 1, 2, 6, 42. Или так: 1*7=7 7*2=14 14*3=42 Итоговые номиналы: 1, 7, 14, 42. Ну или так: 1*3=3 3*7=21 21*2=42 Итоговые номиналы: 1, 3, 21, 42. Есть еще варианты, всего их будет (n-1)! , где n - количество делителей, в приведенном примере это будет 3!=6. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
при каких условиях алгоритм закончит свою работу? | незнайка_на_земле | Помощь студентам | 3 | 08.03.2011 00:40 |
Тестовые задания при приеме на работу | crazy horse | Свободное общение | 3 | 02.07.2010 21:32 |
Вопрос профессионалам | Maxim1 | Общие вопросы C/C++ | 0 | 02.06.2010 01:14 |
К профессионалам | kenta | Microsoft Office Word | 1 | 12.05.2010 16:51 |